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