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