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