← Back to branch summary

~stub/ubuntu/trusty/avro-c/trunk

« back to all changes in this revision

Viewing changes to src/st.c

  • Committer: Stuart Bishop
  • Date: 2015-05-14 11:53:53 UTC
  • Revision ID: stuart@stuartbishop.net-20150514115353-0cvnrcyohcq5l7yj
Tags: upstream-1.7.7
Import upstream version 1.7.7

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/st.c
 
1
/*
 
2
 * This is a public domain general purpose hash table package written by
 
3
 * Peter Moore @ UCB. 
 
4
 */
 
5
 
 
6
/*
 
7
 * static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; 
 
8
 */
 
9
 
 
10
#include "avro_private.h"
 
11
#include "avro/allocation.h"
 
12
#include <stdio.h>
 
13
#include <stdlib.h>
 
14
#include <string.h>
 
15
 
 
16
#include "st.h"
 
17
 
 
18
typedef struct st_table_entry st_table_entry;
 
19
 
 
20
struct st_table_entry {
 
21
        unsigned int hash;
 
22
        st_data_t key;
 
23
        st_data_t record;
 
24
        st_table_entry *next;
 
25
};
 
26
 
 
27
#define ST_DEFAULT_MAX_DENSITY 5
 
28
#define ST_DEFAULT_INIT_TABLE_SIZE 11
 
29
 
 
30
        /*
 
31
         * DEFAULT_MAX_DENSITY is the default for the largest we allow the
 
32
         * average number of items per bin before increasing the number of
 
33
         * bins
 
34
         *
 
35
         * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
 
36
         * allocated initially
 
37
         *
 
38
         */
 
39
static int numcmp(long, long);
 
40
static int numhash(long);
 
41
static struct st_hash_type type_numhash = {
 
42
        HASH_FUNCTION_CAST numcmp,
 
43
        HASH_FUNCTION_CAST numhash
 
44
};
 
45
 
 
46
/*
 
47
 * extern int strcmp(const char *, const char *); 
 
48
 */
 
49
static int strhash(const char *);
 
50
static struct st_hash_type type_strhash = {
 
51
        HASH_FUNCTION_CAST strcmp,
 
52
        HASH_FUNCTION_CAST strhash
 
53
};
 
54
 
 
55
static void rehash(st_table *);
 
56
 
 
57
#ifdef RUBY
 
58
#define malloc xmalloc
 
59
#define calloc xcalloc
 
60
#endif
 
61
 
 
62
#define Calloc(n,s) (char*)avro_calloc((n),(s))
 
63
 
 
64
#define free_bins(tbl)  \
 
65
        avro_free(tbl->bins, tbl->num_bins * sizeof(st_table_entry *))
 
66
 
 
67
#define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
 
68
 
 
69
#define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
 
70
#define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)
 
71
 
 
72
/*
 
73
 * MINSIZE is the minimum size of a dictionary.
 
74
 */
 
75
 
 
76
#define MINSIZE 8
 
77
 
 
78
/*
 
79
 * Table of prime numbers 2^n+a, 2<=n<=30. 
 
80
 */
 
81
static long primes[] = {
 
82
        8 + 3,
 
83
        16 + 3,
 
84
        32 + 5,
 
85
        64 + 3,
 
86
        128 + 3,
 
87
        256 + 27,
 
88
        512 + 9,
 
89
        1024 + 9,
 
90
        2048 + 5,
 
91
        4096 + 3,
 
92
        8192 + 27,
 
93
        16384 + 43,
 
94
        32768 + 3,
 
95
        65536 + 45,
 
96
        131072 + 29,
 
97
        262144 + 3,
 
98
        524288 + 21,
 
99
        1048576 + 7,
 
100
        2097152 + 17,
 
101
        4194304 + 15,
 
102
        8388608 + 9,
 
103
        16777216 + 43,
 
104
        33554432 + 35,
 
105
        67108864 + 15,
 
106
        134217728 + 29,
 
107
        268435456 + 3,
 
108
        536870912 + 11,
 
109
        1073741824 + 85,
 
110
        0
 
111
};
 
112
 
 
113
static int new_size(int size)
 
114
{
 
115
        unsigned int i;
 
116
 
 
117
#if 0
 
118
        for (i = 3; i < 31; i++) {
 
119
                if ((1 << i) > size)
 
120
                        return 1 << i;
 
121
        }
 
122
        return -1;
 
123
#else
 
124
        int newsize;
 
125
 
 
126
        for (i = 0, newsize = MINSIZE;
 
127
             i < sizeof(primes) / sizeof(primes[0]); i++, newsize <<= 1) {
 
128
                if (newsize > size)
 
129
                        return primes[i];
 
130
        }
 
131
        /*
 
132
         * Ran out of polynomials 
 
133
         */
 
134
        return -1;              /* should raise exception */
 
135
#endif
 
136
}
 
