Subversion Repositories HelenOS-doc

Rev

Rev 52 | Rev 59 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 52 Rev 53
Line 58... Line 58...
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>