2 * RCS $Id: redblack.h,v 1.2 2005/10/17 00:29:49 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.2 2005/10/17 00:29:49 bdemsky
82 * Hacks to allow repairs of fields used to define layouts of arrays.
84 * Revision 1.1 2005/10/10 03:30:12 bdemsky
87 * Checking in repair runtime and generated repair code for freeciv.
89 * Revision 1.1 2004/10/28 19:29:04 bdemsky
90 * Checking in C runtime.
92 * Revision 1.1 2004/04/06 19:57:17 bdemsky
93 * Checking in redblack sources
95 * Revision 1.2 2003/06/18 06:06:18 bdemsky
98 * Added option to pass in function to free items in the redblack interval tree.
100 * Revision 1.5 2002/01/30 07:54:53 damo
101 * Fixed up the libtool versioning stuff (finally)
102 * Fixed bug 500600 (not detecting a NULL return from malloc)
103 * Fixed bug 509485 (no longer needs search.h)
104 * Cleaned up debugging section
105 * Allow multiple inclusions of redblack.h
106 * Thanks to Matthias Andree for reporting (and fixing) these
108 * Revision 1.4 2000/06/06 14:43:43 damo
109 * Added all the rbwalk & rbopenlist stuff. Fixed up malloc instead of sbrk.
110 * Added two new examples
112 * Revision 1.3 2000/05/24 06:45:27 damo
113 * Converted everything over to using const
114 * Added a new example1.c file to demonstrate the worst case scenario
115 * Minor fixups of the spec file
117 * Revision 1.2 2000/05/24 06:17:10 damo
118 * Fixed up the License (now the LGPL)
120 * Revision 1.1 2000/05/24 04:15:53 damo
121 * Initial import of files. Versions are now all over the place. Oh well