]>
Commit | Line | Data |
---|---|---|
1 | // Copyright (C) 2000, 2001 Stephen Cleary | |
2 | // | |
3 | // Distributed under the Boost Software License, Version 1.0. (See | |
4 | // accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | // | |
7 | // See http://www.boost.org for updates, documentation, and revision history. | |
8 | ||
9 | #ifndef BOOST_SIMPLE_SEGREGATED_STORAGE_HPP | |
10 | #define BOOST_SIMPLE_SEGREGATED_STORAGE_HPP | |
11 | ||
12 | /*! | |
13 | \file | |
14 | \brief Simple Segregated Storage. | |
15 | \details A simple segregated storage implementation: | |
16 | simple segregated storage is the basic idea behind the Boost Pool library. | |
17 | Simple segregated storage is the simplest, and probably the fastest, | |
18 | memory allocation/deallocation algorithm. | |
19 | It begins by partitioning a memory block into fixed-size chunks. | |
20 | Where the block comes from is not important until implementation time. | |
21 | A Pool is some object that uses Simple Segregated Storage in this fashion. | |
22 | */ | |
23 | ||
24 | // std::greater | |
25 | #include <functional> | |
26 | ||
27 | #include <boost/pool/poolfwd.hpp> | |
28 | ||
29 | #ifdef BOOST_MSVC | |
30 | #pragma warning(push) | |
31 | #pragma warning(disable:4127) // Conditional expression is constant | |
32 | #endif | |
33 | ||
34 | #ifdef BOOST_POOL_VALIDATE | |
35 | # define BOOST_POOL_VALIDATE_INTERNALS validate(); | |
36 | #else | |
37 | # define BOOST_POOL_VALIDATE_INTERNALS | |
38 | #endif | |
39 | ||
40 | namespace boost { | |
41 | ||
42 | /*! | |
43 | ||
44 | \brief Simple Segregated Storage is the simplest, and probably the fastest, | |
45 | memory allocation/deallocation algorithm. It is responsible for | |
46 | partitioning a memory block into fixed-size chunks: where the block comes from | |
47 | is determined by the client of the class. | |
48 | ||
49 | \details Template class simple_segregated_storage controls access to a free list of memory chunks. | |
50 | Please note that this is a very simple class, with preconditions on almost all its functions. It is intended to | |
51 | be the fastest and smallest possible quick memory allocator - e.g., something to use in embedded systems. | |
52 | This class delegates many difficult preconditions to the user (i.e., alignment issues). | |
53 | ||
54 | An object of type simple_segregated_storage<SizeType> is empty if its free list is empty. | |
55 | If it is not empty, then it is ordered if its free list is ordered. A free list is ordered if repeated calls | |
56 | to <tt>malloc()</tt> will result in a constantly-increasing sequence of values, as determined by <tt>std::less<void *></tt>. | |
57 | A member function is <i>order-preserving</i> if the free list maintains its order orientation (that is, an | |
58 | ordered free list is still ordered after the member function call). | |
59 | ||
60 | */ | |
61 | template <typename SizeType> | |
62 | class simple_segregated_storage | |
63 | { | |
64 | public: | |
65 | typedef SizeType size_type; | |
66 | ||
67 | private: | |
68 | simple_segregated_storage(const simple_segregated_storage &); | |
69 | void operator=(const simple_segregated_storage &); | |
70 | ||
71 | static void * try_malloc_n(void * & start, size_type n, | |
72 | size_type partition_size); | |
73 | ||
74 | protected: | |
75 | void * first; /*!< This data member is the free list. | |
76 | It points to the first chunk in the free list, | |
77 | or is equal to 0 if the free list is empty. | |
78 | */ | |
79 | ||
80 | void * find_prev(void * ptr); | |
81 | ||
82 | // for the sake of code readability :) | |
83 | static void * & nextof(void * const ptr) | |
84 | { //! The return value is just *ptr cast to the appropriate type. ptr must not be 0. (For the sake of code readability :) | |
85 | //! As an example, let us assume that we want to truncate the free list after the first chunk. | |
86 | //! That is, we want to set *first to 0; this will result in a free list with only one entry. | |
87 | //! The normal way to do this is to first cast first to a pointer to a pointer to void, | |
88 | //! and then dereference and assign (*static_cast<void **>(first) = 0;). | |
89 | //! This can be done more easily through the use of this convenience function (nextof(first) = 0;). | |
90 | //! \returns dereferenced pointer. | |
91 | return *(static_cast<void **>(ptr)); | |
92 | } | |
93 | ||
94 | public: | |
95 | // Post: empty() | |
96 | simple_segregated_storage() | |
97 | :first(0) | |
98 | { //! Construct empty storage area. | |
99 | //! \post empty() | |
100 | } | |
101 | ||
102 | static void * segregate(void * block, | |
103 | size_type nsz, size_type npartition_sz, | |
104 | void * end = 0); | |
105 | ||
106 | // Same preconditions as 'segregate' | |
107 | // Post: !empty() | |
108 | void add_block(void * const block, | |
109 | const size_type nsz, const size_type npartition_sz) | |
110 | { //! Add block | |
111 | //! Segregate this block and merge its free list into the | |
112 | //! free list referred to by "first". | |
113 | //! \pre Same as segregate. | |
114 | //! \post !empty() | |
115 | BOOST_POOL_VALIDATE_INTERNALS | |
116 | first = segregate(block, nsz, npartition_sz, first); | |
117 | BOOST_POOL_VALIDATE_INTERNALS | |
118 | } | |
119 | ||
120 | // Same preconditions as 'segregate' | |
121 | // Post: !empty() | |
122 | void add_ordered_block(void * const block, | |
123 | const size_type nsz, const size_type npartition_sz) | |
124 | { //! add block (ordered into list) | |
125 | //! This (slower) version of add_block segregates the | |
126 | //! block and merges its free list into our free list | |
127 | //! in the proper order. | |
128 | BOOST_POOL_VALIDATE_INTERNALS | |
129 | // Find where "block" would go in the free list | |
130 | void * const loc = find_prev(block); | |
131 | ||
132 | // Place either at beginning or in middle/end | |
133 | if (loc == 0) | |
134 | add_block(block, nsz, npartition_sz); | |
135 | else | |
136 | nextof(loc) = segregate(block, nsz, npartition_sz, nextof(loc)); | |
137 | BOOST_POOL_VALIDATE_INTERNALS | |
138 | } | |
139 | ||
140 | // default destructor. | |
141 | ||
142 | bool empty() const | |
143 | { //! \returns true only if simple_segregated_storage is empty. | |
144 | return (first == 0); | |
145 | } | |
146 | ||
147 | void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION() | |
148 | { //! Create a chunk. | |
149 | //! \pre !empty() | |
150 | //! Increment the "first" pointer to point to the next chunk. | |
151 | BOOST_POOL_VALIDATE_INTERNALS | |
152 | void * const ret = first; | |
153 | ||
154 | // Increment the "first" pointer to point to the next chunk. | |
155 | first = nextof(first); | |
156 | BOOST_POOL_VALIDATE_INTERNALS | |
157 | return ret; | |
158 | } | |
159 | ||
160 | void free BOOST_PREVENT_MACRO_SUBSTITUTION(void * const chunk) | |
161 | { //! Free a chunk. | |
162 | //! \pre chunk was previously returned from a malloc() referring to the same free list. | |
163 | //! \post !empty() | |
164 | BOOST_POOL_VALIDATE_INTERNALS | |
165 | nextof(chunk) = first; | |
166 | first = chunk; | |
167 | BOOST_POOL_VALIDATE_INTERNALS | |
168 | } | |
169 | ||
170 | void ordered_free(void * const chunk) | |
171 | { //! This (slower) implementation of 'free' places the memory | |
172 | //! back in the list in its proper order. | |
173 | //! \pre chunk was previously returned from a malloc() referring to the same free list | |
174 | //! \post !empty(). | |
175 | ||
176 | // Find where "chunk" goes in the free list | |
177 | BOOST_POOL_VALIDATE_INTERNALS | |
178 | void * const loc = find_prev(chunk); | |
179 | ||
180 | // Place either at beginning or in middle/end. | |
181 | if (loc == 0) | |
182 | (free)(chunk); | |
183 | else | |
184 | { | |
185 | nextof(chunk) = nextof(loc); | |
186 | nextof(loc) = chunk; | |
187 | } | |
188 | BOOST_POOL_VALIDATE_INTERNALS | |
189 | } | |
190 | ||
191 | void * malloc_n(size_type n, size_type partition_size); | |
192 | ||
193 | //! \pre chunks was previously allocated from *this with the same | |
194 | //! values for n and partition_size. | |
195 | //! \post !empty() | |
196 | //! \note If you're allocating/deallocating n a lot, you should | |
197 | //! be using an ordered pool. | |
198 | void free_n(void * const chunks, const size_type n, | |
199 | const size_type partition_size) | |
200 | { | |
201 | BOOST_POOL_VALIDATE_INTERNALS | |
202 | if(n != 0) | |
203 | add_block(chunks, n * partition_size, partition_size); | |
204 | BOOST_POOL_VALIDATE_INTERNALS | |
205 | } | |
206 | ||
207 | // pre: chunks was previously allocated from *this with the same | |
208 | // values for n and partition_size. | |
209 | // post: !empty() | |
210 | void ordered_free_n(void * const chunks, const size_type n, | |
211 | const size_type partition_size) | |
212 | { //! Free n chunks from order list. | |
213 | //! \pre chunks was previously allocated from *this with the same | |
214 | //! values for n and partition_size. | |
215 | ||
216 | //! \pre n should not be zero (n == 0 has no effect). | |
217 | BOOST_POOL_VALIDATE_INTERNALS | |
218 | if(n != 0) | |
219 | add_ordered_block(chunks, n * partition_size, partition_size); | |
220 | BOOST_POOL_VALIDATE_INTERNALS | |
221 | } | |
222 | #ifdef BOOST_POOL_VALIDATE | |
223 | void validate() | |
224 | { | |
225 | int index = 0; | |
226 | void* old = 0; | |
227 | void* ptr = first; | |
228 | while(ptr) | |
229 | { | |
230 | void* pt = nextof(ptr); // trigger possible segfault *before* we update variables | |
231 | ++index; | |
232 | old = ptr; | |
233 | ptr = nextof(ptr); | |
234 | } | |
235 | } | |
236 | #endif | |
237 | }; | |
238 | ||
239 | //! Traverses the free list referred to by "first", | |
240 | //! and returns the iterator previous to where | |
241 | //! "ptr" would go if it was in the free list. | |
242 | //! Returns 0 if "ptr" would go at the beginning | |
243 | //! of the free list (i.e., before "first"). | |
244 | ||
245 | //! \note Note that this function finds the location previous to where ptr would go | |
246 | //! if it was in the free list. | |
247 | //! It does not find the entry in the free list before ptr | |
248 | //! (unless ptr is already in the free list). | |
249 | //! Specifically, find_prev(0) will return 0, | |
250 | //! not the last entry in the free list. | |
251 | //! \returns location previous to where ptr would go if it was in the free list. | |
252 | template <typename SizeType> | |
253 | void * simple_segregated_storage<SizeType>::find_prev(void * const ptr) | |
254 | { | |
255 | // Handle border case. | |
256 | if (first == 0 || std::greater<void *>()(first, ptr)) | |
257 | return 0; | |
258 | ||
259 | void * iter = first; | |
260 | while (true) | |
261 | { | |
262 | // if we're about to hit the end, or if we've found where "ptr" goes. | |
263 | if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr)) | |
264 | return iter; | |
265 | ||
266 | iter = nextof(iter); | |
267 | } | |
268 | } | |
269 | ||
270 | //! Segregate block into chunks. | |
271 | //! \pre npartition_sz >= sizeof(void *) | |
272 | //! \pre npartition_sz = sizeof(void *) * i, for some integer i | |
273 | //! \pre nsz >= npartition_sz | |
274 | //! \pre Block is properly aligned for an array of object of | |
275 | //! size npartition_sz and array of void *. | |
276 | //! The requirements above guarantee that any pointer to a chunk | |
277 | //! (which is a pointer to an element in an array of npartition_sz) | |
278 | //! may be cast to void **. | |
279 | template <typename SizeType> | |
280 | void * simple_segregated_storage<SizeType>::segregate( | |
281 | void * const block, | |
282 | const size_type sz, | |
283 | const size_type partition_sz, | |
284 | void * const end) | |
285 | { | |
286 | // Get pointer to last valid chunk, preventing overflow on size calculations | |
287 | // The division followed by the multiplication just makes sure that | |
288 | // old == block + partition_sz * i, for some integer i, even if the | |
289 | // block size (sz) is not a multiple of the partition size. | |
290 | char * old = static_cast<char *>(block) | |
291 | + ((sz - partition_sz) / partition_sz) * partition_sz; | |
292 | ||
293 | // Set it to point to the end | |
294 | nextof(old) = end; | |
295 | ||
296 | // Handle border case where sz == partition_sz (i.e., we're handling an array | |
297 | // of 1 element) | |
298 | if (old == block) | |
299 | return block; | |
300 | ||
301 | // Iterate backwards, building a singly-linked list of pointers | |
302 | for (char * iter = old - partition_sz; iter != block; | |
303 | old = iter, iter -= partition_sz) | |
304 | nextof(iter) = old; | |
305 | ||
306 | // Point the first pointer, too | |
307 | nextof(block) = old; | |
308 | ||
309 | return block; | |
310 | } | |
311 | ||
312 | //! \pre (n > 0), (start != 0), (nextof(start) != 0) | |
313 | //! \post (start != 0) | |
314 | //! The function attempts to find n contiguous chunks | |
315 | //! of size partition_size in the free list, starting at start. | |
316 | //! If it succeds, it returns the last chunk in that contiguous | |
317 | //! sequence, so that the sequence is known by [start, {retval}] | |
318 | //! If it fails, it does do either because it's at the end of the | |
319 | //! free list or hits a non-contiguous chunk. In either case, | |
320 | //! it will return 0, and set start to the last considered | |
321 | //! chunk. You are at the end of the free list if | |
322 | //! nextof(start) == 0. Otherwise, start points to the last | |
323 | //! chunk in the contiguous sequence, and nextof(start) points | |
324 | //! to the first chunk in the next contiguous sequence (assuming | |
325 | //! an ordered free list). | |
326 | template <typename SizeType> | |
327 | void * simple_segregated_storage<SizeType>::try_malloc_n( | |
328 | void * & start, size_type n, const size_type partition_size) | |
329 | { | |
330 | void * iter = nextof(start); | |
331 | while (--n != 0) | |
332 | { | |
333 | void * next = nextof(iter); | |
334 | if (next != static_cast<char *>(iter) + partition_size) | |
335 | { | |
336 | // next == 0 (end-of-list) or non-contiguous chunk found | |
337 | start = iter; | |
338 | return 0; | |
339 | } | |
340 | iter = next; | |
341 | } | |
342 | return iter; | |
343 | } | |
344 | ||
345 | //! Attempts to find a contiguous sequence of n partition_sz-sized chunks. If found, removes them | |
346 | //! all from the free list and returns a pointer to the first. If not found, returns 0. It is strongly | |
347 | //! recommended (but not required) that the free list be ordered, as this algorithm will fail to find | |
348 | //! a contiguous sequence unless it is contiguous in the free list as well. Order-preserving. | |
349 | //! O(N) with respect to the size of the free list. | |
350 | template <typename SizeType> | |
351 | void * simple_segregated_storage<SizeType>::malloc_n(const size_type n, | |
352 | const size_type partition_size) | |
353 | { | |
354 | BOOST_POOL_VALIDATE_INTERNALS | |
355 | if(n == 0) | |
356 | return 0; | |
357 | void * start = &first; | |
358 | void * iter; | |
359 | do | |
360 | { | |
361 | if (nextof(start) == 0) | |
362 | return 0; | |
363 | iter = try_malloc_n(start, n, partition_size); | |
364 | } while (iter == 0); | |
365 | void * const ret = nextof(start); | |
366 | nextof(start) = nextof(iter); | |
367 | BOOST_POOL_VALIDATE_INTERNALS | |
368 | return ret; | |
369 | } | |
370 | ||
371 | } // namespace boost | |
372 | ||
373 | #ifdef BOOST_MSVC | |
374 | #pragma warning(pop) | |
375 | #endif | |
376 | ||
377 | #endif |