Commit | Line | Data |
---|---|---|
f7ef6e94 | 1 | /* |
62a2aae7 KB |
2 | * Copyright (c) 1992, 1993 |
3 | * The Regents of the University of California. All rights reserved. | |
f7ef6e94 CT |
4 | * |
5 | * This software was developed by the Computer Systems Engineering group | |
6 | * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and | |
7 | * contributed to Berkeley. | |
8 | * | |
9 | * All advertising materials mentioning features or use of this software | |
10 | * must display the following acknowledgement: | |
11 | * This product includes software developed by the University of | |
12 | * California, Lawrence Berkeley Laboratories. | |
13 | * | |
14 | * %sccs.include.redist.c% | |
15 | * | |
62a2aae7 | 16 | * @(#)hash.c 8.1 (Berkeley) %G% |
f7ef6e94 CT |
17 | */ |
18 | ||
19 | #include <sys/param.h> | |
20 | #include <stdlib.h> | |
21 | #include <string.h> | |
22 | #include "config.h" | |
23 | ||
24 | /* | |
25 | * Interned strings are kept in a hash table. By making each string | |
26 | * unique, the program can compare strings by comparing pointers. | |
27 | */ | |
28 | struct hashent { | |
29 | struct hashent *h_next; /* hash buckets are chained */ | |
30 | const char *h_name; /* the string */ | |
31 | u_int h_hash; /* its hash value */ | |
32 | void *h_value; /* other values (for name=value) */ | |
33 | }; | |
34 | struct hashtab { | |
35 | size_t ht_size; /* size (power of 2) */ | |
36 | u_int ht_mask; /* == ht_size - 1 */ | |
37 | u_int ht_used; /* number of entries used */ | |
38 | u_int ht_lim; /* when to expand */ | |
39 | struct hashent **ht_tab; /* base of table */ | |
40 | }; | |
41 | static struct hashtab strings; | |
42 | ||
43 | /* | |
44 | * HASHFRACTION controls ht_lim, which in turn controls the average chain | |
45 | * length. We allow a few entries, on average, as comparing them is usually | |
46 | * cheap (the h_hash values prevent a strcmp). | |
47 | */ | |
48 | #define HASHFRACTION(sz) ((sz) * 3 / 2) | |
49 | ||
50 | /* round up to next multiple of y, where y is a power of 2 */ | |
51 | #define ROUND(x, y) (((x) + (y) - 1) & ~((y) - 1)) | |
52 | ||
53 | /* | |
54 | * Allocate space that will never be freed. | |
55 | */ | |
56 | static void * | |
57 | poolalloc(size) | |
58 | size_t size; | |
59 | { | |
60 | register char *p; | |
61 | register size_t alloc; | |
62 | static char *pool; | |
63 | static size_t nleft; | |
64 | ||
65 | if (nleft < size) { | |
66 | /* | |
67 | * Compute a `good' size to allocate via malloc. | |
68 | * 16384 is a guess at a good page size for malloc; | |
69 | * 32 is a guess at malloc's overhead. | |
70 | */ | |
71 | alloc = ROUND(size + 32, 16384) - 32; | |
72 | p = emalloc(alloc); | |
73 | nleft = alloc - size; | |
74 | } else { | |
75 | p = pool; | |
76 | nleft -= size; | |
77 | } | |
78 | pool = p + size; | |
79 | return (p); | |
80 | } | |
81 | ||
82 | /* | |
83 | * Initialize a new hash table. The size must be a power of 2. | |
84 | */ | |
85 | static void | |
86 | ht_init(ht, sz) | |
87 | register struct hashtab *ht; | |
88 | size_t sz; | |
89 | { | |
90 | register struct hashent **h; | |
91 | register u_int n; | |
92 | ||
93 | h = emalloc(sz * sizeof *h); | |
94 | ht->ht_tab = h; | |
95 | ht->ht_size = sz; | |
96 | ht->ht_mask = sz - 1; | |
97 | for (n = 0; n < sz; n++) | |
98 | *h++ = NULL; | |
99 | ht->ht_used = 0; | |
100 | ht->ht_lim = HASHFRACTION(sz); | |
101 | } | |
102 | ||
103 | /* | |
104 | * Expand an existing hash table. | |
105 | */ | |
106 | static void | |
107 | ht_expand(ht) | |
108 | register struct hashtab *ht; | |
109 | { | |
110 | register struct hashent *p, **h, **oldh, *q; | |
111 | register u_int n, i; | |
112 | ||
113 | n = ht->ht_size * 2; | |
114 | h = emalloc(n * sizeof *h); | |
115 | for (i = 0; i < n; i++) | |
116 | h[i] = NULL; | |
117 | oldh = ht->ht_tab; | |
118 | n--; | |
119 | for (i = ht->ht_size; i != 0; i--) { | |
120 | for (p = *oldh++; p != NULL; p = q) { | |
121 | q = p->h_next; | |
122 | p->h_next = h[p->h_hash & n]; | |
123 | h[p->h_hash & n] = p; | |
124 | } | |
125 | } | |
126 | free(ht->ht_tab); | |
127 | ht->ht_tab = h; | |
128 | ht->ht_mask = n; | |
129 | ht->ht_size = ++n; | |
130 | ht->ht_lim = HASHFRACTION(n); | |
131 | } | |
132 | ||
133 | /* | |
134 | * Make a new hash entry, setting its h_next to NULL. | |
135 | */ | |
136 | static inline struct hashent * | |
137 | newhashent(name, h) | |
138 | const char *name; | |
139 | u_int h; | |
140 | { | |
141 | register struct hashent *hp; | |
142 | register char *m; | |
143 | ||
144 | m = poolalloc(sizeof(*hp) + ALIGNBYTES); | |
145 | hp = (struct hashent *)ALIGN(m); | |
146 | hp->h_name = name; | |
147 | hp->h_hash = h; | |
148 | hp->h_next = NULL; | |
149 | return (hp); | |
150 | } | |
151 | ||
152 | /* | |
153 | * Hash a string. | |
154 | */ | |
155 | static inline u_int | |
156 | hash(str) | |
157 | register const char *str; | |
158 | { | |
159 | register u_int h; | |
160 | ||
161 | for (h = 0; *str;) | |
162 | h = (h << 5) + h + *str++; | |
163 | return (h); | |
164 | } | |
165 | ||
166 | void | |
167 | initintern() | |
168 | { | |
169 | ||
170 | ht_init(&strings, 128); | |
171 | } | |
172 | ||
173 | /* | |
174 | * Generate a single unique copy of the given string. We expect this | |
175 | * function to be used frequently, so it should be fast. | |
176 | */ | |
177 | const char * | |
178 | intern(s) | |
179 | register const char *s; | |
180 | { | |
181 | register struct hashtab *ht; | |
182 | register struct hashent *hp, **hpp; | |
183 | register u_int h; | |
184 | register char *p; | |
185 | register size_t l; | |
186 | ||
187 | ht = &strings; | |
188 | h = hash(s); | |
189 | hpp = &ht->ht_tab[h & ht->ht_mask]; | |
190 | for (; (hp = *hpp) != NULL; hpp = &hp->h_next) | |
191 | if (hp->h_hash == h && strcmp(hp->h_name, s) == 0) | |
192 | return (hp->h_name); | |
193 | l = strlen(s) + 1; | |
194 | p = poolalloc(l); | |
195 | bcopy(s, p, l); | |
196 | *hpp = newhashent(p, h); | |
197 | if (++ht->ht_used > ht->ht_lim) | |
198 | ht_expand(ht); | |
199 | return (p); | |
200 | } | |
201 | ||
202 | struct hashtab * | |
203 | ht_new() | |
204 | { | |
205 | register struct hashtab *ht; | |
206 | ||
207 | ht = emalloc(sizeof *ht); | |
208 | ht_init(ht, 8); | |
209 | return (ht); | |
210 | } | |
211 | ||
212 | /* | |
213 | * Insert and/or replace. | |
214 | */ | |
215 | int | |
216 | ht_insrep(ht, nam, val, replace) | |
217 | register struct hashtab *ht; | |
218 | register const char *nam; | |
219 | void *val; | |
220 | int replace; | |
221 | { | |
222 | register struct hashent *hp, **hpp; | |
223 | register u_int h; | |
224 | ||
225 | h = hash(nam); | |
226 | hpp = &ht->ht_tab[h & ht->ht_mask]; | |
227 | for (; (hp = *hpp) != NULL; hpp = &hp->h_next) { | |
228 | if (hp->h_name == nam) { | |
229 | if (replace) | |
230 | hp->h_value = val; | |
231 | return (1); | |
232 | } | |
233 | } | |
234 | *hpp = hp = newhashent(nam, h); | |
235 | hp->h_value = val; | |
236 | return (0); | |
237 | } | |
238 | ||
239 | void * | |
240 | ht_lookup(ht, nam) | |
241 | register struct hashtab *ht; | |
242 | register const char *nam; | |
243 | { | |
244 | register struct hashent *hp, **hpp; | |
245 | register u_int h; | |
246 | ||
247 | h = hash(nam); | |
248 | hpp = &ht->ht_tab[h & ht->ht_mask]; | |
249 | for (; (hp = *hpp) != NULL; hpp = &hp->h_next) | |
250 | if (hp->h_name == nam) | |
251 | return (hp->h_value); | |
252 | return (NULL); | |
253 | } |