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

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

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

revision 2947 by schoenebeck, Sun Apr 10 18:22:23 2016 UTC revision 2948 by schoenebeck, Fri Jul 15 15:29:04 2016 UTC
# Line 1  Line 1 
1  /*  /*
2   * Copyright (c) 2015 Christian Schoenebeck   * Copyright (c) 2015-2016 Christian Schoenebeck
3   *   *
4   * http://www.linuxsampler.org   * http://www.linuxsampler.org
5   *   *
# Line 15  Line 15 
15    
16  #include "RTMath.h"  #include "RTMath.h"
17    
18    class RTAVLTreeBase;
19    
20  /**  /**
21   * @brief Base class of RTAVLTree elements.   * @brief Base class of RTAVLTree elements.
22   *   *
# Line 38  Line 40 
40   * terminal.   * terminal.
41   */   */
42  class RTAVLNode {  class RTAVLNode {
43    public:
44        /**
45         * Returns the current RTAVLTree this node is a member of.
46         *
47         * @b CAUTION: This method must only be used if RTAVLTree's template
48         * parameter was set to T_SAFE = true. Using the result of this method call
49         * with T_SAFE = false may result in undefined behavior!
50         */
51        RTAVLTreeBase* rtavlTree() const { return tree; }
52    
53  protected:  protected:
54      /**      /**
55       * Initialize the members of this node. It is not necessearily required to       * Initialize the members of this node. It is not necessearily required to
# Line 53  protected: Line 65  protected:
65          prevTwin = nextTwin = this;          prevTwin = nextTwin = this;
66          balance = 0;          balance = 0;
67          twinHead = true;          twinHead = true;
68            tree = NULL;
69      }      }
70    
71      /**      /**
# Line 77  protected: Line 90  protected:
90      RTAVLNode* nextTwin;      RTAVLNode* nextTwin;
91      int balance;      int balance;
92      bool twinHead;      bool twinHead;
93      template<class T_node> friend class RTAVLTree;      RTAVLTreeBase* tree; ///< This is only used by RTAVLTree if T_SAFE = true
94        template<class T_node, bool T_SAFE> friend class RTAVLTree;
95    };
96    
97    /**
98     * Abstract base class for deriving tempalte class RTAVLTree. This is just
99     * needed for the "tree" pointer member variable in RTAVLNode.
100     */
101    class RTAVLTreeBase {
102    public:
103  };  };
104    
105  /**  /**
# Line 98  protected: Line 120  protected:
120   * implementations, this implementation of an AVL tree provides   * implementations, this implementation of an AVL tree provides
121   * constant time average complexity for erase operations.   * constant time average complexity for erase operations.
122   *   *
123     * @c T_SAFE: this boolean template class parameter defines whether the tree's
124     * algorithm should be more safe but a bit slower or rather fast and less safe.
125     * If T_SAFE = true then additional checks and measures will be performed when
126     * calling insert() or erase(). The latter methods will then check whether the
127     * passed node is already part of the tree and act accordingly to avoid
128     * undefined behavior which could happen if T_SAFE = false. So if you decide to
129     * set T_SAFE = false then it is your responsibility to only insert() elements
130     * to this tree which are not yet members of the tree and to only erase()
131     * nodes which are really members of the tree. The only real performance
132     * penalty that comes with T_SAFE = true is the efficiency of the clear() method
133     * which will be much slower than with T_SAFE = false. See the description of the
134     * clear() method for the precise performance differences regarding T_SAFE.
135     *
136   * @b IMPORTANT: some of the methods of this class are only intended for unit   * @b IMPORTANT: some of the methods of this class are only intended for unit
137   * tests and debugging purposes and are not real-time safe! Those methods are   * tests and debugging purposes and are not real-time safe! Those methods are
138   * explicitly marked as such and must not be used in a real-time context!   * explicitly marked as such and must not be used in a real-time context!
139   */   */
140  template<class T_node>  template<class T_node, bool T_SAFE = true>
141  class RTAVLTree {  class RTAVLTree : public RTAVLTreeBase {
142  public:  public:
143      enum Dir_t {      enum Dir_t {
144          LEFT,          LEFT,
# Line 140  public: Line 175  public:
175       * some non-unique keys).       * some non-unique keys).
176       *       *
177       * Trying to insert an item that is already part of the tree will be       * Trying to insert an item that is already part of the tree will be
178       * detected and ignored. Note however, that this detection is limited to       * detected and ignored. Note however, that if T_SAFE = false then this
179       * unique elements! So better take care to only insert a new element that       * detection is limited to unique elements! So if T_SAFE = false then better
180       * is not yet member of the tree.       * take care to only insert a new element that is not yet member of the
181         * tree.
182       *       *
183       * This method is real-time safe.       * This method is real-time safe.
184       *       *
# Line 151  public: Line 187  public:
187       * @param item - new element to be inserted into the tree       * @param item - new element to be inserted into the tree
188       */       */
189      void insert(T_node& item) {      void insert(T_node& item) {
190            if (T_SAFE && item.tree == this) return;
191    
192          if (!root) {          if (!root) {
193              item.reset();              item.reset();
194                if (T_SAFE) item.tree = this;
195              root = &item;              root = &item;
196              ++nodesCount;              ++nodesCount;
197              return;              return;
# Line 170  public: Line 209  public:
209                      // it is the same key, but different item, so insert the                      // it is the same key, but different item, so insert the
210                      // passed item to this twin ring                      // passed item to this twin ring
211                      item.reset();                      item.reset();
212                        if (T_SAFE) item.tree = this;
213                      node->prevTwin->nextTwin = &item;                      node->prevTwin->nextTwin = &item;
214                      item.prevTwin = node->prevTwin;                      item.prevTwin = node->prevTwin;
215                      item.nextTwin = node;                      item.nextTwin = node;
# Line 184  public: Line 224  public:
224                      node = node->children[dir];                      node = node->children[dir];
225                  } else {                  } else {
226                      item.reset();                      item.reset();
227                        if (T_SAFE) item.tree = this;
228                      node->children[dir] = &item;                      node->children[dir] = &item;
229                      item.parent = node;                      item.parent = node;
230                      node = &item;                      node = &item;
# Line 207  public: Line 248  public:
248      }      }
249    
250      /**      /**
251       * Removes the existing element @a item from the tree. It is assumed that       * Removes the existing element @a item from the tree.
252       * the passed @a item is really a member of this tree when this method is       *
253       * called. There are some checks which abort the erase operation if the       * If T_SAFE = true then calling erase() with a node that is not part of
254         * this tree will simply be ignored.
255         *
256         * If T_SAFE = false then it is assumed that the passed @a item is really
257         * a member of this tree when this method is called. There are some checks
258         * even if T_SAFE = false which abort the erase operation if the
259       * passed element is detected not being part of the tree, however these       * passed element is detected not being part of the tree, however these
260       * checks do not cover all possible cases and they also require that       * checks do not cover all possible cases and they also require that
261       * RTAVLNode::reset() was called after the element was allocated. So better       * RTAVLNode::reset() was called after the element was allocated. So better
262       * don't rely on those checks and only call erase() for elements which are       * don't rely on those checks if T_SAFE = flase and only call erase() in this
263       * really a member of this tree at that point.       * case for elements which are really a member of this tree at that point.
264       *       *
265       * This method is real-time safe.       * This method is real-time safe.
266       *       *
# Line 223  public: Line 269  public:
269       * @param item - element of the tree to be removed from the tree       * @param item - element of the tree to be removed from the tree
270       */       */
271      void erase(T_node& item) {      void erase(T_node& item) {
272            if (T_SAFE && item.tree != this) return;
273    
274          if (!root) {          if (!root) {
275              item.reset();              item.reset();
276              return;              return;
# Line 484  public: Line 532  public:
532       * Removes all elements from this tree. That is size() will return @c 0       * Removes all elements from this tree. That is size() will return @c 0
533       * after calling this method.       * after calling this method.
534       *       *
535       * @b IMPORTANT: Note that the current implementation does not reset the       * @b IMPORTANT: For the precise behavior and efficiency of this method, as
536         * well as saftety of subsequent other method calls, it is important which
537         * value you assigned for template class parameter @c T_SAFE :
538         *
539         * If @c T_SAFE @c = @c false then this method does not reset the
540       * invidual element nodes (for performance reasons). Due to this, after       * invidual element nodes (for performance reasons). Due to this, after
541       * calling clear(), you @b must @b not pass any of those elements to the       * calling clear(), you @b must @b not pass any of those elements to the
542       * erase() method of this class, nor to any static method of this class.       * erase() method of this class, nor to any static method of this class.
543       * Doing so would lead to undefined behavior. Re-inserting the elements to       * Doing so would lead to undefined behavior. Re-inserting the elements to
544       * this or to any other tree with insert() is safe though.       * this or to any other tree with insert() is safe though. The advantage on
545         * the other hand is that clear() is extremely fast if T_SAFE = false
546         * (see algorithm complexity below).
547         *
548         * If @c T_SAFE @c = @c true then this method will reset() @b each node of
549         * this tree before removing the nodes and thus clearing the tree. The
550         * advantage is that with T_SAFE = true subsequent method calls on
551         * this tree are way more safe, because guaranteed checks can be performed
552         * whether the respective node is already member of the tree. This safety
553         * comes with the price that clear() calls will be much slower (see
554         * algorithm complexity below).
555       *       *
556       * This method is real-time safe.       * This method is real-time safe.
557       *       *
558       * Complexity: Theta(1).       * Complexity: Theta(1) if T_SAFE = false, or n log n if T_SAFE = true.
559       */       */
560      inline void clear() {      inline void clear() {
561            if (T_SAFE) {
562                while (root) erase(*(T_node*)root);
563            }
564          root = NULL;          root = NULL;
565          nodesCount = 0;          nodesCount = 0;
566      }      }
Legend:
Removed from v.2947  
changed lines
  Added in v.2948
  ViewVC Help
Powered by ViewVC