WebSVN – HelenOS-doc – Diff – /design/trunk/src/ch_ds.xml


<?xml version="1.0" encoding="UTF-8"?>
<chapter id="ds">
  <?dbhtml filename="ds.html"?>
 
  <title>Data Structures</title>
 
  <para>There is lots of data that either flows through various HelenOS
  subsystems or is stored directly by them. Each subsystem uses its own data
  structures to represent the data. These data structures need to be kept
  somewhere. In order to work efficiently, HelenOS, and especially its kernel,
  deploys several house keeping data types that are designed to faciliate
  managing other data structures. Most of them serve like generic
  containers.</para>
 
  <section>
    <title>Lists</title>
 
    <indexterm>
      <primary>linked list</primary>
    </indexterm>
 
    <para>HelenOS uses doubly-circularly-linked lists to bind related data
    together. Lists are composed of an independent sentinel node called head
    and links that are always part of the object that is to be put into the
    list. Adding items to a list thus doesn't require any further memory
    allocations. Head and each link then contains forward and backward
    pointer. An empty list is composed of a sole head whose both pointers
    reference the head itself. The expense of two times bigger memory
    consumption as compared to memory consumption of singly linked lists is
    justified by constant insertion and removal times at random positions
    within the list.</para>
 
    <para>Lists are frequently used to implement FIFO behaviour (e.g.
    scheduler run queues or synchronization wait queues). Contrary to the FIFO
    type, which is also supported by HelenOS, they don't take up any unused
    space and are more general. On the other hand, they are slower than
    in-array FIFOs and can be hardly used to implement buffers.</para>
 
    <figure float="1">
      <mediaobject id="list" xreflabel="">
        <imageobject role="pdf">
          <imagedata fileref="images/list.pdf" format="PDF" />
        </imageobject>
 
        <imageobject role="html">
          <imagedata fileref="images/list.png" format="PNG" />
        </imageobject>
 
        <imageobject role="fop">
          <imagedata fileref="images/list.svg" format="SVG" />
        </imageobject>
      </mediaobject>
 
      <title>Doubly-circularly-linked list</title>
    </figure>
  </section>
 
  <section>
    <title>FIFO Queues</title>
 
    <indexterm>
      <primary>FIFO queue</primary>
    </indexterm>
 
    <para>FIFO queues are implemented as either statically or dynamically
    allocated arrays<footnote>
        <para>Depending on the array size.</para>
      </footnote> of some generic type with two indices. The first index
    points to the head of the FIFO queue and the other points to the tail
    thereof. There can be as many items in the FIFO as is the number of
    elements in the array and no more. The indices are taken modulo size of
    the queue because as a consequence of insertions and deletions, the tail
    can have numericaly lower index than the head.</para>
 
    <para>FIFO queues are used, for example, in ASID management code to store
    inactive ASIDs or in userspace keyboard driver to buffer read
    characters.</para>
 
    <figure float="1">
      <mediaobject id="fifo" xreflabel="">
        <imageobject role="pdf">
          <imagedata fileref="images/fifo.pdf" format="PDF" />
        </imageobject>
 
        <imageobject role="html">
          <imagedata fileref="images/fifo.png" format="PNG" />
        </imageobject>
 
        <imageobject role="fop">
          <imagedata fileref="images/fifo.svg" format="SVG" />
        </imageobject>
      </mediaobject>
 
      <title>FIFO queue showing the wrap around the end of the array.</title>
    </figure>
  </section>
 
  <section id="hashtables">
    <title>Hash Tables</title>
 
    <indexterm>
      <primary>hash table</primary>
    </indexterm>
 
    <para>The kernel, as well as userspace, provides hash table data type
    which uses separate chaining. The hash table type is very generic in that
    it forces the user to supply methods for computing the hash index,
    comparing items against a set of keys and the item removal callback
    function. Besides these virtual operations, the hash table is composed of
    a dynamically allocated array of list heads that represent each chain,
    number of chains and the maximal number of keys.</para>
 
    <figure float="1">
      <mediaobject id="hash" xreflabel="">
        <imageobject role="pdf">
          <imagedata fileref="images/hash.pdf" format="PDF" />
        </imageobject>
 
        <imageobject role="html">
          <imagedata fileref="images/hash.png" format="PNG" />
        </imageobject>
 
        <imageobject role="fop">
          <imagedata fileref="images/hash.svg" format="SVG" />
        </imageobject>
      </mediaobject>
 
      <title>Generic hash table.</title>
    </figure>
  </section>
 
  <section>
    <title>Bitmaps</title>
 
    <indexterm>
      <primary>bitmap</primary>
    </indexterm>
 
    <para>Several bitmap operations such as clearing or setting consecutive
    bit sequences as well as copying portions of one bitmap into another one
    are supported.</para>
  </section>
 
  <section>
    <title>B+trees</title>
 
    <indexterm>
      <primary>B-trees</primary>
 
      <secondary>- B+tree</secondary>
    </indexterm>
 
    <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in
    HelenOS implementation, are 3-4-5 balanced trees. They are characteristic
    by the fact that values are kept only in the leaf-level nodes and that
    these nodes are linked together in a list. This data structure has
    logaritmic search, insertion and deletion times and, thanks to the
    leaf-level list, provides fantastic means of walking the nodes containing
    data. Moreover, B+trees can be used for easy storing, resizing and merging
    of disjunctive intervals.</para>
 
    <figure float="1">
      <mediaobject id="btree" xreflabel="">
        <imageobject role="pdf">
          <imagedata fileref="images/btree.pdf" format="PDF" />
        </imageobject>
 
        <imageobject role="html">
          <imagedata fileref="images/btree.png" format="PNG" />
        </imageobject>
 
        <imageobject role="fop">
          <imagedata fileref="images/btree.svg" format="SVG" />
        </imageobject>
      </mediaobject>
 
      <title>B+tree containing keys ranging from 1 to 12.</title>
    </figure>
  </section>
