1#define _GNU_SOURCE
2#include <stdlib.h>
3#include <string.h>
4#include <search.h>
5#include "libc.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
25static struct hsearch_data htab;
26
27int __hcreate_r(size_t, struct hsearch_data *);
28void __hdestroy_r(struct hsearch_data *);
29int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
30
31static 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
41static 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
73int hcreate(size_t nel)
74{
75	return __hcreate_r(nel, &htab);
76}
77
78void hdestroy(void)
79{
80	__hdestroy_r(&htab);
81}
82
83static 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
96ENTRY *hsearch(ENTRY item, ACTION action)
97{
98	ENTRY *e;
99
100	__hsearch_r(item, action, &e, &htab);
101	return e;
102}
103
104int __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}
118weak_alias(__hcreate_r, hcreate_r);
119
120void __hdestroy_r(struct hsearch_data *htab)
121{
122	if (htab->__tab) free(htab->__tab->entries);
123	free(htab->__tab);
124	htab->__tab = 0;
125}
126weak_alias(__hdestroy_r, hdestroy_r);
127
128int __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}
154weak_alias(__hsearch_r, hsearch_r);
155