Mercurial > hg > Papers > 2018 > nozomi-master
comparison paper/cbc.tex @ 26:5510bb043a74
Add rbtree description
| author | atton <atton@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 23 Jan 2017 15:42:08 +0900 |
| parents | 9325a5d0a6e0 |
| children | 243d8dc4a292 |
comparison
equal
deleted
inserted
replaced
| 25:9325a5d0a6e0 | 26:5510bb043a74 |
|---|---|
| 222 \includegraphics[scale=0.5]{fig/non-destructive-rbtree} | 222 \includegraphics[scale=0.5]{fig/non-destructive-rbtree} |
| 223 \caption{非破壊赤黒木の編集} | 223 \caption{非破壊赤黒木の編集} |
| 224 \label{fig:non-destructive-rbtree} | 224 \label{fig:non-destructive-rbtree} |
| 225 \end{center} | 225 \end{center} |
| 226 \end{figure} | 226 \end{figure} |
| 227 | |
| 228 CbC を用いて赤黒木を実装する際の問題として、関数の呼び出しスタックが存在しないため、関数の再帰呼び出しによって木が辿れないことがある。 | |
| 229 経路を辿るためにはノードに親への参照を持たせるか、挿入・削除時に辿った経路を記憶する必要がある。 | |
| 230 ノードが親への参照を持つ非破壊木構造は共通部分の共有が行なえないため、辿った経路を記憶する方法を使う。 | |
| 231 経路の記憶にはスタックを用い、スタックは Meta DataSegment に保持させる。 | |
| 232 | |
| 233 赤黒木を格納する DataSegment と Meta DataSegment の定義をリスト\ref{src:rbtree-context}に示す。 | |
| 234 経路の記憶に用いるスタックは Meta DataSegment である Context 内部の \verb/node_stack/ である。 | |
| 235 DataSegment は各ノード情報を持つ \verb/Node/構造体と、赤黒木を格納する \verb/Tree/構造体、挿入などで操作中の一時的な木を格納する \verb/Traverse/共用体などがある。 | |
| 236 | |
| 237 \lstinputlisting[label=src:rbtree-context, caption=赤黒木の DataSegment と Meta DataSegment] {src/rbtreeContext.h} | |
| 238 | |
| 239 Meta DataSegment を初期化する Meta CodeSegment initLLRBContext をリスト\ref{src:init-rbtree-context}に示す。 | |
| 240 この Meta CodeSegment ではメモリ領域の確保、CodeSegment 名と CodeSegment の実体の対応表の作成などを行なう。 | |
| 241 メモリ領域はプログラムの起動時に一定数のメモリを確保し、ヒープとして \verb/heap/ フィールドに保持させる。 | |
| 242 CodeSegment 名と CodeSegment の実体との対応は、enum で定義された CodeSegment 名の添字へと CodeSegment の関数ポインタを代入することにより持つ。 | |
| 243 例えば \verb/Put/ の実体は \verb/put_stub/ である。 | |
| 244 他にも DataSegment の初期化(リスト\ref{src:init-rbtree-context} 34-48)とスタックの初期化(リスト\ref{src:init-rbtree-context} 50-51)を行なう。 | |
| 245 | |
| 246 \lstinputlisting[label=src:init-rbtree-context, caption=赤黒木の Meta DataSegment の初期化を行なう Meta CodeSegment ] {src/initLLRBContext.c} | |
| 247 | |
| 248 実際の赤黒木の実装に用いられている Meta CodeSegment の一例をリスト\ref{src:rbtree-insert-case-2}に示す。 | |
| 249 Meta CodeSegment \verb/insertCase2/ は要素を挿入した場合に呼ばれる Meta CodeSegment の一つであり、親ノードの色によって処理を変える。 | |
| 250 まず、色を確認するために経路を記憶しているスタックから親の情報を取り出す。 | |
| 251 親の色が黒ならば処理を終了し、次の CodeSegment へと軽量継続する(リスト\ref{src:rbtree-insert-case-2} 5-8)。 | |
| 252 親の色が赤であるならばさらに処理を続行して \verb/InsertCase3/ へと軽量継続する。 | |
| 253 ここで、経路情報を再現するためにスタックへと親を再代入してから軽量継続を行なっている。 | |
| 254 なお、Meta CodeSegment でも Context から DataSegment を展開する処理は stub によって行なわれる(リスト\ref{src:rbtree-insert-case-2} 14-16)。 | |
| 255 | |
| 256 \lstinputlisting[label=src:rbtree-insert-case-2, caption=赤黒木の実装に用いられている Meta CodeSegment例] {src/insertCase2.c} | |
| 257 | |
| 258 | |
| 259 % TODO: akasha context case x の解説くらい | |
| 260 % TODO: akasha context の初期化 | |
| 261 % TODO: verification の assert | |
| 262 % TODO: akasha の結果 |