Mercurial > hg > Papers > 2024 > matac-master

changeset 38:9e5d521df475

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
rbtree def fig
author matac42 <matac@cr.ie.u-ryukyu.ac.jp>
date Sat, 20 Jan 2024 14:27:59 +0900
parents 727091139c84
children 701d5906f7f0
files Paper/fig/rbtree_def.drawio Paper/fig/rbtree_def.png Paper/master_paper.lol Paper/master_paper.pdf Paper/master_paper.tex TODO.md
diffstat 6 files changed, 151 insertions(+), 9 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/fig/rbtree_def.drawio	Sat Jan 20 14:27:59 2024 +0900
@@ -0,0 +1,130 @@
+<mxfile host="65bd71144e">
+    <diagram id="PxV3Z1aBI1mM_MlTBdEj" name="Page-1">
+        <mxGraphModel dx="818" dy="647" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0">
+            <root>
+                <mxCell id="0"/>
+                <mxCell id="1" parent="0"/>
+                <mxCell id="75" value="" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;fillColor=none;strokeColor=#999999;" vertex="1" parent="1">
+                    <mxGeometry x="300" y="20" width="260" height="260" as="geometry"/>
+                </mxCell>
+                <mxCell id="73" value="" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;fillColor=none;strokeColor=#999999;" vertex="1" parent="1">
+                    <mxGeometry x="30" y="20" width="260" height="260" as="geometry"/>
+                </mxCell>
+                <mxCell id="9" style="edgeStyle=none;html=1;entryX=0.55;entryY=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="2" target="4">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="10" style="edgeStyle=none;html=1;entryX=0.45;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="2" target="3">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="2" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="360" y="107.5" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="11" style="edgeStyle=none;html=1;entryX=0.7;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="3" target="8">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="12" style="edgeStyle=none;html=1;entryX=0.4;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="3" target="5">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="3" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="390" y="147.5" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="4" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="330" y="147.5" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="5" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="420" y="187.5" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="8" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="360" y="187.5" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="41" style="edgeStyle=none;html=1;entryX=0.55;entryY=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="43" target="47">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="42" style="edgeStyle=none;html=1;entryX=0.45;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="43" target="46">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="43" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="70" y="95" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="44" style="edgeStyle=none;html=1;entryX=0.7;entryY=0.5;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="46" target="53">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="45" style="edgeStyle=none;html=1;entryX=0.4;entryY=0.7;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="46" target="50">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="46" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="100" y="135" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="47" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="40" y="135" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="48" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="50" target="52">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="49" style="edgeStyle=none;html=1;entryX=0.3;entryY=0.95;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="50" target="51">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="50" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="130" y="175" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="51" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="160" y="215" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="52" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="100" y="215" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="53" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1">
+                    <mxGeometry x="70" y="175" width="20" height="20" as="geometry"/>
+                </mxCell>
+                <mxCell id="58" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0.503;entryY=0.347;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;curved=1;dashed=1;" edge="1" parent="1" source="54" target="43">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="54" value="root" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="160" y="70" width="30" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="60" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;entryX=0.586;entryY=0.347;entryDx=0;entryDy=0;entryPerimeter=0;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="55" target="46">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="55" value="previous" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="174" y="105" width="60" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="61" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="56" target="50">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="56" value="current" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="200" y="145" width="50" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="62" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;entryX=0.642;entryY=0.292;entryDx=0;entryDy=0;entryPerimeter=0;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="57" target="51">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="57" value="newNode" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="220" y="185" width="60" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="66" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;entryX=0.704;entryY=0.481;entryDx=0;entryDy=0;entryPerimeter=0;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="63" target="2">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="63" value="grandparent" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="450" y="82.5" width="80" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="67" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="64" target="3">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="64" value="parent" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="475" y="117.5" width="50" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="68" style="edgeStyle=orthogonalEdgeStyle;curved=1;html=1;dashed=1;endArrow=none;endFill=0;" edge="1" parent="1" source="65" target="5">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="65" value="operation node" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="465" y="157.5" width="90" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="70" value="Parent RedBlackTree" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="100" y="40" width="120" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="71" value="When rotating" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="385" y="40" width="90" height="30" as="geometry"/>
+                </mxCell>
+            </root>
+        </mxGraphModel>
+    </diagram>
+</mxfile>
\ No newline at end of file
Binary file Paper/fig/rbtree_def.png has changed
--- a/Paper/master_paper.lol	Fri Jan 19 19:50:13 2024 +0900
+++ b/Paper/master_paper.lol	Sat Jan 20 14:27:59 2024 +0900
@@ -5,6 +5,6 @@
 \contentsline {lstlisting}{\numberline {3.4}SingleLinkedQueueの型定義}{15}{}%
 \contentsline {lstlisting}{\numberline {3.5}Treeの仕様}{15}{}%
 \contentsline {lstlisting}{\numberline {3.6}RedBlackTreeの実装}{16}{}%
