60,7 → 60,7 |
<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 |
to supply methods for computing the hash index, comparing items against a set of 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. |
70,7 → 70,12 |
<section> |
<title>B+trees</title> |
<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 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 logaritmic search, insertion and deletion times and, thanks to the leaf-level list, |
provides fantastic means of walking the nodes containing data. Moreover, B+trees can be used |
for easy storing, resizing and merging of disjunctive intervals. |
</para> |
</section> |
|