Subversion Repositories HelenOS-doc

<?xml version="1.0" encoding="UTF-8"?>

<?xml version="1.0" encoding="UTF-8"?>

<chapter id="ds">

<chapter id="ds">

  <?dbhtml filename="ds.html"?>

  <?dbhtml filename="ds.html"?>

  <title>Data structures</title>

  <title>Data structures</title>

  <para>There is lots of data that either flows through various HelenOS

  <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

  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

  structures to represent the data. These data structures need to be kept

  somewhere. In order to work efficiently, HelenOS, and especially its kernel,

  somewhere. In order to work efficiently, HelenOS, and especially its kernel,

  deploys several house keeping data types that are designed to faciliate

  deploys several house keeping data types that are designed to faciliate

  managing other data structures. Most of them serve like generic

  managing other data structures. Most of them serve like generic

  containers.</para>

  containers.</para>

  <section>

  <section>

    <title>Lists</title>

    <title>Lists</title>

    <indexterm>

    <indexterm>

      <primary>linked list</primary>

      <primary>linked list</primary>

    </indexterm>

    </indexterm>

    <para>HelenOS uses doubly-circularly-linked lists to bind related data

    <para>HelenOS uses doubly-circularly-linked lists to bind related data

    together. Lists are composed of an independent sentinel node called head

    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

    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

    list. Adding items to a list thus doesn't require any further memory

    allocations. Head and each link then contains forward and backward

    allocations. Head and each link then contains forward and backward

    pointer. An empty list is composed of a sole head whose both pointers

    pointer. An empty list is composed of a sole head whose both pointers

    reference the head itself. The expense of two times bigger memory

    reference the head itself. The expense of two times bigger memory

    consumption as compared to memory consumption of singly linked lists is

    consumption as compared to memory consumption of singly linked lists is

    justified by constant insertion and removal times at random positions

    justified by constant insertion and removal times at random positions

    within the list.</para>

    within the list.</para>

    <para>Lists are frequently used to implement FIFO behaviour (e.g.

    <para>Lists are frequently used to implement FIFO behaviour (e.g.

    scheduler run queues or synchronization wait queues). Contrary to the FIFO

    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

    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

    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>

    in-array FIFOs and can be hardly used to implement buffers.</para>

  </section>

  </section>

  <section>

  <section>

    <title>FIFO queues</title>

    <title>FIFO queues</title>

    <indexterm>

    <indexterm>

      <primary>FIFO queue</primary>

      <primary>FIFO queue</primary>

    </indexterm>

    </indexterm>

    <para>FIFO queues are implemented as either statically or dynamically

    <para>FIFO queues are implemented as either statically or dynamically

    allocated arrays<footnote>

    allocated arrays<footnote>

        <para>Depending on the array size.</para>

        <para>Depending on the array size.</para>

      </footnote> of some generic type with two indices. The first index

      </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

    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

    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

    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

    the queue because as a consequence of insertions and deletions, the tail

    can have numericaly lower index than the head.</para>

    can have numericaly lower index than the head.</para>

    <para>FIFO queues are used, for example, in ASID management code to store

    <para>FIFO queues are used, for example, in ASID management code to store

    inactive ASIDs or in userspace keyboard driver to buffer read

    inactive ASIDs or in userspace keyboard driver to buffer read

    characters.</para>

    characters.</para>

    <figure>

    <figure>

      <mediaobject id="fifo" xreflabel="">

      <mediaobject id="fifo" xreflabel="">

        <imageobject role="html">

        <imageobject role="html">

          <imagedata fileref="images/fifo.png" format="PNG" />

          <imagedata fileref="images/fifo.png" format="PNG" />

        </imageobject>

        </imageobject>

        <imageobject role="fop">

        <imageobject role="fop">

          <imagedata fileref="images.vector/fifo.svg" format="SVG" />

          <imagedata fileref="images.vector/fifo.svg" format="SVG" />

        </imageobject>

        </imageobject>

      </mediaobject>

      </mediaobject>

      <title>FIFO queue showing the wrap around the end of the array.</title>

      <title>FIFO queue showing the wrap around the end of the array.</title>

    </figure>

    </figure>

  </section>

  </section>

    <title>Hash tables</title>

    <title>Hash tables</title>

    <indexterm>

    <indexterm>

      <primary>hash table</primary>

      <primary>hash table</primary>

    </indexterm>

    </indexterm>

    <para>The kernel, as well as userspace, provides hash table data type

    <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

    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,

    it forces the user to supply methods for computing the hash index,

    comparing items against a set of keys and the item removal callback

    comparing items against a set of keys and the item removal callback

    function. Besides these virtual operations, the hash table is composed of

    function. Besides these virtual operations, the hash table is composed of

    a dynamically allocated array of list heads that represent each chain,

    a dynamically allocated array of list heads that represent each chain,

    number of chains and the maximal number of keys.</para>

    number of chains and the maximal number of keys.</para>

  </section>

  </section>

  <section>

  <section>

    <title>Bitmaps</title>

    <title>Bitmaps</title>

    <indexterm>

    <indexterm>

      <primary>bitmap</primary>

      <primary>bitmap</primary>

    </indexterm>

    </indexterm>

    <para>Several bitmap operations such as clearing or setting consecutive

    <para>Several bitmap operations such as clearing or setting consecutive

    bit sequences as well as copying portions of one bitmap into another one

    bit sequences as well as copying portions of one bitmap into another one

    are supported.</para>

    are supported.</para>

  </section>

  </section>

  <section>

  <section>

    <title>B+trees</title>

    <title>B+trees</title>

    <indexterm>

    <indexterm>

      <primary>B-tree</primary>

      <primary>B-tree</primary>

    </indexterm>

    </indexterm>

    <para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in

    <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

    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

    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

    these nodes are linked together in a list. This data structure has

    logaritmic search, insertion and deletion times and, thanks to the

    logaritmic search, insertion and deletion times and, thanks to the

    leaf-level list, provides fantastic means of walking the nodes containing

    leaf-level list, provides fantastic means of walking the nodes containing

    data. Moreover, B+trees can be used for easy storing, resizing and merging

    data. Moreover, B+trees can be used for easy storing, resizing and merging

    of disjunctive intervals.</para>

    of disjunctive intervals.</para>

    <figure>

    <figure>

      <mediaobject id="btree" xreflabel="">

      <mediaobject id="btree" xreflabel="">

        <imageobject role="html">

        <imageobject role="html">

          <imagedata fileref="images/btree.png" format="PNG" />

          <imagedata fileref="images/btree.png" format="PNG" />

        </imageobject>

        </imageobject>

        <imageobject role="fop">

        <imageobject role="fop">

          <imagedata fileref="images.vector/btree.svg" format="SVG" />

          <imagedata fileref="images.vector/btree.svg" format="SVG" />

        </imageobject>

        </imageobject>

      </mediaobject>

      </mediaobject>

      <title>B+tree containing keys ranging from 1 to 12.</title>

      <title>B+tree containing keys ranging from 1 to 12.</title>

    </figure>

    </figure>

  </section>

  </section>

</chapter>

</chapter>