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