メインページ | アルファベット順一覧 | 構成 | ファイル一覧 | 構成メンバ | ファイルメンバ | 関連ページ

# dkc2Tree.c

`#include "dkc2Tree.h"`
`#include "dkcStdio.h"`
`#include "dkcStack.h"`
`#include "dkcMemoryStream.h"`

dkc2Tree.cのインクルード依存関係図

ソースコードを見る。

## マクロ定義
#define | DKUTIL_C_2TREE_C
## 関数
static DKC_INLINE void * | alloc_2tree_node (DKC_2TREE_ROOT *root, size_t data_size)
static DKC_INLINE void | free_2tree_node (DKC_2TREE_ROOT *root, DKC_2TREE_NODE **node)
static DKC_INLINE DKC_2TREE_NODE * | alloc_set (DKC_2TREE_ROOT *ptr, const void *Key, const void *data, size_t data_size)
static DKC_INLINE void | erase_tree_with_node (DKC_2TREE_ROOT *ptr, DKC_2TREE_NODE **leaf_node)
DKC_2TREE_ROOT *WINAPI | dkcAlloc2TreeRoot (size_t key_size, size_t pool_max, DKC_COMPARE_TYPE compare, size_t max_num)
| ２分木領域を得る。
static DKC_INLINE void | free_2tree_root (DKC_2TREE_ROOT *root)
DKC_INLINE int | dkcFree2TreeWithVector (DKC_2TREE_ROOT *ptr)
void | dkcFree2TreeReflexive (DKC_2TREE_ROOT *ptr, DKC_2TREE_NODE **pp)
| ppから左、右についた葉を削除
int | dkcFree2TreeReflexiveBegin (DKC_2TREE_ROOT *ptr)
int WINAPI | dkcFree2TreeRoot (DKC_2TREE_ROOT **ptr)
| dkcAllocNew2Tree()で確保したリスト領域と内部バッファを削除。dkcAllocNew2Treeと対。
static DKC_2TREE_NODE * | dkcAlloc2TreeInsertPoint (DKC_2TREE_NODE *ptr, int Key)
int WINAPI | dkc2TreeInsert (DKC_2TREE_ROOT *ptr, const void *Key, const void *data, size_t data_size)
| 新しいデータを挿入する。
int WINAPI | dkc2TreeErase (DKC_2TREE_ROOT *ptr, DKC_2TREE_NODE *node)
int WINAPI | dkc2TreeEraseFromKey (DKC_2TREE_ROOT *ptr, const void *Key)
static int WINAPI | tree_exist_reflexive (DKC_2TREE_ROOT *ptr, DKC_2TREE_NODE *node, DKC_2TREE_NODE **leaf_ptr, const DKC_2TREE_NODE *target, DKC_2TREE_NODE *parent, DKC_2TREE_EXIST *re)
DKC_2TREE_EXIST WINAPI | dkc2TreeExist (DKC_2TREE_ROOT *ptr, const DKC_2TREE_NODE *node)
| nodeに入れたポインタがptr内に存在するかどうか調べる存在したら結果値を返す。
DKC_2TREE_NODE *WINAPI | dkc2TreeFindEqual (DKC_2TREE_ROOT *ptr, const void *Key)
static DKC_2TREE_NODE * | find_lg_base (DKC_2TREE_ROOT *ptr, const void *Key, BOOL isGreater)
DKC_2TREE_NODE *WINAPI | dkc2TreeFindMaximumLess (DKC_2TREE_ROOT *ptr, const void *Key)
DKC_2TREE_NODE *WINAPI | dkc2TreeFindMinimalGreater (DKC_2TREE_ROOT *ptr, const void *Key)
int WINAPI | dkc2TreeGetBuffer (DKC_2TREE_NODE *ptr, void *data, size_t size)
| ２分木構造体内に保存しているデータをもらう
int WINAPI | dkc2TreeSetBuffer (DKC_2TREE_NODE *ptr, const void *data, size_t size)
| ２分木構造体に保存しているデータ領域にデータを入れる。 ２分木構造体内のバッファが足りない場合はこの関数の内部で拡張してくれる。

## 説明

作者:
  d金魚

から:
  2004/12/13

覚え書き:
  参考文献：Ｃ言語による最新アルゴリズム事典 tree.c

dkc2Tree.c で定義されています。

## マクロ定義

#define DKUTIL_C_2TREE_C

| dkc2Tree.c の 10 行で定義されています。

## 関数

static DKC_INLINE void* alloc_2tree_node | ( | DKC_2TREE_ROOT * | root,
|  | size_t | data_size
| ) | `[static]`

