1    	/*
2    	 * rbtree - Implements a red-black tree with parent pointers.
3    	 *
4    	 * Copyright (C) 2010-2014 Franck Bui-Huu <fbuihuu@gmail.com>
5    	 *
6    	 * This file is part of libtree which is free software; you can
7    	 * redistribute it and/or modify it under the terms of the GNU Lesser
8    	 * General Public License as published by the Free Software
9    	 * Foundation; either version 2.1 of the License, or (at your option)
10   	 * any later version.
11   	 *
12   	 * This library is distributed in the hope that it will be useful, but
13   	 * WITHOUT ANY WARRANTY; without even the implied warranty of
14   	 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
15   	 *
16   	 * See the LICENSE file for license rights and limitations.
17   	 */
18   	
19   	/*
20   	 * For recall a red-black tree has the following properties:
21   	 *
22   	 *     1. All nodes are either BLACK or RED
23   	 *     2. Leafs are BLACK
24   	 *     3. A RED node has BLACK children only
25   	 *     4. Path from a node to any leafs has the same number of BLACK nodes.
26   	 *
27   	 */
28   	#include "avltree.h"
29   	
30   	/*
31   	 * Some helpers
32   	 */
33   	#ifdef UINTPTR_MAX
34   	
35   	static inline enum rb_color get_color(const struct rbtree_node *node)
36   	{
37   		return node->parent & 1;
38   	}
39   	
40   	static inline void set_color(enum rb_color color, struct rbtree_node *node)
41   	{
42   		node->parent = (node->parent & ~1UL) | color;
43   	}
44   	
45   	static inline struct rbtree_node *get_parent(const struct rbtree_node *node)
46   	{
47   		return (struct rbtree_node *)(node->parent & ~1UL);
48   	}
49   	
50   	static inline void set_parent(struct rbtree_node *parent,
51   				      struct rbtree_node *node)
52   	{
53   		node->parent = (uintptr_t) parent | (node->parent & 1);
54   	}
55   	
56   	#else
57   	
58   	static inline enum rb_color get_color(const struct rbtree_node *node)
59   	{
60   		return node->color;
61   	}
62   	
63   	static inline void set_color(enum rb_color color, struct rbtree_node *node)
64   	{
65   		node->color = color;
66   	}
67   	
68   	static inline struct rbtree_node *get_parent(const struct rbtree_node *node)
69   	{
70   		return node->parent;
71   	}
72   	
73   	static inline void set_parent(struct rbtree_node *parent,
74   				      struct rbtree_node *node)
75   	{
76   		node->parent = parent;
77   	}
78   	
79   	#endif				/* UINTPTR_MAX */
80   	
81   	static inline int is_root(struct rbtree_node *node)
82   	{
83   		return get_parent(node) == NULL;
84   	}
85   	
86   	static inline int is_black(struct rbtree_node *node)
87   	{
88   		return get_color(node) == RB_BLACK;
89   	}
90   	
91   	static inline int is_red(struct rbtree_node *node)
92   	{
93   		return !is_black(node);
94   	}
95   	
96   	/*
97   	 * Iterators
98   	 */
99   	static inline struct rbtree_node *get_first(struct rbtree_node *node)
100  	{
101  		while (node->left)
102  			node = node->left;
103  		return node;
104  	}
105  	
106  	static inline struct rbtree_node *get_last(struct rbtree_node *node)
107  	{
108  		while (node->right)
109  			node = node->right;
110  		return node;
111  	}
112  	
113  	struct rbtree_node *rbtree_first(const struct rbtree *tree)
114  	{
115  		return tree->first;
116  	}
117  	
118  	struct rbtree_node *rbtree_last(const struct rbtree *tree)
119  	{
120  		return tree->last;
121  	}
122  	
123  	struct rbtree_node *rbtree_next(const struct rbtree_node *node)
124  	{
125  		struct rbtree_node *parent;
126  	
127  		if (node->right)
128  			return get_first(node->right);
129  	
130  		while ((parent = get_parent(node)) && parent->right == node)
131  			node = parent;
132  		return parent;
133  	}
134  	
135  	struct rbtree_node *rbtree_prev(const struct rbtree_node *node)
136  	{
137  		struct rbtree_node *parent;
138  	
139  		if (node->left)
140  			return get_last(node->left);
141  	
142  		while ((parent = get_parent(node)) && parent->left == node)
143  			node = parent;
144  		return parent;
145  	}
146  	
147  	/*
148  	 * 'pparent' and 'is_left' are only used for insertions. Normally GCC
149  	 * will notice this and get rid of them for lookups.
150  	 */
151  	static inline struct rbtree_node *do_lookup(const struct rbtree_node *key,
152  						    const struct rbtree *tree,
153  						    struct rbtree_node **pparent,
154  						    int *is_left)
155  	{
156  		struct rbtree_node *node = tree->root;
157  	
158  		*pparent = NULL;
159  		*is_left = 0;
160  	
161  		while (node) {
162  			int res = tree->cmp_fn(node, key);
163  			if (res == 0)
164  				return node;
165  			*pparent = node;
166  			if ((*is_left = res > 0))
167  				node = node->left;
168  			else
169  				node = node->right;
170  		}
171  		return NULL;
172  	}
173  	
174  	/*
175  	 * Rotate operations (They preserve the binary search tree property,
176  	 * assuming that the keys are unique).
177  	 */
178  	static void rotate_left(struct rbtree_node *node, struct rbtree *tree)
179  	{
180  		struct rbtree_node *p = node;
181  		struct rbtree_node *q = node->right;	/* can't be NULL */
182  		struct rbtree_node *parent = get_parent(p);
183  	
184  		if (!is_root(p)) {
185  			if (parent->left == p)
186  				parent->left = q;
187  			else
188  				parent->right = q;
189  		} else
190  			tree->root = q;
191  		set_parent(parent, q);
192  		set_parent(q, p);
193  	
194  		p->right = q->left;
195  		if (p->right)
196  			set_parent(p, p->right);
197  		q->left = p;
198  	}
199  	
200  	static void rotate_right(struct rbtree_node *node, struct rbtree *tree)
201  	{
202  		struct rbtree_node *p = node;
203  		struct rbtree_node *q = node->left;	/* can't be NULL */
204  		struct rbtree_node *parent = get_parent(p);
205  	
206  		if (!is_root(p)) {
207  			if (parent->left == p)
208  				parent->left = q;
209  			else
210  				parent->right = q;
211  		} else
212  			tree->root = q;
213  		set_parent(parent, q);
214  		set_parent(q, p);
215  	
216  		p->left = q->right;
217  		if (p->left)
218  			set_parent(p, p->left);
219  		q->right = p;
220  	}
221  	
222  	struct rbtree_node *rbtree_lookup(const struct rbtree_node *key,
223  					  const struct rbtree *tree)
224  	{
225  		struct rbtree_node *parent;
226  		int is_left;
227  	
228  		return do_lookup(key, tree, &parent, &is_left);
229  	}
230  	
231  	static void set_child(struct rbtree_node *child, struct rbtree_node *node,
232  			      int left)
233  	{
234  		if (left)
235  			node->left = child;
236  		else
237  			node->right = child;
238  	}
239  	
240  	struct rbtree_node *rbtree_insert(struct rbtree_node *node, struct rbtree *tree)
241  	{
242  		struct rbtree_node *key, *parent;
243  		int is_left;
244  	
245  		key = do_lookup(node, tree, &parent, &is_left);
246  		if (key)
247  			return key;
248  	
249  		node->left = NULL;
250  		node->right = NULL;
251  		set_color(RB_RED, node);
252  		set_parent(parent, node);
253  	
254  		if (parent) {
255  			if (is_left) {
256  				if (parent == tree->first)
257  					tree->first = node;
258  			} else {
259  				if (parent == tree->last)
260  					tree->last = node;
261  			}
262  			set_child(node, parent, is_left);
263  		} else {
264  			tree->root = node;
265  			tree->first = node;
266  			tree->last = node;
267  		}
268  	
269  		/*
270  		 * Fixup the modified tree by recoloring nodes and performing
271  		 * rotations (2 at most) hence the red-black tree properties are
272  		 * preserved.
273  		 */
274  		while ((parent = get_parent(node)) && is_red(parent)) {
275  			struct rbtree_node *grandpa = get_parent(parent);
276  	
277  			if (parent == grandpa->left) {
278  				struct rbtree_node *uncle = grandpa->right;
279  	
280  				if (uncle && is_red(uncle)) {
281  					set_color(RB_BLACK, parent);
282  					set_color(RB_BLACK, uncle);
283  					set_color(RB_RED, grandpa);
284  					node = grandpa;
285  				} else {
286  					if (node == parent->right) {
287  						rotate_left(parent, tree);
288  						node = parent;
289  						parent = get_parent(node);
290  					}
291  					set_color(RB_BLACK, parent);
292  					set_color(RB_RED, grandpa);
293  					rotate_right(grandpa, tree);
294  				}
295  			} else {
296  				struct rbtree_node *uncle = grandpa->left;
297  	
298  				if (uncle && is_red(uncle)) {
299  					set_color(RB_BLACK, parent);
300  					set_color(RB_BLACK, uncle);
301  					set_color(RB_RED, grandpa);
302  					node = grandpa;
303  				} else {
304  					if (node == parent->left) {
305  						rotate_right(parent, tree);
306  						node = parent;
307  						parent = get_parent(node);
308  					}
309  					set_color(RB_BLACK, parent);
310  					set_color(RB_RED, grandpa);
311  					rotate_left(grandpa, tree);
312  				}
313  			}
314  		}
315  		set_color(RB_BLACK, tree->root);
316  		return NULL;
317  	}
318  	
319  	void rbtree_remove(struct rbtree_node *node, struct rbtree *tree)
320  	{
321  		struct rbtree_node *parent = get_parent(node);
322  		struct rbtree_node *left = node->left;
323  		struct rbtree_node *right = node->right;
324  		struct rbtree_node *next;
325  		enum rb_color color;
326  	
(1) Event cond_true: Condition "node == tree->first", taking true branch.
327  		if (node == tree->first)
328  			tree->first = rbtree_next(node);
(2) Event cond_true: Condition "node == tree->last", taking true branch.
329  		if (node == tree->last)
330  			tree->last = rbtree_prev(node);
331  	
(3) Event cond_true: Condition "!left", taking true branch.
332  		if (!left)
(4) Event if_fallthrough: Falling through to end of if statement.
333  			next = right;
334  		else if (!right)
335  			next = left;
336  		else
(5) Event if_end: End of if statement.
337  			next = get_first(right);
338  	
(6) Event cond_false: Condition "parent", taking false branch.
(8) Event var_compare_op: Comparing "parent" to null implies that "parent" might be null.
Also see events: [var_deref_op]
339  		if (parent)
340  			set_child(next, parent, parent->left == node);
341  		else
(7) Event else_branch: Reached else branch.
342  			tree->root = next;
343  	
(9) Event cond_false: Condition "left", taking false branch.
344  		if (left && right) {
345  			color = get_color(next);
346  			set_color(get_color(node), next);
347  	
348  			next->left = left;
349  			set_parent(next, left);
350  	
351  			if (next != right) {
352  				parent = get_parent(next);
353  				set_parent(get_parent(node), next);
354  	
355  				node = next->right;
356  				parent->left = node;
357  	
358  				next->right = right;
359  				set_parent(next, right);
360  			} else {
361  				set_parent(parent, next);
362  				parent = next;
363  				node = next->right;
364  			}
(10) Event else_branch: Reached else branch.
365  		} else {
366  			color = get_color(node);
367  			node = next;
368  		}
369  		/*
370  		 * 'node' is now the sole successor's child and 'parent' its
371  		 * new parent (since the successor can have been moved).
372  		 */
(11) Event cond_true: Condition "node", taking true branch.
373  		if (node)
374  			set_parent(parent, node);
375  	
376  		/*
377  		 * The 'easy' cases.
378  		 */
(12) Event cond_false: Condition "color == RB_RED", taking false branch.
379  		if (color == RB_RED)
(13) Event if_end: End of if statement.
380  			return;
(14) Event cond_true: Condition "node", taking true branch.
(15) Event cond_false: Condition "is_red(node)", taking false branch.
381  		if (node && is_red(node)) {
382  			set_color(RB_BLACK, node);
383  			return;
(16) Event if_end: End of if statement.
384  		}
385  	
386  		do {
(17) Event cond_false: Condition "node == tree->root", taking false branch.
387  			if (node == tree->root)
(18) Event if_end: End of if statement.
388  				break;
389  	
(19) Event var_deref_op: Dereferencing null pointer "parent".
Also see events: [var_compare_op]
390  			if (node == parent->left) {
391  				struct rbtree_node *sibling = parent->right;
392  	
393  				if (is_red(sibling)) {
394  					set_color(RB_BLACK, sibling);
395  					set_color(RB_RED, parent);
396  					rotate_left(parent, tree);
397  					sibling = parent->right;
398  				}
399  				if ((!sibling->left || is_black(sibling->left))
400  				    && (!sibling->right || is_black(sibling->right))) {
401  					set_color(RB_RED, sibling);
402  					node = parent;
403  					parent = get_parent(parent);
404  					continue;
405  				}
406  				if (!sibling->right || is_black(sibling->right)) {
407  					set_color(RB_BLACK, sibling->left);
408  					set_color(RB_RED, sibling);
409  					rotate_right(sibling, tree);
410  					sibling = parent->right;
411  				}
412  				set_color(get_color(parent), sibling);
413  				set_color(RB_BLACK, parent);
414  				set_color(RB_BLACK, sibling->right);
415  				rotate_left(parent, tree);
416  				node = tree->root;
417  				break;
418  			} else {
419  				struct rbtree_node *sibling = parent->left;
420  	
421  				if (is_red(sibling)) {
422  					set_color(RB_BLACK, sibling);
423  					set_color(RB_RED, parent);
424  					rotate_right(parent, tree);
425  					sibling = parent->left;
426  				}
427  				if ((!sibling->left || is_black(sibling->left))
428  				    && (!sibling->right || is_black(sibling->right))) {
429  					set_color(RB_RED, sibling);
430  					node = parent;
431  					parent = get_parent(parent);
432  					continue;
433  				}
434  				if (!sibling->left || is_black(sibling->left)) {
435  					set_color(RB_BLACK, sibling->right);
436  					set_color(RB_RED, sibling);
437  					rotate_left(sibling, tree);
438  					sibling = parent->left;
439  				}
440  				set_color(get_color(parent), sibling);
441  				set_color(RB_BLACK, parent);
442  				set_color(RB_BLACK, sibling->left);
443  				rotate_right(parent, tree);
444  				node = tree->root;
445  				break;
446  			}
447  		} while (is_black(node));
448  	
449  		if (node)
450  			set_color(RB_BLACK, node);
451  	}
452  	
453  	void rbtree_replace(struct rbtree_node *old, struct rbtree_node *new,
454  			    struct rbtree *tree)
455  	{
456  		struct rbtree_node *parent = get_parent(old);
457  	
458  		if (parent)
459  			set_child(new, parent, parent->left == old);
460  		else
461  			tree->root = new;
462  	
463  		if (old->left)
464  			set_parent(new, old->left);
465  		if (old->right)
466  			set_parent(new, old->right);
467  	
468  		if (tree->first == old)
469  			tree->first = new;
470  		if (tree->last == old)
471  			tree->last = new;
472  	
473  		*new = *old;
474  	}
475  	
476  	int rbtree_init(struct rbtree *tree, rbtree_cmp_fn_t fn, unsigned long flags)
477  	{
478  		if (flags)
479  			return -1;
480  		tree->root = NULL;
481  		tree->cmp_fn = fn;
482  		tree->first = NULL;
483  		tree->last = NULL;
484  		return 0;
485  	}
486