Mercurial > hg > Papers > 2024 > matac-master
diff Paper/master_paper.tex @ 28:4b5c140233f3
...
author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 16 Jan 2024 20:24:32 +0900 |
parents | f4b076177b9a |
children | 92e8cd87fb2b |
line wrap: on
line diff
--- a/Paper/master_paper.tex Tue Jan 16 19:31:10 2024 +0900 +++ b/Paper/master_paper.tex Tue Jan 16 20:24:32 2024 +0900 @@ -335,7 +335,7 @@ そのためこのnewはC言語のnewとは違うGearsOS独自の記述であり, 実際にはメタレベルにアロケートを行う処理を挿入している. 10〜16行目ではSingleLinkedQueueで使用するCodeGearとDataGearを -queueのメソッドとしてセットしている. +queueのメソッドとして初期化している. CodeGearはQueueの仕様で記述したCodeGearと一致している. \texttt{C\_}で始まる記述にはenum CodeにおけるCodeGearの整数を格納している. CodeGearはenum Codeで整数と対応付けられており, @@ -346,15 +346,24 @@ \section{GearsOSのRedBlackTree} -RedBlackTreeはGearsFileSystemで用いられる重要な構造の1つであり, -ディレクトリ構造を表現するために使用されている. -GearsOSにおけるRedBlackTreeの実装の記述の一部をソースコード\ref{src:RedBlackTreeImpl.cbc}, -Treeの仕様記述をソースコード\ref{src:Tree.h}に示す. +Red-black tree(赤黒木)は二分探索木の一種で, +ノードに赤か黒の色を付けて色に関するいくつかの条件をもつデータ構造である. +木に対する探索,挿入,削除操作における最悪計算量がO(log n)であるため, +赤黒木は大規模なデータを扱う際に効率的なデータ構造となる. -\lstinputlisting[label=src:RedBlackTreeImpl.cbc, caption=RedBlackTreeの実装]{src/RedBlackTreeImpl.cbc} +GearsOSのRedBlackTreeはGearsFileSystemで用いられる重要な構造の1つであり, +ディレクトリ構造を表現するために使用されている. +GearsOSにおけるTreeの仕様記述をソースコード\ref{src:Tree.h}に, +RedBlackTreeの実装の記述の一部をソースコード\ref{src:RedBlackTreeImpl.cbc}に示す. + \lstinputlisting[label=src:Tree.h, caption=Treeの仕様]{src/Tree.h} +\lstinputlisting[label=src:RedBlackTreeImpl.cbc, caption=RedBlackTreeの実装]{src/RedBlackTreeImpl.cbc} -4行目からRedBlackTreeはTreeの仕様の実装であることがわかる. +ソースコード\ref{src:Tree.h}より,Treeはtree DataGearと +put,get,remove,nextの4つのCodeGearを持っていることがわかる. +ソースコード\ref{src:RedBlackTreeImpl.cbc}の4行目から, +RedBlackTreeはTreeの仕様の実装であることがわかり, +13〜16行目で仕様に対応するCodeGearを初期化している. \chapter{GearsOSのファイルシステム} \section{DataGearManagerによる分散ファイルシステム}