1 | /* -*- c++ -*- |
---|
2 | |
---|
3 | C++ Indexable objects pool |
---|
4 | |
---|
5 | This file is part of the dpp library of C++ template classes |
---|
6 | |
---|
7 | doc: http://diaxen.ssji.net/dpp/index.html |
---|
8 | repo: https://www.ssji.net/svn/projets/trunk/libdpp |
---|
9 | |
---|
10 | This program is free software: you can redistribute it and/or |
---|
11 | modify it under the terms of the GNU Lesser General Public License |
---|
12 | as published by the Free Software Foundation, either version 3 of |
---|
13 | the License, or (at your option) any later version. |
---|
14 | |
---|
15 | This program is distributed in the hope that it will be useful, but |
---|
16 | WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
17 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
18 | Lesser General Public License for more details. |
---|
19 | |
---|
20 | You should have received a copy of the GNU Lesser General Public |
---|
21 | License along with this program. If not, see |
---|
22 | <http://www.gnu.org/licenses/>. |
---|
23 | |
---|
24 | (c) 2010 Alexandre Becoulet <alexandre.becoulet@free.fr> |
---|
25 | |
---|
26 | */ |
---|
27 | |
---|
28 | #ifndef DPP_VECTOR_POOL_HH_ |
---|
29 | #define DPP_VECTOR_POOL_HH_ |
---|
30 | |
---|
31 | #include <stdexcept> |
---|
32 | #include <memory> |
---|
33 | #include <vector> |
---|
34 | |
---|
35 | /** @file @module{Vector pool} */ |
---|
36 | |
---|
37 | namespace dpp { |
---|
38 | |
---|
39 | template <class X, unsigned int block_size = 32, |
---|
40 | class Allocator = std::allocator<X>, |
---|
41 | class PtrAllocator = std::allocator<X*> > |
---|
42 | class vector_pool; |
---|
43 | |
---|
44 | /** @short Vector pool iterator class |
---|
45 | @module {Vector pool} |
---|
46 | @header dpp/vector_pool |
---|
47 | @internal |
---|
48 | |
---|
49 | @This contains the iterator implementation for the @ref |
---|
50 | vector_pool class. |
---|
51 | */ |
---|
52 | template <typename P, typename E, int direction> /* FIXME rework iterator (more ops, copy, const, ...) */ |
---|
53 | class vector_pool_iterator |
---|
54 | { |
---|
55 | template <class, unsigned int, class, class> friend class vector_pool; |
---|
56 | template <class, class, int> friend class vector_pool_iterator; |
---|
57 | |
---|
58 | P *_pool; |
---|
59 | unsigned int _i; |
---|
60 | |
---|
61 | vector_pool_iterator (P *pool, unsigned int i) |
---|
62 | : _pool(pool), |
---|
63 | _i(i) |
---|
64 | { |
---|
65 | } |
---|
66 | |
---|
67 | public: |
---|
68 | |
---|
69 | typedef typename P::value_type value_type; |
---|
70 | typedef typename P::reference reference; |
---|
71 | typedef typename P::const_reference const_reference; |
---|
72 | typedef typename P::pointer pointer; |
---|
73 | typedef typename P::const_pointer const_pointer; |
---|
74 | typedef unsigned int size_type; |
---|
75 | typedef int difference_type; |
---|
76 | |
---|
77 | typedef std::bidirectional_iterator_tag iterator_category; |
---|
78 | |
---|
79 | vector_pool_iterator() |
---|
80 | { |
---|
81 | } |
---|
82 | |
---|
83 | template <class P_, class E_> |
---|
84 | vector_pool_iterator(const vector_pool_iterator<P_, E_, direction> &i) |
---|
85 | : _pool(i._pool), |
---|
86 | _i(i._i) |
---|
87 | { |
---|
88 | } |
---|
89 | |
---|
90 | inline E & operator*() |
---|
91 | { |
---|
92 | return (*_pool)[_i]; |
---|
93 | } |
---|
94 | |
---|
95 | inline E * operator->() |
---|
96 | { |
---|
97 | return &(*_pool)[_i]; |
---|
98 | } |
---|
99 | |
---|
100 | inline vector_pool_iterator & operator++() |
---|
101 | { |
---|
102 | _i += direction; |
---|
103 | return *this; |
---|
104 | } |
---|
105 | |
---|
106 | inline vector_pool_iterator operator++(int) |
---|
107 | { |
---|
108 | vector_pool_iterator tmp(*this); |
---|
109 | _i += direction; |
---|
110 | return tmp; |
---|
111 | } |
---|
112 | |
---|
113 | inline vector_pool_iterator & operator--() |
---|
114 | { |
---|
115 | _i -= direction; |
---|
116 | return *this; |
---|
117 | } |
---|
118 | |
---|
119 | inline vector_pool_iterator operator--(int) |
---|
120 | { |
---|
121 | vector_pool_iterator tmp(*this); |
---|
122 | _i -= direction; |
---|
123 | return tmp; |
---|
124 | } |
---|
125 | |
---|
126 | vector_pool_iterator operator-(int x) const |
---|
127 | { |
---|
128 | return vector_pool_iterator(_pool, _i - x * direction); |
---|
129 | } |
---|
130 | |
---|
131 | vector_pool_iterator operator+(int x) const |
---|
132 | { |
---|
133 | return vector_pool_iterator(_pool, _i + x * direction); |
---|
134 | } |
---|
135 | |
---|
136 | difference_type operator-(const vector_pool_iterator & i) const |
---|
137 | { |
---|
138 | return (_i - i._i) * direction; |
---|
139 | } |
---|
140 | |
---|
141 | inline bool operator<(const vector_pool_iterator &i) const |
---|
142 | { |
---|
143 | return _i < i._i; |
---|
144 | } |
---|
145 | |
---|
146 | inline bool operator==(const vector_pool_iterator &i) const |
---|
147 | { |
---|
148 | return _i == i._i; |
---|
149 | } |
---|
150 | |
---|
151 | inline bool operator!=(const vector_pool_iterator &i) const |
---|
152 | { |
---|
153 | return _i != i._i; |
---|
154 | } |
---|
155 | }; |
---|
156 | |
---|
157 | |
---|
158 | /** @short Indexable allocation pool |
---|
159 | @module {Vector pool} |
---|
160 | @header dpp/vector_pool |
---|
161 | @main |
---|
162 | @showvalue |
---|
163 | |
---|
164 | This class provides an indexable object allocation pool. The |
---|
165 | pool can be accessed and traversed like a @ref std::vector. |
---|
166 | Only the last or all objects in pool can be removed at once. |
---|
167 | |
---|
168 | The @ref create functions must be used to allocate and construct |
---|
169 | objects in pool. Unlike @ref std::vector this class does not |
---|
170 | require assignment operator to be available in the object class. |
---|
171 | |
---|
172 | The pool allocates storage blocks for multiple objects at once. |
---|
173 | The number of objects in a storage block can be specified as |
---|
174 | template parameter. Moreover a static storage space can be |
---|
175 | provided for first storage blocks when creating the pool. |
---|
176 | |
---|
177 | Unlike @ref std::vector, iterators and pointers to objects in |
---|
178 | the pool are not invalidated by allocation and elements in the |
---|
179 | pool are not stored at contiguous locations when crossing the @tt |
---|
180 | block_size boundary. |
---|
181 | |
---|
182 | The @tt Allocator and @tt PtrAllocator standard allocators |
---|
183 | parameters are used to allocate objects and manage vector of |
---|
184 | storage blocks respectively. |
---|
185 | */ |
---|
186 | template <class X, unsigned int block_size, |
---|
187 | class Allocator, class PtrAllocator> |
---|
188 | class vector_pool |
---|
189 | { |
---|
190 | vector_pool(const vector_pool &); |
---|
191 | const vector_pool & operator= (const vector_pool &); |
---|
192 | |
---|
193 | typedef std::vector<X *, PtrAllocator> block_list_t; |
---|
194 | |
---|
195 | block_list_t _blocks; |
---|
196 | size_t _free_count; |
---|
197 | size_t _static_size; |
---|
198 | Allocator _allocator; |
---|
199 | |
---|
200 | X * get_ptr(unsigned int i) const |
---|
201 | { |
---|
202 | return _blocks[i / block_size] + i % block_size; |
---|
203 | } |
---|
204 | |
---|
205 | X *alloc(size_t count = 1) |
---|
206 | { |
---|
207 | while (_free_count < count) |
---|
208 | add_block(); |
---|
209 | |
---|
210 | unsigned int id = _blocks.size() * block_size - _free_count; |
---|
211 | _free_count -= count; |
---|
212 | |
---|
213 | return get_ptr(id); |
---|
214 | } |
---|
215 | |
---|
216 | void add_block() |
---|
217 | { |
---|
218 | const void *hint = _blocks.empty() ? 0 : (const void*)_blocks.front(); |
---|
219 | X *b = (X*)_allocator.allocate(block_size, hint); |
---|
220 | |
---|
221 | _free_count += block_size; |
---|
222 | _blocks.push_back(b); |
---|
223 | } |
---|
224 | |
---|
225 | public: |
---|
226 | |
---|
227 | typedef X value_type; |
---|
228 | typedef X & reference; |
---|
229 | typedef const X & const_reference; |
---|
230 | typedef X * pointer; |
---|
231 | typedef const X * const_pointer; |
---|
232 | typedef unsigned int size_type; |
---|
233 | typedef int difference_type; |
---|
234 | typedef Allocator allocator_type; |
---|
235 | |
---|
236 | typedef vector_pool_iterator<vector_pool<X, block_size>, X, 1 > iterator; |
---|
237 | typedef vector_pool_iterator<const vector_pool<X, block_size>, const X, 1 > const_iterator; |
---|
238 | typedef vector_pool_iterator<vector_pool<X, block_size>, X, -1 > reverse_iterator; |
---|
239 | typedef vector_pool_iterator<const vector_pool<X, block_size>, const X, -1 > const_reverse_iterator; |
---|
240 | |
---|
241 | /** Storage space for a single block of objects in pool */ |
---|
242 | typedef unsigned char block_type[sizeof(X) * block_size]; |
---|
243 | |
---|
244 | /** @This creates a new pool with empty storage. */ |
---|
245 | vector_pool(const Allocator &a = Allocator(), |
---|
246 | const PtrAllocator &pa = PtrAllocator()) |
---|
247 | : _blocks(pa), |
---|
248 | _free_count(0), |
---|
249 | _static_size(0), |
---|
250 | _allocator(a) |
---|
251 | { |
---|
252 | } |
---|
253 | |
---|
254 | /** @This creates a new pool and provide static storage space for |
---|
255 | the first block. */ |
---|
256 | vector_pool(block_type &first, |
---|
257 | const Allocator &a = Allocator(), |
---|
258 | const PtrAllocator &pa = PtrAllocator()) |
---|
259 | : _blocks(pa), |
---|
260 | _free_count(block_size), |
---|
261 | _static_size(1), |
---|
262 | _allocator(a) |
---|
263 | { |
---|
264 | _blocks.push_back((X*)first); |
---|
265 | } |
---|
266 | |
---|
267 | /** @This creates a new pool and provide static storage space for |
---|
268 | multiple blocks. */ |
---|
269 | vector_pool(block_type block[], size_t count, |
---|
270 | const Allocator &a = Allocator(), |
---|
271 | const PtrAllocator &pa = PtrAllocator()) |
---|
272 | : _blocks(pa), |
---|
273 | _free_count(block_size * count), |
---|
274 | _static_size(count), |
---|
275 | _allocator(a) |
---|
276 | { |
---|
277 | for (unsigned int i = 0; i < count; i++) |
---|
278 | _blocks.push_back((X*)block[i]); |
---|
279 | } |
---|
280 | |
---|
281 | /** @This destroy pool along with contained objects */ |
---|
282 | ~vector_pool() |
---|
283 | { |
---|
284 | clear(); |
---|
285 | shrink(); |
---|
286 | } |
---|
287 | |
---|
288 | /** @This returns reference to object at given position in pool */ |
---|
289 | const X & operator[](unsigned int i) const |
---|
290 | { |
---|
291 | return *get_ptr(i); |
---|
292 | } |
---|
293 | |
---|
294 | /** @This returns reference to object at given position in pool */ |
---|
295 | X & operator[](unsigned int i) |
---|
296 | { |
---|
297 | return *get_ptr(i); |
---|
298 | } |
---|
299 | |
---|
300 | /** @This returns reference to object at given position in pool |
---|
301 | with bound checking */ |
---|
302 | const X & at(unsigned int i) const throw (std::out_of_range) |
---|
303 | { |
---|
304 | if (i >= size()) |
---|
305 | throw std::out_of_range("vector_pool access out of bounds"); |
---|
306 | return *get_ptr(i); |
---|
307 | } |
---|
308 | |
---|
309 | /** @This returns reference to object at given position in pool |
---|
310 | with bound checking */ |
---|
311 | X & at(unsigned int i) throw (std::out_of_range) |
---|
312 | { |
---|
313 | if (i >= size()) |
---|
314 | throw std::out_of_range("vector_pool access out of bounds"); |
---|
315 | return *get_ptr(i); |
---|
316 | } |
---|
317 | |
---|
318 | /** @This allocates and construct a new object in pool */ |
---|
319 | X &create() |
---|
320 | { |
---|
321 | return *new(alloc())X(); |
---|
322 | } |
---|
323 | |
---|
324 | X * create_array(size_t count) |
---|
325 | { |
---|
326 | X *t = alloc(count); |
---|
327 | for (unsigned int i = 0; i < count; i++) |
---|
328 | new(t + i)X(); |
---|
329 | return t; |
---|
330 | } |
---|
331 | |
---|
332 | #define _DPP_VECTOR_POOL_CREATE(a, b, ...) \ |
---|
333 | template <__VA_ARGS__> \ |
---|
334 | inline X &create a \ |
---|
335 | { \ |
---|
336 | return *new(alloc())X b; \ |
---|
337 | } |
---|
338 | |
---|
339 | #define _DPP_VECTOR_POOL_CREATE_ARRAY(a, b, ...) \ |
---|
340 | template <__VA_ARGS__> \ |
---|
341 | inline X * create_array a \ |
---|
342 | { \ |
---|
343 | X *t = alloc(count); \ |
---|
344 | for (unsigned int i = 0; i < count; i++) \ |
---|
345 | new(t + i)X b; \ |
---|
346 | return t; \ |
---|
347 | } |
---|
348 | |
---|
349 | /** @multiple |
---|
350 | @This allocates and construct a new object in pool. Parameters |
---|
351 | are passed to constructor. */ |
---|
352 | |
---|
353 | _DPP_VECTOR_POOL_CREATE((const P1 &p1), (p1), typename P1); |
---|
354 | |
---|
355 | _DPP_VECTOR_POOL_CREATE((const P1 &p1, const P2 &p2), (p1, p2), typename P1, typename P2); |
---|
356 | |
---|
357 | _DPP_VECTOR_POOL_CREATE((const P1 &p1, const P2 &p2, const P3 &p3), (p1, p2, p3), |
---|
358 | typename P1, typename P2, typename P3); |
---|
359 | |
---|
360 | _DPP_VECTOR_POOL_CREATE((const P1 &p1, const P2 &p2, const P3 &p3, |
---|
361 | const P4 &p4), |
---|
362 | (p1, p2, p3, p4), |
---|
363 | typename P1, typename P2, typename P3, |
---|
364 | typename P4); |
---|
365 | |
---|
366 | _DPP_VECTOR_POOL_CREATE((const P1 &p1, const P2 &p2, const P3 &p3, |
---|
367 | const P4 &p4, const P5 &p5), |
---|
368 | (p1, p2, p3, p4, p5), |
---|
369 | typename P1, typename P2, typename P3, |
---|
370 | typename P4, typename P5); |
---|
371 | |
---|
372 | _DPP_VECTOR_POOL_CREATE((const P1 &p1, const P2 &p2, const P3 &p3, |
---|
373 | const P4 &p4, const P5 &p5, const P6 &p6), |
---|
374 | (p1, p2, p3, p4, p5, p6), |
---|
375 | typename P1, typename P2, typename P3, |
---|
376 | typename P4, typename P5, typename P6); |
---|
377 | |
---|
378 | /** @multiple |
---|
379 | @This allocates and construct multiple objects in pool. Parameters |
---|
380 | are passed to constructor. */ |
---|
381 | |
---|
382 | _DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1), (p1), typename P1); |
---|
383 | |
---|
384 | _DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1, const P2 &p2), (p1, p2), typename P1, typename P2); |
---|
385 | |
---|
386 | _DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1, const P2 &p2, const P3 &p3), (p1, p2, p3), |
---|
387 | typename P1, typename P2, typename P3); |
---|
388 | |
---|
389 | _DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1, const P2 &p2, const P3 &p3, |
---|
390 | const P4 &p4), |
---|
391 | (p1, p2, p3, p4), |
---|
392 | typename P1, typename P2, typename P3, |
---|
393 | typename P4); |
---|
394 | |
---|
395 | _DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1, const P2 &p2, const P3 &p3, |
---|
396 | const P4 &p4, const P5 &p5), |
---|
397 | (p1, p2, p3, p4, p5), |
---|
398 | typename P1, typename P2, typename P3, |
---|
399 | typename P4, typename P5); |
---|
400 | |
---|
401 | _DPP_VECTOR_POOL_CREATE_ARRAY((size_t count, const P1 &p1, const P2 &p2, const P3 &p3, |
---|
402 | const P4 &p4, const P5 &p5, const P6 &p6), |
---|
403 | (p1, p2, p3, p4, p5, p6), |
---|
404 | typename P1, typename P2, typename P3, |
---|
405 | typename P4, typename P5, typename P6); |
---|
406 | |
---|
407 | /** @This removes last entry. It does not reduce |
---|
408 | allocated blocks count. @see shrink */ |
---|
409 | void pop_back() |
---|
410 | { |
---|
411 | unsigned int id = _blocks.size() * block_size - ++_free_count; |
---|
412 | |
---|
413 | get_ptr(id)->~X(); |
---|
414 | } |
---|
415 | |
---|
416 | /** @This destroys all objects in pool. It does not reduce |
---|
417 | allocated blocks count. @see shrink */ |
---|
418 | void clear() |
---|
419 | { |
---|
420 | int i; |
---|
421 | unsigned int j; |
---|
422 | |
---|
423 | for (i = _blocks.size() - 1; i >= 0; i--) |
---|
424 | { |
---|
425 | for (j = 0; j < block_size - _free_count % block_size; j++) |
---|
426 | _blocks[i][j].~X(); |
---|
427 | _free_count += j; |
---|
428 | } |
---|
429 | } |
---|
430 | |
---|
431 | /** @This frees unused storage blocks at end of pool. */ |
---|
432 | void shrink() |
---|
433 | { |
---|
434 | while (_blocks.size() > _static_size) |
---|
435 | { |
---|
436 | _allocator.deallocate(_blocks.back(), block_size); |
---|
437 | _blocks.pop_back(); |
---|
438 | _free_count -= block_size; |
---|
439 | } |
---|
440 | } |
---|
441 | |
---|
442 | /** @This allocates enough storage blocks to hold at least @tt |
---|
443 | count objects */ |
---|
444 | void reserve(size_t count) |
---|
445 | { |
---|
446 | while (capacity() < count) |
---|
447 | add_block(); |
---|
448 | } |
---|
449 | |
---|
450 | /** @This returns current live objects count in pool */ |
---|
451 | inline size_t size() const |
---|
452 | { |
---|
453 | return _blocks.size() * block_size - _free_count; |
---|
454 | } |
---|
455 | |
---|
456 | /** @This returns current allocated storage space in objects count unit */ |
---|
457 | inline size_t capacity() const |
---|
458 | { |
---|
459 | return _blocks.size() * block_size; |
---|
460 | } |
---|
461 | |
---|
462 | /** @This tests pool empty state */ |
---|
463 | inline bool empty() const |
---|
464 | { |
---|
465 | return size() == 0; |
---|
466 | } |
---|
467 | |
---|
468 | /** @This returns first object in pool */ |
---|
469 | inline const X & front() const |
---|
470 | { |
---|
471 | return *_blocks.front(); |
---|
472 | } |
---|
473 | |
---|
474 | /** @This returns first object in pool */ |
---|
475 | inline X & front() |
---|
476 | { |
---|
477 | return *_blocks.front(); |
---|
478 | } |
---|
479 | |
---|
480 | /** @This returns last object in pool */ |
---|
481 | inline const X & back() const |
---|
482 | { |
---|
483 | return *get_ptr(size() - 1); |
---|
484 | } |
---|
485 | |
---|
486 | /** @This returns last object in pool */ |
---|
487 | inline X & back() |
---|
488 | { |
---|
489 | return *get_ptr(size() - 1); |
---|
490 | } |
---|
491 | |
---|
492 | /** @This returns @ref iterator to first object in pool */ |
---|
493 | inline iterator begin() |
---|
494 | { |
---|
495 | return iterator(this, 0); |
---|
496 | } |
---|
497 | |
---|
498 | /** @This returns end @ref iterator */ |
---|
499 | inline iterator end() |
---|
500 | { |
---|
501 | return iterator(this, size()); |
---|
502 | } |
---|
503 | |
---|
504 | /** @This returns @ref const_iterator to first object in pool */ |
---|
505 | inline const_iterator begin() const |
---|
506 | { |
---|
507 | return const_iterator(this, 0); |
---|
508 | } |
---|
509 | |
---|
510 | /** @This returns end @ref const_iterator */ |
---|
511 | inline const_iterator end() const |
---|
512 | { |
---|
513 | return const_iterator(this, size()); |
---|
514 | } |
---|
515 | |
---|
516 | /** @This returns @ref reverse_iterator to last object in pool */ |
---|
517 | inline reverse_iterator rbegin() |
---|
518 | { |
---|
519 | return reverse_iterator(this, size() - 1); |
---|
520 | } |
---|
521 | |
---|
522 | /** @This returns end @ref reverse_iterator */ |
---|
523 | inline reverse_iterator rend() |
---|
524 | { |
---|
525 | return reverse_iterator(this, -1); |
---|
526 | } |
---|
527 | |
---|
528 | /** @This returns @ref const_reverse_iterator to first object in pool */ |
---|
529 | inline const_reverse_iterator rbegin() const |
---|
530 | { |
---|
531 | return const_reverse_iterator(this, size() - 1); |
---|
532 | } |
---|
533 | |
---|
534 | /** @This returns end @ref const_reverse_iterator */ |
---|
535 | inline const_reverse_iterator rend() const |
---|
536 | { |
---|
537 | return const_reverse_iterator(this, -1); |
---|
538 | } |
---|
539 | |
---|
540 | /** @This returns pool object allocator */ |
---|
541 | const allocator_type & get_allocator() const |
---|
542 | { |
---|
543 | return _allocator; |
---|
544 | } |
---|
545 | }; |
---|
546 | |
---|
547 | } |
---|
548 | |
---|
549 | #endif |
---|
550 | |
---|