/[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 2598 - (show annotations) (download) (as text)
Fri Jun 6 12:38:54 2014 UTC (9 years, 9 months ago) by schoenebeck
File MIME type: text/x-c++hdr
File size: 25845 byte(s)
* ScriptVM (WIP): Built-in script function "play_note()" now returns the
  event ID of the triggered note.
* ScriptVM (WIP): Implemented built-in script int variable $EVENT_ID.
* ScriptVM (WIP): Implemented built-in script function "ignore_event()".
* ScriptVM (WIP): Implemented built-in script function
  "ignore_controller()" (accepts one and no argument).
* Bumped version (1.0.0.svn44).

1 /***************************************************************************
2 * *
3 * LinuxSampler - modular, streaming capable sampler *
4 * *
5 * Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck *
6 * Copyright (C) 2005 - 2014 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 // just symbol prototyping
50 template<typename T> class Pool;
51 template<typename T> class RTList;
52
53 template<typename T>
54 class RTListBase {
55 protected:
56 template<typename T1>
57 struct _Node {
58 _Node<T1>* next;
59 _Node<T1>* prev;
60 T1* data;
61 #if CONFIG_DEVMODE
62 RTListBase<T1>* list; // list to which this node currently belongs to
63 #endif // CONFIG_DEVMODE
64 int reincarnation; // just for Pool::fromID()
65
66 _Node() {
67 next = NULL;
68 prev = NULL;
69 data = NULL;
70 #if CONFIG_DEVMODE
71 list = NULL;
72 #endif // CONFIG_DEVMODE
73 reincarnation = 0;
74 }
75 };
76 typedef _Node<T> Node;
77
78 public:
79 template<typename T1>
80 class _Iterator {
81 public:
82 _Iterator() {
83 current = NULL;
84 fallback = NULL;
85 #if CONFIG_DEVMODE
86 list = NULL;
87 #endif // CONFIG_DEVMODE
88 }
89
90 /// prefix increment op.
91 inline _Iterator& operator++() {
92 #if CONFIG_DEVMODE
93 if (!isValid()) {
94 #if CONFIG_RT_EXCEPTIONS
95 throw std::runtime_error(__err_msg_iterator_invalidated);
96 #else
97 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
98 return *(_Iterator*)NULL; // force segfault if iterator became invalidated
99 #endif // CONFIG_RT_EXCEPTIONS
100 }
101 #endif // CONFIG_DEVMODE
102 fallback = current;
103 current = current->next;
104 return *this;
105 }
106
107 /// postfix increment op.
108 inline _Iterator operator++(int) {
109 _Iterator preval = *this;
110 ++*this; // use prefix operator implementation
111 return preval;
112 }
113
114 /// prefix decrement op.
115 inline _Iterator& operator--() {
116 #if CONFIG_DEVMODE
117 if (!isValid()) {
118 #if CONFIG_RT_EXCEPTIONS
119 throw std::runtime_error(__err_msg_iterator_invalidated);
120 #else
121 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
122 return *(_Iterator*)NULL; // force segfault if iterator became invalidated
123 #endif // CONFIG_RT_EXCEPTIONS
124 }
125 #endif // CONFIG_DEVMODE
126 fallback = current;
127 current = current->prev;
128 return *this;
129 }
130
131 /// postfix decrement op.
132 inline _Iterator operator--(int) {
133 _Iterator preval = *this;
134 --*this; // use prefix operator implementation
135 return preval;
136 }
137
138 inline T1& operator*() {
139 #if CONFIG_DEVMODE
140 if (!isValid()) { // if iterator became invalidated
141 #if CONFIG_RT_EXCEPTIONS
142 throw std::runtime_error(__err_msg_iterator_invalidated);
143 #else
144 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
145 return *((T1*)NULL); // force segfault if iterator became invalidated
146 #endif // CONFIG_RT_EXCEPTIONS
147 }
148 #endif // CONFIG_DEVMODE
149 return *current->data;
150 }
151
152 inline const T1& operator*() const {
153 #if CONFIG_DEVMODE
154 if (!isValid()) { // if iterator became invalidated
155 #if CONFIG_RT_EXCEPTIONS
156 throw std::runtime_error(__err_msg_iterator_invalidated);
157 #else
158 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
159 return *((const T1*)NULL); // force segfault if iterator became invalidated
160 #endif // CONFIG_RT_EXCEPTIONS
161 }
162 #endif // CONFIG_DEVMODE
163 return *current->data;
164 }
165
166 inline T1* operator->() {
167 #if CONFIG_DEVMODE
168 if (!isValid()) { // if iterator became invalidated
169 #if CONFIG_RT_EXCEPTIONS
170 throw std::runtime_error(__err_msg_iterator_invalidated);
171 #else
172 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
173 return (T1*)NULL; // force segfault if iterator became invalidated
174 #endif // CONFIG_RT_EXCEPTIONS
175 }
176 #endif // CONFIG_DEVMODE
177 return current->data;
178 }
179
180 inline const T1* operator->() const {
181 #if CONFIG_DEVMODE
182 if (!isValid()) { // if iterator became invalidated
183 #if CONFIG_RT_EXCEPTIONS
184 throw std::runtime_error(__err_msg_iterator_invalidated);
185 #else
186 std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
187 return (const T1*)NULL; // force segfault if iterator became invalidated
188 #endif // CONFIG_RT_EXCEPTIONS
189 }
190 #endif // CONFIG_DEVMODE
191 return current->data;
192 }
193
194 inline bool operator==(const _Iterator<T1> other) const {
195 return current == other.current;
196 }
197
198 inline bool operator!=(const _Iterator<T1> other) const {
199 return current != other.current;
200 }
201
202 inline operator bool() const {
203 return current && current->data;
204 }
205
206 inline bool operator!() const {
207 return !(current && current->data);
208 }
209
210 inline _Iterator moveToEndOf(RTListBase<T1>* pDstList) {
211 detach();
212 pDstList->append(*this);
213 _Iterator iterOnDstList = _Iterator(current);
214 current = fallback;
215 return iterOnDstList;
216 }
217
218 inline _Iterator moveToBeginOf(RTListBase<T1>* pDstList) {
219 detach();
220 pDstList->prepend(*this);
221 _Iterator iterOnDstList = _Iterator(current);
222 current = fallback;
223 return iterOnDstList;
224 }
225
226 #if CONFIG_DEVMODE
227 inline bool isValid() const {
228 return current->list == list;
229 }
230 #endif // CONFIG_DEVMODE
231
232 protected:
233 Node* current;
234 Node* fallback;
235 enum dir_t {
236 dir_forward,
237 dir_backward
238 };
239 #if CONFIG_DEVMODE
240 RTListBase<T1>* list;
241 #endif // CONFIG_DEVMODE
242
243 _Iterator(Node* pNode, dir_t direction = dir_forward) {
244 current = pNode;
245 fallback = (direction == dir_forward) ? pNode->prev : pNode->next;
246 #if CONFIG_DEVMODE
247 list = pNode->list;
248 #endif // CONFIG_DEVMODE
249 }
250
251 inline Node* node() {
252 #if CONFIG_DEVMODE
253 #if CONFIG_RT_EXCEPTIONS
254 if (isValid()) return current;
255 else throw std::runtime_error(__err_msg_iterator_invalidated);
256 #else
257 return (isValid()) ? current : (Node*)NULL; // force segfault if iterator became invalidated
258 #endif // CONFIG_RT_EXCEPTIONS
259 #else
260 return current;
261 #endif // CONFIG_DEVMODE
262 }
263
264 inline const Node* node() const {
265 #if CONFIG_DEVMODE
266 #if CONFIG_RT_EXCEPTIONS
267 if (isValid()) return current;
268 else throw std::runtime_error(__err_msg_iterator_invalidated);
269 #else
270 return (isValid()) ? current : (const Node*)NULL; // force segfault if iterator became invalidated
271 #endif // CONFIG_RT_EXCEPTIONS
272 #else
273 return current;
274 #endif // CONFIG_DEVMODE
275 }
276
277 inline void detach() {
278 RTListBase<T1>::detach(*this);
279 }
280
281 friend class RTListBase<T1>;
282 friend class RTList<T1>;
283 friend class Pool<T1>;
284 };
285 typedef _Iterator<T> Iterator;
286
287 inline Iterator first() {
288 return Iterator(_begin.next, Iterator::dir_forward);
289 }
290
291 inline Iterator last() {
292 return Iterator(_end.prev, Iterator::dir_backward);
293 }
294
295 inline Iterator begin() {
296 return Iterator(&_begin, Iterator::dir_forward);
297 }
298
299 inline Iterator end() {
300 return Iterator(&_end, Iterator::dir_backward);
301 }
302
303 inline bool isEmpty() const {
304 return _begin.next == &_end;
305 }
306
307 inline int count() {
308 int elements = 0;
309 for (Iterator it = first(); it != end(); ++it) ++elements;
310 return elements;
311 }
312
313 protected:
314 Node _begin; // fake node (without data) which represents the begin of the list - not the first element!
315 Node _end; // fake node (without data) which represents the end of the list - not the last element!
316
317 RTListBase() {
318 init();
319 }
320
321 void init() {
322 // initialize boundary nodes
323 _begin.prev = &_begin;
324 _begin.next = &_end;
325 _begin.data = NULL;
326 _end.next = &_end;
327 _end.prev = &_begin;
328 _end.data = NULL;
329 #if CONFIG_DEVMODE
330 _begin.list = this;
331 _end.list = this;
332 #endif // CONFIG_DEVMODE
333 }
334
335 inline void append(Iterator itElement) {
336 Node* pNode = itElement.current;
337 Node* last = _end.prev;
338 last->next = pNode;
339 pNode->prev = last; // if a segfault happens here, then because 'itElement' Iterator became invalidated
340 pNode->next = &_end;
341 _end.prev = pNode;
342 #if CONFIG_DEVMODE
343 pNode->list = this;
344 #endif // CONFIG_DEVMODE
345 }
346
347 inline void append(Iterator itFirst, Iterator itLast) {
348 Node* pFirst = itFirst.current;
349 Node* pLast = itLast.current;
350 Node* last = _end.prev;
351 last->next = pFirst;
352 pFirst->prev = last; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
353 pLast->next = &_end; // if a segfault happens here, then because 'itLast' Iterator became invalidated
354 _end.prev = pLast;
355 #if CONFIG_DEVMODE
356 for (Node* pNode = pFirst; true; pNode = pNode->next) {
357 pNode->list = this;
358 if (pNode == pLast) break;
359 }
360 #endif // CONFIG_DEVMODE
361 }
362
363 inline void prepend(Iterator itElement) {
364 Node* pNode = itElement.current;
365 Node* first = _begin.next;
366 _begin.next = pNode;
367 pNode->prev = &_begin; // if a segfault happens here, then because 'itElement' Iterator became invalidated
368 pNode->next = first;
369 first->prev = pNode;
370 #if CONFIG_DEVMODE
371 pNode->list = this;
372 #endif // CONFIG_DEVMODE
373 }
374
375 inline void prepend(Iterator itFirst, Iterator itLast) {
376 Node* pFirst = itFirst.current;
377 Node* pLast = itLast.current;
378 Node* first = _begin.next;
379 _begin.next = pFirst;
380 pFirst->prev = &_begin; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
381 pLast->next = first; // if a segfault happens here, then because 'itLast' Iterator became invalidated
382 first->prev = pLast;
383 #if CONFIG_DEVMODE
384 for (Node* pNode = pFirst; true; pNode = pNode->next) {
385 pNode->list = this;
386 if (pNode == pLast) break;
387 }
388 #endif // CONFIG_DEVMODE
389 }
390
391 static inline void detach(Iterator itElement) {
392 Node* pNode = itElement.node();
393 Node* prev = pNode->prev; // if a segfault happens here, then because 'itElement' Iterator became invalidated
394 Node* next = pNode->next;
395 prev->next = next;
396 next->prev = prev;
397 }
398
399 static inline void detach(Iterator itFirst, Iterator itLast) {
400 Node* prev = itFirst.node()->prev; // if a segfault happens here, then because 'itFirst' Iterator became invalidated
401 Node* next = itLast.node()->next; // if a segfault happens here, then because 'itLast' Iterator became invalidated
402 prev->next = next;
403 next->prev = prev;
404 }
405
406 friend class _Iterator<T>;
407 friend class RTList<T>;
408 friend class Pool<T>;
409 };
410
411 template<typename T>
412 class RTList : public RTListBase<T> {
413 public:
414 typedef typename RTListBase<T>::Node Node;
415 typedef typename RTListBase<T>::Iterator Iterator;
416
417 /**
418 * Constructor
419 *
420 * @param pPool - pool this list uses for allocation and
421 * deallocation of elements
422 */
423 RTList(Pool<T>* pPool) : RTListBase<T>::RTListBase() {
424 this->pPool = pPool;
425 }
426
427 /**
428 * Copy constructor
429 */
430 RTList(RTList<T>& list) : RTListBase<T>::RTListBase() {
431 this->pPool = list.pPool;
432 Iterator it = list.first();
433 Iterator end = list.end();
434 for(; it != end; ++it) {
435 if (poolIsEmpty()) break;
436 *(allocAppend()) = *it;
437 }
438 }
439
440 virtual ~RTList() {
441 clear();
442 }
443
444 inline bool poolIsEmpty() const {
445 return pPool->poolIsEmpty();
446 }
447
448 inline Iterator allocAppend() {
449 if (pPool->poolIsEmpty()) return RTListBase<T>::begin();
450 Iterator element = pPool->alloc();
451 this->append(element);
452 #if CONFIG_DEVMODE
453 element.list = this;
454 #endif // CONFIG_DEVMODE
455 return element;
456 }
457
458 inline Iterator allocPrepend() {
459 if (pPool->poolIsEmpty()) return RTListBase<T>::end();
460 Iterator element = pPool->alloc();
461 prepend(element);
462 #if CONFIG_DEVMODE
463 element.list = this;
464 #endif // CONFIG_DEVMODE
465 return element;
466 }
467
468 inline void free(Iterator& itElement) {
469 itElement.detach();
470 pPool->freeToPool(itElement);
471 itElement.current = itElement.fallback;
472 }
473
474 inline void clear() {
475 if (!RTListBase<T>::isEmpty()) {
476 Node* first = RTListBase<T>::_begin.next;
477 Node* last = RTListBase<T>::_end.prev;
478 RTListBase<T>::detach(first, last);
479 pPool->freeToPool(first, last);
480 }
481 }
482
483 inline int getID(const T* obj) const {
484 return pPool->getID(obj);
485 }
486
487 inline int getID(const Iterator& it) const {
488 return pPool->getID(&*it);
489 }
490
491 inline Iterator fromID(int id) const {
492 return pPool->fromID(id);
493 }
494
495 protected:
496 Pool<T>* pPool;
497 };
498
499 template<typename T>
500 class Pool : public RTList<T> {
501 public:
502 typedef typename RTList<T>::Node Node;
503 typedef typename RTList<T>::Iterator Iterator;
504
505 Node* nodes;
506 T* data;
507 RTListBase<T> freelist; // not yet allocated elements
508 int poolsize;
509
510 Pool(int Elements) : RTList<T>::RTList(this) {
511 _init(Elements);
512 }
513
514 virtual ~Pool() {
515 if (nodes) delete[] nodes;
516 if (data) delete[] data;
517 }
518
519 inline bool poolIsEmpty() const {
520 return freelist.isEmpty();
521 }
522
523 /**
524 * Returns the current size of the pool, that is the amount of
525 * pre-allocated elements from the operating system. It equals the
526 * amount of elements given to the constructor unless resizePool()
527 * is called.
528 *
529 * @see resizePool()
530 */
531 int poolSize() const {
532 return poolsize;
533 }
534
535 /**
536 * Alters the amount of elements to be pre-allocated from the
537 * operating system for this pool object.
538 *
539 * @e CAUTION: you MUST free all elements in use before calling this
540 * method ( e.g. by calling clear() )! Also make sure that no
541 * references of elements before this call will still be used after this
542 * call, since all elements will be reallocated and their old memory
543 * addresses become invalid!
544 *
545 * @see poolSize()
546 */
547 void resizePool(int Elements) {
548 if (freelist.count() != poolsize) {
549 #if CONFIG_DEVMODE
550 throw std::runtime_error(__err_msg_resize_while_in_use);
551 #else
552 std::cerr << __err_msg_resize_while_in_use << std::endl << std::flush;
553 // if we're here something's terribly wrong, but we try to do the best
554 RTList<T>::clear();
555 #endif
556 }
557 if (nodes) delete[] nodes;
558 if (data) delete[] data;
559 freelist.init();
560 RTListBase<T>::init();
561 _init(Elements);
562 }
563
564 /**
565 * Returns an abstract, unique numeric ID for the given object of
566 * this pool, it returns -1 in case the passed object is not a member
567 * of this Pool, i.e. because it is simply an invalid pointer or member
568 * of another Pool. The returned ID is unique among all elements of this
569 * Pool and it differs with each reincarnation of an object. That means
570 * each time you free an element to and allocate the same element back
571 * from the Pool, it will have a different ID.
572 *
573 * Members are always translated both, from Iterators/pointers to IDs,
574 * and from IDs to Iterators/pointers in constant time.
575 *
576 * You might want to use this alternative approach of referencing Pool
577 * members under certain scenarios. For example if you need to expose
578 * an ID to the end user and/or if you want to represent an object of
579 * this pool by a smaller number instead of a native pointer (i.e. 16
580 * bits vs. 64 bits). You can also detect this way whether the object
581 * has already been freed / reallocated from the Pool in the meantime.
582 *
583 * @param obj - raw pointer to a data member of this Pool
584 * @returns unique numeric ID of @a obj or -1 if pointer was invalid
585 */
586 int getID(const T* obj) const {
587 if (!poolsize) return -1;
588 int index = obj - &data[0];
589 if (index < 0 || index >= poolsize) return -1;
590 return (nodes[index].reincarnation << bitsForSize(poolsize)) | index;
591 }
592
593 /**
594 * Overridden convenience method, behaves like the method above.
595 */
596 int getID(const Iterator& it) const {
597 return getID(&*it);
598 }
599
600 /**
601 * Returns an Iterator object of the Pool data member reflected by the
602 * given abstract, unique numeric ID, it returns an invalid Iterator in
603 * case the ID is invalid or if the Pool's data element reflected by
604 * given ID was at least once released/freed back to the Pool in the
605 * meantime.
606 *
607 * Members are always translated both, from Iterators/pointers to IDs,
608 * and from IDs to Iterators/pointers in constant time.
609 *
610 * You might want to use this alternative approach of referencing Pool
611 * members under certain scenarios. For example if you need to expose
612 * an ID to the end user and/or if you want to represent an object of
613 * this pool by a smaller number instead of a native pointer (i.e. 16
614 * bits vs. 64 bits). You can also detect this way whether the object
615 * has already been freed / reallocated from the Pool in the meantime.
616 *
617 * @param id - unique ID of a Pool's data member
618 * @returns Iterator object pointing to Pool's data element, invalid
619 * Iterator in case ID was invalid or data element was freed
620 */
621 Iterator fromID(int id) const {
622 if (id < 0) return Iterator(); // invalid iterator
623 const uint bits = bitsForSize(poolsize);
624 uint index = id & ((1 << bits) - 1);
625 if (index >= poolsize) return Iterator(); // invalid iterator
626 Node* node = &nodes[index];
627 int reincarnation = uint(id) >> bits;
628 if (reincarnation != node->reincarnation) return Iterator(); // invalid iterator
629 return Iterator(node);
630 }
631
632 protected:
633 // caution: assumes pool (that is freelist) is not empty!
634 inline Iterator alloc() {
635 Iterator element = freelist.last();
636 element.detach();
637 return element;
638 }
639
640 inline void freeToPool(Iterator itElement) {
641 itElement.node()->reincarnation++;
642 freelist.append(itElement);
643 }
644
645 inline void freeToPool(Iterator itFirst, Iterator itLast) {
646 for (Node* n = itFirst.node(); true; n = n->next) {
647 n->reincarnation++;
648 if (n == itLast.node()) break;
649 }
650 freelist.append(itFirst, itLast);
651 }
652
653 friend class RTList<T>;
654
655 private:
656 void _init(int Elements) {
657 data = new T[Elements];
658 nodes = new Node[Elements];
659 for (int i = 0; i < Elements; i++) {
660 nodes[i].data = &data[i];
661 freelist.append(&nodes[i]);
662 }
663 poolsize = Elements;
664 }
665
666 inline static int bitsForSize(int size) {
667 if (!size) return 0;
668 size--;
669 int bits = 0;
670 for (; size > 1; bits += 2, size >>= 2);
671 return bits + size;
672 }
673 };
674
675 #endif // __LS_POOL_H__

  ViewVC Help
Powered by ViewVC