Rev 60 | Rev 62 | Go to most recent revision | Only display areas with differences | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 60 | Rev 61 | ||
---|---|---|---|
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 | <para>HelenOS uses doubly-circularly-linked lists to bind related data |
18 | <para>HelenOS uses doubly-circularly-linked lists to bind related data |
19 | together. Lists are composed of an independent sentinel node called head |
19 | together. Lists are composed of an independent sentinel node called head |
20 | and links that are always part of the object that is to be put into the |
20 | and links that are always part of the object that is to be put into the |
21 | list. Adding items to a list thus doesn't require any further memory |
21 | list. Adding items to a list thus doesn't require any further memory |
22 | allocations. Head and each link then contains forward and backward |
22 | allocations. Head and each link then contains forward and backward |
23 | pointer. An empty list is composed of a sole head whose both pointers |
23 | pointer. An empty list is composed of a sole head whose both pointers |
24 | reference the head itself. The expense of two times bigger memory |
24 | reference the head itself. The expense of two times bigger memory |
25 | consumption as compared to memory consumption of singly linked lists is |
25 | consumption as compared to memory consumption of singly linked lists is |
26 | justified by constant insertion and removal times at random positions |
26 | justified by constant insertion and removal times at random positions |
27 | within the list.</para> |
27 | within the list.</para> |
28 | 28 | ||
29 | <para>Lists are frequently used to implement FIFO behaviour (e.g. |
29 | <para>Lists are frequently used to implement FIFO behaviour (e.g. |
30 | scheduler run queues or synchronization wait queues). Contrary to the FIFO |
30 | scheduler run queues or synchronization wait queues). Contrary to the FIFO |
31 | type, which is also supported by HelenOS, they don't take up any unused |
31 | type, which is also supported by HelenOS, they don't take up any unused |
32 | space and are more general. On the other hand, they are slower than |
32 | space and are more general. On the other hand, they are slower than |
33 | in-array FIFOs and can be hardly used to implement buffers.</para> |
33 | in-array FIFOs and can be hardly used to implement buffers.</para> |
34 | </section> |
34 | </section> |
35 | 35 | ||
36 | <section> |
36 | <section> |
37 | <title>FIFO queues</title> |
37 | <title>FIFO queues</title> |
38 | 38 | ||
39 | <para>FIFO queues are implemented as either statically or dynamically |
39 | <para>FIFO queues are implemented as either statically or dynamically |
40 | allocated arrays<footnote> |
40 | allocated arrays<footnote> |
41 | <para>Depending on the array size.</para> |
41 | <para>Depending on the array size.</para> |
42 | </footnote> of some generic type with two indices. The first index |
42 | </footnote> of some generic type with two indices. The first index |
43 | points to the head of the FIFO queue and the other points to the tail |
43 | points to the head of the FIFO queue and the other points to the tail |
44 | thereof. There can be as many items in the FIFO as is the number of |
44 | thereof. There can be as many items in the FIFO as is the number of |
45 | elements in the array and no more. The indices are taken modulo size of |
45 | elements in the array and no more. The indices are taken modulo size of |
46 | the queue because as a consequence of insertions and deletions, the tail |
46 | the queue because as a consequence of insertions and deletions, the tail |
47 | can have numericaly lower index than the head.</para> |
47 | can have numericaly lower index than the head.</para> |
48 | 48 | ||
49 | <para>FIFO queues are used, for example, in ASID management code to store |
49 | <para>FIFO queues are used, for example, in ASID management code to store |
50 | inactive ASIDs or in userspace keyboard driver to buffer read |
50 | inactive ASIDs or in userspace keyboard driver to buffer read |
51 | characters.</para> |
51 | characters.</para> |
- | 52 | ||
- | 53 | <para> |
|
- | 54 | <mediaobject id="fifo" xreflabel=""> |
|
- | 55 | <imageobject role="html"> |
|
- | 56 | <imagedata fileref="images/fifo.png" format="PNG" /> |
|
- | 57 | </imageobject> |
|
- | 58 | ||
- | 59 | <imageobject role="fop"> |
|
- | 60 | <imagedata fileref="images.vector/fifo.svg" format="SVG" /> |
|
- | 61 | </imageobject> |
|
- | 62 | ||
- | 63 | <caption>FIFO queue showing the wrap around the end of the array.</caption> |
|
- | 64 | </mediaobject> |
|
- | 65 | </para> |
|
- | 66 | ||
52 | </section> |
67 | </section> |
53 | 68 | ||
54 | <section> |
69 | <section> |
55 | <title>Hash tables</title> |
70 | <title>Hash tables</title> |
56 | 71 | ||
57 | <para>The kernel, as well as userspace, provides hash table data type |
72 | <para>The kernel, as well as userspace, provides hash table data type |
58 | which uses separate chaining. The hash table type is very generic in that |
73 | which uses separate chaining. The hash table type is very generic in that |
59 | it forces the user to supply methods for computing the hash index, |
74 | it forces the user to supply methods for computing the hash index, |
60 | comparing items against a set of keys and the item removal callback |
75 | comparing items against a set of keys and the item removal callback |
61 | function. Besides these virtual operations, the hash table is composed of |
76 | function. Besides these virtual operations, the hash table is composed of |
62 | a dynamically allocated array of list heads that represent each chain, |
77 | a dynamically allocated array of list heads that represent each chain, |
63 | number of chains and the maximal number of keys.</para> |
78 | number of chains and the maximal number of keys.</para> |
64 | </section> |
79 | </section> |
65 | 80 | ||
66 | <section> |
81 | <section> |
67 | <title>Bitmaps</title> |
82 | <title>Bitmaps</title> |
68 | 83 | ||
69 | <para>Several bitmap operations such as clearing or setting consecutive |
84 | <para>Several bitmap operations such as clearing or setting consecutive |
70 | bit sequences as well as copying portions of one bitmap into another one |
85 | bit sequences as well as copying portions of one bitmap into another one |
71 | are supported.</para> |
86 | are supported.</para> |
72 | </section> |
87 | </section> |
73 | 88 | ||
74 | <section> |
89 | <section> |
75 | <title>B+trees</title> |
90 | <title>B+trees</title> |
76 | 91 | ||
77 | <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in |
92 | <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in |
78 | HelenOS implementation, are 3-4-5 balanced trees. They are characteristic |
93 | HelenOS implementation, are 3-4-5 balanced trees. They are characteristic |
79 | by the fact that values are kept only in the leaf-level nodes and that |
94 | by the fact that values are kept only in the leaf-level nodes and that |
80 | these nodes are linked together in a list. This data structure has |
95 | these nodes are linked together in a list. This data structure has |
81 | logaritmic search, insertion and deletion times and, thanks to the |
96 | logaritmic search, insertion and deletion times and, thanks to the |
82 | leaf-level list, provides fantastic means of walking the nodes containing |
97 | leaf-level list, provides fantastic means of walking the nodes containing |
83 | data. Moreover, B+trees can be used for easy storing, resizing and merging |
98 | data. Moreover, B+trees can be used for easy storing, resizing and merging |
84 | of disjunctive intervals.</para> |
99 | of disjunctive intervals.</para> |
85 | 100 | ||
86 | <para> |
101 | <para> |
87 | <mediaobject id="btree" xreflabel=""> |
102 | <mediaobject id="btree" xreflabel=""> |
88 | <imageobject role="html"> |
103 | <imageobject role="html"> |
89 | <imagedata fileref="images/btree.png" format="PNG" /> |
104 | <imagedata fileref="images/btree.png" format="PNG" /> |
90 | </imageobject> |
105 | </imageobject> |
91 | 106 | ||
92 | <imageobject role="fop"> |
107 | <imageobject role="fop"> |
93 | <imagedata fileref="images.vector/btree.svg" format="SVG" /> |
108 | <imagedata fileref="images.vector/btree.svg" format="SVG" /> |
94 | </imageobject> |
109 | </imageobject> |
95 | 110 | ||
96 | <caption>B+tree</caption> |
111 | <caption>B+tree containing keys ranging from 1 to 12.</caption> |
97 | </mediaobject> |
112 | </mediaobject> |
98 | </para> |
113 | </para> |
99 | 114 | ||
100 | </section> |
115 | </section> |
101 | </chapter> |
116 | </chapter> |