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

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

Parent Directory | Revision Log | View Patch Patch

-revision 1800 by schoenebeck,
Sun Dec  7 01:26:46 2008 UTC
+revision 3293 by schoenebeck,
Tue Jun 27 22:19:19 2017 UTC
 Line 3
   *   LinuxSampler - modular, streaming capable sampler                     *
   *                                                                         *
   *   Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck   *
-  *   Copyright (C) 2005 - 2008 Christian Schoenebeck                       *
+  *   Copyright (C) 2005 - 2017 Christian Schoenebeck                       *
   *                                                                         *
   *   This program is free software; you can redistribute it and/or modify  *
   *   it under the terms of the GNU General Public License as published by  *
 Line 38
  # include <string>
  #endif // CONFIG_RT_EXCEPTIONS
+ #include <iostream>
  #if CONFIG_DEVMODE
  # include <string>
- # include <iostream>
  const std::string __err_msg_iterator_invalidated = "Pool/RTList iterator invalidated";
  #endif // CONFIG_DEVMODE
  const std::string __err_msg_resize_while_in_use = "Pool::resizePool() ERROR: elements still in use!";
+ /**
+  * Unique numeric ID for exactly one incarnation of one element allocated from
+  * a Pool. As soon as the respective element is once freed back to the Pool,
+  * the ID becomes invalid. Such an ID may be used to safely store an abstract
+  * reference to one Pool element for longer time. Since the Pool classes
+  * automatically detect whether an ID became invalid, using such an ID is thus
+  * safer than storing an Iterator or even a raw pointer in use case scenarios of
+  * storing long term references to Pool elements.
+  *
+  * This ID type is currently set (constrained) to 32-bit because the current
+  * real-time instrument script infrastructure implementation, which heavily
+  * relies on element IDs, is currently using 32-bit for its integer script
+  * variable type.
+  */
+ typedef uint32_t pool_element_id_t;
  // just symbol prototyping
  template<typename T> class Pool;
  template<typename T> class RTList;
