Subversion Repositories HelenOS-doc

Rev

Rev 53 | 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.  
  3. <chapter id="ds"><?dbhtml filename="ds.html"?>
  4.     <title>Data structures</title>
  5.    
  6.     <para>
  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
  9.     to represent the data. These data structures need to be kept
  10.     somewhere. In order to work efficiently, HelenOS, and especially its
  11.     kernel, deploys several house keeping data types that are designed
  12.     to faciliate managing other data structures. They serve like generic
  13.     containers.
  14.     </para>
  15.    
  16.     <section>
  17.       <title>Lists</title>
  18.       <para>
  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
  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
  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
  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
  27.      within the list.
  28.      </para>
  29.      
  30.      <para>
  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
  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
  35.       buffers.
  36.       </para>
  37.      
  38.     </section>
  39.  
  40.     <section>
  41.       <title>FIFO queues</title>
  42.       <para>
  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
  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
  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
  49.       lower index than the head.
  50.       </para>
  51.      
  52.       <para>
  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.
  55.       </para>
  56.     </section>
  57.  
  58.     <section>
  59.       <title>Hash tables</title>
  60.       <para>
  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
  63.       to supply methods for computing the hash index, comparing items with several keys
  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
  66.       represent each chain, number of chains and the maximal number of keys.
  67.       </para>
  68.     </section>
  69.  
  70.     <section>
  71.       <title>B+trees</title>
  72.       <para>
  73.      
  74.       </para>
  75.     </section>
  76.  
  77. </chapter>
  78.