Subversion Repositories HelenOS-doc

Rev

Rev 133 | 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
 
133 jermar 5
  <title>Data Structures</title>
52 jermar 6
 
139 palkovsky 7
  <para>There is a lot of data that either flows through various HelenOS
59 jermar 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,
139 palkovsky 11
  deploys several house keeping data types that are designed to facilitate
59 jermar 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
 
101 bondari 39
    <figure float="1">
95 bondari 40
      <mediaobject id="list" xreflabel="">
41
        <imageobject role="pdf">
105 bondari 42
          <imagedata fileref="images/list.pdf" format="PDF" />
95 bondari 43
        </imageobject>
44
 
45
        <imageobject role="html">
46
          <imagedata fileref="images/list.png" format="PNG" />
47
        </imageobject>
48
 
49
        <imageobject role="fop">
105 bondari 50
          <imagedata fileref="images/list.svg" format="SVG" />
95 bondari 51
        </imageobject>
52
      </mediaobject>
53
 
54
      <title>Doubly-circularly-linked list</title>
55
    </figure>
59 jermar 56
  </section>
57
 
58
  <section>
131 jermar 59
    <title>FIFO Queues</title>
59 jermar 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
 
101 bondari 79
    <figure float="1">
73 bondari 80
      <mediaobject id="fifo" xreflabel="">
87 bondari 81
        <imageobject role="pdf">
105 bondari 82
          <imagedata fileref="images/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">
105 bondari 90
          <imagedata fileref="images/fifo.svg" format="SVG" />
73 bondari 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">
131 jermar 99
    <title>Hash Tables</title>
59 jermar 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
 
101 bondari 113
    <figure float="1">
95 bondari 114
      <mediaobject id="hash" xreflabel="">
115
        <imageobject role="pdf">
105 bondari 116
          <imagedata fileref="images/hash.pdf" format="PDF" />
95 bondari 117
        </imageobject>
118
 
119
        <imageobject role="html">
120
          <imagedata fileref="images/hash.png" format="PNG" />
121
        </imageobject>
122
 
123
        <imageobject role="fop">
105 bondari 124
          <imagedata fileref="images/hash.svg" format="SVG" />
95 bondari 125
        </imageobject>
126
      </mediaobject>
127
 
128
      <title>Generic hash table.</title>
129
    </figure>
59 jermar 130
  </section>
131
 
132
  <section>
133
    <title>Bitmaps</title>
134
 
73 bondari 135
    <indexterm>
136
      <primary>bitmap</primary>
137
    </indexterm>
138
 
59 jermar 139
    <para>Several bitmap operations such as clearing or setting consecutive
140
    bit sequences as well as copying portions of one bitmap into another one
141
    are supported.</para>
142
  </section>
143
 
144
  <section>
145
    <title>B+trees</title>
146
 
73 bondari 147
    <indexterm>
98 bondari 148
      <primary>B-trees</primary>
131 jermar 149
 
150
      <secondary>- B+tree</secondary>
73 bondari 151
    </indexterm>
152
 
59 jermar 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
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
157
    logaritmic search, insertion and deletion times and, thanks to the
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
160
    of disjunctive intervals.</para>
60 jermar 161
 
101 bondari 162
    <figure float="1">
73 bondari 163
      <mediaobject id="btree" xreflabel="">
87 bondari 164
        <imageobject role="pdf">
105 bondari 165
          <imagedata fileref="images/btree.pdf" format="PDF" />
77 bondari 166
        </imageobject>
167
 
73 bondari 168
        <imageobject role="html">
169
          <imagedata fileref="images/btree.png" format="PNG" />
170
        </imageobject>
62 jermar 171
 
73 bondari 172
        <imageobject role="fop">
105 bondari 173
          <imagedata fileref="images/btree.svg" format="SVG" />
73 bondari 174
        </imageobject>
175
      </mediaobject>
176
 
177
      <title>B+tree containing keys ranging from 1 to 12.</title>
62 jermar 178
    </figure>
59 jermar 179
  </section>
180
</chapter>