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