Subversion Repositories HelenOS-doc

<?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 with several 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>

      </para>

    </section>

</chapter>