set.c 10.8 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/**
 * @file
 * @brief       implementation of set
 * @author      Markus Armbruster
Götz Lindenmaier's avatar
Götz Lindenmaier committed
24
 */
Christian Schäfer's avatar
Christian Schäfer committed
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/*  This code is derived from:

    From: ejp@ausmelb.oz.AU (Esmond Pitt)
    Date: Tue, 7 Mar 1989 22:06:26 GMT
    Subject: v06i042: dynamic hashing version of hsearch(3)
    Message-ID: <1821@basser.oz>
    Newsgroups: comp.sources.misc
    Sender: msgs@basser.oz

    Posting-number: Volume 6, Issue 42
    Submitted-By: Esmond Pitt <ejp@ausmelb.oz.AU>
    Archive-name: dynamic-hash

Sebastian Felis's avatar
Sebastian Felis committed
39
40
41
    * Dynamic hashing, after CACM April 1988 pp 446-457, by Per-Ake Larson.
    * Coded into C, with minor code improvements, and with hsearch(3) interface,
    * by ejp@ausmelb.oz, Jul 26, 1988: 13:16;
Christian Schäfer's avatar
Christian Schäfer committed
42
43
44

    TODO: Fix Esmond's ugly MixedCapsIdentifiers ;->
 */
Matthias Braun's avatar
Matthias Braun committed
45
#include "config.h"
Christian Schäfer's avatar
Christian Schäfer committed
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#ifdef PSET
# define SET pset
# define PMANGLE(pre) pre##_pset
# define MANGLEP(post) pset_##post
# define MANGLE(pre, post) pre##pset##post
# define EQUAL(cmp, elt, key, siz) (!(cmp) ((elt)->entry.dptr, (key)))
#else
# define SET set
# define PMANGLE(pre) pre##_set
# define MANGLEP(post) set_##post
# define MANGLE(pre, post) pre##set##post
# define EQUAL(cmp, elt, key, siz) \
    (((elt)->entry.size == (siz)) && !(cmp) ((elt)->entry.dptr, (key), (siz)))
#endif

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
66
#include "xmalloc.h"
67
#include "lc_printf.h"
Christian Schäfer's avatar
Christian Schäfer committed
68
69
70
71
72
73
#ifdef PSET
# include "pset.h"
#else
# include "set.h"
#endif

74

Christian Schäfer's avatar
Christian Schäfer committed
75
76
77
78
#define TOBSTACK_ID MANGLEP(tag)
#include "obst.h"


79
80
81
82
83
#define SEGMENT_SIZE_SHIFT   8
#define SEGMENT_SIZE         (1 << SEGMENT_SIZE_SHIFT)
#define DIRECTORY_SIZE_SHIFT 8
#define DIRECTORY_SIZE       (1 << DIRECTORY_SIZE_SHIFT)
#define MAX_LOAD_FACTOR      4
Christian Schäfer's avatar
Christian Schäfer committed
84
85
86


typedef struct element {
87
88
	struct element *chain;    /**< for chaining Elements */
	MANGLEP (entry) entry;
Christian Schäfer's avatar
Christian Schäfer committed
89
90
91
92
} Element, *Segment;


struct SET {
93
94
95
96
	size_t p;             /**< Next bucket to be split */
	size_t maxp;          /**< upper bound on p during expansion */
	size_t nkey;          /**< current # keys */
	size_t nseg;          /**< current # segments */
97
98
99
100
	Segment *dir[DIRECTORY_SIZE];
	MANGLEP(cmp_fun) cmp;     /**< function comparing entries */
	unsigned iter_i, iter_j;
	Element *iter_tail;       /**< non-NULL while iterating over elts */
Christian Schäfer's avatar
Christian Schäfer committed
101
#ifdef PSET
102
	Element *free_list;       /**< list of free Elements */
Christian Schäfer's avatar
Christian Schäfer committed
103
#endif
104
	struct obstack obst;      /**< obstack for allocation all data */
Christian Schäfer's avatar
Christian Schäfer committed
105
106
107
};