| dkc2Tree.c の 18 行で定義されています。 参照先 dkc_2TreeNode::data, dkc_2TreeNode::data_size, dkcAllocateFast(), dkcSameObjectPoolAlloc(), dkcSameObjectPoolRecycle(), dkc_2TreeNode::key, dkc_2TreeRoot::key_ac, dkc_2TreeNode::left, NULL, dkc_2TreeRoot::obj_ac, dkc_2TreeNode::right, と dkc_2TreeRoot::sentinel. 参照元 alloc_set(), と dkcAlloc2TreeRoot().
    00019 {
    00020
    00021     DKC_2TREE_NODE *np = NULL;
    00022     void *data = NULL;
    00023     void *key = NULL;
    00024     np = (DKC_2TREE_NODE *)dkcSameObjectPoolAlloc(root->obj_ac);
    00025     //np = (DKC_2TREE_NODE *)dkcAllocate(sizeof(DKC_2TREE_NODE));
    00026
    00027     if(NULL==np){
    00028         return NULL;
    00029     }
    00030     key = dkcSameObjectPoolAlloc(root->key_ac);
    00031     if(NULL==key){
    00032         goto Error;
    00033     }
    00034     if(0 != data_size){
    00035
    00036         data = dkcAllocateFast(data_size);
    00037         if(NULL==data){
    00038             goto Error;
    00039         }
    00040     }
    00041
    00042     np->data = data;
    00043     np->key = key;
    00044     np->data_size = data_size;
    00045     np->right = np->left = root->sentinel;
    00046
    00047
    00048     return np;
    00049 Error:
    00050     dkcSameObjectPoolRecycle(root->key_ac,key);
    00051     dkcSameObjectPoolRecycle(root->obj_ac,np);
    00052     return NULL;
    00053 }

static DKC_INLINE DKC_2TREE_NODE* alloc_set | ( | DKC_2TREE_ROOT * | ptr,
|  | const void * | Key,
|  | const void * | data,
|  | size_t | data_size
| ) | `[static]`

| dkc2Tree.c の 67 行で定義されています。 参照先 alloc_2tree_node(), dkc2TreeSetBuffer(), dkcm2TREE_SET_BUFFER_ERROR, free_2tree_node(), dkc_2TreeNode::key, dkc_2TreeRoot::key_size, と NULL. 参照元 dkc2TreeInsert().
    00069 {
    00070     DKC_2TREE_NODE *np;
    00071     int tr;
    00072
    00073     np  = alloc_2tree_node(ptr,data_size);
    00074     if(NULL==np){
    00075         return NULL;
    00076     }
    00077     tr = dkc2TreeSetBuffer(np,data,data_size);
    00078     //if(tr != edk_NoValueToProcess && DKUTIL_FAILED(tr)){
    00079     if(dkcm2TREE_SET_BUFFER_ERROR(tr)){
    00080         goto Error;
    00081     }
    00082
    00083     memcpy(np->key,Key,ptr->key_size);
    00084     return np;
    00085 Error:
    00086     free_2tree_node(ptr,&np);
    00087     return NULL;
    00088 }

int WINAPI dkc2TreeErase | ( | DKC_2TREE_ROOT * | ptr,
|  | DKC_2TREE_NODE * | node
| ) |

| dkc2Tree.c の 338 行で定義されています。 参照先 dkc2TreeExist(), erase_tree_with_node(), FALSE, dkc_2TreeExist::isExist, dkc_2TreeExist::leaf_ptr, NULL, と dkc_2TreeRoot::sentinel.
    00339 {
    00340
    00341     DKC_2TREE_EXIST ex;
    00342     if(NULL==node || node == ptr->sentinel){
    00343         return edk_FAILED;
    00344     }
    00345     ex = dkc2TreeExist(ptr,node);
    00346     if(FALSE==ex.isExist){
    00347         return edk_FAILED;
    00348     }
    00349     erase_tree_with_node(ptr,ex.leaf_ptr);
    00350
    00351     return edk_SUCCEEDED;
    00352 }

int WINAPI dkc2TreeEraseFromKey | ( | DKC_2TREE_ROOT * | ptr,
|  | const void * | Key
| ) |

  | 引数:
  | ptr[in] | 削除したいNodeへのキー
dkc2Tree.c の 386 行で定義されています。 参照先 dkc_2TreeRoot::compare, erase_tree_with_node(), dkc_2TreeNode::key, dkc_2TreeRoot::key_size, NULL, dkc_2TreeRoot::root, と dkc_2TreeRoot::sentinel.
    00387 {
    00388     DKC_2TREE_NODE **p = &(ptr->root);
    00389     int tr;
    00390     DKC_COMPARE_TYPE compare = ptr->compare;
    00391
    00392     if(NULL==(*p)){
    00393         return edk_FAILED;
    00394     }
    00395
    00396     //番兵
    00397     memcpy(ptr->sentinel->key,Key,ptr->key_size);
    00398
    00399     for(;;){
    00400         tr = compare(Key,(*p)->key);
    00401         if(0==tr){//同じキーがある
    00402             break;
    00403         }
    00404         if(tr < 0){
    00405             p = &((*p)->left);
    00406         }else{
    00407             p = &((*p)->right);
    00408         }
    00409     }
    00410     if(*p == ptr->sentinel)
    00411     {//見つからず
    00412         return edk_FAILED;
    00413     }
    00414
    00415     erase_tree_with_node(ptr,p);
    00416     //return dkc2TreeErase(ptr,p);
    00417     //return dkc2TreeErase(ptr,p,(*p));
    00418     return edk_SUCCEEDED;
    00419
    00420 }

