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