set.c 13.2 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 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
24
 *
 * 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
 * @version     $Id$
Götz Lindenmaier's avatar
Götz Lindenmaier committed
25
 */
Christian Schäfer's avatar
Christian Schäfer committed
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/*  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
40
41
42
    * 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
43
44
45

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

#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>
67
#include "xmalloc.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
79
80
81
82
#define TOBSTACK_ID MANGLEP(tag)
#include "obst.h"


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


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


struct SET {
Michael Beck's avatar
Michael Beck committed
93
94
95
96
  unsigned p;			/**< Next bucket to be split	*/
  unsigned maxp;		/**< upper bound on p during expansion	*/
  unsigned nkey;		/**< current # keys	*/
  unsigned nseg;		/**< current # segments	*/
Christian Schäfer's avatar
Christian Schäfer committed
97
  Segment *dir[DIRECTORY_SIZE];
Michael Beck's avatar
Michael Beck committed
98
  MANGLEP(cmp_fun) cmp;		/**< function comparing entries */
99
  unsigned iter_i, iter_j;
Michael Beck's avatar
Michael Beck committed
100
  Element *iter_tail;		/**< non-NULL while iterating over elts */
Christian Schäfer's avatar
Christian Schäfer committed
101
#ifdef PSET
Michael Beck's avatar
Michael Beck committed
102
  Element *free_list;		/**< list of free Elements */
Christian Schäfer's avatar
Christian Schäfer committed
103
#endif
Michael Beck's avatar
Michael Beck committed
104
  struct obstack obst;		/**< obstack for allocation all data */
Christian Schäfer's avatar
Christian Schäfer committed
105
106
107
108
109
#ifdef STATS
  int naccess, ncollision, ndups;
  int max_chain_len;
#endif
#ifdef DEBUG
Michael Beck's avatar
Michael Beck committed
110
  const char *tag;              /**< an optionally tag for distinguishing sets */
Christian Schäfer's avatar
Christian Schäfer committed
111
112
113
114
115
116
#endif
};


#ifdef STATS