DKC_2TREE_EXIST WINAPI dkc2TreeExist | ( | DKC_2TREE_ROOT * | ptr,
|  | const DKC_2TREE_NODE * | node
| ) |

| nodeに入れたポインタがptr内に存在するかどうか調べる存在したら結果値を返す。 dkc2Tree.c の 471 行で定義されています。 参照先 FALSE, dkc_2TreeExist::isExist, dkc_2TreeExist::leaf_ptr, dkc_2TreeNode::left, dkc_2TreeExist::node, NULL, dkc_2TreeExist::parent, dkc_2TreeNode::right, dkc_2TreeRoot::root, dkc_2TreeRoot::sentinel, tree_exist_reflexive(), と TRUE. 参照元 dkc2TreeErase().
    00472 {
    00473     DKC_2TREE_NODE *root = ptr->root;
    00474     DKC_2TREE_EXIST re;
    00475     int t;
    00476
    00477     re.isExist = FALSE;
    00478     re.leaf_ptr = NULL;
    00479     re.node = ptr->sentinel;
    00480     re.parent = re.node;
    00481
    00482     if(ptr->root == ptr->sentinel){//中には何も無し･･･
    00483         goto End;
    00484     }
    00485     if(ptr->root == node){
    00486         re.isExist = TRUE;
    00487         //re.leaf_ptr = NULL;
    00488         re.node = ptr->root;
    00489         re.parent = NULL;
    00490         goto End;
    00491     }
    00492
    00493     //左
    00494     t = tree_exist_reflexive(ptr,root->left,&(root->left),node,
    00495         NULL,&re);
    00496     if(t != 0){
    00497         goto End;
    00498     }
    00499
    00500     //右
    00501     tree_exist_reflexive(ptr,root->right,&(root->right),node,
    00502         NULL,&re);
    00503
    00504
    00505 End:
    00506     return re;
    00507 }

DKC_2TREE_NODE* WINAPI dkc2TreeFindEqual | ( | DKC_2TREE_ROOT * | ptr,
|  | const void * | Key
| ) |

  | 引数:
  | Key[in] | key ID
戻り値: 見つかったらDKC_2TREEへのポインタを返す。見つからない場合はNULL dkc2Tree.c の 637 行で定義されています。 参照先 dkc_2TreeRoot::compare, dkcmASSERT, dkc_2TreeNode::key, dkc_2TreeRoot::key_size, dkc_2TreeNode::left, NULL, dkc_2TreeNode::right, dkc_2TreeRoot::root, と dkc_2TreeRoot::sentinel.
    00638 {
    00639     DKC_2TREE_NODE *it = ptr->root;
    00640     DKC_COMPARE_TYPE compare = ptr->compare;
    00641     int tr;
    00642
    00643     dkcmASSERT(compare);
    00644
    00645     //番兵
    00646     memcpy(ptr->sentinel->key,Key,ptr->key_size);
    00647     for(;;){
    00648
    00649         tr = compare(Key,it->key);
    00650         if(0==tr){
    00651             break;
    00652         }
    00653         if(tr < 0){
    00654             it = it->left;
    00655         }else{
    00656             it = it->right;
    00657         }
    00658
    00659     }
    00660     if(it == ptr->sentinel){//見つからん
    00661         return NULL;
    00662     }
    00663     return it;
    00664 }

DKC_2TREE_NODE* WINAPI dkc2TreeFindMaximumLess | ( | DKC_2TREE_ROOT * | ptr,
|  | const void * | Key
| ) |

