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