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
36namespace 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.
49template <class T>
50class TreeNode {
51public:
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
150private:
151    NodeType* m_next;
152    NodeType* m_previous;
153    NodeType* m_parent;
154    NodeType* m_firstChild;
155    NodeType* m_lastChild;
156};
157
158template<class T>
159inline 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
177template<class T>
178inline 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
186template<class T>
187inline 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
202using WTF::TreeNode;
203using WTF::traverseNext;
204using WTF::traverseNextPostOrder;
205
206#endif
207