Subversion Repositories HelenOS-doc

Rev

Rev 95 | Rev 105 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. <?xml version="1.0" encoding="UTF-8"?>
  2. <chapter id="ds">
  3.   <?dbhtml filename="ds.html"?>
  4.  
  5.   <title>Data structures</title>
  6.  
  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
  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,
  11.   deploys several house keeping data types that are designed to faciliate
  12.   managing other data structures. Most of them serve like generic
  13.   containers.</para>
  14.  
  15.   <section>
  16.     <title>Lists</title>
  17.  
  18.     <indexterm>
  19.       <primary>linked list</primary>
  20.     </indexterm>
  21.  
  22.     <para>HelenOS uses doubly-circularly-linked lists to bind related data
  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
  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
  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
  29.    consumption as compared to memory consumption of singly linked lists is
  30.    justified by constant insertion and removal times at random positions
  31.    within the list.</para>
  32.  
  33.    <para>Lists are frequently used to implement FIFO behaviour (e.g.
  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
  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>
  38.  
  39.     <figure>
  40.       <mediaobject id="list" xreflabel="">
  41.         <imageobject role="pdf">
  42.           <imagedata fileref="images.vector/list.pdf" format="PDF" />
  43.         </imageobject>
  44.  
  45.         <imageobject role="html">
  46.           <imagedata fileref="images/list.png" format="PNG" />
  47.         </imageobject>
  48.  
  49.         <imageobject role="fop">
  50.           <imagedata fileref="images.vector/list.svg" format="SVG" />
  51.         </imageobject>
  52.       </mediaobject>
  53.  
  54.       <title>Doubly-circularly-linked list</title>
  55.     </figure>
  56.   </section>
  57.  
  58.   <section>
  59.     <title>FIFO queues</title>
  60.  
  61.     <indexterm>
  62.       <primary>FIFO queue</primary>
  63.     </indexterm>
  64.  
  65.     <para>FIFO queues are implemented as either statically or dynamically
  66.     allocated arrays<footnote>
  67.         <para>Depending on the array size.</para>
  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
  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
  72.     the queue because as a consequence of insertions and deletions, the tail
  73.     can have numericaly lower index than the head.</para>
  74.  
  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
  77.     characters.</para>
  78.  
  79.     <figure>
  80.       <mediaobject id="fifo" xreflabel="">
  81.         <imageobject role="pdf">
  82.           <imagedata fileref="images.vector/fifo.pdf" format="PDF" />
  83.         </imageobject>
  84.  
  85.         <imageobject role="html">
  86.           <imagedata fileref="images/fifo.png" format="PNG" />
  87.         </imageobject>
  88.  
  89.         <imageobject role="fop">
  90.           <imagedata fileref="images.vector/fifo.svg" format="SVG" />
  91.         </imageobject>
  92.       </mediaobject>
  93.  
  94.       <title>FIFO queue showing the wrap around the end of the array.</title>
  95.     </figure>
  96.   </section>
  97.  
  98.   <section id="hashtables">
  99.     <title>Hash tables</title>
  100.  
  101.     <indexterm>
  102.       <primary>hash table</primary>
  103.     </indexterm>
  104.  
  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
  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
  109.     function. Besides these virtual operations, the hash table is composed of
  110.     a dynamically allocated array of list heads that represent each chain,
  111.     number of chains and the maximal number of keys.</para>
  112.  
  113.     <figure>
  114.       <mediaobject id="hash" xreflabel="">
  115.         <imageobject role="pdf">
  116.           <imagedata fileref="images.vector/hash.pdf" format="PDF" />
  117.         </imageobject>
  118.  
  119.         <imageobject role="html">
  120.           <imagedata fileref="images/hash.png" format="PNG" />
  121.         </imageobject>
  122.  
  123.         <imageobject role="fop">
  124.           <imagedata fileref="images.vector/hash.svg" format="SVG" />
  125.         </imageobject>
  126.       </mediaobject>
  127.  
  128.       <title>Generic hash table.</title>
  129.     </figure>
  130.  
  131.   </section>
  132.  
  133.   <section>
  134.     <title>Bitmaps</title>
  135.  
  136.     <indexterm>
  137.       <primary>bitmap</primary>
  138.     </indexterm>
  139.  
  140.     <para>Several bitmap operations such as clearing or setting consecutive
  141.     bit sequences as well as copying portions of one bitmap into another one
  142.     are supported.</para>
  143.   </section>
  144.  
  145.   <section>
  146.     <title>B+trees</title>
  147.  
  148.     <indexterm>
  149.       <primary>B-trees</primary>
  150.       <secondary> - B+tree</secondary>
  151.     </indexterm>
  152.  
  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
  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
  157.     logaritmic search, insertion and deletion times and, thanks to the
  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
  160.     of disjunctive intervals.</para>
  161.  
  162.     <figure>
  163.       <mediaobject id="btree" xreflabel="">
  164.         <imageobject role="pdf">
  165.           <imagedata fileref="images.vector/btree.pdf" format="PDF" />
  166.         </imageobject>
  167.  
  168.         <imageobject role="html">
  169.           <imagedata fileref="images/btree.png" format="PNG" />
  170.         </imageobject>
  171.  
  172.         <imageobject role="fop">
  173.           <imagedata fileref="images.vector/btree.svg" format="SVG" />
  174.         </imageobject>
  175.       </mediaobject>
  176.  
  177.       <title>B+tree containing keys ranging from 1 to 12.</title>
  178.     </figure>
  179.   </section>
  180. </chapter>