Line data Source code
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 0 : 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 0 : simple_segregated_storage()
97 0 : :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 0 : 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 0 : first = segregate(block, nsz, npartition_sz, first);
117 : BOOST_POOL_VALIDATE_INTERNALS
118 0 : }
119 :
120 : // Same preconditions as 'segregate'
121 : // Post: !empty()
122 0 : 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 0 : void * const loc = find_prev(block);
131 :
132 : // Place either at beginning or in middle/end
133 : if (loc == 0)
134 0 : add_block(block, nsz, npartition_sz);
135 : else
136 0 : nextof(loc) = segregate(block, nsz, npartition_sz, nextof(loc));
137 : BOOST_POOL_VALIDATE_INTERNALS
138 0 : }
139 :
140 : // default destructor.
141 :
142 0 : bool empty() const
143 : { //! \returns true only if simple_segregated_storage is empty.
144 : return (first == 0);
145 : }
146 :
147 0 : 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 0 : void * const ret = first;
153 :
154 : // Increment the "first" pointer to point to the next chunk.
155 0 : first = nextof(first);
156 : BOOST_POOL_VALIDATE_INTERNALS
157 : return ret;
158 : }
159 :
160 0 : 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 0 : nextof(chunk) = first;
166 0 : 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 0 : void * simple_segregated_storage<SizeType>::find_prev(void * const ptr)
254 : {
255 : // Handle border case.
256 0 : 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 0 : if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr))
264 : return iter;
265 :
266 0 : 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 0 : 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 0 : char * old = static_cast<char *>(block)
291 0 : + ((sz - partition_sz) / partition_sz) * partition_sz;
292 :
293 : // Set it to point to the end
294 0 : nextof(old) = end;
295 :
296 : // Handle border case where sz == partition_sz (i.e., we're handling an array
297 : // of 1 element)
298 0 : if (old == block)
299 : return block;
300 :
301 : // Iterate backwards, building a singly-linked list of pointers
302 0 : for (char * iter = old - partition_sz; iter != block;
303 : old = iter, iter -= partition_sz)
304 0 : nextof(iter) = old;
305 :
306 : // Point the first pointer, too
307 0 : nextof(block) = old;
308 :
309 0 : 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 0 : void * iter = nextof(start);
331 0 : while (--n != 0)
332 : {
333 0 : void * next = nextof(iter);
334 0 : 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 0 : void * simple_segregated_storage<SizeType>::malloc_n(const size_type n,
352 : const size_type partition_size)
353 : {
354 : BOOST_POOL_VALIDATE_INTERNALS
355 0 : if(n == 0)
356 : return 0;
357 0 : void * start = &first;
358 : void * iter;
359 : do
360 : {
361 0 : if (nextof(start) == 0)
362 : return 0;
363 0 : iter = try_malloc_n(start, n, partition_size);
364 0 : } while (iter == 0);
365 0 : void * const ret = nextof(start);
366 0 : nextof(start) = nextof(iter);
367 : BOOST_POOL_VALIDATE_INTERNALS
368 0 : return ret;
369 : }
370 :
371 : } // namespace boost
372 :
373 : #ifdef BOOST_MSVC
374 : #pragma warning(pop)
375 : #endif
376 :
377 : #endif
|
