OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2013 Google Inc. All rights reserved. | 2 * Copyright (C) 2013 Google Inc. All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions are | 5 * modification, are permitted provided that the following conditions are |
6 * met: | 6 * met: |
7 * | 7 * |
8 * * Redistributions of source code must retain the above copyright | 8 * * Redistributions of source code must retain the above copyright |
9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
10 * * Redistributions in binary form must reproduce the above | 10 * * Redistributions in binary form must reproduce the above |
(...skipping 25 matching lines...) Expand all Loading... |
36 namespace WTF { | 36 namespace WTF { |
37 | 37 |
38 // | 38 // |
39 // TreeNode is generic, ContainerNode-like linked tree data structure. | 39 // TreeNode is generic, ContainerNode-like linked tree data structure. |
40 // There are a few notable difference between TreeNode and Node: | 40 // There are a few notable difference between TreeNode and Node: |
41 // | 41 // |
42 // * Each TreeNode node is NOT ref counted. The user have to retain its | 42 // * Each TreeNode node is NOT ref counted. The user have to retain its |
43 // lifetime somehow. | 43 // lifetime somehow. |
44 // FIXME: lifetime management could be parameterized so that ref counted | 44 // FIXME: lifetime management could be parameterized so that ref counted |
45 // implementations can be used. | 45 // implementations can be used. |
46 // * It ASSERT()s invalid input. The callers have to ensure that given | 46 // * It checks invalid input. The callers have to ensure that given |
47 // parameter is sound. | 47 // parameter is sound. |
48 // * There is no branch-leaf difference. Every node can be a parent of other | 48 // * There is no branch-leaf difference. Every node can be a parent of other |
49 // node. | 49 // node. |
50 // | 50 // |
51 // FIXME: oilpan: Trace tree node edges to ensure we don't have dangling | 51 // FIXME: oilpan: Trace tree node edges to ensure we don't have dangling |
52 // pointers. | 52 // pointers. |
53 // As it is used in HTMLImport it is safe since they all die together. | 53 // As it is used in HTMLImport it is safe since they all die together. |
54 template <class T> | 54 template <class T> |
55 class TreeNode { | 55 class TreeNode { |
56 public: | 56 public: |
(...skipping 14 matching lines...) Expand all Loading... |
71 NodeType* here() const { | 71 NodeType* here() const { |
72 return static_cast<NodeType*>(const_cast<TreeNode*>(this)); | 72 return static_cast<NodeType*>(const_cast<TreeNode*>(this)); |
73 } | 73 } |
74 | 74 |
75 bool orphan() const { | 75 bool orphan() const { |
76 return !m_parent && !m_next && !m_previous && !m_firstChild && !m_lastChild; | 76 return !m_parent && !m_next && !m_previous && !m_firstChild && !m_lastChild; |
77 } | 77 } |
78 bool hasChildren() const { return m_firstChild; } | 78 bool hasChildren() const { return m_firstChild; } |
79 | 79 |
80 void insertBefore(NodeType* newChild, NodeType* refChild) { | 80 void insertBefore(NodeType* newChild, NodeType* refChild) { |
81 ASSERT(!newChild->parent()); | 81 DCHECK(!newChild->parent()); |
82 ASSERT(!newChild->next()); | 82 DCHECK(!newChild->next()); |
83 ASSERT(!newChild->previous()); | 83 DCHECK(!newChild->previous()); |
84 | 84 |
85 ASSERT(!refChild || this == refChild->parent()); | 85 DCHECK(!refChild || this == refChild->parent()); |
86 | 86 |
87 if (!refChild) { | 87 if (!refChild) { |
88 appendChild(newChild); | 88 appendChild(newChild); |
89 return; | 89 return; |
90 } | 90 } |
91 | 91 |
92 NodeType* newPrevious = refChild->previous(); | 92 NodeType* newPrevious = refChild->previous(); |
93 newChild->m_parent = here(); | 93 newChild->m_parent = here(); |
94 newChild->m_next = refChild; | 94 newChild->m_next = refChild; |
95 newChild->m_previous = newPrevious; | 95 newChild->m_previous = newPrevious; |
96 refChild->m_previous = newChild; | 96 refChild->m_previous = newChild; |
97 if (newPrevious) | 97 if (newPrevious) |
98 newPrevious->m_next = newChild; | 98 newPrevious->m_next = newChild; |
99 else | 99 else |
100 m_firstChild = newChild; | 100 m_firstChild = newChild; |
101 } | 101 } |
102 | 102 |
103 void appendChild(NodeType* child) { | 103 void appendChild(NodeType* child) { |
104 ASSERT(!child->parent()); | 104 DCHECK(!child->parent()); |
105 ASSERT(!child->next()); | 105 DCHECK(!child->next()); |
106 ASSERT(!child->previous()); | 106 DCHECK(!child->previous()); |
107 | 107 |
108 child->m_parent = here(); | 108 child->m_parent = here(); |
109 | 109 |
110 if (!m_lastChild) { | 110 if (!m_lastChild) { |
111 ASSERT(!m_firstChild); | 111 DCHECK(!m_firstChild); |
112 m_lastChild = m_firstChild = child; | 112 m_lastChild = m_firstChild = child; |
113 return; | 113 return; |
114 } | 114 } |
115 | 115 |
116 ASSERT(!m_lastChild->m_next); | 116 DCHECK(!m_lastChild->m_next); |
117 NodeType* oldLast = m_lastChild; | 117 NodeType* oldLast = m_lastChild; |
118 m_lastChild = child; | 118 m_lastChild = child; |
119 | 119 |
120 child->m_previous = oldLast; | 120 child->m_previous = oldLast; |
121 oldLast->m_next = child; | 121 oldLast->m_next = child; |
122 } | 122 } |
123 | 123 |
124 NodeType* removeChild(NodeType* child) { | 124 NodeType* removeChild(NodeType* child) { |
125 ASSERT(child->parent() == this); | 125 DCHECK_EQ(child->parent(), this); |
126 | 126 |
127 if (m_firstChild == child) | 127 if (m_firstChild == child) |
128 m_firstChild = child->next(); | 128 m_firstChild = child->next(); |
129 if (m_lastChild == child) | 129 if (m_lastChild == child) |
130 m_lastChild = child->previous(); | 130 m_lastChild = child->previous(); |
131 | 131 |
132 NodeType* oldNext = child->next(); | 132 NodeType* oldNext = child->next(); |
133 NodeType* oldPrevious = child->previous(); | 133 NodeType* oldPrevious = child->previous(); |
134 child->m_parent = child->m_next = child->m_previous = 0; | 134 child->m_parent = child->m_next = child->m_previous = 0; |
135 | 135 |
136 if (oldNext) | 136 if (oldNext) |
137 oldNext->m_previous = oldPrevious; | 137 oldNext->m_previous = oldPrevious; |
138 if (oldPrevious) | 138 if (oldPrevious) |
139 oldPrevious->m_next = oldNext; | 139 oldPrevious->m_next = oldNext; |
140 | 140 |
141 return child; | 141 return child; |
142 } | 142 } |
143 | 143 |
144 void takeChildrenFrom(NodeType* oldParent) { | 144 void takeChildrenFrom(NodeType* oldParent) { |
145 ASSERT(oldParent != this); | 145 DCHECK_NE(oldParent, this); |
146 while (oldParent->hasChildren()) { | 146 while (oldParent->hasChildren()) { |
147 NodeType* child = oldParent->firstChild(); | 147 NodeType* child = oldParent->firstChild(); |
148 oldParent->removeChild(child); | 148 oldParent->removeChild(child); |
149 this->appendChild(child); | 149 this->appendChild(child); |
150 } | 150 } |
151 } | 151 } |
152 | 152 |
153 private: | 153 private: |
154 NodeType* m_next; | 154 NodeType* m_next; |
155 NodeType* m_previous; | 155 NodeType* m_previous; |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
203 return next; | 203 return next; |
204 } | 204 } |
205 | 205 |
206 } // namespace WTF | 206 } // namespace WTF |
207 | 207 |
208 using WTF::TreeNode; | 208 using WTF::TreeNode; |
209 using WTF::traverseNext; | 209 using WTF::traverseNext; |
210 using WTF::traverseNextPostOrder; | 210 using WTF::traverseNextPostOrder; |
211 | 211 |
212 #endif | 212 #endif |
OLD | NEW |