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

# dkc2Tree.c

説明を見る。

    00001
    00010 #define DKUTIL_C_2TREE_C
    00011
    00012 #include "dkc2Tree.h"
    00013 #include "dkcStdio.h"
    00014 #include "dkcStack.h"
    00015 #include "dkcMemoryStream.h"
    00016
    00017
    00018 static DKC_INLINE void *alloc_2tree_node(DKC_2TREE_ROOT *root,size_t data_size)
    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 }
    00054
    00055 static DKC_INLINE void free_2tree_node(DKC_2TREE_ROOT *root,DKC_2TREE_NODE **node)
    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 }
    00067 static DKC_INLINE DKC_2TREE_NODE* alloc_set(DKC_2TREE_ROOT *ptr,
    00068                                                     const void* Key,const void *data,size_t data_size)
    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 }
    00089
    00090 static DKC_INLINE void erase_tree_with_node(DKC_2TREE_ROOT *ptr,DKC_2TREE_NODE **leaf_node)
    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 }
    00113
    00114 DKC_2TREE_ROOT * WINAPI
    00115     dkcAlloc2TreeRoot(size_t key_size,size_t pool_max,DKC_COMPARE_TYPE compare,size_t max_num)
    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 }
    00150
    00151 static DKC_INLINE void free_2tree_root(DKC_2TREE_ROOT *root){
    00152     free_2tree_node(root,&(root->sentinel));
    00153     dkcFreeSameObjectPool(&(root->key_ac));
    00154     dkcFreeSameObjectPool(&(root->obj_ac));
    00155     dkcFree(&root);
    00156
    00157 }
    00158
    00159
    00160
    00161 DKC_INLINE int dkcFree2TreeWithVector(DKC_2TREE_ROOT *ptr){
    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 }
    00201
    00202
    00203 #ifdef _MSC_VER
    00204 //stack overflow 警告
    00205 #   pragma warning(disable:4717)
    00206 #endif
    00207
    00208 void dkcFree2TreeReflexive(DKC_2TREE_ROOT *ptr,DKC_2TREE_NODE **pp)
    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 }
    00235 #ifdef _MSC_VER
    00236 #   pragma warning(default:4717)
    00237 #endif
    00238
    00239 int dkcFree2TreeReflexiveBegin(DKC_2TREE_ROOT *ptr){
    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 }
    00249
    00250 int WINAPI dkcFree2TreeRoot(DKC_2TREE_ROOT **ptr){
    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 }
    00284
    00285 static DKC_2TREE_NODE *dkcAlloc2TreeInsertPoint(DKC_2TREE_NODE *ptr,int Key){
    00286
    00287
    00288 }
    00289
    00290
    00291
    00292 int WINAPI dkc2TreeInsert(DKC_2TREE_ROOT *ptr,
    00293                                                     const void* Key,const void *data,size_t data_size)
    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 }
    00335
    00336
    00337
    00338 int WINAPI dkc2TreeErase(DKC_2TREE_ROOT *ptr,DKC_2TREE_NODE *node)
    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 }
    00353
    00354 /*
    00355 int WINAPI dkc2TreeErase(DKC_2TREE_ROOT *ptr,DKC_2TREE_NODE **parent,DKC_2TREE_NODE *node){
    00356     //DKC_2TREE_NODE **q,*n2;
    00357     if(NULL==node){
    00358         return edk_FAILED;
    00359     }
    00360
    00361     if(node->right == NULL){
    00362         *parent = node->left;
    00363     }else if (node->left  == NULL){
    00364         *parent = node->right;
    00365     }
    00366     else
    00367     {
    00368
    00369         q = &(node->left);
    00370         while ((*q)->right != NULL){
    00371             q = &((*q)->right);
    00372         }
    00373         n2 = *q;
    00374         *q = n2->left;
    00375         n2->left = node->left;
    00376         n2->right = node->right;
    00377         *parent = n2;
    00378
    00379     }
    00380
    00381     free_2tree_node(ptr,node);
    00382     return edk_SUCCEEDED;
    00383 }
    00384 */
    00385
    00386 int WINAPI dkc2TreeEraseFromKey(DKC_2TREE_ROOT *ptr,const void *Key)
    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 }
    00421
    00422
    00423 /*
    00424 DKC_2TREE_NODE * WINAPI dkc2TreeSearchWithStack(DKC_2TREE_NODE *ptr,DKC_STACK *ps,int Key)
    00425 {
    00426
    00427
    00428
    00429
    00430 }
    00431 */
    00432
    00433 #if 1
    00434
    00436 static int WINAPI tree_exist_reflexive(DKC_2TREE_ROOT *ptr,
    00437                                                                              DKC_2TREE_NODE *node,DKC_2TREE_NODE **leaf_ptr,
    00438                                                                             const DKC_2TREE_NODE *target,DKC_2TREE_NODE *parent,
    00439                                                                             DKC_2TREE_EXIST *re)
    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 }
    00470
    00471 DKC_2TREE_EXIST WINAPI dkc2TreeExist(DKC_2TREE_ROOT *ptr,const DKC_2TREE_NODE *node)
    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 }
    00508
    00509
    00510 #elif 0
    00511
    00513 static DKC_INLINE int exist_check(int t,DKC_2TREE_NODE *node,DKC_2TREE_NODE **leaf_ptr,
    00514                                                                     DKC_2TREE_EXIST *re){
    00515     switch(t){
    00516     case 2:
    00517         return 2;
    00518     case 1:
    00519         re->parent = node;
    00520         re->leaf_ptr = leaf_ptr;
    00521         return 2;
    00522     //jump tableを作成させるために defaultは使わない
    00523     }
    00524     return 0;
    00525 }
    00526
    00527
    00529 static int WINAPI tree_exist_reflexive(DKC_2TREE_ROOT *ptr,DKC_2TREE_NODE *node,
    00530                                                                                 DKC_2TREE_NODE *target,DKC_2TREE_EXIST *re)
    00531 {
    00532     int t;
    00533     if(ptr->sentinel == node){
    00534         return 0;
    00535     }
    00536     if(node == target){
    00537         re->isExist = TRUE;
    00538         //re->leaf_ptr = &target;
    00539         re->node = node;
    00540         return 1;
    00541     }
    00542     //左
    00543     t = tree_exist_reflexive(ptr,node->left,target,re);
    00544     t = exist_check(t,node,&(node->left),re);
    00545     if(t != 0){
    00546         return t;
    00547     }
    00548
    00549     //右
    00550     t = tree_exist_reflexive(ptr,node->right,target,re);
    00551     t = exist_check(t,node,&(node->right),re);
    00552     if(t != 0){
    00553         return t;
    00554     }
    00555
    00556     //見つからない･･･。
    00557     return 0;
    00558 }
    00559
    00560 DKC_2TREE_EXIST WINAPI dkc2TreeExist(DKC_2TREE_ROOT *ptr,DKC_2TREE_NODE *node)
    00561 {
    00562     DKC_2TREE_NODE *tp = ptr->root;
    00563     DKC_2TREE_EXIST re;
    00564     int t;
    00565
    00566     re.isExist = FALSE;
    00567     re.leaf_ptr = NULL;
    00568     re.node = ptr->sentinel;
    00569     re.parent = re.node;
    00570
    00571
    00572
    00573     //左
    00574     t = tree_exist_reflexive(ptr,tp->left,node,&re);
    00575     t = exist_check(t,tp,&(tp->left),&re);
    00576     if(t != 0){
    00577         goto End;
    00578     }
    00579
    00580     //右
    00581     t = tree_exist_reflexive(ptr,tp->right,node,&re);
    00582     t = exist_check(t,tp,&(tp->right),&re);
    00583     if(t != 0){//無くてもいいが･･･
    00584
    00585         goto End;
    00586     }
    00587 End:
    00588     return re;
    00589 }
    00590
    00591 #else
    00592
    00593
    00594 /*
    00595 DKC_2TREE_EXIST WINAPI dkc2TreeExist(DKC_2TREE_ROOT *ptr,const DKC_2TREE_NODE *node)
    00596 {
    00597     DKC_2TREE_NODE *st = ptr->sentinel;
    00598     DKC_2TREE_NODE *it = ptr->root;
    00599     DKC_2TREE_NODE *save = ptr->sentinel,
    00600     DKC_2TREE_NODE **lp = NULL;
    00601     DKC_2TREE_EXIST re;
    00602     int t;
    00603
    00604     re.isExist = FALSE;
    00605     re.leaf_ptr = NULL;
    00606     re.node = st;
    00607     re.parent = re.node;
    00608
    00609
    00610
    00611     //左
    00612     for(;;){
    00613
    00614         if(it1 == node){
    00615             re.Exist = TRUE
    00616             re.leaf_ptr = lp;
    00617             re.node = it1;
    00618             re.parent = save;
    00619             break;
    00620         }
    00621         if(it2 == node){
    00622             re.Exist = TRUE
    00623             re.leaf_ptr = lp;
    00624             re.node = it2;
    00625             re.parent = save;
    00626             break;
    00627         }
    00628
    00629
    00630
    00631     }
    00632     return re;
    00633 }
    00634 */
    00635 #endif
    00636
    00637 DKC_2TREE_NODE * WINAPI dkc2TreeFindEqual(DKC_2TREE_ROOT *ptr,const void* Key)
    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 }
    00665
    00666
    00667 static DKC_2TREE_NODE *find_lg_base(DKC_2TREE_ROOT *ptr,const void* Key,BOOL isGreater)
    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 }
    00734
    00742 DKC_2TREE_NODE *WINAPI dkc2TreeFindMaximumLess(DKC_2TREE_ROOT *ptr,const void* Key)
    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 }
    00825 DKC_2TREE_NODE * WINAPI dkc2TreeFindMinimalGreater(DKC_2TREE_ROOT *ptr,const void* Key)
    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 }
    00901
    00902
    00903 int WINAPI dkc2TreeGetBuffer(DKC_2TREE_NODE *ptr,void *data,size_t size){
    00904     return dkc_memcpy_zc(data,size,ptr->data,ptr->data_size);
    00905 }
    00906
    00907 int WINAPI dkc2TreeSetBuffer(DKC_2TREE_NODE *ptr,const void *data,size_t size){
    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 }