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

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 271 by schoenebeck, Fri Oct 8 20:51:39 2004 UTC revision 3549 by schoenebeck, Wed Jul 31 15:43:53 2019 UTC
# Line 3  Line 3 
3   *   LinuxSampler - modular, streaming capable sampler                     *   *   LinuxSampler - modular, streaming capable sampler                     *
4   *                                                                         *   *                                                                         *
5   *   Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck   *   *   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  *   *   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  *   *   it under the terms of the GNU General Public License as published by  *
# Line 23  Line 24 
24  #ifndef __LS_POOL_H__  #ifndef __LS_POOL_H__
25  #define __LS_POOL_H__  #define __LS_POOL_H__
26    
27  #ifndef DEVMODE  #ifdef HAVE_CONFIG_H
28  # include "global.h" // just to check if we should compile in 'DEVMODE'  # include <config.h>
29  #endif  #endif
30    
31  // we just use exceptions for debugging, better not in the final realtime thread !  // we just use exceptions for debugging, better not in the final realtime thread !
32  #ifndef USE_EXCEPTIONS  #ifndef CONFIG_RT_EXCEPTIONS
33  # define USE_EXCEPTIONS 0  # define CONFIG_RT_EXCEPTIONS 0
34  #endif  #endif
35    
36  #if USE_EXCEPTIONS  #if CONFIG_RT_EXCEPTIONS
37  # include <stdexcept>  # include <stdexcept>
38  # include <string>  # 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";  const std::string __err_msg_iterator_invalidated = "Pool/RTList iterator invalidated";
50  #endif // USE_EXCEPTIONS  #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  // just symbol prototyping
71  template<typename T> class Pool;  template<typename T> class Pool;
# Line 45  template<typename T> class RTList; Line 74  template<typename T> class RTList;
74  template<typename T>  template<typename T>
75  class RTListBase {  class RTListBase {
76      protected:      protected:
77          template<typename _T>          template<typename T1>
78          struct _Node {          struct _Node {
79              _Node<_T>* next;              _Node<T1>* next;
80              _Node<_T>* prev;              _Node<T1>* prev;
81              _T* data;              T1* data;
82              #if DEVMODE              #if CONFIG_DEVMODE
83              RTListBase<_T>* list; // list to which this node currently belongs to              RTListBase<T1>* list; // list to which this node currently belongs to
84              #endif // DEVMODE              #endif // CONFIG_DEVMODE
85                uint reincarnation; // just for Pool::fromID()
86    
87              _Node() {              _Node() {
88                  next = NULL;                  next = NULL;
89                  prev = NULL;                  prev = NULL;
90                  data = NULL;                  data = NULL;
91                  #if DEVMODE                  #if CONFIG_DEVMODE
92                  list = NULL;                  list = NULL;
93                  #endif // DEVMODE                  #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;          typedef _Node<T> Node;
104    
105      public:      public:
106          template<typename _T>          /**
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 {          class _Iterator {
116              public:              public:
117                  _Iterator() {                  _Iterator() {
118                      current  = NULL;                      current  = NULL;
119                      fallback = NULL;                      fallback = NULL;
120                      #if DEVMODE                      #if CONFIG_DEVMODE
121                      list = NULL;                      list = NULL;
122                      #endif // DEVMODE                      #endif // CONFIG_DEVMODE
123                  }                  }
124    
125                  /// prefix increment op.                  /// prefix increment op.
126                  inline _Iterator& operator++() {                  inline _Iterator& operator++() {
127                      #if DEVMODE                      #if CONFIG_DEVMODE
128                      #if USE_EXCEPTIONS                      if (!isValid()) {
129                      if (!isValid()) throw std::runtime_error(__err_msg_iterator_invalidated);                          #if CONFIG_RT_EXCEPTIONS
130                      #else                          throw std::runtime_error(__err_msg_iterator_invalidated);
131                      if (!isValid()) return *(_Iterator*)NULL; // force segfault if iterator became invalidated                          #else
132                      #endif // USE_EXCEPTIONS                          std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
133                      #endif // DEVMODE                          return *(_Iterator*)NULL; // force segfault if iterator became invalidated
134                            #endif // CONFIG_RT_EXCEPTIONS
135                        }
136                        #endif // CONFIG_DEVMODE
137                      fallback = current;                      fallback = current;
138                      current  = current->next;                      current  = current->next;
139                      return *this;                      return *this;
# Line 94  class RTListBase { Line 142  class RTListBase {
142                  /// postfix increment op.                  /// postfix increment op.
143                  inline _Iterator operator++(int) {                  inline _Iterator operator++(int) {
144                      _Iterator preval = *this;                      _Iterator preval = *this;
145                      ++*this;                      ++*this; // use prefix operator implementation
146                      return preval;                      return preval;
147                  }                  }
148    
149                  /// prefix decrement op.                  /// prefix decrement op.
150                  inline _Iterator& operator--() {                  inline _Iterator& operator--() {
151                      #if DEVMODE                      #if CONFIG_DEVMODE
152                      #if USE_EXCEPTIONS                      if (!isValid()) {
153                      if (!isValid()) throw std::runtime_error(__err_msg_iterator_invalidated);                          #if CONFIG_RT_EXCEPTIONS
154                      #else                          throw std::runtime_error(__err_msg_iterator_invalidated);
155                      if (!isValid()) return *(_Iterator*)NULL; // force segfault if iterator became invalidated                          #else
156                      #endif // USE_EXCEPTIONS                          std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
157                      #endif // DEVMODE                          return *(_Iterator*)NULL; // force segfault if iterator became invalidated
158                            #endif // CONFIG_RT_EXCEPTIONS
159                        }
160                        #endif // CONFIG_DEVMODE
161                      fallback = current;                      fallback = current;
162                      current  = current->prev;                      current  = current->prev;
163                      return *this;                      return *this;
# Line 115  class RTListBase { Line 166  class RTListBase {
166                  /// postfix decrement op.                  /// postfix decrement op.
167                  inline _Iterator operator--(int) {                  inline _Iterator operator--(int) {
168                      _Iterator preval = *this;                      _Iterator preval = *this;
169                      --*this;                      --*this; // use prefix operator implementation
170                      return preval;                      return preval;
171                  }                  }
172    
173                  inline _T& operator*() {                  inline T1& operator*() {
174                      #if DEVMODE                      #if CONFIG_DEVMODE
175                      #if USE_EXCEPTIONS                      if (!isValid()) { // if iterator became invalidated
176                      if (isValid()) return *current->data;                          #if CONFIG_RT_EXCEPTIONS
177                      else throw std::runtime_error(__err_msg_iterator_invalidated);                          throw std::runtime_error(__err_msg_iterator_invalidated);
178                      #else                          #else
179                      return *(isValid() ? current->data : (_T*)NULL); // force segfault if iterator became invalidated                          std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
180                      #endif // USE_EXCEPTIONS                          return *((T1*)NULL); // force segfault if iterator became invalidated
181                      #else                          #endif // CONFIG_RT_EXCEPTIONS
182                        }
183                        #endif // CONFIG_DEVMODE
184                      return *current->data;                      return *current->data;
                     #endif // DEVMODE  
185                  }                  }
186    
187                  inline _T* operator->() {                  inline const T1& operator*() const {
188                      #if DEVMODE                      #if CONFIG_DEVMODE
189                      #if USE_EXCEPTIONS                      if (!isValid()) { // if iterator became invalidated
190                      if (isValid()) return current->data;                          #if CONFIG_RT_EXCEPTIONS
191                      else throw std::runtime_error(__err_msg_iterator_invalidated);                          throw std::runtime_error(__err_msg_iterator_invalidated);
192                      #else                          #else
193                      return isValid() ? current->data : (_T*)NULL; // force segfault if iterator became invalidated                          std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
194                      #endif // USE_EXCEPTIONS                          return *((const T1*)NULL); // force segfault if iterator became invalidated
195                      #else                          #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;                      return current->data;
                     #endif // DEVMODE  
213                  }                  }
214    
215                  inline bool operator==(const _Iterator<_T> other) {                  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;                      return current == other.current;
231                  }                  }
232    
233                  inline bool operator!=(const _Iterator<_T> other) {                  inline bool operator!=(const _Iterator<T1> other) const {
234                      return current != other.current;                      return current != other.current;
235                  }                  }
236    
# Line 161  class RTListBase { Line 242  class RTListBase {
242                      return !(current && current->data);                      return !(current && current->data);
243                  }                  }
244    
245                  inline _Iterator moveToEndOf(RTListBase<_T>* pDstList) {                  /**
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();                      detach();
270                      pDstList->append(*this);                      pDstList->append(*this);
271                      _Iterator iterOnDstList = _Iterator(current);                      _Iterator iterOnDstList = _Iterator(current);
# Line 169  class RTListBase { Line 273  class RTListBase {
273                      return iterOnDstList;                      return iterOnDstList;
274                  }                  }
275    
276                  inline _Iterator moveToBeginOf(RTListBase<_T>* pDstList) {                  /**
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();                      detach();
301                      pDstList->prepend(*this);                      pDstList->prepend(*this);
302                      _Iterator iterOnDstList = _Iterator(current);                      _Iterator iterOnDstList = _Iterator(current);
# Line 177  class RTListBase { Line 304  class RTListBase {
304                      return iterOnDstList;                      return iterOnDstList;
305                  }                  }
306    
307                  #if DEVMODE                  /**
308                  inline bool isValid() {                   * 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;                      return current->list == list;
376                  }                  }
377                  #endif // DEVMODE                  #endif // CONFIG_DEVMODE
378    
379              protected:              protected:
380                  Node* current;                  Node* current;
# Line 190  class RTListBase { Line 383  class RTListBase {
383                      dir_forward,                      dir_forward,
384                      dir_backward                      dir_backward
385                  };                  };
386                  #if DEVMODE                  #if CONFIG_DEVMODE
387                  RTListBase<_T>* list;                  RTListBase<T1>* list;
388                  #endif // DEVMODE                  #endif // CONFIG_DEVMODE
389    
390                  _Iterator(Node* pNode, dir_t direction = dir_forward) {                  _Iterator(Node* pNode, dir_t direction = dir_forward) {
391                      current  = pNode;                      current  = pNode;
392                      fallback = (direction == dir_forward) ? pNode->prev : pNode->next;                      fallback = (direction == dir_forward) ? pNode->prev : pNode->next;
393                      #if DEVMODE                      #if CONFIG_DEVMODE
394                      list = pNode->list;                      list = pNode->list;
395                      #endif // DEVMODE                      #endif // CONFIG_DEVMODE
396                  }                  }
397    
398                  inline Node* node() {                  inline Node* node() {
399                      #if DEVMODE                      #if CONFIG_DEVMODE
400                      #if USE_EXCEPTIONS                      #if CONFIG_RT_EXCEPTIONS
401                      if (isValid()) return current;                      if (isValid()) return current;
402                      else throw std::runtime_error(__err_msg_iterator_invalidated);                      else throw std::runtime_error(__err_msg_iterator_invalidated);
403                      #else                      #else
404                      return (isValid()) ? current : (Node*)NULL; // force segfault if iterator became invalidated                      return (isValid()) ? current : (Node*)NULL; // force segfault if iterator became invalidated
405                      #endif // USE_EXCEPTIONS                      #endif // CONFIG_RT_EXCEPTIONS
406                      #else                      #else
407                      return current;                      return current;
408                      #endif // DEVMODE                      #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() {                  inline void detach() {
425                      RTListBase<_T>::detach(*this);                      RTListBase<T1>::detach(*this);
426                  }                  }
427    
428                  friend class RTListBase<_T>;                  friend class RTListBase<T1>;
429                  friend class RTList<_T>;                  friend class RTList<T1>;
430                  friend class Pool<_T>;                  friend class Pool<T1>;
431          };          };
432          typedef _Iterator<T> Iterator;          typedef _Iterator<T> Iterator;
433    
# Line 241  class RTListBase { Line 447  class RTListBase {
447              return Iterator(&_end, Iterator::dir_backward);              return Iterator(&_end, Iterator::dir_backward);
448          }          }
449    
450          inline bool isEmpty() {          inline bool isEmpty() const {
451              return _begin.next == &_end;              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:      protected:
461          Node _begin; // fake node (without data) which represents the begin of the list - not the first element!          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!          Node _end;   // fake node (without data) which represents the end of the list - not the last element!
463    
464          RTListBase() {          RTListBase() {
465                init();
466            }
467    
468            void init() {
469              // initialize boundary nodes              // initialize boundary nodes
470              _begin.prev = &_begin;              _begin.prev = &_begin;
471              _begin.next = &_end;              _begin.next = &_end;
# Line 257  class RTListBase { Line 473  class RTListBase {
473              _end.next = &_end;              _end.next = &_end;
474              _end.prev = &_begin;              _end.prev = &_begin;
475              _end.data = NULL;              _end.data = NULL;
476              #if DEVMODE              #if CONFIG_DEVMODE
477              _begin.list = this;              _begin.list = this;
478              _end.list   = this;              _end.list   = this;
479              #endif // DEVMODE              #endif // CONFIG_DEVMODE
480          }          }
481    
482          inline void append(Iterator itElement) {          inline void append(Iterator itElement) {
# Line 270  class RTListBase { Line 486  class RTListBase {
486              pNode->prev = last; // if a segfault happens here, then because 'itElement' Iterator became invalidated              pNode->prev = last; // if a segfault happens here, then because 'itElement' Iterator became invalidated
487              pNode->next = &_end;              pNode->next = &_end;
488              _end.prev   = pNode;              _end.prev   = pNode;
489              #if DEVMODE              #if CONFIG_DEVMODE
490              pNode->list = this;              pNode->list = this;
491              #endif // DEVMODE              #endif // CONFIG_DEVMODE
492          }          }
493    
494          inline void append(Iterator itFirst, Iterator itLast) {          inline void append(Iterator itFirst, Iterator itLast) {
# Line 283  class RTListBase { Line 499  class RTListBase {
499              pFirst->prev = last;  // if a segfault happens here, then because 'itFirst' Iterator became invalidated              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              pLast->next  = &_end; // if a segfault happens here, then because 'itLast' Iterator became invalidated
501              _end.prev    = pLast;              _end.prev    = pLast;
502              #if DEVMODE              #if CONFIG_DEVMODE
503              for (Node* pNode = pFirst; true; pNode = pNode->next) {              for (Node* pNode = pFirst; true; pNode = pNode->next) {
504                  pNode->list = this;                  pNode->list = this;
505                  if (pNode == pLast) break;                  if (pNode == pLast) break;
506              }              }
507              #endif // DEVMODE              #endif // CONFIG_DEVMODE
508          }          }
509    
510          inline void prepend(Iterator itElement) {          inline void prepend(Iterator itElement) {
# Line 298  class RTListBase { Line 514  class RTListBase {
514              pNode->prev = &_begin; // if a segfault happens here, then because 'itElement' Iterator became invalidated              pNode->prev = &_begin; // if a segfault happens here, then because 'itElement' Iterator became invalidated
515              pNode->next = first;              pNode->next = first;
516              first->prev = pNode;              first->prev = pNode;
517              #if DEVMODE              #if CONFIG_DEVMODE
518              pNode->list = this;              pNode->list = this;
519              #endif // DEVMODE              #endif // CONFIG_DEVMODE
520          }          }
521    
522          inline void prepend(Iterator itFirst, Iterator itLast) {          inline void prepend(Iterator itFirst, Iterator itLast) {
# Line 311  class RTListBase { Line 527  class RTListBase {
527              pFirst->prev = &_begin; // if a segfault happens here, then because 'itFirst' Iterator became invalidated              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              pLast->next  = first;   // if a segfault happens here, then because 'itLast' Iterator became invalidated
529              first->prev  = pLast;              first->prev  = pLast;
530              #if DEVMODE              #if CONFIG_DEVMODE
531              for (Node* pNode = pFirst; true; pNode = pNode->next) {              for (Node* pNode = pFirst; true; pNode = pNode->next) {
532                  pNode->list = this;                  pNode->list = this;
533                  if (pNode == pLast) break;                  if (pNode == pLast) break;
534              }              }
535              #endif // DEVMODE              #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) {          static inline void detach(Iterator itElement) {
# Line 334  class RTListBase { Line 576  class RTListBase {
576              next->prev = prev;              next->prev = prev;
577          }          }
578    
579            friend class _Iterator<T>;
580            friend class RTList<T>;
581          friend class Pool<T>;          friend class Pool<T>;
582  };  };
583    
# Line 352  class RTList : public RTListBase<T> { Line 596  class RTList : public RTListBase<T> {
596          RTList(Pool<T>* pPool) : RTListBase<T>::RTListBase() {          RTList(Pool<T>* pPool) : RTListBase<T>::RTListBase() {
597              this->pPool = pPool;              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() {          virtual ~RTList() {
614              clear();              clear();
615          }          }
616    
617          inline bool poolIsEmpty() {          inline bool poolIsEmpty() const {
618              return pPool->poolIsEmpty();              return pPool->poolIsEmpty();
619          }          }
620    
621          inline Iterator allocAppend() {          inline Iterator allocAppend() {
622              if (pPool->poolIsEmpty()) return RTListBase<T>::begin();              if (pPool->poolIsEmpty()) return RTListBase<T>::begin();
623              Iterator element = pPool->alloc();              Iterator element = pPool->alloc();
624              append(element);              this->append(element);
625              #if DEVMODE              #if CONFIG_DEVMODE
626              element.list = this;              element.list = this;
627              #endif // DEVMODE              #endif // CONFIG_DEVMODE
628              return element;              return element;
629          }          }
630    
631          inline Iterator allocPrepend() {          inline Iterator allocPrepend() {
632              if (pPool->poolIsEmpty()) return RTListBase<T>::end();              if (pPool->poolIsEmpty()) return RTListBase<T>::end();
633              Iterator element = pPool->alloc();              Iterator element = pPool->alloc();
634              prepend(element);              this->prepend(element);
635              #if DEVMODE              #if CONFIG_DEVMODE
636              element.list = this;              element.list = this;
637              #endif // DEVMODE              #endif // CONFIG_DEVMODE
638              return element;              return element;
639          }          }
640    
# Line 396  class RTList : public RTListBase<T> { Line 653  class RTList : public RTListBase<T> {
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:      protected:
673          Pool<T>* pPool;          Pool<T>* pPool;
674  };  };
# Line 409  class Pool : public RTList<T> { Line 682  class Pool : public RTList<T> {
682          Node*         nodes;          Node*         nodes;
683          T*            data;          T*            data;
684          RTListBase<T> freelist; // not yet allocated elements          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) {          Pool(int Elements) : RTList<T>::RTList(this), reservedbits(0) {
692              data  = new T[Elements];              _init(Elements);
             nodes = new Node[Elements];  
             for (int i = 0; i < Elements; i++) {  
                 nodes[i].data = &data[i];  
                 freelist.append(&nodes[i]);  
             }  
693          }          }
694    
695          virtual ~Pool() {          virtual ~Pool() {
# Line 424  class Pool : public RTList<T> { Line 697  class Pool : public RTList<T> {
697              if (data)  delete[] data;              if (data)  delete[] data;
698          }          }
699    
700          inline bool poolIsEmpty() {          /**
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();              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:      protected:
877          // caution: assumes pool (that is freelist) is not empty!          // caution: assumes pool (that is freelist) is not empty!
878          inline Iterator alloc() {          inline Iterator alloc() {
# Line 437  class Pool : public RTList<T> { Line 882  class Pool : public RTList<T> {
882          }          }
883    
884          inline void freeToPool(Iterator itElement) {          inline void freeToPool(Iterator itElement) {
885                itElement.node()->bumpReincarnation(reincarnationbits);
886              freelist.append(itElement);              freelist.append(itElement);
887          }          }
888    
889          inline void freeToPool(Iterator itFirst, Iterator itLast) {          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);              freelist.append(itFirst, itLast);
895          }          }
896    
897          friend class RTList<T>;          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__  #endif // __LS_POOL_H__
Legend:
Removed from v.271  
changed lines
  Added in v.3549
  ViewVC Help
Powered by ViewVC