Subversion Repositories HelenOS-doc

Rev

Rev 62 | Rev 74 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 62 Rev 73
Line 13... Line 13...
13 
  containers.</para>
 13 
  containers.</para>
14 
 
 14 
 
15 
  <section>
 15 
  <section>
16 
    <title>Lists</title>
 16 
    <title>Lists</title>
17 
 
 17 
 
- 
 
 18 
    <indexterm>
- 
 
 19 
      <primary>linked list</primary>
- 
 
 20 
    </indexterm>
- 
 
 21 
 
18 
    <para>HelenOS uses doubly-circularly-linked lists to bind related data
 22 
    <para>HelenOS uses doubly-circularly-linked lists to bind related data
19 
    together. Lists are composed of an independent sentinel node called head
 23 
    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
 24 
    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
 25 
    list. Adding items to a list thus doesn't require any further memory
22 
    allocations. Head and each link then contains forward and backward
 26 
    allocations. Head and each link then contains forward and backward
Line 34... Line 38...
34 
  </section>
 38 
  </section>
35 
 
 39 
 
36 
  <section>
 40 
  <section>
37 
    <title>FIFO queues</title>
 41 
    <title>FIFO queues</title>
38 
 
 42 
 
- 
 
 43 
    <indexterm>
- 
 
 44 
      <primary>FIFO queue</primary>
- 
 
 45 
    </indexterm>
- 
 
 46 
 
39 
    <para>FIFO queues are implemented as either statically or dynamically
 47 
    <para>FIFO queues are implemented as either statically or dynamically
40 
    allocated arrays<footnote>
 48 
    allocated arrays<footnote>
41 
        <para>Depending on the array size.</para>
 49 
        <para>Depending on the array size.</para>
42 
      </footnote> of some generic type with two indices. The first index
 50 
      </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
 51 
    points to the head of the FIFO queue and the other points to the tail
Line 49... Line 57...
49 
    <para>FIFO queues are used, for example, in ASID management code to store
 57 
    <para>FIFO queues are used, for example, in ASID management code to store
50 
    inactive ASIDs or in userspace keyboard driver to buffer read
 58 
    inactive ASIDs or in userspace keyboard driver to buffer read
51 
    characters.</para>
 59 
    characters.</para>
52 
 
 60 
 
53 
    <figure>
 61 
    <figure>
54 
    <mediaobject id="fifo" xreflabel="">
 62 
      <mediaobject id="fifo" xreflabel="">
55 
    <imageobject role="html">
 63 
        <imageobject role="html">
56 
        <imagedata fileref="images/fifo.png" format="PNG" />
 64 
          <imagedata fileref="images/fifo.png" format="PNG" />
57 
    </imageobject>
 65 
        </imageobject>
58 
           
 66 
 
59 
    <imageobject role="fop">
 67 
        <imageobject role="fop">
60 
        <imagedata fileref="images.vector/fifo.svg" format="SVG" />
 68 
          <imagedata fileref="images.vector/fifo.svg" format="SVG" />
61 
    </imageobject>
 69 
        </imageobject>
62 
                   
 - 
 
63 
    </mediaobject>
 70 
      </mediaobject>
64 
    <title>FIFO queue showing the wrap around the end of the array.</title>
 - 
 
65 
    </figure>
 - 
 
66 
 
 71 
 
- 
 
 72 
      <title>FIFO queue showing the wrap around the end of the array.</title>
- 
 
 73 
    </figure>
67 
  </section>
 74 
  </section>
68 
 
 75 
 
69 
  <section>
 76 
  <section>
70 
    <title>Hash tables</title>
 77 
    <title>Hash tables</title>
71 
 
 78 
 
- 
 
 79 
    <indexterm>
- 
 
 80 
      <primary>hash table</primary>
- 
 
 81 
    </indexterm>
- 
 
 82 
 
72 
    <para>The kernel, as well as userspace, provides hash table data type
 83 
    <para>The kernel, as well as userspace, provides hash table data type
