preproc.c: completed deprecation of MMacro structure
[nasm.git] / hashtbl.c
blob348bc40df99ce359f9d8bd709c518c83b4887d18
1 /* ----------------------------------------------------------------------- *
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.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following
9 * conditions are met:
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.
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.
32 * ----------------------------------------------------------------------- */
35 * hashtbl.c
37 * Efficient dictionary hash table class.
40 #include "compiler.h"
42 #include <inttypes.h>
43 #include <string.h>
44 #include "nasm.h"
45 #include "hashtbl.h"
47 #define HASH_MAX_LOAD 2 /* Higher = more memory-efficient, slower */
49 #define hash_calc(key) crc64(CRC64_INIT, (key))
50 #define hash_calci(key) crc64i(CRC64_INIT, (key))
51 #define hash_max_load(size) ((size) * (HASH_MAX_LOAD - 1) / HASH_MAX_LOAD)
52 #define hash_expand(size) ((size) << 1)
53 #define hash_mask(size) ((size) - 1)
54 #define hash_pos(hash, mask) ((hash) & (mask))
55 #define hash_inc(hash, mask) ((((hash) >> 32) & (mask)) | 1) /* always odd */
56 #define hash_pos_next(pos, inc, mask) (((pos) + (inc)) & (mask))
58 static struct hash_tbl_node *alloc_table(size_t newsize)
60 size_t bytes = newsize * sizeof(struct hash_tbl_node);
61 return nasm_zalloc(bytes);
64 void hash_init(struct hash_table *head, size_t size)
66 nasm_assert(is_power2(size));
67 head->table = alloc_table(size);
68 head->load = 0;
69 head->size = size;
70 head->max_load = hash_max_load(size);
74 * Find an entry in a hash table.
76 * On failure, if "insert" is non-NULL, store data in that structure
77 * which can be used to insert that node using hash_add().
79 * WARNING: this data is only valid until the very next call of
80 * hash_add(); it cannot be "saved" to a later date.
82 * On success, return a pointer to the "data" element of the hash
83 * structure.
85 void **hash_find(struct hash_table *head, const char *key,
86 struct hash_insert *insert)
88 struct hash_tbl_node *np;
89 struct hash_tbl_node *tbl = head->table;
90 uint64_t hash = hash_calc(key);
91 size_t mask = hash_mask(head->size);
92 size_t pos = hash_pos(hash, mask);
93 size_t inc = hash_inc(hash, mask);
95 while ((np = &tbl[pos])->key) {
96 if (hash == np->hash && !strcmp(key, np->key))
97 return &np->data;
98 pos = hash_pos_next(pos, inc, mask);
101 /* Not found. Store info for insert if requested. */
102 if (insert) {
103 insert->head = head;
104 insert->hash = hash;
105 insert->where = np;
107 return NULL;
111 * Same as hash_find, but for case-insensitive hashing.
113 void **hash_findi(struct hash_table *head, const char *key,
114 struct hash_insert *insert)
116 struct hash_tbl_node *np;
117 struct hash_tbl_node *tbl = head->table;
118 uint64_t hash = hash_calci(key);
119 size_t mask = hash_mask(head->size);
120 size_t pos = hash_pos(hash, mask);
121 size_t inc = hash_inc(hash, mask);
123 while ((np = &tbl[pos])->key) {
124 if (hash == np->hash && !nasm_stricmp(key, np->key))
125 return &np->data;
126 pos = hash_pos_next(pos, inc, mask);
129 /* Not found. Store info for insert if requested. */
130 if (insert) {
131 insert->head = head;
132 insert->hash = hash;
133 insert->where = np;
135 return NULL;
139 * Insert node. Return a pointer to the "data" element of the newly
140 * created hash node.
142 void **hash_add(struct hash_insert *insert, const char *key, void *data)
144 struct hash_table *head = insert->head;
145 struct hash_tbl_node *np = insert->where;
148 * Insert node. We can always do this, even if we need to
149 * rebalance immediately after.
151 np->hash = insert->hash;
152 np->key = key;
153 np->data = data;
155 if (++head->load > head->max_load) {
156 /* Need to expand the table */
157 size_t newsize = hash_expand(head->size);
158 struct hash_tbl_node *newtbl = alloc_table(newsize);
159 size_t mask = hash_mask(newsize);
161 if (head->table) {
162 struct hash_tbl_node *op, *xp;
163 size_t i;
165 /* Rebalance all the entries */
166 for (i = 0, op = head->table; i < head->size; i++, op++) {
167 if (op->key) {
168 size_t pos = hash_pos(op->hash, mask);
169 size_t inc = hash_inc(op->hash, mask);
171 while ((xp = &newtbl[pos])->key)
172 pos = hash_pos_next(pos, inc, mask);
174 *xp = *op;
175 if (op == np)
176 np = xp;
179 nasm_free(head->table);
182 head->table = newtbl;
183 head->size = newsize;
184 head->max_load = hash_max_load(newsize);
187 return &np->data;
191 * Iterate over all members of a hash set. For the first call,
192 * iterator should be initialized to NULL. Returns the data pointer,
193 * or NULL on failure.
195 void *hash_iterate(const struct hash_table *head,
196 struct hash_tbl_node **iterator,
197 const char **key)
199 struct hash_tbl_node *np = *iterator;
200 struct hash_tbl_node *ep = head->table + head->size;
202 if (!np) {
203 np = head->table;
204 if (!np)
205 return NULL; /* Uninitialized table */
208 while (np < ep) {
209 if (np->key) {
210 *iterator = np + 1;
211 if (key)
212 *key = np->key;
213 return np->data;
215 np++;
218 *iterator = NULL;
219 if (key)
220 *key = NULL;
221 return NULL;
225 * Free the hash itself. Doesn't free the data elements; use
226 * hash_iterate() to do that first, if needed.
228 void hash_free(struct hash_table *head)
230 void *p = head->table;
231 head->table = NULL;
232 nasm_free(p);