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] = OALLOCNZ(&table->obst, Segment, SEGMENT_SIZE);
 210     table->nseg++;
 211   }
 212
 213 #ifdef STATS
 214   table->naccess = table->ncollision = table->ndups = 0;
 215   table->max_chain_len = 0;
 216 #endif
 217 #ifdef DEBUG
 218   table->tag = MANGLEP(tag);
 219 #endif
 220   return table;
 221 }
 222
 223
 224 void
 225 PMANGLE(del) (SET *table)
 226 {
 227 #ifdef DEBUG
 228   MANGLEP(tag) = table->tag;
 229 #endif
 230   obstack_free (&table->obst, NULL);
 231   xfree (table);
 232 }
 233
 234 int
 235 MANGLEP(count) (SET *table)
 236 {
 237   return table->nkey;
 238 }
 239
 240 /*
 241  * do one iteration step, return 1
 242  * if still data in the set, 0 else
 243  */
 244 static inline int
 245 iter_step (SET *table)
 246 {
 247   if (++table->iter_j >= SEGMENT_SIZE) {
 248     table->iter_j = 0;
 249     if (++table->iter_i >= table->nseg) {
 250       table->iter_i = 0;
 251       return 0;
 252     }
 253   }
 254   return 1;
 255 }
 256
 257 /*
 258  * finds the first entry in the table
 259  */
 260 void *
 261 MANGLEP(first) (SET *table)
 262 {
 263   assert (!table->iter_tail);
 264   table->iter_i = 0;
 265   table->iter_j = 0;
 266   while (!table->dir[table->iter_i][table->iter_j]) {
 267     if (!iter_step (table)) return NULL;
 268   }
 269   table->iter_tail = table->dir[table->iter_i][table->iter_j];
 270   assert (table->iter_tail->entry.dptr);
 271   return table->iter_tail->entry.dptr;
 272 }
 273
 274 /*
 275  * returns next entry in the table
 276  */
 277 void *
 278 MANGLEP(next) (SET *table)
 279 {
 280   if (!table->iter_tail)
 281     return NULL;
 282
 283   /* follow collision chain */
 284   table->iter_tail = table->iter_tail->chain;
 285   if (!table->iter_tail) {
 286     /* go to next segment */
 287     do {
 288       if (!iter_step (table)) return NULL;
 289     } while (!table->dir[table->iter_i][table->iter_j]);
 290     table->iter_tail = table->dir[table->iter_i][table->iter_j];
 291   }
 292   assert (table->iter_tail->entry.dptr);
 293   return table->iter_tail->entry.dptr;
 294 }
 295
 296 void
 297 MANGLEP(break) (SET *table)
 298 {
 299   table->iter_tail = NULL;
 300 }
 301
 302 /*
 303  * limit the hash value
 304  */
 305 static inline unsigned
 306 Hash (SET *table, unsigned h)
 307 {
 308   unsigned address;
 309   address = h & (table->maxp - 1);          /* h % table->maxp */
 310   if (address < (unsigned)table->p)
 311     address = h & ((table->maxp << 1) - 1); /* h % (2*table->maxp) */
 312   return address;
 313 }
 314
 315 /*
 316  * returns non-zero if the number of elements in
 317  * the set is greater then number of segments * MAX_LOAD_FACTOR
 318  */
 319 static inline int
 320 loaded (SET *table)
 321 {
 322   return (  ++table->nkey
 323           > (table->nseg << SEGMENT_SIZE_SHIFT) * MAX_LOAD_FACTOR);
 324 }
 325
 326 /*
 327  * expand the hash-table: the algorithm is split, so on every
 328  * insert, only ONE segment is rehashed!
 329  *
 330  * table->p contains the current segment to split
 331  * after all segments were split, table->p is set to zero and
 332  * table->maxp is duplicated.
 333  */
 334 static void
 335 expand_table (SET *table)
 336 {
 337   unsigned NewAddress;
 338   int OldSegmentIndex, NewSegmentIndex;
 339   int OldSegmentDir, NewSegmentDir;
 340   Segment *OldSegment;
 341   Segment *NewSegment;
 342   Element *Current;
 343   Element **Previous;
 344   Element **LastOfNew;
 345
 346   if (table->maxp + table->p < (DIRECTORY_SIZE << SEGMENT_SIZE_SHIFT)) {
 347     /* Locate the bucket to be split */
 348     OldSegmentDir   = table->p >> SEGMENT_SIZE_SHIFT;
 349     OldSegment      = table->dir[OldSegmentDir];
 350     OldSegmentIndex = table->p & (SEGMENT_SIZE-1);
 351
 352     /* Expand address space; if necessary create a new segment */
 353     NewAddress      = table->maxp + table->p;
 354     NewSegmentDir   = NewAddress >> SEGMENT_SIZE_SHIFT;
 355     NewSegmentIndex = NewAddress & (SEGMENT_SIZE-1);
 356     if (NewSegmentIndex == 0) {
 357       table->dir[NewSegmentDir] = OALLOCNZ(&table->obst, Segment, SEGMENT_SIZE);
 358       table->nseg++;
 359     }
 360     NewSegment = table->dir[NewSegmentDir];
 361
 362     /* Adjust state variables */
 363     table->p++;
 364     if (table->p == table->maxp) {
 365       table->maxp <<= 1;        /* table->maxp *= 2     */
 366       table->p = 0;
 367     }
 368
 369     /* Relocate records to the new bucket */
 370     Previous = &OldSegment[OldSegmentIndex];
 371     Current = *Previous;
 372     LastOfNew = &NewSegment[NewSegmentIndex];
 373     *LastOfNew = NULL;
 374     while (Current != NULL) {
 375       if (Hash (table, Current->entry.hash) == NewAddress) {
 376         /* move to new chain */
 377         *LastOfNew = Current;
 378         *Previous  = Current->chain;
 379         LastOfNew  = &Current->chain;
 380         Current    = Current->chain;
 381         *LastOfNew = NULL;
 382       } else {
 383         /* leave on old chain */
 384         Previous = &Current->chain;
 385         Current = Current->chain;
 386       }
 387     }
 388   }
 389 }
 390
 391
 392 void *
 393 MANGLE(_,_search) (SET *table,
 394                    const void *key,
 395 #ifndef PSET
 396                    size_t size,
 397 #endif
 398                    unsigned hash,
 399                    MANGLE(_,_action) action)
 400 {
 401   unsigned h;
 402   Segment *CurrentSegment;
 403   int SegmentIndex;
 404   MANGLEP(cmp_fun) cmp = table->cmp;
 405   Segment q;
 406   int chain_len = 0;
 407
 408   assert (table);
 409   assert (key);
 410 #ifdef DEBUG
 411   MANGLEP(tag) = table->tag;
 412 #endif
 413   stat_access (table);
 414
 415   /* Find collision chain */
 416   h = Hash (table, hash);
 417   SegmentIndex   = h & (SEGMENT_SIZE-1);
 418   CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
 419   assert (CurrentSegment != NULL);
 420   q = CurrentSegment[SegmentIndex];
 421
 422   /* Follow collision chain */
 423   while (q && !EQUAL (cmp, q, key, size)) {
 424     q = q->chain;
 425     ++chain_len;
 426   }
 427
 428   stat_chain_len (table, chain_len);
 429
 430   if (!q && (action != MANGLE(_,_find))) { /* not found, insert */
 431     assert (!table->iter_tail && "insert an element into a set that is iterated");
 432
 433     if (CurrentSegment[SegmentIndex]) stat_dup (table);
 434
 435 #ifdef PSET
 436     if (table->free_list) {
 437       q = table->free_list;
 438       table->free_list = table->free_list->chain;
 439     } else {
 440       q = OALLOC(&table->obst, Element);
 441     }
 442     q->entry.dptr = (void *)key;
 443 #else
 444     obstack_blank (&table->obst, offsetof (Element, entry.dptr));
 445     if (action == _set_hinsert0)
 446       obstack_grow0 (&table->obst, key, size);
 447     else
 448       obstack_grow (&table->obst, key, size);
 449     q = obstack_finish (&table->obst);
 450     q->entry.size = size;
 451 #endif
 452     q->chain = CurrentSegment[SegmentIndex];
 453     q->entry.hash = hash;
 454     CurrentSegment[SegmentIndex] = q;
 455
 456     if (loaded (table)) {
 457       expand_table(table);      /* doesn't affect q */
 458     }
 459   }
 460
 461   if (!q) return NULL;
 462 #ifdef PSET
 463   if (action == _pset_hinsert) return &q->entry;
 464 #else
 465   if (action == _set_hinsert || action == _set_hinsert0) return &q->entry;
 466 #endif
 467   return q->entry.dptr;
 468 }
 469
 470
 471 #ifdef PSET
 472
 473 int pset_default_ptr_cmp(const void *x, const void *y)
 474 {
 475         return x != y;
 476 }
 477
 478 void *
 479 pset_remove (SET *table, const void *key, unsigned hash)
 480 {
 481   unsigned h;
 482   Segment *CurrentSegment;
 483   int SegmentIndex;
 484   pset_cmp_fun cmp = table->cmp;
 485   Segment *p;
 486   Segment q;
 487   int chain_len = 0;
 488
 489   assert (table && !table->iter_tail);
 490   stat_access (table);
 491
 492   /* Find collision chain */
 493   h = Hash (table, hash);
 494   SegmentIndex = h & (SEGMENT_SIZE-1);
 495   CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
 496   assert (CurrentSegment != NULL);
 497   p = &CurrentSegment[SegmentIndex];
 498
 499   /* Follow collision chain */
 500   while (!EQUAL (cmp, *p, key, size)) {
 501     p = &(*p)->chain;
 502     assert (*p);
 503     ++chain_len;
 504   }
 505
 506   stat_chain_len (table, chain_len);
 507
 508   q = *p;
 509
 510   if (q == table->iter_tail) {
 511     /* removing current element */
 512     table->iter_tail = q->chain;
 513     if (!table->iter_tail) {
 514       /* go to next segment */
 515       do {
 516         if (!iter_step (table))
 517           break;
 518       } while (!table->dir[table->iter_i][table->iter_j]);
 519       table->iter_tail = table->dir[table->iter_i][table->iter_j];
 520     }
 521   }
 522
 523   *p = (*p)->chain;
 524   q->chain = table->free_list;
 525   table->free_list = q;
 526   --table->nkey;
 527
 528   return q->entry.dptr;
 529 }
 530
 531
 532 void *
 533 (pset_find) (SET *se, const void *key, unsigned hash)
 534 {
 535   return pset_find (se, key, hash);
 536 }
 537
 538
 539 void *
 540 (pset_insert) (SET *se, const void *key, unsigned hash)
 541 {
 542   return pset_insert (se, key, hash);
 543 }
 544
 545
 546 MANGLEP(entry) *
 547 (pset_hinsert) (SET *se, const void *key, unsigned hash)
 548 {
 549   return pset_hinsert (se, key, hash);
 550 }
 551
 552 void pset_insert_pset_ptr(pset *target, pset *src)
 553 {
 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 */