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