OSDN Git Service

* doc/xml/manual/bitmap_allocator.xml: Fix typos.
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / doc / xml / manual / bitmap_allocator.xml
index 6f1b26b..300cbab 100644 (file)
@@ -1,7 +1,8 @@
-<sect1 id="manual.ext.allocator.bitmap" xreflabel="bitmap_allocator">
+<section xmlns="http://docbook.org/ns/docbook" version="5.0" 
+        xml:id="manual.ext.allocator.bitmap" xreflabel="bitmap_allocator">
 <?dbhtml filename="bitmap_allocator.html"?>
-<sect1info>
+
+<info><title>bitmap_allocator</title>
   <keywordset>
     <keyword>
       ISO C++
       allocator
     </keyword>
   </keywordset>
-</sect1info>
+</info>
+
 
-<title>bitmap_allocator</title>
 
 <para>
 </para>
 
-<sect2 id="allocator.bitmap.design">
-<title>Design</title>
+<section xml:id="allocator.bitmap.design"><info><title>Design</title></info>
+
 
   <para>
     As this name suggests, this allocator uses a bit-map to keep track
-    of the used and unused memory locations for it's book-keeping
+    of the used and unused memory locations for its book-keeping
     purposes.
   </para>
   <para>
     layer.
   </para>
 
-</sect2>
+</section>
 
-<sect2 id="allocator.bitmap.impl">
-<title>Implementation</title>
+<section xml:id="allocator.bitmap.impl"><info><title>Implementation</title></info>
 
-<sect3 id="bitmap.impl.free_list_store" xreflabel="Free List Store">
-  <title>Free List Store</title>
+
+<section xml:id="bitmap.impl.free_list_store" xreflabel="Free List Store"><info><title>Free List Store</title></info>
+  
 
   <para>
     The Free List Store (referred to as FLS for the remaining part of this
@@ -81,9 +82,9 @@
     the search would go up given an increasing size, for 64 entries
     however, lg(64) == 6 comparisons are enough to locate the correct
     free list if it exists.
-  </para>  
+  </para>
   <para>
-    Suppose the free list size has reached it's threshold, then the
+    Suppose the free list size has reached its threshold, then the
     largest block from among those in the list and the new block will
     be selected and given back to the OS. This is done because it
     reduces external fragmentation, and allows the OS to use the
@@ -121,10 +122,10 @@ else return false.</para></listitem>
     Currently, (3) is being used with a value of 36% Maximum wastage per
     Super Block.
   </para>
-</sect3>
+</section>
 
-<sect3 id="bitmap.impl.super_block" xreflabel="Super Block">
-  <title>Super Block</title>
+<section xml:id="bitmap.impl.super_block" xreflabel="Super Block"><info><title>Super Block</title></info>
+  
 
   <para>
     A super block is the block of memory acquired from the FLS from
@@ -144,10 +145,10 @@ else return false.</para></listitem>
     getting / returning Super Bocks to and from the OS using operator new
     as defined by the C++ standard.
   </para>
-</sect3>
+</section>
 
-<sect3 id="bitmap.impl.super_block_data" xreflabel="Super Block Data">
-  <title>Super Block Data Layout</title>
+<section xml:id="bitmap.impl.super_block_data" xreflabel="Super Block Data"><info><title>Super Block Data Layout</title></info>
+  
   <para>
     Each Super Block will be of some size that is a multiple of the
     number of Bits Per Block. Typically, this value is chosen as
@@ -165,14 +166,15 @@ else return false.</para></listitem>
     (assume a 32-bit system where, size_t is a 32-bit entity).
   </para>
 
-<table frame='all'>
+<table frame="all">
 <title>Bitmap Allocator Memory Map</title>
-<tgroup cols='5' align='left' colsep='1' rowsep='1'>
-<colspec colname='c1'></colspec>
-<colspec colname='c2'></colspec>
-<colspec colname='c3'></colspec>
-<colspec colname='c4'></colspec>
-<colspec colname='c5'></colspec>
+
+<tgroup cols="5" align="left" colsep="1" rowsep="1">
+<colspec colname="c1"/>
+<colspec colname="c2"/>
+<colspec colname="c3"/>
+<colspec colname="c4"/>
+<colspec colname="c5"/>
 
 <tbody>
   <row>
@@ -219,11 +221,11 @@ else return false.</para></listitem>
     x 2,
     which is 8-bytes, or 2 x sizeof(size_t).
   </para>
-</sect3>
+</section>
+
+<section xml:id="bitmap.impl.max_wasted" xreflabel="Max Wasted Percentage"><info><title>Maximum Wasted Percentage</title></info>
+  
 
-<sect3 id="bitmap.impl.max_wasted" xreflabel="Max Wasted Percentage">
-  <title>Maximum Wasted Percentage</title>
   <para>
     This has nothing to do with the algorithm per-se,
     only with some vales that must be chosen correctly to ensure that the
@@ -260,10 +262,10 @@ For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524%
     create a function that returns the Max_Wastage_Percentage for us to use.
   </para>
 
-</sect3>
+</section>
 
-<sect3 id="bitmap.impl.allocate" xreflabel="Allocate">
-  <title><function>allocate</function></title>
+<section xml:id="bitmap.impl.allocate" xreflabel="Allocate"><info><title><function>allocate</function></title></info>
+  
 
   <para>
     The allocate function is specialized for single object allocation
@@ -328,12 +330,12 @@ For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524%
        <listitem>
          <para>
            Gets more memory from the Global Free List of the Required
-           size.  
+           size.
          </para>
        </listitem>
       <listitem>
       <para>
-      Adjusts the size for the next call to itself. 
+      Adjusts the size for the next call to itself.
       </para>
       </listitem>
       <listitem>
@@ -344,7 +346,7 @@ For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524%
       <listitem>
        <para>
        Sets the use count for that super-block just allocated to 0
-       (zero).  
+       (zero).
       </para>
       </listitem>
       <listitem>
@@ -353,7 +355,7 @@ For map/multimap: k = 12, and c = 4 (int and double), we get: 37.524%
          for the allocator. If the invariant is maintained, we are
          sure that all is well. Now, the same process is applied on
          the newly acquired free blocks, which are dispatched
-         accordingly.  
+         accordingly.
       </para>
       </listitem>
     </itemizedlist>
@@ -366,10 +368,10 @@ combination of the next-fit and first-fit algorithm optimized ONLY for
 single object allocations.
 </para>
 
-</sect3>
+</section>
 
-<sect3 id="bitmap.impl.deallocate" xreflabel="Deallocate">
-  <title><function>deallocate</function></title>
+<section xml:id="bitmap.impl.deallocate" xreflabel="Deallocate"><info><title><function>deallocate</function></title></info>
+  
   <para>
     The deallocate function again is specialized for single objects ONLY.
     For all n belonging to &gt; 1, the operator delete is called without
@@ -378,7 +380,7 @@ single object allocations.
   <para>
     However for n == 1, a series of steps are performed:
   </para>
-  
+
   <orderedlist>
     <listitem><para>
       We first need to locate that super-block which holds the memory
@@ -410,13 +412,13 @@ single object allocations.
     invariant is maintained by making sure that _S_last_request and
     _S_last_dealloc_index point to valid locations within the vector.
   </para>
-</sect3>
+</section>
 
-<sect3 id="bitmap.impl.questions" xreflabel="Questions">
-  <title>Questions</title>
+<section xml:id="bitmap.impl.questions" xreflabel="Questions"><info><title>Questions</title></info>
+  
 
-  <sect4 id="bitmap.impl.question.1" xreflabel="Question 1">
-    <title>1</title>
+  <section xml:id="bitmap.impl.question.1" xreflabel="Question 1"><info><title>1</title></info>
+    
     <para>
 Q1) The "Data Layout" section is
 cryptic. I have no idea of what you are trying to say. Layout of what?
