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 int
 227 MANGLEP(count) (SET *table)
 228 {
 229   return table->nkey;
 230 }
 231
 232 /*
 233  * do one iteration step, return 1
 234  * if still data in the set, 0 else
 235  */
 236 static INLINE int
 237 iter_step (SET *table)
 238 {
 239   if (++table->iter_j >= SEGMENT_SIZE) {
 240     table->iter_j = 0;
 241     if (++table->iter_i >= table->nseg) {
 242       table->iter_i = 0;
 243       return 0;
 244     }
 245   }
 246   return 1;
 247 }
 248
 249 /*
 250  * finds the first entry in the table
 251  */
 252 void *
 253 MANGLEP(first) (SET *table)
 254 {
 255   assert (!table->iter_tail);
 256   table->iter_i = 0;
 257   table->iter_j = 0;
 258   while (!table->dir[table->iter_i][table->iter_j]) {
 259     if (!iter_step (table)) return NULL;
 260   }
 261   table->iter_tail = table->dir[table->iter_i][table->iter_j];
 262   assert (table->iter_tail->entry.dptr);
 263   return table->iter_tail->entry.dptr;
 264 }
 265
 266 /*
 267  * returns next entry in the table
 268  */
 269 void *
 270 MANGLEP(next) (SET *table)
 271 {
 272   if (!table->iter_tail)
 273     return NULL;
 274
 275   /* follow collision chain */
 276   table->iter_tail = table->iter_tail->chain;
 277   if (!table->iter_tail) {
 278     /* go to next segment */
 279     do {
 280       if (!iter_step (table)) return NULL;
 281     } while (!table->dir[table->iter_i][table->iter_j]);
 282     table->iter_tail = table->dir[table->iter_i][table->iter_j];
 283   }
 284   assert (table->iter_tail->entry.dptr);
 285   return table->iter_tail->entry.dptr;
 286 }
 287
 288 void
 289 MANGLEP(break) (SET *table)
 290 {
 291   table->iter_tail = NULL;
 292 }
 293
 294 /*
 295  * limit the hash value
 296  */
 297 static INLINE unsigned
 298 Hash (SET *table, unsigned h)
 299 {
 300   unsigned address;
 301
 302   address = h & (table->maxp - 1);          /* h % table->maxp */
 303   if (address < (unsigned)table->p)
 304     address = h & ((table->maxp << 1) - 1); /* h % (2*table->maxp) */
 305   return address;
 306 }
 307
 308 /*
 309  * returns non-zero if the number of elements in
 310  * the set is greater then number of segments * MAX_LOAD_FACTOR
 311  */
 312 static INLINE int
 313 loaded (SET *table)
 314 {
 315   return (  ++table->nkey
 316           > (table->nseg << SEGMENT_SIZE_SHIFT) * MAX_LOAD_FACTOR);
 317 }
 318
 319 /*
 320  * expand the hash-table: the algorithm is split, so on every
 321  * insert, only ONE segment is rehashed!
 322  *
 323  * table->p contains the current segment to split
 324  * after all segments were split, table->p is set to zero and
 325  * table->maxp is duplicated.
 326  */
 327 static void
 328 expand_table (SET *table)
 329 {
 330   unsigned NewAddress;
 331   int OldSegmentIndex, NewSegmentIndex;
 332   int OldSegmentDir, NewSegmentDir;
 333   Segment *OldSegment;
 334   Segment *NewSegment;
 335   Element *Current;
 336   Element **Previous;
 337   Element **LastOfNew;
 338
 339   if (table->maxp + table->p < (DIRECTORY_SIZE << SEGMENT_SIZE_SHIFT)) {
 340     /* Locate the bucket to be split */
 341     OldSegmentDir   = table->p >> SEGMENT_SIZE_SHIFT;
 342     OldSegment      = table->dir[OldSegmentDir];
 343     OldSegmentIndex = table->p & (SEGMENT_SIZE-1);
 344
 345     /* Expand address space; if necessary create a new segment */
 346     NewAddress      = table->maxp + table->p;
 347     NewSegmentDir   = NewAddress >> SEGMENT_SIZE_SHIFT;
 348     NewSegmentIndex = NewAddress & (SEGMENT_SIZE-1);
 349     if (NewSegmentIndex == 0) {
 350       table->dir[NewSegmentDir] =
 351         (Segment *)obstack_alloc (&table->obst,
 352                                   sizeof(Segment) * SEGMENT_SIZE);
 353       memset(table->dir[NewSegmentDir], 0, sizeof(Segment) * SEGMENT_SIZE);
 354     }
 355     NewSegment = table->dir[NewSegmentDir];
 356
 357     /* Adjust state variables */
 358     table->p++;
 359     if (table->p == table->maxp) {
 360       table->maxp <<= 1;        /* table->maxp *= 2     */
 361       table->p = 0;
 362     }
 363     table->nseg++;
 364
 365     /* Relocate records to the new bucket */
 366     Previous = &OldSegment[OldSegmentIndex];
 367     Current = *Previous;
 368     LastOfNew = &NewSegment[NewSegmentIndex];
 369     *LastOfNew = NULL;
 370     while (Current != NULL) {
 371       if (Hash (table, Current->entry.hash) == NewAddress) {
 372         /* move to new chain */
 373         *LastOfNew = Current;
 374         *Previous  = Current->chain;
 375         LastOfNew  = &Current->chain;
 376         Current    = Current->chain;
 377         *LastOfNew = NULL;
 378       } else {
 379         /* leave on old chain */
 380         Previous = &Current->chain;
 381         Current = Current->chain;
 382       }
 383     }
 384   }
 385 }
 386
 387
 388 void *
 389 MANGLE(_,_search) (SET *table,
 390                    const void *key,
 391 #ifndef PSET
 392                    size_t size,
 393 #endif
 394                    unsigned hash,
 395                    MANGLE(_,_action) action)
 396 {
 397   unsigned h;
 398   Segment *CurrentSegment;
 399   int SegmentIndex;
 400   MANGLEP(cmp_fun) cmp = table->cmp;
 401   Segment q;
 402   int chain_len = 0;
 403
 404   assert (table);
 405   assert (!table->iter_tail);
 406   assert (key);
 407 #ifdef DEBUG
 408   MANGLEP(tag) = table->tag;
 409 #endif
 410   stat_access (table);
 411
 412   /* Find collision chain */
 413   h = Hash (table, hash);
 414   SegmentIndex   = h & (SEGMENT_SIZE-1);
 415   CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
 416   assert (CurrentSegment != NULL);
 417   q = CurrentSegment[SegmentIndex];
 418
 419   /* Follow collision chain */
 420   while (q && !EQUAL (cmp, q, key, size)) {
 421     q = q->chain;
 422     ++chain_len;
 423   }
 424
 425   stat_chain_len (table, chain_len);
 426
 427   if (!q && (action != MANGLE(_,_find))) { /* not found, insert */
 428     if (CurrentSegment[SegmentIndex]) stat_dup (table);
 429
 430 #ifdef PSET
 431     if (table->free_list) {
 432       q = table->free_list;
 433       table->free_list = table->free_list->chain;
 434     } else {
 435       q = obstack_alloc (&table->obst, sizeof (Element));
 436     }
 437     q->entry.dptr = (void *)key;
 438 #else
 439     obstack_blank (&table->obst, offsetof (Element, entry.dptr));
 440     if (action == _set_hinsert0)
 441       obstack_grow0 (&table->obst, key, size);
 442     else
 443       obstack_grow (&table->obst, key, size);
 444     q = obstack_finish (&table->obst);
 445     q->entry.size = size;
 446 #endif
 447     q->chain = CurrentSegment[SegmentIndex];
 448     q->entry.hash = hash;
 449     CurrentSegment[SegmentIndex] = q;
 450
 451     if (loaded (table)) {
 452       expand_table(table);      /* doesn't affect q */
 453     }
 454   }
 455
 456   if (!q) return NULL;
 457 #ifdef PSET
 458   if (action == _pset_hinsert) return &q->entry;
 459 #else
 460   if (action == _set_hinsert || action == _set_hinsert0) return &q->entry;
 461 #endif
 462   return q->entry.dptr;
 463 }
 464
 465
 466 #ifdef PSET
 467
 468 void *
 469 pset_remove (SET *table, const void *key, unsigned hash)
 470 {
 471   unsigned h;
 472   Segment *CurrentSegment;
 473   int SegmentIndex;
 474   pset_cmp_fun cmp = table->cmp;
 475   Segment *p;
 476   Segment q;
 477   int chain_len = 0;
 478
 479   assert (table && !table->iter_tail);
 480   stat_access (table);
 481
 482   /* Find collision chain */
 483   h = Hash (table, hash);
 484   SegmentIndex = h & (SEGMENT_SIZE-1);
 485   CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
 486   assert (CurrentSegment != NULL);
 487   p = &CurrentSegment[SegmentIndex];
 488
 489   /* Follow collision chain */
 490   while (!EQUAL (cmp, *p, key, size)) {
 491     p = &(*p)->chain;
 492     assert (*p);
 493     ++chain_len;
 494   }
 495
 496   stat_chain_len (table, chain_len);
 497
 498   q = *p;
 499
 500   if (q == table->iter_tail) {
 501     /* removing current element */
 502     table->iter_tail = q->chain;
 503     if (!table->iter_tail) {
 504       /* go to next segment */
 505       do {
 506         if (!iter_step (table))
 507           break;
 508       } while (!table->dir[table->iter_i][table->iter_j]);
 509       table->iter_tail = table->dir[table->iter_i][table->iter_j];
 510     }
 511   }
 512
 513   *p = (*p)->chain;
 514   q->chain = table->free_list;
 515   table->free_list = q;
 516   --table->nkey;
 517
 518   return q->entry.dptr;
 519 }
 520
 521
 522 void *
 523 (pset_find) (SET *se, const void *key, unsigned hash)
 524 {
 525   return pset_find (se, key, hash);
 526 }
 527
 528
 529 void *
 530 (pset_insert) (SET *se, const void *key, unsigned hash)
 531 {
 532   return pset_insert (se, key, hash);
 533 }
 534
 535
 536 MANGLEP(entry) *
 537 (pset_hinsert) (SET *se, const void *key, unsigned hash)
 538 {
 539   return pset_hinsert (se, key, hash);
 540 }
 541
 542 #else /* !PSET */
 543
 544 void *
 545 (set_find) (set *se, const void *key, size_t size, unsigned hash)
 546 {
 547   return set_find (se, key, size, hash);
 548 }
 549
 550
 551 void *
 552 (set_insert) (set *se, const void *key, size_t size, unsigned hash)
 553 {
 554   return set_insert (se, key, size, hash);
 555 }
 556
 557
 558 set_entry *
 559 (set_hinsert) (set *se, const void *key, size_t size, unsigned hash)
 560 {
 561   return set_hinsert (se, key, size, hash);
 562 }
 563
 564 #endif /* !PSET */