2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these librararies and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
23 /* $XConsortium: tree.c /main/4 1995/11/09 12:53:11 rswiston $ */
25 * (c) Copyright 1993, 1994 Hewlett-Packard Company
26 * (c) Copyright 1993, 1994 International Business Machines Corp.
27 * (c) Copyright 1993, 1994 Novell, Inc.
28 * (c) Copyright 1993, 1994 Sun Microsystems, Inc.
31 /* 2-3-4 tree, a.k.a. red-black tree, implementation */
33 #include <EUSCompat.h>
34 #include <sys/param.h>
42 int size; /* used in insert and size */
43 int count; /* used in checktree only */
44 Rb_Status status; /* used in checktree and insert */
45 caddr_t data; /* used in lookups only */
46 Tree_node *i; /* used in insert only */
47 caddr_t key; /* used in insert only */
48 Tree_node *d; /* used in delete only */
49 Tree_node *y; /* dummy that is at both links of z */
50 Tree_node *z; /* dummy used as child of leaf nodes */
51 Rb_tree *tree; /* back link to parent tree */
53 _DtCmsEnumerateProc enumerate;
54 _DtCmsCompareProc compare;
57 typedef void (*Action_proc)
58 (/* Private *private; Tree_node *y, *z, *root */);
62 balance(Tree_node *gg, Tree_node *g, Tree_node *f, Tree_node *x)
66 if (gg == NULL || g == NULL) exit (-1);
93 if (g == gg->rlink) gg->rlink = f;
102 doit(Rb_tree *tree, Action_proc proc)
107 if (tree==NULL) return;
108 private = (Private *) tree->private;
110 if (root == NULL || root->llink != NULL) {
111 private->status = rb_badtable;
114 proc(private, private->y, private->z, root);
118 rb_create (_DtCmsGetKeyProc get, _DtCmsCompareProc compare)
121 Tree_node *root, *y, *z;
124 p = (Private *) calloc (1, sizeof(Private));
132 p->y = (Tree_node *) calloc (1, sizeof(Tree_node));
133 p->z = (Tree_node *) calloc (1, sizeof(Tree_node));
136 p->compare = compare;
138 root = (Tree_node *) calloc (1, sizeof(Tree_node));
141 tree = (Rb_tree *) calloc (1, sizeof(Rb_tree));
143 tree->private = (caddr_t) p;
144 p->tree = tree; /* link back so callbacks can access */
149 y->llink = y->rlink = NULL;
151 z->llink = z->rlink = y;
158 rb_destroy(Rb_tree *tree, _DtCmsEnumerateProc destroy)
162 Tree_node *node = NULL;
165 /* NOTE:there is a client data field
166 associated with the tree struct.
167 It is up to the client to destroy
169 if (tree==NULL) return;
170 p = (Private *) tree->private;
171 data = rb_lookup_smallest(tree);
173 /* enumerate tree, destroying data */
174 while(data != NULL) {
176 node = rb_delete(tree, key);
180 data = rb_lookup_next_larger(tree, key);
183 /* destroy the private internal struct */
188 /* destroy the root node */
191 /* destroy the tree */
197 size_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
199 /* dummy proc for monitor */
203 rb_size(Rb_tree *tree)
206 if (tree==NULL) return(0);
207 p = (Private *) tree->private;
209 doit(tree, size_callback);
217 insert_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
219 Tree_node *x=NULL, *gg=NULL, *g=NULL, *f=NULL;
220 _DtCmsComparisonResult c = _DtCmsIsGreater;
225 if (x->llink->color == red && x->rlink->color == red) {
227 if (c == _DtCmsIsEqual) {
228 private->status = rb_duplicate;
229 root->rlink->color = black;
235 if (c == _DtCmsIsLess) f->llink = x; else f->rlink = x;
239 x->llink->color = black;
240 x->rlink->color = black;
242 if (f->color == red) {
243 g = balance (gg, g, f, x);
247 if (c == _DtCmsIsEqual) break;
248 gg = g; g = f; f = x;
249 c = private->compare (private->key, x->data);
250 if (c==_DtCmsIsEqual) {
251 private->status=rb_duplicate;
252 root->rlink->color=black;
255 x = (c == _DtCmsIsLess) ? x->llink : x-> rlink;
257 root->rlink->color = black;
261 rb_insert_node(Rb_tree *tree, Tree_node *node, caddr_t key)
265 if (tree==NULL) return(rb_notable);
266 private = (Private *) tree->private;
267 private->status = rb_ok;
270 doit (tree, insert_callback);
271 return (private->status);
275 rb_insert(Rb_tree *tree, caddr_t data, caddr_t key)
279 if (tree==NULL) return(rb_notable);
280 node = (Tree_node *)calloc(1, sizeof(Tree_node));
282 return(rb_insert_node(tree, node, key));
286 delete_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
288 Tree_node *f, *result, *parent;
289 Tree_node *x, *g, *b;
290 _DtCmsComparisonResult c;
298 if (x->llink->color == black && x->rlink->color == black)
300 c = private->compare(private->key, x->data);
301 if (c == _DtCmsIsEqual) {
308 if (c == _DtCmsIsLess) {
317 c = private->compare(private->key, x->data);
318 if (c == _DtCmsIsEqual) {
323 if (x->color == red || x->llink->color == red ||
324 x->rlink->color == red) continue;
325 if (b->color == red) {
336 if (f == g->llink) g->llink = b;
339 c = private->compare(private->key, x->data);
344 if (b->llink->color == red) {
345 b->llink->color = black;
346 x = balance (g, f, b, b->llink);
347 c = private->compare(private->key, x->data);
350 if (b->rlink->color == red) {
351 b->rlink->color = black;
352 x = balance(g, f, b, b->rlink);
353 c = private->compare(private->key, x->data);
359 root->rlink->color = black;
362 if (result != NULL) {
363 if (g->llink == f) g->llink = z;
366 if (parent->llink == result) parent->llink = f;
367 else parent->rlink = f;
368 f->llink = result->llink;
369 f->rlink = result->rlink;
370 f->color = result->color;
378 rb_delete(Rb_tree *tree, caddr_t key)
381 if (tree==NULL) return((Tree_node *)NULL);
382 p = (Private *) tree->private;
384 p->d = NULL; /* in case the key is not found */
385 doit (tree, delete_callback);
391 lookup_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
393 _DtCmsComparisonResult c;
394 Tree_node *eq = root->rlink;
397 c = private->compare(private->key, eq->data);
404 case _DtCmsIsGreater:
411 bye: private->data = eq->data;
415 rb_lookup(Rb_tree *tree, caddr_t key)
418 if (tree==NULL) return((caddr_t)NULL);
419 private = (Private *)tree->private;
421 private->data = NULL; /* might have been previously used */
422 doit (tree, lookup_callback);
423 return (private->data);
428 lookup_smallest_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
430 Tree_node *smallest = root->rlink;
431 if (smallest == z) return;
432 while (smallest->llink != z) {
433 smallest = smallest->llink;
435 private->data = smallest->data;
439 rb_lookup_smallest(Rb_tree *tree)
442 if (tree==NULL) return((caddr_t)NULL);
443 private = (Private *)tree->private;
444 private->data = NULL; /* might have been previously used */
445 doit (tree, lookup_smallest_callback);
446 return (private->data);
451 next_larger_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
453 Tree_node *larger = NULL;
454 Tree_node *x = root->rlink;
456 if (private->compare (private->key, x->data) == _DtCmsIsLess) {
462 if (larger != NULL) private->data = larger->data;
466 rb_lookup_next_larger(Rb_tree *tree, caddr_t key)
469 if (tree==NULL) return((caddr_t)NULL);
470 private = (Private *) tree->private;
472 private->data = NULL; /* might have been previously used */
473 doit (tree, next_larger_callback);
474 return(private->data);
479 lookup_largest_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
481 Tree_node *largest = root->rlink;
482 if (largest == z) return;
483 while (largest->rlink != z) {
484 largest = largest->rlink;
486 private->data = largest->data;
490 rb_lookup_largest(Rb_tree *tree)
494 if (tree==NULL) return((caddr_t)NULL);
495 private = (Private *) tree->private;
496 private->data = NULL; /* might have been previously used */
497 doit (tree, lookup_largest_callback);
498 return (private->data);
503 next_smaller_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
506 Tree_node *smaller = NULL;
507 Tree_node *x = root->rlink;
509 if (private->compare(private->key, x->data) == _DtCmsIsGreater) {
515 if (smaller != NULL) private->data = smaller->data;
519 rb_lookup_next_smaller(Rb_tree *tree, caddr_t key)
522 if (tree==NULL) return((caddr_t)NULL);
523 private = (Private *) tree->private;
525 private->data = NULL; /* might have been previously used */
526 doit (tree, next_smaller_callback);
527 return(private->data);
530 typedef enum {up, down} Direction;
533 visit_subtree(Tree_node *node, Private *p, Tree_node *z, Direction dir)
536 link = (dir == up) ? node->llink : node->rlink;
537 if (link != z && visit_subtree(link, p, z, dir)) return(B_TRUE);
538 if (p->enumerate((caddr_t)node, node->data)) return(B_TRUE);
539 link = (dir == up) ? node->rlink : node->llink;
540 if (link != z) return(visit_subtree(link, p, z, dir));
541 else return(B_FALSE);
546 enumerate_up_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
548 if (root == NULL || root->rlink == z) return (B_FALSE);
549 return (visit_subtree(root->rlink, private, z, up));
553 rb_enumerate_up(Rb_tree *tree, _DtCmsEnumerateProc proc)
556 if (tree==NULL) return (rb_badtable);
557 private = (Private *) tree->private;
558 private->enumerate = proc;
559 if (tree->root == NULL || tree->root->llink != NULL)
562 if (enumerate_up_callback(private, private->y, private->z, tree->root))
570 enumerate_down_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
572 if (root == NULL || root->rlink == z) return;
573 (void) visit_subtree(root->rlink, private, z, down);
577 rb_enumerate_down(Rb_tree *tree, _DtCmsEnumerateProc proc)
580 if (tree==NULL) return;
581 private = (Private *) tree->private;
582 private->enumerate = proc;
583 doit (tree, enumerate_down_callback);
586 /* --------------------DEBUGGING-------------------------*/
594 typedef struct {caddr_t max; int i; boolean_t bool;} Rec;
597 check1(Tree_node *x, caddr_t max, Tree_node *z, Rec *rec, Private *private)
601 Rec localrec; Rec *localp = &localrec;
608 check1(x->llink, max, z, localp, private);
609 if (private->status == rb_badtable) return;
612 redchild = localp->bool;
613 if (!assert (!(redchild && (x->color == red)))) {
614 private->status = rb_badtable;
617 if (!assert (private->compare(max, x->data) ==
618 (private->count == 0 ? _DtCmsIsEqual : _DtCmsIsLess))) {
619 private->status = rb_badtable;
623 check1(x->rlink, private->get(x->data), z, localp, private);
624 if (private->status == rb_badtable) return;
627 redchild = localp->bool;
628 if (!assert (!(redchild && (x->color == red)))) {
629 private->status = rb_badtable;
632 if (!assert (dl == dr)) {
633 private->status = rb_badtable;
637 rec->i = dl + ((x->color == black) ? 1 : 0);
638 rec->bool = ((x->color == red) ? B_TRUE : B_FALSE);
642 check_tree_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
644 if (!assert (z->llink == y)) {
645 private->status = rb_badtable;
648 if (!assert (z->rlink == y)) {
649 private->status = rb_badtable;
652 if (root->rlink != z) {
654 Rec *localp = &localrec;
655 Tree_node *smallest = root->rlink;
656 while (smallest->llink != z) {
657 smallest = smallest->llink;
659 check1(root->rlink, private->get(smallest->data), z, localp, private);
660 if (private->status == rb_badtable) return;
665 rb_check_tree(Rb_tree *tree)
668 if (tree==NULL) return(rb_notable);
669 p = (Private *) tree->private;
672 doit (tree, check_tree_callback);