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