#include "dkcOSIndependent.h"
#include "dkcBuffer.h"
#include "dkcMemoryPool.h"
dkcRedBlackTree.hのインクルード依存関係図
このグラフは、どのファイルから直接、間接的にインクルードされているかを示しています。
The below red-black tree implementation of was written by Thomas Niemann and is available on his algorithm collection webpages. This code is not subject to copyright restrictions.
dkcRedBlackTree.h で定義されています。
|
dkcRedBlackTree.h の 106 行で定義されています。 参照元 dkcRedBlackTree_deleteNode(), dkcRedBlackTree_findNode(), dkcRedBlackTree_insertNode(), dkcRedBlackTree_rotateLeft(), と dkcRedBlackTree_rotateRight(). |
|
dkcRedBlackTree.h の 37 行で定義されています。 参照元 dkcRedBlackTree_findNode(), と dkcRedBlackTree_insertNode(). |
|
dkcRedBlackTree.h の 36 行で定義されています。 参照元 dkcRedBlackTree_findNode(), と dkcRedBlackTree_insertNode(). |
|
dkcRedBlackTree.h の 68 行で定義されています。 |
|
|
|
|
|
|
|
|
|
dkcRedBlackTreeAllErase()等でで使われるDKC_RED_BLACK_NODE内のdataに対するデストラクター
dkcRedBlackTree.h の 46 行で定義されています。 |
|
red black treeのdataの型
dkcRedBlackTree.h の 44 行で定義されています。 |
|
red black treeのkeyの型
dkcRedBlackTree.h の 42 行で定義されています。 |
|
dkcRedBlackTree.h の 40 行で定義されています。 00040 { edkcBLACK = 0, edkcRED } edkRedBlackTreeColor;
|
|
dkcRedBlackTree.c の 12 行で定義されています。 参照先 dkc_RedBlackRoot::destructor, dkcAllocate(), dkcAllocSameObjectPool(), dkcFree(), dkcmREDBLACKTREE_NIL, dkcRedBlackTreeInitSentinelNode(), dkc_RedBlackRoot::node_count, dkc_RedBlackRoot::node_max, dkc_RedBlackRoot::node_pool, NULL, と dkc_RedBlackRoot::root. 00014 { 00015 DKC_RB_TREE_ROOT *p; 00016 if(NULL==destructor_) return NULL; 00017 p = dkcAllocate(sizeof(DKC_RB_TREE_ROOT)); 00018 if(NULL==p) return NULL; 00019 00020 dkcRedBlackTreeInitSentinelNode( 00021 dkcmREDBLACKTREE_NIL(p) 00022 ); 00023 00024 p->root = dkcmREDBLACKTREE_NIL(p); 00025 p->node_pool = dkcAllocSameObjectPool( 00026 sizeof(DKC_RED_BLACK_NODE),pool_max,NULL,NULL 00027 ); 00028 if(NULL==p->node_pool){ 00029 goto Error; 00030 } 00031 p->node_max = node_max; 00032 p->node_count = 0; 00033 p->destructor = destructor_; 00034 return p; 00035 Error: 00036 dkcFree(&p); 00037 return NULL; 00038 }
|
|
dkcRedBlackTree.c の 40 行で定義されています。 参照先 dkcFree(), dkcFreeSameObjectPool(), dkcRedBlackTreeAllErase(), dkc_RedBlackRoot::node_pool, と NULL. 00041 { 00042 if(NULL==ptr || NULL==*ptr) 00043 { 00044 return edk_ArgumentException; 00045 } 00046 00047 { 00048 DKC_RB_TREE_ROOT *p = *ptr; 00049 00050 dkcRedBlackTreeAllErase(p); 00051 00052 dkcFreeSameObjectPool(&(p->node_pool)); 00053 } 00054 return dkcFree(ptr); 00055 }
|
|
dkcRedBlackTree.h の 322 行で定義されています。 参照先 dkc_RedBlackNode::color, dkcRedBlackTree_rotateLeft(), dkcRedBlackTree_rotateRight(), edkcBLACK, edkcRED, dkc_RedBlackNode::left, dkc_RedBlackNode::parent, dkc_RedBlackNode::right, と dkc_RedBlackRoot::root. 参照元 dkcRedBlackTree_deleteNode(). 00322 { 00323 00324 /************************************* 00325 * maintain Red-Black tree balance * 00326 * after deleting node x * 00327 *************************************/ 00328 // DKC_RED_BLACK_NODE *root = proot->root; 00329 while (x != proot->root && x->color == edkcBLACK) { 00330 if (x == x->parent->left) { 00331 DKC_RED_BLACK_NODE *w = x->parent->right; 00332 if (w->color == edkcRED) { 00333 w->color = edkcBLACK; 00334 x->parent->color = edkcRED; 00335 dkcRedBlackTree_rotateLeft(proot,x->parent); 00336 w = x->parent->right; 00337 } 00338 if (w->left->color == edkcBLACK && w->right->color == edkcBLACK) { 00339 w->color = edkcRED; 00340 x = x->parent; 00341 } else { 00342 if (w->right->color == edkcBLACK) { 00343 w->left->color = edkcBLACK; 00344 w->color = edkcRED; 00345 dkcRedBlackTree_rotateRight(proot,w); 00346 w = x->parent->right; 00347 } 00348 w->color = x->parent->color; 00349 x->parent->color = edkcBLACK; 00350 w->right->color = edkcBLACK; 00351 dkcRedBlackTree_rotateLeft(proot,x->parent); 00352 x = proot->root; 00353 } 00354 } else { 00355 DKC_RED_BLACK_NODE *w = x->parent->left; 00356 if (w->color == edkcRED) { 00357 w->color = edkcBLACK; 00358 x->parent->color = edkcRED; 00359 dkcRedBlackTree_rotateRight(proot,x->parent); 00360 w = x->parent->left; 00361 } 00362 if (w->right->color == edkcBLACK && w->left->color == edkcBLACK) { 00363 w->color = edkcRED; 00364 x = x->parent; 00365 } else { 00366 if (w->left->color == edkcBLACK) { 00367 w->right->color = edkcBLACK; 00368 w->color = edkcRED; 00369 dkcRedBlackTree_rotateLeft(proot,w); 00370 w = x->parent->left; 00371 } 00372 w->color = x->parent->color; 00373 x->parent->color = edkcBLACK; 00374 w->left->color = edkcBLACK; 00375 dkcRedBlackTree_rotateRight(proot,x->parent); 00376 x = proot->root; 00377 } 00378 } 00379 } 00380 //update 00381 x->color = edkcBLACK; 00382 00383 }
|
|
dkcRedBlackTree.h の 389 行で定義されています。 参照先 dkc_RedBlackNode::color, dkc_RedBlackNode::data, dkcdREDBLACKTREE_NIL_IN, dkcmNOT_ASSERT, dkcRedBlackTree_deleteFixup(), dkcSameObjectPoolRecycle(), edkcBLACK, dkc_RedBlackNode::left, dkc_RedBlackRoot::node_count, dkc_RedBlackRoot::node_pool, dkc_RedBlackNode::parent, dkc_RedBlackNode::right, と dkc_RedBlackRoot::root. 参照元 dkcRedBlackTreeAllErase(). 00390 { 00391 DKC_RED_BLACK_NODE *x, *y; 00392 //DKC_RED_BLACK_NODE *root = proot->root; 00393 /***************************** 00394 * delete node z from tree * 00395 *****************************/ 00396 00397 //まぁ、プログラマに任せるって方針で。 00398 dkcmNOT_ASSERT(proot->node_count==0); 00399 00400 if (!z || z == dkcdREDBLACKTREE_NIL_IN){ 00401 return edk_FAILED; 00402 } 00403 //内部バッファ開放 00404 // dkcBufferUninit(&z->buffer); 00405 *pdval = z->data; 00406 00407 if (z->left == dkcdREDBLACKTREE_NIL_IN || z->right == dkcdREDBLACKTREE_NIL_IN) { 00408 /* y has a NIL node as a child */ 00409 y = z; 00410 } else { 00411 /* find tree successor with a NIL node as a child */ 00412 y = z->right; 00413 while (y->left != dkcdREDBLACKTREE_NIL_IN) y = y->left; 00414 } 00415 00416 /* x is y's only child */ 00417 if (y->left != dkcdREDBLACKTREE_NIL_IN) 00418 x = y->left; 00419 else 00420 x = y->right; 00421 00422 /* remove y from the parent chain */ 00423 x->parent = y->parent; 00424 if (y->parent){ 00425 if (y == y->parent->left) 00426 y->parent->left = x; 00427 else 00428 y->parent->right = x; 00429 }else{ 00430 proot->root = x; 00431 00432 } 00433 if (y != z){ 00434 z->data = y->data; 00435 //dkcBufferCopyShared(&z->buffer,&y->buffer); 00436 } 00437 00438 00439 //dkcmNOT_ASSERT(proot->root==x); 00440 if (y->color == edkcBLACK){ 00441 dkcRedBlackTree_deleteFixup (proot,x); 00442 } 00443 00444 proot->node_count--; 00445 //free (y); 00446 //dkcmNOT_ASSERT(proot->root==y); 00447 //dkcSameObjectPoolFree(y); 00448 dkcSameObjectPoolRecycle(proot->node_pool,y); 00449 return edk_SUCCEEDED; 00450 }
|
|
dkcRedBlackTree.h の 453 行で定義されています。 参照先 dkcdREDBLACKTREE_NIL_IN, dkcm_RedBlackCompEQ, dkcm_RedBlackCompLT, dkc_RedBlackNode::key, dkc_RedBlackNode::left, NULL, dkc_RedBlackNode::right, と dkc_RedBlackRoot::root. 00453 { 00454 00455 /******************************* 00456 * find node containing data * 00457 *******************************/ 00458 DKC_RED_BLACK_NODE *root = proot->root; 00459 DKC_RED_BLACK_NODE *current = root; 00460 while(current != dkcdREDBLACKTREE_NIL_IN){ 00461 //if(dkcm_RedBlackCompEQ(data, current->data)){ 00462 if(dkcm_RedBlackCompEQ(key, current->key)){ 00463 return (current); 00464 }else{ 00465 //current = dkcm_RedBlackCompLT (data, current->data) ? current->left : current->right; 00466 current = dkcm_RedBlackCompLT (key, current->key) ? current->left : current->right; 00467 } 00468 } 00469 //return(0); 00470 return NULL; 00471 }
|
|
dkcRedBlackTree.h の 181 行で定義されています。 参照先 dkc_RedBlackNode::color, dkcRedBlackTree_rotateLeft(), dkcRedBlackTree_rotateRight(), edkcBLACK, edkcRED, dkc_RedBlackNode::left, dkc_RedBlackNode::parent, dkc_RedBlackNode::right, と dkc_RedBlackRoot::root. 参照元 dkcRedBlackTree_insertNode(). 00181 { 00182 00183 /************************************* 00184 * maintain Red-Black tree balance * 00185 * after inserting node x * 00186 *************************************/ 00187 //DKC_RED_BLACK_NODE *root = proot->root; 00188 /* check Red-Black properties */ 00189 while (x != proot->root && x->parent->color == edkcRED) { 00190 /* we have a violation */ 00191 if (x->parent == x->parent->parent->left) { 00192 DKC_RED_BLACK_NODE *y = x->parent->parent->right; 00193 if (y->color == edkcRED) { 00194 00195 /* uncle is RED */ 00196 x->parent->color = edkcBLACK; 00197 y->color = edkcBLACK; 00198 x->parent->parent->color = edkcRED; 00199 x = x->parent->parent; 00200 } else { 00201 00202 /* uncle is BLACK */ 00203 if (x == x->parent->right) { 00204 /* make x a left child */ 00205 x = x->parent; 00206 dkcRedBlackTree_rotateLeft(proot,x); 00207 } 00208 00209 /* recolor and rotate */ 00210 x->parent->color = edkcBLACK; 00211 x->parent->parent->color = edkcRED; 00212 dkcRedBlackTree_rotateRight(proot,x->parent->parent); 00213 } 00214 } else { 00215 00216 /* mirror image of above code */ 00217 DKC_RED_BLACK_NODE *y = x->parent->parent->left; 00218 if (y->color == edkcRED) { 00219 00220 /* uncle is RED */ 00221 x->parent->color = edkcBLACK; 00222 y->color = edkcBLACK; 00223 x->parent->parent->color = edkcRED; 00224 x = x->parent->parent; 00225 } else { 00226 00227 /* uncle is BLACK */ 00228 if (x == x->parent->left) { 00229 x = x->parent; 00230 dkcRedBlackTree_rotateRight(proot,x); 00231 } 00232 x->parent->color = edkcBLACK; 00233 x->parent->parent->color = edkcRED; 00234 dkcRedBlackTree_rotateLeft(proot,x->parent->parent); 00235 } 00236 } 00237 } 00238 //update 00239 proot->root->color = edkcBLACK; 00240 00241 00242 }
|
|
dkcRedBlackTree.h の 250 行で定義されています。 参照先 dkc_RedBlackNode::color, dkc_RedBlackNode::data, dkcdREDBLACKTREE_NIL_IN, dkcm_RedBlackCompEQ, dkcm_RedBlackCompLT, dkcmNOT_ASSERT, dkcRedBlackTree_insertFixup(), dkcSameObjectPoolAlloc(), edkcRED, dkc_RedBlackNode::key, dkc_RedBlackNode::left, dkc_RedBlackRoot::node_count, dkc_RedBlackRoot::node_max, dkc_RedBlackRoot::node_pool, NULL, dkc_RedBlackNode::parent, dkc_RedBlackNode::right, と dkc_RedBlackRoot::root. 00252 { 00253 DKC_RED_BLACK_NODE *current, *parent, *x; 00254 // DKC_RED_BLACK_NODE *root = proot->root; 00255 /*********************************************** 00256 * allocate node for data and insert in tree * 00257 ***********************************************/ 00258 00259 /* find where node belongs */ 00260 current = proot->root; 00261 //parent = 0; 00262 parent = NULL; 00263 if(proot->node_max <= proot->node_count) 00264 {//capacity over 00265 return NULL; 00266 } 00267 while (current != dkcdREDBLACKTREE_NIL_IN) { 00268 //if (dkcm_RedBlackCompEQ(data, current->data)) return (current); 00269 if (dkcm_RedBlackCompEQ(key, current->key)) return (current); 00270 00271 parent = current; 00272 //current = dkcm_RedBlackCompLT(data, current->data) ? current->left : current->right; 00273 current = dkcm_RedBlackCompLT(key,current->key) ? current->left : current->right; 00274 } 00275 00276 /* setup new node */ 00277 /*if ((x = malloc (sizeof(*x))) == 0) { 00278 printf ("insufficient memory (insertNode)\n"); 00279 exit(1); 00280 }*/ 00281 x = (DKC_RED_BLACK_NODE *)dkcSameObjectPoolAlloc(proot->node_pool); 00282 dkcmNOT_ASSERT(x==NULL); 00283 if(NULL==x){ 00284 return NULL; 00285 } 00286 00287 //initialize 00288 //x->buffer.mBuff = NULL; 00289 //x->buffer.mSize = 0; 00290 00291 //dkcBufferCopyShared(&(x->buffer),data); 00292 x->data = data; 00293 x->key = key; 00294 x->parent = parent; 00295 x->left = dkcdREDBLACKTREE_NIL_IN; 00296 x->right = dkcdREDBLACKTREE_NIL_IN; 00297 x->color = edkcRED; 00298 /* 00299 x->data = data; 00300 x->parent = parent; 00301 x->left = dkcdREDBLACKTREE_NIL_IN; 00302 x->right = dkcdREDBLACKTREE_NIL_IN; 00303 x->color = edkcRED; 00304 */ 00305 /* insert node in tree */ 00306 if(parent) { 00307 //if(dkcm_RedBlackCompLT(data, parent->data)) 00308 if(dkcm_RedBlackCompLT(key,parent->key)) 00309 parent->left = x; 00310 else 00311 parent->right = x; 00312 } else { 00313 proot->root = x; 00314 00315 } 00316 00317 dkcRedBlackTree_insertFixup(proot,x); 00318 proot->node_count++; 00319 return(x); 00320 }
|
|
基本的に使わないでおいてください。
dkcRedBlackTree.h の 112 行で定義されています。 参照先 dkcdREDBLACKTREE_NIL_IN, dkc_RedBlackNode::left, dkc_RedBlackNode::parent, dkc_RedBlackNode::right, と dkc_RedBlackRoot::root. 参照元 dkcRedBlackTree_deleteFixup(), と dkcRedBlackTree_insertFixup(). 00112 { 00113 00114 /************************** 00115 * rotate node x to left * 00116 **************************/ 00117 // DKC_RED_BLACK_NODE *root = proot->root; 00118 DKC_RED_BLACK_NODE *y = x->right; 00119 00120 /* establish x->right link */ 00121 x->right = y->left; 00122 if (y->left != dkcdREDBLACKTREE_NIL_IN) y->left->parent = x; 00123 00124 /* establish y->parent link */ 00125 if (y != dkcdREDBLACKTREE_NIL_IN) y->parent = x->parent; 00126 if (x->parent) { 00127 if (x == x->parent->left) 00128 x->parent->left = y; 00129 else 00130 x->parent->right = y; 00131 } else { 00132 proot->root = y; 00133 00134 } 00135 00136 /* link x and y */ 00137 y->left = x; 00138 if (x != dkcdREDBLACKTREE_NIL_IN) x->parent = y; 00139 00140 }
|
|
dkcRedBlackTree.h の 143 行で定義されています。 参照先 dkcdREDBLACKTREE_NIL_IN, dkc_RedBlackNode::left, dkc_RedBlackNode::parent, dkc_RedBlackNode::right, と dkc_RedBlackRoot::root. 参照元 dkcRedBlackTree_deleteFixup(), と dkcRedBlackTree_insertFixup(). 00143 { 00144 00145 /**************************** 00146 * rotate node x to right * 00147 ****************************/ 00148 //DKC_RED_BLACK_NODE *root = proot->root; 00149 DKC_RED_BLACK_NODE *y = x->left; 00150 00151 /* establish x->left link */ 00152 x->left = y->right; 00153 if (y->right != dkcdREDBLACKTREE_NIL_IN) y->right->parent = x; 00154 00155 /* establish y->parent link */ 00156 if (y != dkcdREDBLACKTREE_NIL_IN) y->parent = x->parent; 00157 if (x->parent) { 00158 if (x == x->parent->right) 00159 x->parent->right = y; 00160 else 00161 x->parent->left = y; 00162 } else { 00163 proot->root = y; 00164 00165 } 00166 00167 /* link x and y */ 00168 y->right = x; 00169 if (x != dkcdREDBLACKTREE_NIL_IN) x->parent = y; 00170 00171 }
|
|
すべてのノードを削除する。
dkcRedBlackTree.c の 57 行で定義されています。 参照先 dkc_RedBlackRoot::destructor, dkcRedBlackTree_deleteNode(), dkc_RedBlackRoot::node_count, NULL, と dkc_RedBlackRoot::root. 参照元 dkcFreeRedBlackTreeRoot(). 00058 { 00059 rb_tree_data_type data = NULL; 00060 while(p->node_count != 0) 00061 { 00062 dkcRedBlackTree_deleteNode(p,p->root,&data); 00063 p->destructor(data); 00064 } 00065 00066 }
|
|
dkcRedBlackTree.h の 92 行で定義されています。 参照先 dkc_RedBlackNode::color, edkcBLACK, dkc_RedBlackNode::key, dkc_RedBlackNode::left, NULL, dkc_RedBlackNode::parent, と dkc_RedBlackNode::right. 参照元 dkcAllocRedBlackTreeRoot(). 00093 { 00094 //#define NIL &sentinel /* all leafs are sentinels */ 00095 //Node sentinel = { NIL, NIL, 0, BLACK, 0}; 00096 p->left = p; 00097 p->right = p; 00098 p->parent = NULL; 00099 p->color = edkcBLACK; 00100 p->key = 0; 00101 //p->buffer; 00102 //p->data = NULL; 00103 //p->data_size = NULL; 00104 }
|