15,10 → 15,6 |
<section> |
<title>Lists</title> |
|
<indexterm> |
<primary>linked list</primary> |
</indexterm> |
|
<para>HelenOS uses doubly-circularly-linked lists to bind related data |
together. Lists are composed of an independent sentinel node called head |
and links that are always part of the object that is to be put into the |
40,10 → 36,6 |
<section> |
<title>FIFO queues</title> |
|
<indexterm> |
<primary>FIFO queue</primary> |
</indexterm> |
|
<para>FIFO queues are implemented as either statically or dynamically |
allocated arrays<footnote> |
<para>Depending on the array size.</para> |
59,27 → 51,24 |
characters.</para> |
|
<figure> |
<mediaobject id="fifo" xreflabel=""> |
<imageobject role="html"> |
<imagedata fileref="images/fifo.png" format="PNG" /> |
</imageobject> |
<mediaobject id="fifo" xreflabel=""> |
<imageobject role="html"> |
<imagedata fileref="images/fifo.png" format="PNG" /> |
</imageobject> |
|
<imageobject role="fop"> |
<imagedata fileref="images.vector/fifo.svg" format="SVG" /> |
</imageobject> |
|
</mediaobject> |
<title>FIFO queue showing the wrap around the end of the array.</title> |
</figure> |
|
<imageobject role="fop"> |
<imagedata fileref="images.vector/fifo.svg" format="SVG" /> |
</imageobject> |
</mediaobject> |
|
<title>FIFO queue showing the wrap around the end of the array.</title> |
</figure> |
</section> |
|
<section> |
<title>Hash tables</title> |
|
<indexterm> |
<primary>hash table</primary> |
</indexterm> |
|
<para>The kernel, as well as userspace, provides hash table data type |
which uses separate chaining. The hash table type is very generic in that |
it forces the user to supply methods for computing the hash index, |
92,10 → 81,6 |
<section> |
<title>Bitmaps</title> |
|
<indexterm> |
<primary>bitmap</primary> |
</indexterm> |
|
<para>Several bitmap operations such as clearing or setting consecutive |
bit sequences as well as copying portions of one bitmap into another one |
are supported.</para> |
104,10 → 89,6 |
<section> |
<title>B+trees</title> |
|
<indexterm> |
<primary>B-tree</primary> |
</indexterm> |
|
<para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in |
HelenOS implementation, are 3-4-5 balanced trees. They are characteristic |
by the fact that values are kept only in the leaf-level nodes and that |
118,17 → 99,19 |
of disjunctive intervals.</para> |
|
<figure> |
<mediaobject id="btree" xreflabel=""> |
<imageobject role="html"> |
<imagedata fileref="images/btree.png" format="PNG" /> |
</imageobject> |
<mediaobject id="btree" xreflabel=""> |
<imageobject role="html"> |
<imagedata fileref="images/btree.png" format="PNG" /> |
</imageobject> |
|
<imageobject role="fop"> |
<imagedata fileref="images.vector/btree.svg" format="SVG" /> |
</imageobject> |
|
|
<imageobject role="fop"> |
<imagedata fileref="images.vector/btree.svg" format="SVG" /> |
</imageobject> |
</mediaobject> |
</mediaobject> |
<title>B+tree containing keys ranging from 1 to 12.</title> |
</figure> |
|
<title>B+tree containing keys ranging from 1 to 12.</title> |
</figure> |
</section> |
</chapter> |