1/*
2 * Copyright (C) 2010, 2011 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 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of Apple Inc. ("Apple") nor the names of
14 * its contributors may be used to endorse or promote products derived
15 * from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#pragma once
30
31#include <wtf/Assertions.h>
32#include <wtf/Noncopyable.h>
33
34namespace WTF {
35
36// This implements a red-black tree with the following properties:
37// - The allocation of nodes in the tree is entirely up to the user.
38// - If you are in possession of a pointer to a node, you can delete
39// it from the tree. The tree will subsequently no longer have a
40// reference to this node.
41// - The key type must implement operator< and ==.
42
43template<class NodeType, typename KeyType>
44class RedBlackTree {
45 WTF_MAKE_NONCOPYABLE(RedBlackTree);
46private:
47 enum Color {
48 Red = 1,
49 Black
50 };
51
52public:
53 class Node {
54 friend class RedBlackTree;
55
56 public:
57 const NodeType* successor() const
58 {
59 const Node* x = this;
60 if (x->right())
61 return treeMinimum(x->right());
62 const NodeType* y = x->parent();
63 while (y && x == y->right()) {
64 x = y;
65 y = y->parent();
66 }
67 return y;
68 }
69
70 const NodeType* predecessor() const
71 {
72 const Node* x = this;
73 if (x->left())
74 return treeMaximum(x->left());
75 const NodeType* y = x->parent();
76 while (y && x == y->left()) {
77 x = y;
78 y = y->parent();
79 }
80 return y;
81 }
82
83 NodeType* successor()
84 {
85 return const_cast<NodeType*>(const_cast<const Node*>(this)->successor());
86 }
87
88 NodeType* predecessor()
89 {
90 return const_cast<NodeType*>(const_cast<const Node*>(this)->predecessor());
91 }
92
93 private:
94 void reset()
95 {
96 m_left = 0;
97 m_right = 0;
98 m_parentAndRed = 1; // initialize to red
99 }
100
101 // NOTE: these methods should pack the parent and red into a single
102 // word. But doing so appears to reveal a bug in the compiler.
103 NodeType* parent() const
104 {
105 return reinterpret_cast<NodeType*>(m_parentAndRed & ~static_cast<uintptr_t>(1));
106 }
107
108 void setParent(NodeType* newParent)
109 {
110 m_parentAndRed = reinterpret_cast<uintptr_t>(newParent) | (m_parentAndRed & 1);
111 }
112
113 NodeType* left() const
114 {
115 return m_left;
116 }
117
118 void setLeft(NodeType* node)
119 {
120 m_left = node;
121 }
122
123 NodeType* right() const
124 {
125 return m_right;
126 }
127
128 void setRight(NodeType* node)
129 {
130 m_right = node;
131 }
132
133 Color color() const
134 {
135 if (m_parentAndRed & 1)
136 return Red;
137 return Black;
138 }
139
140 void setColor(Color value)
141 {
142 if (value == Red)
143 m_parentAndRed |= 1;
144 else
145 m_parentAndRed &= ~static_cast<uintptr_t>(1);
146 }
147
148 NodeType* m_left;
149 NodeType* m_right;
150 uintptr_t m_parentAndRed;
151 };
152
153 RedBlackTree()
154 : m_root(0)
155 {
156 }
157
158 void insert(NodeType* x)
159 {
160 x->reset();
161 treeInsert(x);
162 x->setColor(Red);
163
164 while (x != m_root && x->parent()->color() == Red) {
165 if (x->parent() == x->parent()->parent()->left()) {
166 NodeType* y = x->parent()->parent()->right();
167 if (y && y->color() == Red) {
168 // Case 1
169 x->parent()->setColor(Black);
170 y->setColor(Black);
171 x->parent()->parent()->setColor(Red);
172 x = x->parent()->parent();
173 } else {
174 if (x == x->parent()->right()) {
175 // Case 2
176 x = x->parent();
177 leftRotate(x);
178 }
179 // Case 3
180 x->parent()->setColor(Black);
181 x->parent()->parent()->setColor(Red);
182 rightRotate(x->parent()->parent());
183 }
184 } else {
185 // Same as "then" clause with "right" and "left" exchanged.
186 NodeType* y = x->parent()->parent()->left();
187 if (y && y->color() == Red) {
188 // Case 1
189 x->parent()->setColor(Black);
190 y->setColor(Black);
191 x->parent()->parent()->setColor(Red);
192 x = x->parent()->parent();
193 } else {
194 if (x == x->parent()->left()) {
195 // Case 2
196 x = x->parent();
197 rightRotate(x);
198 }
199 // Case 3
200 x->parent()->setColor(Black);
201 x->parent()->parent()->setColor(Red);
202 leftRotate(x->parent()->parent());
203 }
204 }
205 }
206
207 m_root->setColor(Black);
208 }
209
210 NodeType* remove(NodeType* z)
211 {
212 ASSERT(z);
213 ASSERT(z->parent() || z == m_root);
214
215 // Y is the node to be unlinked from the tree.
216 NodeType* y;
217 if (!z->left() || !z->right())
218 y = z;
219 else
220 y = z->successor();
221
222 // Y is guaranteed to be non-null at this point.
223 NodeType* x;
224 if (y->left())
225 x = y->left();
226 else
227 x = y->right();
228
229 // X is the child of y which might potentially replace y in
230 // the tree. X might be null at this point.
231 NodeType* xParent;
232 if (x) {
233 x->setParent(y->parent());
234 xParent = x->parent();
235 } else
236 xParent = y->parent();
237 if (!y->parent())
238 m_root = x;
239 else {
240 if (y == y->parent()->left())
241 y->parent()->setLeft(x);
242 else
243 y->parent()->setRight(x);
244 }
245
246 if (y != z) {
247 if (y->color() == Black)
248 removeFixup(x, xParent);
249
250 y->setParent(z->parent());
251 y->setColor(z->color());
252 y->setLeft(z->left());
253 y->setRight(z->right());
254
255 if (z->left())
256 z->left()->setParent(y);
257 if (z->right())
258 z->right()->setParent(y);
259 if (z->parent()) {
260 if (z->parent()->left() == z)
261 z->parent()->setLeft(y);
262 else
263 z->parent()->setRight(y);
264 } else {
265 ASSERT(m_root == z);
266 m_root = y;
267 }
268 } else if (y->color() == Black)
269 removeFixup(x, xParent);
270
271 return z;
272 }
273
274 NodeType* remove(const KeyType& key)
275 {
276 NodeType* result = findExact(key);
277 if (!result)
278 return 0;
279 return remove(result);
280 }
281
282 NodeType* findExact(const KeyType& key) const
283 {
284 for (NodeType* current = m_root; current;) {
285 if (current->key() == key)
286 return current;
287 if (key < current->key())
288 current = current->left();
289 else
290 current = current->right();
291 }
292 return 0;
293 }
294
295 NodeType* findLeastGreaterThanOrEqual(const KeyType& key) const
296 {
297 NodeType* best = 0;
298 for (NodeType* current = m_root; current;) {
299 if (current->key() == key)
300 return current;
301 if (current->key() < key)
302 current = current->right();
303 else {
304 best = current;
305 current = current->left();
306 }
307 }
308 return best;
309 }
310
311 NodeType* findGreatestLessThanOrEqual(const KeyType& key) const
312 {
313 NodeType* best = 0;
314 for (NodeType* current = m_root; current;) {
315 if (current->key() == key)
316 return current;
317 if (current->key() > key)
318 current = current->left();
319 else {
320 best = current;
321 current = current->right();
322 }
323 }
324 return best;
325 }
326
327 NodeType* first() const
328 {
329 if (!m_root)
330 return 0;
331 return treeMinimum(m_root);
332 }
333
334 NodeType* last() const
335 {
336 if (!m_root)
337 return 0;
338 return treeMaximum(m_root);
339 }
340
341 // This is an O(n) operation.
342 size_t size()
343 {
344 size_t result = 0;
345 for (NodeType* current = first(); current; current = current->successor())
346 result++;
347 return result;
348 }
349
350 // This is an O(1) operation.
351 bool isEmpty()
352 {
353 return !m_root;
354 }
355
356private:
357 // Finds the minimum element in the sub-tree rooted at the given
358 // node.
359 static NodeType* treeMinimum(NodeType* x)
360 {
361 while (x->left())
362 x = x->left();
363 return x;
364 }
365
366 static NodeType* treeMaximum(NodeType* x)
367 {
368 while (x->right())
369 x = x->right();
370 return x;
371 }
372
373 static const NodeType* treeMinimum(const NodeType* x)
374 {
375 while (x->left())
376 x = x->left();
377 return x;
378 }
379
380 static const NodeType* treeMaximum(const NodeType* x)
381 {
382 while (x->right())
383 x = x->right();
384 return x;
385 }
386
387 void treeInsert(NodeType* z)
388 {
389 ASSERT(!z->left());
390 ASSERT(!z->right());
391 ASSERT(!z->parent());
392 ASSERT(z->color() == Red);
393
394 NodeType* y = 0;
395 NodeType* x = m_root;
396 while (x) {
397 y = x;
398 if (z->key() < x->key())
399 x = x->left();
400 else
401 x = x->right();
402 }
403 z->setParent(y);
404 if (!y)
405 m_root = z;
406 else {
407 if (z->key() < y->key())
408 y->setLeft(z);
409 else
410 y->setRight(z);
411 }
412 }
413
414 //----------------------------------------------------------------------
415 // Red-Black tree operations
416 //
417
418 // Left-rotates the subtree rooted at x.
419 // Returns the new root of the subtree (x's right child).
420 NodeType* leftRotate(NodeType* x)
421 {
422 // Set y.
423 NodeType* y = x->right();
424
425 // Turn y's left subtree into x's right subtree.
426 x->setRight(y->left());
427 if (y->left())
428 y->left()->setParent(x);
429
430 // Link x's parent to y.
431 y->setParent(x->parent());
432 if (!x->parent())
433 m_root = y;
434 else {
435 if (x == x->parent()->left())
436 x->parent()->setLeft(y);
437 else
438 x->parent()->setRight(y);
439 }
440
441 // Put x on y's left.
442 y->setLeft(x);
443 x->setParent(y);
444
445 return y;
446 }
447
448 // Right-rotates the subtree rooted at y.
449 // Returns the new root of the subtree (y's left child).
450 NodeType* rightRotate(NodeType* y)
451 {
452 // Set x.
453 NodeType* x = y->left();
454
455 // Turn x's right subtree into y's left subtree.
456 y->setLeft(x->right());
457 if (x->right())
458 x->right()->setParent(y);
459
460 // Link y's parent to x.
461 x->setParent(y->parent());
462 if (!y->parent())
463 m_root = x;
464 else {
465 if (y == y->parent()->left())
466 y->parent()->setLeft(x);
467 else
468 y->parent()->setRight(x);
469 }
470
471 // Put y on x's right.
472 x->setRight(y);
473 y->setParent(x);
474
475 return x;
476 }
477
478 // Restores the red-black property to the tree after splicing out
479 // a node. Note that x may be null, which is why xParent must be
480 // supplied.
481 void removeFixup(NodeType* x, NodeType* xParent)
482 {
483 while (x != m_root && (!x || x->color() == Black)) {
484 if (x == xParent->left()) {
485 // Note: the text points out that w can not be null.
486 // The reason is not obvious from simply looking at
487 // the code; it comes about from the properties of the
488 // red-black tree.
489 NodeType* w = xParent->right();
490 ASSERT(w); // x's sibling should not be null.
491 if (w->color() == Red) {
492 // Case 1
493 w->setColor(Black);
494 xParent->setColor(Red);
495 leftRotate(xParent);
496 w = xParent->right();
497 }
498 if ((!w->left() || w->left()->color() == Black)
499 && (!w->right() || w->right()->color() == Black)) {
500 // Case 2
501 w->setColor(Red);
502 x = xParent;
503 xParent = x->parent();
504 } else {
505 if (!w->right() || w->right()->color() == Black) {
506 // Case 3
507 w->left()->setColor(Black);
508 w->setColor(Red);
509 rightRotate(w);
510 w = xParent->right();
511 }
512 // Case 4
513 w->setColor(xParent->color());
514 xParent->setColor(Black);
515 if (w->right())
516 w->right()->setColor(Black);
517 leftRotate(xParent);
518 x = m_root;
519 xParent = x->parent();
520 }
521 } else {
522 // Same as "then" clause with "right" and "left"
523 // exchanged.
524
525 // Note: the text points out that w can not be null.
526 // The reason is not obvious from simply looking at
527 // the code; it comes about from the properties of the
528 // red-black tree.
529 NodeType* w = xParent->left();
530 ASSERT(w); // x's sibling should not be null.
531 if (w->color() == Red) {
532 // Case 1
533 w->setColor(Black);
534 xParent->setColor(Red);
535 rightRotate(xParent);
536 w = xParent->left();
537 }
538 if ((!w->right() || w->right()->color() == Black)
539 && (!w->left() || w->left()->color() == Black)) {
540 // Case 2
541 w->setColor(Red);
542 x = xParent;
543 xParent = x->parent();
544 } else {
545 if (!w->left() || w->left()->color() == Black) {
546 // Case 3
547 w->right()->setColor(Black);
548 w->setColor(Red);
549 leftRotate(w);
550 w = xParent->left();
551 }
552 // Case 4
553 w->setColor(xParent->color());
554 xParent->setColor(Black);
555 if (w->left())
556 w->left()->setColor(Black);
557 rightRotate(xParent);
558 x = m_root;
559 xParent = x->parent();
560 }
561 }
562 }
563 if (x)
564 x->setColor(Black);
565 }
566
567 NodeType* m_root;
568};
569
570}
571