137
 
 
138
#ifdef HASH_LOG
 
139
static int collision = 0;
 
140
static int init_st = 0;
 
141
 
 
142
static void stat_col()
 
143
{
 
144
        FILE *f = fopen("/tmp/col", "w");
 
145
        fprintf(f, "collision: %d\n", collision);
 
146
        fclose(f);
 
147
}
 
148
#endif
 
149
 
 
150
st_table *st_init_table_with_size(struct st_hash_type *type, int size)
 
151
{
 
152
        st_table *tbl;
 
153
 
 
154
#ifdef HASH_LOG
 
155
        if (init_st == 0) {
 
156
                init_st = 1;
 
157
                atexit(stat_col);
 
158
        }
 
159
#endif
 
160
 
 
161
        size = new_size(size);  /* round up to prime number */
 
162
 
 
163
        tbl = (st_table *) avro_new(st_table);
 
164
        tbl->type = type;
 
165
        tbl->num_entries = 0;
 
166
        tbl->num_bins = size;
 
167
        tbl->bins = (st_table_entry **) Calloc(size, sizeof(st_table_entry *));
 
168
 
 
169
        return tbl;
 
170
}
 
171
 
 
172
st_table *st_init_table(struct st_hash_type *type)
 
173
{
 
174
        return st_init_table_with_size(type, 0);
 
175
}
 
176
 
 
177
st_table *st_init_numtable(void)
 
178
{
 
179
        return st_init_table(&type_numhash);
 
180
}
 
181
 
 
182
st_table *st_init_numtable_with_size(int size)
 
183
{
 
184
        return st_init_table_with_size(&type_numhash, size);
 
185
}
 
186
 
 
187
st_table *st_init_strtable(void)
 
188
{
 
189
        return st_init_table(&type_strhash);
 
190
}
 
191
 
 
192
st_table *st_init_strtable_with_size(int size)
 
193
{
 
194
        return st_init_table_with_size(&type_strhash, size);
 
195
}
 
196
 
 
197
void st_free_table(st_table *table)
 
198
{
 
199
        register st_table_entry *ptr, *next;
 
200
        int i;
 
201
 
 
202
        for (i = 0; i < table->num_bins; i++) {
 
203
                ptr = table->bins[i];
 
204
                while (ptr != 0) {
 
205
                        next = ptr->next;
 
206
                        avro_freet(st_table_entry, ptr);
 
207
                        ptr = next;
 
208
                }
 
209
        }
 
210
        free_bins(table);
 
211
        avro_freet(st_table, table);
 
212
}
 
213
 
 
214
#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
 
215
((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
 
216
 
 
217
#ifdef HASH_LOG
 
218
#define COLLISION collision++
 
219
#else
 
220
#define COLLISION
 
221
#endif
 
222
 
 
223
#define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
 
224
    bin_pos = hash_val%(table)->num_bins;\
 
225
    ptr = (table)->bins[bin_pos];\
 
226
    if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
 
227
        COLLISION;\
 
228
        while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
 
229
            ptr = ptr->next;\
 
230
        }\
 
231
        ptr = ptr->next;\
 
232
    }\
 
233
} while (0)
 
234
 
 
235
int st_lookup(st_table *table, register st_data_t key, st_data_t *value)
 
236
{
 
237
        unsigned int hash_val, bin_pos;
 
238
        register st_table_entry *ptr;
 
239
 
 
240
        hash_val = do_hash(key, table);
 
241
        FIND_ENTRY(table, ptr, hash_val, bin_pos);
 
242
 
 
243
        if (ptr == 0) {
 
244
                return 0;
 
245
        } else {
 
246
                if (value != 0)
 
247
                        *value = ptr->record;
 
248
                return 1;
 
249
        }
 
250
}
 
251
 
 
252
#define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
 
253
do {\
 
254
    st_table_entry *entry;\
 
255
    if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
 
256
        rehash(table);\
 
257
        bin_pos = hash_val % table->num_bins;\
 
258
    }\
 
259
    \
 
260
    entry = (st_table_entry *) avro_new(st_table_entry);\
 
261
    \
 
262
    entry->hash = hash_val;\
 
263
    entry->key = key;\
 
264
    entry->record = value;\
 
265
    entry->next = table->bins[bin_pos];\
 
266
    table->bins[bin_pos] = entry;\
 
267
    table->num_entries++;\
 
268
} while (0)
 
269
 
 
270
int st_insert(register st_table *table, register st_data_t key, st_data_t value)
 
