l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.7/doc/html/manual/bk01pt03ch20s04.html

   1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
   3 <html xmlns="http://www.w3.org/1999/xhtml"><head><title>Single Thread Example</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"/><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      allocator&#10;    "/><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      library&#10;    "/><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      runtime&#10;    , &#10;      library&#10;    "/><link rel="home" href="../index.html" title="The GNU C++ Library"/><link rel="up" href="mt_allocator.html" title="Chapter 20. The mt_allocator"/><link rel="prev" href="bk01pt03ch20s03.html" title="Implementation"/><link rel="next" href="bk01pt03ch20s05.html" title="Multiple Thread Example"/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Single Thread Example</th></tr><tr><td align="left"><a accesskey="p" href="bk01pt03ch20s03.html">Prev</a> </td><th width="60%" align="center">Chapter 20. The mt_allocator</th><td align="right"> <a accesskey="n" href="bk01pt03ch20s05.html">Next</a></td></tr></table><hr/></div><div class="section" title="Single Thread Example"><div class="titlepage"><div><div><h2 class="title"><a id="allocator.mt.example_single"/>Single Thread Example</h2></div></div></div><p>
   4 Let's start by describing how the data on a freelist is laid out in memory.
   5 This is the first two blocks in freelist for thread id 3 in bin 3 (8 bytes):
   6 </p><pre class="programlisting">
   7 +----------------+
   8 | next* ---------|--+  (_S_bin[ 3 ].first[ 3 ] points here)
   9 |                |  |
  10 |                |  |
  11 |                |  |
  12 +----------------+  |
  13 | thread_id = 3  |  |
  14 |                |  |
  15 |                |  |
  16 |                |  |
  17 +----------------+  |
  18 | DATA           |  |  (A pointer to here is what is returned to the
  19 |                |  |   the application when needed)
  20 |                |  |
  21 |                |  |
  22 |                |  |
  23 |                |  |
  24 |                |  |
  25 |                |  |
  26 +----------------+  |
  27 +----------------+  |
  28 | next*          |&lt;-+  (If next == NULL it's the last one on the list)
  29 |                |
  30 |                |
  31 |                |
  32 +----------------+
  33 | thread_id = 3  |
  34 |                |
  35 |                |
  36 |                |
  37 +----------------+
  38 | DATA           |
  39 |                |
  40 |                |
  41 |                |
  42 |                |
  43 |                |
  44 |                |
  45 |                |
  46 +----------------+
  47 </pre><p>
  48 With this in mind we simplify things a bit for a while and say that there is
  49 only one thread (a ST application). In this case all operations are made to
  50 what is referred to as the global pool - thread id 0 (No thread may be
  51 assigned this id since they span from 1 to _S_max_threads in a MT application).
  52 </p><p>
  53 When the application requests memory (calling allocate()) we first look at the
  54 requested size and if this is &gt; _S_max_bytes we call new() directly and return.
  55 </p><p>
  56 If the requested size is within limits we start by finding out from which
  57 bin we should serve this request by looking in _S_binmap.
  58 </p><p>
  59 A quick look at _S_bin[ bin ].first[ 0 ] tells us if there are any blocks of
  60 this size on the freelist (0). If this is not NULL - fine, just remove the
  61 block that _S_bin[ bin ].first[ 0 ] points to from the list,
  62 update _S_bin[ bin ].first[ 0 ] and return a pointer to that blocks data.
  63 </p><p>
  64 If the freelist is empty (the pointer is NULL) we must get memory from the
  65 system and build us a freelist within this memory. All requests for new memory
  66 is made in chunks of _S_chunk_size. Knowing the size of a block_record and
  67 the bytes that this bin stores we then calculate how many blocks we can create
  68 within this chunk, build the list, remove the first block, update the pointer
  69 (_S_bin[ bin ].first[ 0 ]) and return a pointer to that blocks data.
  70 </p><p>
  71 Deallocation is equally simple; the pointer is casted back to a block_record
  72 pointer, lookup which bin to use based on the size, add the block to the front
  73 of the global freelist and update the pointer as needed
  74 (_S_bin[ bin ].first[ 0 ]).
  75 </p><p>
  76 The decision to add deallocated blocks to the front of the freelist was made
  77 after a set of performance measurements that showed that this is roughly 10%
  78 faster than maintaining a set of "last pointers" as well.
  79 </p></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td align="left"><a accesskey="p" href="bk01pt03ch20s03.html">Prev</a> </td><td align="center"><a accesskey="u" href="mt_allocator.html">Up</a></td><td align="right"> <a accesskey="n" href="bk01pt03ch20s05.html">Next</a></td></tr><tr><td align="left" valign="top">Implementation </td><td align="center"><a accesskey="h" href="../index.html">Home</a></td><td align="right" valign="top"> Multiple Thread Example</td></tr></table></div></body></html>