Repair/RepairCompiler/MCC/CRuntime/redblack.h

   1 /*
   2  * RCS $Id: redblack.h,v 1.1 2004/10/28 19:28:59 bdemsky Exp $
   3  */
   4
   5 /*
   6    Redblack balanced tree algorithm
   7    Copyright (C) Damian Ivereigh 2000
   8
   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.
  13
  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.
  18
  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.
  22  */
  23
  24 /* Header file for redblack.c, should be included by any code that
  25 ** uses redblack.c since it defines the functions
  26 */
  27
  28 /* Stop multiple includes */
  29 #ifndef _REDBLACK_H
  30
  31 /* For rbwalk - pinched from search.h */
  32 typedef enum {
  33   preorder,
  34   postorder,
  35   endorder,
  36   leaf
  37 } VISIT;
  38
  39 struct rblists {
  40   const struct rbnode *rootp;
  41   const struct rbnode *nextp;
  42 };
  43
  44 #define RBLIST struct rblists
  45
  46 struct rbtree {
  47   /* root of tree */
  48   struct rbnode *rb_root;
  49 };
  50
  51 struct pair {
  52   const void *low,*high;
  53 };
  54
  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 *),
  64                 void *);
  65 RBLIST *rbopenlist(const struct rbtree *);
  66 const void *rbreadlist(RBLIST *);
  67 void rbcloselist(RBLIST *);
  68
  69 /* Some useful macros */
  70 #define rbmin(rbinfo) rblookup(RB_LUFIRST, NULL, (rbinfo))
  71 #define rbmax(rbinfo) rblookup(RB_LULAST, NULL, (rbinfo))
  72
  73 #define _REDBLACK_H
  74 #endif /* _REDBLACK_H */
  75
  76 /*
  77  *
  78  * $Log: redblack.h,v $
  79  * Revision 1.1  2004/10/28 19:28:59  bdemsky
  80  * Checking in C runtime.
  81  *
  82  * Revision 1.1  2004/03/07 22:02:43  bdemsky
  83  *
  84  *
  85  * Still buggy, but getting closer...
  86  *
  87  * Revision 1.2  2003/06/18 06:06:18  bdemsky
  88  *
  89  *
  90  * Added option to pass in function to free items in the redblack interval tree.
  91  *
  92  * Revision 1.5  2002/01/30 07:54:53  damo
  93  * Fixed up the libtool versioning stuff (finally)
  94  * Fixed bug 500600 (not detecting a NULL return from malloc)
  95  * Fixed bug 509485 (no longer needs search.h)
  96  * Cleaned up debugging section
  97  * Allow multiple inclusions of redblack.h
  98  * Thanks to Matthias Andree for reporting (and fixing) these
  99  *
 100  * Revision 1.4  2000/06/06 14:43:43  damo
 101  * Added all the rbwalk & rbopenlist stuff. Fixed up malloc instead of sbrk.
 102  * Added two new examples
 103  *
 104  * Revision 1.3  2000/05/24 06:45:27  damo
 105  * Converted everything over to using const
 106  * Added a new example1.c file to demonstrate the worst case scenario
 107  * Minor fixups of the spec file
 108  *
 109  * Revision 1.2  2000/05/24 06:17:10  damo
 110  * Fixed up the License (now the LGPL)
 111  *
 112  * Revision 1.1  2000/05/24 04:15:53  damo
 113  * Initial import of files. Versions are now all over the place. Oh well
 114  *
 115  */
 116