1 /* Copyright (c) 2007-2014 Massachusetts Institute of Technology
3 * Permission is hereby granted, free of charge, to any person obtaining
4 * a copy of this software and associated documentation files (the
5 * "Software"), to deal in the Software without restriction, including
6 * without limitation the rights to use, copy, modify, merge, publish,
7 * distribute, sublicense, and/or sell copies of the Software, and to
8 * permit persons to whom the Software is furnished to do so, subject to
9 * the following conditions:
11 * The above copyright notice and this permission notice shall be
12 * included in all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
17 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
18 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
19 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
20 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 /* simple implementation of red-black trees optimized for use with DIRECT */
29 /* it is convenient to use an explicit node for NULL nodes ... we need
30 to be careful never to change this node indirectly via one of our
32 rb_node nil = {&nil, &nil, &nil, 0, BLACK};
35 void rb_tree_init(rb_tree *t, rb_compare compare) {
41 static void destroy(rb_node *n)
44 destroy(n->l); destroy(n->r);
49 void rb_tree_destroy(rb_tree *t)
55 void rb_tree_destroy_with_keys(rb_tree *t)
57 rb_node *n = rb_tree_min(t);
59 free(n->k); n->k = NULL;
65 static void rotate_left(rb_node *p, rb_tree *t)
67 rb_node *n = p->r; /* must be non-NIL */
71 if (p == p->p->l) p->p->l = n;
78 if (p->r != NIL) p->r->p = p;
81 static void rotate_right(rb_node *p, rb_tree *t)
83 rb_node *n = p->l; /* must be non-NIL */
87 if (p == p->p->l) p->p->l = n;
94 if (p->l != NIL) p->l->p = p;
97 static void insert_node(rb_tree *t, rb_node *n)
99 rb_compare compare = t->compare;
101 rb_node *p = t->root;
103 n->p = n->l = n->r = NIL;
110 /* insert (RED) node into tree */
112 if (compare(k, p->k) <= 0) { /* k <= p->k */
132 if (n->p->c == RED) { /* red cannot have red child */
133 rb_node *u = p == p->p->l ? p->p->r : p->p->l;
134 if (u != NIL && u->c == RED) {
137 if ((p = n->p) != NIL) {
143 if (n == p->r && p == p->p->l) {
147 else if (n == p->l && p == p->p->r) {
153 if (n == p->l && p == p->p->l)
154 rotate_right(p->p, t);
155 else if (n == p->r && p == p->p->r)
156 rotate_left(p->p, t);
162 rb_node *rb_tree_insert(rb_tree *t, rb_key k)
164 rb_node *n = (rb_node *) malloc(sizeof(rb_node));
171 static int check_node(rb_node *n, int *nblack, rb_tree *t)
174 rb_compare compare = t->compare;
175 if (n == NIL) { *nblack = 0; return 1; }
176 if (n->r != NIL && n->r->p != n) return 0;
177 if (n->r != NIL && compare(n->r->k, n->k) < 0)
179 if (n->l != NIL && n->l->p != n) return 0;
180 if (n->l != NIL && compare(n->l->k, n->k) > 0)
183 if (n->r != NIL && n->r->c == RED) return 0;
184 if (n->l != NIL && n->l->c == RED) return 0;
186 if (!(check_node(n->r, &nbl, t) && check_node(n->l, &nbr, t)))
188 if (nbl != nbr) return 0;
189 *nblack = nbl + (n->c == BLACK);
192 int rb_tree_check(rb_tree *t)
195 if (nil.c != BLACK) return 0;
196 if (nil.p != NIL || nil.r != NIL || nil.l != NIL) return 0;
197 if (t->root == NIL) return 1;
198 if (t->root->c != BLACK) return 0;
199 return check_node(t->root, &nblack, t);
202 rb_node *rb_tree_find(rb_tree *t, rb_key k)
204 rb_compare compare = t->compare;
205 rb_node *p = t->root;
207 int comp = compare(k, p->k);
209 p = comp <= 0 ? p->l : p->r;
214 /* find greatest point in subtree p that is <= k */
215 static rb_node *find_le(rb_node *p, rb_key k, rb_tree *t)
217 rb_compare compare = t->compare;
219 if (compare(p->k, k) <= 0) { /* p->k <= k */
220 rb_node *r = find_le(p->r, k, t);
227 return NULL; /* k < everything in subtree */
230 /* find greatest point in t <= k */
231 rb_node *rb_tree_find_le(rb_tree *t, rb_key k)
233 return find_le(t->root, k, t);
236 /* find greatest point in subtree p that is < k */
237 static rb_node *find_lt(rb_node *p, rb_key k, rb_tree *t)
239 rb_compare compare = t->compare;
241 if (compare(p->k, k) < 0) { /* p->k < k */
242 rb_node *r = find_lt(p->r, k, t);
249 return NULL; /* k <= everything in subtree */
252 /* find greatest point in t < k */
253 rb_node *rb_tree_find_lt(rb_tree *t, rb_key k)
255 return find_lt(t->root, k, t);
258 /* find least point in subtree p that is > k */
259 static rb_node *find_gt(rb_node *p, rb_key k, rb_tree *t)
261 rb_compare compare = t->compare;
263 if (compare(p->k, k) > 0) { /* p->k > k */
264 rb_node *l = find_gt(p->l, k, t);
271 return NULL; /* k >= everything in subtree */
274 /* find least point in t > k */
275 rb_node *rb_tree_find_gt(rb_tree *t, rb_key k)
277 return find_gt(t->root, k, t);
280 rb_node *rb_tree_min(rb_tree *t)
282 rb_node *n = t->root;
283 while (n != NIL && n->l != NIL)
285 return(n == NIL ? NULL : n);
288 rb_node *rb_tree_max(rb_tree *t)
290 rb_node *n = t->root;
291 while (n != NIL && n->r != NIL)
293 return(n == NIL ? NULL : n);
296 rb_node *rb_tree_succ(rb_node *n)
304 } while (prev == n->r && n != NIL);
305 return n == NIL ? NULL : n;
315 rb_node *rb_tree_pred(rb_node *n)
323 } while (prev == n->l && n != NIL);
324 return n == NIL ? NULL : n;
334 rb_node *rb_tree_remove(rb_tree *t, rb_node *n)
338 if (n->l != NIL && n->r != NIL) {
339 rb_node *lmax = n->l;
340 while (lmax->r != NIL) lmax = lmax->r;
344 m = n->l != NIL ? n->l : n->r;
346 if (n->p->r == n) n->p->r = m;
352 if (m != NIL) m->p = mp;
359 rb_node *s = m == mp->l ? mp->r : mp->l;
363 if (m == mp->l) rotate_left(mp, t);
364 else rotate_right(mp, t);
365 s = m == mp->l ? mp->r : mp->l;
367 if (mp->c == BLACK && s->c == BLACK
368 && s->l->c == BLACK && s->r->c == BLACK) {
369 if (s != NIL) s->c = RED;
373 else if (mp->c == RED && s->c == BLACK &&
374 s->l->c == BLACK && s->r->c == BLACK) {
375 if (s != NIL) s->c = RED;
379 if (m == mp->l && s->c == BLACK &&
380 s->l->c == RED && s->r->c == BLACK) {
384 s = m == mp->l ? mp->r : mp->l;
386 else if (m == mp->r && s->c == BLACK &&
387 s->r->c == RED && s->l->c == BLACK) {
391 s = m == mp->l ? mp->r : mp->l;
408 n->k = k; /* n may have changed during remove */
409 return n; /* the node that was deleted may be different from initial n */
412 rb_node *rb_tree_resort(rb_tree *t, rb_node *n)
414 n = rb_tree_remove(t, n);
419 /* shift all key pointers by kshift ... this is useful when the keys
420 are pointers into another array, that has been resized with realloc */
421 static void shift_keys(rb_node *n, ptrdiff_t kshift) /* assumes n != NIL */
424 if (n->l != NIL) shift_keys(n->l, kshift);
425 if (n->r != NIL) shift_keys(n->r, kshift);
427 void rb_tree_shift_keys(rb_tree *t, ptrdiff_t kshift)
429 if (t->root != NIL) shift_keys(t->root, kshift);