0,0 → 1,77 |
<?xml version="1.0" encoding="UTF-8"?> |
|
<chapter id="ds"><?dbhtml filename="ds.html"?> |
<title>Data structures</title> |
|
<para> |
There is lots 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 faciliate managing other data structures. They serve like generic |
containers. |
</para> |
|
<section> |
<title>Lists</title> |
<para> |
HelenOS uses circular doubly linked lists to bind related data |
together. Lists are composed of an independent 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> |
|
</section> |
|
<section> |
<title>FIFO queues</title> |
<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> |
</section> |
|
<section> |
<title>Hash tables</title> |
<para> |
The kernel, as well as userspace, makes use of the hash table implementation with |
separate chaining. The implementation is very generic in that it forces the user |
to supply methods for computing the hash index, comparing items with several 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> |
</section> |
|
<section> |
<title>B+trees</title> |
<para> |
|
</para> |
</section> |
|
</chapter> |