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

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 }

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