Mercurial > hg > Papers > 2024 > matac-master
changeset 65:47b4ddf35b1d
...
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Wed, 07 Feb 2024 14:32:11 +0900 |
| parents | 6513f369e624 |
| children | b036cdccbdcc |
| files | Paper/fig/test_pattern.drawio Paper/fig/test_pattern.pdf Paper/master_paper.pdf Paper/master_paper.tex mindmaps/gears_fs_db.mm |
| diffstat | 5 files changed, 272 insertions(+), 9 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/fig/test_pattern.drawio Wed Feb 07 14:32:11 2024 +0900 @@ -0,0 +1,231 @@ +<mxfile host="65bd71144e"> + <diagram id="_LRVqJ0d2ANkV6t0JXP-" name="Page-1"> + <mxGraphModel dx="662" dy="532" 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="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="150" y="310" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="5" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="3" target="4"> + <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="230" y="310" 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="200" y="350" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="6" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="7" target="8"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="10" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="7" target="9"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="7" 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="370" y="310" 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="340" y="350" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="9" 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="400" y="350" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="14" style="edgeStyle=none;html=1;endArrow=none;endFill=0;startArrow=none;entryX=0.334;entryY=0.439;entryDx=0;entryDy=0;entryPerimeter=0;" edge="1" parent="1" target="15" source="16"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="280" y="320" as="sourcePoint"/> + </mxGeometry> + </mxCell> + <mxCell id="15" 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="300" y="350" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="17" value="" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" target="16"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="280" y="320" as="sourcePoint"/> + <mxPoint x="250" y="360" as="targetPoint"/> + </mxGeometry> + </mxCell> + <mxCell id="16" 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="270" y="310" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="18" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="20" target="21"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="19" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="20" target="22"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="20" 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="150" y="370" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="24" style="edgeStyle=none;html=1;entryX=0.566;entryY=0.598;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="21" target="23"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="21" 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="120" y="410" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="22" 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="180" y="410" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="23" 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="90" y="450" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="28" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="30" target="31"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="29" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="30" target="32"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="30" 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="230" y="370" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="31" 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="200" y="410" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="34" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="32" target="33"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="32" 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="260" y="410" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="33" 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="290" y="450" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="35" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="37" target="38"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="36" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="37" target="40"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="37" 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="440" y="370" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="38" 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="410" y="410" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="39" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="40" target="41"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="40" 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="470" y="410" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="41" 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="440" y="450" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="42" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="44" target="46"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="43" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="44" target="47"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="44" 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="350" y="370" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="45" style="edgeStyle=none;html=1;entryX=0.566;entryY=0.598;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="46" target="48"> + <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="320" y="410" 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="380" y="410" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="48" 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="350" y="450" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="49" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="51" target="53"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="50" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="51" target="54"> + <mxGeometry relative="1" 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="150" y="470" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="52" style="edgeStyle=none;html=1;entryX=0.566;entryY=0.598;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="53" target="55"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="64" style="edgeStyle=none;html=1;entryX=0.468;entryY=0.641;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="53" target="63"> + <mxGeometry relative="1" 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="120" y="510" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="54" 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="180" y="510" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="55" 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="90" y="550" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="56" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="58" target="59"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="57" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="58" target="61"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="58" 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="230" y="470" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="59" 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="200" y="510" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="60" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="61" target="62"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="66" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="61" target="65"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="61" 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="260" y="510" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="62" 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="290" y="550" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="63" 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="150" y="550" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="65" 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="230" y="550" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="67" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="69" target="70"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="68" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="69" target="73"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="69" 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="380" y="470" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="77" style="edgeStyle=none;html=1;entryX=0.624;entryY=0.666;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="70" target="76"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="79" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="70" target="78"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="70" 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="350" y="510" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="71" style="edgeStyle=none;html=1;endArrow=none;endFill=0;entryX=0.69;entryY=0.02;entryDx=0;entryDy=0;entryPerimeter=0;" edge="1" parent="1" source="73" target="74"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="72" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="73" target="75"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="73" 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="410" y="510" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="74" 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="440" y="550" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="75" 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="550" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="76" 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="320" y="550" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="78" 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="370" y="550" width="20" height="20" as="geometry"/> + </mxCell> + </root> + </mxGraphModel> + </diagram> +</mxfile> \ No newline at end of file
--- a/Paper/master_paper.tex Wed Feb 07 13:38:42 2024 +0900 +++ b/Paper/master_paper.tex Wed Feb 07 14:32:11 2024 +0900 @@ -973,7 +973,7 @@ \label{fig:swap} \end{figure} -\chapter{評価} +\chapter{実装の評価} \section{非破壊RedBlackTreeの増大抑制} @@ -988,16 +988,44 @@ 別Contextへ木をコピーし， コピー元のContext自体を廃棄する仕組みを実装することでメモリ領域の再利用が可能であると考える． +\section{テストコード} + +CopyRedBlackTreeのプログラムを作成する際に， +図\ref{testPattern}のような11パターンの木の状態と10000ノードの木をコピーするテストコードを作成した． +11パターンの木の状態においてコピーは動作した． +10000ノードの木のコピーはヒープオーバーフローによるsegmentation fault errorが発生する． +3616ノードでは動作するため，ヒープ領域の容量が不足していると考えられる． +この事象を解決するためには，ALLOCATEする際にヒープ領域の容量不足を検知し， +ヒープ領域の拡張を行うことが考えられる． +これらのテストコードによってある程度の動作確認は可能であるが， +完全に正しい動作をしているかどうかの証明はできていない． + +\begin{figure}[ht] + \begin{center} + \includegraphics[width=120mm]{fig/test_pattern.pdf} + \end{center} + \caption{CopyRedBlackTreeのテストパターン} + \label{fig:testPattern} +\end{figure} + \section{RedBlackTreeの持続性} +CopyRedBlackTreeは木を単純にコピーする機能であるため， +RedBlackTree乃至，データの持続性が確保されている． + + +\section{Stackの使用} + +今回の実装ではSingleLinkedStackを2つ使用している． +CbCはcall stackなどの状態を持たないことによる利点があるため， +Stackを使用することによってその利点を得られなくなってしまうことが考えられる． +しかしながら，今回のStackはCall stackとは違い，プログラムの中で明示的に使用され， +また，CodeGear自体が状態を持たないため問題がない． + +\section{GCやレプリケーションへの適用} + -\section{ヒープオーバーフロー問題} - -\section{Stackの使用} - - -\section{同一Contextへのコピー} \chapter{まとめと今後の課題} @@ -1020,6 +1048,10 @@ 想定した動作をするか確認するために木を生成するコードを書いた． C言語で +\section{ヒープオーバーフロー問題} + +\section{テストコードでは不完全な部分} + \section{ファイルシステムにおけるスキーマ}
--- a/mindmaps/gears_fs_db.mm Wed Feb 07 13:38:42 2024 +0900 +++ b/mindmaps/gears_fs_db.mm Wed Feb 07 14:32:11 2024 +0900 @@ -958,7 +958,7 @@ </node> <node TEXT="tree->rootを書き換えて，途中のノードからコピーできるみたいなの作りたい" ID="ID_1603927493" CREATED="1706692686178" MODIFIED="1706692704418"/> </node> -<node TEXT="評価" FOLDED="true" POSITION="right" ID="ID_1699170037" CREATED="1706803749390" MODIFIED="1707213585346" HGAP_QUANTITY="14.75 pt" VSHIFT_QUANTITY="121.5 pt"> +<node TEXT="評価" POSITION="right" ID="ID_1699170037" CREATED="1706803749390" MODIFIED="1707213585346" HGAP_QUANTITY="14.75 pt" VSHIFT_QUANTITY="121.5 pt"> <node TEXT="説明" ID="ID_1332913546" CREATED="1707024290462" MODIFIED="1707024304655"> <node TEXT="テストコード" ID="ID_83989606" CREATED="1707024312272" MODIFIED="1707024315913"> <node TEXT="いくつかの考えられる木の形はテストした" ID="ID_401372478" CREATED="1707024501611" MODIFIED="1707024539431"> @@ -1055,7 +1055,7 @@ <node TEXT="それ以外はまとめと今後の課題に書く" ID="ID_1941288242" CREATED="1706803862696" MODIFIED="1706803878303"/> </node> </node> -<node TEXT="まとめと今後の課題" POSITION="right" ID="ID_912711900" CREATED="1706956151544" MODIFIED="1707213611142"> +<node TEXT="まとめと今後の課題" FOLDED="true" POSITION="right" ID="ID_912711900" CREATED="1706956151544" MODIFIED="1707213611142"> <node TEXT="非破壊RedBlackTreeの増大を防ぐ仕組みを構築できた" ID="ID_418966492" CREATED="1706956585170" MODIFIED="1706956610719"/> <node TEXT="別コンテキストへのコピー" ID="ID_1209930854" CREATED="1706956313462" MODIFIED="1706956324424"/> <node TEXT="GearsOS全体をGCすることも考えられる" ID="ID_1250275844" CREATED="1707013490904" MODIFIED="1707013522142"/>