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

dkcRedBlackTree.h

Red Black Tree [詳細]

#include "dkcOSIndependent.h"
#include "dkcBuffer.h"
#include "dkcMemoryPool.h"

dkcRedBlackTree.hのインクルード依存関係図

このグラフは、どのファイルから直接、間接的にインクルードされているかを示しています。

ソースコードを見る。

構成

struct  dkc_RedBlackNode
struct  dkc_RedBlackRoot

マクロ定義

#define dkcm_RedBlackCompLT(a, b)   (a < b)
#define dkcm_RedBlackCompEQ(a, b)   (a == b)
#define dkcmREDBLACKTREE_NIL(p)   (&((p)->sentinel))
#define dkcdREDBLACKTREE_NIL_IN   dkcmREDBLACKTREE_NIL(proot)

型定義

typedef unsigned int rb_tree_key_type
 red black treeのkeyの型
typedef void * rb_tree_data_type
 red black treeのdataの型
typedef void(* DKC_RED_BLACK_TREE_DESTRUCTOR_F_TYPE )(rb_tree_data_type data)
 dkcRedBlackTreeAllErase()等でで使われるDKC_RED_BLACK_NODE内のdataに対するデストラクター
typedef dkc_RedBlackNode DKC_RED_BLACK_NODE
typedef dkc_RedBlackNode DKC_RB_TREE_NODE
typedef dkc_RedBlackRoot DKC_RED_BLACK_ROOT
typedef dkc_RedBlackRoot DKC_RB_TREE_ROOT

列挙型

enum  edkRedBlackTreeColor { edkcBLACK = 0, edkcRED }

関数

DKC_EXTERN DKC_RB_TREE_ROOT
*WINAPI 
dkcAllocRedBlackTreeRoot (size_t node_max, size_t pool_max, DKC_RED_BLACK_TREE_DESTRUCTOR_F_TYPE destructor_)
DKC_EXTERN int WINAPI dkcFreeRedBlackTreeRoot (DKC_RB_TREE_ROOT **ptr)
DKC_EXTERN void WINAPI dkcRedBlackTreeAllErase (DKC_RB_TREE_ROOT *p)
 すべてのノードを削除する。
DKC_INLINE void dkcRedBlackTreeInitSentinelNode (DKC_RED_BLACK_NODE *p)
DKC_INLINE void dkcRedBlackTree_rotateLeft (DKC_RED_BLACK_ROOT *proot, DKC_RED_BLACK_NODE *x)
 基本的に使わないでおいてください。
DKC_INLINE void dkcRedBlackTree_rotateRight (DKC_RED_BLACK_ROOT *proot, DKC_RED_BLACK_NODE *x)
DKC_INLINE void dkcRedBlackTree_insertFixup (DKC_RED_BLACK_ROOT *proot, DKC_RED_BLACK_NODE *x)
DKC_INLINE DKC_RED_BLACK_NODEdkcRedBlackTree_insertNode (DKC_RED_BLACK_ROOT *proot, rb_tree_key_type key, rb_tree_data_type data)
DKC_INLINE void dkcRedBlackTree_deleteFixup (DKC_RED_BLACK_ROOT *proot, DKC_RED_BLACK_NODE *x)
DKC_INLINE int dkcRedBlackTree_deleteNode (DKC_RED_BLACK_ROOT *proot, DKC_RED_BLACK_NODE *z, rb_tree_data_type *pdval)
DKC_INLINE DKC_RED_BLACK_NODEdkcRedBlackTree_findNode (DKC_RED_BLACK_ROOT *proot, rb_tree_key_type key)


説明

Red Black Tree

作者:
written by Thomas Niemann / turned into objective by d金魚

dkcRedBlackTree更新履歴

2006/01/15:データ構造にDKC_BUFFERは不便だと思い、void *に変えてみた。 2006/01/14:テスト終了。なんか完成した。データ構造はDKC_BUFFERを利用している。
覚え書き:
C++版が欲しい方はhttp://d.hatena.ne.jp/studiokingyo/20050322

また、このソースは速度重視にするのでdkc2Tree.cの実装のようにkeyを登録していたcompare 関数で比較したりせずkeyはunsigned int型に固定する。各自ハッシュ法なり何なりでkey値を決定しとく感じだ。

under is original source comment:
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 で定義されています。


マクロ定義

#define dkcdREDBLACKTREE_NIL_IN   dkcmREDBLACKTREE_NIL(proot)
 

dkcRedBlackTree.h106 行で定義されています。

参照元 dkcRedBlackTree_deleteNode(), dkcRedBlackTree_findNode(), dkcRedBlackTree_insertNode(), dkcRedBlackTree_rotateLeft(), と dkcRedBlackTree_rotateRight().

#define dkcm_RedBlackCompEQ a,
 )     (a == b)
 

dkcRedBlackTree.h37 行で定義されています。

参照元 dkcRedBlackTree_findNode(), と dkcRedBlackTree_insertNode().

#define dkcm_RedBlackCompLT a,
 )     (a < b)
 

dkcRedBlackTree.h36 行で定義されています。

