Subversion Repositories HelenOS-doc

Rev

Rev 53 | Rev 60 | 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
 
59 jermar 18
    <para>HelenOS uses doubly-circularly-linked lists to bind related data
19
    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
21
    list. Adding items to a list thus doesn't require any further memory
22
    allocations. Head and each link then contains forward and backward
23
    pointer. An empty list is composed of a sole head whose both pointers
24
    reference the head itself. The expense of two times bigger memory
25
    consumption as compared to memory consumption of singly linked lists is
26
    justified by constant insertion and removal times at random positions
27
    within the list.</para>
52 jermar 28
 
59 jermar 29
    <para>Lists are frequently used to implement FIFO behaviour (e.g.
30
    scheduler run queues or synchronization wait queues). Contrary to the FIFO
31
    type, which is also supported by HelenOS, they don't take up any unused
32
    space and are more general. On the other hand, they are slower than
33
    in-array FIFOs and can be hardly used to implement buffers.</para>
34
  </section>
35
 
36
  <section>
37
    <title>FIFO queues</title>
38
 
39
    <para>FIFO queues are implemented as either statically or dynamically
40
    allocated arrays<footnote>
41
        <para>Depending on the array size.</para>
42
      </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
44
    thereof. There can be as many items in the FIFO as is the number of
45
    elements in the array and no more. The indices are taken modulo size of
46
    the queue because as a consequence of insertions and deletions, the tail
47
    can have numericaly lower index than the head.</para>
48
 
49
    <para>FIFO queues are used, for example, in ASID management code to store
50
    inactive ASIDs or in userspace keyboard driver to buffer read
51
    characters.</para>
52
  </section>
53
 
54
  <section>
55
    <title>Hash tables</title>
56
 
57
    <para>The kernel, as well as userspace, provides hash table data type
58
    which uses separate chaining. The hash table type is very generic in that
59
    it forces the user to supply methods for computing the hash index,
60
    comparing items against a set of keys and the item removal callback
61
    function. Besides these virtual operations, the hash table is composed of
62
    a dynamically allocated array of list heads that represent each chain,
63
    number of chains and the maximal number of keys.</para>
64
  </section>
65
 
66
  <section>
67
    <title>Bitmaps</title>
68
 
69
    <para>Several bitmap operations such as clearing or setting consecutive
70
    bit sequences as well as copying portions of one bitmap into another one
71
    are supported.</para>
72
  </section>
73
 
74
  <section>
75
    <title>B+trees</title>
76
 
77
    <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in
78
    HelenOS implementation, are 3-4-5 balanced trees. They are characteristic
79
    by the fact that values are kept only in the leaf-level nodes and that
80
    these nodes are linked together in a list. This data structure has
81
    logaritmic search, insertion and deletion times and, thanks to the
82
    leaf-level list, provides fantastic means of walking the nodes containing
83
    data. Moreover, B+trees can be used for easy storing, resizing and merging
84
    of disjunctive intervals.</para>
85
  </section>
86
</chapter>