271
{
 
272
        unsigned int hash_val, bin_pos;
 
273
        register st_table_entry *ptr;
 
274
 
 
275
        hash_val = do_hash(key, table);
 
276
        FIND_ENTRY(table, ptr, hash_val, bin_pos);
 
277
 
 
278
        if (ptr == 0) {
 
279
                ADD_DIRECT(table, key, value, hash_val, bin_pos);
 
280
                return 0;
 
281
        } else {
 
282
                ptr->record = value;
 
283
                return 1;
 
284
        }
 
285
}
 
286
 
 
287
void st_add_direct(st_table *table,st_data_t key,st_data_t value)
 
288
{
 
289
        unsigned int hash_val, bin_pos;
 
290
 
 
291
        hash_val = do_hash(key, table);
 
292
        bin_pos = hash_val % table->num_bins;
 
293
        ADD_DIRECT(table, key, value, hash_val, bin_pos);
 
294
}
 
295
 
 
296
static void rehash(register st_table *table)
 
297
{
 
298
        register st_table_entry *ptr, *next, **new_bins;
 
299
        int i, old_num_bins = table->num_bins, new_num_bins;
 
300
        unsigned int hash_val;
 
301
 
 
302
        new_num_bins = new_size(old_num_bins + 1);
 
303
        new_bins =
 
304
            (st_table_entry **) Calloc(new_num_bins, sizeof(st_table_entry *));
 
305
 
 
306
        for (i = 0; i < old_num_bins; i++) {
 
307
                ptr = table->bins[i];
 
308
                while (ptr != 0) {
 
309
                        next = ptr->next;
 
310
                        hash_val = ptr->hash % new_num_bins;
 
311
                        ptr->next = new_bins[hash_val];
 
312
                        new_bins[hash_val] = ptr;
 
313
                        ptr = next;
 
314
                }
 
315
        }
 
316
        free_bins(table);
 
317
        table->num_bins = new_num_bins;
 
318
        table->bins = new_bins;
 
319
}
 
320
 
 
321
st_table *st_copy(st_table *old_table)
 
322
{
 
323
        st_table *new_table;
 
324
        st_table_entry *ptr, *entry;
 
325
        int i, num_bins = old_table->num_bins;
 
326
 
 
327
        new_table = (st_table *) avro_new(st_table);
 
328
        if (new_table == 0) {
 
329
                return 0;
 
330
        }
 
331
 
 
332
        *new_table = *old_table;
 
333
        new_table->bins = (st_table_entry **)
 
334
            Calloc((unsigned)num_bins, sizeof(st_table_entry *));
 
335
 
 
336
        if (new_table->bins == 0) {
 
337
                avro_freet(st_table, new_table);
 
338
                return 0;
 
339
        }
 
340
 
 
341
        for (i = 0; i < num_bins; i++) {
 
342
                new_table->bins[i] = 0;
 
343
                ptr = old_table->bins[i];
 
344
                while (ptr != 0) {
 
345
                        entry = (st_table_entry *) avro_new(st_table_entry);
 
346
                        if (entry == 0) {
 
347
                                free_bins(new_table);
 
348
                                avro_freet(st_table, new_table);
 
349
                                return 0;
 
350
                        }
 
351
                        *entry = *ptr;
 
352
                        entry->next = new_table->bins[i];
 
353
                        new_table->bins[i] = entry;
 
354
                        ptr = ptr->next;
 
355
                }
 
356
        }
 
357
        return new_table;
 
358
}
 
359
 
 
360
int st_delete(register st_table *table,register st_data_t *key,st_data_t *value)
 
361
{
 
362
        unsigned int hash_val;
 
363
        st_table_entry *tmp;
 
364
        register st_table_entry *ptr;
 
365
 
 
366
        hash_val = do_hash_bin(*key, table);
 
367
        ptr = table->bins[hash_val];
 
368
 
 
369
        if (ptr == 0) {
 
370
                if (value != 0)
 
371
                        *value = 0;
 
372
                return 0;
 
373
        }
 
374
 
 
375
        if (EQUAL(table, *key, ptr->key)) {
 
376
                table->bins[hash_val] = ptr->next;
 
377
                table->num_entries--;
 
378
                if (value != 0)
 
379
                        *value = ptr->record;
 
380
                *key = ptr->key;
 
381
                avro_freet(st_table_entry, ptr);
 
382
                return 1;
 
383
        }
 
384
 
 
385
        for (; ptr->next != 0; ptr = ptr->next) {
 
386
                if (EQUAL(table, ptr->next->key, *key)) {
 
387
                        tmp = ptr->next;
 
388
                        ptr->next = ptr->next->next;
 
389
                        table->num_entries--;
 
390
                        if (value != 0)
 
391
                                *value = tmp->record;
 
392
                        *key = tmp->key;
 
393
                        avro_freet(st_table_entry, tmp);
 
394
                        return 1;
 
395
                }
 
396
        }
 
397
 
 
398
        return 0;
 
399
}
 
400
 
 
401
int st_delete_safe(register st_table *table,register st_data_t *key,st_data_t *value,st_data_t never)
 
