HelenOS-docHelenOSHelenOS-historic

Català-Valencià – Catalan中文 – Chinese (Simplified)中文 – Chinese (Traditional)Česky – CzechDansk – DanishNederlands – DutchEnglish – EnglishSuomi – FinnishFrançais – FrenchDeutsch – Germanעברית – Hebrewहिंदी – HindiMagyar – HungarianBahasa Indonesia – IndonesianItaliano – Italian日本語 – Japanese한국어 – KoreanМакедонски – Macedonianमराठी – MarathiNorsk – NorwegianPolski – PolishPortuguês – PortuguesePortuguês – Portuguese (Brazil)Русский – RussianSlovenčina – SlovakSlovenščina – SlovenianEspañol – SpanishSvenska – SwedishTürkçe – TurkishУкраїнська – UkrainianOëzbekcha – Uzbek

Compare Revisions

• This comparison shows the changes necessary to convert path

  → /design/trunk/src/ch_ds.xml @ 72

  → /design/trunk/src/ch_ds.xml @ 73

  ↔ Reverse comparison

• Compare Path:	Rev

  With Path:	Rev

Ignore whitespace Rev 72 → Rev 73

/design/trunk/src/ch_ds.xml
15,6 → 15,10
<section>
<title>Lists</title>
<indexterm>
<primary>linked list</primary>
</indexterm>
<para>HelenOS uses doubly-circularly-linked lists to bind related data
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
36,6 → 40,10
<section>
<title>FIFO queues</title>
<indexterm>
<primary>FIFO queue</primary>
</indexterm>
<para>FIFO queues are implemented as either statically or dynamically
allocated arrays<footnote>
<para>Depending on the array size.</para>
51,24 → 59,27
characters.</para>
<figure>
<mediaobject id="fifo" xreflabel="">
<imageobject role="html">
<imagedata fileref="images/fifo.png" format="PNG" />
</imageobject>
<imageobject role="fop">
<imagedata fileref="images.vector/fifo.svg" format="SVG" />
</imageobject>
</mediaobject>
<title>FIFO queue showing the wrap around the end of the array.</title>
<mediaobject id="fifo" xreflabel="">
<imageobject role="html">
<imagedata fileref="images/fifo.png" format="PNG" />
</imageobject>
<imageobject role="fop">
<imagedata fileref="images.vector/fifo.svg" format="SVG" />
</imageobject>
</mediaobject>
<title>FIFO queue showing the wrap around the end of the array.</title>
</figure>
</section>
<section>
<title>Hash tables</title>
<indexterm>
<primary>hash table</primary>
</indexterm>
<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
it forces the user to supply methods for computing the hash index,
81,6 → 92,10
<section>
<title>Bitmaps</title>
<indexterm>
<primary>bitmap</primary>
</indexterm>
<para>Several bitmap operations such as clearing or setting consecutive
bit sequences as well as copying portions of one bitmap into another one
are supported.</para>
89,6 → 104,10
<section>
<title>B+trees</title>
<indexterm>
<primary>B-tree</primary>
</indexterm>
<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
99,19 → 118,17
of disjunctive intervals.</para>
<figure>
<mediaobject id="btree" xreflabel="">
<imageobject role="html">
<imagedata fileref="images/btree.png" format="PNG" />
</imageobject>
<imageobject role="fop">
<imagedata fileref="images.vector/btree.svg" format="SVG" />
</imageobject>
<mediaobject id="btree" xreflabel="">
<imageobject role="html">
<imagedata fileref="images/btree.png" format="PNG" />
</imageobject>
</mediaobject>
<title>B+tree containing keys ranging from 1 to 12.</title>
<imageobject role="fop">
<imagedata fileref="images.vector/btree.svg" format="SVG" />
</imageobject>
</mediaobject>
<title>B+tree containing keys ranging from 1 to 12.</title>
</figure>
</section>
</chapter>