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