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