Subversion Repositories HelenOS-doc

Rev

Rev 53 | Rev 60 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed

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