| 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> |