| 覚え書き: 条件 同じキーが見つかったら次が対象 大きいキー -> 小さいキー だったら そのときのが対象 最初から小さかったら大きいのから再探索 0 初期 前が大きいキー 1 dkc2Tree.c の 742 行で定義されています。 参照先 dkc_2TreeRoot::compare, dkcmASSERT, dkcmNOT_ASSERT, dkc_2TreeNode::key, dkc_2TreeNode::left, NULL, dkc_2TreeRoot::root, と dkc_2TreeRoot::sentinel.
    00743 {
    00744
    00745     DKC_2TREE_NODE *it = ptr->root,*st = ptr->sentinel;
    00746     DKC_2TREE_NODE *save = st;
    00747     //*save;
    00748     DKC_COMPARE_TYPE compare = ptr->compare;
    00749     int tr;
    00751     int state = 0;
    00752
    00753     dkcmASSERT(compare);
    00754
    00755     for(;;){
    00756
    00757         if(it == st){
    00758             dkcmNOT_ASSERT(NULL==it);
    00759             if(NULL==it){//と、いうかありえない･･･
    00760                 break;
    00761             }
    00762             switch(state){
    00763             case 1:
    00764                 return save;
    00765             case 2:
    00766                 return it;
    00767             }
    00768             it = NULL;
    00769             break;
    00770         }
    00771
    00772         tr = compare(Key,it->key);
    00773
    00774         if(tr==0){//同じの見つかったら次に左
    00775             if(it->left == st){//つーか、終わりでしたから･･･
    00776                 return NULL;
    00777             }
    00778             return it->left;
    00779         }
    00780
    00781         if(tr > 0){//Keyの方が大きい
    00782             switch(state){
    00783             case 0:
    00784                 state = 1;
    00785                 break;
    00786             case 1:
    00787                 return save;
    00788             case 2:
    00789                 return it;
    00790                 break;
    00791             default:
    00792                 state = 0;
    00793             }
    00794             save = it;
    00795             //
    00796             it = it->left;
    00797
    00798
    00799         }else{//Keyの方がちっこい
    00800             switch(state){
    00801             case 0:
    00802                 state = 2;
    00803                 break;
    00804             }
    00805             save = it;
    00806
    00807             it = it->left;
    00808
    00809         }
    00810
    00811
    00812     }
    00813
    00814     return it;
    00815
    00816
    00817 }

DKC_2TREE_NODE* WINAPI dkc2TreeFindMinimalGreater | ( | DKC_2TREE_ROOT * | ptr,
|  | const void * | Key
| ) |

| 覚え書き: MinimalGreaterの条件 同じキーが見つかったら次が対象 小さいキー -> 大きいキー だったら そのときのが対象 最初から大きかったら小さいのから再探索 dkc2Tree.c の 825 行で定義されています。 参照先 dkc_2TreeRoot::compare, dkcmASSERT, dkcmNOT_ASSERT, dkc_2TreeNode::key, NULL, dkc_2TreeNode::right, dkc_2TreeRoot::root, と dkc_2TreeRoot::sentinel.
    00826 {
    00827
    00828     DKC_2TREE_NODE *it = ptr->root,*st = ptr->sentinel;
    00829     DKC_2TREE_NODE *save = st;
    00830     //*save;
    00831     DKC_COMPARE_TYPE compare = ptr->compare;
    00832     int tr;
    00833     //0 初期 / 1 前がKeyの方が小さいキー / 2 前がKeyの方が大きいキー
    00834     //
    00835     int state = 0;
    00836
    00837     dkcmASSERT(compare);
    00838
    00839     for(;;){
    00840         if(it == st){
    00841             dkcmNOT_ASSERT(NULL==it);
    00842             if(NULL==it){//と、いうかありえない･･･
    00843                 break;
    00844             }
    00845             switch(state){
    00846             case 1:
    00847                 return save;
    00848             case 2:
    00849                 return it;
    00850             }
    00851             it = NULL;
    00852             break;
    00853         }
    00854         tr = compare(Key,it->key);
    00855
    00856
    00857         if(tr==0){//同じの見つかったら次にデカイのは右
    00858             if(it->right == st){//つーか、終わりでしたから･･･
    00859                 return NULL;
    00860             }
    00861             return it->right;
    00862         }
    00863
    00864
    00865         if(tr > 0){//Keyの方が大きい
    00866
    00867             switch(state){
    00868             case 0:
    00869                 state = 2;
    00870                 break;
    00871             }
    00872             save = it;
    00873             //Keyの方が大きいからitはより大きいのを調べる
    00874             it = it->right;
    00875
    00876         }else{//Keyの方がちっこい
    00877             switch(state){
    00878             case 0:
    00879                 state = 1;
    00880                 break;
    00881             case 1:
    00882                 return save;
    00883             case 2:
    00884                 return it;
    00885                 break;
    00886             default:
    00887                 state = 0;
    00888             }
    00889             save = it;
    00890             //ちっこいからでかいのに移る
    00891             it = it->right;
    00892
    00893         }
    00894
    00895     }
    00896
    00897
    00898     return it;
    00899
    00900 }

int WINAPI dkc2TreeGetBuffer | ( | DKC_2TREE_NODE * | ptr,
|  | void * | data,
|  | size_t | size
| ) |

| ２分木構造体内に保存しているデータをもらう dkc2Tree.c の 903 行で定義されています。 参照先 dkc_2TreeNode::data, dkc_2TreeNode::data_size, と dkc_memcpy_zc().
    00903                                                                         {
    00904     return dkc_memcpy_zc(data,size,ptr->data,ptr->data_size);
    00905 }

