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

# dkcRedBlackTree.h

説明を見る。

    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 /* red-black tree */
    00033
    00034
    00035 // typedef int T;                  /* type of item to be stored */
    00036  #define dkcm_RedBlackCompLT(a,b) (a < b)
    00037  #define dkcm_RedBlackCompEQ(a,b) (a == b)
    00038
    00039  /* Red-Black tree description */
    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;         /* left child */
    00050     struct dkc_RedBlackNode *right;        /* right child */
    00051     struct dkc_RedBlackNode *parent;       /* parent */
    00052     //uint8 color;            /* node color (BLACK, RED) */
    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     //#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 }
    00105
    00106 #define dkcdREDBLACKTREE_NIL_IN dkcmREDBLACKTREE_NIL(proot)//(&(proot->sentinel))
    00107
    00108 //  DKC_RED_BLACK_NODE *root = NIL;               /* root of Red-Black tree */
    00109
    00110
    00112 DKC_INLINE void dkcRedBlackTree_rotateLeft(DKC_RED_BLACK_ROOT *proot,DKC_RED_BLACK_NODE *x) {
    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  }
    00141
    00142
    00143 DKC_INLINE void dkcRedBlackTree_rotateRight(DKC_RED_BLACK_ROOT *proot,DKC_RED_BLACK_NODE *x) {
    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 }
    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    *  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 }
    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     //  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 }
    00321
    00322 DKC_INLINE void dkcRedBlackTree_deleteFixup(DKC_RED_BLACK_ROOT *proot,DKC_RED_BLACK_NODE *x) {
    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 }
    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     //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 }
    00451
    00452 //DKC_RED_BLACK_NODE *dkcRedBlackTree_findNode(DKC_RED_BLACK_ROOT *proot,DKC_BUFFER data) {
    00453 DKC_INLINE DKC_RED_BLACK_NODE *dkcRedBlackTree_findNode(DKC_RED_BLACK_ROOT *proot,rb_tree_key_type key) {
    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 }
    00472
    00473
    00474
    00475 #endif //end of include once