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. They serve like generic
    containers.
    </para>
   
    <section>
      <title>Lists</title>
      <para>
      HelenOS uses circular doubly linked lists to bind related data
      together. Lists are composed of an independent 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>
     
    </section>
 
    <section>
      <title>FIFO queues</title>
      <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>
    </section>
 
    <section>
      <title>Hash tables</title>
      <para>
      The kernel, as well as userspace, makes use of the hash table implementation with
      separate chaining. The implementation 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>
    </section>
 
    <section>
      <title>B+trees</title>
      <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>
    </section>
 
</chapter>
 

Rev 52	Rev 53
1	<?xml version="1.0" encoding="UTF-8"?>	1	<?xml version="1.0" encoding="UTF-8"?>
2		2
3	<chapter id="ds"><?dbhtml filename="ds.html"?>	3	<chapter id="ds"><?dbhtml filename="ds.html"?>
4	<title>Data structures</title>	4	<title>Data structures</title>
5		5
6	<para>	6	<para>
7	There is lots of data that either flows through various HelenOS subsystems	7	There is lots of data that either flows through various HelenOS subsystems
8	or is stored directly by them. Each subsystem uses its own data structures	8	or is stored directly by them. Each subsystem uses its own data structures
9	to represent the data. These data structures need to be kept	9	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
11	kernel, deploys several house keeping data types that are designed	11	kernel, deploys several house keeping data types that are designed
12	to faciliate managing other data structures. They serve like generic	12	to faciliate managing other data structures. They serve like generic
13	containers.	13	containers.
14	</para>	14	</para>
15		15
16	<section>	16	<section>
17	<title>Lists</title>	17	<title>Lists</title>
18	<para>	18	<para>
19	HelenOS uses circular doubly linked lists to bind related data	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	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	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	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	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	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	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	26	lists is justified by constant insertion and removal times at random positions
27	within the list.	27	within the list.
28	</para>	28	</para>
29		29
30	<para>	30	<para>
31	Lists are frequently used to implement FIFO behaviour (e.g. scheduler run queues	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	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	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	34	other hand, they are slower than in-array FIFOs and can be hardly used to implement
35	buffers.	35	buffers.
36	</para>	36	</para>
37		37
38	</section>	38	</section>
39		39
40	<section>	40	<section>
41	<title>FIFO queues</title>	41	<title>FIFO queues</title>
42	<para>	42	<para>
43	FIFO queues are implemented as either statically or dynamically allocated	43	FIFO queues are implemented as either statically or dynamically allocated
44	arrays<footnote><para>Depending on the array size.</para></footnote> of some generic type	44	arrays<footnote><para>Depending on the array size.</para></footnote> of some generic type
45	with two indices. The first index points to the head of the FIFO queue and the other	45	with two indices. The first index points to the head of the FIFO queue and the other
46	points to the tail thereof. There can be as many items in the FIFO as is the number	46	points to the tail thereof. There can be as many items in the FIFO as is the number
47	of elements in the array and no more. The indices are taken modulo size of the queue	47	of elements in the array and no more. The indices are taken modulo size of the queue
48	because as a consequence of insertions and deletions, the tail can have numericaly	48	because as a consequence of insertions and deletions, the tail can have numericaly
49	lower index than the head.	49	lower index than the head.
50	</para>	50	</para>
51		51
52	<para>	52	<para>
53	FIFO queues are used, for example, in ASID management code to store inactive ASIDs or	53	FIFO queues are used, for example, in ASID management code to store inactive ASIDs or
54	in userspace keyboard driver to buffer read characters.	54	in userspace keyboard driver to buffer read characters.
55	</para>	55	</para>
56	</section>	56	</section>
57		57
58	<section>	58	<section>
59	<title>Hash tables</title>	59	<title>Hash tables</title>
60	<para>	60	<para>
61	The kernel, as well as userspace, makes use of the hash table implementation with	61	The kernel, as well as userspace, makes use of the hash table implementation with
62	separate chaining. The implementation is very generic in that it forces the user	62	separate chaining. The implementation is very generic in that it forces the user
63	to supply methods for computing the hash index, comparing items with several keys	63	to supply methods for computing the hash index, comparing items against a set of keys
64	and the item removal callback function. Besides these virtual operations,	64	and the item removal callback function. Besides these virtual operations,
65	the hash table is composed of a dynamically allocated array of list heads that	65	the hash table is composed of a dynamically allocated array of list heads that
66	represent each chain, number of chains and the maximal number of keys.	66	represent each chain, number of chains and the maximal number of keys.
67	</para>	67	</para>
68	</section>	68	</section>
69		69
70	<section>	70	<section>
71	<title>B+trees</title>	71	<title>B+trees</title>
72	<para>	72	<para>
-		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
-		78	for easy storing, resizing and merging of disjunctive intervals.
73		-
74	</para>	79	</para>
75	</section>	80	</section>
76		81
77	</chapter>	82	</chapter>
78		83

Subversion Repositories HelenOS-doc

(root)/design/trunk/src/ch_ds.xml – Rev 52 → 53