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
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 * ----------------------------------------------------------------------- */
37 * Efficient dictionary hash table class.
47 #define HASH_MAX_LOAD 2 /* Higher = more memory-efficient, slower */
49 static struct hash_tbl_node *alloc_table(size_t newsize)
51 size_t bytes = newsize*sizeof(struct hash_tbl_node);
52 struct hash_tbl_node *newtbl = nasm_zalloc(bytes);
57 void hash_init(struct hash_table *head, size_t size)
59 head->table = alloc_table(size);
62 head->max_load = size*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
66 * Find an entry in a hash table.
68 * On failure, if "insert" is non-NULL, store data in that structure
69 * which can be used to insert that node using hash_add().
71 * WARNING: this data is only valid until the very next call of
72 * hash_add(); it cannot be "saved" to a later date.
74 * On success, return a pointer to the "data" element of the hash
77 void **hash_find(struct hash_table *head, const char *key,
78 struct hash_insert *insert)
80 struct hash_tbl_node *np;
81 uint64_t hash = crc64(CRC64_INIT, key);
82 struct hash_tbl_node *tbl = head->table;
83 size_t mask = head->size-1;
84 size_t pos = hash & mask;
85 size_t inc = ((hash >> 32) & mask) | 1; /* Always odd */
87 while ((np = &tbl[pos])->key) {
88 if (hash == np->hash && !strcmp(key, np->key))
90 pos = (pos+inc) & mask;
93 /* Not found. Store info for insert if requested. */
103 * Same as hash_find, but for case-insensitive hashing.
105 void **hash_findi(struct hash_table *head, const char *key,
106 struct hash_insert *insert)
108 struct hash_tbl_node *np;
109 uint64_t hash = crc64i(CRC64_INIT, key);
110 struct hash_tbl_node *tbl = head->table;
111 size_t mask = head->size-1;
112 size_t pos = hash & mask;
113 size_t inc = ((hash >> 32) & mask) | 1; /* Always odd */
115 while ((np = &tbl[pos])->key) {
116 if (hash == np->hash && !nasm_stricmp(key, np->key))
118 pos = (pos+inc) & mask;
121 /* Not found. Store info for insert if requested. */
131 * Insert node. Return a pointer to the "data" element of the newly
134 void **hash_add(struct hash_insert *insert, const char *key, void *data)
136 struct hash_table *head = insert->head;
137 struct hash_tbl_node *np = insert->where;
139 /* Insert node. We can always do this, even if we need to
140 rebalance immediately after. */
141 np->hash = insert->hash;
145 if (++head->load > head->max_load) {
146 /* Need to expand the table */
147 size_t newsize = head->size << 1;
148 struct hash_tbl_node *newtbl = alloc_table(newsize);
149 size_t mask = newsize-1;
152 struct hash_tbl_node *op, *xp;
155 /* Rebalance all the entries */
156 for (i = 0, op = head->table; i < head->size; i++, op++) {
158 size_t pos = op->hash & mask;
159 size_t inc = ((op->hash >> 32) & mask) | 1;
161 while ((xp = &newtbl[pos])->key)
162 pos = (pos+inc) & mask;
169 nasm_free(head->table);
172 head->table = newtbl;
173 head->size = newsize;
174 head->max_load = newsize*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
181 * Iterate over all members of a hash set. For the first call,
182 * iterator should be initialized to NULL. Returns the data pointer,
183 * or NULL on failure.
185 void *hash_iterate(const struct hash_table *head,
186 struct hash_tbl_node **iterator,
189 struct hash_tbl_node *np = *iterator;
190 struct hash_tbl_node *ep = head->table + head->size;
195 return NULL; /* Uninitialized table */
215 * Free the hash itself. Doesn't free the data elements; use
216 * hash_iterate() to do that first, if needed.
218 void hash_free(struct hash_table *head)
220 void *p = head->table;