Subversion Repositories HelenOS-doc

Rev

Rev 74 | Rev 87 | 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>
38
  </section>
39
 
40
  <section>
41
    <title>FIFO queues</title>
42
 
73 bondari 43
    <indexterm>
44
      <primary>FIFO queue</primary>
45
    </indexterm>
46
 
59 jermar 47
    <para>FIFO queues are implemented as either statically or dynamically
48
    allocated arrays<footnote>
49
        <para>Depending on the array size.</para>
50
      </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
52
    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
54
    the queue because as a consequence of insertions and deletions, the tail
55
    can have numericaly lower index than the head.</para>
56
 
57
    <para>FIFO queues are used, for example, in ASID management code to store
58
    inactive ASIDs or in userspace keyboard driver to buffer read
59
    characters.</para>
61 jermar 60
 
62 jermar 61
    <figure>
73 bondari 62
      <mediaobject id="fifo" xreflabel="">
77 bondari 63
        <imageobject role="eps">
64
          <imagedata fileref="images.vector/fifo.eps" format="EPS" />
65
        </imageobject>
66
 
73 bondari 67
        <imageobject role="html">
68
          <imagedata fileref="images/fifo.png" format="PNG" />
69
        </imageobject>
70
 
71
        <imageobject role="fop">
72
          <imagedata fileref="images.vector/fifo.svg" format="SVG" />
73
        </imageobject>
74
      </mediaobject>
75
 
76
      <title>FIFO queue showing the wrap around the end of the array.</title>
62 jermar 77
    </figure>
59 jermar 78
  </section>
79
 
74 bondari 80
  <section id="hashtables">
59 jermar 81
    <title>Hash tables</title>
82
 
73 bondari 83
    <indexterm>
84
      <primary>hash table</primary>
85
    </indexterm>
86
 
59 jermar 87
    <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
89
    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
91
    function. Besides these virtual operations, the hash table is composed of
92
    a dynamically allocated array of list heads that represent each chain,
93
    number of chains and the maximal number of keys.</para>
94
  </section>
95
 
96
  <section>
97
    <title>Bitmaps</title>
98
 
73 bondari 99
    <indexterm>
100
      <primary>bitmap</primary>
101
    </indexterm>
102
 
59 jermar 103
    <para>Several bitmap operations such as clearing or setting consecutive
104
    bit sequences as well as copying portions of one bitmap into another one
105
    are supported.</para>
106
  </section>
107
 
108
  <section>
109
    <title>B+trees</title>
110
 
73 bondari 111
    <indexterm>
112
      <primary>B-tree</primary>
113
    </indexterm>
114
 
59 jermar 115
    <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
117
    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
119
    logaritmic search, insertion and deletion times and, thanks to the
120
    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
122
    of disjunctive intervals.</para>
60 jermar 123
 
62 jermar 124
    <figure>
73 bondari 125
      <mediaobject id="btree" xreflabel="">
77 bondari 126
        <imageobject role="eps">
127
          <imagedata fileref="images.vector/btree.eps" format="EPS" />
128
        </imageobject>
129
 
73 bondari 130
        <imageobject role="html">
131
          <imagedata fileref="images/btree.png" format="PNG" />
132
        </imageobject>
62 jermar 133
 
73 bondari 134
        <imageobject role="fop">
135
          <imagedata fileref="images.vector/btree.svg" format="SVG" />
136
        </imageobject>
137
      </mediaobject>
138
 
139
      <title>B+tree containing keys ranging from 1 to 12.</title>
62 jermar 140
    </figure>
59 jermar 141
  </section>
142
</chapter>