nsz Git - libfirm/blob - ir/adt/set.c

   1 /* Set --- collection of entries that are unique wrt to a key.
   2    Copyright (C) 1995, 1996 Markus Armbruster */
   3
   4 /*  This code is derived from:
   5
   6     From: ejp@ausmelb.oz.AU (Esmond Pitt)
   7     Date: Tue, 7 Mar 1989 22:06:26 GMT
   8     Subject: v06i042: dynamic hashing version of hsearch(3)
   9     Message-ID: <1821@basser.oz>
  10     Newsgroups: comp.sources.misc
  11     Sender: msgs@basser.oz
  12
  13     Posting-number: Volume 6, Issue 42
  14     Submitted-By: Esmond Pitt <ejp@ausmelb.oz.AU>
  15     Archive-name: dynamic-hash
  16
  17     * Dynamic hashing, after CACM April 1988 pp 446-457, by Per-Ake Larson.
  18     * Coded into C, with minor code improvements, and with hsearch(3) interface,
  19     * by ejp@ausmelb.oz, Jul 26, 1988: 13:16;
  20
  21     TODO: Fix Esmond's ugly MixedCapsIdentifiers ;->
  22  */
  23
  24 /* $Id$ */
  25
  26 #ifdef HAVE_CONFIG_H
  27 # include <config.h>
  28 #endif
  29
  30 #ifdef USE_GCC_INLINE
  31 #define INLINE inline
  32 #else
  33 #define INLINE
  34 #endif
  35
  36 /* bcopy is not ISO C *
  37 #define bcopy(X, Y, Z) memcpy((Y), (X), (Z))
  38 */
  39
  40 #ifdef PSET
  41 # define SET pset
  42 # define PMANGLE(pre) pre##_pset
  43 # define MANGLEP(post) pset_##post
  44 # define MANGLE(pre, post) pre##pset##post
  45 # define EQUAL(cmp, elt, key, siz) (!(cmp) ((elt)->entry.dptr, (key)))
  46 #else
  47 # define SET set
  48 # define PMANGLE(pre) pre##_set
  49 # define MANGLEP(post) set_##post
  50 # define MANGLE(pre, post) pre##set##post
  51 # define EQUAL(cmp, elt, key, siz) \
  52     (((elt)->entry.size == (siz)) && !(cmp) ((elt)->entry.dptr, (key), (siz)))
  53 #endif
  54
  55 #include <assert.h>
  56 #include <stdlib.h>
  57 #include <stdio.h>
  58 #include <string.h>
  59 #include "misc.h"
  60 #ifdef PSET
  61 # include "pset.h"
  62 #else
  63 # include "set.h"
  64 #endif
  65
  66 #define TOBSTACK_ID MANGLEP(tag)
  67 #include "obst.h"
  68
  69
  70 #define SEGMENT_SIZE_SHIFT      8
  71 #define SEGMENT_SIZE            (1 << SEGMENT_SIZE_SHIFT)
  72 #define DIRECTORY_SIZE_SHIFT    8
  73 #define DIRECTORY_SIZE          (1 << DIRECTORY_SIZE_SHIFT)
  74 #define MAX_LOAD_FACTOR 4
  75
  76
  77 typedef struct element {
  78   struct element *chain;
  79   MANGLEP (entry) entry;
  80 } Element, *Segment;
  81
  82
  83 struct SET {
  84   short p;                      /* Next bucket to be split      */
  85   short maxp;                   /* upper bound on p during expansion    */
  86   int nkey;                     /* current # keys       */
  87   short nseg;                   /* current # segments   */
  88   Segment *dir[DIRECTORY_SIZE];
  89   MANGLEP(cmp_fun) cmp;         /* function comparing entries */
  90   int iter_i, iter_j;
  91   Element *iter_tail;           /* non-NULL while iterating over elts */
  92 #ifdef PSET
  93   Element *free_list;
  94 #endif
  95   struct obstack obst;
  96 #ifdef STATS
  97   int naccess, ncollision, ndups;
  98   int max_chain_len;
  99 #endif
 100 #ifdef DEBUG
 101   const char *tag;
 102 #endif
 103 };
 104
 105
 106 #ifdef STATS
 107
 108 void
 109 MANGLEP(stats) (SET *table)
 110 {
 111   int nfree = 0;
 112 #ifdef PSET
 113   Element *q = table->free_list;
 114   while (q) { q = q->chain; ++nfree; }
 115 #endif
 116   printf ("     accesses  collisions        keys  duplicates     longest      wasted\n%12d%12d%12d%12d%12d%12d\n",
 117           table->naccess, table->ncollision, table->nkey, table->ndups, table->max_chain_len, nfree);
 118 }
 119
 120 static INLINE void
 121 stat_chain_len (SET *table, int chain_len)
 122 {
 123   table->ncollision += chain_len;
 124   if (table->max_chain_len < chain_len) table->max_chain_len = chain_len;
 125 }
 126
 127 # define stat_access(table) (++(table)->naccess)
 128 # define stat_dup(table) (++(table)->ndups)
 129
 130 #else /* !STATS */
 131
 132 # define stat_chain_len(table, chain_len) ((void)0)
 133 # define stat_access(table) ((void)0)
 134 # define stat_dup(table) ((void)0)
 135
 136 #endif /* !STATS */
 137
 138 #ifdef DEBUG
 139
 140 const char *MANGLEP(tag);
 141
 142
 143 static void
 144 MANGLEP(describe) (SET *table)
 145 {
 146   int i, j, collide;
 147   Element *ptr;
 148   Segment *seg;
 149
 150   printf ("p=%d maxp=%d nkey=%d nseg=%d\n",
 151           table->p, table->maxp, table->nkey, table->nseg);
 152   for (i = 0;  i < table->nseg;  i++) {
 153     seg = table->dir[i];
 154     for (j = 0;  j < SEGMENT_SIZE;  j++) {
 155       collide = 0;
 156       ptr = seg[j];
 157       while (ptr) {
 158         if (collide) printf ("<%3d>", collide);
 159         else printf ("table");
 160         printf ("[%d][%3d]: %u %p\n", i, j, ptr->entry.hash, ptr->entry.dptr);
 161         ptr = ptr->chain;
 162         collide++;
 163       }
 164     }
 165   }
 166 }
 167
 168 #endif /* !DEBUG */
 169
 170
 171 SET *
 172 (PMANGLE(new)) (MANGLEP(cmp_fun) cmp, int nslots)
 173 {
 174   int i;
 175   SET *table = xmalloc (sizeof (SET));
 176
 177   /* Adjust nslots up to next power of 2, minimum SEGMENT_SIZE */
 178   assert (nslots >= 0);
 179   for (i = SEGMENT_SIZE;  i < nslots;  i <<= 1) assert (i < (i << 1));
 180   nslots = i >> SEGMENT_SIZE_SHIFT;
 181
 182   table->nseg = table->p = table->nkey = 0;
 183   table->maxp = nslots << SEGMENT_SIZE_SHIFT;
 184   table->cmp = cmp;
 185   table->iter_tail = NULL;
 186 #ifdef PSET
 187   table->free_list = NULL;
 188 #endif
 189   obstack_init (&table->obst);
 190
 191   /* Make segments */
 192   for (i = 0;  i < nslots;  ++i) {
 193     table->dir[i] = (Segment *)obstack_alloc (&table->obst,
 194                                               sizeof (Segment) * SEGMENT_SIZE);
 195
 196     memset (table->dir[i], 0, sizeof (Segment) * SEGMENT_SIZE);
 197     table->nseg++;
 198   }
 199
 200 #ifdef STATS
 201   table->naccess = table->ncollision = table->ndups = 0;
 202   table->max_chain_len = 0;
 203 #endif
 204 #ifdef DEBUG
 205   table->tag = MANGLEP(tag);
 206 #endif
 207   return table;
 208 }
 209
 210
 211 void
 212 PMANGLE(del) (SET *table)
 213 {
 214 #ifdef DEBUG
 215   MANGLEP(tag) = table->tag;
 216 #endif
 217   obstack_free (&table->obst, NULL);
 218   xfree (table);
 219 }
 220
 221
 222 static INLINE int
 223 iter_step (SET *table)
 224 {
 225   if (++table->iter_j >= SEGMENT_SIZE) {
 226     table->iter_j = 0;
 227     if (++table->iter_i >= table->nseg) {
 228       table->iter_i = 0;
 229       return 0;
 230     }
 231   }
 232   return 1;
 233 }
 234
 235
 236 void *
 237 MANGLEP(first) (SET *table)
 238 {
 239   assert (!table->iter_tail);
 240   table->iter_i = 0;
 241   table->iter_j = 0;
 242   while (!table->dir[table->iter_i][table->iter_j]) {
 243     if (!iter_step (table)) return NULL;
 244   }
 245   table->iter_tail = table->dir[table->iter_i][table->iter_j];
 246   assert (table->iter_tail->entry.dptr);
 247   return table->iter_tail->entry.dptr;
 248 }
 249
 250
 251 void *
 252 MANGLEP(next) (SET *table)
 253 {
 254   assert (table->iter_tail);
 255   table->iter_tail = table->iter_tail->chain;
 256   if (!table->iter_tail) {
 257     do {
 258       if (!iter_step (table)) return NULL;
 259     } while (!table->dir[table->iter_i][table->iter_j]);
 260     table->iter_tail = table->dir[table->iter_i][table->iter_j];
 261   }
 262   assert (table->iter_tail->entry.dptr);
 263   return table->iter_tail->entry.dptr;
 264 }
 265
 266 void
 267 MANGLEP(break) (SET *table)
 268 {
 269   assert (table->iter_tail);
 270   table->iter_tail = NULL;
 271 }
 272
 273
 274 static INLINE unsigned
 275 Hash (SET *table, unsigned h)
 276 {
 277   unsigned address;
 278
 279   address = h & (table->maxp - 1);
 280   if (address < (unsigned)table->p)
 281     address = h & ((table->maxp << 1) - 1); /* h % (2*table->maxp) */
 282   return address;
 283 }
 284
 285
 286 static INLINE int
 287 loaded (SET *table)
 288 {
 289   return (  ++table->nkey
 290           > (table->nseg << SEGMENT_SIZE_SHIFT) * MAX_LOAD_FACTOR);
 291 }
 292
 293
 294 static void
 295 expand_table (SET *table)
 296 {
 297   unsigned NewAddress;
 298   int OldSegmentIndex, NewSegmentIndex;
 299   int OldSegmentDir, NewSegmentDir;
 300   Segment *OldSegment;
 301   Segment *NewSegment;
 302   Element *Current;
 303   Element **Previous;
 304   Element **LastOfNew;
 305
 306   if (table->maxp + table->p < (DIRECTORY_SIZE << SEGMENT_SIZE_SHIFT)) {
 307     /* Locate the bucket to be split */
 308     OldSegmentDir = table->p >> SEGMENT_SIZE_SHIFT;
 309     OldSegment = table->dir[OldSegmentDir];
 310     OldSegmentIndex = table->p & (SEGMENT_SIZE-1);
 311
 312     /* Expand address space; if necessary create a new segment */
 313     NewAddress = table->maxp + table->p;
 314     NewSegmentDir = NewAddress >> SEGMENT_SIZE_SHIFT;
 315     NewSegmentIndex = NewAddress & (SEGMENT_SIZE-1);
 316     if (NewSegmentIndex == 0) {
 317       table->dir[NewSegmentDir] =
 318         (Segment *)obstack_alloc (&table->obst,
 319                                   sizeof(Segment) * SEGMENT_SIZE);
 320     }
 321     NewSegment = table->dir[NewSegmentDir];
 322
 323     /* Adjust state variables */
 324     table->p++;
 325     if (table->p == table->maxp) {
 326       table->maxp <<= 1;        /* table->maxp *= 2     */
 327       table->p = 0;
 328     }
 329     table->nseg++;
 330
 331     /* Relocate records to the new bucket */
 332     Previous = &OldSegment[OldSegmentIndex];
 333     Current = *Previous;
 334     LastOfNew = &NewSegment[NewSegmentIndex];
 335     *LastOfNew = NULL;
 336     while (Current != NULL) {
 337       if (Hash (table, Current->entry.hash) == NewAddress) {
 338         /* move to new chain */
 339         *LastOfNew = Current;
 340         *Previous = Current->chain;
 341         LastOfNew = &Current->chain;
 342         Current = Current->chain;
 343         *LastOfNew = NULL;
 344       } else {
 345         /* leave on old chain */
 346         Previous = &Current->chain;
 347         Current = Current->chain;
 348       }
 349     }
 350   }
 351 }
 352
 353
 354 void *
 355 MANGLE(_,_search) (SET *table,
 356                    const void *key,
 357 #ifndef PSET
 358                    size_t size,
 359 #endif
 360                    unsigned hash,
 361                    MANGLE(_,_action) action)
 362 {
 363   unsigned h;
 364   Segment *CurrentSegment;
 365   int SegmentIndex;
 366   MANGLEP(cmp_fun) cmp = table->cmp;
 367   Segment q;
 368   int chain_len = 0;
 369
 370   assert (table);
 371   assert (!table->iter_tail);
 372   assert (key);
 373 #ifdef DEBUG
 374   MANGLEP(tag) = table->tag;
 375 #endif
 376   stat_access (table);
 377
 378   /* Find collision chain */
 379   h = Hash (table, hash);
 380   SegmentIndex = h & (SEGMENT_SIZE-1);
 381   CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
 382   assert (CurrentSegment != NULL);
 383   q = CurrentSegment[SegmentIndex];
 384
 385   /* Follow collision chain */
 386   while (q && !EQUAL (cmp, q, key, size)) {
 387     q = q->chain;
 388     ++chain_len;
 389   }
 390
 391   stat_chain_len (table, chain_len);
 392
 393   if (!q && (action != MANGLE(_,_find))) { /* not found, insert */
 394     if (CurrentSegment[SegmentIndex]) stat_dup (table);
 395
 396 #ifdef PSET
 397     if (table->free_list) {
 398       q = table->free_list;
 399       table->free_list = table->free_list->chain;
 400     } else {
 401       q = obstack_alloc (&table->obst, sizeof (Element));
 402     }
 403     q->entry.dptr = (void *)key;
 404 #else
 405     obstack_blank (&table->obst, offsetof (Element, entry.dptr));
 406     if (action == _set_hinsert0)
 407       obstack_grow0 (&table->obst, key, size);
 408     else
 409       obstack_grow (&table->obst, key, size);
 410     q = obstack_finish (&table->obst);
 411     q->entry.size = size;
 412 #endif
 413     q->chain = CurrentSegment[SegmentIndex];
 414     q->entry.hash = hash;
 415     CurrentSegment[SegmentIndex] = q;
 416
 417     if (loaded (table)) {
 418       expand_table(table);      /* doesn't affect q */
 419     }
 420   }
 421
 422   if (!q) return NULL;
 423 #ifdef PSET
 424   if (action == _pset_hinsert) return &q->entry;
 425 #else
 426   if (action == _set_hinsert || action == _set_hinsert0) return &q->entry;
 427 #endif
 428   return q->entry.dptr;
 429 }
 430
 431
 432 #ifdef PSET
 433
 434 void *
 435 pset_remove (SET *table, const void *key, unsigned hash)
 436 {
 437   unsigned h;
 438   Segment *CurrentSegment;
 439   int SegmentIndex;
 440   pset_cmp_fun cmp = table->cmp;
 441   Segment *p;
 442   Segment q;
 443   int chain_len = 0;
 444
 445   assert (table && !table->iter_tail);
 446   stat_access (table);
 447
 448   /* Find collision chain */
 449   h = Hash (table, hash);
 450   SegmentIndex = h & (SEGMENT_SIZE-1);
 451   CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
 452   assert (CurrentSegment != NULL);
 453   p = &CurrentSegment[SegmentIndex];
 454
 455   /* Follow collision chain */
 456   while (!EQUAL (cmp, *p, key, size)) {
 457     p = &(*p)->chain;
 458     assert (*p);
 459     ++chain_len;
 460   }
 461
 462   stat_chain_len (table, chain_len);
 463
 464   q = *p;
 465   *p = (*p)->chain;
 466   q->chain = table->free_list;
 467   table->free_list = q;
 468
 469   return q->entry.dptr;
 470 }
 471
 472
 473 void *
 474 (pset_find) (SET *se, const void *key, unsigned hash)
 475 {
 476   return pset_find (se, key, hash);
 477 }
 478
 479
 480 void *
 481 (pset_insert) (SET *se, const void *key, unsigned hash)
 482 {
 483   return pset_insert (se, key, hash);
 484 }
 485
 486
 487 MANGLEP(entry) *
 488 (pset_hinsert) (SET *se, const void *key, unsigned hash)
 489 {
 490   return pset_hinsert (se, key, hash);
 491 }
 492
 493 #else /* !PSET */
 494
 495 void *
 496 (set_find) (set *se, const void *key, size_t size, unsigned hash)
 497 {
 498   return set_find (se, key, size, hash);
 499 }
 500
 501
 502 void *
 503 (set_insert) (set *se, const void *key, size_t size, unsigned hash)
 504 {
 505   return set_insert (se, key, size, hash);
 506 }
 507
 508
 509 set_entry *
 510 (set_hinsert) (set *se, const void *key, size_t size, unsigned hash)
 511 {
 512   return set_hinsert (se, key, size, hash);
 513 }
 514
 515 #endif /* !PSET */