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 libraries 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.h /main/4 1995/11/09 12:53:31 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.
38 ** 2-3-4 tree, a.k.a. red-black tree
41 typedef enum {red=0, black=1} Color;
52 caddr_t private; /* for internal tool state */
55 extern Rb_tree* rb_create P((_DtCmsGetKeyProc, _DtCmsCompareProc));
57 extern void rb_destroy P((Rb_tree*, _DtCmsEnumerateProc));
59 extern int rb_size P((Rb_tree*t));
61 extern Rb_Status rb_insert P((Rb_tree*, caddr_t data, caddr_t key));
63 extern Rb_Status rb_insert_node P((Rb_tree*, Tree_node*, caddr_t key));
65 extern Tree_node * rb_delete P((Rb_tree*, caddr_t key));
67 extern caddr_t rb_lookup P((Rb_tree*, caddr_t key));
69 extern caddr_t rb_lookup_next_larger P((Rb_tree*, caddr_t key));
71 extern caddr_t rb_lookup_next_smaller P((Rb_tree*, caddr_t key));
73 extern caddr_t rb_lookup_smallest P((Rb_tree*));
75 extern caddr_t rb_lookup_largest P((Rb_tree*));
77 extern Rb_Status rb_enumerate_up P((Rb_tree*, _DtCmsEnumerateProc));
79 extern void rb_enumerate_down P((Rb_tree*, _DtCmsEnumerateProc));
81 extern Rb_Status rb_check_tree P((Rb_tree *));