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