# HG changeset patch
# User matac42 <matac@cr.ie.u-ryukyu.ac.jp>
# Date 1705404272 -32400
# Node ID 4b5c140233f3434edc06f6ab968b7e2b0c9e7cf6
# Parent  f4b076177b9ace84e3b2eae1fcc309d49fd7a4fb
...

diff -r f4b076177b9a -r 4b5c140233f3 Paper/master_paper.lol
--- a/Paper/master_paper.lol	Tue Jan 16 19:31:10 2024 +0900
+++ b/Paper/master_paper.lol	Tue Jan 16 20:24:32 2024 +0900
@@ -2,7 +2,7 @@
 \contentsline {lstlisting}{\numberline {3.1}Queueのインターフェース}{12}{}%
 \contentsline {lstlisting}{\numberline {3.2}Interfaceの呼び出し}{13}{}%
 \contentsline {lstlisting}{\numberline {3.3}Queueのインターフェース}{13}{}%
-\contentsline {lstlisting}{\numberline {3.4}RedBlackTreeの実装}{15}{}%
-\contentsline {lstlisting}{\numberline {3.5}Treeの仕様}{15}{}%
-\contentsline {lstlisting}{\numberline {6.1}CopyRedBlackTreeの実装}{25}{}%
-\contentsline {lstlisting}{\numberline {6.2}CopyRedBlackTreeのアルゴリズム}{27}{}%
+\contentsline {lstlisting}{\numberline {3.4}Treeの仕様}{15}{}%
+\contentsline {lstlisting}{\numberline {3.5}RedBlackTreeの実装}{15}{}%
+\contentsline {lstlisting}{\numberline {6.1}CopyRedBlackTreeの実装}{26}{}%
+\contentsline {lstlisting}{\numberline {6.2}CopyRedBlackTreeのアルゴリズム}{28}{}%
diff -r f4b076177b9a -r 4b5c140233f3 Paper/master_paper.pdf
Binary file Paper/master_paper.pdf has changed
diff -r f4b076177b9a -r 4b5c140233f3 Paper/master_paper.tex
--- 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による分散ファイルシステム}
diff -r f4b076177b9a -r 4b5c140233f3 Paper/src/Tree.h
--- a/Paper/src/Tree.h	Tue Jan 16 19:31:10 2024 +0900
+++ b/Paper/src/Tree.h	Tue Jan 16 20:24:32 2024 +0900
@@ -7,7 +7,6 @@
   __code put(Impl* tree, Type* node, __code next(...));
   __code get(Impl* tree, Type* node, __code next(...));
   __code remove(Impl* tree, Type* node, __code next(...));
-  __code copy(Impl* tree, Type* node, __code next(...));
   // __code clearRedBlackTree();
   __code next(...);
 } Tree;
\ No newline at end of file
diff -r f4b076177b9a -r 4b5c140233f3 mindmaps/gears_fs_db.mm
--- a/mindmaps/gears_fs_db.mm	Tue Jan 16 19:31:10 2024 +0900
+++ b/mindmaps/gears_fs_db.mm	Tue Jan 16 20:24:32 2024 +0900
@@ -326,6 +326,29 @@
 </node>
 <node TEXT="証明しやすい" ID="ID_1313077784" CREATED="1699849438956" MODIFIED="1699849443715"/>
 <node TEXT="全ての操作が最悪でもO(log n)" ID="ID_1382477887" CREATED="1699855369743" MODIFIED="1699855390827"/>
+<node TEXT="GearsFileSystemで用いられる重要な構造" ID="ID_1889670571" CREATED="1705393830088" MODIFIED="1705393854760"/>
+<node TEXT="GearsOSのRedBlackTree" ID="ID_1808262456" CREATED="1704625749056" MODIFIED="1704625759342">
+<node TEXT="Tree仕様" ID="ID_247537990" CREATED="1705298991306" MODIFIED="1705299008258">
+<node TEXT="Tree.h" ID="ID_1679703570" CREATED="1705299046915" MODIFIED="1705299050496">
+<node TEXT="仕様の定義" ID="ID_1409400056" CREATED="1705299053969" MODIFIED="1705299066971"/>
+</node>
+</node>
+<node TEXT="RedBlackTree実装" ID="ID_1365581239" CREATED="1704625938387" MODIFIED="1705299021394">
+<node TEXT="RedBlackTree.h" ID="ID_514994168" CREATED="1705057440091" MODIFIED="1705057447006">
+<node TEXT="implの型定義ファイル" ID="ID_884167229" CREATED="1705299034323" MODIFIED="1705299041442"/>
+</node>
+</node>
+<node TEXT="Tree interface" ID="ID_1582061146" CREATED="1705050144077" MODIFIED="1705050161749">
+<node TEXT="DG" ID="ID_1117156367" CREATED="1705050163353" MODIFIED="1705050166212"/>
+<node TEXT="CG" ID="ID_892070786" CREATED="1705050166599" MODIFIED="1705050168009"/>
+</node>
+</node>
+<node TEXT="Red-black tree(一般的な説明)" ID="ID_89990981" CREATED="1705402671067" MODIFIED="1705402684466">
+<node TEXT="二分探索木" ID="ID_899325725" CREATED="1705402685486" MODIFIED="1705402941637"/>
+<node TEXT="ノードに赤or黒の色をつける" ID="ID_594853418" CREATED="1705402942420" MODIFIED="1705402969509"/>
+<node TEXT="探索，挿入，削除操作のオーダーが最悪の場合でもO(log n)" ID="ID_1352435743" CREATED="1705402694002" MODIFIED="1705402896426"/>
+<node TEXT="データ構造の一つ" ID="ID_1144589445" CREATED="1705402772112" MODIFIED="1705402780832"/>
+</node>
 </node>
 <node TEXT="Rustの所有権" POSITION="right" ID="ID_612327915" CREATED="1704949737149" MODIFIED="1704949745661">
 <node TEXT="メモリを所有する変数のスコープを抜けるとメモリも解放される" ID="ID_972875880" CREATED="1704949746103" MODIFIED="1704949765401"/>