int WINAPI dkc2TreeInsert | ( | DKC_2TREE_ROOT * | ptr,
|  | const void * | Key,
|  | const void * | data,
|  | size_t | data_size
| ) |

| 新しいデータを挿入する。 dkc2Tree.c の 292 行で定義されています。 参照先 alloc_set(), dkc_2TreeRoot::compare, dkc_2TreeNode::key, dkc_2TreeRoot::key_size, NULL, dkc_2TreeNode::right, dkc_2TreeRoot::root, と dkc_2TreeRoot::sentinel.
    00294 {
    00295     typedef DKC_2TREE_NODE *DKC_2TREE_NODE_PTR;
    00296     int cmp;
    00297     DKC_2TREE_NODE_PTR *p, q;
    00298     DKC_COMPARE_TYPE compare = ptr->compare;
    00299
    00300     p = &(ptr->root);
    00301
    00302     //番兵
    00303     memcpy(ptr->sentinel->key,Key,ptr->key_size);
    00304
    00305     for(;;){
    00306         cmp = compare(Key, (*p)->key);
    00307         if(0==cmp){
    00308             break;
    00309         }
    00310         if (cmp < 0){
    00311             p = &((*p)->left );
    00312         }else{
    00313             p = &((*p)->right);
    00314         }
    00315     }
    00316
    00317     if (*p != ptr->sentinel)
    00318     {//登録済み
    00319         return edk_FAILED;
    00320     }
    00321
    00322     q = alloc_set(ptr,Key,data,data_size);
    00323     if(NULL==q){
    00324         return edk_OutOfMemory;
    00325     }
    00326
    00327     q->left = ptr->sentinel;
    00328   q->right = *p;
    00329   *p = q;
    00330 #ifdef DEBUG
    00331     //printf("key = %d\n",*(int *)(q->key));
    00332 #endif
    00333     return edk_SUCCEEDED;
    00334 }

int WINAPI dkc2TreeSetBuffer | ( | DKC_2TREE_NODE * | ptr,
|  | const void * | data,
|  | size_t | size
| ) |

| ２分木構造体に保存しているデータ領域にデータを入れる。 ２分木構造体内のバッファが足りない場合はこの関数の内部で拡張してくれる。 戻り値: size==0だとedk_NoValueToProcessを返す。精巧だと edk_SUCCEEDED dkc2Tree.c の 907 行で定義されています。 参照先 dkc_2TreeNode::data, dkc_2TreeNode::data_size, dkc2TreeSetBuffer(), dkc_memcpy_zc(), dkcReallocate(), と NULL. 参照元 alloc_set(), と dkc2TreeSetBuffer().
    00907                                                                               {
    00908     int t;
    00909     void *np = NULL;
    00910     if(size == 0){
    00911         return edk_NoValueToProcess;
    00912     }
    00913     t = dkc_memcpy_zc(ptr->data,ptr->data_size,data,size);
    00914
    00915     if(DKUTIL_FAILED(t))
    00916     {
    00917         t = dkcReallocate(&np,size,&(ptr->data));
    00918         if(DKUTIL_FAILED(t)){
    00919             return t;
    00920         }
    00921         ptr->data = np;
    00922         ptr->data_size = size;
    00923         return dkc2TreeSetBuffer(ptr,data,size);
    00924     }
    00925     return t;
    00926 }

static DKC_2TREE_NODE* dkcAlloc2TreeInsertPoint | ( | DKC_2TREE_NODE * | ptr,
|  | int | Key
| ) | `[static]`

| dkc2Tree.c の 285 行で定義されています。
    00285                                                                             {
    00286
    00287
    00288 }

DKC_2TREE_ROOT* WINAPI dkcAlloc2TreeRoot | ( | size_t | key_size,
|  | size_t | pool_num,
|  | DKC_COMPARE_TYPE | compare,
|  | size_t | max_num
| ) |

  | ２分木領域を得る。 引数:
  | key_size[in] | キーのサイズを設定する。
  | pool_num[in] | プールの容量
  | compare[in] | 比較関数へのポインタ qsort()と同じ規格
  | max_num[in] | 二分木の最大容量を設定する。0xFFFFFFFFでOK
