#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) |
2分木領域を得る。 | |
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) |
2分木構造体内に保存しているデータをもらう | |
DKC_EXTERN int WINAPI | dkc2TreeSetBuffer (DKC_2TREE_NODE *ptr, const void *data, size_t size) |
2分木構造体に保存しているデータ領域にデータを入れる。 2分木構造体内のバッファが足りない場合はこの関数の内部で拡張してくれる。 |
define DKUTIL_C_2TREE_FAST_IMPL を宣言すると、ノード一つ分が+4バイト多く使用しますが、ノード指定での削除処理をO(1)にします。
dkc2Tree.h で定義されています。
|
dkc2TreeSetBuffer()がエラーをチェックするマクロ TRUE だったらエラー
dkc2Tree.h の 149 行で定義されています。 参照元 alloc_set(). |
|
dkc2TreeExist()で返される結果の構造体
|
|
|
|
いわいるRootみたいなもの。
|
|
2分木をチェインする。 destにsrcを繋げる。 destの2分木とsrcの二分木をソートしてdestに出力する。 しかし、
|
|
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 }
|
|
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 }
|
|
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 }
|
|
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 }
|
|
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 }
|
|
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 }
|
|
2分木構造体内に保存しているデータをもらう
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 }
|
|
新しいデータを挿入する。
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 }
|
|
2分木構造体に保存しているデータ領域にデータを入れる。 2分木構造体内のバッファが足りない場合はこの関数の内部で拡張してくれる。
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 }
|
|
2分木領域を得る。
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 }
|
|
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 }
|