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

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

dkutil_cに対してMon Jan 16 00:39:49 2006に生成されました。  doxygen 1.4.4