|
10554
|
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.
|
|
|
226 */
|
|
|
227 void hash_free(struct hash_table *head)
|
|
|
228 {
|
|
|
229 void *p = head->table;
|
|
|
230 head->table = NULL;
|
|
|
231 nasm_free(p);
|
|
|
232 }
|
