1 /*
2 * Copyright (C) 2012 Apple 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
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26 #include "third_party/blink/renderer/platform/wtf/tree_node.h"
27
28 #include "base/memory/scoped_refptr.h"
29 #include "testing/gtest/include/gtest/gtest.h"
30 #include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
31 #include "third_party/blink/renderer/platform/wtf/ref_counted.h"
32
33 namespace WTF {
34
35 class TestTree : public RefCounted<TestTree>, public TreeNode<TestTree> {
36 public:
Create()37 static scoped_refptr<TestTree> Create() {
38 return base::AdoptRef(new TestTree());
39 }
40 };
41
TEST(TreeNodeTest,AppendChild)42 TEST(TreeNodeTest, AppendChild) {
43 scoped_refptr<TestTree> root = TestTree::Create();
44 scoped_refptr<TestTree> first_child = TestTree::Create();
45 scoped_refptr<TestTree> last_child = TestTree::Create();
46
47 root->AppendChild(first_child.get());
48 EXPECT_EQ(root->FirstChild(), first_child.get());
49 EXPECT_EQ(root->LastChild(), first_child.get());
50 EXPECT_EQ(first_child->Parent(), root.get());
51
52 root->AppendChild(last_child.get());
53 EXPECT_EQ(root->FirstChild(), first_child.get());
54 EXPECT_EQ(root->LastChild(), last_child.get());
55 EXPECT_EQ(last_child->Previous(), first_child.get());
56 EXPECT_EQ(first_child->Next(), last_child.get());
57 EXPECT_EQ(last_child->Parent(), root.get());
58 }
59
TEST(TreeNodeTest,InsertBefore)60 TEST(TreeNodeTest, InsertBefore) {
61 scoped_refptr<TestTree> root = TestTree::Create();
62 scoped_refptr<TestTree> first_child = TestTree::Create();
63 scoped_refptr<TestTree> middle_child = TestTree::Create();
64 scoped_refptr<TestTree> last_child = TestTree::Create();
65
66 // Inserting single node
67 root->InsertBefore(last_child.get(), nullptr);
68 EXPECT_EQ(last_child->Parent(), root.get());
69 EXPECT_EQ(root->FirstChild(), last_child.get());
70 EXPECT_EQ(root->LastChild(), last_child.get());
71
72 // Then prepend
73 root->InsertBefore(first_child.get(), last_child.get());
74 EXPECT_EQ(first_child->Parent(), root.get());
75 EXPECT_EQ(root->FirstChild(), first_child.get());
76 EXPECT_EQ(root->LastChild(), last_child.get());
77 EXPECT_EQ(first_child->Next(), last_child.get());
78 EXPECT_EQ(first_child.get(), last_child->Previous());
79
80 // Inserting in the middle
81 root->InsertBefore(middle_child.get(), last_child.get());
82 EXPECT_EQ(middle_child->Parent(), root.get());
83 EXPECT_EQ(root->FirstChild(), first_child.get());
84 EXPECT_EQ(root->LastChild(), last_child.get());
85 EXPECT_EQ(middle_child->Previous(), first_child.get());
86 EXPECT_EQ(middle_child->Next(), last_child.get());
87 EXPECT_EQ(first_child->Next(), middle_child.get());
88 EXPECT_EQ(last_child->Previous(), middle_child.get());
89 }
90
TEST(TreeNodeTest,RemoveSingle)91 TEST(TreeNodeTest, RemoveSingle) {
92 scoped_refptr<TestTree> root = TestTree::Create();
93 scoped_refptr<TestTree> child = TestTree::Create();
94 scoped_refptr<TestTree> null_node;
95
96 root->AppendChild(child.get());
97 root->RemoveChild(child.get());
98 EXPECT_EQ(child->Next(), null_node.get());
99 EXPECT_EQ(child->Previous(), null_node.get());
100 EXPECT_EQ(child->Parent(), null_node.get());
101 EXPECT_EQ(root->FirstChild(), null_node.get());
102 EXPECT_EQ(root->LastChild(), null_node.get());
103 }
104
105 class Trio {
106 STACK_ALLOCATED();
107
108 public:
Trio()109 Trio()
110 : root(TestTree::Create()),
111 first_child(TestTree::Create()),
112 middle_child(TestTree::Create()),
113 last_child(TestTree::Create()) {}
114
AppendChildren()115 void AppendChildren() {
116 root->AppendChild(first_child.get());
117 root->AppendChild(middle_child.get());
118 root->AppendChild(last_child.get());
119 }
120
121 scoped_refptr<TestTree> root;
122 scoped_refptr<TestTree> first_child;
123 scoped_refptr<TestTree> middle_child;
124 scoped_refptr<TestTree> last_child;
125 };
126
TEST(TreeNodeTest,RemoveMiddle)127 TEST(TreeNodeTest, RemoveMiddle) {
128 Trio trio;
129 trio.AppendChildren();
130
131 trio.root->RemoveChild(trio.middle_child.get());
132 EXPECT_TRUE(trio.middle_child->Orphan());
133 EXPECT_EQ(trio.first_child->Next(), trio.last_child.get());
134 EXPECT_EQ(trio.last_child->Previous(), trio.first_child.get());
135 EXPECT_EQ(trio.root->FirstChild(), trio.first_child.get());
136 EXPECT_EQ(trio.root->LastChild(), trio.last_child.get());
137 }
138
TEST(TreeNodeTest,RemoveLast)139 TEST(TreeNodeTest, RemoveLast) {
140 scoped_refptr<TestTree> null_node;
141 Trio trio;
142 trio.AppendChildren();
143
144 trio.root->RemoveChild(trio.last_child.get());
145 EXPECT_TRUE(trio.last_child->Orphan());
146 EXPECT_EQ(trio.middle_child->Next(), null_node.get());
147 EXPECT_EQ(trio.root->FirstChild(), trio.first_child.get());
148 EXPECT_EQ(trio.root->LastChild(), trio.middle_child.get());
149 }
150
TEST(TreeNodeTest,RemoveFirst)151 TEST(TreeNodeTest, RemoveFirst) {
152 scoped_refptr<TestTree> null_node;
153 Trio trio;
154 trio.AppendChildren();
155
156 trio.root->RemoveChild(trio.first_child.get());
157 EXPECT_TRUE(trio.first_child->Orphan());
158 EXPECT_EQ(trio.middle_child->Previous(), null_node.get());
159 EXPECT_EQ(trio.root->FirstChild(), trio.middle_child.get());
160 EXPECT_EQ(trio.root->LastChild(), trio.last_child.get());
161 }
162
TEST(TreeNodeTest,TakeChildrenFrom)163 TEST(TreeNodeTest, TakeChildrenFrom) {
164 scoped_refptr<TestTree> new_parent = TestTree::Create();
165 Trio trio;
166 trio.AppendChildren();
167
168 new_parent->TakeChildrenFrom(trio.root.get());
169
170 EXPECT_FALSE(trio.root->HasChildren());
171 EXPECT_TRUE(new_parent->HasChildren());
172 EXPECT_EQ(trio.first_child.get(), new_parent->FirstChild());
173 EXPECT_EQ(trio.middle_child.get(), new_parent->FirstChild()->Next());
174 EXPECT_EQ(trio.last_child.get(), new_parent->LastChild());
175 }
176
177 class TrioWithGrandChild : public Trio {
178 public:
TrioWithGrandChild()179 TrioWithGrandChild() : grand_child(TestTree::Create()) {}
180
AppendChildren()181 void AppendChildren() {
182 Trio::AppendChildren();
183 middle_child->AppendChild(grand_child.get());
184 }
185
186 scoped_refptr<TestTree> grand_child;
187 };
188
TEST(TreeNodeTest,TraverseNext)189 TEST(TreeNodeTest, TraverseNext) {
190 TrioWithGrandChild trio;
191 trio.AppendChildren();
192
193 TestTree* order[] = {trio.root.get(), trio.first_child.get(),
194 trio.middle_child.get(), trio.grand_child.get(),
195 trio.last_child.get()};
196
197 unsigned order_index = 0;
198 for (TestTree *node = trio.root.get(); node;
199 node = TraverseNext(node), order_index++)
200 EXPECT_EQ(node, order[order_index]);
201 EXPECT_EQ(order_index, sizeof(order) / sizeof(TestTree*));
202 }
203
TEST(TreeNodeTest,TraverseNextPostORder)204 TEST(TreeNodeTest, TraverseNextPostORder) {
205 TrioWithGrandChild trio;
206 trio.AppendChildren();
207
208 TestTree* order[] = {trio.first_child.get(), trio.grand_child.get(),
209 trio.middle_child.get(), trio.last_child.get(),
210 trio.root.get()};
211
212 unsigned order_index = 0;
213 for (TestTree *node = TraverseFirstPostOrder(trio.root.get()); node;
214 node = TraverseNextPostOrder(node), order_index++)
215 EXPECT_EQ(node, order[order_index]);
216 EXPECT_EQ(order_index, sizeof(order) / sizeof(TestTree*));
217 }
218
219 } // namespace WTF
220