1 /*
2 * Copyright (c) 1992, 1993
3 * The Regents of the University of California. All rights reserved.
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 *
16 * @(#)hash.c 8.1 (Berkeley) 06/06/93
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 *
poolalloc(size)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
ht_init(ht,sz)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
ht_expand(ht)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 *
newhashent(name,h)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
hash(str)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
initintern()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 *
intern(s)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 *
ht_new()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
ht_insrep(ht,nam,val,replace)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 *
ht_lookup(ht,nam)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 }
254