Source code

Revision control

Other Tools

1
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2
* vim: set ts=8 sts=2 et sw=2 tw=80:
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
struct Node {
26
T item;
27
Node* left;
28
Node* right;
29
Node* parent;
30
31
explicit Node(const T& item)
32
: item(item), left(nullptr), right(nullptr), parent(nullptr) {}
33
};
34
35
LifoAlloc* alloc;
36
Node* root;
37
Node* freeList;
38
39
#ifdef DEBUG
40
bool enableCheckCoherency;
41
#endif
42
43
SplayTree(const SplayTree&) = delete;
44
SplayTree& operator=(const SplayTree&) = delete;
45
46
public:
47
explicit SplayTree(LifoAlloc* alloc = nullptr)
48
: alloc(alloc),
49
root(nullptr),
50
freeList(nullptr)
51
#ifdef DEBUG
52
,
53
enableCheckCoherency(true)
54
#endif
55
{
56
}
57
58
void setAllocator(LifoAlloc* alloc) { this->alloc = alloc; }
59
60
void disableCheckCoherency() {
61
#ifdef DEBUG
62
enableCheckCoherency = false;
63
#endif
64
}
65
66
bool empty() const { return !root; }
67
68
T* maybeLookup(const T& v) {
69
if (!root) {
70
return nullptr;
71
}
72
Node* last = lookup(v);
73
return (C::compare(v, last->item) == 0) ? &(last->item) : nullptr;
74
}
75
76
bool contains(const T& v, T* res) {
77
if (!root) {
78
return false;
79
}
80
Node* last = lookup(v);
81
splay(last);
82
checkCoherency();
83
if (C::compare(v, last->item) == 0) {
84
*res = last->item;
85
return true;
86
}
87
return false;
88
}
89
90
MOZ_MUST_USE bool insert(const T& v) {
91
Node* element = allocateNode(v);
92
if (!element) {
93
return false;
94
}
95
96
if (!root) {
97
root = element;
98
return true;
99
}
100
Node* last = lookup(v);
101
int cmp = C::compare(v, last->item);
102
103
// Don't tolerate duplicate elements.
104
MOZ_DIAGNOSTIC_ASSERT(cmp);
105
106
Node*& parentPointer = (cmp < 0) ? last->left : last->right;
107
MOZ_ASSERT(!parentPointer);
108
parentPointer = element;
109
element->parent = last;
110
111
splay(element);
112
checkCoherency();
113
return true;
114
}
115
116
void remove(const T& v) {
117
Node* last = lookup(v);
118
MOZ_ASSERT(last && C::compare(v, last->item) == 0);
119
120
splay(last);
121
MOZ_ASSERT(last == root);
122
123
// Find another node which can be swapped in for the root: either the
124
// rightmost child of the root's left, or the leftmost child of the
125
// root's right.
126
Node* swap;
127
Node* swapChild;
128
if (root->left) {
129
swap = root->left;
130
while (swap->right) {
131
swap = swap->right;
132
}
133
swapChild = swap->left;
134
} else if (root->right) {
135
swap = root->right;
136
while (swap->left) {
137
swap = swap->left;
138
}
139
swapChild = swap->right;
140
} else {
141
freeNode(root);
142
root = nullptr;
143
return;
144
}
145
146
// The selected node has at most one child, in swapChild. Detach it
147
// from the subtree by replacing it with that child.
148
if (swap == swap->parent->left) {
149
swap->parent->left = swapChild;
150
} else {
151
swap->parent->right = swapChild;
152
}
153
if (swapChild) {
154
swapChild->parent = swap->parent;
155
}
156
157
root->item = swap->item;
158
freeNode(swap);
159
160
checkCoherency();
161
}
162
163
template <class Op>
164
void forEach(Op op) {
165
forEachInner<Op>(op, root);
166
}
167
168
private:
169
Node* lookup(const T& v) {
170
MOZ_ASSERT(root);
171
Node* node = root;
172
Node* parent;
173
do {
174
parent = node;
175
int c = C::compare(v, node->item);
176
if (c == 0) {
177
return node;
178
} else if (c < 0) {
179
node = node->left;
180
} else {
181
node = node->right;
182
}
183
} while (node);
184
return parent;
185
}
186
187
Node* allocateNode(const T& v) {
188
Node* node = freeList;
189
if (node) {
190
freeList = node->left;
191
new (node) Node(v);
192
return node;
193
}
194
return alloc->new_<Node>(v);
195
}
196
197
void freeNode(Node* node) {
198
node->left = freeList;
199
freeList = node;
200
}
201
202
void splay(Node* node) {
203
// Rotate the element until it is at the root of the tree. Performing
204
// the rotations in this fashion preserves the amortized balancing of
205
// the tree.
206
MOZ_ASSERT(node);
207
while (node != root) {
208
Node* parent = node->parent;
209
if (parent == root) {
210
// Zig rotation.
211
rotate(node);
212
MOZ_ASSERT(node == root);
213
return;
214
}
215
Node* grandparent = parent->parent;
216
if ((parent->left == node) == (grandparent->left == parent)) {
217
// Zig-zig rotation.
218
rotate(parent);
219
rotate(node);
220
} else {
221
// Zig-zag rotation.
222
rotate(node);
223
rotate(node);
224
}
225
}
226
}
227
228
void rotate(Node* node) {
229
// Rearrange nodes so that node becomes the parent of its current
230
// parent, while preserving the sortedness of the tree.
231
Node* parent = node->parent;
232
if (parent->left == node) {
233
// x y
234
// y c ==> a x
235
// a b b c
236
parent->left = node->right;
237
if (node->right) {
238
node->right->parent = parent;
239
}
240
node->right = parent;
241
} else {
242
MOZ_ASSERT(parent->right == node);
243
// x y
244
// a y ==> x c
245
// b c a b
246
parent->right = node->left;
247
if (node->left) {
248
node->left->parent = parent;
249
}
250
node->left = parent;
251
}
252
node->parent = parent->parent;
253
parent->parent = node;
254
if (Node* grandparent = node->parent) {
255
if (grandparent->left == parent) {
256
grandparent->left = node;
257
} else {
258
grandparent->right = node;
259
}
260
} else {
261
root = node;
262
}
263
}
264
265
template <class Op>
266
void forEachInner(Op op, Node* node) {
267
if (!node) {
268
return;
269
}
270
271
forEachInner<Op>(op, node->left);
272
op(node->item);
273
forEachInner<Op>(op, node->right);
274
}
275
276
void checkCoherency() const {
277
#ifdef DEBUG
278
if (!enableCheckCoherency) {
279
return;
280
}
281
if (!root) {
282
return;
283
}
284
MOZ_ASSERT(root->parent == nullptr);
285
const Node* node = root;
286
const Node* minimum = nullptr;
287
MOZ_ASSERT_IF(node->left, node->left->parent == node);
288
MOZ_ASSERT_IF(node->right, node->right->parent == node);
289
290
// This is doing a depth-first search and check that the values are
291
// ordered properly.
292
while (true) {
293
// Go to the left-most child.
294
while (node->left) {
295
MOZ_ASSERT_IF(node->left, node->left->parent == node);
296
MOZ_ASSERT_IF(node->right, node->right->parent == node);
297
node = node->left;
298
}
299
300
MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0);
301
minimum = node;
302
303
if (node->right) {
304
// Go once to the right and try again.
305
MOZ_ASSERT_IF(node->left, node->left->parent == node);
306
MOZ_ASSERT_IF(node->right, node->right->parent == node);
307
node = node->right;
308
} else {
309
// We reached a leaf node, move to the first branch to the right of
310
// our current left-most sub-tree.
311
MOZ_ASSERT(!node->left && !node->right);
312
const Node* prev = nullptr;
313
314
// Visit the parent node, to find the right branch which we have
315
// not visited yet. Either we are coming back from the right
316
// branch, or we are coming back from the left branch with no
317
// right branch to visit.
318
while (node->parent) {
319
prev = node;
320
node = node->parent;
321
322
// If we came back from the left branch, visit the value.
323
if (node->left == prev) {
324
MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0);
325
minimum = node;
326
}
327
328
if (node->right != prev && node->right != nullptr) {
329
break;
330
}
331
}
332
333
if (!node->parent) {
334
MOZ_ASSERT(node == root);
335
// We reached the root node either because we came back from
336
// the right hand side, or because the root node had a
337
// single child.
338
if (node->right == prev || node->right == nullptr) {
339
return;
340
}
341
}
342
343
// Go to the right node which we have not visited yet.
344
MOZ_ASSERT(node->right != prev && node->right != nullptr);
345
node = node->right;
346
}
347
}
348
#endif
349
}
350
};
351
352
} /* namespace js */
353
354
#endif /* ds_SplayTree_h */