src/third_party/WebKit/Source/wtf/TreeNode.h

   1 /*
   2  * Copyright (C) 2013 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #ifndef TreeNode_h
  32 #define TreeNode_h
  33
  34 #include "wtf/Assertions.h"
  35
  36 namespace WTF {
  37
  38 //
  39 // TreeNode is generic, ContainerNode-like linked tree data structure.
  40 // There are a few notable difference between TreeNode and Node:
  41 //
  42 //  * Each TreeNode node is NOT ref counted. The user have to retain its lifetime somehow.
  43 //    FIXME: lifetime management could be parameterized so that ref counted implementations can be used.
  44 //  * It ASSERT()s invalid input. The callers have to ensure that given parameter is sound.
  45 //  * There is no branch-leaf difference. Every node can be a parent of other node.
  46 //
  47 template <class T>
  48 class TreeNode {
  49 public:
  50     typedef T NodeType;
  51
  52     TreeNode()
  53         : m_next(0)
  54         , m_previous(0)
  55         , m_parent(0)
  56         , m_firstChild(0)
  57         , m_lastChild(0)
  58     {
  59     }
  60
  61     NodeType* next() const { return m_next; }
  62     NodeType* previous() const { return m_previous; }
  63     NodeType* parent() const { return m_parent; }
  64     NodeType* firstChild() const { return m_firstChild; }
  65     NodeType* lastChild() const { return m_lastChild; }
  66     NodeType* here() const { return static_cast<NodeType*>(const_cast<TreeNode*>(this)); }
  67
  68     bool orphan() const { return !m_parent && !m_next && !m_previous && !m_firstChild && !m_lastChild; }
  69     bool hasChildren() const { return m_firstChild; }
  70
  71     void insertBefore(NodeType* newChild, NodeType* refChild)
  72     {
  73         ASSERT(!newChild->parent());
  74         ASSERT(!newChild->next());
  75         ASSERT(!newChild->previous());
  76
  77         ASSERT(!refChild || this == refChild->parent());
  78
  79         if (!refChild) {
  80             appendChild(newChild);
  81             return;
  82         }
  83
  84         NodeType* newPrevious = refChild->previous();
  85         newChild->m_parent = here();
  86         newChild->m_next = refChild;
  87         newChild->m_previous = newPrevious;
  88         refChild->m_previous = newChild;
  89         if (newPrevious)
  90             newPrevious->m_next = newChild;
  91         else
  92             m_firstChild = newChild;
  93     }
  94
  95     void appendChild(NodeType* child)
  96     {
  97         ASSERT(!child->parent());
  98         ASSERT(!child->next());
  99         ASSERT(!child->previous());
 100
 101         child->m_parent = here();
 102
 103         if (!m_lastChild) {
 104             ASSERT(!m_firstChild);
 105             m_lastChild = m_firstChild = child;
 106             return;
 107         }
 108
 109         ASSERT(!m_lastChild->m_next);
 110         NodeType* oldLast = m_lastChild;
 111         m_lastChild = child;
 112
 113         child->m_previous = oldLast;
 114         oldLast->m_next = child;
 115     }
 116
 117     NodeType* removeChild(NodeType* child)
 118     {
 119         ASSERT(child->parent() == this);
 120
 121         if (m_firstChild == child)
 122             m_firstChild = child->next();
 123         if (m_lastChild == child)
 124             m_lastChild = child->previous();
 125
 126         NodeType* oldNext = child->next();
 127         NodeType* oldPrevious = child->previous();
 128         child->m_parent = child->m_next = child->m_previous = 0;
 129
 130         if (oldNext)
 131             oldNext->m_previous = oldPrevious;
 132         if (oldPrevious)
 133             oldPrevious->m_next = oldNext;
 134
 135         return child;
 136     }
 137
 138     void takeChildrenFrom(NodeType* oldParent)
 139     {
 140         ASSERT(oldParent != this);
 141         while (oldParent->hasChildren()) {
 142             NodeType* child = oldParent->firstChild();
 143             oldParent->removeChild(child);
 144             this->appendChild(child);
 145         }
 146     }
 147
 148 private:
 149     NodeType* m_next;
 150     NodeType* m_previous;
 151     NodeType* m_parent;
 152     NodeType* m_firstChild;
 153     NodeType* m_lastChild;
 154 };
 155
 156 template<class T>
 157 inline typename TreeNode<T>::NodeType* traverseNext(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0)
 158 {
 159     if (typename TreeNode<T>::NodeType* next = current->firstChild())
 160         return next;
 161     if (current == stayWithin)
 162         return 0;
 163     if (typename TreeNode<T>::NodeType* next = current->next())
 164         return next;
 165     for (typename TreeNode<T>::NodeType* parent = current->parent(); parent; parent = parent->parent()) {
 166         if (parent == stayWithin)
 167             return 0;
 168         if (typename TreeNode<T>::NodeType* next = parent->next())
 169             return next;
 170     }
 171
 172     return 0;
 173 }
 174
 175 template<class T>
 176 inline typename TreeNode<T>::NodeType* traverseFirstPostOrder(const TreeNode<T>* current)
 177 {
 178     typename TreeNode<T>::NodeType* first = current->here();
 179     while (first->firstChild())
 180         first = first->firstChild();
 181     return first;
 182 }
 183
 184 template<class T>
 185 inline typename TreeNode<T>::NodeType* traverseNextPostOrder(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0)
 186 {
 187     if (current == stayWithin)
 188         return 0;
 189
 190     typename TreeNode<T>::NodeType* next = current->next();
 191     if (!next)
 192         return current->parent();
 193     while (next->firstChild())
 194         next = next->firstChild();
 195     return next;
 196 }
 197
 198 }
 199
 200 using WTF::TreeNode;
 201 using WTF::traverseNext;
 202 using WTF::traverseNextPostOrder;
 203
 204 #endif