73 
    which uses separate chaining. The hash table type is very generic in that
 84 
    which uses separate chaining. The hash table type is very generic in that
74 
    it forces the user to supply methods for computing the hash index,
 85 
    it forces the user to supply methods for computing the hash index,
75 
    comparing items against a set of keys and the item removal callback
 86 
    comparing items against a set of keys and the item removal callback
76 
    function. Besides these virtual operations, the hash table is composed of
 87 
    function. Besides these virtual operations, the hash table is composed of
Line 79... Line 90...
79 
  </section>
 90 
  </section>
80 
 
 91 
 
81 
  <section>
 92 
  <section>
82 
    <title>Bitmaps</title>
 93 
    <title>Bitmaps</title>
83 
 
 94 
 
- 
 
 95 
    <indexterm>
- 
 
 96 
      <primary>bitmap</primary>
- 
 
 97 
    </indexterm>
- 
 
 98 
 
84 
    <para>Several bitmap operations such as clearing or setting consecutive
 99 
    <para>Several bitmap operations such as clearing or setting consecutive
85 
    bit sequences as well as copying portions of one bitmap into another one
 100 
    bit sequences as well as copying portions of one bitmap into another one
86 
    are supported.</para>
 101 
    are supported.</para>
87 
  </section>
 102 
  </section>
88 
 
 103 
 
89 
  <section>
 104 
  <section>
90 
    <title>B+trees</title>
 105 
    <title>B+trees</title>
91 
 
 106 
 
- 
 
 107 
    <indexterm>
- 
 
 108 
      <primary>B-tree</primary>
- 
 
 109 
    </indexterm>
- 
 
 110 
 
92 
    <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in
 111 
    <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in
93 
    HelenOS implementation, are 3-4-5 balanced trees. They are characteristic
 112 
    HelenOS implementation, are 3-4-5 balanced trees. They are characteristic
94 
    by the fact that values are kept only in the leaf-level nodes and that
 113 
    by the fact that values are kept only in the leaf-level nodes and that
95 
    these nodes are linked together in a list. This data structure has
 114 
    these nodes are linked together in a list. This data structure has
96 
    logaritmic search, insertion and deletion times and, thanks to the
 115 
    logaritmic search, insertion and deletion times and, thanks to the
97 
    leaf-level list, provides fantastic means of walking the nodes containing
 116 
    leaf-level list, provides fantastic means of walking the nodes containing
98 
    data. Moreover, B+trees can be used for easy storing, resizing and merging
 117 
    data. Moreover, B+trees can be used for easy storing, resizing and merging
99 
    of disjunctive intervals.</para>
 118 
    of disjunctive intervals.</para>
100 
 
 119 
 
101 
    <figure>
 120 
    <figure>
102 
    <mediaobject id="btree" xreflabel="">
 121 
      <mediaobject id="btree" xreflabel="">
103 
    <imageobject role="html">
 122 
        <imageobject role="html">
104 
        <imagedata fileref="images/btree.png" format="PNG" />
 123 
          <imagedata fileref="images/btree.png" format="PNG" />
105 
    </imageobject>
 124 
        </imageobject>
106 
           
 125 
 
107 
    <imageobject role="fop">
 126 
        <imageobject role="fop">
108 
        <imagedata fileref="images.vector/btree.svg" format="SVG" />
 127 
          <imagedata fileref="images.vector/btree.svg" format="SVG" />
109 
    </imageobject>
 128 
        </imageobject>
110 
                   
 129 
      </mediaobject>
111 
 
 130 
 
112 
    </mediaobject>
 - 
 
113 
    <title>B+tree containing keys ranging from 1 to 12.</title>
 131 
      <title>B+tree containing keys ranging from 1 to 12.</title>
114 
    </figure>
 132 
    </figure>
115 
 
 - 
 
116 
  </section>
 133 
  </section>
117 
</chapter>
 134 
</chapter>
118 

            135