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