1 /* $OpenBSD: hash.c,v 1.2 2017/08/11 14:58:56 jasper Exp $ */
2
3 /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18 #include <stddef.h>
19 #include <stdint.h>
20 #include <stdlib.h>
21 #include <string.h>
22 #include <limits.h>
23
24 #include "hash.h"
25
26 struct _hash_record {
27 uint32_t hv;
28 struct hash_entry *p;
29 };
30
31 struct hash {
32 struct _hash_record *t;
33 unsigned int size;
34 unsigned int total;
35 unsigned int deleted;
36 };
37
38 #define DELETED ((struct hash_entry *)h)
39 #define NONE (h->size)
40
41 /* Don't bother changing the hash table if the change is small enough. */
42 #define MINSIZE (1UL << 4)
43 #define MINDELETED 4
44
45 static void hash_resize(struct hash *);
46 static uint32_t hash_interval(const char *, const char **);
47 static unsigned int hash_qlookup(struct hash *, const char *);
48
49
50 /* hash_delete only frees the hash structure. Use hash_first/hash_next
51 * to free entries as well. */
52 void
hash_delete(struct hash * h)53 hash_delete(struct hash *h)
54 {
55 free(h->t);
56 h->t = NULL;
57 }
58
59 static void
hash_resize(struct hash * h)60 hash_resize(struct hash *h)
61 {
62 struct _hash_record *n;
63 size_t ns;
64 unsigned int j;
65 unsigned int i, incr;
66
67 if (4 * h->deleted < h->total) {
68 if (h->size >= (UINT_MAX >> 1U))
69 ns = UINT_MAX;
70 else
71 ns = h->size << 1U;
72 } else if (3 * h->deleted > 2 * h->total)
73 ns = h->size >> 1U;
74 else
75 ns = h->size;
76 if (ns < MINSIZE)
77 ns = MINSIZE;
78
79 n = calloc(ns, sizeof(struct _hash_record));
80 if (!n)
81 return;
82
83 for (j = 0; j < h->size; j++) {
84 if (h->t[j].p != NULL && h->t[j].p != DELETED) {
85 i = h->t[j].hv % ns;
86 incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
87 while (n[i].p != NULL) {
88 i += incr;
89 if (i >= ns)
90 i -= ns;
91 }
92 n[i].hv = h->t[j].hv;
93 n[i].p = h->t[j].p;
94 }
95 }
96 free(h->t);
97 h->t = n;
98 h->size = ns;
99 h->total -= h->deleted;
100 h->deleted = 0;
101 }
102
103 void *
hash_remove(struct hash * h,unsigned int i)104 hash_remove(struct hash *h, unsigned int i)
105 {
106 void *result = (void *)h->t[i].p;
107
108 if (result == NULL || result == DELETED)
109 return NULL;
110
111 h->t[i].p = DELETED;
112 h->deleted++;
113 if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
114 hash_resize(h);
115 return result;
116 }
117
118 void
hash_insert(struct hash * h,unsigned int i,struct hash_entry * p,const char * key)119 hash_insert(struct hash *h, unsigned int i, struct hash_entry *p,
120 const char *key)
121 {
122 p->hkey = key;
123
124 if (h->t[i].p == DELETED) {
125 h->deleted--;
126 h->t[i].p = p;
127 } else {
128 h->t[i].p = p;
129 /* Arbitrary resize boundary. Tweak if not efficient enough. */
130 if (++h->total * 4 > h->size * 3)
131 hash_resize(h);
132 }
133 }
134
135 void *
hash_first(struct hash * h,unsigned int * pos)136 hash_first(struct hash *h, unsigned int *pos)
137 {
138 *pos = 0;
139 return hash_next(h, pos);
140 }
141
142 void *
hash_next(struct hash * h,unsigned int * pos)143 hash_next(struct hash *h, unsigned int *pos)
144 {
145 for (; *pos < h->size; (*pos)++)
146 if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
147 return (void *)h->t[(*pos)++].p;
148 return NULL;
149 }
150
151 struct hash *
hash_init(unsigned int size)152 hash_init(unsigned int size)
153 {
154 struct hash *h;
155
156 h = calloc(1, sizeof(*h));
157 if (h == NULL)
158 return NULL;
159
160 h->size = 1UL << size;
161 if (h->size < MINSIZE)
162 h->size = MINSIZE;
163 /* Copy info so that caller may free it. */
164 h->total = h->deleted = 0;
165 h->t = calloc(h->size, sizeof(struct _hash_record));
166 if (h->t == NULL) {
167 free(h);
168 return NULL;
169 }
170
171 return h;
172 }
173
174 static uint32_t
hash_interval(const char * s,const char ** e)175 hash_interval(const char *s, const char **e)
176 {
177 uint32_t k;
178
179 if (!*e)
180 *e = s + strlen(s);
181 if (s == *e)
182 k = 0;
183 else
184 k = *s++;
185 while (s != *e)
186 k = ((k << 2) | (k >> 30)) ^ *s++;
187 return k;
188 }
189
190 static unsigned int
hash_qlookup(struct hash * h,const char * start)191 hash_qlookup(struct hash *h, const char *start)
192 {
193 const char *end = NULL;
194 unsigned int i, incr;
195 unsigned int empty;
196 uint32_t hv;
197
198 hv = hash_interval(start, &end);
199
200 empty = NONE;
201 i = hv % h->size;
202 incr = ((hv % (h->size-2)) & ~1) + 1;
203 while (h->t[i].p != NULL) {
204 if (h->t[i].p == DELETED) {
205 if (empty == NONE)
206 empty = i;
207 } else if (h->t[i].hv == hv &&
208 strncmp(h->t[i].p->hkey, start, end - start) == 0 &&
209 (h->t[i].p->hkey)[end-start] == '\0') {
210 if (empty != NONE) {
211 h->t[empty].hv = hv;
212 h->t[empty].p = h->t[i].p;
213 h->t[i].p = DELETED;
214 return empty;
215 } else {
216 return i;
217 }
218 }
219 i += incr;
220 if (i >= h->size)
221 i -= h->size;
222 }
223
224 /* Found an empty position. */
225 if (empty != NONE)
226 i = empty;
227 h->t[i].hv = hv;
228 return i;
229 }
230
231 struct hash_entry *
hash_find(struct hash * h,const char * start,unsigned int * slot)232 hash_find(struct hash *h, const char *start, unsigned int *slot)
233 {
234 unsigned int i;
235
236 i = hash_qlookup(h, start);
237 if (slot != NULL)
238 *slot = i;
239
240 if (h->t[i].p == DELETED)
241 return NULL;
242
243 return h->t[i].p;
244 }
245