2 * Generic implementation of hash-based key value mappings.
7 #define FNV32_BASE ((unsigned int) 0x811c9dc5)
8 #define FNV32_PRIME ((unsigned int) 0x01000193)
10 unsigned int strhash(const char *str
)
12 unsigned int c
, hash
= FNV32_BASE
;
13 while ((c
= (unsigned char) *str
++))
14 hash
= (hash
* FNV32_PRIME
) ^ c
;
18 unsigned int strihash(const char *str
)
20 unsigned int c
, hash
= FNV32_BASE
;
21 while ((c
= (unsigned char) *str
++)) {
22 if (c
>= 'a' && c
<= 'z')
24 hash
= (hash
* FNV32_PRIME
) ^ c
;
29 unsigned int memhash(const void *buf
, size_t len
)
31 unsigned int hash
= FNV32_BASE
;
32 unsigned char *ucbuf
= (unsigned char *) buf
;
34 unsigned int c
= *ucbuf
++;
35 hash
= (hash
* FNV32_PRIME
) ^ c
;
40 unsigned int memihash(const void *buf
, size_t len
)
42 unsigned int hash
= FNV32_BASE
;
43 unsigned char *ucbuf
= (unsigned char *) buf
;
45 unsigned int c
= *ucbuf
++;
46 if (c
>= 'a' && c
<= 'z')
48 hash
= (hash
* FNV32_PRIME
) ^ c
;
54 * Incoporate another chunk of data into a memihash
57 unsigned int memihash_cont(unsigned int hash_seed
, const void *buf
, size_t len
)
59 unsigned int hash
= hash_seed
;
60 unsigned char *ucbuf
= (unsigned char *) buf
;
62 unsigned int c
= *ucbuf
++;
63 if (c
>= 'a' && c
<= 'z')
65 hash
= (hash
* FNV32_PRIME
) ^ c
;
70 #define HASHMAP_INITIAL_SIZE 64
71 /* grow / shrink by 2^2 */
72 #define HASHMAP_RESIZE_BITS 2
73 /* load factor in percent */
74 #define HASHMAP_LOAD_FACTOR 80
76 static void alloc_table(struct hashmap
*map
, unsigned int size
)
78 map
->tablesize
= size
;
79 map
->table
= xcalloc(size
, sizeof(struct hashmap_entry
*));
81 /* calculate resize thresholds for new size */
82 map
->grow_at
= (unsigned int) ((uint64_t) size
* HASHMAP_LOAD_FACTOR
/ 100);
83 if (size
<= HASHMAP_INITIAL_SIZE
)
87 * The shrink-threshold must be slightly smaller than
88 * (grow-threshold / resize-factor) to prevent erratic resizing,
89 * thus we divide by (resize-factor + 1).
91 map
->shrink_at
= map
->grow_at
/ ((1 << HASHMAP_RESIZE_BITS
) + 1);
94 static inline int entry_equals(const struct hashmap
*map
,
95 const struct hashmap_entry
*e1
, const struct hashmap_entry
*e2
,
98 return (e1
== e2
) || (e1
->hash
== e2
->hash
&& !map
->cmpfn(e1
, e2
, keydata
));
101 static inline unsigned int bucket(const struct hashmap
*map
,
102 const struct hashmap_entry
*key
)
104 return key
->hash
& (map
->tablesize
- 1);
107 static void rehash(struct hashmap
*map
, unsigned int newsize
)
109 unsigned int i
, oldsize
= map
->tablesize
;
110 struct hashmap_entry
**oldtable
= map
->table
;
112 alloc_table(map
, newsize
);
113 for (i
= 0; i
< oldsize
; i
++) {
114 struct hashmap_entry
*e
= oldtable
[i
];
116 struct hashmap_entry
*next
= e
->next
;
117 unsigned int b
= bucket(map
, e
);
118 e
->next
= map
->table
[b
];
126 static inline struct hashmap_entry
**find_entry_ptr(const struct hashmap
*map
,
127 const struct hashmap_entry
*key
, const void *keydata
)
129 struct hashmap_entry
**e
= &map
->table
[bucket(map
, key
)];
130 while (*e
&& !entry_equals(map
, *e
, key
, keydata
))
135 static int always_equal(const void *unused1
, const void *unused2
, const void *unused3
)
140 void hashmap_init(struct hashmap
*map
, hashmap_cmp_fn equals_function
,
143 unsigned int size
= HASHMAP_INITIAL_SIZE
;
145 map
->cmpfn
= equals_function
? equals_function
: always_equal
;
147 /* calculate initial table size and allocate the table */
148 initial_size
= (unsigned int) ((uint64_t) initial_size
* 100
149 / HASHMAP_LOAD_FACTOR
);
150 while (initial_size
> size
)
151 size
<<= HASHMAP_RESIZE_BITS
;
152 alloc_table(map
, size
);
155 void hashmap_free(struct hashmap
*map
, int free_entries
)
157 if (!map
|| !map
->table
)
160 struct hashmap_iter iter
;
161 struct hashmap_entry
*e
;
162 hashmap_iter_init(map
, &iter
);
163 while ((e
= hashmap_iter_next(&iter
)))
167 memset(map
, 0, sizeof(*map
));
170 void *hashmap_get(const struct hashmap
*map
, const void *key
, const void *keydata
)
172 return *find_entry_ptr(map
, key
, keydata
);
175 void *hashmap_get_next(const struct hashmap
*map
, const void *entry
)
177 struct hashmap_entry
*e
= ((struct hashmap_entry
*) entry
)->next
;
178 for (; e
; e
= e
->next
)
179 if (entry_equals(map
, entry
, e
, NULL
))
184 void hashmap_add(struct hashmap
*map
, void *entry
)
186 unsigned int b
= bucket(map
, entry
);
189 ((struct hashmap_entry
*) entry
)->next
= map
->table
[b
];
190 map
->table
[b
] = entry
;
192 /* fix size and rehash if appropriate */
194 if (map
->size
> map
->grow_at
)
195 rehash(map
, map
->tablesize
<< HASHMAP_RESIZE_BITS
);
198 void *hashmap_remove(struct hashmap
*map
, const void *key
, const void *keydata
)
200 struct hashmap_entry
*old
;
201 struct hashmap_entry
**e
= find_entry_ptr(map
, key
, keydata
);
205 /* remove existing entry */
210 /* fix size and rehash if appropriate */
212 if (map
->size
< map
->shrink_at
)
213 rehash(map
, map
->tablesize
>> HASHMAP_RESIZE_BITS
);
217 void *hashmap_put(struct hashmap
*map
, void *entry
)
219 struct hashmap_entry
*old
= hashmap_remove(map
, entry
, NULL
);
220 hashmap_add(map
, entry
);
224 void hashmap_iter_init(struct hashmap
*map
, struct hashmap_iter
*iter
)
231 void *hashmap_iter_next(struct hashmap_iter
*iter
)
233 struct hashmap_entry
*current
= iter
->next
;
236 iter
->next
= current
->next
;
240 if (iter
->tablepos
>= iter
->map
->tablesize
)
243 current
= iter
->map
->table
[iter
->tablepos
++];
248 struct hashmap_entry ent
;
250 unsigned char data
[FLEX_ARRAY
];
253 static int pool_entry_cmp(const struct pool_entry
*e1
,
254 const struct pool_entry
*e2
,
255 const unsigned char *keydata
)
257 return e1
->data
!= keydata
&&
258 (e1
->len
!= e2
->len
|| memcmp(e1
->data
, keydata
, e1
->len
));
261 const void *memintern(const void *data
, size_t len
)
263 static struct hashmap map
;
264 struct pool_entry key
, *e
;
266 /* initialize string pool hashmap */
268 hashmap_init(&map
, (hashmap_cmp_fn
) pool_entry_cmp
, 0);
270 /* lookup interned string in pool */
271 hashmap_entry_init(&key
, memhash(data
, len
));
273 e
= hashmap_get(&map
, &key
, data
);
275 /* not found: create it */
276 FLEX_ALLOC_MEM(e
, data
, data
, len
);
277 hashmap_entry_init(e
, key
.ent
.hash
);
279 hashmap_add(&map
, e
);