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

   1 /*
   2  * Copyright (C) 1995-2011 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  */
  25
  26 /*  This code is derived from:
  27
  28     From: ejp@ausmelb.oz.AU (Esmond Pitt)
  29     Date: Tue, 7 Mar 1989 22:06:26 GMT
  30     Subject: v06i042: dynamic hashing version of hsearch(3)
  31     Message-ID: <1821@basser.oz>
  32     Newsgroups: comp.sources.misc
  33     Sender: msgs@basser.oz
  34
  35     Posting-number: Volume 6, Issue 42
  36     Submitted-By: Esmond Pitt <ejp@ausmelb.oz.AU>
  37     Archive-name: dynamic-hash
  38
  39     * Dynamic hashing, after CACM April 1988 pp 446-457, by Per-Ake Larson.
  40     * Coded into C, with minor code improvements, and with hsearch(3) interface,
  41     * by ejp@ausmelb.oz, Jul 26, 1988: 13:16;
  42
  43     TODO: Fix Esmond's ugly MixedCapsIdentifiers ;->
  44  */
  45 #include "config.h"
  46
  47 #ifdef PSET
  48 # define SET pset
  49 # define PMANGLE(pre) pre##_pset
  50 # define MANGLEP(post) pset_##post
  51 # define MANGLE(pre, post) pre##pset##post
  52 # define EQUAL(cmp, elt, key, siz) (!(cmp) ((elt)->entry.dptr, (key)))
  53 #else
  54 # define SET set
  55 # define PMANGLE(pre) pre##_set
  56 # define MANGLEP(post) set_##post
  57 # define MANGLE(pre, post) pre##set##post
  58 # define EQUAL(cmp, elt, key, siz) \
  59     (((elt)->entry.size == (siz)) && !(cmp) ((elt)->entry.dptr, (key), (siz)))
  60 #endif
  61
  62 #include <assert.h>
  63 #include <stdlib.h>
  64 #include <stdio.h>
  65 #include <string.h>
  66 #include "xmalloc.h"
  67 #include "lc_printf.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         size_t p;             /**< Next bucket to be split */
  94         size_t maxp;          /**< upper bound on p during expansion */
  95         size_t nkey;          /**< current # keys */
  96         size_t 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 };
 106
 107
 108 SET *(PMANGLE(new)) (MANGLEP(cmp_fun) cmp, size_t nslots)
 109 {
 110         SET   *table = XMALLOC(SET);
 111         size_t i;
 112
 113         if (nslots > SEGMENT_SIZE * DIRECTORY_SIZE)
 114                 nslots = DIRECTORY_SIZE;
 115         else {
 116                 /* Adjust nslots up to next power of 2, minimum SEGMENT_SIZE */
 117                 for (i = SEGMENT_SIZE;  i < nslots;  i <<= 1) {
 118                 }
 119                 nslots = i >> SEGMENT_SIZE_SHIFT;
 120         }
 121
 122         table->nseg = table->p = table->nkey = 0;
 123         table->maxp = nslots << SEGMENT_SIZE_SHIFT;
 124         table->cmp = cmp;
 125         table->iter_tail = NULL;
 126 #ifdef PSET
 127         table->free_list = NULL;
 128 #endif
 129         obstack_init (&table->obst);
 130
 131         /* Make segments */
 132         for (i = 0;  i < nslots;  ++i) {
 133                 table->dir[i] = OALLOCNZ(&table->obst, Segment, SEGMENT_SIZE);
 134                 table->nseg++;
 135         }
 136
 137         return table;
 138 }
 139
 140
 141 void PMANGLE(del) (SET *table)
 142 {
 143         obstack_free (&table->obst, NULL);
 144         xfree (table);
 145 }
 146
 147 size_t MANGLEP(count) (SET *table)
 148 {
 149         return table->nkey;
 150 }
 151
 152 /*
 153  * do one iteration step, return 1
 154  * if still data in the set, 0 else
 155  */
 156 static inline int iter_step(SET *table)
 157 {
 158         if (++table->iter_j >= SEGMENT_SIZE) {
 159                 table->iter_j = 0;
 160                 if (++table->iter_i >= table->nseg) {
 161                         table->iter_i = 0;
 162                         return 0;
 163                 }
 164         }
 165         return 1;
 166 }
 167
 168 /*
 169  * finds the first entry in the table
 170  */
 171 void *(MANGLEP(first))(SET *table)
 172 {
 173         assert (!table->iter_tail);
 174         table->iter_i = 0;
 175         table->iter_j = 0;
 176         while (!table->dir[table->iter_i][table->iter_j]) {
 177                 if (!iter_step (table)) return NULL;
 178         }
 179         table->iter_tail = table->dir[table->iter_i][table->iter_j];
 180         assert (table->iter_tail->entry.dptr);
 181         return table->iter_tail->entry.dptr;
 182 }
 183
 184 /*
 185  * returns next entry in the table
 186  */
 187 void *(MANGLEP(next))(SET *table)
 188 {
 189         if (!table->iter_tail)
 190                 return NULL;
 191
 192         /* follow collision chain */
 193         table->iter_tail = table->iter_tail->chain;
 194         if (!table->iter_tail) {
 195                 /* go to next segment */
 196                 do {
 197                         if (!iter_step (table)) return NULL;
 198                 } while (!table->dir[table->iter_i][table->iter_j]);
 199                 table->iter_tail = table->dir[table->iter_i][table->iter_j];
 200         }
 201         assert (table->iter_tail->entry.dptr);
 202         return table->iter_tail->entry.dptr;
 203 }
 204
 205 void MANGLEP(break) (SET *table)
 206 {
 207         table->iter_tail = NULL;
 208 }
 209
 210 /*
 211  * limit the hash value
 212  */
 213 static inline unsigned Hash(SET *table, unsigned h)
 214 {
 215         unsigned address;
 216         address = h & (table->maxp - 1);          /* h % table->maxp */
 217         if (address < (unsigned)table->p)
 218                 address = h & ((table->maxp << 1) - 1); /* h % (2*table->maxp) */
 219         return address;
 220 }
 221
 222 /*
 223  * returns non-zero if the number of elements in
 224  * the set is greater then number of segments * MAX_LOAD_FACTOR
 225  */
 226 static inline int loaded(SET *table)
 227 {
 228         return (  ++table->nkey
 229                         > (table->nseg << SEGMENT_SIZE_SHIFT) * MAX_LOAD_FACTOR);
 230 }
 231
 232 /*
 233  * expand the hash-table: the algorithm is split, so on every
 234  * insert, only ONE segment is rehashed!
 235  *
 236  * table->p contains the current segment to split
 237  * after all segments were split, table->p is set to zero and
 238  * table->maxp is duplicated.
 239  */
 240 static void expand_table(SET *table)
 241 {
 242         size_t NewAddress;
 243         size_t OldSegmentIndex, NewSegmentIndex;
 244         size_t OldSegmentDir, NewSegmentDir;
 245         Segment *OldSegment;
 246         Segment *NewSegment;
 247         Element *Current;
 248         Element **Previous;
 249         Element **LastOfNew;
 250
 251         if (table->maxp + table->p < (DIRECTORY_SIZE << SEGMENT_SIZE_SHIFT)) {
 252                 /* Locate the bucket to be split */
 253                 OldSegmentDir   = table->p >> SEGMENT_SIZE_SHIFT;
 254                 OldSegment      = table->dir[OldSegmentDir];
 255                 OldSegmentIndex = table->p & (SEGMENT_SIZE-1);
 256
 257                 /* Expand address space; if necessary create a new segment */
 258                 NewAddress      = table->maxp + table->p;
 259                 NewSegmentDir   = NewAddress >> SEGMENT_SIZE_SHIFT;
 260                 NewSegmentIndex = NewAddress & (SEGMENT_SIZE-1);
 261                 if (NewSegmentIndex == 0) {
 262                         table->dir[NewSegmentDir] = OALLOCNZ(&table->obst, Segment, SEGMENT_SIZE);
 263                         table->nseg++;
 264                 }
 265                 NewSegment = table->dir[NewSegmentDir];
 266
 267                 /* Adjust state variables */
 268                 table->p++;
 269                 if (table->p == table->maxp) {
 270                         table->maxp <<= 1;  /* table->maxp *= 2 */
 271                         table->p = 0;
 272                 }
 273
 274                 /* Relocate records to the new bucket */
 275                 Previous = &OldSegment[OldSegmentIndex];
 276                 Current = *Previous;
 277                 LastOfNew = &NewSegment[NewSegmentIndex];
 278                 *LastOfNew = NULL;
 279                 while (Current != NULL) {
 280                         if (Hash (table, Current->entry.hash) == NewAddress) {
 281                                 /* move to new chain */
 282                                 *LastOfNew = Current;
 283                                 *Previous  = Current->chain;
 284                                 LastOfNew  = &Current->chain;
 285                                 Current    = Current->chain;
 286                                 *LastOfNew = NULL;
 287                         } else {
 288                                 /* leave on old chain */
 289                                 Previous = &Current->chain;
 290                                 Current = Current->chain;
 291                         }
 292                 }
 293         }
 294 }
 295
 296
 297 void * MANGLE(_,_search) (SET *table,
 298                 const void *key,
 299 #ifndef PSET
 300                 size_t size,
 301 #endif
 302                 unsigned hash,
 303                 MANGLE(_,_action) action)
 304 {
 305         unsigned h;
 306         Segment *CurrentSegment;
 307         int SegmentIndex;
 308         MANGLEP(cmp_fun) cmp = table->cmp;
 309         Segment q;
 310
 311         assert (table);
 312         assert (key);
 313
 314         /* Find collision chain */
 315         h = Hash (table, hash);
 316         SegmentIndex   = h & (SEGMENT_SIZE-1);
 317         CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
 318         assert (CurrentSegment != NULL);
 319         q = CurrentSegment[SegmentIndex];
 320
 321         /* Follow collision chain */
 322         while (q && !EQUAL (cmp, q, key, size)) {
 323                 q = q->chain;
 324         }
 325
 326         if (!q && (action != MANGLE(_,_find))) { /* not found, insert */
 327                 assert (!table->iter_tail && "insert an element into a set that is iterated");
 328
 329 #ifdef PSET
 330                 if (table->free_list) {
 331                         q = table->free_list;
 332                         table->free_list = table->free_list->chain;
 333                 } else {
 334                         q = OALLOC(&table->obst, Element);
 335                 }
 336                 q->entry.dptr = (void *)key;
 337 #else
 338                 obstack_blank (&table->obst, offsetof (Element, entry.dptr));
 339                 if (action == _set_hinsert0)
 340                         obstack_grow0 (&table->obst, key, size);
 341                 else
 342                         obstack_grow (&table->obst, key, size);
 343                 q = (Segment) obstack_finish (&table->obst);
 344                 q->entry.size = size;
 345 #endif
 346                 q->chain = CurrentSegment[SegmentIndex];
 347                 q->entry.hash = hash;
 348                 CurrentSegment[SegmentIndex] = q;
 349
 350                 if (loaded (table)) {
 351                         expand_table(table);    /* doesn't affect q */
 352                 }
 353         }
 354
 355         if (!q) return NULL;
 356 #ifdef PSET
 357         if (action == _pset_hinsert) return &q->entry;
 358 #else
 359         if (action == _set_hinsert || action == _set_hinsert0) return &q->entry;
 360 #endif
 361         return q->entry.dptr;
 362 }
 363
 364
 365 #ifdef PSET
 366
 367 int pset_default_ptr_cmp(const void *x, const void *y)
 368 {
 369         return x != y;
 370 }
 371
 372 void *pset_remove(SET *table, const void *key, unsigned hash)
 373 {
 374         unsigned h;
 375         Segment *CurrentSegment;
 376         int SegmentIndex;
 377         pset_cmp_fun cmp = table->cmp;
 378         Segment *p;
 379         Segment q;
 380
 381         assert (table && !table->iter_tail);
 382
 383         /* Find collision chain */
 384         h = Hash (table, hash);
 385         SegmentIndex = h & (SEGMENT_SIZE-1);
 386         CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
 387         assert (CurrentSegment != NULL);
 388         p = &CurrentSegment[SegmentIndex];
 389
 390         /* Follow collision chain */
 391         while (!EQUAL (cmp, *p, key, size)) {
 392                 p = &(*p)->chain;
 393                 assert (*p);
 394         }
 395
 396         q = *p;
 397
 398         if (q == table->iter_tail) {
 399                 /* removing current element */
 400                 table->iter_tail = q->chain;
 401                 if (!table->iter_tail) {
 402                         /* go to next segment */
 403                         do {
 404                                 if (!iter_step (table))
 405                                         break;
 406                         } while (!table->dir[table->iter_i][table->iter_j]);
 407                         table->iter_tail = table->dir[table->iter_i][table->iter_j];
 408                 }
 409         }
 410
 411         *p = (*p)->chain;
 412         q->chain = table->free_list;
 413         table->free_list = q;
 414         --table->nkey;
 415
 416         return q->entry.dptr;
 417 }
 418
 419
 420 void *(pset_find) (SET *se, const void *key, unsigned hash)
 421 {
 422         return pset_find (se, key, hash);
 423 }
 424
 425
 426 void *(pset_insert) (SET *se, const void *key, unsigned hash)
 427 {
 428         return pset_insert (se, key, hash);
 429 }
 430
 431
 432         MANGLEP(entry) *
 433 (pset_hinsert) (SET *se, const void *key, unsigned hash)
 434 {
 435         return pset_hinsert (se, key, hash);
 436 }
 437
 438 void pset_insert_pset_ptr(pset *target, pset *src)
 439 {
 440         foreach_pset(src, void, elt) {
 441                 pset_insert_ptr(target, elt);
 442         }
 443 }
 444
 445 #else /* !PSET */
 446
 447 void *(set_find) (set *se, const void *key, size_t size, unsigned hash)
 448 {
 449         return set_find(void, se, key, size, hash);
 450 }
 451
 452
 453 void *(set_insert) (set *se, const void *key, size_t size, unsigned hash)
 454 {
 455         return set_insert(void, se, key, size, hash);
 456 }
 457
 458
 459 set_entry *(set_hinsert) (set *se, const void *key, size_t size, unsigned hash)
 460 {
 461         return set_hinsert (se, key, size, hash);
 462 }
 463
 464 #endif /* !PSET */