Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef ds_SplayTree_h
8 : #define ds_SplayTree_h
9 :
10 : #include "ds/LifoAlloc.h"
11 :
12 : namespace js {
13 :
14 : /*
15 : * Class which represents a splay tree with nodes allocated from a LifoAlloc.
16 : * Splay trees are balanced binary search trees for which search, insert and
17 : * remove are all amortized O(log n).
18 : *
19 : * T indicates the type of tree elements, C must have a static
20 : * compare(const T&, const T&) method ordering the elements. As for LifoAlloc
21 : * objects, T objects stored in the tree will not be explicitly destroyed.
22 : */
23 : template <class T, class C>
24 : class SplayTree
25 : {
26 : struct Node {
27 : T item;
28 : Node* left;
29 : Node* right;
30 : Node* parent;
31 :
32 4476 : explicit Node(const T& item)
33 4476 : : item(item), left(nullptr), right(nullptr), parent(nullptr)
34 4476 : {}
35 : };
36 :
37 : LifoAlloc* alloc;
38 : Node* root;
39 : Node* freeList;
40 :
41 : #ifdef DEBUG
42 : bool enableCheckCoherency;
43 : #endif
44 :
45 : SplayTree(const SplayTree&) = delete;
46 : SplayTree& operator=(const SplayTree&) = delete;
47 :
48 : public:
49 :
50 615 : explicit SplayTree(LifoAlloc* alloc = nullptr)
51 : : alloc(alloc), root(nullptr), freeList(nullptr)
52 : #ifdef DEBUG
53 615 : , enableCheckCoherency(true)
54 : #endif
55 615 : {}
56 :
57 528 : void setAllocator(LifoAlloc* alloc) {
58 528 : this->alloc = alloc;
59 528 : }
60 :
61 : void disableCheckCoherency() {
62 : #ifdef DEBUG
63 : enableCheckCoherency = false;
64 : #endif
65 : }
66 :
67 0 : bool empty() const {
68 0 : return !root;
69 : }
70 :
71 0 : T* maybeLookup(const T& v)
72 : {
73 0 : if (!root)
74 0 : return nullptr;
75 0 : Node* last = lookup(v);
76 0 : return (C::compare(v, last->item) == 0) ? &(last->item) : nullptr;
77 : }
78 :
79 24978 : bool contains(const T& v, T* res)
80 : {
81 24978 : if (!root)
82 79 : return false;
83 24899 : Node* last = lookup(v);
84 24899 : splay(last);
85 24899 : checkCoherency(root, nullptr);
86 24899 : if (C::compare(v, last->item) == 0) {
87 12232 : *res = last->item;
88 12232 : return true;
89 : }
90 12667 : return false;
91 : }
92 :
93 4476 : MOZ_MUST_USE bool insert(const T& v)
94 : {
95 4476 : Node* element = allocateNode(v);
96 4476 : if (!element)
97 0 : return false;
98 :
99 4476 : if (!root) {
100 459 : root = element;
101 459 : return true;
102 : }
103 4017 : Node* last = lookup(v);
104 4017 : int cmp = C::compare(v, last->item);
105 :
106 : // Don't tolerate duplicate elements.
107 4017 : MOZ_ASSERT(cmp);
108 :
109 4017 : Node*& parentPointer = (cmp < 0) ? last->left : last->right;
110 4017 : MOZ_ASSERT(!parentPointer);
111 4017 : parentPointer = element;
112 4017 : element->parent = last;
113 :
114 4017 : splay(element);
115 4017 : checkCoherency(root, nullptr);
116 4017 : return true;
117 : }
118 :
119 171 : void remove(const T& v)
120 : {
121 171 : Node* last = lookup(v);
122 171 : MOZ_ASSERT(last && C::compare(v, last->item) == 0);
123 :
124 171 : splay(last);
125 171 : MOZ_ASSERT(last == root);
126 :
127 : // Find another node which can be swapped in for the root: either the
128 : // rightmost child of the root's left, or the leftmost child of the
129 : // root's right.
130 : Node* swap;
131 : Node* swapChild;
132 171 : if (root->left) {
133 88 : swap = root->left;
134 186 : while (swap->right)
135 49 : swap = swap->right;
136 88 : swapChild = swap->left;
137 83 : } else if (root->right) {
138 80 : swap = root->right;
139 162 : while (swap->left)
140 41 : swap = swap->left;
141 80 : swapChild = swap->right;
142 : } else {
143 3 : freeNode(root);
144 3 : root = nullptr;
145 3 : return;
146 : }
147 :
148 : // The selected node has at most one child, in swapChild. Detach it
149 : // from the subtree by replacing it with that child.
150 168 : if (swap == swap->parent->left)
151 97 : swap->parent->left = swapChild;
152 : else
153 71 : swap->parent->right = swapChild;
154 168 : if (swapChild)
155 121 : swapChild->parent = swap->parent;
156 :
157 168 : root->item = swap->item;
158 168 : freeNode(swap);
159 :
160 168 : checkCoherency(root, nullptr);
161 : }
162 :
163 : template <class Op>
164 0 : void forEach(Op op)
165 : {
166 0 : forEachInner<Op>(op, root);
167 0 : }
168 :
169 : private:
170 :
171 29087 : Node* lookup(const T& v)
172 : {
173 29087 : MOZ_ASSERT(root);
174 29087 : Node* node = root;
175 : Node* parent;
176 55229 : do {
177 67632 : parent = node;
178 67632 : int c = C::compare(v, node->item);
179 67632 : if (c == 0)
180 12403 : return node;
181 55229 : else if (c < 0)
182 30449 : node = node->left;
183 : else
184 24780 : node = node->right;
185 : } while (node);
186 16684 : return parent;
187 : }
188 :
189 4476 : Node* allocateNode(const T& v)
190 : {
191 4476 : Node* node = freeList;
192 4476 : if (node) {
193 159 : freeList = node->left;
194 159 : new(node) Node(v);
195 159 : return node;
196 : }
197 4317 : return alloc->new_<Node>(v);
198 : }
199 :
200 171 : void freeNode(Node* node)
201 : {
202 171 : node->left = freeList;
203 171 : freeList = node;
204 171 : }
205 :
206 29087 : void splay(Node* node)
207 : {
208 : // Rotate the element until it is at the root of the tree. Performing
209 : // the rotations in this fashion preserves the amortized balancing of
210 : // the tree.
211 29087 : MOZ_ASSERT(node);
212 55587 : while (node != root) {
213 29312 : Node* parent = node->parent;
214 29312 : if (parent == root) {
215 : // Zig rotation.
216 16062 : rotate(node);
217 16062 : MOZ_ASSERT(node == root);
218 16062 : return;
219 : }
220 13250 : Node* grandparent = parent->parent;
221 13250 : if ((parent->left == node) == (grandparent->left == parent)) {
222 : // Zig-zig rotation.
223 8279 : rotate(parent);
224 8279 : rotate(node);
225 : } else {
226 : // Zig-zag rotation.
227 4971 : rotate(node);
228 4971 : rotate(node);
229 : }
230 : }
231 : }
232 :
233 42562 : void rotate(Node* node)
234 : {
235 : // Rearrange nodes so that node becomes the parent of its current
236 : // parent, while preserving the sortedness of the tree.
237 42562 : Node* parent = node->parent;
238 42562 : if (parent->left == node) {
239 : // x y
240 : // y c ==> a x
241 : // a b b c
242 23664 : parent->left = node->right;
243 23664 : if (node->right)
244 9516 : node->right->parent = parent;
245 23664 : node->right = parent;
246 : } else {
247 18898 : MOZ_ASSERT(parent->right == node);
248 : // x y
249 : // a y ==> x c
250 : // b c a b
251 18898 : parent->right = node->left;
252 18898 : if (node->left)
253 6047 : node->left->parent = parent;
254 18898 : node->left = parent;
255 : }
256 42562 : node->parent = parent->parent;
257 42562 : parent->parent = node;
258 42562 : if (Node* grandparent = node->parent) {
259 18077 : if (grandparent->left == parent)
260 9734 : grandparent->left = node;
261 : else
262 8343 : grandparent->right = node;
263 : } else {
264 24485 : root = node;
265 : }
266 42562 : }
267 :
268 : template <class Op>
269 0 : void forEachInner(Op op, Node* node)
270 : {
271 0 : if (!node)
272 0 : return;
273 :
274 0 : forEachInner<Op>(op, node->left);
275 0 : op(node->item);
276 0 : forEachInner<Op>(op, node->right);
277 : }
278 :
279 618681 : Node* checkCoherency(Node* node, Node* minimum)
280 : {
281 : #ifdef DEBUG
282 618681 : if (!enableCheckCoherency)
283 0 : return nullptr;
284 618681 : if (!node) {
285 0 : MOZ_ASSERT(!root);
286 0 : return nullptr;
287 : }
288 618681 : MOZ_ASSERT_IF(!node->parent, node == root);
289 618681 : MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0);
290 618681 : if (node->left) {
291 282330 : MOZ_ASSERT(node->left->parent == node);
292 282330 : Node* leftMaximum = checkCoherency(node->left, minimum);
293 282330 : MOZ_ASSERT(C::compare(leftMaximum->item, node->item) < 0);
294 : }
295 618681 : if (node->right) {
296 307267 : MOZ_ASSERT(node->right->parent == node);
297 307267 : return checkCoherency(node->right, node);
298 : }
299 311414 : return node;
300 : #else
301 : return nullptr;
302 : #endif
303 : }
304 : };
305 :
306 : } /* namespace js */
307 :
308 : #endif /* ds_SplayTree_h */
|