-Line 61 
 class RTListBase {
+Line 78 
 class RTListBase {
              #if CONFIG_DEVMODE
              RTListBase<T1>* list; // list to which this node currently belongs to
              #endif // CONFIG_DEVMODE
+             uint reincarnation; // just for Pool::fromID()
              _Node() {
                  next = NULL;
-Line 69 
 class RTListBase {
+Line 87 
 class RTListBase {
                  #if CONFIG_DEVMODE
                  list = NULL;
                  #endif // CONFIG_DEVMODE
+                 reincarnation = 0;
+             }
+             inline void bumpReincarnation(uint bits) {
+                 reincarnation++;
+                 // constrain the bitrange of "reincarnation", because Pool::fromID() will shift up/down for pool_element_id_t and compare this bitwise
+                 reincarnation &= ((1 << bits) - 1);
              }
          };
          typedef _Node<T> Node;
      public:
+         /**
+          * Pointer-like object which allows to iterate over elements of a RTList,
+          * similar to iterators of STL container classes. Note that the main
+          * purpose of this class is to access elements of a list / pool i.e.
+          * within a @c while() loop. If you rather want to keep a reference to
+          * one particular element (i.e. for longer time) then you might
+          * consider using @c pool_element_id_t variables instead.
+          */
          template<typename T1>
          class _Iterator {
              public:
-Line 145 
 class RTListBase {
+Line 178 
 class RTListBase {
                      }
                      #endif // CONFIG_DEVMODE
                      return *current->data;
+                 }
+                 inline const T1& operator*() const {
+                     #if CONFIG_DEVMODE
+                     if (!isValid()) { // if iterator became invalidated
+                         #if CONFIG_RT_EXCEPTIONS
+                         throw std::runtime_error(__err_msg_iterator_invalidated);
+                         #else
+                         std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
+                         return *((const T1*)NULL); // force segfault if iterator became invalidated
+                         #endif // CONFIG_RT_EXCEPTIONS
+                     }
+                     #endif // CONFIG_DEVMODE
+                     return *current->data;
                  }
                  inline T1* operator->() {
-Line 162 
 class RTListBase {
+Line 208 
 class RTListBase {
                      return current->data;
                  }
-                 inline bool operator==(const _Iterator<T1> other) {
+                 inline const T1* operator->() const {
+                     #if CONFIG_DEVMODE
+                     if (!isValid()) { // if iterator became invalidated
+                         #if CONFIG_RT_EXCEPTIONS
+                         throw std::runtime_error(__err_msg_iterator_invalidated);
+                         #else
+                         std::cerr << __err_msg_iterator_invalidated << std::endl << std::flush;
+                         return (const T1*)NULL; // force segfault if iterator became invalidated
+                         #endif // CONFIG_RT_EXCEPTIONS
+                     }
+                     #endif // CONFIG_DEVMODE
+                     return current->data;
+                 }
+                 inline bool operator==(const _Iterator<T1> other) const {
                      return current == other.current;
                  }
-                 inline bool operator!=(const _Iterator<T1> other) {
+                 inline bool operator!=(const _Iterator<T1> other) const {
                      return current != other.current;
                  }
-Line 178 
 class RTListBase {
+Line 238 
 class RTListBase {
                      return !(current && current->data);
                  }
+                 /**
+                  * Moves the element pointed by this Iterator from its current
+                  * list to the beginning of the destination list @a pDstList.
+                  *
+                  * @b CAUTION: When this method returns, this Iterator does
+                  * @b NOT point to the element on the new list anymore, instead it
+                  * points at a completely different element! In case of a
+                  * forward Iterator this Iterator object will point to the
+                  * previous element on the source list, in case of a backward
+                  * Iterator it will point to the subsequent element on the
+                  * source list. This behavior is enforced to avoid breaking an
+                  * active loop code working with this Iterator object.
+                  *
+                  * Thus if you intend to continue working with the same element,
+                  * you should do like this:
+                  * @code
+                  * it = it.moveToEndOf(anotherList);
+                  * @endcode
+                  *
+                  * @param pDstList - destination list
+                  * @returns Iterator object pointing at the moved element on
+                  *          the destination list
+                  */
                  inline _Iterator moveToEndOf(RTListBase<T1>* pDstList) {
                      detach();
                      pDstList->append(*this);
-Line 186 
 class RTListBase {
+Line 269 
 class RTListBase {
                      return iterOnDstList;
                  }
+                 /**
+                  * Moves the element pointed by this Iterator from its current
+                  * list to the end of destination list @a pDstList.
+                  *
+                  * @b CAUTION: When this method returns, this Iterator does
+                  * @b NOT point to the element on the new list anymore, instead it
+                  * points at a completely different element! In case of a
+                  * forward Iterator this Iterator object will point to the
+                  * previous element on the source list, in case of a backward
+                  * Iterator it will point to the subsequent element on the
+                  * source list. This behavior is enforced to avoid breaking an
+                  * active loop code working with this Iterator object.
+                  *
+                  * Thus if you intend to continue working with the same element,
+                  * you should do like this:
+                  * @code
+                  * it = it.moveToBeginOf(anotherList);
+                  * @endcode
+                  *
+                  * @param pDstList - destination list
+                  * @returns Iterator object pointing at the moved element on
+                  *          the destination list
+                  */
                  inline _Iterator moveToBeginOf(RTListBase<T1>* pDstList) {
                      detach();
                      pDstList->prepend(*this);
-Line 194 
 class RTListBase {
+Line 300 
 class RTListBase {
                      return iterOnDstList;
                  }
+                 /**
+                  * Moves the element pointed by this Iterator from its current
+                  * position to the position right before @a itDst. That move
+                  * may either be from and to the same list, or to a another
+                  * list.
+                  *
+                  * @b CAUTION: When this method returns, this Iterator does
+                  * @b NOT point to the element on the new list anymore, instead it
+                  * points at a completely different element! In case of a
+                  * forward Iterator this Iterator object will point to the
+                  * previous element on the source list, in case of a backward
+                  * Iterator it will point to the subsequent element on the
+                  * source list. This behavior is enforced to avoid breaking an
+                  * active loop code working with this Iterator object.
+                  *
+                  * Thus if you intend to continue working with the same element,
+                  * you should do like this:
+                  * @code
+                  * itSourceElement = itSourceElement.moveBefore(itDestinationElement);
+                  * @endcode
+                  *
+                  * @param itDst - destination element to be inserted before
+                  * @returns Iterator object pointing at the moved element on
+                  *          the destination list
+                  */
+                 inline _Iterator moveBefore(_Iterator<T1> itDst) {
+                     detach();
+                     RTList<T1>::prependBefore(*this, itDst);
+                     _Iterator iterOnDstList = _Iterator(current);
+                     current = fallback;
+                     return iterOnDstList;
+                 }
+                 /**
+                  * Moves the element pointed by this Iterator from its current
+                  * position to the position right after @a itDst. That move
+                  * may either be from and to the same list, or to a another
+                  * list.
+                  *
+                  * @b CAUTION: When this method returns, this Iterator does
+                  * @b NOT point to the element on the new list anymore, instead it
+                  * points at a completely different element! In case of a
+                  * forward Iterator this Iterator object will point to the
+                  * previous element on the source list, in case of a backward
+                  * Iterator it will point to the subsequent element on the
+                  * source list. This behavior is enforced to avoid breaking an
+                  * active loop code working with this Iterator object.
+                  *
+                  * Thus if you intend to continue working with the same element,
+                  * you should do like this:
+                  * @code
+                  * itSourceElement = itSourceElement.moveAfter(itDestinationElement);
+                  * @endcode
+                  *
+                  * @param itDst - destination element to be inserted after
+                  * @returns Iterator object pointing at the moved element on
+                  *          the destination list
+                  */
+                 inline _Iterator moveAfter(_Iterator<T1> itDst) {
+                     detach();
+                     RTList<T1>::appendAfter(*this, itDst);
+                     _Iterator iterOnDstList = _Iterator(current);
+                     current = fallback;
+                     return iterOnDstList;
+                 }
                  #if CONFIG_DEVMODE
-                 inline bool isValid() {
+                 inline bool isValid() const {
                      return current->list == list;
                  }
                  #endif // CONFIG_DEVMODE
-Line 232 
 class RTListBase {
+Line 404 
 class RTListBase {
                      #endif // CONFIG_DEVMODE
                  }
+                 inline const Node* node() const {
+                     #if CONFIG_DEVMODE
+                     #if CONFIG_RT_EXCEPTIONS
+                     if (isValid()) return current;
+                     else throw std::runtime_error(__err_msg_iterator_invalidated);
+                     #else
+                     return (isValid()) ? current : (const Node*)NULL; // force segfault if iterator became invalidated
+                     #endif // CONFIG_RT_EXCEPTIONS
+                     #else
+                     return current;
+                     #endif // CONFIG_DEVMODE
+                 }
                  inline void detach() {
                      RTListBase<T1>::detach(*this);
                  }
-Line 258 
 class RTListBase {
+Line 443 
 class RTListBase {
              return Iterator(&_end, Iterator::dir_backward);
          }
-         inline bool isEmpty() {
+         inline bool isEmpty() const {
              return _begin.next == &_end;
          }
-Line 346 
 class RTListBase {
+Line 531 
 class RTListBase {
              #endif // CONFIG_DEVMODE
          }
+         static inline void prependBefore(Iterator itSrc, Iterator itDst) {
+             Node* src = itSrc.current;
+             Node* dst = itDst.current;
+             Node* prev = dst->prev;
+             prev->next = src;
+             dst->prev  = src;
+             src->prev  = prev;
+             src->next  = dst;
+             #if CONFIG_DEVMODE
+             src->list = this;
+             #endif // CONFIG_DEVMODE
+         }
+         static inline void appendAfter(Iterator itSrc, Iterator itDst) {
+             Node* src = itSrc.current;
+             Node* dst = itDst.current;
+             Node* next = dst->next;
+             next->prev = src;
+             dst->next  = src;
+             src->prev  = dst;
+             src->next  = next;
+             #if CONFIG_DEVMODE
+             src->list = this;
+             #endif // CONFIG_DEVMODE
+         }
          static inline void detach(Iterator itElement) {
              Node* pNode = itElement.node();
              Node* prev = pNode->prev; // if a segfault happens here, then because 'itElement' Iterator became invalidated
-Line 381 
 class RTList : public RTListBase<T> {
+Line 592 
 class RTList : public RTListBase<T> {
          RTList(Pool<T>* pPool) : RTListBase<T>::RTListBase() {
              this->pPool = pPool;
          }
+         /**
+          * Copy constructor
+          */
+         RTList(RTList<T>& list) : RTListBase<T>::RTListBase() {
+             this->pPool = list.pPool;
+             Iterator it = list.first();
+             Iterator end = list.end();
+             for(; it != end; ++it) {
+                 if (poolIsEmpty()) break;
+                 *(allocAppend()) = *it;
+             }
+         }
          virtual ~RTList() {
              clear();
          }
-         inline bool poolIsEmpty() {
+         inline bool poolIsEmpty() const {
              return pPool->poolIsEmpty();
          }
          inline Iterator allocAppend() {
              if (pPool->poolIsEmpty()) return RTListBase<T>::begin();
              Iterator element = pPool->alloc();
-             append(element);
+             this->append(element);
              #if CONFIG_DEVMODE
              element.list = this;
              #endif // CONFIG_DEVMODE
-Line 425 
 class RTList : public RTListBase<T> {
+Line 649 
 class RTList : public RTListBase<T> {
              }
          }
+         inline pool_element_id_t getID(const T* obj) const {
+             return pPool->getID(obj);
+         }
+         inline pool_element_id_t getID(const Iterator& it) const {
+             return pPool->getID(&*it);
+         }
+         inline Iterator fromID(pool_element_id_t id) const {
+             return pPool->fromID(id);
+         }
+         inline Iterator fromPtr(const T* obj) const {
+             return pPool->fromPtr(obj);
+         }
      protected:
          Pool<T>* pPool;
  };
-Line 438 
 class Pool : public RTList<T> {
+Line 678 
 class Pool : public RTList<T> {
          Node*         nodes;
          T*            data;
          RTListBase<T> freelist; // not yet allocated elements
-         int           poolsize;
+         uint          poolsize;
+         // following 3 used for element ID generation (and vice versa)
+         uint          poolsizebits; ///< Amount of bits required to index all elements of this pool (according to current pool size).
+         uint          reservedbits; ///< 3rd party reserved bits on the left side of id (default: 0).
+         uint          reincarnationbits; ///< Amount of bits allowed for reincarnation counter.
-         Pool(int Elements) : RTList<T>::RTList(this) {
+         Pool(int Elements) : RTList<T>::RTList(this), reservedbits(0) {
              _init(Elements);
          }
-Line 449 
 class Pool : public RTList<T> {
+Line 693 
 class Pool : public RTList<T> {
              if (data)  delete[] data;
          }
-         inline bool poolIsEmpty() {
+         /**
+          * Returns true if there is at least one free element that could be
+          * allocated from the pool with i.e. allocAppend() or allocPreprend().
+          *
+          * @see poolHasFreeElements()
+          */
+         inline bool poolIsEmpty() const {
              return freelist.isEmpty();
          }
          /**
+          * Returns true if at least the requested amount of free @a elements is
+          * currently available for being allocated from the pool with i.e.
+          * allocAppend() or allocPreprend().
+          *
+          * @see poolIsEmpty()
+          */
+         bool poolHasFreeElements(int elements) {
+             for (Iterator it = freelist.first(); it != freelist.end() && elements >= 0; ++it)
+                 --elements;
+             return elements <= 0;
+         }
+         /**
           * Returns the current size of the pool, that is the amount of
           * pre-allocated elements from the operating system. It equals the
           * amount of elements given to the constructor unless resizePool()
-Line 461 
 class Pool : public RTList<T> {
+Line 724 
 class Pool : public RTList<T> {
           *
           * @see resizePool()
           */
-         int poolSize() const {
+         uint poolSize() const {
              return poolsize;
          }
-Line 494 
 class Pool : public RTList<T> {
+Line 757 
 class Pool : public RTList<T> {
              _init(Elements);
          }
+         /**
+          * Sets the amount of bits on the left hand side of pool_element_id_t
+          * numbers to be reserved for 3rd party usage. So if you pass @c 1 for
+          * argument @a bits for example, then all generated element IDs will be
+          * maximum 31 bit large.
+          *
+          * By default there are no reserved bits, and thus by default all IDs
+          * are max. 32 bit large.
+          *
+          * @param bits - amount of bits to reserve on every ID for other purposes
+          * @see pool_element_id_t
+          */
+         void setPoolElementIDsReservedBits(uint bits) {
+             reservedbits = bits;
+             updateReincarnationBits();
+         }
+         /**
+          * Returns an abstract, unique numeric ID for the given object of
+          * this pool, it returns 0 in case the passed object is not a member
+          * of this Pool, i.e. because it is simply an invalid pointer or member
+          * of another Pool. The returned ID is unique among all elements of this
+          * Pool and it differs with each reincarnation of an object. That means
+          * each time you free an element to and allocate the same element back
+          * from the Pool, it will have a different ID.
+          *
+          * A valid ID will never be zero, so you may use ID values of 0 in your
+          * data structures for special purposes (i.e. reflecting an invalid
+          * object ID or not yet assigned object).
+          *
+          * Members are always translated both, from Iterators/pointers to IDs,
+          * and from IDs to Iterators/pointers in constant time.
+          *
+          * You might want to use this alternative approach of referencing Pool
+          * members under certain scenarios. For example if you need to expose
+          * an ID to the end user and/or if you want to represent an object of
+          * this pool by a smaller number instead of a native pointer (i.e. 16
+          * bits vs. 64 bits). You can also detect this way whether the object
+          * has already been freed / reallocated from the Pool in the meantime.
+          *
+          * @param obj - raw pointer to a data member of this Pool
+          * @returns unique numeric ID (!= 0) of @a obj or 0 if pointer was invalid
+          */
+         pool_element_id_t getID(const T* obj) const {
+             if (!poolsize) return 0;
+             int index = int( obj - &data[0] );
+             if (index < 0 || index >= poolsize) return 0;
+             return ((nodes[index].reincarnation << poolsizebits) | index) + 1;
+         }
+         /**
+          * Overridden convenience method, behaves like the method above.
+          */
+         pool_element_id_t getID(const Iterator& it) const {
+             return getID(&*it);
+         }
+         /**
+          * Returns an Iterator object of the Pool data member reflected by the
+          * given abstract, unique numeric ID, it returns an invalid Iterator in
+          * case the ID is invalid or if the Pool's data element reflected by
+          * given ID was at least once released/freed back to the Pool in the
+          * meantime.
+          *
+          * Members are always translated both, from Iterators/pointers to IDs,
+          * and from IDs to Iterators/pointers in constant time.
+          *
+          * You might want to use this alternative approach of referencing Pool
+          * members under certain scenarios. For example if you need to expose
+          * an ID to the end user and/or if you want to represent an object of
+          * this pool by a smaller number instead of a native pointer (i.e. 16
+          * bits vs. 64 bits). You can also detect this way whether the object
+          * has already been freed / reallocated from the Pool in the meantime.
+          *
+          * @param id - unique ID (!= 0) of a Pool's data member
+          * @returns Iterator object pointing to Pool's data element, invalid
+          *          Iterator in case ID was invalid or data element was freed
+          */
+         Iterator fromID(pool_element_id_t id) const {
+             //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
+             if (id == 0 || id == -1) return Iterator(); // invalid iterator
+             id--;
+             const uint bits = poolsizebits;
+             uint index = id & ((1 << bits) - 1);
+             if (index >= poolsize) return Iterator(); // invalid iterator
+             Node* node = &nodes[index];
+             uint reincarnation = id >> bits;
+             if (reincarnation != node->reincarnation) return Iterator(); // invalid iterator
+             return Iterator(node);
+         }
+         /**
+          * Returns an Iterator object for the object pointed by @a obj. This
+          * method will check whether the supplied object is actually part of
+          * this pool, and if it is not part of this pool an invalid Iterator is
+          * returned instead.
+          *
+          * @param obj - raw pointer to an object managed by this pool
+          * @returns Iterator object pointing to the supplied object, invalid
+          *          Iterator in case object is not part of this pool
+          */
+         Iterator fromPtr(const T* obj) const {
+             if (!poolsize) return Iterator(); // invalid iterator
+             int index = int( obj - &data[0] );
+             if (index < 0 || index >= poolsize) return Iterator(); // invalid iterator
+             return Iterator(&nodes[index]);
+         }
      protected:
          // caution: assumes pool (that is freelist) is not empty!
          inline Iterator alloc() {
-Line 503 
 class Pool : public RTList<T> {
+Line 874 
 class Pool : public RTList<T> {
          }
          inline void freeToPool(Iterator itElement) {
+             itElement.node()->bumpReincarnation(reincarnationbits);
              freelist.append(itElement);
          }
          inline void freeToPool(Iterator itFirst, Iterator itLast) {
+             for (Node* n = itFirst.node(); true; n = n->next) {
+                 n->bumpReincarnation(reincarnationbits);
+                 if (n == itLast.node()) break;
+             }
              freelist.append(itFirst, itLast);
          }
-Line 521 
 class Pool : public RTList<T> {
+Line 897 
 class Pool : public RTList<T> {
                  freelist.append(&nodes[i]);
              }
              poolsize = Elements;
+             poolsizebits = bitsForSize(poolsize + 1); // +1 here just because IDs are always incremented by one (to avoid them ever being zero)
+             updateReincarnationBits();
+         }
+         inline void updateReincarnationBits() {
+             reincarnationbits = sizeof(pool_element_id_t) * 8 - poolsizebits - reservedbits;
+         }
+         inline static int bitsForSize(int size) {
+             if (!size) return 0;
+             size--;
+             int bits = 0;
+             for (; size > 1; bits += 2, size >>= 2);
+             return bits + size;
          }
  };

 Legend:



Removed from v.1800
 


changed lines


 
Added in v.3293
 Legend:



Removed from v.1800
 


changed lines


 
Added in v.3293
-Removed from v.1800
+Added in v.3293

	ViewVC Help
Powered by ViewVC