<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>UbixOS V2: src/sys/ubixfsv2/btree.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
<link href="tabs.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.4.7 -->
<div class="tabs">
<ul>
<li><a href="main.html"><span>Main Page</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="classes.html"><span>Data Structures</span></a></li>
<li id="current"><a href="files.html"><span>Files</span></a></li>
<li><a href="dirs.html"><span>Directories</span></a></li>
<li>
<form action="search.php" method="get">
<table cellspacing="0" cellpadding="0" border="0">
<tr>
<td><label> <u>S</u>earch for </label></td>
<td><input type="text" name="query" value="" size="20" accesskey="s"/></td>
</tr>
</table>
</form>
</li>
</ul></div>
<div class="tabs">
<ul>
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>Globals</span></a></li>
</ul></div>
<div class="nav">
<a class="el" href="dir_897b6a2d7bab147dd1db58381aad3984.html">src</a> » <a class="el" href="dir_832905b1f7f5feaf61a306b40c0ac817.html">sys</a> » <a class="el" href="dir_21e0927e9dd41d8ff1206ca4f0555726.html">ubixfsv2</a></div>
<h1>btree.h</h1><a href="btree_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="preprocessor">#ifndef BTREE_H</span>
<a name="l00002"></a>00002 <span class="preprocessor"></span><span class="preprocessor">#define BTREE_H</span>
<a name="l00003"></a>00003 <span class="preprocessor"></span>
<a name="l00004"></a>00004 <span class="preprocessor">#include <stdio.h></span>
<a name="l00005"></a>00005
<a name="l00006"></a>00006 <span class="preprocessor">#include "<a class="code" href="ubixfsv2_2ubixfs_8h.html">ubixfs.h</a>"</span>
<a name="l00007"></a>00007 <span class="preprocessor">#include "<a class="code" href="btreeheader_8h.html">btreeheader.h</a>"</span>
<a name="l00008"></a>00008 <span class="preprocessor">#include "<a class="code" href="ubixfsv2_2file_8h.html">file.h</a>"</span>
<a name="l00009"></a>00009
<a name="l00010"></a><a class="code" href="btree_8h.html#6068ceea0c729502fc2c30fb5fe68e75">00010</a> <span class="preprocessor">#define B_NODE_MAGIC_1 0xDEADBEEF</span>
<a name="l00011"></a><a class="code" href="btree_8h.html#6d1cceff07f71b93f2b82935353e3846">00011</a> <span class="preprocessor"></span><span class="preprocessor">#define B_NODE_MAGIC_2 0x1900BABE</span>
<a name="l00012"></a>00012 <span class="preprocessor"></span>
<a name="l00013"></a><a class="code" href="btree_8h.html#d0a8c9702b88c517fad6d76b2f2e837c">00013</a> <span class="preprocessor">#define B_MAX_KEYS 15</span>
<a name="l00014"></a><a class="code" href="btree_8h.html#4d914af1586d2b2c41b4427e9488decf">00014</a> <span class="preprocessor"></span><span class="preprocessor">#define B_MAX_NAME_LENGTH 240</span>
<a name="l00015"></a><a class="code" href="btree_8h.html#6612d45a89119eb036b8f2f28c99205c">00015</a> <span class="preprocessor"></span><span class="preprocessor">#define B_MAX_CHILD_COUNT 4</span>
<a name="l00016"></a>00016 <span class="preprocessor"></span>
<a name="l00017"></a>00017 <span class="comment">// if any of these structs change they have to be updated in the format</span>
<a name="l00018"></a>00018 <span class="comment">// utility too</span>
<a name="l00019"></a>00019
<a name="l00020"></a><a class="code" href="structbNode.html">00020</a> <span class="keyword">typedef</span> <span class="keyword">struct </span><a class="code" href="structbNode.html">bNode</a> {
<a name="l00021"></a>00021 <a class="code" href="include_2ubixos_2types_8h.html#5847ea0262a5aa61eee48cbe95544a78">uInt32</a> magic1 <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00022"></a>00022 <a class="code" href="include_2ubixos_2types_8h.html#5847ea0262a5aa61eee48cbe95544a78">uInt32</a> used <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00023"></a>00023 <a class="code" href="unionuPtr.html">uPtr</a> parent <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00024"></a>00024 <a class="code" href="ubixfsv2_2types_8h.html#3eb5cd6e01deaee22057b8182b791bd3">uInt64</a> tag <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00025"></a>00025 <span class="keywordtype">char</span> keys[<a class="code" href="btree_8h.html#d0a8c9702b88c517fad6d76b2f2e837c">B_MAX_KEYS</a>][<a class="code" href="btree_8h.html#4d914af1586d2b2c41b4427e9488decf">B_MAX_NAME_LENGTH</a>] <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00026"></a>00026 <span class="keywordtype">bool</span> present[<a class="code" href="btree_8h.html#d0a8c9702b88c517fad6d76b2f2e837c">B_MAX_KEYS</a>+1] <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00027"></a>00027 <a class="code" href="unionuPtr.html">uPtr</a> head[<a class="code" href="btree_8h.html#d0a8c9702b88c517fad6d76b2f2e837c">B_MAX_KEYS</a>+1] <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00028"></a>00028 <a class="code" href="unionuPtr.html">uPtr</a> tail[<a class="code" href="btree_8h.html#d0a8c9702b88c517fad6d76b2f2e837c">B_MAX_KEYS</a>+1] <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00029"></a>00029 <a class="code" href="include_2ubixos_2types_8h.html#5847ea0262a5aa61eee48cbe95544a78">uInt32</a> childCount[<a class="code" href="btree_8h.html#d0a8c9702b88c517fad6d76b2f2e837c">B_MAX_KEYS</a>+1] <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00030"></a>00030 <a class="code" href="include_2ubixos_2types_8h.html#5847ea0262a5aa61eee48cbe95544a78">uInt32</a> magic2 <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00031"></a>00031 <span class="keywordtype">bool</span> leaf <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00032"></a>00032 <span class="keywordtype">char</span> reserved[131] <a class="code" href="structbNode.html#8cd46327a348d2717169b3b5e0a51cf8">__attribute__</a> ((<a class="code" href="gdt_8h.html#a8e25552752eade51544ff9e9fbd7bdf">packed</a>));
<a name="l00033"></a>00033 } <a class="code" href="structbNode.html">bNode</a>; <span class="comment">// bNode</span>
<a name="l00034"></a>00034
<a name="l00035"></a>00035 <span class="keyword">struct </span><a class="code" href="structubixfsInode.html">ubixfsInode</a>;
<a name="l00036"></a>00036
<a name="l00037"></a><a class="code" href="classbTree.html">00037</a> <span class="keyword">class </span><a class="code" href="classbTree.html">bTree</a> {
<a name="l00038"></a>00038 <span class="keyword">protected</span>:
<a name="l00039"></a><a class="code" href="classbTree.html#136e55de9f7c2144aaa86729413bb0c6">00039</a> <a class="code" href="structbNode.html">bNode</a> * <a class="code" href="classbTree.html#136e55de9f7c2144aaa86729413bb0c6">root</a>;
<a name="l00040"></a><a class="code" href="classbTree.html#42e664483d5d3b81965fa4c8808c0f16">00040</a> <a class="code" href="classUbixFS.html">UbixFS</a> * <a class="code" href="structfs.html">fs</a>;
<a name="l00041"></a><a class="code" href="classbTree.html#8bef0f48cc7ace024ca327ce774185c8">00041</a> <a class="code" href="structbTreeHeader.html">bTreeHeader</a> * <a class="code" href="classbTree.html#8bef0f48cc7ace024ca327ce774185c8">header</a>;
<a name="l00042"></a><a class="code" href="classbTree.html#adb550cc0b77f9f3ed14a5f679dbd954">00042</a> <a class="code" href="structfileDescriptor.html">fileDescriptor</a> * <a class="code" href="classbTree.html#adb550cc0b77f9f3ed14a5f679dbd954">fd</a>;
<a name="l00043"></a><a class="code" href="classbTree.html#28b1926c127d65af730a534a3ca1a7a5">00043</a> <a class="code" href="include_2ubixos_2types_8h.html#5847ea0262a5aa61eee48cbe95544a78">uInt32</a> <a class="code" href="classbTree.html#28b1926c127d65af730a534a3ca1a7a5">tag</a>;
<a name="l00044"></a>00044 <a class="code" href="structubixfsInode.html">ubixfsInode</a> * <a class="code" href="classbTree.html#dddfb323e06a20e5f57896ad6de6430c">treeSearch</a>(<a class="code" href="structbNode.html">bNode</a> *, <span class="keyword">const</span> <span class="keywordtype">char</span> *);
<a name="l00045"></a>00045 <a class="code" href="structubixfsInode.html">ubixfsInode</a> * <a class="code" href="classbTree.html#033edc7c078c7c90f59610ca8946cebe">inodeSearch</a>(<a class="code" href="structubixfsInode.html">ubixfsInode</a> *, <span class="keyword">const</span> <span class="keywordtype">char</span> *);
<a name="l00046"></a>00046 <span class="keywordtype">void</span> <a class="code" href="classbTree.html#51f94e9190f4c21c66367932b22c10aa">splitNode</a>(<a class="code" href="structbNode.html">bNode</a> *);
<a name="l00047"></a>00047 <a class="code" href="structbNode.html">bNode</a> * <a class="code" href="classbTree.html#ee13657d4417aaf2f772663fbbb3687c">allocEmptyNode</a>(<span class="keywordtype">void</span>);
<a name="l00048"></a>00048 <span class="keywordtype">void</span> <a class="code" href="classbTree.html#8f732470e0bc0b0a5a0810c944c51122">insertNode</a>(<a class="code" href="structbNode.html">bNode</a> *, <span class="keyword">const</span> <span class="keywordtype">char</span> *, <a class="code" href="structbNode.html">bNode</a> *);
<a name="l00049"></a>00049 <a class="code" href="structbNode.html">bNode</a> * <a class="code" href="classbTree.html#757a2be70e2309d4bf0be2eff562a8b9">findLeafNode</a>(<a class="code" href="structbNode.html">bNode</a> *, <span class="keyword">const</span> <span class="keywordtype">char</span> *);
<a name="l00050"></a>00050 <span class="keywordtype">void</span> <a class="code" href="classbTree.html#1c516c3e73c273ded54df841e8271954">Print</a>(<a class="code" href="structbNode.html">bNode</a> *);
<a name="l00051"></a>00051 <span class="keywordtype">void</span> <a class="code" href="classbTree.html#9fec062b5b9f54ab6147cba2e92763c2">saveNode</a>(FILE *, <a class="code" href="structbNode.html">bNode</a> *, <span class="keywordtype">void</span> *);
<a name="l00052"></a>00052 <span class="keyword">public</span>:
<a name="l00053"></a>00053 <a class="code" href="classbTree.html#f6969b750661bc6859f3a1a5b60cca90">bTree</a>(<span class="keyword">const</span> <span class="keywordtype">char</span> *, <a class="code" href="structubixfsInode.html">ubixfsInode</a> *);
<a name="l00054"></a>00054 <a class="code" href="classbTree.html#f6969b750661bc6859f3a1a5b60cca90">bTree</a>(<a class="code" href="classUbixFS.html">UbixFS</a> *, <a class="code" href="structfileDescriptor.html">fileDescriptor</a> *);
<a name="l00055"></a>00055 <a class="code" href="structubixfsInode.html">ubixfsInode</a> * <a class="code" href="classbTree.html#3e852a247447d5611a7e5cd7de53ecf9">Find</a>(<span class="keyword">const</span> <span class="keywordtype">char</span> *);
<a name="l00056"></a>00056 <a class="code" href="structubixfsInode.html">ubixfsInode</a> * <a class="code" href="classbTree.html#8d04e7d1bb555d157f32673af0977244">GetFirstNode</a>(<span class="keywordtype">void</span>);
<a name="l00057"></a>00057 <a class="code" href="structubixfsInode.html">ubixfsInode</a> * <a class="code" href="classbTree.html#8d04e7d1bb555d157f32673af0977244">GetFirstNode</a>(<a class="code" href="structbNode.html">bNode</a> *);
<a name="l00058"></a>00058 <span class="keywordtype">bool</span> <a class="code" href="classbTree.html#ca63b57c49aed1565117d6de1d47036e">Delete</a>(<span class="keyword">const</span> <span class="keywordtype">char</span> *);
<a name="l00059"></a>00059 <span class="keywordtype">void</span> <a class="code" href="classbTree.html#e095e3365ec7b4656efcf0889ff43a6c">Info</a>(<span class="keywordtype">void</span>);
<a name="l00060"></a>00060 <span class="keywordtype">void</span> <a class="code" href="classbTree.html#e095e3365ec7b4656efcf0889ff43a6c">Info</a>(<span class="keyword">const</span> <a class="code" href="structbNode.html">bNode</a> *);
<a name="l00061"></a>00061 <span class="keywordtype">bool</span> <a class="code" href="classbTree.html#fbaa745c86c8bfaa77d2196a0c1eb85b">Insert</a>(<span class="keyword">const</span> <span class="keywordtype">char</span> *, <a class="code" href="structubixfsInode.html">ubixfsInode</a> *);
<a name="l00062"></a>00062 <span class="keywordtype">bool</span> <a class="code" href="classbTree.html#58a7211e172868c67ee7ed12e8015c4f">Save</a>(<span class="keyword">const</span> <span class="keywordtype">char</span> *);
<a name="l00063"></a>00063 <span class="keywordtype">bool</span> <a class="code" href="classbTree.html#80f234b61d3d99a44dba29f0754607dc">Load</a>(<span class="keyword">const</span> <span class="keywordtype">char</span> *);
<a name="l00064"></a>00064 <span class="keywordtype">void</span> <a class="code" href="classbTree.html#1c516c3e73c273ded54df841e8271954">Print</a>(<span class="keywordtype">void</span>);
<a name="l00065"></a>00065 <span class="keywordtype">void</span> <a class="code" href="classbTree.html#167dc542695e9e90d741dedb07a8fee4">PrintWholeTree</a>(<span class="keywordtype">void</span>);
<a name="l00066"></a>00066 <span class="keywordtype">bool</span> <a class="code" href="classbTree.html#73a18a32abfb03fc233f35a237ad094f">Verify</a>(<span class="keywordtype">void</span>);
<a name="l00067"></a>00067 <a class="code" href="classbTree.html#2daef081948bc350347520ca9781cc1b">~bTree</a>(<span class="keywordtype">void</span>);
<a name="l00068"></a><a class="code" href="classbTree.html#1760ad02c8a49e1b7df47d6f0d2a8234">00068</a> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="classUbixFS.html">UbixFS</a>;
<a name="l00069"></a>00069 }; <span class="comment">// bTree</span>
<a name="l00070"></a>00070 <span class="preprocessor">#endif // !BTREE_H</span>
</pre></div><hr size="1"><address style="align: right;"><small>Generated on Tue Dec 5 23:34:58 2006 for UbixOS V2 by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.4.7 </small></address>
</body>
</html>
