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 // FIXME: oilpan: Trace tree node edges to ensure we don't have dangling pointers.
  48 // As it is used in HTMLImport it is safe since they all die together.
  49 template <class T>
  50 class TreeNode {
  51 public:
  52     typedef T NodeType;
  53
  54     TreeNode()
  55         : m_next(0)
  56         , m_previous(0)
  57         , m_parent(0)
  58         , m_firstChild(0)
  59         , m_lastChild(0)
  60     {
  61     }
  62
  63     NodeType* next() const { return m_next; }
  64     NodeType* previous() const { return m_previous; }
  65     NodeType* parent() const { return m_parent; }
  66     NodeType* firstChild() const { return m_firstChild; }
  67     NodeType* lastChild() const { return m_lastChild; }
  68     NodeType* here() const { return static_cast<NodeType*>(const_cast<TreeNode*>(this)); }
  69
  70     bool orphan() const { return !m_parent && !m_next && !m_previous && !m_firstChild && !m_lastChild; }
  71     bool hasChildren() const { return m_firstChild; }
  72
  73     void insertBefore(NodeType* newChild, NodeType* refChild)
  74     {
  75         ASSERT(!newChild->parent());
  76         ASSERT(!newChild->next());
  77         ASSERT(!newChild->previous());
  78
  79         ASSERT(!refChild || this == refChild->parent());
  80
  81         if (!refChild) {
  82             appendChild(newChild);
  83             return;
  84         }
  85
  86         NodeType* newPrevious = refChild->previous();
  87         newChild->m_parent = here();
  88         newChild->m_next = refChild;
  89         newChild->m_previous = newPrevious;
  90         refChild->m_previous = newChild;
  91         if (newPrevious)
  92             newPrevious->m_next = newChild;
  93         else
  94             m_firstChild = newChild;
  95     }
  96
  97     void appendChild(NodeType* child)
  98     {
  99         ASSERT(!child->parent());
 100         ASSERT(!child->next());
 101         ASSERT(!child->previous());
 102
 103         child->m_parent = here();
 104
 105         if (!m_lastChild) {
 106             ASSERT(!m_firstChild);
 107             m_lastChild = m_firstChild = child;
 108             return;
 109         }
 110
 111         ASSERT(!m_lastChild->m_next);
 112         NodeType* oldLast = m_lastChild;
 113         m_lastChild = child;
 114
 115         child->m_previous = oldLast;
 116         oldLast->m_next = child;
 117     }
 118
 119     NodeType* removeChild(NodeType* child)
 120     {
 121         ASSERT(child->parent() == this);
 122
 123         if (m_firstChild == child)
 124             m_firstChild = child->next();
 125         if (m_lastChild == child)
 126             m_lastChild = child->previous();
 127
 128         NodeType* oldNext = child->next();
 129         NodeType* oldPrevious = child->previous();
 130         child->m_parent = child->m_next = child->m_previous = 0;
 131
 132         if (oldNext)
 133             oldNext->m_previous = oldPrevious;
 134         if (oldPrevious)
 135             oldPrevious->m_next = oldNext;
 136
 137         return child;
 138     }
 139
 140     void takeChildrenFrom(NodeType* oldParent)
 141     {
 142         ASSERT(oldParent != this);
 143         while (oldParent->hasChildren()) {
 144             NodeType* child = oldParent->firstChild();
 145             oldParent->removeChild(child);
 146             this->appendChild(child);
 147         }
 148     }
 149
 150 private:
 151     NodeType* m_next;
 152     NodeType* m_previous;
 153     NodeType* m_parent;
 154     NodeType* m_firstChild;
 155     NodeType* m_lastChild;
 156 };
 157
 158 template<class T>
 159 inline typename TreeNode<T>::NodeType* traverseNext(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0)
 160 {
 161     if (typename TreeNode<T>::NodeType* next = current->firstChild())
 162         return next;
 163     if (current == stayWithin)
 164         return 0;
 165     if (typename TreeNode<T>::NodeType* next = current->next())
 166         return next;
 167     for (typename TreeNode<T>::NodeType* parent = current->parent(); parent; parent = parent->parent()) {
 168         if (parent == stayWithin)
 169             return 0;
 170         if (typename TreeNode<T>::NodeType* next = parent->next())
 171             return next;
 172     }
 173
 174     return 0;
 175 }
 176
 177 template<class T>
 178 inline typename TreeNode<T>::NodeType* traverseFirstPostOrder(const TreeNode<T>* current)
 179 {
 180     typename TreeNode<T>::NodeType* first = current->here();
 181     while (first->firstChild())
 182         first = first->firstChild();
 183     return first;
 184 }
 185
 186 template<class T>
 187 inline typename TreeNode<T>::NodeType* traverseNextPostOrder(const TreeNode<T>* current, const TreeNode<T>* stayWithin = 0)
 188 {
 189     if (current == stayWithin)
 190         return 0;
 191
 192     typename TreeNode<T>::NodeType* next = current->next();
 193     if (!next)
 194         return current->parent();
 195     while (next->firstChild())
 196         next = next->firstChild();
 197     return next;
 198 }
 199
 200 }
 201
 202 using WTF::TreeNode;
 203 using WTF::traverseNext;
 204 using WTF::traverseNextPostOrder;
 205
 206 #endif