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