Rev 62 | Rev 74 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 62 | Rev 73 | ||
---|---|---|---|
Line 13... | Line 13... | ||
13 | containers.</para> |
13 | containers.</para> |
14 | 14 | ||
15 | <section> |
15 | <section> |
16 | <title>Lists</title> |
16 | <title>Lists</title> |
17 | 17 | ||
- | 18 | <indexterm> |
|
- | 19 | <primary>linked list</primary> |
|
- | 20 | </indexterm> |
|
- | 21 | ||
18 | <para>HelenOS uses doubly-circularly-linked lists to bind related data |
22 | <para>HelenOS uses doubly-circularly-linked lists to bind related data |
19 | together. Lists are composed of an independent sentinel node called head |
23 | 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 |
24 | 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 |
25 | list. Adding items to a list thus doesn't require any further memory |
22 | allocations. Head and each link then contains forward and backward |
26 | allocations. Head and each link then contains forward and backward |
Line 34... | Line 38... | ||
34 | </section> |
38 | </section> |
35 | 39 | ||
36 | <section> |
40 | <section> |
37 | <title>FIFO queues</title> |
41 | <title>FIFO queues</title> |
38 | 42 | ||
- | 43 | <indexterm> |
|
- | 44 | <primary>FIFO queue</primary> |
|
- | 45 | </indexterm> |
|
- | 46 | ||
39 | <para>FIFO queues are implemented as either statically or dynamically |
47 | <para>FIFO queues are implemented as either statically or dynamically |
40 | allocated arrays<footnote> |
48 | allocated arrays<footnote> |
41 | <para>Depending on the array size.</para> |
49 | <para>Depending on the array size.</para> |
42 | </footnote> of some generic type with two indices. The first index |
50 | </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 |
51 | points to the head of the FIFO queue and the other points to the tail |
Line 49... | Line 57... | ||
49 | <para>FIFO queues are used, for example, in ASID management code to store |
57 | <para>FIFO queues are used, for example, in ASID management code to store |
50 | inactive ASIDs or in userspace keyboard driver to buffer read |
58 | inactive ASIDs or in userspace keyboard driver to buffer read |
51 | characters.</para> |
59 | characters.</para> |
52 | 60 | ||
53 | <figure> |
61 | <figure> |
54 | <mediaobject id="fifo" xreflabel=""> |
62 | <mediaobject id="fifo" xreflabel=""> |
55 | <imageobject role="html"> |
63 | <imageobject role="html"> |
56 | <imagedata fileref="images/fifo.png" format="PNG" /> |
64 | <imagedata fileref="images/fifo.png" format="PNG" /> |
57 | </imageobject> |
65 | </imageobject> |
58 | 66 | ||
59 | <imageobject role="fop"> |
67 | <imageobject role="fop"> |
60 | <imagedata fileref="images.vector/fifo.svg" format="SVG" /> |
68 | <imagedata fileref="images.vector/fifo.svg" format="SVG" /> |
61 | </imageobject> |
69 | </imageobject> |
62 | - | ||
63 | </mediaobject> |
70 | </mediaobject> |
64 | <title>FIFO queue showing the wrap around the end of the array.</title> |
- | |
65 | </figure> |
- | |
66 | 71 | ||
- | 72 | <title>FIFO queue showing the wrap around the end of the array.</title> |
|
- | 73 | </figure> |
|
67 | </section> |
74 | </section> |
68 | 75 | ||
69 | <section> |
76 | <section> |
70 | <title>Hash tables</title> |
77 | <title>Hash tables</title> |
71 | 78 | ||
- | 79 | <indexterm> |
|
- | 80 | <primary>hash table</primary> |
|
- | 81 | </indexterm> |
|
- | 82 | ||
72 | <para>The kernel, as well as userspace, provides hash table data type |
83 | <para>The kernel, as well as userspace, provides hash table data type |
73 | which uses separate chaining. The hash table type is very generic in that |
84 | which uses separate chaining. The hash table type is very generic in that |
74 | it forces the user to supply methods for computing the hash index, |
85 | it forces the user to supply methods for computing the hash index, |
75 | comparing items against a set of keys and the item removal callback |
86 | comparing items against a set of keys and the item removal callback |
76 | function. Besides these virtual operations, the hash table is composed of |
87 | function. Besides these virtual operations, the hash table is composed of |
Line 79... | Line 90... | ||
79 | </section> |
90 | </section> |
80 | 91 | ||
81 | <section> |
92 | <section> |
82 | <title>Bitmaps</title> |
93 | <title>Bitmaps</title> |
83 | 94 | ||
- | 95 | <indexterm> |
|
- | 96 | <primary>bitmap</primary> |
|
- | 97 | </indexterm> |
|
- | 98 | ||
84 | <para>Several bitmap operations such as clearing or setting consecutive |
99 | <para>Several bitmap operations such as clearing or setting consecutive |
85 | bit sequences as well as copying portions of one bitmap into another one |
100 | bit sequences as well as copying portions of one bitmap into another one |
86 | are supported.</para> |
101 | are supported.</para> |
87 | </section> |
102 | </section> |
88 | 103 | ||
89 | <section> |
104 | <section> |
90 | <title>B+trees</title> |
105 | <title>B+trees</title> |
91 | 106 | ||
- | 107 | <indexterm> |
|
- | 108 | <primary>B-tree</primary> |
|
- | 109 | </indexterm> |
|
- | 110 | ||
92 | <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in |
111 | <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in |
93 | HelenOS implementation, are 3-4-5 balanced trees. They are characteristic |
112 | HelenOS implementation, are 3-4-5 balanced trees. They are characteristic |
94 | by the fact that values are kept only in the leaf-level nodes and that |
113 | by the fact that values are kept only in the leaf-level nodes and that |
95 | these nodes are linked together in a list. This data structure has |
114 | these nodes are linked together in a list. This data structure has |
96 | logaritmic search, insertion and deletion times and, thanks to the |
115 | logaritmic search, insertion and deletion times and, thanks to the |
97 | leaf-level list, provides fantastic means of walking the nodes containing |
116 | leaf-level list, provides fantastic means of walking the nodes containing |
98 | data. Moreover, B+trees can be used for easy storing, resizing and merging |
117 | data. Moreover, B+trees can be used for easy storing, resizing and merging |
99 | of disjunctive intervals.</para> |
118 | of disjunctive intervals.</para> |
100 | 119 | ||
101 | <figure> |
120 | <figure> |
102 | <mediaobject id="btree" xreflabel=""> |
121 | <mediaobject id="btree" xreflabel=""> |
103 | <imageobject role="html"> |
122 | <imageobject role="html"> |
104 | <imagedata fileref="images/btree.png" format="PNG" /> |
123 | <imagedata fileref="images/btree.png" format="PNG" /> |
105 | </imageobject> |
124 | </imageobject> |
106 | 125 | ||
107 | <imageobject role="fop"> |
126 | <imageobject role="fop"> |
108 | <imagedata fileref="images.vector/btree.svg" format="SVG" /> |
127 | <imagedata fileref="images.vector/btree.svg" format="SVG" /> |
109 | </imageobject> |
128 | </imageobject> |
110 | 129 | </mediaobject> |
|
111 | 130 | ||
112 | </mediaobject> |
- | |
113 | <title>B+tree containing keys ranging from 1 to 12.</title> |
131 | <title>B+tree containing keys ranging from 1 to 12.</title> |
114 | </figure> |
132 | </figure> |
115 | - | ||
116 | </section> |
133 | </section> |
117 | </chapter> |
134 | </chapter> |
118 | 135 |