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