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