108
SET *(PMANGLE(new)) (MANGLEP(cmp_fun) cmp, size_t nslots)
Christian Schäfer's avatar
Christian Schäfer committed
109
{
110
111
	SET   *table = XMALLOC(SET);
	size_t i;
112
113
114
115
116
117
118
119

	if (nslots > SEGMENT_SIZE * DIRECTORY_SIZE)
		nslots = DIRECTORY_SIZE;
	else {
		/* Adjust nslots up to next power of 2, minimum SEGMENT_SIZE */
		for (i = SEGMENT_SIZE;  i < nslots;  i <<= 1) {
		}
		nslots = i >> SEGMENT_SIZE_SHIFT;
120
	}
Christian Schäfer's avatar
Christian Schäfer committed
121

122
123
124
125
	table->nseg = table->p = table->nkey = 0;
	table->maxp = nslots << SEGMENT_SIZE_SHIFT;
	table->cmp = cmp;
	table->iter_tail = NULL;
Christian Schäfer's avatar
Christian Schäfer committed
126
#ifdef PSET
127
	table->free_list = NULL;
Christian Schäfer's avatar
Christian Schäfer committed
128
#endif
129
	obstack_init (&table->obst);
Christian Schäfer's avatar
Christian Schäfer committed
130

131
132
133
134
135
	/* Make segments */
	for (i = 0;  i < nslots;  ++i) {
		table->dir[i] = OALLOCNZ(&table->obst, Segment, SEGMENT_SIZE);
		table->nseg++;
	}
Christian Schäfer's avatar
Christian Schäfer committed
136

137
	return table;
Christian Schäfer's avatar
Christian Schäfer committed
138
139
140
}


