Mercurial > hg > Papers > 2018 > parusu-master
changeset 3:86340b0bf212
Update
| author | Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Wed, 17 Jan 2018 08:48:10 +0900 |
| parents | b3fc9cc0d85f |
| children | 7df8596223fb |
| files | mindmap.mm paper/gearsOS.tex paper/master_paper.tex paper/src/cg1.cbc paper/src/context.h paper/src/initContext.c paper/src/queueInterface.h paper/src/singleLinkedQueue.cbc paper/src/singleLinkedQueueTest.cbc paper/src/singleLinkedQueueTest_script.cbc |
| diffstat | 10 files changed, 312 insertions(+), 27 deletions(-) [+] |
line wrap: on
line diff
--- a/mindmap.mm Sun Jan 07 05:22:05 2018 +0900 +++ b/mindmap.mm Wed Jan 17 08:48:10 2018 +0900 @@ -110,20 +110,41 @@ </node> </node> </node> -<node CREATED="1512459138764" ID="ID_1903848084" MODIFIED="1512459176537" POSITION="right" TEXT="CbC"> -<node CREATED="1512459188214" ID="ID_59092144" MODIFIED="1512459194712" TEXT="code Gear, Data Gear"/> +<node CREATED="1515489773550" ID="ID_182275024" MODIFIED="1515489776577" POSITION="right" TEXT="Gears OS"> +<node CREATED="1515489795847" ID="ID_789491775" MODIFIED="1515489801928" TEXT="Code Gear, Data Gear"/> +<node CREATED="1515489868685" ID="ID_1534618965" MODIFIED="1515489870518" TEXT="継続"/> +<node CREATED="1512459138764" ID="ID_1903848084" MODIFIED="1512459176537" TEXT="CbC"> +<node CREATED="1512459188214" ID="ID_59092144" MODIFIED="1515489899341" TEXT="code Gearを記述出来る言語"/> +<node CREATED="1515489834796" ID="ID_945167143" MODIFIED="1515489836287" TEXT="goto"/> <node CREATED="1512459195550" ID="ID_759671304" MODIFIED="1512459207695" TEXT="meta computation"> <node CREATED="1512459207696" ID="ID_1753156845" MODIFIED="1512459215215" TEXT="stub"/> </node> <node CREATED="1512459217895" ID="ID_620166500" MODIFIED="1512459227058" TEXT="interface"/> </node> -<node CREATED="1512459051002" ID="ID_1406407128" MODIFIED="1512460037059" POSITION="right" TEXT="並列処理の構成"> +<node CREATED="1515489816813" ID="ID_1315035351" MODIFIED="1515489891580" TEXT="Gears での Data Gear"> +<node CREATED="1515489943522" ID="ID_1142363267" MODIFIED="1515489958632" TEXT="union と struct を組合せで表現する"/> +<node CREATED="1515489904234" ID="ID_756344413" MODIFIED="1515489907740" TEXT="interface"> +<node CREATED="1515489908157" ID="ID_1799558180" MODIFIED="1515489931027" TEXT="データと振る舞いの集合である Data Gear"/> +</node> +</node> +<node CREATED="1515489810423" ID="ID_1853930962" MODIFIED="1515489833006" TEXT="meta Gear"> +<node CREATED="1515489845374" ID="ID_1496192306" MODIFIED="1515489862316" TEXT="Gears は meta Gear を通常の Gearの間に接続する"/> +</node> +</node> +<node CREATED="1512459051002" ID="ID_1406407128" MODIFIED="1515488831956" POSITION="right" TEXT="並列処理の構成"> <node CREATED="1492598873929" ID="ID_341820755" MODIFIED="1492598875273" TEXT="Context"> +<node CREATED="1515736011060" ID="ID_1535255002" MODIFIED="1515736016842" TEXT="代表的な Meta Data"/> <node CREATED="1492599273720" ID="ID_1145032049" MODIFIED="1492599302246" TEXT="CG のリスト"/> <node CREATED="1492599280124" ID="ID_1742110158" MODIFIED="1492599304862" TEXT="DG のリスト"/> <node CREATED="1492599284153" ID="ID_1876844818" MODIFIED="1492599312025" TEXT="DG の allocate"/> <node CREATED="1492599605705" ID="ID_887878285" MODIFIED="1492599610261" TEXT="その他いろいろ"/> <node CREATED="1492599614820" ID="ID_1536135754" MODIFIED="1492599619148" TEXT="Task も Context"/> +<node CREATED="1515735879699" ID="ID_1522228763" MODIFIED="1515735890529" TEXT="Thread や process と同等"/> +<node CREATED="1515735890953" ID="ID_1463747048" MODIFIED="1515735898232" TEXT="context を切り替えながら処理をしていく"/> +<node CREATED="1515735901576" ID="ID_1462001635" MODIFIED="1515735952947" TEXT="Meta level から normal level への遷移も context を経由して行う"> +<node CREATED="1515735953434" ID="ID_1792294525" MODIFIED="1515735990034" TEXT="normal level の input data は contextがすべてのDGのポインタを持っているので可能"/> +<node CREATED="1515735990388" ID="ID_394841631" MODIFIED="1515736004025" TEXT="Output も 最終的には context に格納される"/> +</node> </node> <node CREATED="1492598864406" ID="ID_1687880423" MODIFIED="1492598866691" TEXT="TaskManager"> <node CREATED="1492599734061" ID="ID_653944383" MODIFIED="1492599741953" TEXT="Task Create"/> @@ -153,6 +174,29 @@ <node CREATED="1514281585150" ID="ID_355165624" MODIFIED="1514281597370" TEXT="length を先に決めておく"/> </node> </node> +<node CREATED="1512460350073" ID="ID_185870589" MODIFIED="1512460351791" TEXT="par goto"> +<node CREATED="1512460353973" ID="ID_1212844908" MODIFIED="1512460356687" TEXT="par goto iterate"/> +<node CREATED="1513922624345" ID="ID_13624334" MODIFIED="1513922630592" TEXT="並列実行用の構文"> +<node CREATED="1513922630782" ID="ID_9443031" MODIFIED="1513923980580" TEXT="par goto を書くと, task の生成, dependency の設定, taskManager への spawn(実体はWorker に task を send) までやってくれる"/> +<node CREATED="1513923983001" ID="ID_1400100723" MODIFIED="1513924003330" TEXT="task は context なので、context をいじる構文"> +<node CREATED="1513924004391" ID="ID_87004753" MODIFIED="1513924034173" TEXT="meta 計算として記述する"/> +<node CREATED="1513924013060" ID="ID_377338595" MODIFIED="1513926029012" TEXT="par goto は normal レベルで記述するはず"/> +<node CREATED="1513924024580" ID="ID_736053385" MODIFIED="1513926011683" TEXT="perl の script で meta 計算を生成する"/> +</node> +</node> +</node> +<node CREATED="1515489156397" ID="ID_1246229506" MODIFIED="1515489191477" TEXT="Thread 間通信"> +<node CREATED="1515489191801" ID="ID_1420841044" MODIFIED="1515489194164" TEXT="Semaphore"/> +</node> +<node CREATED="1515489496108" ID="ID_271409357" MODIFIED="1515489510090" TEXT="iterate"> +<node CREATED="1515489510551" ID="ID_15556582" MODIFIED="1515489538967" TEXT="配列や, Listなどの要素一つ一つに処理を適用するもの"/> +<node CREATED="1515489553012" ID="ID_431969583" MODIFIED="1515489602342" TEXT="一つ一つ要素への処理は並列で実行する"> +<node CREATED="1515489604871" ID="ID_1570107481" MODIFIED="1515489658574" TEXT="iterate な task を copy して, 指定した長さ分 task を作って並列に実行する"/> +<node CREATED="1515489662442" ID="ID_539429740" MODIFIED="1515489681211" TEXT="GPU へのマッピングでも使われる"> +<node CREATED="1515489681764" ID="ID_1709717666" MODIFIED="1515489682620" TEXT="SIMD"/> +</node> +</node> +</node> </node> <node CREATED="1512459624453" ID="ID_1863644916" MODIFIED="1512460342956" POSITION="right" TEXT="GPU 実行"> <node CREATED="1512459627489" ID="ID_1073024940" MODIFIED="1512459629873" TEXT="CUDA Worker"> @@ -162,6 +206,7 @@ <node CREATED="1512460155955" ID="ID_1415092848" MODIFIED="1512460177862" TEXT="Data Gear を GPU の Data構造にマッピングするためのもの"/> </node> <node CREATED="1512460105826" ID="ID_1054295790" MODIFIED="1512460153903" TEXT="Code Gear stub で GPU用のFunction を呼ぶ"/> +<node CREATED="1515489729575" ID="ID_970060224" MODIFIED="1515489758336" TEXT="Code Gear への待ち合わせの際に, cpu へ一度結果を書き出すので遅い"/> </node> <node CREATED="1512460310214" ID="ID_1936995951" MODIFIED="1512460317608" POSITION="right" TEXT="Gears OS の記述"> <node CREATED="1512460345799" ID="ID_149182714" MODIFIED="1512460349488" TEXT="Interface"> @@ -170,17 +215,6 @@ <node CREATED="1513922594130" ID="ID_229338484" MODIFIED="1513922620704" TEXT="つまり impl 毎に違う挙動を書く事ができる"/> </node> </node> -<node CREATED="1512460350073" ID="ID_185870589" MODIFIED="1512460351791" TEXT="par goto"> -<node CREATED="1512460353973" ID="ID_1212844908" MODIFIED="1512460356687" TEXT="par goto iterate"/> -<node CREATED="1513922624345" ID="ID_13624334" MODIFIED="1513922630592" TEXT="並列実行用の構文"> -<node CREATED="1513922630782" ID="ID_9443031" MODIFIED="1513923980580" TEXT="par goto を書くと, task の生成, dependency の設定, taskManager への spawn(実体はWorker に task を send) までやってくれる"/> -<node CREATED="1513923983001" ID="ID_1400100723" MODIFIED="1513924003330" TEXT="task は context なので、context をいじる構文"> -<node CREATED="1513924004391" ID="ID_87004753" MODIFIED="1513924034173" TEXT="meta 計算として記述する"/> -<node CREATED="1513924013060" ID="ID_377338595" MODIFIED="1513926029012" TEXT="par goto は normal レベルで記述するはず"/> -<node CREATED="1513924024580" ID="ID_736053385" MODIFIED="1513926011683" TEXT="perl の script で meta 計算を生成する"/> -</node> -</node> -</node> <node CREATED="1512460367213" ID="ID_567384353" MODIFIED="1512460368327" TEXT="stub"/> <node CREATED="1512460370758" ID="ID_945629592" MODIFIED="1512460383581" TEXT="perl script な 変換"/> </node>
--- a/paper/gearsOS.tex Sun Jan 07 05:22:05 2018 +0900 +++ b/paper/gearsOS.tex Wed Jan 17 08:48:10 2018 +0900 @@ -3,27 +3,27 @@ Gears OS はプログラムとデータの単位として Gear を用いる。 Gear は並列実行の単位、データの分割、Gear 間の接続等になる。 -Code Gear はプログラムの処理そのもので、任意の数の Input Data Gear を参照し、処理が完了すると任意の数の Output Data Gear に書き込む。 +Code Gear はプログラムの処理そのもので、\figref{cdg1} で示しているように任意の数の Input Data Gear を参照し、処理が完了すると任意の数の Output Data Gear に書き込む。 また、Code Gear は接続された Data Gear 以外には参照を行わない。 -Gears OS では \figref{codegear-datagear} で示しているように Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を可能とする。 +この Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を可能とする。 Code Gear 間の移動は継続を用いて行われる。 継続は関数呼び出しとは異なり、呼び出し元に戻らず、Code Gear 内で次の Code Gear への継続を行う。 -そのため Code Gear, Data Gear を使ったプログラミングは末尾再帰を強制したスタイルになる。 +そのため Code Gear、Data Gear を使ったプログラミングは末尾再帰を強制したスタイルになる。 Gear の特徴として処理やデータの構造が Code Gear、 Data Gear に閉じていることにある。 これにより、実行時間、メモリ使用量などを予想可能なものにする事が可能になる。 \begin{figure}[htbp] \begin{center} - \includegraphics[scale=1.0]{./fig/codegear-datagear.pdf} + \includegraphics[scale=0.6]{./fig/codegear-datagear.pdf} \end{center} - \caption{Code Gear と Data Gear の依存関係} - \label{fig:codegear-datagear} + \caption{Code Gear と Data Gear の関係} + \label{fig:cdg1} \end{figure} \section{Continuation based C} -Gears OS の実装は本研究室で開発されているCbC(Continuation based C) を用いて行う。 +Gears OS の実装は本研究室で開発されているCbC (Continuation based C) を用いて行う。 CbC は Code Gear を基本的な処理単位として記述できるプログラミング言語である。 CbC の記述例を\coderef{cg1}に, 実際にこのソースコードが実行される際の遷移を\figref{cg1}に示す。 @@ -31,13 +31,14 @@ Code Gear は継続で次の Code Gear に遷移する性質上、関数とは違い戻り値は持たない。 そのため、\_\_code は Code Gear の戻り値ではなく、Code Gear であることを示すフラグとなっている。 Code Gear から次の Code Gear への遷移は goto による継続で処理を行い、次の Code Gear への引数として入出力を与える。 -\coderef{cg1}内の goto cg1(a+b); が継続にあたり、(a+b) がcg1 への入力になる。 - -CbC の goto による継続は Scheme の継続と異なり、呼び出し元の環境を必要とせず、行き先を指定すれば良い。 -したがって、この継続を軽量継続と呼ぶ。 +\coderef{cg1}内の goto cg1 (a+b); が継続にあたり、 (a+b) がcg1 への入力になる。 \lstinputlisting[caption=CodeSegmentの軽量継続, label=code:cg1]{./src/cg1.cbc} +CbC の goto による継続は Scheme のcall/ccといった継続と異なり、呼び出し元の環境を必要とせず、行き先を指定すれば良い。 +この継続を軽量継続と呼ぶ。 +\coderef{cg1} は cs0 から cs1 へ継続したあとには cs0 へ戻らずに処理を続ける。 + \begin{figure}[htbp] \begin{center} \includegraphics[scale=1.0]{./fig/goto.pdf} @@ -46,7 +47,97 @@ \label{fig:cg1} \end{figure} -\section{Meta Computation} +\section{メタ計算} +プログラムの記述する際は、ノーマルレベルの計算の他に、メモリ管理、スレッド管理、CPUがGPUの資源管理等を記述しなければならない処理が存在する。 +これらの計算はノーマルレベルの計算と区別してメタ計算と呼ぶ。 + +メタ計算は関数型言語では Monad を用いて表現される。 +Monad は Haskell では実行時の環境を記述する構文として使われる。 + +従来の OS では、メタ計算はシステムコールやライブラリーコールの単位で行われる。 +実行時にメタ計算の変更を行う場合には OS 内部のパラメータの変更を使用し、実行されるユーザープログラム自体への変更は限定的である。 +しかし、メタ計算は性能測定あるいはプログラム検証、さらに並列分散計算のチューニングなど細かい処理が必要で実際のシステムコール単位では不十分である。 +例えば、モデル検査ではアセンブラあるいは バイトコード、インタプリタレベルでのメタ計算が必要になる。 +しかし、バイトコードレベルでは 粒度が細かすぎて扱いが困難になっている。具体的にはメタ計算の実行時間が大きくなってしまう。 + +\section{Meta Gear} +Gears OS の Code Gear は関数に比べて細かく分割されているため、メタ計算をより柔軟に記述できる。 +Code Gear と Data Gear にはそれぞれメタ計算の区分として Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実装する。 +Meta Gear は 制限された Monad に相当し、型付きアセンブラよりは大きな表現単位を提供する。 +Haskell などの関数型プログラミング言語では実行環境が複雑であり、実行時の資源使用を明確にすることができないが、Gears OS を記述している CbC はスタック上に隠された環境を持たないので、メタ計算で使用する資源を明確にできる利点がある。 +Meta Code Gear は\figref{mcg1}に示すように通常の Code Gear の直後に遷移され、メタ計算を実行する。 +また、 Meta Code Gear は、その階層からさらにメタ計算を記述することが可能である。 + +\begin{figure}[htbp] + \begin{center} + \includegraphics[scale=0.6]{./fig/meta_cg_dg.pdf} + \end{center} + \caption{Meta Code Gear の実行} + \label{fig:mcg1} +\end{figure} \section{Context} +Context は接続可能な Code/Data Gear のリスト、Data Gearを確保するメモリ空間、実行される Task への Code Gear等を持っている Meta Data Gearである。 +Gears OS では Code Gear と Data Gear への接続を Context を通して行う。 + +また、Context は並列実行の Task でもあり、従来のスレッドやプロセスに対応する。 +そのため Gears OS で並列実行を行うには Context を生成し、Task の実行を行う。 + +\coderef{context} に Context の定義を示す。 + +\lstinputlisting[caption=Contextの定義, label=code:context]{./src/context.h} + +\coderef{context} は以下の内容を定義している。 + +\begin{itemize} + \item Code Gear の名前と関数ポインタとの対応表 + Code Gear の名前とポインタの対応は Context 内の code(\coderef{context} 4行目) に格納される。 + code は全ての Code Gear を列挙した enum と関数ポインタの組で表現される。 + Code Gear の名前は enum で定義され、コンパイル後には整数へと変換される。 + 実際に Code Gear に接続する際は番号(enum)を指定することで接続を行う。 + これにより、メタ計算の実行時に接続する Code Gear を動的に切り替えることが可能となる。 + \item Data Gear の Allocation 用の情報 + Data Gear のメモリ空間は事前に領域を確保した後、必要に応じてその領域を割り当てることで実現する。 + 実際に Allocation する際は Context内の heap(\coderef{context} 8行目)を Data Gear のサイズ分インクリメントすることで実現する。 + \item Code Gear が参照する DataGear へのポインタ + Allocation で生成した Data Gear へのポインタは Context 内のdata(\coderef{context} 6行目) に格納される。 + Code Gear は data を参照して Data Gear へアクセスする。 + \item 並列実行用の Task 情報 + Context は 並列実行の Task も兼任するため、待っている Input Data Gear のカウンタ、Input/Output Data Gear が格納されている場所を示すインデックス、GPU での実行フラグ等を持っている(\coderef{context} 13-30行目)。 + \item Data Gear の型情報 + Data Gear は構造体を用いて定義する(\coderef{context} 34-49行目)。Timer や TimerImplなどの構造体が Data Gear に相当する。 + メタ計算では任意のData Gear を一律に扱うため、全ての Data Gear の共用体を定義する(\coderef{context} 33-51行目)。 + Data Gear を確保する際のサイズはこの型情報から決定する。 +\end{itemize} + \section{Interface} +Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合を表現する Data Gear である。 +Interface には複数の実装を持つことができ、実装によって実行する Code Gear を切り替えることが可能になる。 + +Queue の Interface を \coderef{queueInterface} に示す。 +Interface は API となる Code Gear を \_\_code として 定義(\coderef{queueInterface} 6-9行目)する。 +この \_\_code 実体は Code Gear への番号が格納される変数であり、Interface の実装毎に値は変化する。 + +\lstinputlisting[caption=QueueのInterface, label=code:queueInterface]{./src/queueInterface.h} + +\coderef{singleLinkedQueue} は Queue Interface を用いた SingleLinkedQueue の実装である。 +createSingleLinkedQueue(\coderef{singleLinkedQueue} 3-14 行目) は Queue Interface を実装した Data Gear の生成を行っている関数であり、 データ構造の初期化と実装した Code Gear の番号(enum)を Queue Interface で定義している Code Gear を示す変数に入れる(\coderef{singleLinkedQueue} 9-12行目)。 + +\lstinputlisting[caption=SingleLinkedQueue の実装, label=code:singleLinkedQueue]{./src/singleLinkedQueue.cbc} + +Interface での Code Gear 呼び出しは ``goto interface->method'' という構文で行う。 +ここの interface は createSingleLinkedQueue(\coderef{singleLinkedQueue} 3-14 行目) 等で初期化を行った Interface へのポインタ、method は実装した Code Gear の番号になる。 + +\coderef{singleLinkedQueueTest} に Queue Interface を使用した Code Gearの呼び出し例を示す。 +この呼び出しでは SingleLinkedQueue の put 実装に継続される。 + +\lstinputlisting[caption=Queue Interface での Code Gear の呼び出し, label=code:singleLinkedQueueTest]{./src/singleLinkedQueueTest.cbc} + +\coderef{singleLinkedQueueTest} は実際にはスクリプトによって \coderef{singleLinkedQueueTest_script} に変換されコンパイルされる。 +\coderef{singleLinkedQueueTest_script} 内の Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す。 +この引数格納用の Data Gear は Context の初期化の際に生成される。 +引数格納用の Data Gear を取り出した後は変換前の呼び出しの引数を Interface で定義した Code Gear の引数情報に合わせて格納し、 指定した Code Gear に継続する。 + +\lstinputlisting[caption=スクリプトによる変換後, label=code:singleLinkedQueueTest_script]{./src/singleLinkedQueueTest_script.cbc} + +\section {stub Code Gear}
--- a/paper/master_paper.tex Sun Jan 07 05:22:05 2018 +0900 +++ b/paper/master_paper.tex Wed Jan 17 08:48:10 2018 +0900 @@ -93,7 +93,6 @@ %chapters \input{introduction.tex} \input{gearsOS.tex} -%\input{cbc.tex} \input{structure_GearsOS.tex} \input{gpu.tex} \input{evaluation.tex}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/cg1.cbc Wed Jan 17 08:48:10 2018 +0900 @@ -0,0 +1,8 @@ +__code cg0(int a, int b) { + goto cg1(a+b); + +} + +__code cg1(int c) { + goto cg2(c); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/context.h Wed Jan 17 08:48:10 2018 +0900 @@ -0,0 +1,52 @@ +/* Context definition */ +struct Context { + enum Code next; + int codeNum; + __code (**code) (struct Context*); + union Data **data; + void* heapStart; + void* heap; + long heapLimit; + int dataNum; + + // task parameter + int idgCount; //number of waiting dataGear + int idg; + int maxIdg; + int odg; + int maxOdg; + int gpu; // GPU task + struct Worker* worker; + struct TaskManager* taskManager; + struct Context* task; + struct Element* taskList; +#ifdef USE_CUDAWorker + int num_exec; + CUmodule module; + CUfunction function; +#endif + /* multi dimension parameter */ + int iterate; + struct Iterator* iterator; +}; + +union Data { + struct Meta { + enum DataType type; + long size; + long len; + struct Queue* wait; // tasks waiting this dataGear + } Meta; + struct Context Context; + struct Timer { + union Data* timer; + enum Code start; + enum Code end; + enum Code next; + } Timer; + struct TimerImpl { + double time; + } TimerImpl; + .... +}; // union Data end this is necessary for context generator +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/initContext.c Wed Jan 17 08:48:10 2018 +0900 @@ -0,0 +1,26 @@ +#include <stdlib.h> + +#include "../context.h" + +void initContext(struct Context* context) { + context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE; + context->code = (__code(**) (struct Context*)) NEWN(ALLOCATE_SIZE, void*); + context->data = NEWN(ALLOCATE_SIZE, union Data*); + context->heapStart = NEWN(context->heapLimit, char); + context->heap = context->heapStart; + // context->codeNum = Exit; + + // Code Gear Init + context->code[C_code1] = code1_stub; + context->code[C_code2] = code2_stub; + .... + + + // allocate Default Data Gear + ALLOC_DATA(context, Context); + ALLOC_DATA(context, Meta); + ALLOC_DATA(context, Timer); + ALLOC_DATA(context, TimerImpl); + ... + context->dataNum = 45; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/queueInterface.h Wed Jan 17 08:48:10 2018 +0900 @@ -0,0 +1,10 @@ +typedef struct Queue<Impl>{ + union Data* queue; + union Data* data; + __code next(...); + __code whenEmpty(...); + __code clear(Impl* queue, __code next(...)); + __code put(Impl* queue, union Data* data, __code next(...)); + __code take(Impl* queue, __code next(union Data*, ...)); + __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...)); +} Queue;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/singleLinkedQueue.cbc Wed Jan 17 08:48:10 2018 +0900 @@ -0,0 +1,48 @@ +#interface "Queue.h" + +Queue* createSingleLinkedQueue(struct Context* context) { + struct Queue* queue = new Queue(); // Allocate Queue interface + struct SingleLinkedQueue* singleLinkedQueue = new SingleLinkedQueue(); // Allocate Queue implement + queue->queue = (union Data*)singleLinkedQueue; + singleLinkedQueue->top = new Element(); + singleLinkedQueue->last = singleLinkedQueue->top; + queue->clear = C_clearSingleLinkedQueue; + queue->put = C_putSingleLinkedQueue; + queue->take = C_takeSingleLinkedQueue; + queue->isEmpty = C_isEmptySingleLinkedQueue; + return queue; +} + +__code clearSingleLinkedQueue(struct SingleLinkedQueue* queue, __code next(...)) { + queue->top = NULL; + goto next(...); +} + +__code putSingleLinkedQueue(struct SingleLinkedQueue* queue, union Data* data, __code next(...)) { + Element* element = new Element(); + element->data = data; + element->next = NULL; + queue->last->next = element; + queue->last = element; + goto next(...); +} + +__code takeSingleLinkedQueue(struct SingleLinkedQueue* queue, __code next(union Data* data, ...)) { + struct Element* top = queue->top; + struct Element* nextElement = top->next; + if (queue->top == queue->last) { + data = NULL; + } else { + queue->top = nextElement; + data = nextElement->data; + } + goto next(data, ...); +} + +__code isEmptySingleLinkedQueue(struct SingleLinkedQueue* queue, __code next(...), __code whenEmpty(...)) { + if (queue->top == queue->last) + goto whenEmpty(...); + else + goto next(...); +} +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/singleLinkedQueueTest.cbc Wed Jan 17 08:48:10 2018 +0900 @@ -0,0 +1,8 @@ +#interface "Queue.h" + +__code code1() { + Queue* queue = createSingleLinkedQueue(context); + Node* node = new Node(); + node->color = Red; + goto queue->put(node, queueTest2); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/singleLinkedQueueTest_script.cbc Wed Jan 17 08:48:10 2018 +0900 @@ -0,0 +1,9 @@ +__code code1(struct Context *context) { + Queue* queue = createSingleLinkedQueue(context); + Node* node = &ALLOCATE(context, Node)->Node; + node->color = Red; + Gearef(context, Queue)->queue = (union Data*) queue; + Gearef(context, Queue)->data = (union Data*) node; + Gearef(context, Queue)->next = C_queueTest2; + goto meta(context, queue->put); +}