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 /* Template implementation of intrusive hash table. Note that while 26 * externally this code is type safe, interally it makes use of void * 27 * pointers and byte offsets of field structures. This permits a 28 * single implementation of the _ihash_grow() function. */ 29 30 #ifndef _IHASH_H_ 31 #define _IHASH_H_ 1 32 33 #ifdef DMALLOC 34 # ifndef IHASH_DEBUG 35 # define IHASH_DEBUG 1 36 # endif /* !IHASH_DEBUG */ 37 # if IHASH_DEBUG 38 /* Check hash table consistency if check-funcs token set */ 39 # define ihash_do_debug() (dmalloc_debug_current () & 0x4000) 40 # include "opnew.h" 41 # endif /* IHASH_DEBUG */ 42 # include <typeinfo> 43 #endif /* DMALLOC */ 44 45 #include "callback.h" 46 #include "keyfunc.h" 47 48 template<class T> class ihash_entry; 49 template<class T, ihash_entry<T> T::*field> class ihash_core; 50 51 struct _ihash_table; 52 extern void _ihash_grow (_ihash_table *, const size_t); 53 54 struct _ihash_entry { 55 void *next; 56 void **pprev; 57 hash_t val; 58 }; 59 60 /* The template is for consistency accross all interfaces. We don't 61 * actually need it. */ 62 template<class T> 63 #ifndef NO_TEMPLATE_FRIENDS 64 class 65 #else /* NO_TEMPLATE_FRIENDS */ 66 struct 67 #endif /* NO_TEMPLATE_FRIENDS */ 68 ihash_entry : _ihash_entry { 69 #ifndef NO_TEMPLATE_FRIENDS 70 template<class U, ihash_entry<U> U::*field> friend class ihash_core; 71 // template<ihash_entry<T> T::*field> friend class ihash_core<T, field>; 72 #endif /* NO_TEMPLATE_FRIENDS */ 73 }; 74 75 struct _ihash_table { 76 size_t buckets; 77 size_t entries; 78 void **tab; 79 }; 80 81 template<class T, ihash_entry<T> T::*field> 82 class ihash_core { 83 _ihash_table t; 84 85 protected: init()86 void init () { 87 t.buckets = t.entries = 0; 88 t.tab = NULL; 89 _ihash_grow (&t, (size_t) &(((T *) 0)->*field)); 90 } ihash_core()91 ihash_core () { init (); } 92 present(T * elm)93 bool present (T *elm) { 94 for (T *e = lookup_val ((elm->*field).val); e; e = next_val (e)) 95 if (e == elm) 96 return true; 97 return false; 98 } _check()99 void _check () { 100 #if IHASH_DEBUG 101 if (ihash_do_debug ()) { 102 size_t s = 0; 103 for (size_t n = 0; n < t.buckets; n++) 104 for (T *e = (T *) t.tab[n], *ne; e; e = ne) { 105 ne = (T *) (e->*field).next; 106 assert (n == (e->*field).val % t.buckets); 107 assert (ne != e); 108 s++; 109 } 110 assert (s == t.entries); 111 } 112 #endif /* IHASH_DEBUG */ 113 } 114 insert_val(T * elm,hash_t hval)115 void insert_val (T *elm, hash_t hval) { 116 #if IHASH_DEBUG 117 if (ihash_do_debug () && present (elm)) 118 panic ("ihash_core(%s)::insert_val: element already in hash table\n", 119 typeid (ihash_core).name ()); 120 #endif /* IHASH_DEBUG */ 121 _check (); 122 if (++t.entries >= t.buckets) 123 _ihash_grow (&t, (size_t) (_ihash_entry *) &(((T *) 0)->*field)); 124 (elm->*field).val = hval; 125 126 size_t bn = hval % t.buckets; 127 T *np; 128 if ((np = (T *) t.tab[bn])) 129 (np->*field).pprev = &(elm->*field).next; 130 (elm->*field).next = np; 131 (elm->*field).pprev = &t.tab[bn]; 132 t.tab[bn] = elm; 133 _check (); 134 } 135 lookup_val(hash_t hval)136 T *lookup_val (hash_t hval) const { 137 T *elm; 138 for (elm = (T *) t.tab[hval % t.buckets]; 139 elm && (elm->*field).val != hval; 140 elm = (T *) (elm->*field).next) 141 ; 142 return elm; 143 } 144 next_val(T * elm)145 static T *next_val (T *elm) { 146 hash_t hval = (elm->*field).val; 147 while ((elm = (T *) (elm->*field).next) && (elm->*field).val != hval) 148 ; 149 return elm; 150 } 151 152 public: clear()153 void clear () { delete[] t.tab; init (); } ~ihash_core()154 ~ihash_core () { delete[] t.tab; } deleteall()155 void deleteall () { 156 for (size_t i = 0; i < t.buckets; i++) 157 for (T *n = (T *) t.tab[i], *nn; n; n = nn) { 158 nn = (T *) (n->*field).next; 159 delete n; 160 } 161 clear (); 162 } size()163 size_t size () const { return t.entries; } constructed()164 bool constructed () const { return t.buckets > 0; } 165 remove(T * elm)166 void remove (T *elm) { 167 #if IHASH_DEBUG 168 if (ihash_do_debug () && !present (elm)) 169 panic ("ihash_core(%s)::remove: element not in hash table\n", 170 typeid (ihash_core).name ()); 171 #endif /* IHASH_DEBUG */ 172 _check (); 173 t.entries--; 174 if ((elm->*field).next) 175 (((T *) (elm->*field).next)->*field).pprev = (elm->*field).pprev; 176 *(elm->*field).pprev = (elm->*field).next; 177 } 178 first()179 T *first () const { 180 if (t.entries) 181 for (size_t i = 0; i < t.buckets; i++) 182 if (t.tab[i]) 183 return (T *) t.tab[i]; 184 return NULL; 185 } 186 next(const T * n)187 T *next (const T *n) const { 188 if ((n->*field).next) 189 return (T *) (n->*field).next; 190 for (size_t i = (n->*field).val % t.buckets; ++i < t.buckets;) 191 if (t.tab[i]) 192 return (T *) t.tab[i]; 193 return NULL; 194 } 195 traverse(typename callback<void,T * >::ref cb)196 void traverse (typename callback<void, T *>::ref cb) { 197 for (size_t i = 0; i < t.buckets; i++) 198 for (T *n = (T *) t.tab[i], *nn; n; n = nn) { 199 nn = (T *) (n->*field).next; 200 (*cb) (n); 201 } 202 } 203 traverse(typename callback<void,const T &>::ref cb)204 void traverse (typename callback<void, const T &>::ref cb) const { 205 for (size_t i = 0; i < t.buckets; i++) 206 for (T *n = (T *) t.tab[i], *nn; n; n = nn) { 207 nn = (T *) (n->*field).next; 208 (*cb) (*n); 209 } 210 } 211 traverse(void (T::* fn)())212 void traverse (void (T::*fn) ()) { 213 for (size_t i = 0; i < t.buckets; i++) 214 for (T *n = (T *) t.tab[i], *nn; n; n = nn) { 215 nn = (T *) (n->*field).next; 216 (n->*fn) (); 217 } 218 } 219 220 private: 221 /* No copying */ 222 ihash_core (const ihash_core &); 223 ihash_core &operator = (const ihash_core &); 224 }; 225 226 template<class K, class V, K V::*key, 227 ihash_entry<V> V::*field, class H = hashfn<K>, class E = equals<K> > 228 class ihash 229 : public ihash_core<V, field> 230 { 231 const E eq; 232 const H hash; 233 234 public: ihash()235 ihash () : eq (E ()), hash (H ()) {} ihash(const E & e,const H & h)236 ihash (const E &e, const H &h) : eq (e), hash (h) {} 237 insert(V * elm)238 void insert (V *elm) { ihash::insert_val (elm, hash (elm->*key)); } 239 240 #if 0 241 template<class T> V *operator[] (const T &k) const { 242 #else 243 V *operator[] (const K &k) const { 244 #endif 245 V *v; 246 for (v = this->lookup_val (hash (k)); 247 v && !eq (k, v->*key); 248 v = this->next_val (v)) 249 ; 250 return v; 251 } 252 nextkeq(V * v)253 V *nextkeq (V *v) { 254 const K &k = v->*key; 255 while ((v = this->next_val (v)) && !eq (k, v->*key)) 256 ; 257 return v; 258 }; 259 }; 260 261 template<class K1, class K2, class V, K1 V::*key1, K2 V::*key2, 262 ihash_entry<V> V::*field, class H = hash2fn<K1, K2>, 263 class E1 = equals<K1>, class E2 = equals<K2> > 264 class ihash2 265 : public ihash_core<V, field> 266 { 267 const E1 eq1; 268 const E2 eq2; 269 const H hash; 270 271 public: ihash2()272 ihash2 () {} ihash2(const E1 & e1,const E2 & e2,const H & h)273 ihash2 (const E1 &e1, const E2 &e2, const H &h) 274 : eq1 (e1), eq2 (e2), hash (h) {} 275 insert(V * elm)276 void insert (V *elm) 277 { insert_val (elm, hash (elm->*key1, elm->*key2)); } 278 operator()279 V *operator() (const K1 &k1, const K2 &k2) const { 280 V *v; 281 for (v = lookup_val (hash (k1, k2)); 282 v && !(eq1 (k1, v->*key1) && eq2 (k2, v->*key2)); 283 v = next_val (v)) 284 ; 285 return v; 286 } 287 nextkeq(V * v)288 V *nextkeq (V *v) { 289 const K1 &k1 = v->*key1; 290 const K1 &k2 = v->*key2; 291 while ((v = next_val (v)) 292 && !(eq1 (k1, v->*key1) && eq2 (k2, v->*key2))) 293 ; 294 return v; 295 }; 296 }; 297 298 template<class V, ihash_entry<V> V::*field, 299 class H = hashfn<V>, class E = equals<V> > 300 class shash 301 : public ihash_core<V, field> 302 { 303 const E eq; 304 const H hash; 305 306 public: shash()307 shash () {} shash(const E & e,const H & h)308 shash (const E &e, const H &h) : eq (e), hash (h) {} 309 insert(V * elm)310 void insert (V *elm) { insert_val (elm, hash (*elm)); } 311 312 V *operator[] (const V &k) const { 313 V *v; 314 for (v = lookup_val (hash (k)); 315 v && !eq (k, *v); 316 v = next_val (v)) 317 ; 318 return v; 319 } 320 nextkeq(V * v)321 V *nextkeq (V *v) { 322 const V &k = *v; 323 while ((v = next_val (v)) && !eq (k, *v)) 324 ; 325 return v; 326 } 327 }; 328 329 template<class V, class K> 330 struct keyfn { keyfnkeyfn331 keyfn () {} operatorkeyfn332 const K & operator() (V *v) const { assert (false); return K (); } 333 }; 334 335 template<class K, class V, ihash_entry<V> V::*field, 336 class F = keyfn<V, K>, class H = hashfn<K>, class E = equals<K> > 337 class fhash 338 : public ihash_core <V, field> 339 { 340 const E eq; 341 const H hash; 342 const F keyfn; 343 344 public: fhash()345 fhash () {} fhash(const E & e,const H & h,const F & k)346 fhash (const E &e, const H &h, const F &k) : eq (e), hash (h), keyfn (k) {} 347 insert(V * elm)348 void insert (V *elm) { insert_val (elm, hash (keyfn (elm))); } 349 350 V *operator[] (const K &k) const { 351 V *v; 352 for (v = lookup_val (hash (k)); 353 v && !eq (k, keyfn (v)); 354 v = next_val (v)) 355 ; 356 return v; 357 } nextkeq(V * v)358 V *nextkeq (V *v) { 359 const K &k = keyfn (v); 360 while ((v = next_val (v)) && !eq (k, keyfn (v))) 361 ; 362 return v; 363 } 364 }; 365 366 367 #endif /* !_IHASH_H_ */ 368