Mercurial > hg > Papers > 2016 > kkb-master
changeset 12:2d6755608f67
revision
author | Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 15 Feb 2016 08:22:50 +0900 |
parents | 12d1c2f53258 |
children | a6188b7c7278 |
files | cbc.tex cerium.tex gearsos.tex images/images.graffle images/nondestructive_tree_modification.bb images/nondestructive_tree_modification.pdf master_paper.pdf master_paper.sty src/initWorker.c src/insert.c src/rb_tree.c src/rotate.c src/tree.h src/twice.c |
diffstat | 14 files changed, 990 insertions(+), 32 deletions(-) [+] |
line wrap: on
line diff
--- a/cbc.tex Sun Feb 14 07:02:11 2016 +0900 +++ b/cbc.tex Mon Feb 15 08:22:50 2016 +0900 @@ -42,6 +42,7 @@ Meta Code Segment への接続も省略して記述できるようにする。 省略形のソースコード:\ref{sample}から実際にコンパイルされるソースコード:\ref{sample_trans}へ変換される。 +\newpage + \lstinputlisting[label=sample, caption=省略形]{src/sample.c} -\newpage \lstinputlisting[label=sample_trans, caption=変換後]{src/sample_transform.c}
--- a/cerium.tex Sun Feb 14 07:02:11 2016 +0900 +++ b/cerium.tex Mon Feb 15 08:22:50 2016 +0900 @@ -82,25 +82,26 @@ \lstinputlisting[label=twice_task_cuda, caption=実行される kernel]{src/twice_cuda.cu} \section{Task のパイプライン実行} +Cell(図:\ref{fig:cellarch})や GPU(図:\ref{fig:gpuarch})のように異なるメモリ空間を持つ Device を計算資源として利用するにはデータの転送が必要になる。 +このデータ転送がボトルネックとなり、並列度が低下してしまう。 +転送処理をオーバーラップし、並列度を維持するために Cerium では Task のパイプライン実行をサポートしている。 + \begin{figure}[htpd] \begin{minipage}[t]{0.5\hsize} \begin{center} - \includegraphics[scale=0.4]{images/cell_arch.pdf} + \includegraphics[scale=0.5]{images/cell_arch.pdf} \end{center} \caption{Cell Architecture} \label{fig:cellarch} \end{minipage} \begin{minipage}[t]{0.5\hsize} \begin{center} - \includegraphics[scale=0.4]{images/gpu_arch.pdf} + \includegraphics[scale=0.5]{images/gpu_arch.pdf} \end{center} \caption{GPU Architecture} \label{fig:gpuarch} \end{minipage} \end{figure} -Cell(図:\ref{fig:cellarch})や GPU(図:\ref{fig:gpuarch})のように異なるメモリ空間を持つ Device を計算資源として利用するにはデータの転送が必要になる。 -このデータ転送がボトルネックとなり、並列度が低下してしまう。 -転送処理をオーバーラップし、並列度を維持するために Cerium では Task のパイプライン実行をサポートしている。 TaskManager である程度の Task をまとめた TaskList を生成し、実行する Device に対応した Scheduler に転送する。 受け取った TaskList に沿ってパイプラインを組み Task を実行していく。 @@ -108,6 +109,8 @@ 実行完了は TaskList 毎ではなく、Task 毎に通知される。 図:\ref{fig:scheduler}は TaskList を受け取り、Task をパイプラインで処理していく様子である。 +\newpage + \begin{figure}[ht] \begin{center} \includegraphics[scale=0.6]{images/scheduler.pdf} @@ -127,6 +130,8 @@ Cerium では DMA 転送を用いて Cell で実行することが可能である。 Multi Core CPU 上で実行する場合、メモリ空間を共有しているので DMA 転送を行なっている部分をポインタ渡しを行うように修正し、直接アクセスさせることでデータ転送の速度の向上が見込める。 +\newpage + \section{データ並列による実行} 並列処理の方法としてタスク並列とデータ並列の2つがある。 @@ -182,7 +187,7 @@ \begin{figure}[ht] \begin{center} - \includegraphics[scale=0.4]{images/stream.pdf} + \includegraphics[scale=0.45]{images/stream.pdf} \end{center} \caption{Overlap Data Transfer} \label{fig:stream} @@ -324,6 +329,8 @@ \label{fig:bitonic_result_1} \end{figure} +\newpage + GPGPU では通信時間を考慮する必要がある。 図:\ref{fig:bitonic_result_2}を見ると要素数$2^{14}$のソートでは GPU が一番遅い。 これはソート処理の時間より通信時間が大きいことが原因であると考えられる。
--- a/gearsos.tex Sun Feb 14 07:02:11 2016 +0900 +++ b/gearsos.tex Mon Feb 15 08:22:50 2016 +0900 @@ -20,6 +20,8 @@ Gear の特徴として処理やデータの構造が Code Gear, Data Gear に閉じていることにある。 これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。 +\newpage + \section{Gears OS の構成} Gears OS は以下の要素で構成される。 \begin{itemize} @@ -49,6 +51,8 @@ 図:\ref{fig:gearsos} は Gears OS の構成図である。 +\newpage + \begin{figure}[!ht] \begin{center} \includegraphics[scale=0.35]{./images/gearsos.pdf} @@ -57,8 +61,6 @@ \label{fig:gearsos} \end{figure} -\newpage - \section{Allocator} Gears OS では Context の生成時にある程度の大きさのメモリ領域を確保する。 Context には確保したメモリ領域を指す情報が格納される。 @@ -69,6 +71,8 @@ \lstinputlisting[label=context, caption=Context]{src/context.h} \lstinputlisting[label=initcontext, caption=initContext]{src/initContext.c} +\newpage + Context はヒープサイズを示す heapLimit, ヒープの初期位置を示す heapStart, ヒープの現在位置を示す heap を持っている。 必要な Data Gear のサイズに応じて heap の位置を動かすことで Allocation を実現する。 @@ -98,8 +102,6 @@ \lstinputlisting[label=allocate, caption=allocate]{src/allocate.c} -\newpage - \section{Synchronized Queue} Gears OS における Synchronized Queue は TaskQueue として利用される。 メインとなる Context と Worker 用の Context で共有され、Woker が TaskQueue から Task を取得し実行することで並列処理を実現する。 @@ -110,7 +112,7 @@ ソースコード:\ref{queue} は Context の定義(ソースコード:\ref{context})に追加する Queue と Element の定義である。 -\lstinputlisting[label=queue, caption=queue]{src/queue.h} +\lstinputlisting[label=queue, caption=Context: queue]{src/queue.h} 新たに Queue に対する操作を行う Code Gear の名前を追加し、UniqueData には Queue の情報が入る Queue(ソースコード:\ref{queue} 9行目) と Enqueue に必要な情報を書き込む Element(ソースコード:\ref{queue} 10行目) を定義している。 @@ -133,10 +135,94 @@ \lstinputlisting[label=sync_enqueue, caption=Enqueue using CAS]{src/sync_enqueue.c} \lstinputlisting[label=sync_dequeue, caption=Dequeue using CAS]{src/sync_dequeue.c} -\section{Worker} +\section{Persistent Data Tree} +Gears OS では Persistent Data Gear の管理に木構造を用いる。 +この木構造は非破壊で構成される。 +非破壊木構造とは一度構築した木構造を破壊することなく新しい木構造を構築することで、木構造を編集する方法である。 +非破壊木構造は木構造を書き換えることなく編集を行う(図:\ref{fig:non-destructive_tree})ため、読み書きを平行して行うことが可能である。 +赤色で示したノードが新しく追加されたノードである。非破壊木構造の基本的な戦略は、変更したいノードへのルートノードからのパスを全てコピーする。 +そして、パス上に存在しないノードはコピー元の木構造と共有することである。 + +\newpage + +\begin{figure}[!h] + \centering + \includegraphics[scale=0.7]{images/nondestructive_tree_modification.pdf} + \caption{木構造の非破壊的編集} + \label{fig:non-destructive_tree} +\end{figure} + +木構造はディレクトリツリー、構文木など階層構造を持つデータを表現する。 +またはデータベースのインデックスなど情報を探索しやすくするための探索木としても用いられる。 +Gears OS では Data Tree として木構造を利用する。 +その場合、普通に木構造を構築するだけでは偏った木構造が構築される可能性がある。 +最悪なケースでは事実上の線形リストになり、計算量が O(n) となる。 +挿入・削除・検索における処理時間を保証するため Red-Black Tree を用いて木構造の平衡性を保証する。 + +Red-Black Tree は通常の二分探索木としての条件の他に以下の条件を持つ。 + +\begin{itemize} +\item 各ノードは赤または黒の色を持つ。 +\item ルートの色は黒である。 +\item 赤ノードは2つの黒ノードを子として持つ(赤ノードが続くことはない)。 +\item ルートから最下位ノードへのパスに含まれる黒ノードの数はどの最下位ノードでも一定である。 +\end{itemize} + +これらの条件によってルートから最も遠い最下位ノードへのパスの長さはルートから最も近い最下位ノードへのパスの長さの2倍に収まることが保証される。 + +Red-Black Tree は挿入・削除を行ったあとに変更したノードからルートへのパスを辿りながら Red-Black Tree の条件を満たすように色の変更や木の回転を行う。 +関数呼び出しが可能なプログラミング言語では戻り値でパスを辿ることができるが、CbC は末尾呼び出し最適化が行われるように記述する必要があるのでパスを辿るにはノードに親への参照を持たせるか挿入・削除時に辿ったパスを記憶するしかない。 +ノードが親への参照を持つと非破壊木構造を構築することが出来ないので、辿ったパスを記憶する方法を用いる。 +辿ったパスを記憶するため Context にスタックを持たせる。 + +ソースコード:\ref{tree}は Context に追加する Tree, Node および Tree の操作を行う Code Gear 名の定義である。 + +\lstinputlisting[label=tree, caption=Context: Red-Black Tree]{src/tree.h} -\section{Red-Black Tree} -Gears OS では Persistent Data Gear の管理に木構造を用いる。 +Tree は参照する木を格納する Code Gear である。 +この Code Gear は Context の生成時に生成される。 +Traverse は木の探索に用いられる Code Gear である。 +Code Gear は末尾最適化されるので呼び出し元の情報が残らない。 +参照しているノードの情報を Code Gear 間で持ち歩くためには Traverse のような Data Gear が必要になる。 + +赤ノードが続かないという Red-Black Tree の条件を満たすか判定する Code Gear はソースコード:\ref{insert}の通りである。 +まず、親の情報が必要なのでパスを記憶しているスタックから親ノードを取得する。 +親ノードが黒である場合、木を回転する必要はなく木は平衡を保っているので木に対する操作を終了する。 + +\lstinputlisting[label=insert, caption=Insert Case]{src/insert.c} + +木の左回転を行う Code Gear はソースコード:\ref{rotateLeft}の通りである。 +自分、親、兄弟の3点のノードの回転である。 +回転を行ったあとにも Red-Black Tree の条件を満たしているか確認する必要があるので回転後に変更された親ノードを再びスタックに記憶する。 +また、回転の際に現在見ているノードが変更する必要がある。 + +\newpage + +\lstinputlisting[label=rotateLeft, caption=Rotate Left]{src/rotate.c} + +\section{Worker} +Worker は TaskQueue から Task を取得し、実行する。 +Task には実行する Code Gear と実行に必要な Code Gear の key が格納されている。 +実行に必要な Code Gear は Persistent Data Tree から key を使って取得する。 + +各 Worker は個別の Context を参照している。 +メモリ空間も独立しているのでメモリを確保する処理で他の Thread を止めることはない。 +ただし、Persistent Data Tree への書き出しは競合する可能性があるので CAS を利用してデータの一貫性を保証する必要がある。 + +Worker が Task の取得を行う Code Gear はソースコード:\ref{sync_dequeue}の通りである。 +TaskQueue から取得した Task から実行する Code Gear と必要な Data Gear の key を Worker Context に書き込むことで実行される。 +Task の実行後に再び Task の取得を行う Code Gear に戻る必要がある。 +Context は実行する Code Gear のスタックを持っているのでそのスタックに積む(ソースコード:\ref{sync_dequeue} 11行目)ことで戻ることができる。 + +Task に格納され Worker で実行される Code Gear はソースコード:\ref{task}の通りである。 +ソースコード:\ref{task}は指定された要素の値を2倍する Twice という例題である。 +Twice は並列実行される。 + +\lstinputlisting[label=task, caption=Task Sample]{src/twice.c} + +並列処理される Code Gear と言っても他の Code Gear と完全に同じである。 +これは Gears OS 自体が Code Gear によって構成されていることに起因する。 +つまり、Gears OS を利用して書かれたプログラムで定義されている Code Gear に依存関係がないときすべて並列に動作させることができるということを意味する。 \section{TaskManager} Gears OS の TaskManager は WaitTaskQueue に入っている Task の依存関係を解決する。 @@ -149,3 +235,5 @@ TaskManager は Worker の管理も行う。 メインとなる Context には Worker の情報が格納されており、TaskManager はこの Context を参照して Worker の起動・停止を行う。 ソースコード\ref{init_worker}は Worker を起動する Code Gear である。 + +\lstinputlisting[label=init_worker, caption=InitWorker]{src/initWorker.c}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/nondestructive_tree_modification.bb Mon Feb 15 08:22:50 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: ./images/nondestructive_tree_modification.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 559 248 +%%CreationDate: Mon Feb 15 04:41:46 2016 +
--- a/master_paper.sty Sun Feb 14 07:02:11 2016 +0900 +++ b/master_paper.sty Mon Feb 15 08:22:50 2016 +0900 @@ -72,7 +72,8 @@ \topmargin 0mm \headheight 10mm \headsep 15mm -\textheight 39\baselineskip \addtolength{\textheight}{\topskip} +%\textheight 39\baselineskip \addtolength{\textheight}{\topskip} +\textheight 212mm \textwidth 160mm \marginparsep 3mm \marginparwidth 15mm @@ -149,23 +150,30 @@ \begin{center}% \let\footnote\thanks - {\Large\bf\thesis\par} - {\Large\bf\ethesis\par\vskip 0.5em} - {\LARGE\bf\mc\@title\par} - {\LARGE\bf{\@etitle}\par\vskip 0.5 em} - {\large\mc\@year\par} - {\large\@eyear\par\vskip 0.2 em} + {\Large\bf\thesis\\} + {\Large\bf\ethesis\vskip 0.4em} + + {\LARGE\bf\mc\@title\\} + {\LARGE\bf{\@etitle}\vskip 0.4 em} + + {\large\mc\@year\\} + {\large\@eyear\vskip 0.3 em} + {\large\bf\mc\@author\par} - {\large\bf\@eauthor\par\vskip 1.0 em} - {\includegraphics[clip,keepaspectratio=true,scale=0.5]{images/u-ryukyu-Mark.eps}\vskip 2.0 em} - {\large\bf\mc\university\par} - {\large\bf\mc\department\par} - {\large\bf\mc\course\par\vskip 0.2 em} - {\large\textbf\ecourse \par} - {\large\textbf\edepartment \par} - {\large\textbf\euniversity \par\vskip 0.2 em} - {\large\bf\mc\@chife\par} - {\large\bf\@echife\par} + {\large\bf\@eauthor\par\vskip 0.8 em} + + {\includegraphics[clip,keepaspectratio=true,scale=0.48]{images/u-ryukyu-Mark.eps}\vskip 0.8 em} + + {\large\bf\mc\university\\} + {\large\bf\mc\department\\} + {\large\bf\mc\course\vskip 0.3 em} + + {\large\textbf\ecourse\\} + {\large\textbf\edepartment\\} + {\large\textbf\euniversity\vskip 0.3em} + + {\large\bf\mc\@chife\\} + {\large\bf\@echife\\} \end{center} }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/initWorker.c Mon Feb 15 08:22:50 2016 +0900 @@ -0,0 +1,24 @@ +// Code Gear +__code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) { + int i = loopCounter->i; + + if (i < worker->num) { + struct Context* worker_context = &worker->contexts[i]; + worker_context->next = GetQueue; + worker_context->data[Tree] = context->data[Tree]; + worker_context->data[ActiveQueue] = context->data[ActiveQueue]; + pthread_create(&worker_context->thread, NULL, (void*)&start_code, worker_context); + worker_context->thread_num = i; + loopCounter->i++; + + goto meta(context, CreateWorker); + } + + loopCounter->i = 0; + goto meta(context, TaskManager); +} + +// Meta Code Gear +__code createWorker_stub(struct Context* context) { + goto createWorker(context, &context->data[LoopCounter]->loopCounter, &context->data[Worker]->worker); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/insert.c Mon Feb 15 08:22:50 2016 +0900 @@ -0,0 +1,18 @@ +// Code Gear +__code insertCase2(struct Context* context, struct Node* current) { + struct Node* parent; + stack_pop(context->node_stack, &parent); + + if (parent->color == Black) { + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); + } + + stack_push(context->node_stack, &parent); + goto meta(context, InsertCase3); +} + +// Meta Code Gear(stub) +__code insert2_stub(struct Context* context) { + goto insertCase2(context, context->data[Traverse]->traverse.current); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/rb_tree.c Mon Feb 15 08:22:50 2016 +0900 @@ -0,0 +1,685 @@ +#include <stdio.h> + +#include "context.h" +#include "origin_cs.h" + +extern void allocator(struct Context* context); +extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2); + +extern int num; + +__code put(struct Context* context, struct Tree* tree, struct Traverse* traverse, struct Node* root, struct Allocate* allocate) { + allocate->size = sizeof(struct Node); + allocator(context); + + stack_push(context->code_stack, &context->next); + + context->next = StackClear; + stack_push(context->code_stack, &context->next); + + tree->root = &context->data[context->dataNum]->node; + + if (root) { + traverse->current = root; + compare(context, traverse, traverse->current->key, context->data[Node]->node.key); + + goto meta(context, Replace); + } + + goto meta(context, Insert); +} + +__code put_stub(struct Context* context) { + goto put(context, + &context->data[Tree]->tree, + &context->data[Traverse]->traverse, + context->data[Tree]->tree.root, + &context->data[Allocate]->allocate); +} + +__code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, int result) { + *newNode = *oldNode; + stack_push(context->node_stack, &newNode); + + if (result == EQ) { + newNode->value = context->data[Node]->node.value; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); + } else if (result == GT) { + traverse->current = oldNode->right; + newNode->right = context->heap; + } else { + traverse->current = oldNode->left; + newNode->left = context->heap; + } + + allocator(context); + + if (traverse->current) { + compare(context, traverse, traverse->current->key, context->data[Node]->node.key); + goto meta(context, Replace); + } + + goto meta(context, Insert); +} + +__code replaceNode_stub(struct Context* context) { + goto replaceNode(context, + &context->data[Traverse]->traverse, + context->data[Traverse]->traverse.current, + &context->data[context->dataNum]->node, + context->data[Traverse]->traverse.result); +} + +__code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) { + node->color = Red; + *newNode = *node; + + traverse->current = newNode; + + goto meta(context, InsertCase1); +} + +__code insertNode_stub(struct Context* context) { + goto insertNode(context, + &context->data[Traverse]->traverse, + &context->data[Node]->node, + &context->data[context->dataNum]->node); +} + +__code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) { + if (!isEmpty(context->node_stack)) + goto meta(context, InsertCase2); + + tree->root->color = Black; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code insert1_stub(struct Context* context) { + goto insertCase1(context, &context->data[Tree]->tree, context->data[Traverse]->traverse.current); +} + +__code insertCase2(struct Context* context, struct Node* current) { + struct Node* parent; + stack_pop(context->node_stack, &parent); + + if (parent->color == Black) { + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); + } + + stack_push(context->node_stack, &parent); + goto meta(context, InsertCase3); +} + +__code insert2_stub(struct Context* context) { + goto insertCase2(context, context->data[Traverse]->traverse.current); +} + +__code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* current) { + struct Node* parent; + struct Node* uncle; + struct Node* grandparent; + + stack_pop(context->node_stack, &parent); + stack_pop(context->node_stack, &grandparent); + + if (grandparent->left == parent) + uncle = grandparent->right; + else + uncle = grandparent->left; + + if (uncle && (uncle->color == Red)) { + parent->color = Black; + uncle->color = Black; + grandparent->color = Red; + traverse->current = grandparent; + goto meta(context, InsertCase1); + } + + stack_push(context->node_stack, &grandparent); + stack_push(context->node_stack, &parent); + + goto meta(context, InsertCase4); +} + +__code insert3_stub(struct Context* context) { + goto insertCase3(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current); +} + +__code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current) { + struct Node* parent; + struct Node* grandparent; + + stack_pop(context->node_stack, &parent); + stack_pop(context->node_stack, &grandparent); + + stack_push(context->node_stack, &grandparent); + + traverse->current = parent; + + if ((current == parent->right) && (parent == grandparent->left)) { + context->next = InsertCase4_1; + + stack_push(context->code_stack, &context->next); + goto meta(context, RotateL); + } else if ((current == parent->left) && (parent == grandparent->right)) { + context->next = InsertCase4_2; + + stack_push(context->code_stack, &context->next); + goto meta(context, RotateR); + } + + stack_push(context->node_stack, &parent); + traverse->current = current; + goto meta(context, InsertCase5); +} + +__code insert4_stub(struct Context* context) { + goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current); +} + +__code insertCase4_1(struct Context* context, struct Traverse* traverse) { + stack_push(context->node_stack, &traverse->current); + traverse->current = traverse->current->left; + goto meta(context, InsertCase5); +} + +__code insert4_1_stub(struct Context* context) { + goto insertCase4_1(context, &context->data[Traverse]->traverse); +} + +__code insertCase4_2(struct Context* context, struct Traverse* traverse) { + stack_push(context->node_stack, &traverse->current); + traverse->current = traverse->current->right; + goto meta(context, InsertCase5); +} + +__code insert4_2_stub(struct Context* context) { + goto insertCase4_2(context, &context->data[Traverse]->traverse); +} + +__code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current) { + struct Node* parent; + struct Node* grandparent; + + stack_pop(context->node_stack, &parent); + stack_pop(context->node_stack, &grandparent); + + parent->color = Black; + grandparent->color = Red; + + traverse->current = grandparent; + + if ((current == parent->left) && (parent == grandparent->left)) + goto meta(context, RotateR); + else + goto meta(context, RotateL); +} + +__code insert5_stub(struct Context* context) { + goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current); +} + +__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) { + struct Node* tmp = node->right; + struct Node* parent = 0; + + stack_pop(context->node_stack, &parent); + + if (parent) { + if (node == parent->left) + parent->left = tmp; + else + parent->right = tmp; + } else { + tree->root = tmp; + } + + stack_push(context->node_stack, &parent); + + node->right = tmp->left; + tmp->left = node; + traverse->current = tmp; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code rotateLeft_stub(struct Context* context) { + goto rotateLeft(context, + context->data[Traverse]->traverse.current, + &context->data[Tree]->tree, + &context->data[Traverse]->traverse); +} + +__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) { + struct Node* tmp = node->left; + struct Node* parent = 0; + + stack_pop(context->node_stack, &parent); + + if (parent) { + if (node == parent->left) + parent->left = tmp; + else + parent->right = tmp; + } else { + tree->root = tmp; + } + + stack_push(context->node_stack, &parent); + + node->left = tmp->right; + tmp->right = node; + traverse->current = tmp; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code rotateRight_stub(struct Context* context) { + goto rotateRight(context, + context->data[Traverse]->traverse.current, + &context->data[Tree]->tree, + &context->data[Traverse]->traverse); +} + +__code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) { + if (stack_pop(node_stack, &traverse->current) == 0) + goto meta(context, StackClear); + + traverse->current = 0; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code stackClear_stub(struct Context* context) { + goto stackClear(context, context->node_stack, &context->data[Traverse]->traverse); +} + + +__code get(struct Context* context, struct Tree* tree, struct Traverse* traverse) { + if (tree->root) { + traverse->current = tree->root; + + goto meta(context, Search); + } + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code get_stub(struct Context* context) { + goto get(context, &context->data[Tree]->tree, &context->data[Traverse]->traverse); +} + +__code search(struct Context* context, struct Traverse* traverse, struct Node* node) { + compare(context, traverse, traverse->current->key, node->key); + + if (traverse->result == EQ) { + *node = *traverse->current; + + goto meta(context, context->next); + } else if (traverse->result == GT) { + traverse->current = traverse->current->right; + } else { + traverse->current = traverse->current->left; + } + + if (traverse->current) + goto meta(context, Search); + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code search_stub(struct Context* context) { + goto search(context, &context->data[Traverse]->traverse, &context->data[Node]->node); +} + +/* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */ +/* /\* if (tree->root) { *\/ */ +/* /\* stack_push(context->code_stack, &context->next); *\/ */ +/* /\* context->next = Delete1; *\/ */ +/* /\* goto meta(context, Get); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, context->next); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete_stub(struct Context* context) { *\/ */ +/* /\* goto delete(context, &context->data[Tree]->tree); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { *\/ */ +/* /\* allocate->size = sizeof(struct Node); *\/ */ +/* /\* allocator(context); *\/ */ + +/* /\* struct Node* root = tree->root; *\/ */ + +/* /\* tree->root = &context->data[context->dataNum]->node; *\/ */ +/* /\* tree->current = root; *\/ */ + +/* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */ + +/* /\* goto meta(context, Replace_d1); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete1_stub(struct Context* context) { *\/ */ +/* /\* goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete2(struct Context* context, struct Node* current) { *\/ */ +/* /\* if (current->color == Black) { *\/ */ +/* /\* struct Node* child = current->right == NULL ? current->left : current->right; *\/ */ +/* /\* current->color = child == NULL ? Black : child->color; *\/ */ + +/* /\* goto meta(context, DeleteCase1); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, Delete3); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete2_stub(struct Context* context) { *\/ */ +/* /\* goto delete2(context, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ +/* /\* struct Node* tmp = current->right == NULL ? current->left : current->right; *\/ */ + +/* /\* if (current->parent) { *\/ */ +/* /\* if (current == current->parent->left) *\/ */ +/* /\* current->parent->left = tmp; *\/ */ +/* /\* else *\/ */ +/* /\* current->parent->right = tmp; *\/ */ +/* /\* } else { *\/ */ +/* /\* tree->root = tmp; *\/ */ +/* /\* } *\/ */ + +/* /\* if (tmp) *\/ */ +/* /\* tmp->parent = current->parent; *\/ */ + +/* /\* if (current->parent == NULL && tmp) *\/ */ +/* /\* tmp->color = Black; *\/ */ + +/* /\* current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); *\/ */ + +/* /\* stack_pop(context->code_stack, &context->next); *\/ */ +/* /\* goto meta(context, context->next); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete3_stub(struct Context* context) { *\/ */ +/* /\* goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { *\/ */ +/* /\* *newNode = *oldNode; *\/ */ + +/* /\* if (result == EQ) *\/ */ +/* /\* goto meta(context, Replace_d2); *\/ */ +/* /\* else if (result == GT) *\/ */ +/* /\* tree->current = newNode->right; *\/ */ +/* /\* else *\/ */ +/* /\* tree->current = newNode->left; *\/ */ + +/* /\* tree->current->parent = newNode; *\/ */ + +/* /\* if (tree->current->left == NULL && tree->current->right == NULL) *\/ */ +/* /\* goto meta(context, Delete2); *\/ */ + +/* /\* if (result == GT) *\/ */ +/* /\* newNode->right = context->heap; *\/ */ +/* /\* else if (result == LT) *\/ */ +/* /\* newNode->left = context->heap; *\/ */ + +/* /\* allocator(context); *\/ */ + +/* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */ + +/* /\* goto meta(context, Replace_d1); *\/ */ +/* /\* } *\/ */ + +/* /\* __code replaceNodeForDelete1_stub(struct Context* context) { *\/ */ +/* /\* goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); *\/ */ +/* /\* } *\/ */ + +/* /\* __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { *\/ */ +/* /\* if (tree->current->left && tree->current->right) { *\/ */ +/* /\* newNode->left->parent = newNode; *\/ */ +/* /\* tree->current = newNode->left; *\/ */ +/* /\* newNode->left = context->heap; *\/ */ +/* /\* tree->deleted = newNode; *\/ */ + +/* /\* allocator(context); *\/ */ +/* /\* tree->current->parent = newNode; *\/ */ + +/* /\* goto meta(context, FindMax1); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, Delete2); *\/ */ +/* /\* } *\/ */ + +/* /\* __code replaceNodeForDelete2_stub(struct Context* context) { *\/ */ +/* /\* goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); *\/ */ +/* /\* } *\/ */ + +/* /\* __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */ +/* /\* *newNode = *oldNode; *\/ */ + +/* /\* if (newNode->right) *\/ */ +/* /\* goto meta(context, FindMax2); *\/ */ + +/* /\* tree->deleted->key = newNode->key; *\/ */ +/* /\* tree->deleted->value = newNode->value; *\/ */ + +/* /\* tree->current = newNode; *\/ */ + +/* /\* goto meta(context, Delete2); *\/ */ +/* /\* } *\/ */ + +/* /\* __code findMax1_stub(struct Context* context) { *\/ */ +/* /\* goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */ +/* /\* } *\/ */ + + +/* /\* __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */ +/* /\* *newNode = *oldNode; *\/ */ + +/* /\* if (newNode->right->right) { *\/ */ +/* /\* tree->current = newNode->right; *\/ */ +/* /\* newNode->right = context->heap; *\/ */ + +/* /\* allocator(context); *\/ */ +/* /\* tree->current->parent = newNode; *\/ */ + +/* /\* goto meta(context, FindMax2); *\/ */ +/* /\* } *\/ */ + +/* /\* tree->deleted->key = newNode->right->key; *\/ */ +/* /\* tree->deleted->value = newNode->right->value; *\/ */ + +/* /\* tree->current = newNode; *\/ */ + +/* /\* goto meta(context, Delete2); *\/ */ +/* /\* } *\/ */ + +/* /\* __code findMax2_stub(struct Context* context) { *\/ */ +/* /\* goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase1(struct Context* context, struct Node* current) { *\/ */ +/* /\* if (current->parent) *\/ */ +/* /\* goto meta(context, DeleteCase2); *\/ */ + +/* /\* goto meta(context, Delete3); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase1_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase1(context, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ +/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ + +/* /\* if ((sibling == NULL ? Black : sibling->color) == Red) { *\/ */ +/* /\* current->parent->color = Red; *\/ */ +/* /\* sibling->color = Black; *\/ */ + +/* /\* current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* context->data[context->dataNum]->node = *sibling; *\/ */ + +/* /\* tree->current = current->parent; *\/ */ + +/* /\* context->next = DeleteCase3; *\/ */ +/* /\* stack_push(context->code_stack, &context->next); *\/ */ + +/* /\* if (current == current->parent->left) *\/ */ +/* /\* goto meta(context, RotateL); *\/ */ +/* /\* else *\/ */ +/* /\* goto meta(context, RotateR); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, DeleteCase3); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase2_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ +/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ + +/* /\* if (current->parent->color == Black && *\/ */ +/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ +/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ +/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ +/* /\* sibling->color = Red; *\/ */ + +/* /\* tree->current = current->parent; *\/ */ +/* /\* goto meta(context, DeleteCase1); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, DeleteCase4); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase3_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase4(struct Context* context, struct Node* current) { *\/ */ +/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ + +/* /\* if (current->parent->color == Red && *\/ */ +/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ +/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ +/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ +/* /\* sibling->color = Red; *\/ */ +/* /\* current->parent->color = Black; *\/ */ + +/* /\* goto meta(context, Delete3); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, DeleteCase5); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase4_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase4(context, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ +/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ +/* /\* sibling->parent = current->parent; *\/ */ + +/* /\* if (current == current->parent->left && *\/ */ +/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ +/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Red && *\/ */ +/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ +/* /\* sibling->color = Red; *\/ */ +/* /\* sibling->left->color = Black; *\/ */ + +/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ +/* /\* *tmp = *sibling; *\/ */ +/* /\* tmp->parent = current; *\/ */ + +/* /\* tmp->left = context->heap; *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* context->data[context->dataNum]->node = *sibling->left; *\/ */ +/* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */ + +/* /\* tree->current = tmp; *\/ */ + +/* /\* context->next = DeleteCase6; *\/ */ +/* /\* stack_push(context->code_stack, &context->next); *\/ */ + +/* /\* goto meta(context, RotateR); *\/ */ +/* /\* } else if (current == current->parent->right && *\/ */ +/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ +/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ +/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Red) { *\/ */ +/* /\* sibling->color = Red; *\/ */ +/* /\* sibling->right->color = Black; *\/ */ + +/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ +/* /\* *tmp = *sibling; *\/ */ +/* /\* tmp->parent = current; *\/ */ + +/* /\* tmp->right = context->heap; *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* context->data[context->dataNum]->node = *sibling->right; *\/ */ +/* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */ + +/* /\* tree->current = tmp; *\/ */ + +/* /\* context->next = DeleteCase6; *\/ */ +/* /\* stack_push(context->code_stack, &context->next); *\/ */ +/* /\* goto meta(context, RotateL); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, DeleteCase6); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase5_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ +/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ + +/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ +/* /\* *tmp = *sibling; *\/ */ +/* /\* tmp->parent = current; *\/ */ + +/* /\* tmp->color = current->parent->color; *\/ */ +/* /\* current->parent->color = Black; *\/ */ + +/* /\* context->next = Delete3; *\/ */ +/* /\* stack_push(context->code_stack, &context->next); *\/ */ + +/* /\* if (current == current->parent->left) { *\/ */ +/* /\* tmp->right->color = Black; *\/ */ +/* /\* tree->current = current->parent; *\/ */ + +/* /\* goto meta(context, RotateL); *\/ */ +/* /\* } else { *\/ */ +/* /\* tmp->left->color = Black; *\/ */ +/* /\* tree->current = current->parent; *\/ */ + +/* /\* goto meta(context, RotateR); *\/ */ +/* /\* } *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase6_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/rotate.c Mon Feb 15 08:22:50 2016 +0900 @@ -0,0 +1,33 @@ +// Code Gear +__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) { + struct Node* tmp = node->right; + struct Node* parent = 0; + + stack_pop(context->node_stack, &parent); + + if (parent) { + if (node == parent->left) + parent->left = tmp; + else + parent->right = tmp; + } else { + tree->root = tmp; + } + + stack_push(context->node_stack, &parent); + + node->right = tmp->left; + tmp->left = node; + traverse->current = tmp; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +// Meta Code Gear(stub) +__code rotateLeft_stub(struct Context* context) { + goto rotateLeft(context, + context->data[Traverse]->traverse.current, + &context->data[Tree]->tree, + &context->data[Traverse]->traverse); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/tree.h Mon Feb 15 08:22:50 2016 +0900 @@ -0,0 +1,63 @@ +// Code Gear Name +enum Code { + PutTree, + Replace, + Insert, + Compare, + RotateL, + RotateR, + SetTree, + InsertCase1, + InsertCase2, + InsertCase3, + InsertCase4, + InsertCase4_1, + InsertCase4_2, + InsertCase5, + StackClear, + Get, + Search, +}; + +// Compare Result +enum Relational { + EQ, + GT, + LT, +}; + +// Unique Data Gear +enum UniqueData { + Tree, + Traverse, + Node, +}; + +// Context definication +struct Context { + stack_ptr node_stack; +}; + +// Red-Black Tree definication +union Data { + // size: 8 byte + struct Tree { + struct Node* root; + } tree; + // size: 12 byte + struct Traverse { + struct Node* current; + int result; + } traverse; + // size: 32 byte + struct Node { + int key; + union Data* value; + struct Node* left; + struct Node* right; + enum Color { + Red, + Black, + } color; + } node; +};
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/twice.c Mon Feb 15 08:22:50 2016 +0900 @@ -0,0 +1,26 @@ +// Code Gear +__code twice(struct Context* context, struct LoopCounter* loopCounter, int index, int alignment, int* array) { + int i = loopCounter->i; + + if (i < alignment) { + array[i+index*alignment] = array[i+index*alignment]*2; + loopCounter->i++; + + goto meta(context, Twice); + } + + loopCounter->i = 0; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +// Meta Code Gear(stub) +__code twice_stub(struct Context* context) { + goto twice(context, + &context->data[LoopCounter]->loopCounter, + context->data[Node]->node.value->array.index, + context->data[Node]->node.value->array.alignment, + context->data[Node]->node.value->array.array); +} +