1 // -*-c++-*- 2 /* $Id$ */ 3 4 /* 5 * 6 * Copyright (C) 1998 David Mazieres (dm@uun.org) 7 * 8 * This program is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU General Public License as 10 * published by the Free Software Foundation; either version 2, or (at 11 * your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, but 14 * WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with this program; if not, write to the Free Software 20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 21 * USA 22 * 23 */ 24 25 26 #ifndef _ITREE_H_ 27 #define _ITREE_H_ 1 28 29 #include "callback.h" 30 #include "keyfunc.h" 31 32 struct __opaquecontainer; 33 #define oc __opaquecontainer_pointer 34 typedef __opaquecontainer *oc; 35 36 enum itree_color {INVALID, BLACK, RED}; 37 38 void itree_insert (oc *, oc, const int, int (*) (void *, oc, oc), void *); 39 void itree_delete (oc *, oc, const int); 40 oc itree_successor (oc, const int); 41 oc itree_predecessor (oc, const int); 42 void __itree_check(oc *, const int, int (*) (void *, oc, oc), void *); 43 #ifdef ITREE_DEBUG 44 #define itree_check(r, os, cmpfn) __itree_check(r, os, cmpfn) 45 #else /* !ITREE_DEBUG */ 46 #define itree_check(r, os, cmpfn) 47 #endif /* !ITREE_DEBUG */ 48 49 struct __itree_entry_private { 50 oc rbe_up; 51 oc rbe_left; 52 oc rbe_right; 53 enum itree_color rbe_color; 54 }; 55 56 template<class T> 57 #ifndef NO_TEMPLATE_FRIENDS 58 class 59 #else /* NO_TEMPLATE_FRIENDS */ 60 struct 61 #endif /* NO_TEMPLATE_FRIENDS */ 62 itree_entry { 63 __itree_entry_private p; 64 #ifndef NO_TEMPLATE_FRIENDS 65 /* Let's get friendly with the implementation... */ 66 template<class U, itree_entry<U> U::*field, class C> 67 friend class itree_core; 68 #endif /* NO_TEMPLATE_FRIENDS */ 69 public: up()70 T *up () const { return (T *) p.rbe_up; } left()71 T *left () const { return (T *) p.rbe_left; } right()72 T *right () const { return (T *) p.rbe_right; } 73 }; 74 75 template<class T, itree_entry<T> T::*field, class C = compare<T> > 76 class itree_core { 77 protected: 78 oc rb_root; 79 80 const C cmp; 81 scmp(void * t,oc a,oc b)82 static int scmp (void *t, oc a, oc b) { 83 return (((itree_core<T, field, C> *) t)->cmp) (*(T *) a, *(T *) b); 84 } 85 86 /* No copying */ 87 itree_core (const itree_core &); 88 itree_core &operator = (const itree_core &); 89 90 #define eos ((ptrdiff_t) &(((T *) 0)->*field).p) 91 #define cmpfn scmp, (void *) this 92 _deleteall_correct(T * n)93 void _deleteall_correct (T *n) 94 { 95 if (n) { 96 _deleteall_correct (left (n)); 97 _deleteall_correct (right (n)); 98 delete n; 99 } 100 } 101 102 public: itree_core()103 itree_core () { clear (); } itree_core(const C & c)104 itree_core (const C &c) : cmp (c) { clear (); } 105 106 // MK 7/6/05: deleteall() is fast but broken; accesses freed memory; 107 // deleteall_correct () is slow but should be safer. 108 // DM: deleteall () possibly fixed deleteall_correct()109 void deleteall_correct () 110 { 111 _deleteall_correct (root ()); 112 clear (); 113 } 114 min_postorder(T * n)115 static T *min_postorder (T *n) { 116 T *nn; 117 if (n) 118 while ((nn = left (n)) || (nn = right (n))) 119 n = nn; 120 return n; 121 } next_postorder(const T * n)122 static T *next_postorder (const T *n) { 123 T *nn = up (n), *nnr; 124 if (nn && (nnr = right (nn)) && n != nnr) 125 return min_postorder (nnr); 126 return nn; 127 } deleteall()128 void deleteall () { 129 T *n, *nn; 130 for (n = min_postorder (root ()); n; n = nn) { 131 nn = next_postorder (n); 132 delete n; 133 } 134 clear (); 135 } 136 clear()137 void clear () {rb_root = NULL;} 138 root()139 T *root () const { return (T *) rb_root; } up(const T * n)140 static T *up (const T *n) { return (n->*field).up (); } left(const T * n)141 static T *left (const T *n) { return (n->*field).left (); } right(const T * n)142 static T *right (const T *n) { return (n->*field).right (); } 143 first()144 T *first () const { 145 T *n, *nn; 146 for (n = root (); n && (nn = left (n)); n = nn) 147 ; 148 return n; 149 } next(const T * n)150 static T *next (const T *n) { return (T *) itree_successor ((oc) n, eos); } prev(const T * n)151 static T *prev (const T *n) { return (T *) itree_predecessor ((oc) n, eos); } 152 insert(T * n)153 void insert (T *n) { 154 itree_insert (&rb_root, (oc) n, eos, cmpfn); 155 itree_check (&rb_root, eos, cmpfn); 156 } remove(T * n)157 void remove (T *n) { 158 itree_delete (&rb_root, (oc) n, eos); 159 itree_check (&rb_root, eos, cmpfn); 160 } 161 search(typename callback<int,const T * >::ref cb)162 T *search (typename callback<int, const T*>::ref cb) const { 163 T *ret = NULL; 164 T *n = root (); 165 166 while (n) { 167 int srchres = (*cb) (n); 168 if (srchres < 0) 169 n = left (n); 170 else if (srchres > 0) 171 n = right (n); 172 else { 173 /* In case there are duplicate keys, keep looking for the first one */ 174 ret = n; 175 n = left (n); 176 } 177 } 178 return ret; 179 } 180 181 // XXX - template search to work around egcs 1.2 bug 182 template<class A1, class A2> search(int (* cb)(const A1 *,const A2 *,const T *),const A1 * a1,const A2 * a2)183 T *search (int (*cb) (const A1 *, const A2 *, const T*), 184 const A1 *a1, const A2 *a2) const { 185 T *ret = NULL; 186 T *n = root (); 187 188 while (n) { 189 int srchres = (*cb) (a1, a2, n); 190 if (srchres < 0) 191 n = left (n); 192 else if (srchres > 0) 193 n = right (n); 194 else { 195 /* In case there are duplicate keys, keep looking for the first one */ 196 ret = n; 197 n = left (n); 198 } 199 } 200 return ret; 201 } 202 traverse(typename callback<void,T * >::ref cb)203 void traverse (typename callback<void, T *>::ref cb) { 204 T *n, *nn; 205 for (n = first (); n; n = nn) { 206 nn = next (n); 207 (*cb) (n); 208 } 209 } traverse(void (T::* fn)())210 void traverse (void (T::*fn) ()) { 211 T *n, *nn; 212 for (n = first (); n; n = nn) { 213 nn = next (n); 214 (n->*fn) (); 215 } 216 } 217 #undef eos 218 #undef cmpfn 219 }; 220 #undef oc 221 222 template<class K, class V, K V::*key, 223 itree_entry<V> V::*field, class C = compare<K> > 224 class itree 225 : public itree_core<V, field, keyfunc_2<int, V, K, key, C> > 226 { 227 typedef keyfunc_2 <int, V, K, key, C> cmp_t; 228 typedef itree_core<V, field, cmp_t> core_t; 229 const C kcmp; 230 231 #if 0 232 template<class T> int kvcmp (const T *k, const V *v) 233 { return kcmp (*k, v->*key); } 234 #else kvcmp(const K * k,const V * v)235 int kvcmp (const K *k, const V *v) 236 { return kcmp (*k, v->*key); } 237 #endif skvcmp(const C * c,const K * k,const V * v)238 static int skvcmp (const C *c, const K *k, const V *v) 239 { return (*c) (*k, v->*key); } 240 241 public: itree()242 itree () {} itree(const C & c)243 itree (const C &c) : core_t (cmp_t (c)), kcmp (c) {} 244 245 #if 0 246 template<class T> V *operator[] (const T &k) { 247 int (itree::*fn) (const T *, const V *) = &kvcmp<T>; 248 return this->search (wrap (this, fn, &k)); 249 } 250 #else 251 V *operator[] (const K &k) { 252 // return search (wrap (this, &kvcmp, &k)); 253 return this->search (skvcmp, &kcmp, &k); 254 } 255 #endif 256 }; 257 258 #endif /* !_ITREE_H_ */ 259