/[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 3054 - (show annotations) (download) (as text)
Thu Dec 15 12:47:45 2016 UTC (7 years, 3 months ago) by schoenebeck
File MIME type: text/x-c++hdr
File size: 37227 byte(s)
* Fixed numerous compiler warnings.
* Bumped version (2.0.0.svn32).

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

  ViewVC Help
Powered by ViewVC