2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief implementation of set
23 * @author Markus Armbruster
26 /* This code is derived from:
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
35 Posting-number: Volume 6, Issue 42
36 Submitted-By: Esmond Pitt <ejp@ausmelb.oz.AU>
37 Archive-name: dynamic-hash
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;
43 TODO: Fix Esmond's ugly MixedCapsIdentifiers ;->
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)))
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)))
67 #include "lc_printf.h"
75 #define TOBSTACK_ID MANGLEP(tag)
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
86 typedef struct element {
87 struct element *chain; /**< for chaining Elements */
88 MANGLEP (entry) entry;
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 */
102 Element *free_list; /**< list of free Elements */
104 struct obstack obst; /**< obstack for allocation all data */
108 SET *(PMANGLE(new)) (MANGLEP(cmp_fun) cmp, size_t nslots)
110 SET *table = XMALLOC(SET);
113 if (nslots > SEGMENT_SIZE * DIRECTORY_SIZE)
114 nslots = DIRECTORY_SIZE;
116 /* Adjust nslots up to next power of 2, minimum SEGMENT_SIZE */
117 for (i = SEGMENT_SIZE; i < nslots; i <<= 1) {
119 nslots = i >> SEGMENT_SIZE_SHIFT;
122 table->nseg = table->p = table->nkey = 0;
123 table->maxp = nslots << SEGMENT_SIZE_SHIFT;
125 table->iter_tail = NULL;
127 table->free_list = NULL;
129 obstack_init (&table->obst);
132 for (i = 0; i < nslots; ++i) {
133 table->dir[i] = OALLOCNZ(&table->obst, Segment, SEGMENT_SIZE);
141 void PMANGLE(del) (SET *table)
143 obstack_free (&table->obst, NULL);
147 size_t MANGLEP(count) (SET *table)
153 * do one iteration step, return 1
154 * if still data in the set, 0 else
156 static inline int iter_step(SET *table)
158 if (++table->iter_j >= SEGMENT_SIZE) {
160 if (++table->iter_i >= table->nseg) {
169 * finds the first entry in the table
171 void *(MANGLEP(first))(SET *table)
173 assert (!table->iter_tail);
176 while (!table->dir[table->iter_i][table->iter_j]) {
177 if (!iter_step (table)) return NULL;
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;
185 * returns next entry in the table
187 void *(MANGLEP(next))(SET *table)
189 if (!table->iter_tail)
192 /* follow collision chain */
193 table->iter_tail = table->iter_tail->chain;
194 if (!table->iter_tail) {
195 /* go to next segment */
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];
201 assert (table->iter_tail->entry.dptr);
202 return table->iter_tail->entry.dptr;
205 void MANGLEP(break) (SET *table)
207 table->iter_tail = NULL;
211 * limit the hash value
213 static inline unsigned Hash(SET *table, unsigned h)
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) */
223 * returns non-zero if the number of elements in
224 * the set is greater then number of segments * MAX_LOAD_FACTOR
226 static inline int loaded(SET *table)
228 return ( ++table->nkey
229 > (table->nseg << SEGMENT_SIZE_SHIFT) * MAX_LOAD_FACTOR);
233 * expand the hash-table: the algorithm is split, so on every
234 * insert, only ONE segment is rehashed!
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.
240 static void expand_table(SET *table)
243 size_t OldSegmentIndex, NewSegmentIndex;
244 size_t OldSegmentDir, NewSegmentDir;
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);
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);
265 NewSegment = table->dir[NewSegmentDir];
267 /* Adjust state variables */
269 if (table->p == table->maxp) {
270 table->maxp <<= 1; /* table->maxp *= 2 */
274 /* Relocate records to the new bucket */
275 Previous = &OldSegment[OldSegmentIndex];
277 LastOfNew = &NewSegment[NewSegmentIndex];
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;
288 /* leave on old chain */
289 Previous = &Current->chain;
290 Current = Current->chain;
297 void * MANGLE(_,_search) (SET *table,
303 MANGLE(_,_action) action)
306 Segment *CurrentSegment;
308 MANGLEP(cmp_fun) cmp = table->cmp;
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];
321 /* Follow collision chain */
322 while (q && !EQUAL (cmp, q, key, size)) {
326 if (!q && (action != MANGLE(_,_find))) { /* not found, insert */
327 assert (!table->iter_tail && "insert an element into a set that is iterated");
330 if (table->free_list) {
331 q = table->free_list;
332 table->free_list = table->free_list->chain;
334 q = OALLOC(&table->obst, Element);
336 q->entry.dptr = (void *)key;
338 obstack_blank (&table->obst, offsetof (Element, entry.dptr));
339 if (action == _set_hinsert0)
340 obstack_grow0 (&table->obst, key, size);
342 obstack_grow (&table->obst, key, size);
343 q = (Segment) obstack_finish (&table->obst);
344 q->entry.size = size;
346 q->chain = CurrentSegment[SegmentIndex];
347 q->entry.hash = hash;
348 CurrentSegment[SegmentIndex] = q;
350 if (loaded (table)) {
351 expand_table(table); /* doesn't affect q */
357 if (action == _pset_hinsert) return &q->entry;
359 if (action == _set_hinsert || action == _set_hinsert0) return &q->entry;
361 return q->entry.dptr;
367 int pset_default_ptr_cmp(const void *x, const void *y)
372 void *pset_remove(SET *table, const void *key, unsigned hash)
375 Segment *CurrentSegment;
377 pset_cmp_fun cmp = table->cmp;
381 assert (table && !table->iter_tail);
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];
390 /* Follow collision chain */
391 while (!EQUAL (cmp, *p, key, size)) {
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 */
404 if (!iter_step (table))
406 } while (!table->dir[table->iter_i][table->iter_j]);
407 table->iter_tail = table->dir[table->iter_i][table->iter_j];
412 q->chain = table->free_list;
413 table->free_list = q;
416 return q->entry.dptr;
420 void *(pset_find) (SET *se, const void *key, unsigned hash)
422 return pset_find (se, key, hash);
426 void *(pset_insert) (SET *se, const void *key, unsigned hash)
428 return pset_insert (se, key, hash);
433 (pset_hinsert) (SET *se, const void *key, unsigned hash)
435 return pset_hinsert (se, key, hash);
438 void pset_insert_pset_ptr(pset *target, pset *src)
440 foreach_pset(src, void, elt) {
441 pset_insert_ptr(target, elt);
447 void *(set_find) (set *se, const void *key, size_t size, unsigned hash)
449 return set_find(void, se, key, size, hash);
453 void *(set_insert) (set *se, const void *key, size_t size, unsigned hash)
455 return set_insert(void, se, key, size, hash);
459 set_entry *(set_hinsert) (set *se, const void *key, size_t size, unsigned hash)
461 return set_hinsert (se, key, size, hash);