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