Subversion Repositories HelenOS-doc

Rev

Rev 87 | Rev 98 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 87 Rev 95
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
 
-
 
39
    <figure>
-
 
40
      <mediaobject id="list" xreflabel="">
-
 
41
        <imageobject role="pdf">
-
 
42
          <imagedata fileref="images.vector/list.pdf" format="PDF" />
-
 
43
        </imageobject>
-
 
44
 
-
 
45
        <imageobject role="html">
-
 
46
          <imagedata fileref="images/list.png" format="PNG" />
-
 
47
        </imageobject>
-
 
48
 
-
 
49
        <imageobject role="fop">
-
 
50
          <imagedata fileref="images.vector/list.svg" format="SVG" />
-
 
51
        </imageobject>
-
 
52
      </mediaobject>
-
 
53
 
-
 
54
      <title>Doubly-circularly-linked list</title>
-
 
55
    </figure>
38
  </section>
56
  </section>
39
 
57
 
40
  <section>
58
  <section>
41
    <title>FIFO queues</title>
59
    <title>FIFO queues</title>
42
 
60
 
43
    <indexterm>
61
    <indexterm>
44
      <primary>FIFO queue</primary>
62
      <primary>FIFO queue</primary>
45
    </indexterm>
63
    </indexterm>
46
 
64
 
47
    <para>FIFO queues are implemented as either statically or dynamically
65
    <para>FIFO queues are implemented as either statically or dynamically
48
    allocated arrays<footnote>
66
    allocated arrays<footnote>
49
        <para>Depending on the array size.</para>
67
        <para>Depending on the array size.</para>
50
      </footnote> of some generic type with two indices. The first index
68
      </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
69
    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
70
    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
71
    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
72
    the queue because as a consequence of insertions and deletions, the tail
55
    can have numericaly lower index than the head.</para>
73
    can have numericaly lower index than the head.</para>
56
 
74
 
57
    <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
58
    inactive ASIDs or in userspace keyboard driver to buffer read
76
    inactive ASIDs or in userspace keyboard driver to buffer read
59
    characters.</para>
77
    characters.</para>
60
 
78
 
61
    <figure>
79
    <figure>
62
      <mediaobject id="fifo" xreflabel="">
80
      <mediaobject id="fifo" xreflabel="">
63
        <imageobject role="pdf">
81
        <imageobject role="pdf">
64
          <imagedata fileref="images.vector/fifo.pdf" format="PDF" />
82
          <imagedata fileref="images.vector/fifo.pdf" format="PDF" />
65
        </imageobject>
83
        </imageobject>
66
 
84
 
67
        <imageobject role="html">
85
        <imageobject role="html">
68
          <imagedata fileref="images/fifo.png" format="PNG" />
86
          <imagedata fileref="images/fifo.png" format="PNG" />
69
        </imageobject>
87
        </imageobject>
70
 
88
 
71
        <imageobject role="fop">
89
        <imageobject role="fop">
72
          <imagedata fileref="images.vector/fifo.svg" format="SVG" />
90
          <imagedata fileref="images.vector/fifo.svg" format="SVG" />
73
        </imageobject>
91
        </imageobject>
74
      </mediaobject>
92
      </mediaobject>
75
 
93
 
76
      <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>
77
    </figure>
95
    </figure>
78
  </section>
96
  </section>
79
 
97
 
80
  <section id="hashtables">
98
  <section id="hashtables">
81
    <title>Hash tables</title>
99
    <title>Hash tables</title>
82
 
100
 
83
    <indexterm>
101
    <indexterm>
84
      <primary>hash table</primary>
102
      <primary>hash table</primary>
85
    </indexterm>
103
    </indexterm>
86
 
104
 
87
    <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
88
    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
89
    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,
90
    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
91
    function. Besides these virtual operations, the hash table is composed of
109
    function. Besides these virtual operations, the hash table is composed of
