Home | History | Annotate | Download | only in wtf 
      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
    207