/[svn]/linuxsampler/trunk/src/common/Pool.h
ViewVC logotype

Contents of /linuxsampler/trunk/src/common/Pool.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3548 - (show annotations) (download) (as text)
Wed Jul 31 09:35:10 2019 UTC (4 years, 7 months ago) by schoenebeck
File MIME type: text/x-c++hdr
File size: 38098 byte(s)
* Fixed compiler error in Pool.h.
* Fixed compiler errors in test cases.
* Updated README for how to compile & run test cases.
* Updated test case
  MutexTest::testDoubleLockStillBlocksConcurrentThread() to latest
  expected behaviour of the Mutex class implementation (recursive
  mutex type).
* Bumped version (2.1.1.svn1).

1 /***************************************************************************
2 * *
3 * LinuxSampler - modular, streaming capable sampler *
4 * *
5 * Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck *
6 * Copyright (C) 2005 - 2019 Christian Schoenebeck *
7 * *
8 * This program is free software; you can redistribute it and/or modify *
9 * it under the terms of the GNU General Public License as published by *
10 * the Free Software Foundation; either version 2 of the License, or *
11 * (at your option) any later version. *
12 * *
13 * This program is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16 * GNU General Public License for more details. *
17 * *
18 * You should have received a copy of the GNU General Public License *
19 * along with this program; if not, write to the Free Software *
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
21 * MA 02111-1307 USA *
22 ***************************************************************************/
23
24 #ifndef __LS_POOL_H__
25 #define __LS_POOL_H__
26
27 #ifdef HAVE_CONFIG_H
28 # include <config.h>
29 #endif
30
31 // we just use exceptions for debugging, better not in the final realtime thread !
32 #ifndef CONFIG_RT_EXCEPTIONS
33 # define CONFIG_RT_EXCEPTIONS 0
34 #endif
35
36 #if CONFIG_RT_EXCEPTIONS
37 # include <stdexcept>
38 # include <string>
39 #endif // CONFIG_RT_EXCEPTIONS
40
41 #include <iostream>
42
43 #if CONFIG_DEVMODE
44 # include <string>
45 # include <stdexcept>
46 const std::string __err_msg_iterator_invalidated = "Pool/RTList iterator invalidated";
47 #endif // CONFIG_DEVMODE
48
49 const std::string __err_msg_resize_while_in_use = "Pool::resizePool() ERROR: elements still in use!";
50
51 /**
52 * Unique numeric ID for exactly one incarnation of one element allocated from
53 * a Pool. As soon as the respective element is once freed back to the Pool,
54 * the ID becomes invalid. Such an ID may be used to safely store an abstract
55 * reference to one Pool element for longer time. Since the Pool classes
56 * automatically detect whether an ID became invalid, using such an ID is thus
57 * safer than storing an Iterator or even a raw pointer in use case scenarios of
58 * storing long term references to Pool elements.
59 *
60 * This ID type is currently set (constrained) to 32-bit because the current
61 * real-time instrument script infrastructure implementation, which heavily
62 * relies on element IDs, is currently using 32-bit for its integer script
63 * variable type.
64 */
65 typedef uint32_t pool_element_id_t;
66
67 // just symbol prototyping
68 template<typename T> class Pool;
69 template<typename T> class RTList;
70
71 template<typename T>
72 class RTListBase {
73 protected:
74 template<typename T1>
75 struct _Node {
76 _Node<T1>* next;
77 _Node<T1>* prev;
78 T1* data;
79 #if CONFIG_DEVMODE
80 RTListBase<T1>* list; // list to which this node currently belongs to
81 #endif // CONFIG_DEVMODE
82 uint reincarnation; // just for Pool::fromID()
83
84 _Node() {
85 next = NULL;
86 prev = NULL;
87 data = NULL;
88 #if CONFIG_DEVMODE
89 list = NULL;
90 #endif // CONFIG_DEVMODE
91 reincarnation = 0;
92 }
93
94 inline void bumpReincarnation(uint bits) {
95 reincarnation++;
96 // constrain the bitrange of "reincarnation", because Pool::fromID() will shift up/down for pool_element_id_t and compare this bitwise
97 reincarnation &= ((1 << bits) - 1);
98 }
99 };
100 typedef _Node<T> Node;
101
102 public:
103 /**
104 * Pointer-like object which allows to iterate over elements of a RTList,
105 * similar to iterators of STL container classes. Note that the main
106 * purpose of this class is to access elements of a list / pool i.e.
107 * within a @c while() loop. If you rather want to keep a reference to
108 * one particular element (i.e. for longer time) then you might
109 * consider using @c pool_element_id_t variables instead.
110 */
111 template<typename T1>
112 class _Iterator {
113 public:
114 _Iterator() {
115 current = NULL;
116 fallback = NULL;
117 #if CONFIG_DEVMODE
118 list = NULL;
119 #endif // CONFIG_DEVMODE
120 }
121
122 /// prefix increment op.
123 inline _Iterator& operator++() {
124 #if CONFIG_DEVMODE
125 if (!isValid()) {
126 #if CONFIG_RT_EXCEPTIONS
127 throw std::runtime_error(__err_msg_iterator_invalidated);
128 #else
129 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
130 return *(_Iterator*)NULL; // force segfault if iterator became invalidated
131 #endif // CONFIG_RT_EXCEPTIONS
132 }
133 #endif // CONFIG_DEVMODE
134 fallback = current;
135 current = current->next;
136 return *this;
137 }
138
139 /// postfix increment op.
140 inline _Iterator operator++(int) {
141 _Iterator preval = *this;
142 ++*this; // use prefix operator implementation
143 return preval;
144 }
145
146 /// prefix decrement op.
147 inline _Iterator& operator--() {
148 #if CONFIG_DEVMODE
149 if (!isValid()) {
150 #if CONFIG_RT_EXCEPTIONS
151 throw std::runtime_error(__err_msg_iterator_invalidated);
152 #else
153 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
154 return *(_Iterator*)NULL; // force segfault if iterator became invalidated
155 #endif // CONFIG_RT_EXCEPTIONS
156 }
157 #endif // CONFIG_DEVMODE
158 fallback = current;
159 current = current->prev;
160 return *this;
161 }
162
163 /// postfix decrement op.
164 inline _Iterator operator--(int) {
165 _Iterator preval = *this;
166 --*this; // use prefix operator implementation
167 return preval;
168 }
169
170 inline T1& operator*() {
171 #if CONFIG_DEVMODE
172 if (!isValid()) { // if iterator became invalidated
173 #if CONFIG_RT_EXCEPTIONS
174 throw std::runtime_error(__err_msg_iterator_invalidated);
175 #else
176 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
177 return *((T1*)NULL); // force segfault if iterator became invalidated
178 #endif // CONFIG_RT_EXCEPTIONS
179 }
180 #endif // CONFIG_DEVMODE
181 return *current->data;
182 }
183
184 inline const T1& operator*() const {
185 #if CONFIG_DEVMODE
186 if (!isValid()) { // if iterator became invalidated
187 #if CONFIG_RT_EXCEPTIONS
188 throw std::runtime_error(__err_msg_iterator_invalidated);
189 #else
190 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
191 return *((const T1*)NULL); // force segfault if iterator became invalidated
192 #endif // CONFIG_RT_EXCEPTIONS
193 }
194 #endif // CONFIG_DEVMODE
195 return *current->data;
196 }
197
198 inline T1* operator->() {
199 #if CONFIG_DEVMODE
200 if (!isValid()) { // if iterator became invalidated
201 #if CONFIG_RT_EXCEPTIONS
202 throw std::runtime_error(__err_msg_iterator_invalidated);
203 #else
204 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
205 return (T1*)NULL; // force segfault if iterator became invalidated
206 #endif // CONFIG_RT_EXCEPTIONS
207 }
208 #endif // CONFIG_DEVMODE
209 return current->data;
210 }
211
212 inline const T1* operator->() const {
213 #if CONFIG_DEVMODE
214 if (!isValid()) { // if iterator became invalidated
215 #if CONFIG_RT_EXCEPTIONS
216 throw std::runtime_error(__err_msg_iterator_invalidated);
217 #else
218 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
219 return (const T1*)NULL; // force segfault if iterator became invalidated
220 #endif // CONFIG_RT_EXCEPTIONS
221 }
222 #endif // CONFIG_DEVMODE
223 return current->data;
224 }
225
226 inline bool operator==(const _Iterator<T1> other) const {
227 return current == other.current;
228 }
229
230 inline bool operator!=(const _Iterator<T1> other) const {
231 return current != other.current;
232 }
233
234 inline operator bool() const {
235 return current && current->data;
236 }
237
238 inline bool operator!() const {
239 return !(current && current->data);
240 }
241
242 /**
243 * Moves the element pointed by this Iterator from its current
244 * list to the beginning of the destination list @a pDstList.
245 *
246 * @b CAUTION: When this method returns, this Iterator does
247 * @b NOT point to the element on the new list anymore, instead it
248 * points at a completely different element! In case of a
249 * forward Iterator this Iterator object will point to the
250 * previous element on the source list, in case of a backward
251 * Iterator it will point to the subsequent element on the
252 * source list. This behavior is enforced to avoid breaking an
253 * active loop code working with this Iterator object.
254 *
255 * Thus if you intend to continue working with the same element,
256 * you should do like this:
257 * @code
258 * it = it.moveToEndOf(anotherList);
259 * @endcode
260 *
261 * @param pDstList - destination list
262 * @returns Iterator object pointing at the moved element on
263 * the destination list
264 */
265 inline _Iterator moveToEndOf(RTListBase<T1>* pDstList) {
266 detach();
267 pDstList->append(*this);
268 _Iterator iterOnDstList = _Iterator(current);
269 current = fallback;
270 return iterOnDstList;
271 }
272
273 /**
274 * Moves the element pointed by this Iterator from its current
275 * list to the end of destination list @a pDstList.
276 *
277 * @b CAUTION: When this method returns, this Iterator does
278 * @b NOT point to the element on the new list anymore, instead it
279 * points at a completely different element! In case of a
280 * forward Iterator this Iterator object will point to the
281 * previous element on the source list, in case of a backward
282 * Iterator it will point to the subsequent element on the
283 * source list. This behavior is enforced to avoid breaking an
284 * active loop code working with this Iterator object.
285 *
286 * Thus if you intend to continue working with the same element,
287 * you should do like this:
288 * @code
289 * it = it.moveToBeginOf(anotherList);
290 * @endcode
291 *
292 * @param pDstList - destination list
293 * @returns Iterator object pointing at the moved element on
294 * the destination list
295 */
296 inline _Iterator moveToBeginOf(RTListBase<T1>* pDstList) {
297 detach();
298 pDstList->prepend(*this);
299 _Iterator iterOnDstList = _Iterator(current);
300 current = fallback;
301 return iterOnDstList;
302 }
303
304 /**
305 * Moves the element pointed by this Iterator from its current
306 * position to the position right before @a itDst. That move
307 * may either be from and to the same list, or to a another
308 * list.
309 *
310 * @b CAUTION: When this method returns, this Iterator does
311 * @b NOT point to the element on the new list anymore, instead it
312 * points at a completely different element! In case of a
313 * forward Iterator this Iterator object will point to the
314 * previous element on the source list, in case of a backward
315 * Iterator it will point to the subsequent element on the
316 * source list. This behavior is enforced to avoid breaking an
317 * active loop code working with this Iterator object.
318 *
319 * Thus if you intend to continue working with the same element,
320 * you should do like this:
321 * @code
322 * itSourceElement = itSourceElement.moveBefore(itDestinationElement);
323 * @endcode
324 *
325 * @param itDst - destination element to be inserted before
326 * @returns Iterator object pointing at the moved element on
327 * the destination list
328 */
329 inline _Iterator moveBefore(_Iterator<T1> itDst) {
330 detach();
331 RTList<T1>::prependBefore(*this, itDst);
332 _Iterator iterOnDstList = _Iterator(current);
333 current = fallback;
334 return iterOnDstList;
335 }
336
337 /**
338 * Moves the element pointed by this Iterator from its current
339 * position to the position right after @a itDst. That move
340 * may either be from and to the same list, or to a another
341 * list.
342 *
343 * @b CAUTION: When this method returns, this Iterator does
344 * @b NOT point to the element on the new list anymore, instead it
345 * points at a completely different element! In case of a
346 * forward Iterator this Iterator object will point to the
347 * previous element on the source list, in case of a backward
348 * Iterator it will point to the subsequent element on the
349 * source list. This behavior is enforced to avoid breaking an
350 * active loop code working with this Iterator object.
351 *
352 * Thus if you intend to continue working with the same element,
353 * you should do like this:
354 * @code
355 * itSourceElement = itSourceElement.moveAfter(itDestinationElement);
356 * @endcode
357 *
358 * @param itDst - destination element to be inserted after
359 * @returns Iterator object pointing at the moved element on
360 * the destination list
361 */
362 inline _Iterator moveAfter(_Iterator<T1> itDst) {
363 detach();
364 RTList<T1>::appendAfter(*this, itDst);
365 _Iterator iterOnDstList = _Iterator(current);
366 current = fallback;
367 return iterOnDstList;
368 }
369
370 #if CONFIG_DEVMODE
371 inline bool isValid() const {
372 return current->list == list;
373 }
374 #endif // CONFIG_DEVMODE
375
376 protected:
377 Node* current;
378 Node* fallback;
379 enum dir_t {
380 dir_forward,
381 dir_backward
382 };
383 #if CONFIG_DEVMODE
384 RTListBase<T1>* list;
385 #endif // CONFIG_DEVMODE
386
387 _Iterator(Node* pNode, dir_t direction = dir_forward) {
388 current = pNode;
389 fallback = (direction == dir_forward) ? pNode->prev : pNode->next;
390 #if CONFIG_DEVMODE
391 list = pNode->list;
392 #endif // CONFIG_DEVMODE
393 }
394
395 inline Node* node() {
396 #if CONFIG_DEVMODE
397 #if CONFIG_RT_EXCEPTIONS
398 if (isValid()) return current;
399 else throw std::runtime_error(__err_msg_iterator_invalidated);
400 #else
401 return (isValid()) ? current : (Node*)NULL; // force segfault if iterator became invalidated
402 #endif // CONFIG_RT_EXCEPTIONS
403 #else
404 return current;
405 #endif // CONFIG_DEVMODE
406 }
407
408 inline const Node* node() const {
409 #if CONFIG_DEVMODE
410 #if CONFIG_RT_EXCEPTIONS
411 if (isValid()) return current;
412 else throw std::runtime_error(__err_msg_iterator_invalidated);
413 #else
414 return (isValid()) ? current : (const Node*)NULL; // force segfault if iterator became invalidated
415 #endif // CONFIG_RT_EXCEPTIONS
416 #else
417 return current;
418 #endif // CONFIG_DEVMODE
419 }
420
421 inline void detach() {
422 RTListBase<T1>::detach(*this);
423 }
424
425 friend class RTListBase<T1>;
426 friend class RTList<T1>;
427 friend class Pool<T1>;
428 };
429 typedef _Iterator<T> Iterator;
430
431 inline Iterator first() {
432 return Iterator(_begin.next, Iterator::dir_forward);
433 }
434
435 inline Iterator last() {
436 return Iterator(_end.prev, Iterator::dir_backward);
437 }
438
439 inline Iterator begin() {
440 return Iterator(&_begin, Iterator::dir_forward);
441 }
442
443 inline Iterator end() {
444 return Iterator(&_end, Iterator::dir_backward);
445 }
446
447 inline bool isEmpty() const {
448 return _begin.next == &_end;
449 }
450
451 inline int count() {
452 int elements = 0;
453 for (Iterator it = first(); it != end(); ++it) ++elements;
454 return elements;
455 }
456
457 protected:
458 Node _begin; // fake node (without data) which represents the begin of the list - not the first element!
459 Node _end; // fake node (without data) which represents the end of the list - not the last element!
460
461 RTListBase() {
462 init();
463 }
464
465 void init() {
466 // initialize boundary nodes
467 _begin.prev = &_begin;
468 _begin.next = &_end;
469 _begin.data = NULL;
470 _end.next = &_end;
471 _end.prev = &_begin;
472 _end.data = NULL;
473 #if CONFIG_DEVMODE
474 _begin.list = this;
475 _end.list = this;
476 #endif // CONFIG_DEVMODE
477 }
478
479 inline void append(Iterator itElement) {
480 Node* pNode = itElement.current;
481 Node* last = _end.prev;
482 last->next = pNode;
483 pNode->prev = last; // if a segfault happens here, then because 'itElement' Iterator became invalidated
484 pNode->next = &_end;
485 _end.prev = pNode;
486 #if CONFIG_DEVMODE
487 pNode->list = this;
488 #endif // CONFIG_DEVMODE
489 }
490
491 inline void append(Iterator itFirst, Iterator itLast) {
492 Node* pFirst = itFirst.current;
493 Node* pLast = itLast.current;
494 Node* last = _end.prev;
495 last->next = pFirst;
496 pFirst->prev = last; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
497 pLast->next = &_end; // if a segfault happens here, then because 'itLast' Iterator became invalidated
498 _end.prev = pLast;
499 #if CONFIG_DEVMODE
500 for (Node* pNode = pFirst; true; pNode = pNode->next) {
501 pNode->list = this;
502 if (pNode == pLast) break;
503 }
504 #endif // CONFIG_DEVMODE
505 }
506
507 inline void prepend(Iterator itElement) {
508 Node* pNode = itElement.current;
509 Node* first = _begin.next;
510 _begin.next = pNode;
511 pNode->prev = &_begin; // if a segfault happens here, then because 'itElement' Iterator became invalidated
512 pNode->next = first;
513 first->prev = pNode;
514 #if CONFIG_DEVMODE
515 pNode->list = this;
516 #endif // CONFIG_DEVMODE
517 }
518
519 inline void prepend(Iterator itFirst, Iterator itLast) {
520 Node* pFirst = itFirst.current;
521 Node* pLast = itLast.current;
522 Node* first = _begin.next;
523 _begin.next = pFirst;
524 pFirst->prev = &_begin; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
525 pLast->next = first; // if a segfault happens here, then because 'itLast' Iterator became invalidated
526 first->prev = pLast;
527 #if CONFIG_DEVMODE
528 for (Node* pNode = pFirst; true; pNode = pNode->next) {
529 pNode->list = this;
530 if (pNode == pLast) break;
531 }
532 #endif // CONFIG_DEVMODE
533 }
534
535 static inline void prependBefore(Iterator itSrc, Iterator itDst) {
536 Node* src = itSrc.current;
537 Node* dst = itDst.current;
538 Node* prev = dst->prev;
539 prev->next = src;
540 dst->prev = src;
541 src->prev = prev;
542 src->next = dst;
543 #if CONFIG_DEVMODE
544 src->list = dst->list;
545 #endif // CONFIG_DEVMODE
546 }
547
548 static inline void appendAfter(Iterator itSrc, Iterator itDst) {
549 Node* src = itSrc.current;
550 Node* dst = itDst.current;
551 Node* next = dst->next;
552 next->prev = src;
553 dst->next = src;
554 src->prev = dst;
555 src->next = next;
556 #if CONFIG_DEVMODE
557 src->list = dst->list;
558 #endif // CONFIG_DEVMODE
559 }
560
561 static inline void detach(Iterator itElement) {
562 Node* pNode = itElement.node();
563 Node* prev = pNode->prev; // if a segfault happens here, then because 'itElement' Iterator became invalidated
564 Node* next = pNode->next;
565 prev->next = next;
566 next->prev = prev;
567 }
568
569 static inline void detach(Iterator itFirst, Iterator itLast) {
570 Node* prev = itFirst.node()->prev; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
571 Node* next = itLast.node()->next; // if a segfault happens here, then because 'itLast' Iterator became invalidated
572 prev->next = next;
573 next->prev = prev;
574 }
575
576 friend class _Iterator<T>;
577 friend class RTList<T>;
578 friend class Pool<T>;
579 };
580
581 template<typename T>
582 class RTList : public RTListBase<T> {
583 public:
584 typedef typename RTListBase<T>::Node Node;
585 typedef typename RTListBase<T>::Iterator Iterator;
586
587 /**
588 * Constructor
589 *
590 * @param pPool - pool this list uses for allocation and
591 * deallocation of elements
592 */
593 RTList(Pool<T>* pPool) : RTListBase<T>::RTListBase() {
594 this->pPool = pPool;
595 }
596
597 /**
598 * Copy constructor
599 */
600 RTList(RTList<T>& list) : RTListBase<T>::RTListBase() {
601 this->pPool = list.pPool;
602 Iterator it = list.first();
603 Iterator end = list.end();
604 for(; it != end; ++it) {
605 if (poolIsEmpty()) break;
606 *(allocAppend()) = *it;
607 }
608 }
609
610 virtual ~RTList() {
611 clear();
612 }
613
614 inline bool poolIsEmpty() const {
615 return pPool->poolIsEmpty();
616 }
617
618 inline Iterator allocAppend() {
619 if (pPool->poolIsEmpty()) return RTListBase<T>::begin();
620 Iterator element = pPool->alloc();
621 this->append(element);
622 #if CONFIG_DEVMODE
623 element.list = this;
624 #endif // CONFIG_DEVMODE
625 return element;
626 }
627
628 inline Iterator allocPrepend() {
629 if (pPool->poolIsEmpty()) return RTListBase<T>::end();
630 Iterator element = pPool->alloc();
631 this->prepend(element);
632 #if CONFIG_DEVMODE
633 element.list = this;
634 #endif // CONFIG_DEVMODE
635 return element;
636 }
637
638 inline void free(Iterator& itElement) {
639 itElement.detach();
640 pPool->freeToPool(itElement);
641 itElement.current = itElement.fallback;
642 }
643
644 inline void clear() {
645 if (!RTListBase<T>::isEmpty()) {
646 Node* first = RTListBase<T>::_begin.next;
647 Node* last = RTListBase<T>::_end.prev;
648 RTListBase<T>::detach(first, last);
649 pPool->freeToPool(first, last);
650 }
651 }
652
653 inline pool_element_id_t getID(const T* obj) const {
654 return pPool->getID(obj);
655 }
656
657 inline pool_element_id_t getID(const Iterator& it) const {
658 return pPool->getID(&*it);
659 }
660
661 inline Iterator fromID(pool_element_id_t id) const {
662 return pPool->fromID(id);
663 }
664
665 inline Iterator fromPtr(const T* obj) const {
666 return pPool->fromPtr(obj);
667 }
668
669 protected:
670 Pool<T>* pPool;
671 };
672
673 template<typename T>
674 class Pool : public RTList<T> {
675 public:
676 typedef typename RTList<T>::Node Node;
677 typedef typename RTList<T>::Iterator Iterator;
678
679 Node* nodes;
680 T* data;
681 RTListBase<T> freelist; // not yet allocated elements
682 uint poolsize;
683 // following 3 used for element ID generation (and vice versa)
684 uint poolsizebits; ///< Amount of bits required to index all elements of this pool (according to current pool size).
685 uint reservedbits; ///< 3rd party reserved bits on the left side of id (default: 0).
686 uint reincarnationbits; ///< Amount of bits allowed for reincarnation counter.
687
688 Pool(int Elements) : RTList<T>::RTList(this), reservedbits(0) {
689 _init(Elements);
690 }
691
692 virtual ~Pool() {
693 if (nodes) delete[] nodes;
694 if (data) delete[] data;
695 }
696
697 /**
698 * Returns true if there is at least one free element that could be
699 * allocated from the pool with i.e. allocAppend() or allocPreprend().
700 *
701 * @see poolHasFreeElements()
702 */
703 inline bool poolIsEmpty() const {
704 return freelist.isEmpty();
705 }
706
707 /**
708 * Returns true if at least the requested amount of free @a elements is
709 * currently available for being allocated from the pool with i.e.
710 * allocAppend() or allocPreprend().
711 *
712 * @see poolIsEmpty()
713 */
714 bool poolHasFreeElements(int elements) {
715 for (Iterator it = freelist.first(); it != freelist.end() && elements >= 0; ++it)
716 --elements;
717 return elements <= 0;
718 }
719
720 int countFreeElements() {
721 return freelist.count();
722 }
723
724 /**
725 * Returns the current size of the pool, that is the amount of
726 * pre-allocated elements from the operating system. It equals the
727 * amount of elements given to the constructor unless resizePool()
728 * is called.
729 *
730 * @see resizePool()
731 */
732 uint poolSize() const {
733 return poolsize;
734 }
735
736 /**
737 * Alters the amount of elements to be pre-allocated from the
738 * operating system for this pool object.
739 *
740 * @e CAUTION: you MUST free all elements in use before calling this
741 * method ( e.g. by calling clear() )! Also make sure that no
742 * references of elements before this call will still be used after this
743 * call, since all elements will be reallocated and their old memory
744 * addresses become invalid!
745 *
746 * @see poolSize()
747 */
748 void resizePool(int Elements) {
749 if (freelist.count() != poolsize) {
750 #if CONFIG_DEVMODE
751 throw std::runtime_error(__err_msg_resize_while_in_use);
752 #else
753 std::cerr << __err_msg_resize_while_in_use << std::endl << std::flush;
754 // if we're here something's terribly wrong, but we try to do the best
755 RTList<T>::clear();
756 #endif
757 }
758 if (nodes) delete[] nodes;
759 if (data) delete[] data;
760 freelist.init();
761 RTListBase<T>::init();
762 _init(Elements);
763 }
764
765 /**
766 * Sets the amount of bits on the left hand side of pool_element_id_t
767 * numbers to be reserved for 3rd party usage. So if you pass @c 1 for
768 * argument @a bits for example, then all generated element IDs will be
769 * maximum 31 bit large.
770 *
771 * By default there are no reserved bits, and thus by default all IDs
772 * are max. 32 bit large.
773 *
774 * @param bits - amount of bits to reserve on every ID for other purposes
775 * @see pool_element_id_t
776 */
777 void setPoolElementIDsReservedBits(uint bits) {
778 reservedbits = bits;
779 updateReincarnationBits();
780 }
781
782 /**
783 * Returns an abstract, unique numeric ID for the given object of
784 * this pool, it returns 0 in case the passed object is not a member
785 * of this Pool, i.e. because it is simply an invalid pointer or member
786 * of another Pool. The returned ID is unique among all elements of this
787 * Pool and it differs with each reincarnation of an object. That means
788 * each time you free an element to and allocate the same element back
789 * from the Pool, it will have a different ID.
790 *
791 * A valid ID will never be zero, so you may use ID values of 0 in your
792 * data structures for special purposes (i.e. reflecting an invalid
793 * object ID or not yet assigned object).
794 *
795 * Members are always translated both, from Iterators/pointers to IDs,
796 * and from IDs to Iterators/pointers in constant time.
797 *
798 * You might want to use this alternative approach of referencing Pool
799 * members under certain scenarios. For example if you need to expose
800 * an ID to the end user and/or if you want to represent an object of
801 * this pool by a smaller number instead of a native pointer (i.e. 16
802 * bits vs. 64 bits). You can also detect this way whether the object
803 * has already been freed / reallocated from the Pool in the meantime.
804 *
805 * @param obj - raw pointer to a data member of this Pool
806 * @returns unique numeric ID (!= 0) of @a obj or 0 if pointer was invalid
807 */
808 pool_element_id_t getID(const T* obj) const {
809 if (!poolsize) return 0;
810 int index = int( obj - &data[0] );
811 if (index < 0 || index >= poolsize) return 0;
812 return ((nodes[index].reincarnation << poolsizebits) | index) + 1;
813 }
814
815 /**
816 * Overridden convenience method, behaves like the method above.
817 */
818 pool_element_id_t getID(const Iterator& it) const {
819 return getID(&*it);
820 }
821
822 /**
823 * Returns an Iterator object of the Pool data member reflected by the
824 * given abstract, unique numeric ID, it returns an invalid Iterator in
825 * case the ID is invalid or if the Pool's data element reflected by
826 * given ID was at least once released/freed back to the Pool in the
827 * meantime.
828 *
829 * Members are always translated both, from Iterators/pointers to IDs,
830 * and from IDs to Iterators/pointers in constant time.
831 *
832 * You might want to use this alternative approach of referencing Pool
833 * members under certain scenarios. For example if you need to expose
834 * an ID to the end user and/or if you want to represent an object of
835 * this pool by a smaller number instead of a native pointer (i.e. 16
836 * bits vs. 64 bits). You can also detect this way whether the object
837 * has already been freed / reallocated from the Pool in the meantime.
838 *
839 * @param id - unique ID (!= 0) of a Pool's data member
840 * @returns Iterator object pointing to Pool's data element, invalid
841 * Iterator in case ID was invalid or data element was freed
842 */
843 Iterator fromID(pool_element_id_t id) const {
844 //TODO: -1 check here is a relict from older versions of Pool.h, once it is certain that no existing code base is still using -1 for "invalid" Pool elements then this -1 check can be removed
845 if (id == 0 || id == -1) return Iterator(); // invalid iterator
846 id--;
847 const uint bits = poolsizebits;
848 uint index = id & ((1 << bits) - 1);
849 if (index >= poolsize) return Iterator(); // invalid iterator
850 Node* node = &nodes[index];
851 uint reincarnation = id >> bits;
852 if (reincarnation != node->reincarnation) return Iterator(); // invalid iterator
853 return Iterator(node);
854 }
855
856 /**
857 * Returns an Iterator object for the object pointed by @a obj. This
858 * method will check whether the supplied object is actually part of
859 * this pool, and if it is not part of this pool an invalid Iterator is
860 * returned instead.
861 *
862 * @param obj - raw pointer to an object managed by this pool
863 * @returns Iterator object pointing to the supplied object, invalid
864 * Iterator in case object is not part of this pool
865 */
866 Iterator fromPtr(const T* obj) const {
867 if (!poolsize) return Iterator(); // invalid iterator
868 int index = int( obj - &data[0] );
869 if (index < 0 || index >= poolsize) return Iterator(); // invalid iterator
870 return Iterator(&nodes[index]);
871 }
872
873 protected:
874 // caution: assumes pool (that is freelist) is not empty!
875 inline Iterator alloc() {
876 Iterator element = freelist.last();
877 element.detach();
878 return element;
879 }
880
881 inline void freeToPool(Iterator itElement) {
882 itElement.node()->bumpReincarnation(reincarnationbits);
883 freelist.append(itElement);
884 }
885
886 inline void freeToPool(Iterator itFirst, Iterator itLast) {
887 for (Node* n = itFirst.node(); true; n = n->next) {
888 n->bumpReincarnation(reincarnationbits);
889 if (n == itLast.node()) break;
890 }
891 freelist.append(itFirst, itLast);
892 }
893
894 friend class RTList<T>;
895
896 private:
897 void _init(int Elements) {
898 data = new T[Elements];
899 nodes = new Node[Elements];
900 for (int i = 0; i < Elements; i++) {
901 nodes[i].data = &data[i];
902 freelist.append(&nodes[i]);
903 }
904 poolsize = Elements;
905 poolsizebits = bitsForSize(poolsize + 1); // +1 here just because IDs are always incremented by one (to avoid them ever being zero)
906 updateReincarnationBits();
907 }
908
909 inline void updateReincarnationBits() {
910 reincarnationbits = sizeof(pool_element_id_t) * 8 - poolsizebits - reservedbits;
911 }
912
913 inline static int bitsForSize(int size) {
914 if (!size) return 0;
915 size--;
916 int bits = 0;
917 for (; size > 1; bits += 2, size >>= 2);
918 return bits + size;
919 }
920 };
921
922 #endif // __LS_POOL_H__

  ViewVC Help
Powered by ViewVC