</chapter>

Rev 131	Rev 133
1	<?xml version="1.0" encoding="UTF-8"?>	1	<?xml version="1.0" encoding="UTF-8"?>
2	<chapter id="ds">	2	<chapter id="ds">
3	<?dbhtml filename="ds.html"?>	3	<?dbhtml filename="ds.html"?>
4		4
5	<title>Data structures</title>	5	<title>Data Structures</title>
6		6
7	<para>There is lots of data that either flows through various HelenOS	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	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	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,	10	somewhere. In order to work efficiently, HelenOS, and especially its kernel,
11	deploys several house keeping data types that are designed to faciliate	11	deploys several house keeping data types that are designed to faciliate
12	managing other data structures. Most of them serve like generic	12	managing other data structures. Most of them serve like generic
13	containers.</para>	13	containers.</para>
14		14
15	<section>	15	<section>
16	<title>Lists</title>	16	<title>Lists</title>
17		17
18	<indexterm>	18	<indexterm>
19	<primary>linked list</primary>	19	<primary>linked list</primary>
20	</indexterm>	20	</indexterm>
21		21
22	<para>HelenOS uses doubly-circularly-linked lists to bind related data	22	<para>HelenOS uses doubly-circularly-linked lists to bind related data
23	together. Lists are composed of an independent sentinel node called head	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	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	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	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	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	28	reference the head itself. The expense of two times bigger memory
29	consumption as compared to memory consumption of singly linked lists is	29	consumption as compared to memory consumption of singly linked lists is
30	justified by constant insertion and removal times at random positions	30	justified by constant insertion and removal times at random positions
31	within the list.</para>	31	within the list.</para>
32		32
33	<para>Lists are frequently used to implement FIFO behaviour (e.g.	33	<para>Lists are frequently used to implement FIFO behaviour (e.g.
34	scheduler run queues or synchronization wait queues). Contrary to the FIFO	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	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	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>	37	in-array FIFOs and can be hardly used to implement buffers.</para>
38		38
39	<figure float="1">	39	<figure float="1">
40	<mediaobject id="list" xreflabel="">	40	<mediaobject id="list" xreflabel="">
41	<imageobject role="pdf">	41	<imageobject role="pdf">
42	<imagedata fileref="images/list.pdf" format="PDF" />	42	<imagedata fileref="images/list.pdf" format="PDF" />
43	</imageobject>	43	</imageobject>
44		44
45	<imageobject role="html">	45	<imageobject role="html">
46	<imagedata fileref="images/list.png" format="PNG" />	46	<imagedata fileref="images/list.png" format="PNG" />
47	</imageobject>	47	</imageobject>
48		48
49	<imageobject role="fop">	49	<imageobject role="fop">
50	<imagedata fileref="images/list.svg" format="SVG" />	50	<imagedata fileref="images/list.svg" format="SVG" />
51	</imageobject>	51	</imageobject>
52	</mediaobject>	52	</mediaobject>
53		53
54	<title>Doubly-circularly-linked list</title>	54	<title>Doubly-circularly-linked list</title>
55	</figure>	55	</figure>
56	</section>	56	</section>
57		57
58	<section>	58	<section>
59	<title>FIFO Queues</title>	59	<title>FIFO Queues</title>
60		60
61	<indexterm>	61	<indexterm>
62	<primary>FIFO queue</primary>	62	<primary>FIFO queue</primary>
63	</indexterm>	63	</indexterm>
64		64
65	<para>FIFO queues are implemented as either statically or dynamically	65	<para>FIFO queues are implemented as either statically or dynamically
66	allocated arrays<footnote>	66	allocated arrays<footnote>
67	<para>Depending on the array size.</para>	67	<para>Depending on the array size.</para>
68	</footnote> of some generic type with two indices. The first index	68	</footnote> of some generic type with two indices. The first index
69	points to the head of the FIFO queue and the other points to the tail	69	points to the head of the FIFO queue and the other points to the tail
70	thereof. There can be as many items in the FIFO as is the number of	70	thereof. There can be as many items in the FIFO as is the number of
71	elements in the array and no more. The indices are taken modulo size of	71	elements in the array and no more. The indices are taken modulo size of
72	the queue because as a consequence of insertions and deletions, the tail	72	the queue because as a consequence of insertions and deletions, the tail
73	can have numericaly lower index than the head.</para>	73	can have numericaly lower index than the head.</para>
74		74
75	<para>FIFO queues are used, for example, in ASID management code to store	75	<para>FIFO queues are used, for example, in ASID management code to store
76	inactive ASIDs or in userspace keyboard driver to buffer read	76	inactive ASIDs or in userspace keyboard driver to buffer read
77	characters.</para>	77	characters.</para>
78		78
79	<figure float="1">	79	<figure float="1">
80	<mediaobject id="fifo" xreflabel="">	80	<mediaobject id="fifo" xreflabel="">
81	<imageobject role="pdf">	81	<imageobject role="pdf">
82	<imagedata fileref="images/fifo.pdf" format="PDF" />	82	<imagedata fileref="images/fifo.pdf" format="PDF" />
83	</imageobject>	83	</imageobject>
84		84
85	<imageobject role="html">	85	<imageobject role="html">
86	<imagedata fileref="images/fifo.png" format="PNG" />	86	<imagedata fileref="images/fifo.png" format="PNG" />
87	</imageobject>	87	</imageobject>
88		88
89	<imageobject role="fop">	89	<imageobject role="fop">
90	<imagedata fileref="images/fifo.svg" format="SVG" />	90	<imagedata fileref="images/fifo.svg" format="SVG" />
91	</imageobject>	91	</imageobject>
92	</mediaobject>	92	</mediaobject>
93		93
94	<title>FIFO queue showing the wrap around the end of the array.</title>	94	<title>FIFO queue showing the wrap around the end of the array.</title>
95	</figure>	95	</figure>
96	</section>	96	</section>
97		97
98	<section id="hashtables">	98	<section id="hashtables">
99	<title>Hash Tables</title>	99	<title>Hash Tables</title>
100		100
101	<indexterm>	101	<indexterm>
102	<primary>hash table</primary>	102	<primary>hash table</primary>
103	</indexterm>	103	</indexterm>
104		104
105	<para>The kernel, as well as userspace, provides hash table data type	105	<para>The kernel, as well as userspace, provides hash table data type
106	which uses separate chaining. The hash table type is very generic in that	106	which uses separate chaining. The hash table type is very generic in that
107	it forces the user to supply methods for computing the hash index,	107	it forces the user to supply methods for computing the hash index,
108	comparing items against a set of keys and the item removal callback	108	comparing items against a set of keys and the item removal callback
109	function. Besides these virtual operations, the hash table is composed of	109	function. Besides these virtual operations, the hash table is composed of
110	a dynamically allocated array of list heads that represent each chain,	110	a dynamically allocated array of list heads that represent each chain,
111	number of chains and the maximal number of keys.</para>	111	number of chains and the maximal number of keys.</para>
112		112
113	<figure float="1">	113	<figure float="1">
114	<mediaobject id="hash" xreflabel="">	114	<mediaobject id="hash" xreflabel="">
115	<imageobject role="pdf">	115	<imageobject role="pdf">
116	<imagedata fileref="images/hash.pdf" format="PDF" />	116	<imagedata fileref="images/hash.pdf" format="PDF" />
117	</imageobject>	117	</imageobject>
118		118
119	<imageobject role="html">	119	<imageobject role="html">
120	<imagedata fileref="images/hash.png" format="PNG" />	120	<imagedata fileref="images/hash.png" format="PNG" />
121	</imageobject>	121	</imageobject>
122		122
123	<imageobject role="fop">	123	<imageobject role="fop">
124	<imagedata fileref="images/hash.svg" format="SVG" />	124	<imagedata fileref="images/hash.svg" format="SVG" />
125	</imageobject>	125	</imageobject>
126	</mediaobject>	126	</mediaobject>
127		127
128	<title>Generic hash table.</title>	128	<title>Generic hash table.</title>
129	</figure>	129	</figure>
130	</section>	130	</section>
131		131
132	<section>	132	<section>
133	<title>Bitmaps</title>	133	<title>Bitmaps</title>
134		134
135	<indexterm>	135	<indexterm>
136	<primary>bitmap</primary>	136	<primary>bitmap</primary>
137	</indexterm>	137	</indexterm>
138		138
139	<para>Several bitmap operations such as clearing or setting consecutive	139	<para>Several bitmap operations such as clearing or setting consecutive
140	bit sequences as well as copying portions of one bitmap into another one	140	bit sequences as well as copying portions of one bitmap into another one
141	are supported.</para>	141	are supported.</para>
142	</section>	142	</section>
143		143
144	<section>	144	<section>
145	<title>B+trees</title>	145	<title>B+trees</title>
146		146
147	<indexterm>	147	<indexterm>
148	<primary>B-trees</primary>	148	<primary>B-trees</primary>
149		149
150	<secondary>- B+tree</secondary>	150	<secondary>- B+tree</secondary>
151	</indexterm>	151	</indexterm>
152		152
153	<para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in	153	<para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in
154	HelenOS implementation, are 3-4-5 balanced trees. They are characteristic	154	HelenOS implementation, are 3-4-5 balanced trees. They are characteristic
155	by the fact that values are kept only in the leaf-level nodes and that	155	by the fact that values are kept only in the leaf-level nodes and that
156	these nodes are linked together in a list. This data structure has	156	these nodes are linked together in a list. This data structure has
157	logaritmic search, insertion and deletion times and, thanks to the	157	logaritmic search, insertion and deletion times and, thanks to the
158	leaf-level list, provides fantastic means of walking the nodes containing	158	leaf-level list, provides fantastic means of walking the nodes containing
159	data. Moreover, B+trees can be used for easy storing, resizing and merging	159	data. Moreover, B+trees can be used for easy storing, resizing and merging
160	of disjunctive intervals.</para>	160	of disjunctive intervals.</para>
161		161
162	<figure float="1">	162	<figure float="1">
163	<mediaobject id="btree" xreflabel="">	163	<mediaobject id="btree" xreflabel="">
164	<imageobject role="pdf">	164	<imageobject role="pdf">
165	<imagedata fileref="images/btree.pdf" format="PDF" />	165	<imagedata fileref="images/btree.pdf" format="PDF" />
166	</imageobject>	166	</imageobject>
167		167
168	<imageobject role="html">	168	<imageobject role="html">
169	<imagedata fileref="images/btree.png" format="PNG" />	169	<imagedata fileref="images/btree.png" format="PNG" />
170	</imageobject>	170	</imageobject>
171		171
172	<imageobject role="fop">	172	<imageobject role="fop">
173	<imagedata fileref="images/btree.svg" format="SVG" />	173	<imagedata fileref="images/btree.svg" format="SVG" />
174	</imageobject>	174	</imageobject>
175	</mediaobject>	175	</mediaobject>
176		176
177	<title>B+tree containing keys ranging from 1 to 12.</title>	177	<title>B+tree containing keys ranging from 1 to 12.</title>
178	</figure>	178	</figure>
179	</section>	179	</section>
180	</chapter>	180	</chapter>

Subversion Repositories HelenOS-doc

(root)/design/trunk/src/ch_ds.xml – Rev 131 → 133