戻り値: DKC_2TREE_ROOT領域を返す。NULLだと失敗。 dkc2Tree.c の 115 行で定義されています。 参照先 alloc_2tree_node(), dkc_2TreeRoot::compare, dkcAllocate(), dkcAllocSameObjectPool(), dkcFree(), dkcFreeSameObjectPool(), dkc_2TreeRoot::key_ac, dkc_2TreeRoot::key_size, dkc_2TreeNode::left, dkc_2TreeRoot::max_num, dkc_2TreeRoot::now_num, NULL, dkc_2TreeRoot::obj_ac, dkc_2TreeRoot::pool_max, dkc_2TreeNode::right, dkc_2TreeRoot::root, と dkc_2TreeRoot::sentinel.
    00116 {
    00117     DKC_2TREE_ROOT *root = dkcAllocate(sizeof(DKC_2TREE_ROOT));
    00118     if(NULL==root){
    00119         return NULL;
    00120     }
    00121     root->key_ac = dkcAllocSameObjectPool(key_size,pool_max,NULL,NULL);
    00122     if(NULL==root->key_ac){
    00123         goto Error;
    00124     }
    00125
    00126     root->obj_ac = dkcAllocSameObjectPool(sizeof(DKC_2TREE_NODE),pool_max,NULL,NULL);
    00127     if(NULL==root->obj_ac){
    00128         goto Error;
    00129     }
    00130     root->max_num = max_num;
    00131     root->key_size = key_size;
    00132     root->pool_max = pool_max;
    00133     root->compare = compare;
    00134     root->now_num = 0;
    00135     root->sentinel = alloc_2tree_node(root,0);
    00136
    00137     if(NULL==root->sentinel){
    00138         goto Error;
    00139     }
    00140     //番兵を入れておく
    00141     root->root = root->sentinel;
    00142     //無限ループにならないようにコーディングしなくては･･･
    00143     root->sentinel->left = root->sentinel->right = root->sentinel;
    00144     return root;
    00145 Error:
    00146     dkcFreeSameObjectPool(&(root->key_ac));
    00147     dkcFree(&root);
    00148     return NULL;
    00149 }

void dkcFree2TreeReflexive | ( | DKC_2TREE_ROOT * | ptr,
|  | DKC_2TREE_NODE ** | pp
| ) |

| ppから左、右についた葉を削除 dkc2Tree.c の 208 行で定義されています。 参照先 erase_tree_with_node(), dkc_2TreeNode::left, dkc_2TreeNode::right, と dkc_2TreeRoot::sentinel. 参照元 dkcFree2TreeReflexiveBegin().
    00209 {
    00210
    00211     //DKC_2TREE_NODE *root = ptr->root;
    00212     DKC_2TREE_NODE *l,*r;
    00213     DKC_2TREE_NODE *node = *pp;
    00214
    00215     if(node==ptr->sentinel)
    00216     {
    00217         return;
    00218     }
    00219
    00220     l = node->left;
    00221     r = node->right;
    00222
    00223
    00224
    00225     dkcFree2TreeReflexive(ptr,&l);
    00226     dkcFree2TreeReflexive(ptr,&r);
    00227
    00228     if(node->left != ptr->sentinel)
    00229         erase_tree_with_node(ptr,&(node->left));
    00230     if(node->right != ptr->sentinel)
    00231         erase_tree_with_node(ptr,&(node->right));
    00232     return;
    00233
    00234 }

int dkcFree2TreeReflexiveBegin | ( | DKC_2TREE_ROOT * | ptr | ) |

| dkc2Tree.c の 239 行で定義されています。 参照先 dkcFree2TreeReflexive(), erase_tree_with_node(), dkc_2TreeRoot::root, と dkc_2TreeRoot::sentinel. 参照元 dkcFree2TreeRoot().
    00239                                                    {
    00240     if(ptr->sentinel==ptr->root){
    00241         goto End;
    00242     }
    00243     //rootから左、右についた葉を削除
    00244     dkcFree2TreeReflexive(ptr,&(ptr->root));
    00245     erase_tree_with_node(ptr,&(ptr->root));
    00246 End:
    00247     return edk_SUCCEEDED;
    00248 }

int WINAPI dkcFree2TreeRoot | ( | DKC_2TREE_ROOT ** | ptr | ) |

