4 * Efficient dictionary hash table class.
14 #define HASH_INITIAL_SIZE 64
15 #define HASH_MAX_LOAD 2 /* Higher = more memory-efficient, slower */
17 static struct hash_tbl_node *alloc_table(size_t newsize)
19 size_t bytes = newsize*sizeof(struct hash_tbl_node);
20 struct hash_tbl_node *newtbl = nasm_zalloc(bytes);
25 struct hash_table *hash_init(void)
27 struct hash_table *head = nasm_malloc(sizeof(struct hash_table));
29 head->table = alloc_table(HASH_INITIAL_SIZE);
31 head->size = HASH_INITIAL_SIZE;
32 head->max_load = HASH_INITIAL_SIZE*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
38 * Find an entry in a hash table.
40 * On failure, if "insert" is non-NULL, store data in that structure
41 * which can be used to insert that node using hash_add().
43 * WARNING: this data is only valid until the very next call of
44 * hash_add(); it cannot be "saved" to a later date.
46 * On success, return a pointer to the "data" element of the hash
49 void **hash_find(struct hash_table *head, const char *key,
50 struct hash_insert *insert)
52 struct hash_tbl_node *np;
53 uint64_t hash = crc64(CRC64_INIT, key);
54 struct hash_tbl_node *tbl = head->table;
55 size_t mask = head->size-1;
56 size_t pos = hash & mask;
57 size_t inc = ((hash >> 32) & mask) | 1; /* Always odd */
59 while ((np = &tbl[pos])->key) {
60 if (hash == np->hash && !strcmp(key, np->key))
62 pos = (pos+inc) & mask;
65 /* Not found. Store info for insert if requested. */
75 * Same as hash_find, but for case-insensitive hashing.
77 void **hash_findi(struct hash_table *head, const char *key,
78 struct hash_insert *insert)
80 struct hash_tbl_node *np;
81 uint64_t hash = crc64i(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 && !nasm_stricmp(key, np->key))
90 pos = (pos+inc) & mask;
93 /* Not found. Store info for insert if requested. */
103 * Insert node. Return a pointer to the "data" element of the newly
106 void **hash_add(struct hash_insert *insert, const char *key, void *data)
108 struct hash_table *head = insert->head;
109 struct hash_tbl_node *np = insert->where;
111 /* Insert node. We can always do this, even if we need to
112 rebalance immediately after. */
113 np->hash = insert->hash;
117 if (++head->load > head->max_load) {
118 /* Need to expand the table */
119 size_t newsize = head->size << 1;
120 struct hash_tbl_node *newtbl = alloc_table(newsize);
121 size_t mask = newsize-1;
124 struct hash_tbl_node *op, *xp;
127 /* Rebalance all the entries */
128 for (i = 0, op = head->table; i < head->size; i++, op++) {
130 size_t pos = op->hash & mask;
131 size_t inc = ((op->hash >> 32) & mask) | 1;
133 while ((xp = &newtbl[pos])->key)
134 pos = (pos+inc) & mask;
141 nasm_free(head->table);
144 head->table = newtbl;
145 head->size = newsize;
146 head->max_load = newsize*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
153 * Iterate over all members of a hash set. For the first call,
154 * iterator should be initialized to NULL. Returns the data pointer,
155 * or NULL on failure.
157 void *hash_iterate(const struct hash_table *head,
158 struct hash_tbl_node **iterator,
161 struct hash_tbl_node *np = *iterator;
162 struct hash_tbl_node *ep = head->table + head->size;
184 * Free the hash itself. Doesn't free the data elements; use
185 * hash_iterate() to do that first, if needed.
187 void hash_free(struct hash_table *head)
189 nasm_free(head->table);