2 * RCS $Id: redblack.h,v 1.1 2004/05/06 21:16:22 bdemsky Exp $
6 Redblack balanced tree algorithm
7 Copyright (C) Damian Ivereigh 2000
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU Lesser General Public License as published by
11 the Free Software Foundation; either version 2.1 of the License, or
12 (at your option) any later version. See the file COPYING for details.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU Lesser General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
24 /* Header file for redblack.c, should be included by any code that
25 ** uses redblack.c since it defines the functions
28 /* Stop multiple includes */
31 /* For rbwalk - pinched from search.h */
40 const struct rbnode *rootp;
41 const struct rbnode *nextp;
44 #define RBLIST struct rblists
48 struct rbnode *rb_root;
52 const void *low,*high;
55 struct rbtree *rbinit();
56 int rbinsert(const void *low, const void * high, void *object,struct rbtree *rbinfo);
57 struct pair rbfind(const void *low,const void *high, struct rbtree *rbinfo);
58 const void *rbdelete(const void *, struct rbtree *);
59 void *rblookup(const void *, const void *,struct rbtree *);
60 int rbsearch(const void *low, const void *high, struct rbtree *rbinfo);
61 void rbdestroy(struct rbtree *,void (*free_function)(void *));
62 void rbwalk(const struct rbtree *,
63 void (*)(const void *, const VISIT, const int, void *),
65 RBLIST *rbopenlist(const struct rbtree *);
66 const void *rbreadlist(RBLIST *);
67 void rbcloselist(RBLIST *);
69 /* Some useful macros */
70 #define rbmin(rbinfo) rblookup(RB_LUFIRST, NULL, (rbinfo))
71 #define rbmax(rbinfo) rblookup(RB_LULAST, NULL, (rbinfo))
74 #endif /* _REDBLACK_H */
78 * $Log: redblack.h,v $
79 * Revision 1.1 2004/05/06 21:16:22 bdemsky
80 * Moved the interpreter
82 * Revision 1.4 2003/06/18 06:08:18 bdemsky
86 * 1) freeing the memory we use (imagine that)...will make dan's life easier &
87 * allow us to run cooler benchmarks. (not completed yet)
88 * 2) generating dot graphs of dependencies...not completed yet - the graphs aren't
89 * appropriately labeled.
91 * Revision 1.2 2003/06/18 06:06:18 bdemsky
94 * Added option to pass in function to free items in the redblack interval tree.
96 * Revision 1.5 2002/01/30 07:54:53 damo
97 * Fixed up the libtool versioning stuff (finally)
98 * Fixed bug 500600 (not detecting a NULL return from malloc)
99 * Fixed bug 509485 (no longer needs search.h)
100 * Cleaned up debugging section
101 * Allow multiple inclusions of redblack.h
102 * Thanks to Matthias Andree for reporting (and fixing) these
104 * Revision 1.4 2000/06/06 14:43:43 damo
105 * Added all the rbwalk & rbopenlist stuff. Fixed up malloc instead of sbrk.
106 * Added two new examples
108 * Revision 1.3 2000/05/24 06:45:27 damo
109 * Converted everything over to using const
110 * Added a new example1.c file to demonstrate the worst case scenario
111 * Minor fixups of the spec file
113 * Revision 1.2 2000/05/24 06:17:10 damo
114 * Fixed up the License (now the LGPL)
116 * Revision 1.1 2000/05/24 04:15:53 damo
117 * Initial import of files. Versions are now all over the place. Oh well