Annotation of mandoc/compat_ohash.c, Revision 1.6
1.1 kristaps 1: #include "config.h"
2:
1.6 ! schwarze 3: #if HAVE_OHASH
1.1 kristaps 4:
5: int dummy;
6:
7: #else
8:
1.3 schwarze 9: /* $OpenBSD: ohash.c,v 1.1 2014/06/02 18:52:03 deraadt Exp $ */
10:
11: /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
12: *
13: * Permission to use, copy, modify, and distribute this software for any
14: * purpose with or without fee is hereby granted, provided that the above
15: * copyright notice and this permission notice appear in all copies.
16: *
17: * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
18: * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
19: * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
20: * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
21: * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
22: * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
23: * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
24: */
1.5 schwarze 25:
26: #include <sys/types.h>
1.1 kristaps 27:
28: #include <stddef.h>
29: #include <stdint.h>
30: #include <stdlib.h>
31: #include <string.h>
1.4 schwarze 32: #include <limits.h>
1.1 kristaps 33: #include "compat_ohash.h"
34:
35: struct _ohash_record {
1.2 schwarze 36: uint32_t hv;
1.3 schwarze 37: const char *p;
1.1 kristaps 38: };
39:
40: #define DELETED ((const char *)h)
41: #define NONE (h->size)
42:
43: /* Don't bother changing the hash table if the change is small enough. */
44: #define MINSIZE (1UL << 4)
45: #define MINDELETED 4
46:
1.3 schwarze 47: static void ohash_resize(struct ohash *);
48:
1.1 kristaps 49:
1.3 schwarze 50: /* This handles the common case of variable length keys, where the
1.1 kristaps 51: * key is stored at the end of the record.
52: */
53: void *
54: ohash_create_entry(struct ohash_info *i, const char *start, const char **end)
55: {
56: char *p;
57:
58: if (!*end)
59: *end = start + strlen(start);
60: p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data);
61: if (p) {
1.3 schwarze 62: memcpy(p+i->key_offset, start, *end-start);
63: p[i->key_offset + (*end - start)] = '\0';
1.1 kristaps 64: }
65: return (void *)p;
66: }
67:
68: /* hash_delete only frees the hash structure. Use hash_first/hash_next
69: * to free entries as well. */
1.3 schwarze 70: void
1.1 kristaps 71: ohash_delete(struct ohash *h)
72: {
1.4 schwarze 73: (h->info.free)(h->t, h->info.data);
1.1 kristaps 74: #ifndef NDEBUG
75: h->t = NULL;
76: #endif
77: }
78:
1.3 schwarze 79: static void
1.1 kristaps 80: ohash_resize(struct ohash *h)
81: {
82: struct _ohash_record *n;
1.4 schwarze 83: size_t ns;
84: unsigned int j;
1.1 kristaps 85: unsigned int i, incr;
86:
1.4 schwarze 87: if (4 * h->deleted < h->total) {
88: if (h->size >= (UINT_MAX >> 1U))
89: ns = UINT_MAX;
90: else
91: ns = h->size << 1U;
92: } else if (3 * h->deleted > 2 * h->total)
93: ns = h->size >> 1U;
1.1 kristaps 94: else
95: ns = h->size;
96: if (ns < MINSIZE)
97: ns = MINSIZE;
98: #ifdef STATS_HASH
99: STAT_HASH_EXPAND++;
100: STAT_HASH_SIZE += ns - h->size;
101: #endif
1.4 schwarze 102:
103: n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);
1.1 kristaps 104: if (!n)
105: return;
106:
107: for (j = 0; j < h->size; j++) {
108: if (h->t[j].p != NULL && h->t[j].p != DELETED) {
109: i = h->t[j].hv % ns;
110: incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
111: while (n[i].p != NULL) {
112: i += incr;
113: if (i >= ns)
114: i -= ns;
1.3 schwarze 115: }
1.1 kristaps 116: n[i].hv = h->t[j].hv;
117: n[i].p = h->t[j].p;
118: }
119: }
1.4 schwarze 120: (h->info.free)(h->t, h->info.data);
1.1 kristaps 121: h->t = n;
122: h->size = ns;
123: h->total -= h->deleted;
124: h->deleted = 0;
125: }
126:
127: void *
128: ohash_remove(struct ohash *h, unsigned int i)
129: {
1.3 schwarze 130: void *result = (void *)h->t[i].p;
1.1 kristaps 131:
132: if (result == NULL || result == DELETED)
133: return NULL;
134:
135: #ifdef STATS_HASH
136: STAT_HASH_ENTRIES--;
137: #endif
138: h->t[i].p = DELETED;
139: h->deleted++;
140: if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
141: ohash_resize(h);
142: return result;
143: }
144:
145: void *
146: ohash_find(struct ohash *h, unsigned int i)
147: {
148: if (h->t[i].p == DELETED)
149: return NULL;
150: else
151: return (void *)h->t[i].p;
152: }
153:
154: void *
155: ohash_insert(struct ohash *h, unsigned int i, void *p)
156: {
157: #ifdef STATS_HASH
158: STAT_HASH_ENTRIES++;
159: #endif
160: if (h->t[i].p == DELETED) {
161: h->deleted--;
162: h->t[i].p = p;
163: } else {
164: h->t[i].p = p;
1.3 schwarze 165: /* Arbitrary resize boundary. Tweak if not efficient enough. */
1.1 kristaps 166: if (++h->total * 4 > h->size * 3)
167: ohash_resize(h);
168: }
1.3 schwarze 169: return p;
1.1 kristaps 170: }
171:
172: unsigned int
173: ohash_entries(struct ohash *h)
174: {
175: return h->total - h->deleted;
176: }
177:
178: void *
179: ohash_first(struct ohash *h, unsigned int *pos)
180: {
181: *pos = 0;
182: return ohash_next(h, pos);
183: }
1.3 schwarze 184:
1.1 kristaps 185: void *
186: ohash_next(struct ohash *h, unsigned int *pos)
187: {
1.3 schwarze 188: for (; *pos < h->size; (*pos)++)
189: if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
1.1 kristaps 190: return (void *)h->t[(*pos)++].p;
191: return NULL;
192: }
193:
1.3 schwarze 194: void
1.1 kristaps 195: ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info)
196: {
197: h->size = 1UL << size;
198: if (h->size < MINSIZE)
199: h->size = MINSIZE;
200: #ifdef STATS_HASH
201: STAT_HASH_CREATION++;
202: STAT_HASH_SIZE += h->size;
203: #endif
204: /* Copy info so that caller may free it. */
205: h->info.key_offset = info->key_offset;
1.4 schwarze 206: h->info.calloc = info->calloc;
207: h->info.free = info->free;
1.1 kristaps 208: h->info.alloc = info->alloc;
209: h->info.data = info->data;
1.4 schwarze 210: h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),
211: h->info.data);
1.1 kristaps 212: h->total = h->deleted = 0;
213: }
214:
215: uint32_t
216: ohash_interval(const char *s, const char **e)
217: {
218: uint32_t k;
219:
220: if (!*e)
221: *e = s + strlen(s);
222: if (s == *e)
223: k = 0;
224: else
225: k = *s++;
226: while (s != *e)
227: k = ((k << 2) | (k >> 30)) ^ *s++;
228: return k;
229: }
230:
231: unsigned int
1.3 schwarze 232: ohash_lookup_interval(struct ohash *h, const char *start, const char *end,
1.1 kristaps 233: uint32_t hv)
234: {
1.3 schwarze 235: unsigned int i, incr;
1.1 kristaps 236: unsigned int empty;
1.3 schwarze 237:
1.1 kristaps 238: #ifdef STATS_HASH
239: STAT_HASH_LOOKUP++;
240: #endif
241: empty = NONE;
242: i = hv % h->size;
243: incr = ((hv % (h->size-2)) & ~1) + 1;
244: while (h->t[i].p != NULL) {
245: #ifdef STATS_HASH
246: STAT_HASH_LENGTH++;
247: #endif
248: if (h->t[i].p == DELETED) {
249: if (empty == NONE)
250: empty = i;
1.3 schwarze 251: } else if (h->t[i].hv == hv &&
252: strncmp(h->t[i].p+h->info.key_offset, start,
253: end - start) == 0 &&
1.1 kristaps 254: (h->t[i].p+h->info.key_offset)[end-start] == '\0') {
1.3 schwarze 255: if (empty != NONE) {
1.1 kristaps 256: h->t[empty].hv = hv;
257: h->t[empty].p = h->t[i].p;
258: h->t[i].p = DELETED;
259: return empty;
260: } else {
261: #ifdef STATS_HASH
262: STAT_HASH_POSITIVE++;
263: #endif
264: return i;
265: }
266: }
267: i += incr;
1.3 schwarze 268: if (i >= h->size)
1.1 kristaps 269: i -= h->size;
270: }
271:
272: /* Found an empty position. */
1.3 schwarze 273: if (empty != NONE)
1.1 kristaps 274: i = empty;
275: h->t[i].hv = hv;
276: return i;
277: }
278:
279: unsigned int
280: ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)
281: {
282: unsigned int i, incr;
283: unsigned int empty;
1.3 schwarze 284:
1.1 kristaps 285: #ifdef STATS_HASH
286: STAT_HASH_LOOKUP++;
287: #endif
288: empty = NONE;
289: i = hv % h->size;
290: incr = ((hv % (h->size-2)) & ~1) + 1;
291: while (h->t[i].p != NULL) {
292: #ifdef STATS_HASH
293: STAT_HASH_LENGTH++;
294: #endif
295: if (h->t[i].p == DELETED) {
296: if (empty == NONE)
297: empty = i;
1.3 schwarze 298: } else if (h->t[i].hv == hv &&
1.1 kristaps 299: memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {
1.3 schwarze 300: if (empty != NONE) {
1.1 kristaps 301: h->t[empty].hv = hv;
302: h->t[empty].p = h->t[i].p;
303: h->t[i].p = DELETED;
304: return empty;
305: } else {
306: #ifdef STATS_HASH
307: STAT_HASH_POSITIVE++;
308: #endif
309: } return i;
310: }
311: i += incr;
1.3 schwarze 312: if (i >= h->size)
1.1 kristaps 313: i -= h->size;
314: }
315:
316: /* Found an empty position. */
1.3 schwarze 317: if (empty != NONE)
1.1 kristaps 318: i = empty;
319: h->t[i].hv = hv;
320: return i;
321: }
322:
323: unsigned int
324: ohash_qlookup(struct ohash *h, const char *s)
325: {
326: const char *e = NULL;
327: return ohash_qlookupi(h, s, &e);
328: }
329:
330: unsigned int
331: ohash_qlookupi(struct ohash *h, const char *s, const char **e)
332: {
1.2 schwarze 333: uint32_t hv;
1.1 kristaps 334:
335: hv = ohash_interval(s, e);
336: return ohash_lookup_interval(h, s, *e, hv);
337: }
338:
339: #endif /*!HAVE_OHASH*/
CVSweb