Rev 98 | Rev 105 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 98 | Rev 101 | ||
---|---|---|---|
1 | <?xml version="1.0" encoding="UTF-8"?> |
1 | <?xml version="1.0" encoding="UTF-8"?> |
2 | <chapter id="ds"> |
2 | <chapter id="ds"> |
3 | <?dbhtml filename="ds.html"?> |
3 | <?dbhtml filename="ds.html"?> |
4 | 4 | ||
5 | <title>Data structures</title> |
5 | <title>Data structures</title> |
6 | 6 | ||
7 | <para>There is lots of data that either flows through various HelenOS |
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 |
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 |
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, |
10 | somewhere. In order to work efficiently, HelenOS, and especially its kernel, |
11 | deploys several house keeping data types that are designed to faciliate |
11 | deploys several house keeping data types that are designed to faciliate |
12 | managing other data structures. Most of them serve like generic |
12 | managing other data structures. Most of them serve like generic |
13 | containers.</para> |
13 | containers.</para> |
14 | 14 | ||
15 | <section> |
15 | <section> |
16 | <title>Lists</title> |
16 | <title>Lists</title> |
17 | 17 | ||
18 | <indexterm> |
18 | <indexterm> |
19 | <primary>linked list</primary> |
19 | <primary>linked list</primary> |
20 | </indexterm> |
20 | </indexterm> |
21 | 21 | ||
22 | <para>HelenOS uses doubly-circularly-linked lists to bind related data |
22 | <para>HelenOS uses doubly-circularly-linked lists to bind related data |
23 | together. Lists are composed of an independent sentinel node called head |
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 |
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 |
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 |
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 |
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 |
28 | reference the head itself. The expense of two times bigger memory |
29 | consumption as compared to memory consumption of singly linked lists is |
29 | consumption as compared to memory consumption of singly linked lists is |
30 | justified by constant insertion and removal times at random positions |
30 | justified by constant insertion and removal times at random positions |
31 | within the list.</para> |
31 | within the list.</para> |
32 | 32 | ||
33 | <para>Lists are frequently used to implement FIFO behaviour (e.g. |
33 | <para>Lists are frequently used to implement FIFO behaviour (e.g. |
34 | scheduler run queues or synchronization wait queues). Contrary to the FIFO |
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 |
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 |
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> |
37 | in-array FIFOs and can be hardly used to implement buffers.</para> |
38 | 38 | ||
39 | <figure> |
39 | <figure float="1"> |
40 | <mediaobject id="list" xreflabel=""> |
40 | <mediaobject id="list" xreflabel=""> |
41 | <imageobject role="pdf"> |
41 | <imageobject role="pdf"> |
42 | <imagedata fileref="images.vector/list.pdf" format="PDF" /> |
42 | <imagedata fileref="images.vector/list.pdf" format="PDF" /> |
43 | </imageobject> |
43 | </imageobject> |
44 | 44 | ||
45 | <imageobject role="html"> |
45 | <imageobject role="html"> |
46 | <imagedata fileref="images/list.png" format="PNG" /> |
46 | <imagedata fileref="images/list.png" format="PNG" /> |
47 | </imageobject> |
47 | </imageobject> |
48 | 48 | ||
49 | <imageobject role="fop"> |
49 | <imageobject role="fop"> |
50 | <imagedata fileref="images.vector/list.svg" format="SVG" /> |
50 | <imagedata fileref="images.vector/list.svg" format="SVG" /> |
51 | </imageobject> |
51 | </imageobject> |
52 | </mediaobject> |
52 | </mediaobject> |
53 | 53 | ||
54 | <title>Doubly-circularly-linked list</title> |
54 | <title>Doubly-circularly-linked list</title> |
55 | </figure> |
55 | </figure> |
56 | </section> |
56 | </section> |
57 | 57 | ||
58 | <section> |
58 | <section> |
59 | <title>FIFO queues</title> |
59 | <title>FIFO queues</title> |
60 | 60 | ||
61 | <indexterm> |
61 | <indexterm> |
62 | <primary>FIFO queue</primary> |
62 | <primary>FIFO queue</primary> |
63 | </indexterm> |
63 | </indexterm> |
64 | 64 | ||
65 | <para>FIFO queues are implemented as either statically or dynamically |
65 | <para>FIFO queues are implemented as either statically or dynamically |
66 | allocated arrays<footnote> |
66 | allocated arrays<footnote> |
67 | <para>Depending on the array size.</para> |
67 | <para>Depending on the array size.</para> |
68 | </footnote> of some generic type with two indices. The first index |
68 | </footnote> of some generic type with two indices. The first index |
69 | points to the head of the FIFO queue and the other points to the tail |
69 | points to the head of the FIFO queue and the other points to the tail |
70 | thereof. There can be as many items in the FIFO as is the number of |
70 | thereof. There can be as many items in the FIFO as is the number of |
71 | elements in the array and no more. The indices are taken modulo size of |
71 | elements in the array and no more. The indices are taken modulo size of |
72 | the queue because as a consequence of insertions and deletions, the tail |
72 | the queue because as a consequence of insertions and deletions, the tail |
73 | can have numericaly lower index than the head.</para> |
73 | can have numericaly lower index than the head.</para> |
74 | 74 | ||
75 | <para>FIFO queues are used, for example, in ASID management code to store |
75 | <para>FIFO queues are used, for example, in ASID management code to store |
76 | inactive ASIDs or in userspace keyboard driver to buffer read |
76 | inactive ASIDs or in userspace keyboard driver to buffer read |
77 | characters.</para> |
77 | characters.</para> |
78 | 78 | ||
79 | <figure> |
79 | <figure float="1"> |
80 | <mediaobject id="fifo" xreflabel=""> |
80 | <mediaobject id="fifo" xreflabel=""> |
81 | <imageobject role="pdf"> |
81 | <imageobject role="pdf"> |
82 | <imagedata fileref="images.vector/fifo.pdf" format="PDF" /> |
82 | <imagedata fileref="images.vector/fifo.pdf" format="PDF" /> |
83 | </imageobject> |
83 | </imageobject> |
84 | 84 | ||
85 | <imageobject role="html"> |
85 | <imageobject role="html"> |
86 | <imagedata fileref="images/fifo.png" format="PNG" /> |
86 | <imagedata fileref="images/fifo.png" format="PNG" /> |
87 | </imageobject> |
87 | </imageobject> |
88 | 88 | ||
89 | <imageobject role="fop"> |
89 | <imageobject role="fop"> |
90 | <imagedata fileref="images.vector/fifo.svg" format="SVG" /> |
90 | <imagedata fileref="images.vector/fifo.svg" format="SVG" /> |
91 | </imageobject> |
91 | </imageobject> |
92 | </mediaobject> |
92 | </mediaobject> |
93 | 93 | ||
94 | <title>FIFO queue showing the wrap around the end of the array.</title> |
94 | <title>FIFO queue showing the wrap around the end of the array.</title> |
95 | </figure> |
95 | </figure> |
96 | </section> |
96 | </section> |
97 | 97 | ||
98 | <section id="hashtables"> |
98 | <section id="hashtables"> |
99 | <title>Hash tables</title> |
99 | <title>Hash tables</title> |
100 | 100 | ||
101 | <indexterm> |
101 | <indexterm> |
102 | <primary>hash table</primary> |
102 | <primary>hash table</primary> |
103 | </indexterm> |
103 | </indexterm> |
104 | 104 | ||
105 | <para>The kernel, as well as userspace, provides hash table data type |
105 | <para>The kernel, as well as userspace, provides hash table data type |
106 | which uses separate chaining. The hash table type is very generic in that |
106 | which uses separate chaining. The hash table type is very generic in that |
107 | it forces the user to supply methods for computing the hash index, |
107 | it forces the user to supply methods for computing the hash index, |
108 | comparing items against a set of keys and the item removal callback |
108 | comparing items against a set of keys and the item removal callback |
109 | function. Besides these virtual operations, the hash table is composed of |
109 | function. Besides these virtual operations, the hash table is composed of |
110 | a dynamically allocated array of list heads that represent each chain, |
110 | a dynamically allocated array of list heads that represent each chain, |
111 | number of chains and the maximal number of keys.</para> |
111 | number of chains and the maximal number of keys.</para> |
112 | 112 | ||
113 | <figure> |
113 | <figure float="1"> |
114 | <mediaobject id="hash" xreflabel=""> |
114 | <mediaobject id="hash" xreflabel=""> |
115 | <imageobject role="pdf"> |
115 | <imageobject role="pdf"> |
116 | <imagedata fileref="images.vector/hash.pdf" format="PDF" /> |
116 | <imagedata fileref="images.vector/hash.pdf" format="PDF" /> |
117 | </imageobject> |
117 | </imageobject> |
118 | 118 | ||
119 | <imageobject role="html"> |
119 | <imageobject role="html"> |
120 | <imagedata fileref="images/hash.png" format="PNG" /> |
120 | <imagedata fileref="images/hash.png" format="PNG" /> |
121 | </imageobject> |
121 | </imageobject> |
122 | 122 | ||
123 | <imageobject role="fop"> |
123 | <imageobject role="fop"> |
124 | <imagedata fileref="images.vector/hash.svg" format="SVG" /> |
124 | <imagedata fileref="images.vector/hash.svg" format="SVG" /> |
125 | </imageobject> |
125 | </imageobject> |
126 | </mediaobject> |
126 | </mediaobject> |
127 | 127 | ||
128 | <title>Generic hash table.</title> |
128 | <title>Generic hash table.</title> |
129 | </figure> |
129 | </figure> |
130 | 130 | ||
131 | </section> |
131 | </section> |
132 | 132 | ||
133 | <section> |
133 | <section> |
134 | <title>Bitmaps</title> |
134 | <title>Bitmaps</title> |
135 | 135 | ||
136 | <indexterm> |
136 | <indexterm> |
137 | <primary>bitmap</primary> |
137 | <primary>bitmap</primary> |
138 | </indexterm> |
138 | </indexterm> |
139 | 139 | ||
140 | <para>Several bitmap operations such as clearing or setting consecutive |
140 | <para>Several bitmap operations such as clearing or setting consecutive |
141 | bit sequences as well as copying portions of one bitmap into another one |
141 | bit sequences as well as copying portions of one bitmap into another one |
142 | are supported.</para> |
142 | are supported.</para> |
143 | </section> |
143 | </section> |
144 | 144 | ||
145 | <section> |
145 | <section> |
146 | <title>B+trees</title> |
146 | <title>B+trees</title> |
147 | 147 | ||
148 | <indexterm> |
148 | <indexterm> |
149 | <primary>B-trees</primary> |
149 | <primary>B-trees</primary> |
150 | <secondary> - B+tree</secondary> |
150 | <secondary> - B+tree</secondary> |
151 | </indexterm> |
151 | </indexterm> |
152 | 152 | ||
153 | <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in |
153 | <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in |
154 | HelenOS implementation, are 3-4-5 balanced trees. They are characteristic |
154 | HelenOS implementation, are 3-4-5 balanced trees. They are characteristic |
155 | by the fact that values are kept only in the leaf-level nodes and that |
155 | by the fact that values are kept only in the leaf-level nodes and that |
156 | these nodes are linked together in a list. This data structure has |
156 | these nodes are linked together in a list. This data structure has |
157 | logaritmic search, insertion and deletion times and, thanks to the |
157 | logaritmic search, insertion and deletion times and, thanks to the |
158 | leaf-level list, provides fantastic means of walking the nodes containing |
158 | leaf-level list, provides fantastic means of walking the nodes containing |
159 | data. Moreover, B+trees can be used for easy storing, resizing and merging |
159 | data. Moreover, B+trees can be used for easy storing, resizing and merging |
160 | of disjunctive intervals.</para> |
160 | of disjunctive intervals.</para> |
161 | 161 | ||
162 | <figure> |
162 | <figure float="1"> |
163 | <mediaobject id="btree" xreflabel=""> |
163 | <mediaobject id="btree" xreflabel=""> |
164 | <imageobject role="pdf"> |
164 | <imageobject role="pdf"> |
165 | <imagedata fileref="images.vector/btree.pdf" format="PDF" /> |
165 | <imagedata fileref="images.vector/btree.pdf" format="PDF" /> |
166 | </imageobject> |
166 | </imageobject> |
167 | 167 | ||
168 | <imageobject role="html"> |
168 | <imageobject role="html"> |
169 | <imagedata fileref="images/btree.png" format="PNG" /> |
169 | <imagedata fileref="images/btree.png" format="PNG" /> |
170 | </imageobject> |
170 | </imageobject> |
171 | 171 | ||
172 | <imageobject role="fop"> |
172 | <imageobject role="fop"> |
173 | <imagedata fileref="images.vector/btree.svg" format="SVG" /> |
173 | <imagedata fileref="images.vector/btree.svg" format="SVG" /> |
174 | </imageobject> |
174 | </imageobject> |
175 | </mediaobject> |
175 | </mediaobject> |
176 | 176 | ||
177 | <title>B+tree containing keys ranging from 1 to 12.</title> |
177 | <title>B+tree containing keys ranging from 1 to 12.</title> |
178 | </figure> |
178 | </figure> |
179 | </section> |
179 | </section> |
180 | </chapter> |
180 | </chapter> |