-\contentsline {lstlisting}{\numberline {3.7}RedBlackTreeの仕様}{16}{}%
-\contentsline {lstlisting}{\numberline {6.1}CopyRedBlackTreeの実装}{27}{}%
-\contentsline {lstlisting}{\numberline {6.2}CopyRedBlackTreeのアルゴリズム}{29}{}%
+\contentsline {lstlisting}{\numberline {3.7}RedBlackTreeの実装の型定義}{16}{}%
+\contentsline {lstlisting}{\numberline {6.1}CopyRedBlackTreeの実装}{28}{}%
+\contentsline {lstlisting}{\numberline {6.2}CopyRedBlackTreeのアルゴリズム}{30}{}%
Binary file Paper/master_paper.pdf has changed
--- a/Paper/master_paper.tex	Fri Jan 19 19:50:13 2024 +0900
+++ b/Paper/master_paper.tex	Sat Jan 20 14:27:59 2024 +0900
@@ -361,8 +361,7 @@
 
 GearsOSのRedBlackTreeはGearsFileSystemで用いられる重要な構造の1つであり，
 ディレクトリ構造を表現するために使用されている．
-GearsOSにおけるTreeの仕様記述をソースコード\ref{src:Tree.h}に，
-RedBlackTreeの実装の記述の一部をソースコード\ref{src:RedBlackTreeImpl.cbc}に示す．
+GearsOSにおけるTreeの仕様記述をソースコード\ref{src:Tree.h}に示す．
 
 \lstinputlisting[label=src:Tree.h, caption=Treeの仕様]{src/Tree.h}
 
@@ -375,13 +374,25 @@
 取得は，指定したnodeと一致するノードを木から探し，
 存在すればそのまま返す．
 
+次に，RedBlackTreeの実装の記述の一部をソースコード\ref{src:RedBlackTreeImpl.cbc}に示す．
+
 \lstinputlisting[label=src:RedBlackTreeImpl.cbc, caption=RedBlackTreeの実装]{src/RedBlackTreeImpl.cbc}
 
 ソースコード\ref{src:RedBlackTreeImpl.cbc}の4行目から，
-RedBlackTreeはTreeの仕様の実装であることがわかり，
+RedBlackTreeはTreeの実装の　であることがわかり，
 13〜16行目で仕様に対応するCodeGearを初期化している．
 
-\lstinputlisting[label=src:RedBlackTree.h, caption=RedBlackTreeの仕様]{src/RedBlackTree.h}
+次に，RedBlackTreeの実装の型定義をソースコード\ref{src:RedBlackTree.h}に示す．
+
+\lstinputlisting[label=src:RedBlackTree.h, caption=RedBlackTreeの実装の型定義]{src/RedBlackTree.h}
+
+\begin{figure}[ht]
+  \begin{center}
+      \includegraphics[width=160mm]{fig/rbtree_def.png}
+  \end{center}
+  \caption{RedBlackTreeの型}
+  \label{fig:rbtree-def}
+\end{figure}
 
 \chapter{GearsFileSystem}
 
--- a/TODO.md	Fri Jan 19 19:50:13 2024 +0900
+++ b/TODO.md	Sat Jan 20 14:27:59 2024 +0900
@@ -1,10 +1,11 @@
 - [x] 要旨
 - [x] 1章 最後
 - [x] implementの型定義の説明
+- [x] 謝辞
+
 - [ ] GearsOSのRedBlackTreeの説明
 - [ ] DGMによる分散ファイルシステム
 - [ ] レプリケーションの説明
 - [ ] 実装の説明
 - [ ] まとめ
-- [ ] 今後の課題
-- [x] 謝辞
\ No newline at end of file
+- [ ] 今後の課題
\ No newline at end of file