[398] | 1 | #define _GNU_SOURCE
|
---|
| 2 | #include <stdlib.h>
|
---|
| 3 | #include <string.h>
|
---|
| 4 | #include <search.h>
|
---|
| 5 | #include "libc.h"
|
---|
| 6 |
|
---|
| 7 | /*
|
---|
| 8 | open addressing hash table with 2^n table size
|
---|
| 9 | quadratic probing is used in case of hash collision
|
---|
| 10 | tab indices and hash are size_t
|
---|
| 11 | after resize fails with ENOMEM the state of tab is still usable
|
---|
| 12 |
|
---|
| 13 | with the posix api items cannot be iterated and length cannot be queried
|
---|
| 14 | */
|
---|
| 15 |
|
---|
| 16 | #define MINSIZE 8
|
---|
| 17 | #define MAXSIZE ((size_t)-1/2 + 1)
|
---|
| 18 |
|
---|
| 19 | struct __tab {
|
---|
| 20 | ENTRY *entries;
|
---|
| 21 | size_t mask;
|
---|
| 22 | size_t used;
|
---|
| 23 | };
|
---|
| 24 |
|
---|
| 25 | static struct hsearch_data htab;
|
---|
| 26 |
|
---|
| 27 | int __hcreate_r(size_t, struct hsearch_data *);
|
---|
| 28 | void __hdestroy_r(struct hsearch_data *);
|
---|
| 29 | int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
|
---|
| 30 |
|
---|
| 31 | static size_t keyhash(char *k)
|
---|
| 32 | {
|
---|
| 33 | unsigned char *p = (void *)k;
|
---|
| 34 | size_t h = 0;
|
---|
| 35 |
|
---|
| 36 | while (*p)
|
---|
| 37 | h = 31*h + *p++;
|
---|
| 38 | return h;
|
---|
| 39 | }
|
---|
| 40 |
|
---|
| 41 | static int resize(size_t nel, struct hsearch_data *htab)
|
---|
| 42 | {
|
---|
| 43 | size_t newsize;
|
---|
| 44 | size_t i, j;
|
---|
| 45 | ENTRY *e, *newe;
|
---|
| 46 | ENTRY *oldtab = htab->__tab->entries;
|
---|
| 47 | ENTRY *oldend = htab->__tab->entries + htab->__tab->mask + 1;
|
---|
| 48 |
|
---|
| 49 | if (nel > MAXSIZE)
|
---|
| 50 | nel = MAXSIZE;
|
---|
| 51 | for (newsize = MINSIZE; newsize < nel; newsize *= 2);
|
---|
| 52 | htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
|
---|
| 53 | if (!htab->__tab->entries) {
|
---|
| 54 | htab->__tab->entries = oldtab;
|
---|
| 55 | return 0;
|
---|
| 56 | }
|
---|
| 57 | htab->__tab->mask = newsize - 1;
|
---|
| 58 | if (!oldtab)
|
---|
| 59 | return 1;
|
---|
| 60 | for (e = oldtab; e < oldend; e++)
|
---|
| 61 | if (e->key) {
|
---|
| 62 | for (i=keyhash(e->key),j=1; ; i+=j++) {
|
---|
| 63 | newe = htab->__tab->entries + (i & htab->__tab->mask);
|
---|
| 64 | if (!newe->key)
|
---|
| 65 | break;
|
---|
| 66 | }
|
---|
| 67 | *newe = *e;
|
---|
| 68 | }
|
---|
| 69 | free(oldtab);
|
---|
| 70 | return 1;
|
---|
| 71 | }
|
---|
| 72 |
|
---|
| 73 | int hcreate(size_t nel)
|
---|
| 74 | {
|
---|
| 75 | return __hcreate_r(nel, &htab);
|
---|
| 76 | }
|
---|
| 77 |
|
---|
| 78 | void hdestroy(void)
|
---|
| 79 | {
|
---|
| 80 | __hdestroy_r(&htab);
|
---|
| 81 | }
|
---|
| 82 |
|
---|
| 83 | static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
|
---|
| 84 | {
|
---|
| 85 | size_t i, j;
|
---|
| 86 | ENTRY *e;
|
---|
| 87 |
|
---|
| 88 | for (i=hash,j=1; ; i+=j++) {
|
---|
| 89 | e = htab->__tab->entries + (i & htab->__tab->mask);
|
---|
| 90 | if (!e->key || strcmp(e->key, key) == 0)
|
---|
| 91 | break;
|
---|
| 92 | }
|
---|
| 93 | return e;
|
---|
| 94 | }
|
---|
| 95 |
|
---|
| 96 | ENTRY *hsearch(ENTRY item, ACTION action)
|
---|
| 97 | {
|
---|
| 98 | ENTRY *e;
|
---|
| 99 |
|
---|
| 100 | __hsearch_r(item, action, &e, &htab);
|
---|
| 101 | return e;
|
---|
| 102 | }
|
---|
| 103 |
|
---|
| 104 | int __hcreate_r(size_t nel, struct hsearch_data *htab)
|
---|
| 105 | {
|
---|
| 106 | int r;
|
---|
| 107 |
|
---|
| 108 | htab->__tab = calloc(1, sizeof *htab->__tab);
|
---|
| 109 | if (!htab->__tab)
|
---|
| 110 | return 0;
|
---|
| 111 | r = resize(nel, htab);
|
---|
| 112 | if (r == 0) {
|
---|
| 113 | free(htab->__tab);
|
---|
| 114 | htab->__tab = 0;
|
---|
| 115 | }
|
---|
| 116 | return r;
|
---|
| 117 | }
|
---|
| 118 | weak_alias(__hcreate_r, hcreate_r);
|
---|
| 119 |
|
---|
| 120 | void __hdestroy_r(struct hsearch_data *htab)
|
---|
| 121 | {
|
---|
| 122 | if (htab->__tab) free(htab->__tab->entries);
|
---|
| 123 | free(htab->__tab);
|
---|
| 124 | htab->__tab = 0;
|
---|
| 125 | }
|
---|
| 126 | weak_alias(__hdestroy_r, hdestroy_r);
|
---|
| 127 |
|
---|
| 128 | int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
|
---|
| 129 | {
|
---|
| 130 | size_t hash = keyhash(item.key);
|
---|
| 131 | ENTRY *e = lookup(item.key, hash, htab);
|
---|
| 132 |
|
---|
| 133 | if (e->key) {
|
---|
| 134 | *retval = e;
|
---|
| 135 | return 1;
|
---|
| 136 | }
|
---|
| 137 | if (action == FIND) {
|
---|
| 138 | *retval = 0;
|
---|
| 139 | return 0;
|
---|
| 140 | }
|
---|
| 141 | *e = item;
|
---|
| 142 | if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
|
---|
| 143 | if (!resize(2*htab->__tab->used, htab)) {
|
---|
| 144 | htab->__tab->used--;
|
---|
| 145 | e->key = 0;
|
---|
| 146 | *retval = 0;
|
---|
| 147 | return 0;
|
---|
| 148 | }
|
---|
| 149 | e = lookup(item.key, hash, htab);
|
---|
| 150 | }
|
---|
| 151 | *retval = e;
|
---|
| 152 | return 1;
|
---|
| 153 | }
|
---|
| 154 | weak_alias(__hsearch_r, hsearch_r);
|
---|