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