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