1 /* $XConsortium: tree.h /main/4 1995/11/09 12:53:31 rswiston $ */
3 * (c) Copyright 1993, 1994 Hewlett-Packard Company
4 * (c) Copyright 1993, 1994 International Business Machines Corp.
5 * (c) Copyright 1993, 1994 Novell, Inc.
6 * (c) Copyright 1993, 1994 Sun Microsystems, Inc.
16 ** 2-3-4 tree, a.k.a. red-black tree
19 typedef enum {red=0, black=1} Color;
30 caddr_t private; /* for internal tool state */
33 extern Rb_tree* rb_create P((_DtCmsGetKeyProc, _DtCmsCompareProc));
35 extern void rb_destroy P((Rb_tree*, _DtCmsEnumerateProc));
37 extern int rb_size P((Rb_tree*t));
39 extern Rb_Status rb_insert P((Rb_tree*, caddr_t data, caddr_t key));
41 extern Rb_Status rb_insert_node P((Rb_tree*, Tree_node*, caddr_t key));
43 extern Tree_node * rb_delete P((Rb_tree*, caddr_t key));
45 extern caddr_t rb_lookup P((Rb_tree*, caddr_t key));
47 extern caddr_t rb_lookup_next_larger P((Rb_tree*, caddr_t key));
49 extern caddr_t rb_lookup_next_smaller P((Rb_tree*, caddr_t key));
51 extern caddr_t rb_lookup_smallest P((Rb_tree*));
53 extern caddr_t rb_lookup_largest P((Rb_tree*));
55 extern Rb_Status rb_enumerate_up P((Rb_tree*, _DtCmsEnumerateProc));
57 extern void rb_enumerate_down P((Rb_tree*, _DtCmsEnumerateProc));
59 extern Rb_Status rb_check_tree P((Rb_tree *));