@@ -429,10 +431,10 @@ general formula for calculating the size of a super block is
 32 x sizeof(value_type) x 2^n, where n ranges from 0 to 32 for 32-bit
 systems.
     </para>
-  </sect4>
+  </section>
 
-  <sect4 id="bitmap.impl.question.2" xreflabel="Question 2">
-    <title>2</title>
+  <section xml:id="bitmap.impl.question.2" xreflabel="Question 2"><info><title>2</title></info>
+    
     <para>
       And since I just mentioned the
 term `each bitmap', what in the world is meant by it? What does each
@@ -452,10 +454,10 @@ Block a bitmap as well?
       whose exact number for a super-block of a given size I have just
       mentioned.
     </para>
-  </sect4>
+  </section>
 
-  <sect4 id="bitmap.impl.question.3" xreflabel="Question 3">
-    <title>3</title>
+  <section xml:id="bitmap.impl.question.3" xreflabel="Question 3"><info><title>3</title></info>
+    
     <para>
       How do the allocate and deallocate functions work in regard to
       bitmaps?
@@ -492,11 +494,11 @@ Block a bitmap as well?
       The bit-map now looks like this:
       1111111111111111111111111111111111111111111111111111111111111110
     </para>
-  </sect4>
-</sect3>
+  </section>
+</section>
 
-<sect3 id="bitmap.impl.locality" xreflabel="Locality">
-  <title>Locality</title>
+<section xml:id="bitmap.impl.locality" xreflabel="Locality"><info><title>Locality</title></info>
+  
   <para>
     Another issue would be whether to keep the all bitmaps in a
     separate area in memory, or to keep them near the actual blocks
@@ -504,10 +506,10 @@ Block a bitmap as well?
     testing, I've decided to keep these bitmaps close to the actual
     blocks. This will help in 2 ways.
   </para>
-  
+
   <orderedlist>
   <listitem><para>Constant time access for the bitmap themselves, since no kind of
-look up will be needed to find the correct bitmap list or it's
+look up will be needed to find the correct bitmap list or its
 equivalent.</para></listitem>
   <listitem><para>And also this would preserve the cache as far as possible.</para></listitem>
   </orderedlist>
@@ -522,10 +524,10 @@ equivalent.</para></listitem>
     single object allocations, though it preserves the locality of blocks
     very well when they are returned back to the allocator.
   </para>
-</sect3>
+</section>
 
-<sect3 id="bitmap.impl.grow_policy" xreflabel="Grow Policy">
-  <title>Overhead and Grow Policy</title>
+<section xml:id="bitmap.impl.grow_policy" xreflabel="Grow Policy"><info><title>Overhead and Grow Policy</title></info>
+  
   <para>
     Expected overhead per block would be 1 bit in memory. Also, once
     the address of the free list has been found, the cost for
@@ -552,8 +554,8 @@ equivalent.</para></listitem>
     which can fit exactly in a CPU register. Hence, the term given is
     exponential growth of the internal pool.
   </para>
-</sect3>
+</section>
+
+</section>
 
-</sect2>
-</sect1>
+</section>