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

# 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_NODE * | dkcRedBlackTree_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_NODE * | dkcRedBlackTree_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.h の 106 行で定義されています。 参照元 dkcRedBlackTree_deleteNode(), dkcRedBlackTree_findNode(), dkcRedBlackTree_insertNode(), dkcRedBlackTree_rotateLeft(), と dkcRedBlackTree_rotateRight().

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

| dkcRedBlackTree.h の 37 行で定義されています。 参照元 dkcRedBlackTree_findNode(), と dkcRedBlackTree_insertNode().

#define dkcm_RedBlackCompLT | ( | a,
|  | b |  | ) | (a < b)

| dkcRedBlackTree.h の 36 行で定義されています。 参照元 dkcRedBlackTree_findNode(), と dkcRedBlackTree_insertNode().

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

| dkcRedBlackTree.h の 68 行で定義されています。 参照元 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.h の 46 行で定義されています。

typedef void* rb_tree_data_type

| red black treeのdataの型 dkcRedBlackTree.h の 44 行で定義されています。

typedef unsigned int rb_tree_key_type

| red black treeのkeyの型 dkcRedBlackTree.h の 42 行で定義されています。

## 列挙型

enum edkRedBlackTreeColor

  | 列挙型の値:
  edkcBLACK |
  edkcRED |
dkcRedBlackTree.h の 40 行で定義されています。
    00040 { edkcBLACK = 0, edkcRED } edkRedBlackTreeColor;

## 関数

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.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 }

DKC_EXTERN int WINAPI dkcFreeRedBlackTreeRoot | ( | DKC_RB_TREE_ROOT ** | ptr | ) |

| 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 }

DKC_INLINE void dkcRedBlackTree_deleteFixup | ( | DKC_RED_BLACK_ROOT * | proot,
|  | DKC_RED_BLACK_NODE * | x
| ) |

| 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 }

DKC_INLINE int dkcRedBlackTree_deleteNode | ( | DKC_RED_BLACK_ROOT * | proot,
|  | DKC_RED_BLACK_NODE * | z,
|  | rb_tree_data_type * | pdval
| ) |

  | 引数:
  | pdval[out] | 削除されたNodeに保存してあったデータを保存する
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 }

DKC_INLINE DKC_RED_BLACK_NODE* dkcRedBlackTree_findNode | ( | DKC_RED_BLACK_ROOT * | proot,
|  | rb_tree_key_type | key
| ) |

| 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 }

DKC_INLINE void dkcRedBlackTree_insertFixup | ( | DKC_RED_BLACK_ROOT * | proot,
|  | DKC_RED_BLACK_NODE * | x
| ) |

| 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 }

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.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 }

DKC_INLINE void dkcRedBlackTree_rotateLeft | ( | DKC_RED_BLACK_ROOT * | proot,
|  | DKC_RED_BLACK_NODE * | x
| ) |

| 基本的に使わないでおいてください。 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  }

DKC_INLINE void dkcRedBlackTree_rotateRight | ( | DKC_RED_BLACK_ROOT * | proot,
|  | DKC_RED_BLACK_NODE * | x
| ) |

| 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 }

DKC_EXTERN void WINAPI dkcRedBlackTreeAllErase | ( | DKC_RB_TREE_ROOT * | p | ) |

| すべてのノードを削除する。 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 }

DKC_INLINE void dkcRedBlackTreeInitSentinelNode | ( | DKC_RED_BLACK_NODE * | p | ) |

| 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 }