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

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_NODEalloc_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)
 2分木領域を得る。
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_NODEdkcAlloc2TreeInsertPoint (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_NODEfind_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)
 2分木構造体内に保存しているデータをもらう
int WINAPI dkc2TreeSetBuffer (DKC_2TREE_NODE *ptr, const void *data, size_t size)
 2分木構造体に保存しているデータ領域にデータを入れる。 2分木構造体内のバッファが足りない場合はこの関数の内部で拡張してくれる。


説明

作者:
d金魚
から:
2004/12/13
覚え書き:
参考文献:C言語による最新アルゴリズム事典 tree.c

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


マクロ定義

#define DKUTIL_C_2TREE_C
 

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


関数

static DKC_INLINE void* alloc_2tree_node DKC_2TREE_ROOT root,
size_t  data_size
[static]
 

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

参照先 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.c67 行で定義されています。

参照先 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.c338 行で定義されています。

参照先 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.c386 行で定義されています。

参照先 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.c471 行で定義されています。

参照先 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.c637 行で定義されています。

参照先 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.c742 行で定義されています。

参照先 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.c825 行で定義されています。

参照先 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
 

2分木構造体内に保存しているデータをもらう

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

参照先 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.c292 行で定義されています。

参照先 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
 

2分木構造体に保存しているデータ領域にデータを入れる。 2分木構造体内のバッファが足りない場合はこの関数の内部で拡張してくれる。

戻り値:
size==0だとedk_NoValueToProcessを返す。精巧だと edk_SUCCEEDED

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

参照先 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.c285 行で定義されています。

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
 

2分木領域を得る。

引数:
key_size[in] キーのサイズを設定する。
pool_num[in] プールの容量
compare[in] 比較関数へのポインタ qsort()と同じ規格
max_num[in] 二分木の最大容量を設定する。0xFFFFFFFFでOK
戻り値:
DKC_2TREE_ROOT領域を返す。NULLだと失敗。

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

参照先 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.c208 行で定義されています。

参照先 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.c239 行で定義されています。

参照先 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.c250 行で定義されています。

参照先 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.c161 行で定義されています。

参照先 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.c90 行で定義されています。

参照先 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.c667 行で定義されています。

参照先 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.c55 行で定義されています。

参照先 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.c151 行で定義されています。

参照先 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.c436 行で定義されています。

参照先 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 }


dkutil_cに対してSat Sep 10 09:24:00 2005に生成されました。  doxygen 1.4.4