Subversion Repositories HelenOS-doc

Rev

Rev 87 | Rev 98 | 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>
95 bondari 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>
59 jermar 56
  </section>
57
 
58
  <section>
59
    <title>FIFO queues</title>
60
 
73 bondari 61
    <indexterm>
62
      <primary>FIFO queue</primary>
63
    </indexterm>
64
 
59 jermar 65
    <para>FIFO queues are implemented as either statically or dynamically
66
    allocated arrays<footnote>
67
        <para>Depending on the array size.</para>
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
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
72
    the queue because as a consequence of insertions and deletions, the tail
73
    can have numericaly lower index than the head.</para>
74
 
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
77
    characters.</para>
61 jermar 78
 
62 jermar 79
    <figure>
73 bondari 80
      <mediaobject id="fifo" xreflabel="">
87 bondari 81
        <imageobject role="pdf">
82
          <imagedata fileref="images.vector/fifo.pdf" format="PDF" />
77 bondari 83
        </imageobject>
84
 
73 bondari 85
        <imageobject role="html">
86
          <imagedata fileref="images/fifo.png" format="PNG" />
87
        </imageobject>
88
 
89
        <imageobject role="fop">
90
          <imagedata fileref="images.vector/fifo.svg" format="SVG" />
91
        </imageobject>
92
      </mediaobject>
93
 
94
      <title>FIFO queue showing the wrap around the end of the array.</title>
62 jermar 95
    </figure>
59 jermar 96
  </section>
97
 
74 bondari 98
  <section id="hashtables">
59 jermar 99
    <title>Hash tables</title>
100
 
73 bondari 101
    <indexterm>
102
      <primary>hash table</primary>
103
    </indexterm>
104
 
59 jermar 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
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
109
    function. Besides these virtual operations, the hash table is composed of
110
    a dynamically allocated array of list heads that represent each chain,
111
    number of chains and the maximal number of keys.</para>
95 bondari 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
 
59 jermar 131
  </section>
132
 
133
  <section>
134
    <title>Bitmaps</title>
135
 
73 bondari 136
    <indexterm>
137
      <primary>bitmap</primary>
138
    </indexterm>
139
 
59 jermar 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
142
    are supported.</para>
143
  </section>
144
 
145
  <section>
146
    <title>B+trees</title>
147
 
73 bondari 148
    <indexterm>
149
      <primary>B-tree</primary>
150
    </indexterm>
151
 
59 jermar 152
    <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in
153
    HelenOS implementation, are 3-4-5 balanced trees. They are characteristic
154
    by the fact that values are kept only in the leaf-level nodes and that
155
    these nodes are linked together in a list. This data structure has
156
    logaritmic search, insertion and deletion times and, thanks to the
157
    leaf-level list, provides fantastic means of walking the nodes containing
158
    data. Moreover, B+trees can be used for easy storing, resizing and merging
159
    of disjunctive intervals.</para>
60 jermar 160
 
62 jermar 161
    <figure>
73 bondari 162
      <mediaobject id="btree" xreflabel="">
87 bondari 163
        <imageobject role="pdf">
164
          <imagedata fileref="images.vector/btree.pdf" format="PDF" />
77 bondari 165
        </imageobject>
166
 
73 bondari 167
        <imageobject role="html">
168
          <imagedata fileref="images/btree.png" format="PNG" />
169
        </imageobject>
62 jermar 170
 
73 bondari 171
        <imageobject role="fop">
172
          <imagedata fileref="images.vector/btree.svg" format="SVG" />
173
        </imageobject>
174
      </mediaobject>
175
 
176
      <title>B+tree containing keys ranging from 1 to 12.</title>
62 jermar 177
    </figure>
59 jermar 178
  </section>
179
</chapter>