1,82 → 1,86 |
<?xml version="1.0" encoding="UTF-8"?> |
<chapter id="ds"> |
<?dbhtml filename="ds.html"?> |
|
<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> |
<title>Data structures</title> |
|
<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> |
<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. Most of them serve like generic |
containers.</para> |
|
<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 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> |
</section> |
<section> |
<title>Lists</title> |
|
<section> |
<title>B+trees</title> |
<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> |
</section> |
<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> |
|
</chapter> |
<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, 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> |
</section> |
|
<section> |
<title>Bitmaps</title> |
|
<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> |
|
<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> |
</section> |
</chapter> |