92
    a dynamically allocated array of list heads that represent each chain,
110
    a dynamically allocated array of list heads that represent each chain,
93
    number of chains and the maximal number of keys.</para>
111
    number of chains and the maximal number of keys.</para>
-
 
112
 
-
 
113
    <figure>
-
 
114
      <mediaobject id="hash" xreflabel="">
-
 
115
        <imageobject role="pdf">
-
 
116
          <imagedata fileref="images.vector/hash.pdf" format="PDF" />
-
 
117
        </imageobject>
-
 
118
 
-
 
119
        <imageobject role="html">
-
 
120
          <imagedata fileref="images/hash.png" format="PNG" />
-
 
121
        </imageobject>
-
 
122
 
-
 
123
        <imageobject role="fop">
-
 
124
          <imagedata fileref="images.vector/hash.svg" format="SVG" />
-
 
125
        </imageobject>
-
 
126
      </mediaobject>
-
 
127
 
-
 
128
      <title>Generic hash table.</title>
-
 
129
    </figure>
-
 
130
 
94
  </section>
131
  </section>
95
 
132
 
96
  <section>
133
  <section>
97
    <title>Bitmaps</title>
134
    <title>Bitmaps</title>
98
 
135
 
99
    <indexterm>
136
    <indexterm>
100
      <primary>bitmap</primary>
137
      <primary>bitmap</primary>
101
    </indexterm>
138
    </indexterm>
102
 
139
 
103
    <para>Several bitmap operations such as clearing or setting consecutive
140
    <para>Several bitmap operations such as clearing or setting consecutive
104
    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
105
    are supported.</para>
142
    are supported.</para>
106
  </section>
143
  </section>
107
 
144
 
108
  <section>
145
  <section>
109
    <title>B+trees</title>
146
    <title>B+trees</title>
110
 
147
 
111
    <indexterm>
148
    <indexterm>
112
      <primary>B-tree</primary>
149
      <primary>B-tree</primary>
113
    </indexterm>
150
    </indexterm>
114
 
151
 
115
    <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in
152
    <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
153
    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
154
    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
155
    these nodes are linked together in a list. This data structure has
119
    logaritmic search, insertion and deletion times and, thanks to the
156
    logaritmic search, insertion and deletion times and, thanks to the
120
    leaf-level list, provides fantastic means of walking the nodes containing
157
    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
158
    data. Moreover, B+trees can be used for easy storing, resizing and merging
122
    of disjunctive intervals.</para>
159
    of disjunctive intervals.</para>
123
 
160
 
124
    <figure>
161
    <figure>
125
      <mediaobject id="btree" xreflabel="">
162
      <mediaobject id="btree" xreflabel="">
126
        <imageobject role="pdf">
163
        <imageobject role="pdf">
127
          <imagedata fileref="images.vector/btree.pdf" format="PDF" />
164
          <imagedata fileref="images.vector/btree.pdf" format="PDF" />
128
        </imageobject>
165
        </imageobject>
129
 
166
 
130
        <imageobject role="html">
167
        <imageobject role="html">
131
          <imagedata fileref="images/btree.png" format="PNG" />
168
          <imagedata fileref="images/btree.png" format="PNG" />
132
        </imageobject>
169
        </imageobject>
133
 
170
 
134
        <imageobject role="fop">
171
        <imageobject role="fop">
135
          <imagedata fileref="images.vector/btree.svg" format="SVG" />
172
          <imagedata fileref="images.vector/btree.svg" format="SVG" />
136
        </imageobject>
173
        </imageobject>
137
      </mediaobject>
174
      </mediaobject>
138
 
175
 
139
      <title>B+tree containing keys ranging from 1 to 12.</title>
176
      <title>B+tree containing keys ranging from 1 to 12.</title>
140
    </figure>
177
    </figure>
141
  </section>
178
  </section>
142
</chapter>
179
</chapter>