@@ -439,7 +462,7 @@
 </node>
 <node TEXT="Contextを含めたGear遷移" ID="ID_1897519980" CREATED="1704779305504" MODIFIED="1704779324312"/>
 </node>
-<node TEXT="モジュール化の仕組みinterface" ID="ID_979914453" CREATED="1705044283721" MODIFIED="1705045105599">
+<node TEXT="モジュール化の仕組みinterface" FOLDED="true" ID="ID_979914453" CREATED="1705044283721" MODIFIED="1705045105599">
 <node TEXT="モジュール化の仕組み" ID="ID_1323690074" CREATED="1705044424301" MODIFIED="1705044435039">
 <node TEXT="Javaのクラスのような仕組み" ID="ID_515246380" CREATED="1705044987112" MODIFIED="1705045006109"/>
 <node TEXT="使用するDGとCGをまとめる" ID="ID_1867289776" CREATED="1705045011571" MODIFIED="1705045022968"/>
@@ -461,6 +484,8 @@
 <node TEXT="interfaceの実装を書く場合に記述する" ID="ID_1568057342" CREATED="1705055994617" MODIFIED="1705056004662"/>
 <node TEXT="implの後ろに実装したいinterface名する" ID="ID_138244749" CREATED="1705056004945" MODIFIED="1705056045083"/>
 <node TEXT="asの後ろに実装の型名を記述する" ID="ID_238410525" CREATED="1705056022794" MODIFIED="1705056041152"/>
+<node TEXT="昔はInterfaceという記述だった" ID="ID_1185735068" CREATED="1705396899032" MODIFIED="1705396911079"/>
+<node TEXT="清水によって追加された記法" ID="ID_1097652467" CREATED="1705397130415" MODIFIED="1705397143359"/>
 </node>
 <node TEXT="create" ID="ID_115012523" CREATED="1705052063509" MODIFIED="1705052066013">
 <node TEXT="コンストラクタである" ID="ID_690330298" CREATED="1705056555895" MODIFIED="1705056577812"/>
@@ -476,16 +501,10 @@
 <node TEXT="SingleLinkedQueue.h" ID="ID_626185032" CREATED="1705052116061" MODIFIED="1705052122797">
 <node TEXT="implementの型定義ファイル" ID="ID_1696501093" CREATED="1705057355651" MODIFIED="1705057369742"/>
 </node>
+<node TEXT="return必要？" ID="ID_368470184" CREATED="1705391830441" MODIFIED="1705391835590"/>
 </node>
 </node>
-<node TEXT="GearsOSのRedBlackTree" ID="ID_894257471" CREATED="1704625749056" MODIFIED="1704625759342">
-<node TEXT="Treeの実装である" ID="ID_830044324" CREATED="1704625938387" MODIFIED="1705057404508"/>
-<node TEXT="Tree interface" ID="ID_137044314" CREATED="1705050144077" MODIFIED="1705050161749">
-<node TEXT="DG" ID="ID_1897529344" CREATED="1705050163353" MODIFIED="1705050166212"/>
-<node TEXT="CG" ID="ID_710468405" CREATED="1705050166599" MODIFIED="1705050168009"/>
-</node>
-<node TEXT="RedBlackTree.h" ID="ID_1180765067" CREATED="1705057440091" MODIFIED="1705057447006"/>
-</node>
+<node TEXT="GearsOSのRedBlackTree" ID="ID_594513732" CREATED="1705400358246" MODIFIED="1705400364641"/>
 </node>
 <node TEXT="GearsOSのファイルシステム(現状の話" FOLDED="true" ID="ID_667012992" CREATED="1701694178540" MODIFIED="1704630791818">
 <node TEXT="GearsOSのファイルシステム" ID="ID_188577314" CREATED="1704630094596" MODIFIED="1704630099465">