1 | /* ----------------------------------------------------------------------- * |
2 | * |
3 | * Copyright 1996-2009 The NASM Authors - All Rights Reserved |
4 | * See the file AUTHORS included with the NASM distribution for |
5 | * the specific copyright holders. |
6 | * |
7 | * Redistribution and use in source and binary forms, with or without |
8 | * modification, are permitted provided that the following |
9 | * conditions are met: |
10 | * |
11 | * * Redistributions of source code must retain the above copyright |
12 | * notice, this list of conditions and the following disclaimer. |
13 | * * Redistributions in binary form must reproduce the above |
14 | * copyright notice, this list of conditions and the following |
15 | * disclaimer in the documentation and/or other materials provided |
16 | * with the distribution. |
17 | * |
18 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND |
19 | * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, |
20 | * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF |
21 | * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
22 | * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR |
23 | * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
24 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
25 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
26 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
27 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
28 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR |
29 | * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, |
30 | * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
31 | * |
32 | * ----------------------------------------------------------------------- */ |
33 | |
34 | /* |
35 | * hashtbl.c |
36 | * |
37 | * Efficient dictionary hash table class. |
38 | */ |
39 | |
40 | #include "compiler.h" |
41 | |
42 | #include <string.h> |
43 | #include "nasm.h" |
44 | #include "hashtbl.h" |
45 | |
46 | #define HASH_MAX_LOAD 2 /* Higher = more memory-efficient, slower */ |
47 | |
48 | #define hash_calc(key) crc64(CRC64_INIT, (key)) |
49 | #define hash_calci(key) crc64i(CRC64_INIT, (key)) |
50 | #define hash_max_load(size) ((size) * (HASH_MAX_LOAD - 1) / HASH_MAX_LOAD) |
51 | #define hash_expand(size) ((size) << 1) |
52 | #define hash_mask(size) ((size) - 1) |
53 | #define hash_pos(hash, mask) ((hash) & (mask)) |
54 | #define hash_inc(hash, mask) ((((hash) >> 32) & (mask)) | 1) /* always odd */ |
55 | #define hash_pos_next(pos, inc, mask) (((pos) + (inc)) & (mask)) |
56 | |
57 | static struct hash_tbl_node *alloc_table(size_t newsize) |
58 | { |
59 | size_t bytes = newsize * sizeof(struct hash_tbl_node); |
60 | return nasm_zalloc(bytes); |
61 | } |
62 | |
63 | void hash_init(struct hash_table *head, size_t size) |
64 | { |
65 | nasm_assert(is_power2(size)); |
66 | head->table = alloc_table(size); |
67 | head->load = 0; |
68 | head->size = size; |
69 | head->max_load = hash_max_load(size); |
70 | } |
71 | |
72 | /* |
73 | * Find an entry in a hash table. |
74 | * |
75 | * On failure, if "insert" is non-NULL, store data in that structure |
76 | * which can be used to insert that node using hash_add(). |
77 | * |
78 | * WARNING: this data is only valid until the very next call of |
79 | * hash_add(); it cannot be "saved" to a later date. |
80 | * |
81 | * On success, return a pointer to the "data" element of the hash |
82 | * structure. |
83 | */ |
84 | void **hash_find(struct hash_table *head, const char *key, |
85 | struct hash_insert *insert) |
86 | { |
87 | struct hash_tbl_node *np; |
88 | struct hash_tbl_node *tbl = head->table; |
89 | uint64_t hash = hash_calc(key); |
90 | size_t mask = hash_mask(head->size); |
91 | size_t pos = hash_pos(hash, mask); |
92 | size_t inc = hash_inc(hash, mask); |
93 | |
94 | while ((np = &tbl[pos])->key) { |
95 | if (hash == np->hash && !strcmp(key, np->key)) |
96 | return &np->data; |
97 | pos = hash_pos_next(pos, inc, mask); |
98 | } |
99 | |
100 | /* Not found. Store info for insert if requested. */ |
101 | if (insert) { |
102 | insert->head = head; |
103 | insert->hash = hash; |
104 | insert->where = np; |
105 | } |
106 | return NULL; |
107 | } |
108 | |
109 | /* |
110 | * Same as hash_find, but for case-insensitive hashing. |
111 | */ |
112 | void **hash_findi(struct hash_table *head, const char *key, |
113 | struct hash_insert *insert) |
114 | { |
115 | struct hash_tbl_node *np; |
116 | struct hash_tbl_node *tbl = head->table; |
117 | uint64_t hash = hash_calci(key); |
118 | size_t mask = hash_mask(head->size); |
119 | size_t pos = hash_pos(hash, mask); |
120 | size_t inc = hash_inc(hash, mask); |
121 | |
122 | while ((np = &tbl[pos])->key) { |
123 | if (hash == np->hash && !nasm_stricmp(key, np->key)) |
124 | return &np->data; |
125 | pos = hash_pos_next(pos, inc, mask); |
126 | } |
127 | |
128 | /* Not found. Store info for insert if requested. */ |
129 | if (insert) { |
130 | insert->head = head; |
131 | insert->hash = hash; |
132 | insert->where = np; |
133 | } |
134 | return NULL; |
135 | } |
136 | |
137 | /* |
138 | * Insert node. Return a pointer to the "data" element of the newly |
139 | * created hash node. |
140 | */ |
141 | void **hash_add(struct hash_insert *insert, const char *key, void *data) |
142 | { |
143 | struct hash_table *head = insert->head; |
144 | struct hash_tbl_node *np = insert->where; |
145 | |
146 | /* |
147 | * Insert node. We can always do this, even if we need to |
148 | * rebalance immediately after. |
149 | */ |
150 | np->hash = insert->hash; |
151 | np->key = key; |
152 | np->data = data; |
153 | |
154 | if (++head->load > head->max_load) { |
155 | /* Need to expand the table */ |
156 | size_t newsize = hash_expand(head->size); |
157 | struct hash_tbl_node *newtbl = alloc_table(newsize); |
158 | size_t mask = hash_mask(newsize); |
159 | |
160 | if (head->table) { |
161 | struct hash_tbl_node *op, *xp; |
162 | size_t i; |
163 | |
164 | /* Rebalance all the entries */ |
165 | for (i = 0, op = head->table; i < head->size; i++, op++) { |
166 | if (op->key) { |
167 | size_t pos = hash_pos(op->hash, mask); |
168 | size_t inc = hash_inc(op->hash, mask); |
169 | |
170 | while ((xp = &newtbl[pos])->key) |
171 | pos = hash_pos_next(pos, inc, mask); |
172 | |
173 | *xp = *op; |
174 | if (op == np) |
175 | np = xp; |
176 | } |
177 | } |
178 | nasm_free(head->table); |
179 | } |
180 | |
181 | head->table = newtbl; |
182 | head->size = newsize; |
183 | head->max_load = hash_max_load(newsize); |
184 | } |
185 | |
186 | return &np->data; |
187 | } |
188 | |
189 | /* |
190 | * Iterate over all members of a hash set. For the first call, |
191 | * iterator should be initialized to NULL. Returns the data pointer, |
192 | * or NULL on failure. |
193 | */ |
194 | void *hash_iterate(const struct hash_table *head, |
195 | struct hash_tbl_node **iterator, |
196 | const char **key) |
197 | { |
198 | struct hash_tbl_node *np = *iterator; |
199 | struct hash_tbl_node *ep = head->table + head->size; |
200 | |
201 | if (!np) { |
202 | np = head->table; |
203 | if (!np) |
204 | return NULL; /* Uninitialized table */ |
205 | } |
206 | |
207 | while (np < ep) { |
208 | if (np->key) { |
209 | *iterator = np + 1; |
210 | if (key) |
211 | *key = np->key; |
212 | return np->data; |
213 | } |
214 | np++; |
215 | } |
216 | |
217 | *iterator = NULL; |
218 | if (key) |
219 | *key = NULL; |
220 | return NULL; |
221 | } |
222 | |
223 | /* |
224 | * Free the hash itself. Doesn't free the data elements; use |
225 | * hash_iterate() to do that first, if needed. This function is normally |
226 | * used when the hash data entries are either freed separately, or |
227 | * compound objects which can't be freed in a single operation. |
228 | */ |
229 | void hash_free(struct hash_table *head) |
230 | { |
231 | void *p = head->table; |
232 | head->table = NULL; |
233 | nasm_free(p); |
234 | } |
235 | |
236 | /* |
237 | * Frees the hash *and* all data elements. This is applicable only in |
238 | * the case where the data element is a single allocation. If the |
239 | * second argument is false, the key string is part of the data |
240 | * allocation or belongs to an allocation which will be freed |
241 | * separately, if it is true the keys are also freed. |
242 | */ |
243 | void hash_free_all(struct hash_table *head, bool free_keys) |
244 | { |
245 | struct hash_tbl_node *iter = NULL; |
246 | const char *keyp; |
247 | void *d; |
248 | |
249 | while ((d = hash_iterate(head, &iter, &keyp))) { |
250 | nasm_free(d); |
251 | if (free_keys) |
252 | nasm_free((void *)keyp); |
253 | } |
254 | |
255 | hash_free(head); |
256 | } |
257 | |