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

# dkc2Tree.h

単純な2分木 [詳細]

`#include "dkcOSIndependent.h"`
`#include "dkcMemoryPool.h"`

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

このグラフは、どのファイルから直接、間接的にインクルードされているかを示しています。

ソースコードを見る。

## 構成
struct | dkc_2TreeNode
struct | dkc_2TreeRoot
| いわいるRootみたいなもの。 [詳細]
struct | dkc_2TreeExist
| dkc2TreeExist()で返される結果の構造体 [詳細]
## マクロ定義
#define | dkcm2TREE_SET_BUFFER_ERROR(tr) (tr != edk_NoValueToProcess && DKUTIL_FAILED(tr))
| dkc2TreeSetBuffer()がエラーをチェックするマクロ TRUE だったらエラー
## 型定義
typedef dkc_2TreeNode | DKC_2TREE_NODE
typedef dkc_2TreeRoot | DKC_2TREE_ROOT
| いわいるRootみたいなもの。
typedef dkc_2TreeExist | DKC_2TREE_EXIST
| dkc2TreeExist()で返される結果の構造体
## 関数
DKC_EXTERN DKC_2TREE_ROOT *WINAPI | dkcAlloc2TreeRoot (size_t key_size, size_t pool_num, DKC_COMPARE_TYPE compare, size_t max_num)
| ２分木領域を得る。
DKC_EXTERN int WINAPI | dkcFree2TreeRoot (DKC_2TREE_ROOT **ptr)
| dkcAllocNew2Tree()で確保したリスト領域と内部バッファを削除。dkcAllocNew2Treeと対。
DKC_EXTERN int WINAPI | dkc2TreeInsert (DKC_2TREE_ROOT *ptr, const void *Key, const void *data, size_t data_size)
| 新しいデータを挿入する。
DKC_EXTERN int WINAPI | dkc2TreeChain (DKC_2TREE_ROOT *dest, DKC_2TREE_ROOT *src)
DKC_EXTERN int WINAPI | dkc2TreeErase (DKC_2TREE_ROOT *ptr, DKC_2TREE_NODE *node)
DKC_EXTERN DKC_2TREE_EXIST WINAPI | dkc2TreeExist (DKC_2TREE_ROOT *ptr, const DKC_2TREE_NODE *node)
| nodeに入れたポインタがptr内に存在するかどうか調べる存在したら結果値を返す。
DKC_EXTERN int WINAPI | dkc2TreeEraseFromKey (DKC_2TREE_ROOT *ptr, const void *Key)
DKC_EXTERN DKC_2TREE_NODE *WINAPI | dkc2TreeFindEqual (DKC_2TREE_ROOT *ptr, const void *Key)
DKC_EXTERN DKC_2TREE_NODE *WINAPI | dkc2TreeFindMinimalGreater (DKC_2TREE_ROOT *ptr, const void *Key)
DKC_EXTERN DKC_2TREE_NODE *WINAPI | dkc2TreeFindMaximumLess (DKC_2TREE_ROOT *ptr, const void *Key)
DKC_EXTERN int WINAPI | dkc2TreeGetBuffer (DKC_2TREE_NODE *ptr, void *data, size_t size)
| ２分木構造体内に保存しているデータをもらう
DKC_EXTERN int WINAPI | dkc2TreeSetBuffer (DKC_2TREE_NODE *ptr, const void *data, size_t size)
| ２分木構造体に保存しているデータ領域にデータを入れる。 ２分木構造体内のバッファが足りない場合はこの関数の内部で拡張してくれる。

## 説明

単純な2分木

から:
  2004/3/xx , 2004/12/13

覚え書き:
  Basic Binary Tree... 単純な2分木です。 AVLとかではなく単純な2分木でdkcSingleList.hの シングルリストと同じ結果をもたらすことがあります。 （詳しくはアルゴリズムの参考書とかを見てください＾＾；

「作る気無し。(　´ゝ`)　」だったが、AVL木を作るのにちとイメージが浮かばなかったため練習のため作る事にした。

define DKUTIL_C_2TREE_FAST_IMPL を宣言すると、ノード一つ分が＋４バイト多く使用しますが、ノード指定での削除処理をO(1)にします。

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

## マクロ定義

#define dkcm2TREE_SET_BUFFER_ERROR | ( | tr |  | ) | (tr != edk_NoValueToProcess && DKUTIL_FAILED(tr))

| dkc2TreeSetBuffer()がエラーをチェックするマクロ TRUE だったらエラー dkc2Tree.h の 149 行で定義されています。 参照元 alloc_set().

## 型定義

typedef struct dkc_2TreeExist DKC_2TREE_EXIST

| dkc2TreeExist()で返される結果の構造体

typedef struct dkc_2TreeNode DKC_2TREE_NODE

typedef struct dkc_2TreeRoot DKC_2TREE_ROOT

| いわいるRootみたいなもの。

## 関数

DKC_EXTERN int WINAPI dkc2TreeChain | ( | DKC_2TREE_ROOT * | dest,
|  | DKC_2TREE_ROOT * | src
| ) |

| ２分木をチェインする。 destにsrcを繋げる。 destの２分木とsrcの二分木をソートしてdestに出力する。 しかし、 destの方にsrcと重複するKeyがあった場合は失敗する。 destとsrcの状態が違っていたら失敗する。 戻り値: enum edkResultのどれかが返る。

DKC_EXTERN 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 }

DKC_EXTERN 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_EXTERN 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_EXTERN 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_EXTERN 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_EXTERN 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 }

DKC_EXTERN 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 }

DKC_EXTERN 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 }

DKC_EXTERN 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 }

DKC_EXTERN 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 }

DKC_EXTERN 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 }