117
void MANGLEP(stats) (SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
118
119
120
121
122
123
124
125
126
127
{
  int nfree = 0;
#ifdef PSET
  Element *q = table->free_list;
  while (q) { q = q->chain; ++nfree; }
#endif
  printf ("     accesses  collisions        keys  duplicates     longest      wasted\n%12d%12d%12d%12d%12d%12d\n",
	  table->naccess, table->ncollision, table->nkey, table->ndups, table->max_chain_len, nfree);
}

128
static inline void stat_chain_len(SET *table, int chain_len)
Christian Schäfer's avatar
Christian Schäfer committed
129
130
131
132
133
134
135
136
137
138
{
  table->ncollision += chain_len;
  if (table->max_chain_len < chain_len) table->max_chain_len = chain_len;
}

# define stat_access(table) (++(table)->naccess)
# define stat_dup(table) (++(table)->ndups)

#else /* !STATS */

139
# define stat_chain_len(table, chain_len) ((void)chain_len)
Christian Schäfer's avatar
Christian Schäfer committed
140
141
142
143
144
145
146
147
148
149
# define stat_access(table) ((void)0)
# define stat_dup(table) ((void)0)

#endif /* !STATS */

#ifdef DEBUG

const char *MANGLEP(tag);


150
void MANGLEP(describe) (SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
151
{
152
  unsigned i, j, collide;
Christian Schäfer's avatar
Christian Schäfer committed
153
154
155
  Element *ptr;
  Segment *seg;

156
  printf ("p=%u maxp=%u nkey=%u nseg=%u\n",
Christian Schäfer's avatar
Christian Schäfer committed
157
158
159
160
161
162
163
164
165
	  table->p, table->maxp, table->nkey, table->nseg);
  for (i = 0;  i < table->nseg;  i++) {
    seg = table->dir[i];
    for (j = 0;  j < SEGMENT_SIZE;  j++) {
      collide = 0;
      ptr = seg[j];
      while (ptr) {
	if (collide) printf ("<%3d>", collide);
	else printf ("table");
Götz Lindenmaier's avatar
fix    
Götz Lindenmaier committed
166
	printf ("[%d][%3d]: %u %p\n", i, j, ptr->entry.hash, (void *)ptr->entry.dptr);
Christian Schäfer's avatar
Christian Schäfer committed
167
168
169
170
171
	ptr = ptr->chain;
	collide++;
      }
    }
  }
172
173
174
#ifdef STATS
  MANGLEP(stats)(table);
#endif
Christian Schäfer's avatar
Christian Schäfer committed
175
176
177
178
179
}

#endif /* !DEBUG */


180
SET *(PMANGLE(new)) (MANGLEP(cmp_fun) cmp, int nslots)
Christian Schäfer's avatar
Christian Schäfer committed
181
182
{
  int i;
183
  SET *table = XMALLOC(SET);
Christian Schäfer's avatar
Christian Schäfer committed
184

185
  if (nslots > SEGMENT_SIZE * DIRECTORY_SIZE)
Götz Lindenmaier's avatar
Götz Lindenmaier committed
186
    nslots = DIRECTORY_SIZE;
187
188
189
  else {
    assert (nslots >= 0);
    /* Adjust nslots up to next power of 2, minimum SEGMENT_SIZE */
190
191
    for (i = SEGMENT_SIZE;  i < nslots;  i <<= 1) {
	}
Götz Lindenmaier's avatar
fix    
Götz Lindenmaier committed
192
    nslots = i >> SEGMENT_SIZE_SHIFT;
193
  }
Christian Schäfer's avatar
Christian Schäfer committed
194
195
196
197
198
199
200
201
202
203
204
205

  table->nseg = table->p = table->nkey = 0;
  table->maxp = nslots << SEGMENT_SIZE_SHIFT;
  table->cmp = cmp;
  table->iter_tail = NULL;
#ifdef PSET
  table->free_list = NULL;
#endif
  obstack_init (&table->obst);

  /* Make segments */
  for (i = 0;  i < nslots;  ++i) {
206
    table->dir[i] = OALLOCNZ(&table->obst, Segment, SEGMENT_SIZE);
Christian Schäfer's avatar
Christian Schäfer committed
207
208
209
210
211
212
213
214
215
216
217
218
219
220
    table->nseg++;
  }

#ifdef STATS
  table->naccess = table->ncollision = table->ndups = 0;
  table->max_chain_len = 0;
#endif
#ifdef DEBUG
  table->tag = MANGLEP(tag);
#endif
  return table;
}


221
void PMANGLE(del) (SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
222
223
224
225
226
227
228
229
{
#ifdef DEBUG
  MANGLEP(tag) = table->tag;
#endif
  obstack_free (&table->obst, NULL);
  xfree (table);
}

230
int MANGLEP(count) (SET *table)
Michael Beck's avatar
Michael Beck committed
231
232
233
234
{
  return table->nkey;
}

235
236
237
238
/*
 * do one iteration step, return 1
 * if still data in the set, 0 else
 */
239
static inline int iter_step(SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
240
241
242
243
244
245
246
247
248
249
250
{
  if (++table->iter_j >= SEGMENT_SIZE) {
    table->iter_j = 0;
    if (++table->iter_i >= table->nseg) {
      table->iter_i = 0;
      return 0;
    }
  }
  return 1;
}

251
252
253
/*
 * finds the first entry in the table
 */
254
void * MANGLEP(first) (SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
255
256
257
258
259
260
261
262
263
264
265
266
{
  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;
}

267
268
269
/*
 * returns next entry in the table
 */
270
void *MANGLEP(next) (SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
271
{
Michael Beck's avatar
Michael Beck committed
272
273
  if (!table->iter_tail)
    return NULL;
274
275

  /* follow collision chain */
Christian Schäfer's avatar
Christian Schäfer committed
276
277
  table->iter_tail = table->iter_tail->chain;
  if (!table->iter_tail) {
278
    /* go to next segment */
Christian Schäfer's avatar
Christian Schäfer committed
279
280
281
282
283
284
285
286
287
    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;
}

288
void MANGLEP(break) (SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
289
290
291
292
{
  table->iter_tail = NULL;
}

293
294
295
/*
 * limit the hash value
 */
296
static inline unsigned Hash(SET *table, unsigned h)
Christian Schäfer's avatar
Christian Schäfer committed
297
298
{
  unsigned address;
299
  address = h & (table->maxp - 1);          /* h % table->maxp */
Christian Schäfer's avatar
Christian Schäfer committed
300
301
302
303
304
  if (address < (unsigned)table->p)
    address = h & ((table->maxp << 1) - 1); /* h % (2*table->maxp) */
  return address;
}

305
306
307
308
/*
 * returns non-zero if the number of elements in
 * the set is greater then number of segments * MAX_LOAD_FACTOR
 */
309
static inline int loaded(SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
310
311
312
313
314
{
  return (  ++table->nkey
	  > (table->nseg << SEGMENT_SIZE_SHIFT) * MAX_LOAD_FACTOR);
}

315
316
317
318
319
320
321
322
/*
 * 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.
 */
323
static void expand_table(SET *table)
Christian Schäfer's avatar
Christian Schäfer committed
324
325
326
327
328
329
330
331
332
333
334
335
{
  unsigned NewAddress;
  int OldSegmentIndex, NewSegmentIndex;
  int OldSegmentDir, NewSegmentDir;
  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 */
336
337
    OldSegmentDir   = table->p >> SEGMENT_SIZE_SHIFT;
    OldSegment      = table->dir[OldSegmentDir];
Christian Schäfer's avatar
Christian Schäfer committed
338
339
340
    OldSegmentIndex = table->p & (SEGMENT_SIZE-1);

    /* Expand address space; if necessary create a new segment */
341
342
    NewAddress      = table->maxp + table->p;
    NewSegmentDir   = NewAddress >> SEGMENT_SIZE_SHIFT;
Christian Schäfer's avatar
Christian Schäfer committed
343
344
    NewSegmentIndex = NewAddress & (SEGMENT_SIZE-1);
    if (NewSegmentIndex == 0) {
345
      table->dir[NewSegmentDir] = OALLOCNZ(&table->obst, Segment, SEGMENT_SIZE);
346
      table->nseg++;
Christian Schäfer's avatar
Christian Schäfer committed
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
    }
    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;
366
367
368
	*Previous  = Current->chain;
	LastOfNew  = &Current->chain;
	Current    = Current->chain;
Christian Schäfer's avatar
Christian Schäfer committed
369
370
371
372
373
374
375
376
377
378
379
	*LastOfNew = NULL;
      } else {
	/* leave on old chain */
	Previous = &Current->chain;
	Current = Current->chain;
      }
    }
  }
}


380
void * MANGLE(_,_search) (SET *table,
Christian Schäfer's avatar
Christian Schäfer committed
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
		   const void *key,
#ifndef PSET
		   size_t size,
#endif
		   unsigned hash,
		   MANGLE(_,_action) action)
{
  unsigned h;
  Segment *CurrentSegment;
  int SegmentIndex;
  MANGLEP(cmp_fun) cmp = table->cmp;
  Segment q;
  int chain_len = 0;

  assert (table);
  assert (key);
#ifdef DEBUG
  MANGLEP(tag) = table->tag;
#endif
  stat_access (table);

  /* Find collision chain */
  h = Hash (table, hash);
404
  SegmentIndex   = h & (SEGMENT_SIZE-1);
Christian Schäfer's avatar
Christian Schäfer committed
405
406
407
408
409
410
411
412
413
414
415
416
417
  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;
    ++chain_len;
  }

  stat_chain_len (table, chain_len);

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

Christian Schäfer's avatar
Christian Schäfer committed
420
421
422
423
424
425
426
    if (CurrentSegment[SegmentIndex]) stat_dup (table);

#ifdef PSET
    if (table->free_list) {
      q = table->free_list;
      table->free_list = table->free_list->chain;
    } else {
427
      q = OALLOC(&table->obst, Element);
Christian Schäfer's avatar
Christian Schäfer committed
428
429
430
431
    }
    q->entry.dptr = (void *)key;
#else
    obstack_blank (&table->obst, offsetof (Element, entry.dptr));
432
433
434
435
    if (action == _set_hinsert0)
      obstack_grow0 (&table->obst, key, size);
    else
      obstack_grow (&table->obst, key, size);
Christian Schäfer's avatar
Christian Schäfer committed
436
437
438
439
440
441
442
443
444
445
446
447
448
    q = obstack_finish (&table->obst);
    q->entry.size = size;
#endif
    q->chain = CurrentSegment[SegmentIndex];
    q->entry.hash = hash;
    CurrentSegment[SegmentIndex] = q;

    if (loaded (table)) {
      expand_table(table);	/* doesn't affect q */
    }
  }

  if (!q) return NULL;
449
450
451
452
453
#ifdef PSET
  if (action == _pset_hinsert) return &q->entry;
#else
  if (action == _set_hinsert || action == _set_hinsert0) return &q->entry;
#endif
Christian Schäfer's avatar
Christian Schäfer committed
454
455
456
457
458
459
  return q->entry.dptr;
}


#ifdef PSET

460
461
462
463
464
int pset_default_ptr_cmp(const void *x, const void *y)
{
	return x != y;
}

465
void *pset_remove(SET *table, const void *key, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
{
  unsigned h;
  Segment *CurrentSegment;
  int SegmentIndex;
  pset_cmp_fun cmp = table->cmp;
  Segment *p;
  Segment q;
  int chain_len = 0;

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

  /* 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);
    ++chain_len;
  }

  stat_chain_len (table, chain_len);

  q = *p;
Michael Beck's avatar
Michael Beck committed
495
496
497
498
499
500
501
502
503
504
505
506
507
508

  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];
    }
  }

Christian Schäfer's avatar
Christian Schäfer committed
509
510
511
  *p = (*p)->chain;
  q->chain = table->free_list;
  table->free_list = q;
Michael Beck's avatar
Michael Beck committed
512
  --table->nkey;
Christian Schäfer's avatar
Christian Schäfer committed
513
514
515
516
517

  return q->entry.dptr;
}


518
void *(pset_find) (SET *se, const void *key, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
519
520
521
522
523
{
  return pset_find (se, key, hash);
}


524
void *(pset_insert) (SET *se, const void *key, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
525
526
527
528
529
530
531
532
533
534
535
{
  return pset_insert (se, key, hash);
}


MANGLEP(entry) *
(pset_hinsert) (SET *se, const void *key, unsigned hash)
{
  return pset_hinsert (se, key, hash);
}

536
537
void pset_insert_pset_ptr(pset *target, pset *src)
{
538
539
540
541
542
543
  void *elt;
  for (elt = pset_first(src); elt; elt = pset_next(src)) {
    pset_insert_ptr(target, elt);
  }
}

Christian Schäfer's avatar
Christian Schäfer committed
544
545
#else /* !PSET */

546
void *(set_find) (set *se, const void *key, size_t size, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
547
548
549
550
551
{
  return set_find (se, key, size, hash);
}


552
void *(set_insert) (set *se, const void *key, size_t size, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
553
554
555
556
557
{
  return set_insert (se, key, size, hash);
}


558
set_entry *(set_hinsert) (set *se, const void *key, size_t size, unsigned hash)
Christian Schäfer's avatar
Christian Schäfer committed
559
560
561
562
563
{
  return set_hinsert (se, key, size, hash);
}

#endif /* !PSET */