141
void PMANGLE(del) (SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
142
{
143
144
	obstack_free (&table->obst, NULL);
	xfree (table);
Christian Schäfer's avatar
Christian Schäfer committed
145
146
}

147
size_t MANGLEP(count) (SET *table)
Michael Beck's avatar
Michael Beck committed
148
{
149
	return table->nkey;
Michael Beck's avatar
Michael Beck committed
150
151
}

152
153
154
155
/*
 * do one iteration step, return 1
 * if still data in the set, 0 else
 */
156
static inline int iter_step(SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
157
{
158
159
160
161
162
163
164
165
	if (++table->iter_j >= SEGMENT_SIZE) {
		table->iter_j = 0;
		if (++table->iter_i >= table->nseg) {
			table->iter_i = 0;
			return 0;
		}
	}
	return 1;
Christian Schäfer's avatar
Christian Schäfer committed
166
167
}

168
169
170
/*
 * finds the first entry in the table
 */
171
void *(MANGLEP(first))(SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
172
{
173
174
175
176
177
178
179
180
181
	assert (!table->iter_tail);
	table->iter_i = 0;
	table->iter_j = 0;
	while (!table->dir[table->iter_i][table->iter_j]) {
		if (!iter_step (table)) return NULL;
	}
	table->iter_tail = table->dir[table->iter_i][table->iter_j];
	assert (table->iter_tail->entry.dptr);
	return table->iter_tail->entry.dptr;
Christian Schäfer's avatar
Christian Schäfer committed
182
183
}

184
185
186
/*
 * returns next entry in the table
 */
187
void *(MANGLEP(next))(SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
188
{
189
190
191
192
193
194
195
196
197
198
199
200
201
202
	if (!table->iter_tail)
		return NULL;

	/* follow collision chain */
	table->iter_tail = table->iter_tail->chain;
	if (!table->iter_tail) {
		/* go to next segment */
		do {
			if (!iter_step (table)) return NULL;
		} while (!table->dir[table->iter_i][table->iter_j]);
		table->iter_tail = table->dir[table->iter_i][table->iter_j];
	}
	assert (table->iter_tail->entry.dptr);
	return table->iter_tail->entry.dptr;
Christian Schäfer's avatar
Christian Schäfer committed
203
204
}

205
void MANGLEP(break) (SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
206
{
207
	table->iter_tail = NULL;
Christian Schäfer's avatar
Christian Schäfer committed
208
209
}

210
211
212
/*
 * limit the hash value
 */
213
static inline unsigned Hash(SET *table, unsigned h)
Christian Schäfer's avatar
Christian Schäfer committed
214
{
215
216
217
218
219
	unsigned address;
	address = h & (table->maxp - 1);          /* h % table->maxp */
	if (address < (unsigned)table->p)
		address = h & ((table->maxp << 1) - 1); /* h % (2*table->maxp) */
	return address;
Christian Schäfer's avatar
Christian Schäfer committed
220
221
}

222
223
224
225
/*
 * returns non-zero if the number of elements in
 * the set is greater then number of segments * MAX_LOAD_FACTOR
 */
226
static inline int loaded(SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
227
{
228
229
	return (  ++table->nkey
			> (table->nseg << SEGMENT_SIZE_SHIFT) * MAX_LOAD_FACTOR);
Christian Schäfer's avatar
Christian Schäfer committed
230
231
}

232
233
234
235
236
237
238
239
/*
 * expand the hash-table: the algorithm is split, so on every
 * insert, only ONE segment is rehashed!
 *
 * table->p contains the current segment to split
 * after all segments were split, table->p is set to zero and
 * table->maxp is duplicated.
 */
240
static void expand_table(SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
241
{
242
243
244
	size_t NewAddress;
	size_t OldSegmentIndex, NewSegmentIndex;
	size_t OldSegmentDir, NewSegmentDir;
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
	Segment *OldSegment;
	Segment *NewSegment;
	Element *Current;
	Element **Previous;
	Element **LastOfNew;

	if (table->maxp + table->p < (DIRECTORY_SIZE << SEGMENT_SIZE_SHIFT)) {
		/* Locate the bucket to be split */
		OldSegmentDir   = table->p >> SEGMENT_SIZE_SHIFT;
		OldSegment      = table->dir[OldSegmentDir];
		OldSegmentIndex = table->p & (SEGMENT_SIZE-1);

		/* Expand address space; if necessary create a new segment */
		NewAddress      = table->maxp + table->p;
		NewSegmentDir   = NewAddress >> SEGMENT_SIZE_SHIFT;
		NewSegmentIndex = NewAddress & (SEGMENT_SIZE-1);
		if (NewSegmentIndex == 0) {
			table->dir[NewSegmentDir] = OALLOCNZ(&table->obst, Segment, SEGMENT_SIZE);
			table->nseg++;
		}
		NewSegment = table->dir[NewSegmentDir];

		/* Adjust state variables */
		table->p++;
		if (table->p == table->maxp) {
			table->maxp <<= 1;  /* table->maxp *= 2 */
			table->p = 0;
		}

		/* Relocate records to the new bucket */
		Previous = &OldSegment[OldSegmentIndex];
		Current = *Previous;
		LastOfNew = &NewSegment[NewSegmentIndex];
		*LastOfNew = NULL;
		while (Current != NULL) {
			if (Hash (table, Current->entry.hash) == NewAddress) {
				/* move to new chain */
				*LastOfNew = Current;
				*Previous  = Current->chain;
				LastOfNew  = &Current->chain;
				Current    = Current->chain;
				*LastOfNew = NULL;
			} else {
				/* leave on old chain */
				Previous = &Current->chain;
				Current = Current->chain;
			}
		}
	}
Christian Schäfer's avatar
Christian Schäfer committed
294
295
296
}


297
void * MANGLE(_,_search) (SET *table,
298
		const void *key,
Christian Schäfer's avatar
Christian Schäfer committed
299
#ifndef PSET
300
		size_t size,
Christian Schäfer's avatar
Christian Schäfer committed
301
#endif
302
303
		unsigned hash,
		MANGLE(_,_action) action)
Christian Schäfer's avatar
Christian Schäfer committed
304
{
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
	unsigned h;
	Segment *CurrentSegment;
	int SegmentIndex;
	MANGLEP(cmp_fun) cmp = table->cmp;
	Segment q;

	assert (table);
	assert (key);

	/* Find collision chain */
	h = Hash (table, hash);
	SegmentIndex   = h & (SEGMENT_SIZE-1);
	CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
	assert (CurrentSegment != NULL);
	q = CurrentSegment[SegmentIndex];

	/* Follow collision chain */
	while (q && !EQUAL (cmp, q, key, size)) {
		q = q->chain;
	}
Christian Schäfer's avatar
Christian Schäfer committed
325

326
327
	if (!q && (action != MANGLE(_,_find))) { /* not found, insert */
		assert (!table->iter_tail && "insert an element into a set that is iterated");
328

Christian Schäfer's avatar
Christian Schäfer committed
329
#ifdef PSET
330
331
332
333
334
335
336
		if (table->free_list) {
			q = table->free_list;
			table->free_list = table->free_list->chain;
		} else {
			q = OALLOC(&table->obst, Element);
		}
		q->entry.dptr = (void *)key;
Christian Schäfer's avatar
Christian Schäfer committed
337
#else
338
339
340
341
342
		obstack_blank (&table->obst, offsetof (Element, entry.dptr));
		if (action == _set_hinsert0)
			obstack_grow0 (&table->obst, key, size);
		else
			obstack_grow (&table->obst, key, size);
343
		q = (Segment) obstack_finish (&table->obst);
344
		q->entry.size = size;
Christian Schäfer's avatar
Christian Schäfer committed
345
#endif
346
347
348
		q->chain = CurrentSegment[SegmentIndex];
		q->entry.hash = hash;
		CurrentSegment[SegmentIndex] = q;
Christian Schäfer's avatar
Christian Schäfer committed
349

350
351
352
353
		if (loaded (table)) {
			expand_table(table);    /* doesn't affect q */
		}
	}
Christian Schäfer's avatar
Christian Schäfer committed
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;
Christian Schäfer's avatar
Christian Schäfer committed
362
363
364
365
366
}


#ifdef PSET

367
368
369
370
371
int pset_default_ptr_cmp(const void *x, const void *y)
{
	return x != y;
}

372
void *pset_remove(SET *table, const void *key, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
373
{
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
	unsigned h;
	Segment *CurrentSegment;
	int SegmentIndex;
	pset_cmp_fun cmp = table->cmp;
	Segment *p;
	Segment q;

	assert (table && !table->iter_tail);

	/* Find collision chain */
	h = Hash (table, hash);
	SegmentIndex = h & (SEGMENT_SIZE-1);
	CurrentSegment = table->dir[h >> SEGMENT_SIZE_SHIFT];
	assert (CurrentSegment != NULL);
	p = &CurrentSegment[SegmentIndex];

	/* Follow collision chain */
	while (!EQUAL (cmp, *p, key, size)) {
		p = &(*p)->chain;
		assert (*p);
	}

	q = *p;

	if (q == table->iter_tail) {
		/* removing current element */
		table->iter_tail = q->chain;
		if (!table->iter_tail) {
			/* go to next segment */
			do {
				if (!iter_step (table))
					break;
			} while (!table->dir[table->iter_i][table->iter_j]);
			table->iter_tail = table->dir[table->iter_i][table->iter_j];
		}
	}

	*p = (*p)->chain;
	q->chain = table->free_list;
	table->free_list = q;
	--table->nkey;

	return q->entry.dptr;
Christian Schäfer's avatar
Christian Schäfer committed
417
418
419
}


420
void *(pset_find) (SET *se, const void *key, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
421
{
422
	return pset_find (se, key, hash);
Christian Schäfer's avatar
Christian Schäfer committed
423
424
425
}


426
void *(pset_insert) (SET *se, const void *key, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
427
{
428
	return pset_insert (se, key, hash);
Christian Schäfer's avatar
Christian Schäfer committed
429
430
431
}


432
	MANGLEP(entry) *
Christian Schäfer's avatar
Christian Schäfer committed
433
434
(pset_hinsert) (SET *se, const void *key, unsigned hash)
{
435
	return pset_hinsert (se, key, hash);
Christian Schäfer's avatar
Christian Schäfer committed
436
437
}

438
439
void pset_insert_pset_ptr(pset *target, pset *src)
{
440
	void *elt;
Christoph Mallon's avatar
Christoph Mallon committed
441
	foreach_pset(src, void*, elt) {
442
443
		pset_insert_ptr(target, elt);
	}
444
445
}

Christian Schäfer's avatar
Christian Schäfer committed
446
447
#else /* !PSET */

448
void *(set_find) (set *se, const void *key, size_t size, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
449
{
450
	return set_find(void, se, key, size, hash);
Christian Schäfer's avatar
Christian Schäfer committed
451
452
453
}


454
void *(set_insert) (set *se, const void *key, size_t size, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
455
{
456
	return set_insert(void, se, key, size, hash);
Christian Schäfer's avatar
Christian Schäfer committed
457
458
459
}


460
set_entry *(set_hinsert) (set *se, const void *key, size_t size, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
461
{
462
	return set_hinsert (se, key, size, hash);
Christian Schäfer's avatar
Christian Schäfer committed
463
464
465
}

#endif /* !PSET */