| dkcAllocNew2Tree()で確保したリスト領域と内部バッファを削除。dkcAllocNew2Treeと対。 DKC_2TREEをデリート (リンクしてあるリストも削除します。 一つだけの要素を削除したい場合はdkcErase2Treeを使ってください。） 覚え書き: 必ず使用したあとはこれを呼んでください。 dkc2Tree.c の 250 行で定義されています。 参照先 dkcAllocStack(), dkcFree2TreeReflexiveBegin(), dkcFree2TreeWithVector(), dkcFreeStack(), free_2tree_root(), と NULL.
    00250                                                  {
    00251
    00252     int result;
    00253
    00254     if(NULL==ptr || NULL==*ptr){
    00255         return edk_ArgumentException;
    00256     }
    00257
    00258 #if 0
    00259     {
    00260
    00261         DKC_STACK *stack;
    00262         stack = dkcAllocStack(100,sizeof(DKC_2TREE_NODE *));
    00263         if(NULL==stack) return edk_FAILED;
    00264
    00265
    00266         result = dkcFree2TreeWithStack((*ptr),stack);
    00267
    00268         dkcFreeStack(&stack);
    00269     }
    00270 #elif 0
    00271     result = dkcFree2TreeWithVector((*ptr));
    00272 #else
    00273     //dkcFree2TreeReflexive((*ptr),(*ptr)->root);
    00274     //result = edk_SUCCEEDED;
    00275     result = dkcFree2TreeReflexiveBegin((*ptr));
    00276
    00277 #endif
    00278     free_2tree_root((*ptr));
    00279
    00280     (*ptr) = NULL;
    00281     return result;
    00282
    00283 }

DKC_INLINE int dkcFree2TreeWithVector | ( | DKC_2TREE_ROOT * | ptr | ) |

| dkc2Tree.c の 161 行で定義されています。 参照先 dkcAllocMemoryStream(), dkcMemoryStreamNowOffset(), dkcMemoryStreamPointer(), dkcMemoryStreamWrite(), free_2tree_node(), dkc_2TreeNode::left, dkc_2TreeRoot::now_num, NULL, dkc_2TreeNode::right, と dkc_2TreeRoot::root. 参照元 dkcFree2TreeRoot().
    00161                                                           {
    00162     DKC_2TREE_NODE *it;
    00163     size_t se,i;
    00164     DKC_MEMORYSTREAM *ms;
    00165     it =  ptr->root;
    00166
    00167     ms = dkcAllocMemoryStream(sizeof(DKC_2TREE_NODE *) * ptr->now_num);
    00168     if(NULL==ms){
    00169         return edk_FAILED;
    00170     }
    00171
    00172     for(;;){
    00173
    00174         if(NULL != it){
    00175             if(it->left){
    00176                 dkcMemoryStreamWrite(ms,it->left,sizeof(DKC_2TREE_NODE *));
    00177                 it = it->left;
    00178                 continue;
    00179             }
    00180             if(it->right){
    00181                 dkcMemoryStreamWrite(ms,it->right,sizeof(DKC_2TREE_NODE *));
    00182                 it = it->right;
    00183                 continue;
    00184             }
    00185         }else{
    00186             dkcMemoryStreamWrite(ms,it,sizeof(DKC_2TREE_NODE *));
    00187             break;
    00188         }
    00189
    00190     }
    00191     it = (DKC_2TREE_NODE *)dkcMemoryStreamPointer(ms);
    00192     se = dkcMemoryStreamNowOffset(ms);
    00193     for(i = 0;i<se;i++,it++){
    00194         free_2tree_node(ptr,&it);
    00195     }
    00196
    00197     return edk_SUCCEEDED;
    00198
    00199
    00200 }

static DKC_INLINE void erase_tree_with_node | ( | DKC_2TREE_ROOT * | ptr,
|  | DKC_2TREE_NODE ** | leaf_node
| ) | `[static]`

| dkc2Tree.c の 90 行で定義されています。 参照先 free_2tree_node(), dkc_2TreeNode::left, dkc_2TreeNode::right, と dkc_2TreeRoot::sentinel. 参照元 dkc2TreeErase(), dkc2TreeEraseFromKey(), dkcFree2TreeReflexive(), と dkcFree2TreeReflexiveBegin().
    00091 {
    00092     DKC_2TREE_NODE *target = (*leaf_node);
    00093     DKC_2TREE_NODE **p = leaf_node, **q,  *s;
    00094
    00095     if(target == ptr->sentinel){
    00096         return;
    00097     }
    00098     if      (target->right == ptr->sentinel) *p = target->left;
    00099     else if (target->left  == ptr->sentinel) *p = target->right;
    00100     else {
    00101         q = &(target->left);
    00102         while ((*q)->right != ptr->sentinel){
    00103             q = &((*q)->right);
    00104         }
    00105         s = *q;  *q = s->left;
    00106         s->left = target->left;
    00107         s->right = target->right;
    00108         *p = s;
    00109     }
    00110     free_2tree_node(ptr,&target);
    00111
    00112 }

static DKC_2TREE_NODE* find_lg_base | ( | DKC_2TREE_ROOT * | ptr,
|  | const void * | Key,
|  | BOOL | isGreater
| ) | `[static]`

| dkc2Tree.c の 667 行で定義されています。 参照先 dkc_2TreeRoot::compare, dkcmASSERT, dkc_2TreeNode::key, NULL, dkc_2TreeNode::right, dkc_2TreeRoot::root, と dkc_2TreeRoot::sentinel.
    00668 {
    00669     DKC_2TREE_NODE *it = ptr->root,*st = ptr->sentinel;
    00670     DKC_2TREE_NODE *save = st;
    00671     //*save;
    00672     DKC_COMPARE_TYPE compare = ptr->compare;
    00673     int tr;
    00674     //0 初期 / 1 前がKeyの方が小さいキー / 2 前がKeyの方が大きいキー
    00675     //
    00676     int state = 0;
    00677
    00678     dkcmASSERT(compare);
    00679
    00680     for(;;){
    00681         if(it == st || NULL==it){
    00682             it = NULL;
    00683             break;
    00684         }
    00685         if(isGreater){
    00686             tr = compare(Key,it->key);
    00687         }else{
    00688             tr = compare(it->key,Key);
    00689         }
    00690
    00691         if(tr==0){//同じの見つかったら次にデカイのは右
    00692             return it->right;
    00693         }
    00694
    00695         if(tr > 0){//Keyの方が大きい
    00696             /*if(1==state){
    00697                 return it;
    00698             }else{
    00699                 state = 0;
    00700             }*/
    00701             switch(state){
    00702             case 0:
    00703                 state = 2;
    00704                 break;
    00705             }
    00706             save = it;
    00707             //Keyの方が大きいからitはより大きいのを調べる
    00708             it = it->right;
    00709
    00710         }else{//Keyの方がちっこい
    00711             switch(state){
    00712             case 0:
    00713                 state = 1;
    00714                 break;
    00715             case 1:
    00716                 return save;
    00717             case 2:
    00718                 return it;
    00719                 break;
    00720             default:
    00721                 state = 0;
    00722             }
    00723             save = it;
    00724             //ちっこいからでかいのに移る
    00725             it = it->right;
    00726
    00727         }
    00728
    00729     }
    00730
    00731     return it;
    00732
    00733 }

static DKC_INLINE void free_2tree_node | ( | DKC_2TREE_ROOT * | root,
|  | DKC_2TREE_NODE ** | node
| ) | `[static]`

| dkc2Tree.c の 55 行で定義されています。 参照先 dkc_2TreeNode::data, dkcFree(), dkcmNOT_ASSERT, dkcSameObjectPoolRecycle(), dkc_2TreeNode::key, dkc_2TreeRoot::key_ac, NULL, と dkc_2TreeRoot::obj_ac. 参照元 alloc_set(), dkcFree2TreeWithVector(), erase_tree_with_node(), と free_2tree_root().
    00056 {
    00057     DKC_2TREE_NODE *n = (*node);
    00058     dkcmNOT_ASSERT(NULL==n);
    00059     dkcFree(&(n->data));
    00060
    00061     dkcSameObjectPoolRecycle(root->key_ac,n->key);
    00062
    00063     dkcSameObjectPoolRecycle(root->obj_ac,n);
    00064     //dkcFree(node);
    00065
    00066 }

static DKC_INLINE void free_2tree_root | ( | DKC_2TREE_ROOT * | root | ) | `[static]`

| dkc2Tree.c の 151 行で定義されています。 参照先 dkcFree(), dkcFreeSameObjectPool(), free_2tree_node(), dkc_2TreeRoot::key_ac, dkc_2TreeRoot::obj_ac, と dkc_2TreeRoot::sentinel. 参照元 dkcFree2TreeRoot().
    00151                                                             {
    00152     free_2tree_node(root,&(root->sentinel));
    00153     dkcFreeSameObjectPool(&(root->key_ac));
    00154     dkcFreeSameObjectPool(&(root->obj_ac));
    00155     dkcFree(&root);
    00156
    00157 }

static int WINAPI tree_exist_reflexive | ( | DKC_2TREE_ROOT * | ptr,
|  | DKC_2TREE_NODE * | node,
|  | DKC_2TREE_NODE ** | leaf_ptr,
|  | const DKC_2TREE_NODE * | target,
|  | DKC_2TREE_NODE * | parent,
|  | DKC_2TREE_EXIST * | re
| ) | `[static]`

| 戻り値: 0見つからない 1見つかった dkc2Tree.c の 436 行で定義されています。 参照先 dkc_2TreeExist::isExist, dkc_2TreeExist::leaf_ptr, dkc_2TreeNode::left, dkc_2TreeExist::node, NULL, dkc_2TreeExist::parent, dkc_2TreeNode::right, dkc_2TreeRoot::sentinel, と TRUE. 参照元 dkc2TreeExist().
    00440 {
    00441     int t;
    00442     if(ptr->sentinel == node){
    00443         return 0;
    00444     }
    00445     if(node == target){
    00446         re->isExist = TRUE;
    00447         re->leaf_ptr = leaf_ptr;
    00448         re->node = node;
    00449         re->parent = parent;
    00450         return 1;
    00451     }
    00452     if(parent == NULL){
    00453         parent = node;
    00454     }
    00455     //左
    00456     t = tree_exist_reflexive(ptr,node->left,&(node->left),target,node,re);
    00457     if(t != 0){
    00458         return t;
    00459     }
    00460
    00461     //右
    00462     t = tree_exist_reflexive(ptr,node->right,&(node->right),target,node,re);
    00463     if(t != 0){
    00464         return t;
    00465     }
    00466
    00467     //見つからない･･･。
    00468     return 0;
    00469 }