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

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