4 * Efficient dictionary hash table class.
14 #define HASH_MAX_LOAD 2 /* Higher = more memory-efficient, slower */
16 static struct hash_tbl_node *alloc_table(size_t newsize)
18 size_t bytes = newsize*sizeof(struct hash_tbl_node);
19 struct hash_tbl_node *newtbl = nasm_zalloc(bytes);
24 void hash_init(struct hash_table *head, size_t size)
26 head->table = alloc_table(size);
29 head->max_load = size*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
33 * Find an entry in a hash table.
35 * On failure, if "insert" is non-NULL, store data in that structure
36 * which can be used to insert that node using hash_add().
38 * WARNING: this data is only valid until the very next call of
39 * hash_add(); it cannot be "saved" to a later date.
41 * On success, return a pointer to the "data" element of the hash
44 void **hash_find(struct hash_table *head, const char *key,
45 struct hash_insert *insert)
47 struct hash_tbl_node *np;
48 uint64_t hash = crc64(CRC64_INIT, key);
49 struct hash_tbl_node *tbl = head->table;
50 size_t mask = head->size-1;
51 size_t pos = hash & mask;
52 size_t inc = ((hash >> 32) & mask) | 1; /* Always odd */
54 while ((np = &tbl[pos])->key) {
55 if (hash == np->hash && !strcmp(key, np->key))
57 pos = (pos+inc) & mask;
60 /* Not found. Store info for insert if requested. */
70 * Same as hash_find, but for case-insensitive hashing.
72 void **hash_findi(struct hash_table *head, const char *key,
73 struct hash_insert *insert)
75 struct hash_tbl_node *np;
76 uint64_t hash = crc64i(CRC64_INIT, key);
77 struct hash_tbl_node *tbl = head->table;
78 size_t mask = head->size-1;
79 size_t pos = hash & mask;
80 size_t inc = ((hash >> 32) & mask) | 1; /* Always odd */
82 while ((np = &tbl[pos])->key) {
83 if (hash == np->hash && !nasm_stricmp(key, np->key))
85 pos = (pos+inc) & mask;
88 /* Not found. Store info for insert if requested. */
98 * Insert node. Return a pointer to the "data" element of the newly
101 void **hash_add(struct hash_insert *insert, const char *key, void *data)
103 struct hash_table *head = insert->head;
104 struct hash_tbl_node *np = insert->where;
106 /* Insert node. We can always do this, even if we need to
107 rebalance immediately after. */
108 np->hash = insert->hash;
112 if (++head->load > head->max_load) {
113 /* Need to expand the table */
114 size_t newsize = head->size << 1;
115 struct hash_tbl_node *newtbl = alloc_table(newsize);
116 size_t mask = newsize-1;
119 struct hash_tbl_node *op, *xp;
122 /* Rebalance all the entries */
123 for (i = 0, op = head->table; i < head->size; i++, op++) {
125 size_t pos = op->hash & mask;
126 size_t inc = ((op->hash >> 32) & mask) | 1;
128 while ((xp = &newtbl[pos])->key)
129 pos = (pos+inc) & mask;
136 nasm_free(head->table);
139 head->table = newtbl;
140 head->size = newsize;
141 head->max_load = newsize*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
148 * Iterate over all members of a hash set. For the first call,
149 * iterator should be initialized to NULL. Returns the data pointer,
150 * or NULL on failure.
152 void *hash_iterate(const struct hash_table *head,
153 struct hash_tbl_node **iterator,
156 struct hash_tbl_node *np = *iterator;
157 struct hash_tbl_node *ep = head->table + head->size;
179 * Free the hash itself. Doesn't free the data elements; use
180 * hash_iterate() to do that first, if needed.
182 void hash_free(struct hash_table *head)
184 void *p = head->table;