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
57static 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
63void 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 */
84void **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 */
112void **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 */
141void **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 */
194void *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 */
229void 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 */
243void 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