/[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 3549 - (show annotations) (download) (as text)
Wed Jul 31 15:43:53 2019 UTC (13 months, 3 weeks ago) by schoenebeck
File MIME type: text/x-c++hdr
File size: 38158 byte(s)
- Fixed another compiler error in Pool.h.

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

  ViewVC Help
Powered by ViewVC