402
{
 
403
        unsigned int hash_val;
 
404
        register st_table_entry *ptr;
 
405
 
 
406
        hash_val = do_hash_bin(*key, table);
 
407
        ptr = table->bins[hash_val];
 
408
 
 
409
        if (ptr == 0) {
 
410
                if (value != 0)
 
411
                        *value = 0;
 
412
                return 0;
 
413
        }
 
414
 
 
415
        for (; ptr != 0; ptr = ptr->next) {
 
416
                if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
 
417
                        table->num_entries--;
 
418
                        *key = ptr->key;
 
419
                        if (value != 0)
 
420
                                *value = ptr->record;
 
421
                        ptr->key = ptr->record = never;
 
422
                        return 1;
 
423
                }
 
424
        }
 
425
 
 
426
        return 0;
 
427
}
 
428
 
 
429
static int delete_never(st_data_t key, st_data_t value, st_data_t never)
 
430
{
 
431
        AVRO_UNUSED(key);
 
432
 
 
433
        if (value == never)
 
434
                return ST_DELETE;
 
435
        return ST_CONTINUE;
 
436
}
 
437
 
 
438
void st_cleanup_safe(st_table *table,st_data_t never)
 
439
{
 
440
        int num_entries = table->num_entries;
 
441
 
 
442
        st_foreach(table, HASH_FUNCTION_CAST delete_never, never);
 
443
        table->num_entries = num_entries;
 
444
}
 
445
 
 
446
int st_foreach(st_table *table,int (*func) (ANYARGS),st_data_t arg)
 
447
{
 
448
        st_table_entry *ptr, *last, *tmp;
 
449
        enum st_retval retval;
 
450
        int i;
 
451
 
 
452
        for (i = 0; i < table->num_bins; i++) {
 
453
                last = 0;
 
454
                for (ptr = table->bins[i]; ptr != 0;) {
 
455
                        retval = (enum st_retval) (*func) (ptr->key, ptr->record, arg);
 
456
                        switch (retval) {
 
457
                        case ST_CHECK:  /* check if hash is modified during
 
458
                                         * iteration */
 
459
                                tmp = 0;
 
460
                                if (i < table->num_bins) {
 
461
                                        for (tmp = table->bins[i]; tmp;
 
462
                                             tmp = tmp->next) {
 
463
                                                if (tmp == ptr)
 
464
                                                        break;
 
465
                                        }
 
466
                                }
 
467
                                if (!tmp) {
 
468
                                        /*
 
469
                                         * call func with error notice 
 
470
                                         */
 
471
                                        return 1;
 
472
                                }
 
473
                                /*
 
474
                                 * fall through 
 
475
                                 */
 
476
                        case ST_CONTINUE:
 
477
                                last = ptr;
 
478
                                ptr = ptr->next;
 
479
                                break;
 
480
                        case ST_STOP:
 
481
                                return 0;
 
482
                        case ST_DELETE:
 
483
                                tmp = ptr;
 
484
                                if (last == 0) {
 
485
                                        table->bins[i] = ptr->next;
 
486
                                } else {
 
487
                                        last->next = ptr->next;
 
488
                                }
 
489
                                ptr = ptr->next;
 
490
                                avro_freet(st_table_entry, tmp);
 
491
                                table->num_entries--;
 
492
                        }
 
493
                }
 
494
        }
 
495
        return 0;
 
496
}
 
497
 
 
498
static int strhash(register const char *string)
 
499
{
 
500
        register int c;
 
501
 
 
502
#ifdef HASH_ELFHASH
 
503
        register unsigned int h = 0, g;
 
504
 
 
505
        while ((c = *string++) != '\0') {
 
506
                h = (h << 4) + c;
 
507
                if (g = h & 0xF0000000)
 
508
                        h ^= g >> 24;
 
509
                h &= ~g;
 
510
        }
 
511
        return h;
 
512
#elif defined(HASH_PERL)
 
513
        register int val = 0;
 
514
 
 
515
        while ((c = *string++) != '\0') {
 
516
                val += c;
 
517
                val += (val << 10);
 
518
                val ^= (val >> 6);
 
519
        }
 
520
        val += (val << 3);
 
521
        val ^= (val >> 11);
 
522
 
 
523
        return val + (val << 15);
 
524
#else
 
525
        register int val = 0;
 
526
 
 
527
        while ((c = *string++) != '\0') {
 
528
                val = val * 997 + c;
 
529
        }
 
530
 
 
531
        return val + (val >> 5);
 
532
#endif
 
533
}
 
534
 
 
535
static int numcmp(long x, long y)
 
536
{
 
537
        return x != y;
 
538
}
 
539
 
 
540
static int numhash(long n)
 
541
{
 
542
        return n;
 
543
}