nsz Git - libfirm/blob - ir/adt/set.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       implementation of set
  23  * @author      Markus Armbruster
  24  * @version     $Id$
  25  */
  26
  27 /*  This code is derived from:
  28
  29     From: ejp@ausmelb.oz.AU (Esmond Pitt)
  30     Date: Tue, 7 Mar 1989 22:06:26 GMT
  31     Subject: v06i042: dynamic hashing version of hsearch(3)
  32     Message-ID: <1821@basser.oz>
  33     Newsgroups: comp.sources.misc
  34     Sender: msgs@basser.oz
  35
  36     Posting-number: Volume 6, Issue 42
  37     Submitted-By: Esmond Pitt <ejp@ausmelb.oz.AU>
  38     Archive-name: dynamic-hash
  39
  40     * Dynamic hashing, after CACM April 1988 pp 446-457, by Per-Ake Larson.
  41     * Coded into C, with minor code improvements, and with hsearch(3) interface,
  42     * by ejp@ausmelb.oz, Jul 26, 1988: 13:16;
  43
  44     TODO: Fix Esmond's ugly MixedCapsIdentifiers ;->
  45  */
  46 #ifdef HAVE_CONFIG_H
  47 # include "config.h"
  48 #endif
  49
  50 #ifdef PSET
  51 # define SET pset
  52 # define PMANGLE(pre) pre##_pset
  53 # define MANGLEP(post) pset_##post
  54 # define MANGLE(pre, post) pre##pset##post
  55 # define EQUAL(cmp, elt, key, siz) (!(cmp) ((elt)->entry.dptr, (key)))
  56 #else
  57 # define SET set
  58 # define PMANGLE(pre) pre##_set
  59 # define MANGLEP(post) set_##post
  60 # define MANGLE(pre, post) pre##set##post
  61 # define EQUAL(cmp, elt, key, siz) \
  62     (((elt)->entry.size == (siz)) && !(cmp) ((elt)->entry.dptr, (key), (siz)))
  63 #endif
  64
  65 #include <assert.h>
  66 #include <stdlib.h>
  67 #include <stdio.h>
  68 #include <string.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;        /**< for chaining Elements */
  90   MANGLEP (entry) entry;
  91 } Element, *Segment;
  92
  93
  94 struct SET {
  95   unsigned p;                   /**< Next bucket to be split    */
  96   unsigned maxp;                /**< upper bound on p during expansion  */
  97   unsigned nkey;                /**< current # keys     */
  98   unsigned nseg;                /**< current # segments */
  99   Segment *dir[DIRECTORY_SIZE];
 100   MANGLEP(cmp_fun) cmp;         /**< function comparing entries */
 101   unsigned iter_i, iter_j;
 102   Element *iter_tail;           /**< non-NULL while iterating over elts */
 103 #ifdef PSET
 104   Element *free_list;           /**< list of free Elements */
 105 #endif
 106   struct obstack obst;          /**< obstack for allocation all data */
 107 #ifdef STATS
 108   int naccess, ncollision, ndups;
 109   int max_chain_len;
 110 #endif
 111 #ifdef DEBUG
 112   const char *tag;              /**< an optionally tag for distinguishing sets */
 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 void
 155 MANGLEP(describe) (SET *table)
 156 {
 157   unsigned i, j, collide;
 158   Element *ptr;
 159   Segment *seg;
 160
 161   printf ("p=%u maxp=%u nkey=%u nseg=%u\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, (void *)ptr->entry.dptr);
 172         ptr = ptr->chain;
 173         collide++;
 174       }
 175     }
 176   }
 177 #ifdef STATS
 178   MANGLEP(stats)(table);
 179 #endif
 180 }
 181
 182 #endif /* !DEBUG */
 183
 184
 185 SET *
 186 (PMANGLE(new)) (MANGLEP(cmp_fun) cmp, int nslots)
 187 {
 188   int i;
 189   SET *table = XMALLOC(SET);
 190
 191   if (nslots > SEGMENT_SIZE * DIRECTORY_SIZE)
 192     nslots = DIRECTORY_SIZE;
 193   else {
 194     assert (nslots >= 0);
 195     /* Adjust nslots up to next power of 2, minimum SEGMENT_SIZE */
 196     for (i = SEGMENT_SIZE;  i < nslots;  i <<= 1);
 197     nslots = i >> SEGMENT_SIZE_SHIFT;
 198   }
 199
 200   table->nseg = table->p = table->nkey = 0;
 201   table->maxp = nslots << SEGMENT_SIZE_SHIFT;
 202   table->cmp = cmp;
 203   table->iter_tail = NULL;
 204 #ifdef PSET
 205   table->free_list = NULL;
 206 #endif
 207   obstack_init (&table->obst);
 208
 209   /* Make segments */
 210   for (i = 0;  i < nslots;  ++i) {
 211     table->dir[i] = (Segment *)obstack_alloc (&table->obst,
 212                                               sizeof (Segment) * SEGMENT_SIZE);
 213
 214     memset(table->dir[i], 0, sizeof (Segment) * SEGMENT_SIZE);
 215     table->nseg++;
 216   }
 217
 218 #ifdef STATS
 219   table->naccess = table->ncollision = table->ndups = 0;
 220   table->max_chain_len = 0;
 221 #endif
 222 #ifdef DEBUG
 223   table->tag = MANGLEP(tag);
 224 #endif
 225   return table;
 226 }
 227
 228
 229 void
 230 PMANGLE(del) (SET *table)
 231 {
 232 #ifdef DEBUG
 233   MANGLEP(tag) = table->tag;
 234 #endif
 235   obstack_free (&table->obst, NULL);
 236   xfree (table);
 237 }
 238
 239 int
 240 MANGLEP(count) (SET *table)
 241 {
 242   return table->nkey;
 243 }
 244
 245 /*
 246  * do one iteration step, return 1
 247  * if still data in the set, 0 else
 248  */
 249 static INLINE int
 250 iter_step (SET *table)
 251 {
 252   if (++table->iter_j >= SEGMENT_SIZE) {
 253     table->iter_j = 0;
 254     if (++table->iter_i >= table->nseg) {
 255       table->iter_i = 0;
 256       return 0;
 257     }
 258   }
 259   return 1;
 260 }
 261
 262 /*
 263  * finds the first entry in the table
 264  */
 265 void *
 266 MANGLEP(first) (SET *table)
 267 {
 268   assert (!table->iter_tail);
 269   table->iter_i = 0;
 270   table->iter_j = 0;
 271   while (!table->dir[table->iter_i][table->iter_j]) {
 272     if (!iter_step (table)) return NULL;
 273   }
 274   table->iter_tail = table->dir[table->iter_i][table->iter_j];
 275   assert (table->iter_tail->entry.dptr);
 276   return table->iter_tail->entry.dptr;
 277 }
 278
 279 /*
 280  * returns next entry in the table
 281  */
 282 void *
 283 MANGLEP(next) (SET *table)
 284 {
 285   if (!table->iter_tail)
 286     return NULL;
 287
 288   /* follow collision chain */
 289   table->iter_tail = table->iter_tail->chain;
 290   if (!table->iter_tail) {
 291     /* go to next segment */
 292     do {
 293       if (!iter_step (table)) return NULL;
 294     } while (!table->dir[table->iter_i][table->iter_j]);
 295     table->iter_tail = table->dir[table->iter_i][table->iter_j];
 296   }
 297   assert (table->iter_tail->entry.dptr);
 298   return table->iter_tail->entry.dptr;
 299 }
 300
 301 void
 302 MANGLEP(break) (SET *table)
 303 {
 304   table->iter_tail = NULL;
 305 }
 306
 307 /*
 308  * limit the hash value
 309  */
 310 static INLINE unsigned
 311 Hash (SET *table, unsigned h)
 312 {
 313   unsigned address;
 314   address = h & (table->maxp - 1);          /* h % table->maxp */
 315   if (address < (unsigned)table->p)
 316     address = h & ((table->maxp << 1) - 1); /* h % (2*table->maxp) */
 317   return address;
 318 }
 319
 320 /*
 321  * returns non-zero if the number of elements in
 322  * the set is greater then number of segments * MAX_LOAD_FACTOR
 323  */
 324 static INLINE int
 325 loaded (SET *table)
 326 {
 327   return (  ++table->nkey
 328           > (table->nseg << SEGMENT_SIZE_SHIFT) * MAX_LOAD_FACTOR);
 329 }
 330
 331 /*
 332  * expand the hash-table: the algorithm is split, so on every
 333  * insert, only ONE segment is rehashed!
 334  *
 335  * table->p contains the current segment to split
 336  * after all segments were split, table->p is set to zero and
 337  * table->maxp is duplicated.
 338  */
 339 static void
 340 expand_table (SET *table)
 341 {
 342   unsigned NewAddress;
 343   int OldSegmentIndex, NewSegmentIndex;
 344   int OldSegmentDir, NewSegmentDir;
 345   Segment *OldSegment;
 346   Segment *NewSegment;
 347   Element *Current;
 348   Element **Previous;
 349   Element **LastOfNew;
 350
 351   if (table->maxp + table->p < (DIRECTORY_SIZE << SEGMENT_SIZE_SHIFT)) {
 352     /* Locate the bucket to be split */
 353     OldSegmentDir   = table->p >> SEGMENT_SIZE_SHIFT;
 354     OldSegment      = table->dir[OldSegmentDir];
 355     OldSegmentIndex = table->p & (SEGMENT_SIZE-1);
 356
 357     /* Expand address space; if necessary create a new segment */
 358     NewAddress      = table->maxp + table->p;
 359     NewSegmentDir   = NewAddress >> SEGMENT_SIZE_SHIFT;
 360     NewSegmentIndex = NewAddress & (SEGMENT_SIZE-1);
 361     if (NewSegmentIndex == 0) {
 362       table->dir[NewSegmentDir] =
 363         (Segment *)obstack_alloc (&table->obst,
 364                                   sizeof(Segment) * SEGMENT_SIZE);
 365       memset(table->dir[NewSegmentDir], 0, sizeof(Segment) * SEGMENT_SIZE);
 366       table->nseg++;
 367     }
 368     NewSegment = table->dir[NewSegmentDir];
 369
 370     /* Adjust state variables */
 371     table->p++;
 372     if (table->p == table->maxp) {
 373       table->maxp <<= 1;        /* table->maxp *= 2     */
 374       table->p = 0;
 375     }
 376
 377     /* Relocate records to the new bucket */
 378     Previous = &OldSegment[OldSegmentIndex];
 379     Current = *Previous;
 380     LastOfNew = &NewSegment[NewSegmentIndex];
 381     *LastOfNew = NULL;
 382     while (Current != NULL) {
 383       if (Hash (table, Current->entry.hash) == NewAddress) {
 384         /* move to new chain */
 385         *LastOfNew = Current;
 386         *Previous  = Current->chain;
 387         LastOfNew  = &Current->chain;
 388         Current    = Current->chain;
 389         *LastOfNew = NULL;
 390       } else {
 391         /* leave on old chain */
 392         Previous = &Current->chain;
 393         Current = Current->chain;
 394       }
 395     }
 396   }
 397 }
 398
 399
 400 void *
 401 MANGLE(_,_search) (SET *table,
 402                    const void *key,
 403 #ifndef PSET
 404                    size_t size,
 405 #endif
 406                    unsigned hash,
 407                    MANGLE(_,_action) action)
 408 {
 409   unsigned h;
 410   Segment *CurrentSegment;
 411   int SegmentIndex;
 412   MANGLEP(cmp_fun) cmp = table->cmp;
 413   Segment q;
 414   int chain_len = 0;
 415
 416   assert (table);
 417   assert (key);
 418 #ifdef DEBUG
 419   MANGLEP(tag) = table->tag;
 420 #endif
 421   stat_access (table);
 422
 423   /* Find collision chain */
 424   h = Hash (table, hash);
 425   SegmentIndex   = h & (SEGMENT_SIZE-1);
 426   CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
 427   assert (CurrentSegment != NULL);
 428   q = CurrentSegment[SegmentIndex];
 429
 430   /* Follow collision chain */
 431   while (q && !EQUAL (cmp, q, key, size)) {
 432     q = q->chain;
 433     ++chain_len;
 434   }
 435
 436   stat_chain_len (table, chain_len);
 437
 438   if (!q && (action != MANGLE(_,_find))) { /* not found, insert */
 439     assert (!table->iter_tail && "insert an element into a set that is iterated");
 440
 441     if (CurrentSegment[SegmentIndex]) stat_dup (table);
 442
 443 #ifdef PSET
 444     if (table->free_list) {
 445       q = table->free_list;
 446       table->free_list = table->free_list->chain;
 447     } else {
 448       q = obstack_alloc (&table->obst, sizeof (Element));
 449     }
 450     q->entry.dptr = (void *)key;
 451 #else
 452     obstack_blank (&table->obst, offsetof (Element, entry.dptr));
 453     if (action == _set_hinsert0)
 454       obstack_grow0 (&table->obst, key, size);
 455     else
 456       obstack_grow (&table->obst, key, size);
 457     q = obstack_finish (&table->obst);
 458     q->entry.size = size;
 459 #endif
 460     q->chain = CurrentSegment[SegmentIndex];
 461     q->entry.hash = hash;
 462     CurrentSegment[SegmentIndex] = q;
 463
 464     if (loaded (table)) {
 465       expand_table(table);      /* doesn't affect q */
 466     }
 467   }
 468
 469   if (!q) return NULL;
 470 #ifdef PSET
 471   if (action == _pset_hinsert) return &q->entry;
 472 #else
 473   if (action == _set_hinsert || action == _set_hinsert0) return &q->entry;
 474 #endif
 475   return q->entry.dptr;
 476 }
 477
 478
 479 #ifdef PSET
 480
 481 int pset_default_ptr_cmp(const void *x, const void *y)
 482 {
 483         return x != y;
 484 }
 485
 486 void *
 487 pset_remove (SET *table, const void *key, unsigned hash)
 488 {
 489   unsigned h;
 490   Segment *CurrentSegment;
 491   int SegmentIndex;
 492   pset_cmp_fun cmp = table->cmp;
 493   Segment *p;
 494   Segment q;
 495   int chain_len = 0;
 496
 497   assert (table && !table->iter_tail);
 498   stat_access (table);
 499
 500   /* Find collision chain */
 501   h = Hash (table, hash);
 502   SegmentIndex = h & (SEGMENT_SIZE-1);
 503   CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
 504   assert (CurrentSegment != NULL);
 505   p = &CurrentSegment[SegmentIndex];
 506
 507   /* Follow collision chain */
 508   while (!EQUAL (cmp, *p, key, size)) {
 509     p = &(*p)->chain;
 510     assert (*p);
 511     ++chain_len;
 512   }
 513
 514   stat_chain_len (table, chain_len);
 515
 516   q = *p;
 517
 518   if (q == table->iter_tail) {
 519     /* removing current element */
 520     table->iter_tail = q->chain;
 521     if (!table->iter_tail) {
 522       /* go to next segment */
 523       do {
 524         if (!iter_step (table))
 525           break;
 526       } while (!table->dir[table->iter_i][table->iter_j]);
 527       table->iter_tail = table->dir[table->iter_i][table->iter_j];
 528     }
 529   }
 530
 531   *p = (*p)->chain;
 532   q->chain = table->free_list;
 533   table->free_list = q;
 534   --table->nkey;
 535
 536   return q->entry.dptr;
 537 }
 538
 539
 540 void *
 541 (pset_find) (SET *se, const void *key, unsigned hash)
 542 {
 543   return pset_find (se, key, hash);
 544 }
 545
 546
 547 void *
 548 (pset_insert) (SET *se, const void *key, unsigned hash)
 549 {
 550   return pset_insert (se, key, hash);
 551 }
 552
 553
 554 MANGLEP(entry) *
 555 (pset_hinsert) (SET *se, const void *key, unsigned hash)
 556 {
 557   return pset_hinsert (se, key, hash);
 558 }
 559
 560 void pset_insert_pset_ptr(pset *target, pset *src) {
 561   void *elt;
 562   for (elt = pset_first(src); elt; elt = pset_next(src)) {
 563     pset_insert_ptr(target, elt);
 564   }
 565 }
 566
 567 #else /* !PSET */
 568
 569 void *
 570 (set_find) (set *se, const void *key, size_t size, unsigned hash)
 571 {
 572   return set_find (se, key, size, hash);
 573 }
 574
 575
 576 void *
 577 (set_insert) (set *se, const void *key, size_t size, unsigned hash)
 578 {
 579   return set_insert (se, key, size, hash);
 580 }
 581
 582
 583 set_entry *
 584 (set_hinsert) (set *se, const void *key, size_t size, unsigned hash)
 585 {
 586   return set_hinsert (se, key, size, hash);
 587 }
 588
 589 #endif /* !PSET */