参照元 dkcRedBlackTree_findNode(), と dkcRedBlackTree_insertNode().

#define dkcmREDBLACKTREE_NIL  )     (&((p)->sentinel))
 

dkcRedBlackTree.h68 行で定義されています。

参照元 dkcAllocRedBlackTreeRoot().


型定義

typedef struct dkc_RedBlackNode DKC_RB_TREE_NODE
 

typedef struct dkc_RedBlackRoot DKC_RB_TREE_ROOT
 

typedef struct dkc_RedBlackNode DKC_RED_BLACK_NODE
 

typedef struct dkc_RedBlackRoot DKC_RED_BLACK_ROOT
 

typedef void(* DKC_RED_BLACK_TREE_DESTRUCTOR_F_TYPE)(rb_tree_data_type data)
 

dkcRedBlackTreeAllErase()等でで使われるDKC_RED_BLACK_NODE内のdataに対するデストラクター

dkcRedBlackTree.h46 行で定義されています。

typedef void* rb_tree_data_type
 

red black treeのdataの型

dkcRedBlackTree.h44 行で定義されています。

typedef unsigned int rb_tree_key_type
 

red black treeのkeyの型

dkcRedBlackTree.h42 行で定義されています。


列挙型

enum edkRedBlackTreeColor
 

列挙型の値:
edkcBLACK 
edkcRED 

dkcRedBlackTree.h40 行で定義されています。


関数

DKC_EXTERN DKC_RB_TREE_ROOT* WINAPI dkcAllocRedBlackTreeRoot size_t  node_max,
size_t  pool_max,
DKC_RED_BLACK_TREE_DESTRUCTOR_F_TYPE  destructor_
 

引数:
node_max[in] 確保されたRootが確保できるnodeの数
pool_max[in] 内部で使うノードプールの最大数
destructor_[in] dkcRedBlackTreeAllErase()等でで使用されるDKC_RED_BLACK_NODEのdataメンバに対する開放関数を登録する。
戻り値:
メモリ領域が確保された Red Black Tree オブジェクトへのポインタ。NULLで失敗
覚え書き:
node_maxとpool_maxを同じにするとすべてのノードがプールされて メモリ確保処理がすべて簡略化される分処理が安定して高速になります。 ですが、メモリとの兼ね合いを考えてください。

dkcRedBlackTree.c12 行で定義されています。

参照先 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 }

DKC_EXTERN int WINAPI dkcFreeRedBlackTreeRoot DKC_RB_TREE_ROOT **  ptr  ) 
 

dkcRedBlackTree.c40 行で定義されています。

参照先 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 }

DKC_INLINE void dkcRedBlackTree_deleteFixup DKC_RED_BLACK_ROOT proot,
DKC_RED_BLACK_NODE x
 

dkcRedBlackTree.h322 行で定義されています。

参照先 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 }

DKC_INLINE int dkcRedBlackTree_deleteNode DKC_RED_BLACK_ROOT proot,
DKC_RED_BLACK_NODE z,
rb_tree_data_type pdval
 

引数:
pdval[out] 削除されたNodeに保存してあったデータを保存する

dkcRedBlackTree.h389 行で定義されています。

参照先 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 }

DKC_INLINE DKC_RED_BLACK_NODE* dkcRedBlackTree_findNode DKC_RED_BLACK_ROOT proot,
rb_tree_key_type  key
 

dkcRedBlackTree.h453 行で定義されています。

参照先 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 }

DKC_INLINE void dkcRedBlackTree_insertFixup DKC_RED_BLACK_ROOT proot,
DKC_RED_BLACK_NODE x
 

dkcRedBlackTree.h181 行で定義されています。

参照先 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 }

DKC_INLINE DKC_RED_BLACK_NODE* dkcRedBlackTree_insertNode DKC_RED_BLACK_ROOT proot,
rb_tree_key_type  key,
rb_tree_data_type  data
 

引数:
data[in] バッファ内のポインタをコピーするだけなので引数に渡したバッファは 後にdkcFreeBuffer()やdkcBufferInit()等で削除しないで下さい。

dkcRedBlackTree.h250 行で定義されています。

参照先 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 }

DKC_INLINE void dkcRedBlackTree_rotateLeft DKC_RED_BLACK_ROOT proot,
DKC_RED_BLACK_NODE x
 

基本的に使わないでおいてください。

dkcRedBlackTree.h112 行で定義されています。

参照先 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  }

DKC_INLINE void dkcRedBlackTree_rotateRight DKC_RED_BLACK_ROOT proot,
DKC_RED_BLACK_NODE x
 

dkcRedBlackTree.h143 行で定義されています。

参照先 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 }

DKC_EXTERN void WINAPI dkcRedBlackTreeAllErase DKC_RB_TREE_ROOT p  ) 
 

すべてのノードを削除する。

dkcRedBlackTree.c57 行で定義されています。

参照先 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 }

DKC_INLINE void dkcRedBlackTreeInitSentinelNode DKC_RED_BLACK_NODE p  ) 
 

dkcRedBlackTree.h92 行で定義されています。

参照先 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 }


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