<?xml version="1.0" encoding="UTF-8"?>
<chapter id="ds">
<?dbhtml filename="ds.html"?>
<title>Data Structures</title>
<para>There is a lot of data that either flows through various HelenOS
subsystems or is stored directly by them. Each subsystem uses its own data
structures to represent the data. These data structures need to be kept
somewhere. In order to work efficiently, HelenOS, and especially its kernel,
deploys several house keeping data types that are designed to facilitate
managing other data structures. Most of them serve like generic
containers.</para>
<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
list. Adding items to a list thus doesn't require any further memory
allocations. Head and each link then contains forward and backward
pointer. An empty list is composed of a sole head whose both pointers
reference the head itself. The expense of two times bigger memory
consumption as compared to memory consumption of singly linked lists is
justified by constant insertion and removal times at random positions
within the list.</para>
<para>Lists are frequently used to implement FIFO behaviour (e.g.
scheduler run queues or synchronization wait queues). Contrary to the FIFO
type, which is also supported by HelenOS, they don't take up any unused
space and are more general. On the other hand, they are slower than
in-array FIFOs and can be hardly used to implement buffers.</para>
<figure float="1">
<mediaobject id="list" xreflabel="">
<imageobject role="pdf">
<imagedata fileref="images/list.pdf" format="PDF" />
</imageobject>
<imageobject role="html">
<imagedata fileref="images/list.png" format="PNG" />
</imageobject>
<imageobject role="fop">
<imagedata fileref="images/list.svg" format="SVG" />
</imageobject>
</mediaobject>
<title>Doubly-circularly-linked list</title>
</figure>
</section>
<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>
</footnote> of some generic type with two indices. The first index
points to the head of the FIFO queue and the other points to the tail
thereof. There can be as many items in the FIFO as is the number of
elements in the array and no more. The indices are taken modulo size of
the queue because as a consequence of insertions and deletions, the tail
can have numericaly lower index than the head.</para>
<para>FIFO queues are used, for example, in ASID management code to store
inactive ASIDs or in userspace keyboard driver to buffer read
characters.</para>
<figure float="1">
<mediaobject id="fifo" xreflabel="">
<imageobject role="pdf">
<imagedata fileref="images/fifo.pdf" format="PDF" />
</imageobject>
<imageobject role="html">
<imagedata fileref="images/fifo.png" format="PNG" />
</imageobject>
<imageobject role="fop">
<imagedata fileref="images/fifo.svg" format="SVG" />
</imageobject>
</mediaobject>
<title>FIFO queue showing the wrap around the end of the array.</title>
</figure>
</section>
<section id="hashtables">
<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,
comparing items against a set of keys and the item removal callback
function. Besides these virtual operations, the hash table is composed of
a dynamically allocated array of list heads that represent each chain,
number of chains and the maximal number of keys.</para>
<figure float="1">
<mediaobject id="hash" xreflabel="">
<imageobject role="pdf">
<imagedata fileref="images/hash.pdf" format="PDF" />
</imageobject>
<imageobject role="html">
<imagedata fileref="images/hash.png" format="PNG" />
</imageobject>
<imageobject role="fop">
<imagedata fileref="images/hash.svg" format="SVG" />
</imageobject>
</mediaobject>
<title>Generic hash table.</title>
</figure>
</section>
<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>
</section>
<section>
<title>B+trees</title>
<indexterm>
<primary>B-trees</primary>
<secondary>- B+tree</secondary>
</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
these nodes are linked together in a list. This data structure has
logaritmic search, insertion and deletion times and, thanks to the
leaf-level list, provides fantastic means of walking the nodes containing
data. Moreover, B+trees can be used for easy storing, resizing and merging
of disjunctive intervals.</para>
<figure float="1">
<mediaobject id="btree" xreflabel="">
<imageobject role="pdf">
<imagedata fileref="images/btree.pdf" format="PDF" />
</imageobject>
<imageobject role="html">
<imagedata fileref="images/btree.png" format="PNG" />
</imageobject>
<imageobject role="fop">
<imagedata fileref="images/btree.svg" format="SVG" />
</imageobject>
</mediaobject>
<title>B+tree containing keys ranging from 1 to 12.</title>
</figure>
</section>
</chapter>