libtu/rb.h

   1 /*
   2 Generic C code for red-black trees.
   3 Copyright (C) 2000 James S. Plank,
   4               2004 Tuomo Valkonen.
   5
   6 This library is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU Lesser General Public
   8 License as published by the Free Software Foundation; either
   9 version 2.1 of the License, or (at your option) any later version.
  10
  11 This library is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 Lesser General Public License for more details.
  15
  16 You should have received a copy of the GNU Lesser General Public
  17 License along with this library; if not, write to the Free Software
  18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA
  19  */
  20
  21 /* Revision 1.2.  Jim Plank */
  22
  23 /* Original code by Jim Plank (plank@cs.utk.edu) */
  24 /* modified for THINK C 6.0 for Macintosh by Chris Bartley */
  25
  26 #ifndef LIBTU_RB_H
  27 #define LIBTU_RB_H
  28
  29 typedef struct rb_status {
  30   unsigned red : 1 ;
  31   unsigned internal : 1 ;
  32   unsigned left : 1 ;
  33   unsigned root : 1 ;
  34   unsigned head : 1 ;
  35 } Rb_status;
  36
  37 /* Main rb_node.  You only ever use the fields
  38
  39    c.list.flink
  40    c.list.blink
  41
  42    k.key or k.ikey
  43    v.val
  44 */
  45
  46
  47 typedef struct rb_node {
  48   union {
  49     struct {
  50       struct rb_node *flink;
  51       struct rb_node *blink;
  52     } list;
  53     struct {
  54       struct rb_node *left;
  55       struct rb_node *right;
  56     } child;
  57   } c;
  58   union {
  59     struct rb_node *parent;
  60     struct rb_node *root;
  61   } p;
  62   Rb_status s;
  63   union {
  64     int ikey;
  65     const void *key;
  66     struct rb_node *lext;
  67   } k;
  68   union {
  69     int ival;
  70     void *val;
  71     struct rb_node *rext;
  72   } v;
  73 } *Rb_node;
  74
  75
  76 typedef int Rb_compfn(const void *, const void *);
  77
  78
  79 extern Rb_node make_rb();   /* Creates a new rb-tree */
  80
  81 /* Creates a node with key key and val val and inserts it into the tree.
  82    rb_insert uses strcmp() as comparison funcion.  rb_inserti uses <>=,
  83    rb_insertg uses func() */
  84
  85 extern Rb_node rb_insert(Rb_node tree, const char *key, void *val);
  86 extern Rb_node rb_inserti(Rb_node tree, int ikey, void *val);
  87 extern Rb_node rb_insertp(Rb_node tree, const void *key, void *val);
  88 extern Rb_node rb_insertg(Rb_node tree, const void *key, void *val,
  89                           Rb_compfn *func);
  90
  91
  92 /* returns an external node in t whose value is equal
  93   k or whose value is the smallest value greater than k. */
  94
  95 extern Rb_node rb_find_key(Rb_node root, const char *key);
  96 extern Rb_node rb_find_ikey(Rb_node root, int ikey);
  97 extern Rb_node rb_find_pkey(Rb_node root, const void *key);
  98 extern Rb_node rb_find_gkey(Rb_node root, const void *key, Rb_compfn *func);
  99
 100
 101 /* Works just like the find_key versions only it returns whether or not
 102    it found the key in the integer variable found */
 103
 104 extern Rb_node rb_find_key_n(Rb_node root, const char *key, int *found);
 105 extern Rb_node rb_find_ikey_n(Rb_node root, int ikey, int *found);
 106 extern Rb_node rb_find_pkey_n(Rb_node root, const void *key, int *found);
 107 extern Rb_node rb_find_gkey_n(Rb_node root, const void *key,
 108                               Rb_compfn *func, int *found);
 109
 110
 111 /* Creates a node with key key and val val and inserts it into the
 112    tree before/after node nd.  Does not check to ensure that you are
 113    keeping the correct order */
 114
 115 extern Rb_node rb_insert_b(Rb_node nd, const void *key, void *val);
 116 extern Rb_node rb_insert_a(Rb_node nd, const void *key, void *val);
 117
 118
 119 extern void rb_delete_node(Rb_node node);  /* Deletes and frees a node (but
 120                                               not the key or val) */
 121 extern void rb_free_tree(Rb_node root);  /* Deletes and frees an entire tree */
 122
 123 extern void *rb_val(Rb_node node);  /* Returns node->v.val -- this is to shut
 124                                        lint up */
 125
 126 extern int rb_nblack(Rb_node n); /* returns # of black nodes in path from
 127                                     n to the root */
 128 int rb_plength(Rb_node n);       /* returns the # of nodes in path from
 129                                     n to the root */
 130
 131 #define rb_first(n) (n->c.list.flink)
 132 #define rb_last(n) (n->c.list.blink)
 133 #define rb_next(n) (n->c.list.flink)
 134 #define rb_prev(n) (n->c.list.blink)
 135 #define rb_empty(t) (t->c.list.flink == t)
 136 #ifndef rb_nil
 137 #define rb_nil(t) (t)
 138 #endif
 139
 140 #define rb_traverse(ptr, lst) \
 141   for(ptr = rb_first(lst); ptr != rb_nil(lst); ptr = rb_next(ptr))
 142
 143 #endif /* LIBTU_RB_H */