![[BACK]](/icons/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / ctfconv|
Return to hash.c CVS log | Up to [local] / src / usr.bin / ctfconv |
1.2 ! jasper 1: /* $OpenBSD$ */
! 2:
1.1 mpi 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
53: hash_delete(struct hash *h)
54: {
55: free(h->t);
56: h->t = NULL;
57: }
58:
59: static void
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 *
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
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 *
136: hash_first(struct hash *h, unsigned int *pos)
137: {
138: *pos = 0;
139: return hash_next(h, pos);
140: }
141:
142: void *
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 *
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
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
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 *
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: }