Rev 74 | Rev 87 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
52 | jermar | 1 | <?xml version="1.0" encoding="UTF-8"?> |
59 | jermar | 2 | <chapter id="ds"> |
3 | <?dbhtml filename="ds.html"?> |
||
52 | jermar | 4 | |
59 | jermar | 5 | <title>Data structures</title> |
52 | jermar | 6 | |
59 | jermar | 7 | <para>There is lots of data that either flows through various HelenOS |
8 | subsystems or is stored directly by them. Each subsystem uses its own data |
||
9 | structures to represent the data. These data structures need to be kept |
||
10 | somewhere. In order to work efficiently, HelenOS, and especially its kernel, |
||
11 | deploys several house keeping data types that are designed to faciliate |
||
12 | managing other data structures. Most of them serve like generic |
||
13 | containers.</para> |
||
52 | jermar | 14 | |
59 | jermar | 15 | <section> |
16 | <title>Lists</title> |
||
52 | jermar | 17 | |
73 | bondari | 18 | <indexterm> |
19 | <primary>linked list</primary> |
||
20 | </indexterm> |
||
21 | |||
59 | jermar | 22 | <para>HelenOS uses doubly-circularly-linked lists to bind related data |
23 | together. Lists are composed of an independent sentinel node called head |
||
24 | and links that are always part of the object that is to be put into the |
||
25 | list. Adding items to a list thus doesn't require any further memory |
||
26 | allocations. Head and each link then contains forward and backward |
||
27 | pointer. An empty list is composed of a sole head whose both pointers |
||
28 | reference the head itself. The expense of two times bigger memory |
||
29 | consumption as compared to memory consumption of singly linked lists is |
||
30 | justified by constant insertion and removal times at random positions |
||
31 | within the list.</para> |
||
52 | jermar | 32 | |
59 | jermar | 33 | <para>Lists are frequently used to implement FIFO behaviour (e.g. |
34 | scheduler run queues or synchronization wait queues). Contrary to the FIFO |
||
35 | type, which is also supported by HelenOS, they don't take up any unused |
||
36 | space and are more general. On the other hand, they are slower than |
||
37 | in-array FIFOs and can be hardly used to implement buffers.</para> |
||
38 | </section> |
||
39 | |||
40 | <section> |
||
41 | <title>FIFO queues</title> |
||
42 | |||
73 | bondari | 43 | <indexterm> |
44 | <primary>FIFO queue</primary> |
||
45 | </indexterm> |
||
46 | |||
59 | jermar | 47 | <para>FIFO queues are implemented as either statically or dynamically |
48 | allocated arrays<footnote> |
||
49 | <para>Depending on the array size.</para> |
||
50 | </footnote> of some generic type with two indices. The first index |
||
51 | points to the head of the FIFO queue and the other points to the tail |
||
52 | thereof. There can be as many items in the FIFO as is the number of |
||
53 | elements in the array and no more. The indices are taken modulo size of |
||
54 | the queue because as a consequence of insertions and deletions, the tail |
||
55 | can have numericaly lower index than the head.</para> |
||
56 | |||
57 | <para>FIFO queues are used, for example, in ASID management code to store |
||
58 | inactive ASIDs or in userspace keyboard driver to buffer read |
||
59 | characters.</para> |
||
61 | jermar | 60 | |
62 | jermar | 61 | <figure> |
73 | bondari | 62 | <mediaobject id="fifo" xreflabel=""> |
77 | bondari | 63 | <imageobject role="eps"> |
64 | <imagedata fileref="images.vector/fifo.eps" format="EPS" /> |
||
65 | </imageobject> |
||
66 | |||
73 | bondari | 67 | <imageobject role="html"> |
68 | <imagedata fileref="images/fifo.png" format="PNG" /> |
||
69 | </imageobject> |
||
70 | |||
71 | <imageobject role="fop"> |
||
72 | <imagedata fileref="images.vector/fifo.svg" format="SVG" /> |
||
73 | </imageobject> |
||
74 | </mediaobject> |
||
75 | |||
76 | <title>FIFO queue showing the wrap around the end of the array.</title> |
||
62 | jermar | 77 | </figure> |
59 | jermar | 78 | </section> |
79 | |||
74 | bondari | 80 | <section id="hashtables"> |
59 | jermar | 81 | <title>Hash tables</title> |
82 | |||
73 | bondari | 83 | <indexterm> |
84 | <primary>hash table</primary> |
||
85 | </indexterm> |
||
86 | |||
59 | jermar | 87 | <para>The kernel, as well as userspace, provides hash table data type |
88 | which uses separate chaining. The hash table type is very generic in that |
||
89 | it forces the user to supply methods for computing the hash index, |
||
90 | comparing items against a set of keys and the item removal callback |
||
91 | function. Besides these virtual operations, the hash table is composed of |
||
92 | a dynamically allocated array of list heads that represent each chain, |
||
93 | number of chains and the maximal number of keys.</para> |
||
94 | </section> |
||
95 | |||
96 | <section> |
||
97 | <title>Bitmaps</title> |
||
98 | |||
73 | bondari | 99 | <indexterm> |
100 | <primary>bitmap</primary> |
||
101 | </indexterm> |
||
102 | |||
59 | jermar | 103 | <para>Several bitmap operations such as clearing or setting consecutive |
104 | bit sequences as well as copying portions of one bitmap into another one |
||
105 | are supported.</para> |
||
106 | </section> |
||
107 | |||
108 | <section> |
||
109 | <title>B+trees</title> |
||
110 | |||
73 | bondari | 111 | <indexterm> |
112 | <primary>B-tree</primary> |
||
113 | </indexterm> |
||
114 | |||
59 | jermar | 115 | <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in |
116 | HelenOS implementation, are 3-4-5 balanced trees. They are characteristic |
||
117 | by the fact that values are kept only in the leaf-level nodes and that |
||
118 | these nodes are linked together in a list. This data structure has |
||
119 | logaritmic search, insertion and deletion times and, thanks to the |
||
120 | leaf-level list, provides fantastic means of walking the nodes containing |
||
121 | data. Moreover, B+trees can be used for easy storing, resizing and merging |
||
122 | of disjunctive intervals.</para> |
||
60 | jermar | 123 | |
62 | jermar | 124 | <figure> |
73 | bondari | 125 | <mediaobject id="btree" xreflabel=""> |
77 | bondari | 126 | <imageobject role="eps"> |
127 | <imagedata fileref="images.vector/btree.eps" format="EPS" /> |
||
128 | </imageobject> |
||
129 | |||
73 | bondari | 130 | <imageobject role="html"> |
131 | <imagedata fileref="images/btree.png" format="PNG" /> |
||
132 | </imageobject> |
||
62 | jermar | 133 | |
73 | bondari | 134 | <imageobject role="fop"> |
135 | <imagedata fileref="images.vector/btree.svg" format="SVG" /> |
||
136 | </imageobject> |
||
137 | </mediaobject> |
||
138 | |||
139 | <title>B+tree containing keys ranging from 1 to 12.</title> |
||
62 | jermar | 140 | </figure> |
59 | jermar | 141 | </section> |
142 | </chapter> |