4 * Efficient dictionary hash table class.
12 #define HASH_INITIAL_SIZE 64
13 #define HASH_MAX_LOAD 2 /* Higher = more memory-efficient, slower */
15 static struct hash_tbl_node *alloc_table(size_t newsize)
17 size_t bytes = newsize*sizeof(struct hash_tbl_node);
18 struct hash_tbl_node *newtbl = nasm_malloc(bytes);
20 memset(newtbl, 0, 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 void *hash_find(struct hash_table *head, const char *key,
47 struct hash_insert *insert)
49 struct hash_tbl_node *np;
50 uint64_t hash = crc64(key);
51 struct hash_tbl_node *tbl = head->table;
52 size_t mask = head->size-1;
53 size_t pos = hash & mask;
54 size_t inc = ((hash >> 32) & mask) | 1; /* Always odd */
56 while ((np = &tbl[pos])->key) {
57 if (hash == np->hash && !strcmp(key, np->key))
59 pos = (pos+inc) & mask;
62 /* Not found. Store info for insert if requested. */
74 void hash_add(struct hash_insert *insert, const char *key, void *data)
76 struct hash_table *head = insert->head;
77 struct hash_tbl_node *np = insert->where;
79 /* Insert node. We can always do this, even if we need to
80 rebalance immediately after. */
81 np->hash = insert->hash;
85 if (++head->load > head->max_load) {
86 /* Need to expand the table */
87 size_t newsize = head->size << 1;
88 struct hash_tbl_node *newtbl = alloc_table(newsize);
89 size_t mask = newsize-1;
92 struct hash_tbl_node *op;
95 /* Rebalance all the entries */
96 for (i = 0, op = head->table; i < head->size; i++, op++) {
98 size_t pos = op->hash & mask;
99 size_t inc = ((op->hash >> 32) & mask) | 1;
101 while ((np = &newtbl[pos])->data)
102 pos = (pos+inc) & mask;
107 nasm_free(head->table);
110 head->table = newtbl;
111 head->size = newsize;
112 head->max_load = newsize*(HASH_MAX_LOAD-1)/HASH_MAX_LOAD;
116 void hash_free(struct hash_table *head, void (*free_func)(char *, void *))
119 struct hash_tbl_node *op;
121 for (i = 0, op = head->table; i < head->size; i++, op++) {
123 free_func((char *)op->key, op->data);
126 nasm_free(head->table);