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

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