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