00001
00025 #ifndef DKUTIL_C_RED_BLACK_TREE_H
00026 #define DKUTIL_C_RED_BLACK_TREE_H
00027
00028 #include "dkcOSIndependent.h"
00029 #include "dkcBuffer.h"
00030 #include "dkcMemoryPool.h"
00031
00032
00033
00034
00035
00036 #define dkcm_RedBlackCompLT(a,b) (a < b)
00037 #define dkcm_RedBlackCompEQ(a,b) (a == b)
00038
00039
00040 typedef enum { edkcBLACK = 0, edkcRED } edkRedBlackTreeColor;
00042 typedef unsigned int rb_tree_key_type;
00044 typedef void *rb_tree_data_type;
00046 typedef void (*DKC_RED_BLACK_TREE_DESTRUCTOR_F_TYPE)(rb_tree_data_type data);
00047
00048 typedef struct dkc_RedBlackNode{
00049 struct dkc_RedBlackNode *left;
00050 struct dkc_RedBlackNode *right;
00051 struct dkc_RedBlackNode *parent;
00052
00053 unsigned int color;
00054 rb_tree_key_type key;
00055 rb_tree_data_type data;
00056 }DKC_RED_BLACK_NODE,DKC_RB_TREE_NODE;
00057
00058 typedef struct dkc_RedBlackRoot{
00059 DKC_RED_BLACK_NODE sentinel;
00060 DKC_RED_BLACK_NODE *root;
00061 DKC_SAME_OBJECT_POOL *node_pool;
00063 unsigned int node_count;
00064 unsigned int node_max;
00065 DKC_RED_BLACK_TREE_DESTRUCTOR_F_TYPE destructor;
00066 }DKC_RED_BLACK_ROOT,DKC_RB_TREE_ROOT;
00067
00068 #define dkcmREDBLACKTREE_NIL(p) (&((p)->sentinel))
00069
00080 DKC_EXTERN DKC_RB_TREE_ROOT * WINAPI
00081 dkcAllocRedBlackTreeRoot(size_t node_max,size_t pool_max,
00082 DKC_RED_BLACK_TREE_DESTRUCTOR_F_TYPE destructor_);
00083
00084 DKC_EXTERN int WINAPI dkcFreeRedBlackTreeRoot(DKC_RB_TREE_ROOT **ptr);
00085
00089 DKC_EXTERN void WINAPI dkcRedBlackTreeAllErase(DKC_RB_TREE_ROOT *p);
00090
00091
00092 DKC_INLINE void dkcRedBlackTreeInitSentinelNode(DKC_RED_BLACK_NODE *p)
00093 {
00094
00095
00096 p->left = p;
00097 p->right = p;
00098 p->parent = NULL;
00099 p->color = edkcBLACK;
00100 p->key = 0;
00101
00102
00103
00104 }
00105
00106 #define dkcdREDBLACKTREE_NIL_IN dkcmREDBLACKTREE_NIL(proot)//(&(proot->sentinel))
00107
00108
00109
00110
00112 DKC_INLINE void dkcRedBlackTree_rotateLeft(DKC_RED_BLACK_ROOT *proot,DKC_RED_BLACK_NODE *x) {
00113
00114
00115
00116
00117
00118 DKC_RED_BLACK_NODE *y = x->right;
00119
00120
00121 x->right = y->left;
00122 if (y->left != dkcdREDBLACKTREE_NIL_IN) y->left->parent = x;
00123
00124
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
00137 y->left = x;
00138 if (x != dkcdREDBLACKTREE_NIL_IN) x->parent = y;
00139
00140 }
00141
00142
00143 DKC_INLINE void dkcRedBlackTree_rotateRight(DKC_RED_BLACK_ROOT *proot,DKC_RED_BLACK_NODE *x) {
00144
00145
00146
00147
00148
00149 DKC_RED_BLACK_NODE *y = x->left;
00150
00151
00152 x->left = y->right;
00153 if (y->right != dkcdREDBLACKTREE_NIL_IN) y->right->parent = x;
00154
00155
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
00168 y->right = x;
00169 if (x != dkcdREDBLACKTREE_NIL_IN) x->parent = y;
00170
00171 }
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181 DKC_INLINE void dkcRedBlackTree_insertFixup(DKC_RED_BLACK_ROOT *proot,DKC_RED_BLACK_NODE *x) {
00182
00183
00184
00185
00186
00187
00188
00189 while (x != proot->root && x->parent->color == edkcRED) {
00190
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
00196 x->parent->color = edkcBLACK;
00197 y->color = edkcBLACK;
00198 x->parent->parent->color = edkcRED;
00199 x = x->parent->parent;
00200 } else {
00201
00202
00203 if (x == x->parent->right) {
00204
00205 x = x->parent;
00206 dkcRedBlackTree_rotateLeft(proot,x);
00207 }
00208
00209
00210 x->parent->color = edkcBLACK;
00211 x->parent->parent->color = edkcRED;
00212 dkcRedBlackTree_rotateRight(proot,x->parent->parent);
00213 }
00214 } else {
00215
00216
00217 DKC_RED_BLACK_NODE *y = x->parent->parent->left;
00218 if (y->color == edkcRED) {
00219
00220
00221 x->parent->color = edkcBLACK;
00222 y->color = edkcBLACK;
00223 x->parent->parent->color = edkcRED;
00224 x = x->parent->parent;
00225 } else {
00226
00227
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
00239 proot->root->color = edkcBLACK;
00240
00241
00242 }
00243
00244
00249 DKC_INLINE DKC_RED_BLACK_NODE *dkcRedBlackTree_insertNode
00250 (DKC_RED_BLACK_ROOT *proot,rb_tree_key_type key,rb_tree_data_type data
00251 )
00252 {
00253 DKC_RED_BLACK_NODE *current, *parent, *x;
00254
00255
00256
00257
00258
00259
00260 current = proot->root;
00261
00262 parent = NULL;
00263 if(proot->node_max <= proot->node_count)
00264 {
00265 return NULL;
00266 }
00267 while (current != dkcdREDBLACKTREE_NIL_IN) {
00268
00269 if (dkcm_RedBlackCompEQ(key, current->key)) return (current);
00270
00271 parent = current;
00272
00273 current = dkcm_RedBlackCompLT(key,current->key) ? current->left : current->right;
00274 }
00275
00276
00277
00278
00279
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
00288
00289
00290
00291
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
00300
00301
00302
00303
00304
00305
00306 if(parent) {
00307
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 }
00321
00322 DKC_INLINE void dkcRedBlackTree_deleteFixup(DKC_RED_BLACK_ROOT *proot,DKC_RED_BLACK_NODE *x) {
00323
00324
00325
00326
00327
00328
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
00381 x->color = edkcBLACK;
00382
00383 }
00384
00388 DKC_INLINE int dkcRedBlackTree_deleteNode
00389 (DKC_RED_BLACK_ROOT *proot,DKC_RED_BLACK_NODE *z,rb_tree_data_type *pdval)
00390 {
00391 DKC_RED_BLACK_NODE *x, *y;
00392
00393
00394
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
00405 *pdval = z->data;
00406
00407 if (z->left == dkcdREDBLACKTREE_NIL_IN || z->right == dkcdREDBLACKTREE_NIL_IN) {
00408
00409 y = z;
00410 } else {
00411
00412 y = z->right;
00413 while (y->left != dkcdREDBLACKTREE_NIL_IN) y = y->left;
00414 }
00415
00416
00417 if (y->left != dkcdREDBLACKTREE_NIL_IN)
00418 x = y->left;
00419 else
00420 x = y->right;
00421
00422
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
00436 }
00437
00438
00439
00440 if (y->color == edkcBLACK){
00441 dkcRedBlackTree_deleteFixup (proot,x);
00442 }
00443
00444 proot->node_count--;
00445
00446
00447
00448 dkcSameObjectPoolRecycle(proot->node_pool,y);
00449 return edk_SUCCEEDED;
00450 }
00451
00452
00453 DKC_INLINE DKC_RED_BLACK_NODE *dkcRedBlackTree_findNode(DKC_RED_BLACK_ROOT *proot,rb_tree_key_type key) {
00454
00455
00456
00457
00458 DKC_RED_BLACK_NODE *root = proot->root;
00459 DKC_RED_BLACK_NODE *current = root;
00460 while(current != dkcdREDBLACKTREE_NIL_IN){
00461
00462 if(dkcm_RedBlackCompEQ(key, current->key)){
00463 return (current);
00464 }else{
00465
00466 current = dkcm_RedBlackCompLT (key, current->key) ? current->left : current->right;
00467 }
00468 }
00469
00470 return NULL;
00471 }
00472
00473
00474
00475 #endif //end of include once