1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Pool in More Depth</title> 5<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../index.html" title="Boost.Pool"> 8<link rel="up" href="../pool.html" title="Introduction and Overview"> 9<link rel="prev" href="interfaces.html" title="Boost Pool Interfaces - What interfaces are provided and when to use each one."> 10<link rel="next" href="../../boost_pool_c___reference.html" title="Boost.Pool C++ Reference"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="interfaces.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../pool.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../../boost_pool_c___reference.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h3 class="title"> 27<a name="boost_pool.pool.pooling"></a><a class="link" href="pooling.html" title="Pool in More Depth">Pool in More Depth</a> 28</h3></div></div></div> 29<div class="toc"><dl class="toc"> 30<dt><span class="section"><a href="pooling.html#boost_pool.pool.pooling.concepts">Basic ideas behind 31 pooling</a></span></dt> 32<dt><span class="section"><a href="pooling.html#boost_pool.pool.pooling.simple">Simple Segregated Storage</a></span></dt> 33<dt><span class="section"><a href="pooling.html#boost_pool.pool.pooling.alignment">Guaranteeing Alignment 34 - How we guarantee alignment portably.</a></span></dt> 35<dd><dl><dt><span class="section"><a href="pooling.html#boost_pool.pool.pooling.alignment.chunks">How Contiguous 36 Chunks are Handled</a></span></dt></dl></dd> 37<dt><span class="section"><a href="pooling.html#boost_pool.pool.pooling.simple_segregated">Simple Segregated 38 Storage (Not for the faint of heart - Embedded programmers only!)</a></span></dt> 39<dt><span class="section"><a href="pooling.html#boost_pool.pool.pooling.user_allocator">The UserAllocator 40 Concept</a></span></dt> 41</dl></div> 42<div class="section"> 43<div class="titlepage"><div><div><h4 class="title"> 44<a name="boost_pool.pool.pooling.concepts"></a><a class="link" href="pooling.html#boost_pool.pool.pooling.concepts" title="Basic ideas behind pooling">Basic ideas behind 45 pooling</a> 46</h4></div></div></div> 47<p> 48 <span class="emphasis"><em>Dynamic memory allocation has been a fundamental part of most 49 computer systems since roughly 1960...</em></span> <a class="link" href="../appendices/references.html#ref1">1</a> 50 </p> 51<p> 52 Everyone uses dynamic memory allocation. If you have ever called malloc 53 or new, then you have used dynamic memory allocation. Most programmers 54 have a tendency to treat the heap as a <span class="quote">“<span class="quote">magic bag"</span>”</span>: 55 we ask it for memory, and it magically creates some for us. Sometimes we 56 run into problems because the heap is not magic. 57 </p> 58<p> 59 The heap is limited. Even on large systems (i.e., not embedded) with huge 60 amounts of virtual memory available, there is a limit. Everyone is aware 61 of the physical limit, but there is a more subtle, 'virtual' limit, that 62 limit at which your program (or the entire system) slows down due to the 63 use of virtual memory. This virtual limit is much closer to your program 64 than the physical limit, especially if you are running on a multitasking 65 system. Therefore, when running on a large system, it is considered <span class="emphasis"><em>nice</em></span> 66 to make your program use as few resources as necessary, and release them 67 as soon as possible. When using an embedded system, programmers usually 68 have no memory to waste. 69 </p> 70<p> 71 The heap is complicated. It has to satisfy any type of memory request, 72 for any size, and do it fast. The common approaches to memory management 73 have to do with splitting the memory up into portions, and keeping them 74 ordered by size in some sort of a tree or list structure. Add in other 75 factors, such as locality and estimating lifetime, and heaps quickly become 76 very complicated. So complicated, in fact, that there is no known <span class="emphasis"><em>perfect</em></span> 77 answer to the problem of how to do dynamic memory allocation. The diagrams 78 below illustrate how most common memory managers work: for each chunk of 79 memory, it uses part of that memory to maintain its internal tree or list 80 structure. Even when a chunk is malloc'ed out to a program, the memory 81 manager must <span class="emphasis"><em>save</em></span> some information in it - usually 82 just its size. Then, when the block is free'd, the memory manager can easily 83 tell how large it is. 84 </p> 85<p> 86 <span class="inlinemediaobject"><img src="../images/../../../images/pc1.png" align="middle"></span> 87 </p> 88<p> 89 <span class="inlinemediaobject"><img src="../images/../../../images/pc2.png" align="middle"></span> 90 </p> 91<h6> 92<a name="boost_pool.pool.pooling.concepts.h0"></a> 93 <span class="phrase"><a name="boost_pool.pool.pooling.concepts.dynamic_memory_allocation_is_often_inefficient"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.concepts.dynamic_memory_allocation_is_often_inefficient">Dynamic 94 memory allocation is often inefficient</a> 95 </h6> 96<p> 97 Because of the complication of dynamic memory allocation, it is often inefficient 98 in terms of time and/or space. Most memory allocation algorithms store 99 some form of information with each memory block, either the block size 100 or some relational information, such as its position in the internal tree 101 or list structure. It is common for such <span class="emphasis"><em>header fields</em></span> 102 to take up one machine word in a block that is being used by the program. 103 The obvious disadvantage, then, is when small objects are dynamically allocated. 104 For example, if ints were dynamically allocated, then automatically the 105 algorithm will reserve space for the header fields as well, and we end 106 up with a 50% waste of memory. Of course, this is a worst-case scenario. 107 However, more modern programs are making use of small objects on the heap; 108 and that is making this problem more and more apparent. Wilson et. al. 109 state that an average-case memory overhead is about ten to twenty percent<a href="../../#ref2" target="_top">2</a>. This memory overhead will grow higher as more programs 110 use more smaller objects. It is this memory overhead that brings programs 111 closer to the virtual limit. 112 </p> 113<p> 114 In larger systems, the memory overhead is not as big of a problem (compared 115 to the amount of time it would take to work around it), and thus is often 116 ignored. However, there are situations where many allocations and/or deallocations 117 of smaller objects are taking place as part of a time-critical algorithm, 118 and in these situations, the system-supplied memory allocator is often 119 too slow. 120 </p> 121<p> 122 Simple segregated storage addresses both of these issues. Almost all memory 123 overhead is done away with, and all allocations can take place in a small 124 amount of (amortized) constant time. However, this is done at the loss 125 of generality; simple segregated storage only can allocate memory chunks 126 of a single size. 127 </p> 128</div> 129<div class="section"> 130<div class="titlepage"><div><div><h4 class="title"> 131<a name="boost_pool.pool.pooling.simple"></a><a class="link" href="pooling.html#boost_pool.pool.pooling.simple" title="Simple Segregated Storage">Simple Segregated Storage</a> 132</h4></div></div></div> 133<p> 134 Simple Segregated Storage is the basic idea behind the Boost Pool library. 135 Simple Segregated Storage is the simplest, and probably the fastest, memory 136 allocation/deallocation algorithm. It begins by partitioning a memory block 137 into fixed-size chunks. Where the block comes from is not important until 138 implementation time. A Pool is some object that uses Simple Segregated 139 Storage in this fashion. To illustrate: 140 </p> 141<p> 142 <span class="inlinemediaobject"><img src="../images/../../../images/pc3.png" align="middle"></span> 143 </p> 144<p> 145 Each of the chunks in any given block are always the same size. This is 146 the fundamental restriction of Simple Segregated Storage: you cannot ask 147 for chunks of different sizes. For example, you cannot ask a Pool of integers 148 for a character, or a Pool of characters for an integer (assuming that 149 characters and integers are different sizes). 150 </p> 151<p> 152 Simple Segregated Storage works by interleaving a free list within the 153 unused chunks. For example: 154 </p> 155<p> 156 <span class="inlinemediaobject"><img src="../images/../../../images/pc4.png" align="middle"></span> 157 </p> 158<p> 159 By interleaving the free list inside the chunks, each Simple Segregated 160 Storage only has the overhead of a single pointer (the pointer to the first 161 element in the list). It has no memory overhead for chunks that are in 162 use by the process. 163 </p> 164<p> 165 Simple Segregated Storage is also extremely fast. In the simplest case, 166 memory allocation is merely removing the first chunk from the free list, 167 a O(1) operation. In the case where the free list is empty, another block 168 may have to be acquired and partitioned, which would result in an amortized 169 O(1) time. Memory deallocation may be as simple as adding that chunk to 170 the front of the free list, a O(1) operation. However, more complicated 171 uses of Simple Segregated Storage may require a sorted free list, which 172 makes deallocation O(N). 173 </p> 174<p> 175 <span class="inlinemediaobject"><img src="../images/../../../images/pc5.png" align="middle"></span> 176 </p> 177<p> 178 Simple Segregated Storage gives faster execution and less memory overhead 179 than a system-supplied allocator, but at the loss of generality. A good 180 place to use a Pool is in situations where many (noncontiguous) small objects 181 may be allocated on the heap, or if allocation and deallocation of the 182 same-sized objects happens repeatedly. 183 </p> 184</div> 185<div class="section"> 186<div class="titlepage"><div><div><h4 class="title"> 187<a name="boost_pool.pool.pooling.alignment"></a><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment" title="Guaranteeing Alignment - How we guarantee alignment portably.">Guaranteeing Alignment 188 - How we guarantee alignment portably.</a> 189</h4></div></div></div> 190<div class="toc"><dl class="toc"><dt><span class="section"><a href="pooling.html#boost_pool.pool.pooling.alignment.chunks">How Contiguous 191 Chunks are Handled</a></span></dt></dl></div> 192<h5> 193<a name="boost_pool.pool.pooling.alignment.h0"></a> 194 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.terminology"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.terminology">Terminology</a> 195 </h5> 196<p> 197 Review the <a class="link" href="pooling.html#boost_pool.pool.pooling.concepts" title="Basic ideas behind pooling">concepts</a> 198 section if you are not already familiar with it. Remember that block is 199 a contiguous section of memory, which is partitioned or segregated into 200 fixed-size chunks. These chunks are what are allocated and deallocated 201 by the user. 202 </p> 203<h5> 204<a name="boost_pool.pool.pooling.alignment.h1"></a> 205 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.overview"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.overview">Overview</a> 206 </h5> 207<p> 208 Each Pool has a single free list that can extend over a number of memory 209 blocks. Thus, Pool also has a linked list of allocated memory blocks. Each 210 memory block, by default, is allocated using <code class="computeroutput"><span class="keyword">new</span><span class="special">[]</span></code>, and all memory blocks are freed on destruction. 211 It is the use of <code class="computeroutput"><span class="keyword">new</span><span class="special">[]</span></code> 212 that allows us to guarantee alignment. 213 </p> 214<h5> 215<a name="boost_pool.pool.pooling.alignment.h2"></a> 216 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.proof_of_concept__guaranteeing_alignment"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.proof_of_concept__guaranteeing_alignment">Proof 217 of Concept: Guaranteeing Alignment</a> 218 </h5> 219<p> 220 Each block of memory is allocated as a POD type (specifically, an array 221 of characters) through <code class="computeroutput"><span class="keyword">operator</span> 222 <span class="keyword">new</span><span class="special">[]</span></code>. 223 Let <code class="computeroutput"><span class="identifier">POD_size</span></code> be the number 224 of characters allocated. 225 </p> 226<h6> 227<a name="boost_pool.pool.pooling.alignment.h3"></a> 228 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.predicate_1__arrays_may_not_have_padding"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.predicate_1__arrays_may_not_have_padding">Predicate 229 1: Arrays may not have padding</a> 230 </h6> 231<p> 232 This follows from the following quote: 233 </p> 234<p> 235 [5.3.3/2] (Expressions::Unary expressions::Sizeof) <span class="emphasis"><em>... When applied 236 to an array, the result is the total number of bytes in the array. This 237 implies that the size of an array of n elements is n times the size of 238 an element.</em></span> 239 </p> 240<p> 241 Therefore, arrays cannot contain padding, though the elements within the 242 arrays may contain padding. 243 </p> 244<h6> 245<a name="boost_pool.pool.pooling.alignment.h4"></a> 246 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.predicate_2__any_block_of_memory_allocated_as_an_array_of_characters_through__code__phrase_role__keyword__operator__phrase___phrase_role__keyword__new__phrase__phrase_role__special______phrase___code___hereafter_referred_to_as_the_block__is_properly_aligned_for_any_object_of_that_size_or_smaller"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.predicate_2__any_block_of_memory_allocated_as_an_array_of_characters_through__code__phrase_role__keyword__operator__phrase___phrase_role__keyword__new__phrase__phrase_role__special______phrase___code___hereafter_referred_to_as_the_block__is_properly_aligned_for_any_object_of_that_size_or_smaller">Predicate 247 2: Any block of memory allocated as an array of characters through <code class="computeroutput"><span class="keyword">operator</span> <span class="keyword">new</span><span class="special">[]</span></code> (hereafter referred to as the block) 248 is properly aligned for any object of that size or smaller</a> 249 </h6> 250<p> 251 This follows from: 252 </p> 253<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 254<li class="listitem"> 255 [3.7.3.1/2] (Basic concepts::Storage duration::Dynamic storage duration::Allocation 256 functions) <span class="emphasis"><em>"... The pointer returned shall be suitably 257 aligned so that it can be converted to a pointer of any complete object 258 type and then used to access the object or array in the storage allocated 259 ..."</em></span> 260 </li> 261<li class="listitem"> 262 [5.3.4/10] (Expressions::Unary expressions::New) <span class="emphasis"><em>"... 263 For arrays of char and unsigned char, the difference between the result 264 of the new-expression and the address returned by the allocation function 265 shall be an integral multiple of the most stringent alignment requirement 266 (3.9) of any object type whose size is no greater than the size of 267 the array being created. [Note: Because allocation functions are assumed 268 to return pointers to storage that is appropriately aligned for objects 269 of any type, this constraint on array allocation overhead permits the 270 common idiom of allocating character arrays into which objects of other 271 types will later be placed."</em></span> 272 </li> 273</ul></div> 274<h6> 275<a name="boost_pool.pool.pooling.alignment.h5"></a> 276 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.consider__imaginary_object_type_element_of_a_size_which_is_a_multiple_of_some_actual_object_size__assume__code__phrase_role__keyword__sizeof__phrase__phrase_role__special_____phrase__phrase_role__identifier__element__phrase__phrase_role__special_____phrase___phrase_role__special___gt___phrase___phrase_role__identifier__pod_size__phrase___code_"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.consider__imaginary_object_type_element_of_a_size_which_is_a_multiple_of_some_actual_object_size__assume__code__phrase_role__keyword__sizeof__phrase__phrase_role__special_____phrase__phrase_role__identifier__element__phrase__phrase_role__special_____phrase___phrase_role__special___gt___phrase___phrase_role__identifier__pod_size__phrase___code_">Consider: 277 imaginary object type Element of a size which is a multiple of some actual 278 object size; assume <code class="computeroutput"><span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">Element</span><span class="special">)</span> <span class="special">></span> <span class="identifier">POD_size</span></code></a> 279 </h6> 280<p> 281 Note that an object of that size can exist. One object of that size is 282 an array of the "actual" objects. 283 </p> 284<p> 285 Note that the block is properly aligned for an Element. This directly follows 286 from Predicate 2. 287 </p> 288<h6> 289<a name="boost_pool.pool.pooling.alignment.h6"></a> 290 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.corollary_1__the_block_is_properly_aligned_for_an_array_of_elements"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.corollary_1__the_block_is_properly_aligned_for_an_array_of_elements">Corollary 291 1: The block is properly aligned for an array of Elements</a> 292 </h6> 293<p> 294 This follows from Predicates 1 and 2, and the following quote: 295 </p> 296<p> 297 [3.9/9] (Basic concepts::Types) <span class="emphasis"><em>"An object type is a (possibly 298 cv-qualified) type that is not a function type, not a reference type, and 299 not a void type."</em></span> 300 </p> 301<p> 302 (Specifically, array types are object types.) 303 </p> 304<h6> 305<a name="boost_pool.pool.pooling.alignment.h7"></a> 306 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.corollary_2__for_any_pointer__code__phrase_role__identifier__p__phrase___code__and_integer__code__phrase_role__identifier__i__phrase___code___if__code__phrase_role__identifier__p__phrase___code__is_properly_aligned_for_the_type_it_points_to__then__code__phrase_role__identifier__p__phrase___phrase_role__special_____phrase___phrase_role__identifier__i__phrase___code___when_well_defined__is_properly_aligned_for_that_type__in_other_words__if_an_array_is_properly_aligned__then_each_element_in_that_array_is_properly_aligned"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.corollary_2__for_any_pointer__code__phrase_role__identifier__p__phrase___code__and_integer__code__phrase_role__identifier__i__phrase___code___if__code__phrase_role__identifier__p__phrase___code__is_properly_aligned_for_the_type_it_points_to__then__code__phrase_role__identifier__p__phrase___phrase_role__special_____phrase___phrase_role__identifier__i__phrase___code___when_well_defined__is_properly_aligned_for_that_type__in_other_words__if_an_array_is_properly_aligned__then_each_element_in_that_array_is_properly_aligned">Corollary 307 2: For any pointer <code class="computeroutput"><span class="identifier">p</span></code> and 308 integer <code class="computeroutput"><span class="identifier">i</span></code>, if <code class="computeroutput"><span class="identifier">p</span></code> is properly aligned for the type it 309 points to, then <code class="computeroutput"><span class="identifier">p</span> <span class="special">+</span> 310 <span class="identifier">i</span></code> (when well-defined) is properly 311 aligned for that type; in other words, if an array is properly aligned, 312 then each element in that array is properly aligned</a> 313 </h6> 314<p> 315 There are no quotes from the Standard to directly support this argument, 316 but it fits the common conception of the meaning of "alignment". 317 </p> 318<p> 319 Note that the conditions for <code class="computeroutput"><span class="identifier">p</span> 320 <span class="special">+</span> <span class="identifier">i</span></code> 321 being well-defined are outlined in [5.7/5]. We do not quote that here, 322 but only make note that it is well-defined if <code class="computeroutput"><span class="identifier">p</span></code> 323 and <code class="computeroutput"><span class="identifier">p</span> <span class="special">+</span> 324 <span class="identifier">i</span></code> both point into or one past 325 the same array. 326 </p> 327<h6> 328<a name="boost_pool.pool.pooling.alignment.h8"></a> 329 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.let___code__phrase_role__keyword__sizeof__phrase__phrase_role__special_____phrase__phrase_role__identifier__element__phrase__phrase_role__special_____phrase___code__be_the_least_common_multiple_of_sizes_of_several_actual_objects__t1__t2__t3______"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.let___code__phrase_role__keyword__sizeof__phrase__phrase_role__special_____phrase__phrase_role__identifier__element__phrase__phrase_role__special_____phrase___code__be_the_least_common_multiple_of_sizes_of_several_actual_objects__t1__t2__t3______">Let: 330 <code class="computeroutput"><span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">Element</span><span class="special">)</span></code> 331 be the least common multiple of sizes of several actual objects (T1, T2, 332 T3, ...)</a> 333 </h6> 334<h6> 335<a name="boost_pool.pool.pooling.alignment.h9"></a> 336 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.let__block_be_a_pointer_to_the_memory_block__pe_be__element____block__and_pn_be__tn____block"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.let__block_be_a_pointer_to_the_memory_block__pe_be__element____block__and_pn_be__tn____block">Let: 337 block be a pointer to the memory block, pe be (Element *) block, and pn 338 be (Tn *) block</a> 339 </h6> 340<h6> 341<a name="boost_pool.pool.pooling.alignment.h10"></a> 342 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.corollary_3__for_each_integer__code__phrase_role__identifier__i__phrase___code___such_that__code__phrase_role__identifier__pe__phrase___phrase_role__special_____phrase___phrase_role__identifier__i__phrase___code__is_well_defined__then_for_each_n__there_exists_some_integer__code__phrase_role__identifier__jn__phrase___code__such_that__code__phrase_role__identifier__pn__phrase___phrase_role__special_____phrase___phrase_role__identifier__jn__phrase___code__is_well_defined_and_refers_to_the_same_memory_address_as__code__phrase_role__identifier__pe__phrase___phrase_role__special_____phrase___phrase_role__identifier__i__phrase___code_"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.corollary_3__for_each_integer__code__phrase_role__identifier__i__phrase___code___such_that__code__phrase_role__identifier__pe__phrase___phrase_role__special_____phrase___phrase_role__identifier__i__phrase___code__is_well_defined__then_for_each_n__there_exists_some_integer__code__phrase_role__identifier__jn__phrase___code__such_that__code__phrase_role__identifier__pn__phrase___phrase_role__special_____phrase___phrase_role__identifier__jn__phrase___code__is_well_defined_and_refers_to_the_same_memory_address_as__code__phrase_role__identifier__pe__phrase___phrase_role__special_____phrase___phrase_role__identifier__i__phrase___code_">Corollary 343 3: For each integer <code class="computeroutput"><span class="identifier">i</span></code>, 344 such that <code class="computeroutput"><span class="identifier">pe</span> <span class="special">+</span> 345 <span class="identifier">i</span></code> is well-defined, then for each 346 n, there exists some integer <code class="computeroutput"><span class="identifier">jn</span></code> 347 such that <code class="computeroutput"><span class="identifier">pn</span> <span class="special">+</span> 348 <span class="identifier">jn</span></code> is well-defined and refers 349 to the same memory address as <code class="computeroutput"><span class="identifier">pe</span> 350 <span class="special">+</span> <span class="identifier">i</span></code></a> 351 </h6> 352<p> 353 This follows naturally, since the memory block is an array of Elements, 354 and for each n, <code class="computeroutput"><span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">Element</span><span class="special">)</span> <span class="special">%</span> <span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">Tn</span><span class="special">)</span> 355 <span class="special">==</span> <span class="number">0</span><span class="special">;</span></code> thus, the boundary of each element in 356 the array of Elements is also a boundary of each element in each array 357 of Tn. 358 </p> 359<h6> 360<a name="boost_pool.pool.pooling.alignment.h11"></a> 361 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.theorem__for_each_integer__code__phrase_role__identifier__i__phrase___code___such_that__code__phrase_role__identifier__pe__phrase___phrase_role__special_____phrase___phrase_role__identifier__i__phrase___code__is_well_defined__that_address__pe___i__is_properly_aligned_for_each_type_tn"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.theorem__for_each_integer__code__phrase_role__identifier__i__phrase___code___such_that__code__phrase_role__identifier__pe__phrase___phrase_role__special_____phrase___phrase_role__identifier__i__phrase___code__is_well_defined__that_address__pe___i__is_properly_aligned_for_each_type_tn">Theorem: 362 For each integer <code class="computeroutput"><span class="identifier">i</span></code>, such 363 that <code class="computeroutput"><span class="identifier">pe</span> <span class="special">+</span> 364 <span class="identifier">i</span></code> is well-defined, that address 365 (pe + i) is properly aligned for each type Tn</a> 366 </h6> 367<p> 368 Since <code class="computeroutput"><span class="identifier">pe</span> <span class="special">+</span> 369 <span class="identifier">i</span></code> is well-defined, then by Corollary 370 3, <code class="computeroutput"><span class="identifier">pn</span> <span class="special">+</span> 371 <span class="identifier">jn</span></code> is well-defined. It is properly 372 aligned from Predicate 2 and Corollaries 1 and 2. 373 </p> 374<h5> 375<a name="boost_pool.pool.pooling.alignment.h12"></a> 376 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.use_of_the_theorem"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.use_of_the_theorem">Use of the 377 Theorem</a> 378 </h5> 379<p> 380 The proof above covers alignment requirements for cutting chunks out of 381 a block. The implementation uses actual object sizes of: 382 </p> 383<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 384<li class="listitem"> 385 The requested object size (<code class="computeroutput"><span class="identifier">requested_size</span></code>); 386 this is the size of chunks requested by the user 387 </li> 388<li class="listitem"> 389 <code class="computeroutput"><span class="keyword">void</span><span class="special">*</span></code> 390 (pointer to void); this is because we interleave our free list through 391 the chunks 392 </li> 393<li class="listitem"> 394 <code class="computeroutput"><span class="identifier">size_type</span></code>; this is 395 because we store the size of the next block within each memory block 396 </li> 397</ul></div> 398<p> 399 Each block also contains a pointer to the next block; but that is stored 400 as a pointer to void and cast when necessary, to simplify alignment requirements 401 to the three types above. 402 </p> 403<p> 404 Therefore, <code class="computeroutput"><span class="identifier">alloc_size</span></code> is 405 defined to be the largest of the sizes above, rounded up to be a multiple 406 of all three sizes. This guarantees alignment provided all alignments are 407 powers of two: something that appears to be true on all known platforms. 408 </p> 409<h5> 410<a name="boost_pool.pool.pooling.alignment.h13"></a> 411 <span class="phrase"><a name="boost_pool.pool.pooling.alignment.a_look_at_the_memory_block"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.a_look_at_the_memory_block">A 412 Look at the Memory Block</a> 413 </h5> 414<p> 415 Each memory block consists of three main sections. The first section is 416 the part that chunks are cut out of, and contains the interleaved free 417 list. The second section is the pointer to the next block, and the third 418 section is the size of the next block. 419 </p> 420<p> 421 Each of these sections may contain padding as necessary to guarantee alignment 422 for each of the next sections. The size of the first section is <code class="computeroutput"><span class="identifier">number_of_chunks</span> <span class="special">*</span> 423 <span class="identifier">lcm</span><span class="special">(</span><span class="identifier">requested_size</span><span class="special">,</span> 424 <span class="keyword">sizeof</span><span class="special">(</span><span class="keyword">void</span> <span class="special">*),</span> <span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">size_type</span><span class="special">));</span></code> 425 the size of the second section is <code class="computeroutput"><span class="identifier">lcm</span><span class="special">(</span><span class="keyword">sizeof</span><span class="special">(</span><span class="keyword">void</span> <span class="special">*),</span> 426 <span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">size_type</span><span class="special">);</span></code> 427 and the size of the third section is <code class="computeroutput"><span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">size_type</span><span class="special">)</span></code>. 428 </p> 429<p> 430 Here's an example memory block, where <code class="computeroutput"><span class="identifier">requested_size</span> 431 <span class="special">==</span> <span class="keyword">sizeof</span><span class="special">(</span><span class="keyword">void</span> <span class="special">*)</span> 432 <span class="special">==</span> <span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">size_type</span><span class="special">)</span> <span class="special">==</span> <span class="number">4</span></code>: 433 </p> 434<p> 435 <span class="inlinemediaobject"><img src="../images/../../../images/mb1.png" align="middle"></span> 436 </p> 437<p> 438 To show a visual example of possible padding, here's an example memory 439 block where <code class="computeroutput"><span class="identifier">requested_size</span> <span class="special">==</span> <span class="number">8</span> <span class="keyword">and</span> 440 <span class="keyword">sizeof</span><span class="special">(</span><span class="keyword">void</span> <span class="special">*)</span> <span class="special">==</span> <span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">size_type</span><span class="special">)</span> <span class="special">==</span> <span class="number">4</span></code> 441 </p> 442<p> 443 <span class="inlinemediaobject"><img src="../images/../../../images/mb2.png" align="middle"></span> 444 </p> 445<div class="section"> 446<div class="titlepage"><div><div><h5 class="title"> 447<a name="boost_pool.pool.pooling.alignment.chunks"></a><a class="link" href="pooling.html#boost_pool.pool.pooling.alignment.chunks" title="How Contiguous Chunks are Handled">How Contiguous 448 Chunks are Handled</a> 449</h5></div></div></div> 450<p> 451 The theorem above guarantees all alignment requirements for allocating 452 chunks and also implementation details such as the interleaved free list. 453 However, it does so by adding padding when necessary; therefore, we have 454 to treat allocations of contiguous chunks in a different way. 455 </p> 456<p> 457 Using array arguments similar to the above, we can translate any request 458 for contiguous memory for <code class="computeroutput"><span class="identifier">n</span></code> 459 objects of <code class="computeroutput"><span class="identifier">requested_size</span></code> 460 into a request for m contiguous chunks. <code class="computeroutput"><span class="identifier">m</span></code> 461 is simply <code class="computeroutput"><span class="identifier">ceil</span><span class="special">(</span><span class="identifier">n</span> <span class="special">*</span> <span class="identifier">requested_size</span> <span class="special">/</span> 462 <span class="identifier">alloc_size</span><span class="special">)</span></code>, 463 where <code class="computeroutput"><span class="identifier">alloc_size</span></code> is the 464 actual size of the chunks. 465 </p> 466<p> 467 To illustrate: 468 </p> 469<p> 470 Here's an example memory block, where <code class="computeroutput"><span class="identifier">requested_size</span> 471 <span class="special">==</span> <span class="number">1</span></code> 472 and <code class="computeroutput"><span class="keyword">sizeof</span><span class="special">(</span><span class="keyword">void</span> <span class="special">*)</span> <span class="special">==</span> <span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">size_type</span><span class="special">)</span> <span class="special">==</span> <span class="number">4</span></code>: 473 </p> 474<p> 475 <span class="inlinemediaobject"><img src="../images/../../../images/mb4.png" align="middle"></span> 476 </p> 477<p> 478 Then, when the user deallocates the contiguous memory, we can split it 479 up into chunks again. 480 </p> 481<p> 482 Note that the implementation provided for allocating contiguous chunks 483 uses a linear instead of quadratic algorithm. This means that it may 484 not find contiguous free chunks if the free list is not ordered. Thus, 485 it is recommended to always use an ordered free list when dealing with 486 contiguous allocation of chunks. (In the example above, if Chunk 1 pointed 487 to Chunk 3 pointed to Chunk 2 pointed to Chunk 4, instead of being in 488 order, the contiguous allocation algorithm would have failed to find 489 any of the contiguous chunks). 490 </p> 491</div> 492</div> 493<div class="section"> 494<div class="titlepage"><div><div><h4 class="title"> 495<a name="boost_pool.pool.pooling.simple_segregated"></a><a class="link" href="pooling.html#boost_pool.pool.pooling.simple_segregated" title="Simple Segregated Storage (Not for the faint of heart - Embedded programmers only!)">Simple Segregated 496 Storage (Not for the faint of heart - Embedded programmers only!)</a> 497</h4></div></div></div> 498<h5> 499<a name="boost_pool.pool.pooling.simple_segregated.h0"></a> 500 <span class="phrase"><a name="boost_pool.pool.pooling.simple_segregated.introduction"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.simple_segregated.introduction">Introduction</a> 501 </h5> 502<p> 503 <code class="computeroutput"><a class="link" href="../../header/boost/pool/simple_segregated_storage_hpp.html" title="Header <boost/pool/simple_segregated_storage.hpp>">simple_segregated_storage.hpp</a></code> 504 provides a template class simple_segregated_storage that controls access 505 to a free list of memory chunks. 506 </p> 507<p> 508 Note that this is a very simple class, with unchecked preconditions on 509 almost all its functions. It is intended to be the fastest and smallest 510 possible quick memory allocator for example, something to use in embedded 511 systems. This class delegates many difficult preconditions to the user 512 (especially alignment issues). For more general usage, see the other <a class="link" href="interfaces.html" title="Boost Pool Interfaces - What interfaces are provided and when to use each one.">Pool Interfaces</a>. 513 </p> 514<h5> 515<a name="boost_pool.pool.pooling.simple_segregated.h1"></a> 516 <span class="phrase"><a name="boost_pool.pool.pooling.simple_segregated.synopsis"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.simple_segregated.synopsis">Synopsis</a> 517 </h5> 518<pre class="programlisting">template <typename SizeType = std::size_t> 519class simple_segregated_storage 520{ 521 private: 522 simple_segregated_storage(const simple_segregated_storage &); 523 void operator=(const simple_segregated_storage &); 524 525 public: 526 typedef SizeType size_type; 527 528 simple_segregated_storage(); 529 ~simple_segregated_storage(); 530 531 static void * segregate(void * block, 532 size_type nsz, size_type npartition_sz, 533 void * end = 0); 534 void add_block(void * block, 535 size_type nsz, size_type npartition_sz); 536 void add_ordered_block(void * block, 537 size_type nsz, size_type npartition_sz); 538 539 bool empty() const; 540 541 void * malloc(); 542 void free(void * chunk); 543 void ordered_free(void * chunk); 544 void * malloc_n(size_type n, size_type partition_sz); 545 void free_n(void * chunks, size_type n, 546 size_type partition_sz); 547 void ordered_free_n(void * chunks, size_type n, 548 size_type partition_sz); 549}; 550</pre> 551<h5> 552<a name="boost_pool.pool.pooling.simple_segregated.h2"></a> 553 <span class="phrase"><a name="boost_pool.pool.pooling.simple_segregated.semantics"></a></span><a class="link" href="pooling.html#boost_pool.pool.pooling.simple_segregated.semantics">Semantics</a> 554 </h5> 555<p> 556 An object of type <code class="computeroutput"><span class="identifier">simple_segregated_storage</span><span class="special"><</span><span class="identifier">SizeType</span><span class="special">></span></code> is empty if its free list is empty. 557 If it is not empty, then it is ordered if its free list is ordered. A free 558 list is ordered if repeated calls to<code class="computeroutput"> <span class="identifier">malloc</span><span class="special">()</span></code> will result in a constantly-increasing 559 sequence of values, as determined by <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special"><</span><span class="keyword">void</span> <span class="special">*></span></code>. A member function is order-preserving 560 if the free-list maintains its order orientation (that is, an ordered free 561 list is still ordered after the member function call). 562 </p> 563<div class="table"> 564<a name="boost_pool.pool.pooling.simple_segregated.ss_symbols"></a><p class="title"><b>Table 1. Symbol Table</b></p> 565<div class="table-contents"><table class="table" summary="Symbol Table" cellspacing="3" cellpadding="5"> 566<colgroup> 567<col> 568<col> 569</colgroup> 570<thead><tr> 571<th> 572 <p> 573 Symbol 574 </p> 575 </th> 576<th> 577 <p> 578 Meaning 579 </p> 580 </th> 581</tr></thead> 582<tbody> 583<tr> 584<td> 585 <p> 586 Store 587 </p> 588 </td> 589<td> 590 <p> 591 simple_segregated_storage<SizeType> 592 </p> 593 </td> 594</tr> 595<tr> 596<td> 597 <p> 598 t 599 </p> 600 </td> 601<td> 602 <p> 603 value of type Store 604 </p> 605 </td> 606</tr> 607<tr> 608<td> 609 <p> 610 u 611 </p> 612 </td> 613<td> 614 <p> 615 value of type const Store 616 </p> 617 </td> 618</tr> 619<tr> 620<td> 621 <p> 622 block, chunk, end 623 </p> 624 </td> 625<td> 626 <p> 627 values of type void * 628 </p> 629 </td> 630</tr> 631<tr> 632<td> 633 <p> 634 partition_sz, sz, n 635 </p> 636 </td> 637<td> 638 <p> 639 values of type Store::size_type 640 </p> 641 </td> 642</tr> 643</tbody> 644</table></div> 645</div> 646<br class="table-break"><div class="table"> 647<a name="boost_pool.pool.pooling.simple_segregated.templates"></a><p class="title"><b>Table 2. Template Parameters</b></p> 648<div class="table-contents"><table class="table" summary="Template Parameters" cellspacing="3" cellpadding="5"> 649<colgroup> 650<col> 651<col> 652<col> 653</colgroup> 654<thead><tr> 655<th> 656 <p> 657 Parameter 658 </p> 659 </th> 660<th> 661 <p> 662 Default 663 </p> 664 </th> 665<th> 666 <p> 667 Requirements 668 </p> 669 </th> 670</tr></thead> 671<tbody><tr> 672<td> 673 <p> 674 SizeType 675 </p> 676 </td> 677<td> 678 <p> 679 std::size_t 680 </p> 681 </td> 682<td> 683 <p> 684 An unsigned integral type 685 </p> 686 </td> 687</tr></tbody> 688</table></div> 689</div> 690<br class="table-break"><div class="table"> 691<a name="boost_pool.pool.pooling.simple_segregated.Typedefs"></a><p class="title"><b>Table 3. Typedefs</b></p> 692<div class="table-contents"><table class="table" summary="Typedefs" cellspacing="3" cellpadding="5"> 693<colgroup> 694<col> 695<col> 696</colgroup> 697<thead><tr> 698<th> 699 <p> 700 Symbol 701 </p> 702 </th> 703<th> 704 <p> 705 Type 706 </p> 707 </th> 708</tr></thead> 709<tbody><tr> 710<td> 711 <p> 712 size_type 713 </p> 714 </td> 715<td> 716 <p> 717 SizeType 718 </p> 719 </td> 720</tr></tbody> 721</table></div> 722</div> 723<br class="table-break"><div class="table"> 724<a name="boost_pool.pool.pooling.simple_segregated.Constructors"></a><p class="title"><b>Table 4. Constructors, Destructors, and State</b></p> 725<div class="table-contents"><table class="table" summary="Constructors, Destructors, and State" cellspacing="3" cellpadding="5"> 726<colgroup> 727<col> 728<col> 729<col> 730<col> 731</colgroup> 732<thead><tr> 733<th> 734 <p> 735 Expression 736 </p> 737 </th> 738<th> 739 <p> 740 Return Type 741 </p> 742 </th> 743<th> 744 <p> 745 Post-Condition 746 </p> 747 </th> 748<th> 749 <p> 750 Notes 751 </p> 752 </th> 753</tr></thead> 754<tbody> 755<tr> 756<td> 757 <p> 758 Store() 759 </p> 760 </td> 761<td> 762 <p> 763 not used 764 </p> 765 </td> 766<td> 767 <p> 768 empty() 769 </p> 770 </td> 771<td> 772 <p> 773 Constructs a new Store 774 </p> 775 </td> 776</tr> 777<tr> 778<td> 779 <p> 780 (&t)->~Store() 781 </p> 782 </td> 783<td> 784 <p> 785 not used 786 </p> 787 </td> 788<td> 789 </td> 790<td> 791 <p> 792 Destructs the Store 793 </p> 794 </td> 795</tr> 796<tr> 797<td> 798 <p> 799 u.empty() 800 </p> 801 </td> 802<td> 803 <p> 804 bool 805 </p> 806 </td> 807<td> 808 </td> 809<td> 810 <p> 811 Returns true if u is empty. Order-preserving. 812 </p> 813 </td> 814</tr> 815</tbody> 816</table></div> 817</div> 818<br class="table-break"><div class="table"> 819<a name="boost_pool.pool.pooling.simple_segregated.Segregation"></a><p class="title"><b>Table 5. Segregation</b></p> 820<div class="table-contents"><table class="table" summary="Segregation" cellspacing="3" cellpadding="5"> 821<colgroup> 822<col> 823<col> 824<col> 825<col> 826<col> 827<col> 828</colgroup> 829<thead><tr> 830<th> 831 <p> 832 Expression 833 </p> 834 </th> 835<th> 836 <p> 837 Return Type 838 </p> 839 </th> 840<th> 841 <p> 842 Pre-Condition 843 </p> 844 </th> 845<th> 846 <p> 847 Post-Condition 848 </p> 849 </th> 850<th> 851 <p> 852 Semantic Equivalence 853 </p> 854 </th> 855<th> 856 <p> 857 Notes 858 </p> 859 </th> 860</tr></thead> 861<tbody> 862<tr> 863<td> 864 <p> 865 Store::segregate(block, sz, partition_sz, end) 866 </p> 867 </td> 868<td> 869 <p> 870 void * 871 </p> 872 </td> 873<td> 874 <p> 875 partition_sz >= sizeof(void *) partition_sz = sizeof(void 876 *) * i, for some integer i sz >= partition_sz block is properly 877 aligned for an array of objects of size partition_sz block is 878 properly aligned for an array of void * 879 </p> 880 </td> 881<td> 882 </td> 883<td> 884 </td> 885<td> 886 <p> 887 Interleaves a free list through the memory block specified by 888 block of size sz bytes, partitioning it into as many partition_sz-sized 889 chunks as possible. The last chunk is set to point to end, and 890 a pointer to the first chunck is returned (this is always equal 891 to block). This interleaved free list is ordered. O(sz). 892 </p> 893 </td> 894</tr> 895<tr> 896<td> 897 <p> 898 Store::segregate(block, sz, partition_sz) 899 </p> 900 </td> 901<td> 902 <p> 903 void * 904 </p> 905 </td> 906<td> 907 <p> 908 Same as above 909 </p> 910 </td> 911<td> 912 </td> 913<td> 914 <p> 915 Store::segregate(block, sz, partition_sz, 0) 916 </p> 917 </td> 918<td> 919 </td> 920</tr> 921<tr> 922<td> 923 <p> 924 t.add_block(block, sz, partition_sz) 925 </p> 926 </td> 927<td> 928 <p> 929 void 930 </p> 931 </td> 932<td> 933 <p> 934 Same as above 935 </p> 936 </td> 937<td> 938 <p> 939 !t.empty() 940 </p> 941 </td> 942<td> 943 </td> 944<td> 945 <p> 946 Segregates the memory block specified by block of size sz bytes 947 into partition_sz-sized chunks, and adds that free list to its 948 own. If t was empty before this call, then it is ordered after 949 this call. O(sz). 950 </p> 951 </td> 952</tr> 953<tr> 954<td> 955 <p> 956 t.add_ordered_block(block, sz, partition_sz) 957 </p> 958 </td> 959<td> 960 <p> 961 void 962 </p> 963 </td> 964<td> 965 <p> 966 Same as above 967 </p> 968 </td> 969<td> 970 <p> 971 !t.empty() 972 </p> 973 </td> 974<td> 975 </td> 976<td> 977 <p> 978 Segregates the memory block specified by block of size sz bytes 979 into partition_sz-sized chunks, and merges that free list into 980 its own. Order-preserving. O(sz). 981 </p> 982 </td> 983</tr> 984</tbody> 985</table></div> 986</div> 987<br class="table-break"><div class="table"> 988<a name="boost_pool.pool.pooling.simple_segregated.alloc"></a><p class="title"><b>Table 6. Allocation and Deallocation</b></p> 989<div class="table-contents"><table class="table" summary="Allocation and Deallocation" cellspacing="3" cellpadding="5"> 990<colgroup> 991<col> 992<col> 993<col> 994<col> 995<col> 996<col> 997</colgroup> 998<thead><tr> 999<th> 1000 <p> 1001 Expression 1002 </p> 1003 </th> 1004<th> 1005 <p> 1006 Return Type 1007 </p> 1008 </th> 1009<th> 1010 <p> 1011 Pre-Condition 1012 </p> 1013 </th> 1014<th> 1015 <p> 1016 Post-Condition 1017 </p> 1018 </th> 1019<th> 1020 <p> 1021 Semantic Equivalence 1022 </p> 1023 </th> 1024<th> 1025 <p> 1026 Notes 1027 </p> 1028 </th> 1029</tr></thead> 1030<tbody> 1031<tr> 1032<td> 1033 <p> 1034 t.malloc() 1035 </p> 1036 </td> 1037<td> 1038 <p> 1039 void * 1040 </p> 1041 </td> 1042<td> 1043 <p> 1044 !t.empty() 1045 </p> 1046 </td> 1047<td> 1048 </td> 1049<td> 1050 </td> 1051<td> 1052 <p> 1053 Takes the first available chunk from the free list and returns 1054 it. Order-preserving. O(1). 1055 </p> 1056 </td> 1057</tr> 1058<tr> 1059<td> 1060 <p> 1061 t.free(chunk) 1062 </p> 1063 </td> 1064<td> 1065 <p> 1066 void 1067 </p> 1068 </td> 1069<td> 1070 <p> 1071 chunk was previously returned from a call to t.malloc() 1072 </p> 1073 </td> 1074<td> 1075 <p> 1076 !t.empty() 1077 </p> 1078 </td> 1079<td> 1080 </td> 1081<td> 1082 <p> 1083 Places chunk back on the free list. Note that chunk may not be 1084 0. O(1). 1085 </p> 1086 </td> 1087</tr> 1088<tr> 1089<td> 1090 <p> 1091 t.ordered_free(chunk) 1092 </p> 1093 </td> 1094<td> 1095 <p> 1096 void 1097 </p> 1098 </td> 1099<td> 1100 <p> 1101 Same as above 1102 </p> 1103 </td> 1104<td> 1105 <p> 1106 !t.empty() 1107 </p> 1108 </td> 1109<td> 1110 </td> 1111<td> 1112 <p> 1113 Places chunk back on the free list. Note that chunk may not be 1114 0. Order-preserving. O(N) with respect to the size of the free 1115 list. 1116 </p> 1117 </td> 1118</tr> 1119<tr> 1120<td> 1121 <p> 1122 t.malloc_n(n, partition_sz) 1123 </p> 1124 </td> 1125<td> 1126 <p> 1127 void * 1128 </p> 1129 </td> 1130<td> 1131 </td> 1132<td> 1133 </td> 1134<td> 1135 </td> 1136<td> 1137 <p> 1138 Attempts to find a contiguous sequence of n partition_sz-sized 1139 chunks. If found, removes them all from the free list and returns 1140 a pointer to the first. If not found, returns 0. It is strongly 1141 recommended (but not required) that the free list be ordered, 1142 as this algorithm will fail to find a contiguous sequence unless 1143 it is contiguous in the free list as well. Order-preserving. 1144 O(N) with respect to the size of the free list. 1145 </p> 1146 </td> 1147</tr> 1148<tr> 1149<td> 1150 <p> 1151 t.free_n(chunk, n, partition_sz) 1152 </p> 1153 </td> 1154<td> 1155 <p> 1156 void 1157 </p> 1158 </td> 1159<td> 1160 <p> 1161 chunk was previously returned from a call to t.malloc_n(n, partition_sz) 1162 </p> 1163 </td> 1164<td> 1165 <p> 1166 !t.empty() 1167 </p> 1168 </td> 1169<td> 1170 <p> 1171 t.add_block(chunk, n * partition_sz, partition_sz) 1172 </p> 1173 </td> 1174<td> 1175 <p> 1176 Assumes that chunk actually refers to a block of chunks spanning 1177 n * partition_sz bytes; segregates and adds in that block. Note 1178 that chunk may not be 0. O(n). 1179 </p> 1180 </td> 1181</tr> 1182<tr> 1183<td> 1184 <p> 1185 t.ordered_free_n(chunk, n, partition_sz) 1186 </p> 1187 </td> 1188<td> 1189 <p> 1190 void 1191 </p> 1192 </td> 1193<td> 1194 <p> 1195 same as above 1196 </p> 1197 </td> 1198<td> 1199 <p> 1200 same as above 1201 </p> 1202 </td> 1203<td> 1204 <p> 1205 t.add_ordered_block(chunk, n * partition_sz, partition_sz) 1206 </p> 1207 </td> 1208<td> 1209 <p> 1210 Same as above, except it merges in the free list. Order-preserving. 1211 O(N + n) where N is the size of the free list. 1212 </p> 1213 </td> 1214</tr> 1215</tbody> 1216</table></div> 1217</div> 1218<br class="table-break"> 1219</div> 1220<div class="section"> 1221<div class="titlepage"><div><div><h4 class="title"> 1222<a name="boost_pool.pool.pooling.user_allocator"></a><a class="link" href="pooling.html#boost_pool.pool.pooling.user_allocator" title="The UserAllocator Concept">The UserAllocator 1223 Concept</a> 1224</h4></div></div></div> 1225<p> 1226 Pool objects need to request memory blocks from the system, which the Pool 1227 then splits into chunks to allocate to the user. By specifying a UserAllocator 1228 template parameter to various Pool interfaces, users can control how those 1229 system memory blocks are allocated. 1230 </p> 1231<p> 1232 In the following table, <span class="emphasis"><em>UserAllocator</em></span> is a User Allocator 1233 type, <span class="emphasis"><em>block</em></span> is a value of type char *, and <span class="emphasis"><em>n</em></span> 1234 is a value of type UserAllocator::size_type 1235 </p> 1236<div class="table"> 1237<a name="boost_pool.pool.pooling.user_allocator.userallocator_requirements"></a><p class="title"><b>Table 7. UserAllocator Requirements</b></p> 1238<div class="table-contents"><table class="table" summary="UserAllocator Requirements" cellspacing="3" cellpadding="5"> 1239<colgroup> 1240<col> 1241<col> 1242<col> 1243</colgroup> 1244<thead><tr> 1245<th> 1246 <p> 1247 Expression 1248 </p> 1249 </th> 1250<th> 1251 <p> 1252 Result 1253 </p> 1254 </th> 1255<th> 1256 <p> 1257 Description 1258 </p> 1259 </th> 1260</tr></thead> 1261<tbody> 1262<tr> 1263<td> 1264 <p> 1265 UserAllocator::size_type 1266 </p> 1267 </td> 1268<td> 1269 </td> 1270<td> 1271 <p> 1272 An unsigned integral type that can represent the size of the 1273 largest object to be allocated. 1274 </p> 1275 </td> 1276</tr> 1277<tr> 1278<td> 1279 <p> 1280 UserAllocator::difference_type 1281 </p> 1282 </td> 1283<td> 1284 </td> 1285<td> 1286 <p> 1287 A signed integral type that can represent the difference of any 1288 two pointers. 1289 </p> 1290 </td> 1291</tr> 1292<tr> 1293<td> 1294 <p> 1295 UserAllocator::malloc(n) 1296 </p> 1297 </td> 1298<td> 1299 <p> 1300 char * 1301 </p> 1302 </td> 1303<td> 1304 <p> 1305 Attempts to allocate n bytes from the system. Returns 0 if out-of-memory. 1306 </p> 1307 </td> 1308</tr> 1309<tr> 1310<td> 1311 <p> 1312 UserAllocator::free(block) 1313 </p> 1314 </td> 1315<td> 1316 <p> 1317 void 1318 </p> 1319 </td> 1320<td> 1321 <p> 1322 block must have been previously returned from a call to UserAllocator::malloc. 1323 </p> 1324 </td> 1325</tr> 1326</tbody> 1327</table></div> 1328</div> 1329<br class="table-break"><p> 1330 There are two UserAllocator classes provided in this library: <code class="computeroutput"><a class="link" href="../../boost/default_user_allocator_new_delete.html" title="Struct default_user_allocator_new_delete">default_user_allocator_new_delete</a></code> 1331 and <code class="computeroutput"><a class="link" href="../../boost/default_user_allocator_malloc_free.html" title="Struct default_user_allocator_malloc_free">default_user_allocator_malloc_free</a></code>, 1332 both in pool.hpp. The default value for the template parameter UserAllocator 1333 is always <code class="computeroutput"><a class="link" href="../../boost/default_user_allocator_new_delete.html" title="Struct default_user_allocator_new_delete">default_user_allocator_new_delete</a></code>. 1334 </p> 1335</div> 1336</div> 1337<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 1338<td align="left"></td> 1339<td align="right"><div class="copyright-footer">Copyright © 2000-2006 Stephen Cleary<br>Copyright © 2011 Paul A. Bristow<p> 1340 Distributed under the Boost Software License, Version 1.0. (See accompanying 1341 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 1342 </p> 1343</div></td> 1344</tr></table> 1345<hr> 1346<div class="spirit-nav"> 1347<a accesskey="p" href="interfaces.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../pool.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../../boost_pool_c___reference.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 1348</div> 1349</body> 1350</html> 1351
