1 #include "tpl_internal.h"
3 struct tpl_util_map_entry {
6 tpl_free_func_t free_func;
7 tpl_util_map_entry_t *next;
11 __get_bucket_index(tpl_util_map_t *map, const tpl_util_key_t key)
16 if (map->key_length_func) key_length = map->key_length_func(key);
18 hash = map->hash_func(key, key_length);
19 return hash & map->bucket_mask;
22 static inline tpl_util_map_entry_t **
23 __get_bucket(tpl_util_map_t *map, const tpl_util_key_t key)
25 return &map->buckets[__get_bucket_index(map, key)];
29 __int64_hash(const tpl_util_key_t key, int key_length)
31 uint64_t _key = key.key64;
33 /* Hash functions from Thomas Wang https://gist.github.com/badboy/6267743 */
34 _key = ~_key + (_key << 18);
45 __int64_key_compare(const tpl_util_key_t key0, int key0_length,
46 const tpl_util_key_t key1, int key1_length)
48 return (int)(key0.key64 - key1.key64);
52 __int32_hash(const tpl_util_key_t key, int key_length)
54 uint32_t _key = (uint32_t)key.key32;
56 /* Hash functions from Thomas Wang https://gist.github.com/badboy/6267743 */
57 _key = ~_key + (_key << 15);
68 __int32_key_compare(const tpl_util_key_t key0, int key0_length,
69 const tpl_util_key_t key1, int key1_length)
71 return (int)(key0.key32 - key1.key32);
75 __pointer_hash(const tpl_util_key_t key, int key_length)
77 #if INTPTR_MAX == INT32_MAX
78 uint32_t _key = (uint32_t)key.ptr;
80 _key = ~_key + (_key << 15);
88 #elif INTPTR_MAX == INT64_MAX
89 uint64_t _key = (uint64_t)key.ptr;
91 _key = ~_key + (_key << 18);
100 #error "Not 32 or 64bit system"
107 __pointer_key_compare(const tpl_util_key_t key0, int key0_length,
108 const tpl_util_key_t key1, int key1_length)
110 return (int)(key0.ptr - key1.ptr);
114 tpl_util_map_init(tpl_util_map_t *map, int bucket_bits,
115 tpl_util_hash_func_t hash_func,
116 tpl_util_key_length_func_t key_length_func,
117 tpl_util_key_compare_func_t key_compare_func,
120 map->hash_func = hash_func;
121 map->key_length_func = key_length_func;
122 map->key_compare_func = key_compare_func;
124 map->bucket_bits = bucket_bits;
125 map->bucket_size = 1 << bucket_bits;
126 map->bucket_mask = map->bucket_size - 1;
128 map->buckets = buckets;
132 tpl_util_map_int32_init(tpl_util_map_t *map, int bucket_bits, void *buckets)
134 tpl_util_map_init(map, bucket_bits, __int32_hash, NULL,
135 __int32_key_compare, buckets);
139 tpl_util_map_int64_init(tpl_util_map_t *map, int bucket_bits, void *buckets)
141 tpl_util_map_init(map, bucket_bits, __int64_hash, NULL,
142 __int64_key_compare, buckets);
146 tpl_util_map_pointer_init(tpl_util_map_t *map, int bucket_bits, void *buckets)
148 tpl_util_map_init(map, bucket_bits, __pointer_hash, NULL,
149 __pointer_key_compare, buckets);
153 tpl_util_map_fini(tpl_util_map_t *map)
155 tpl_util_map_clear(map);
159 tpl_util_map_create(int bucket_bits, tpl_util_hash_func_t hash_func,
160 tpl_util_key_length_func_t key_length_func,
161 tpl_util_key_compare_func_t key_compare_func)
164 int bucket_size = 1 << bucket_bits;
167 sizeof(tpl_util_map_t) + bucket_size * sizeof(tpl_util_map_entry_t *));
168 TPL_CHECK_ON_FALSE_RETURN_VAL(map, NULL);
170 tpl_util_map_init(map, bucket_bits, hash_func, key_length_func,
171 key_compare_func, map + 1);
177 tpl_util_map_int32_create(int bucket_bits)
179 return tpl_util_map_create(bucket_bits, __int32_hash, NULL,
180 __int32_key_compare);
184 tpl_util_map_int64_create(int bucket_bits)
186 return tpl_util_map_create(bucket_bits, __int64_hash, NULL,
187 __int64_key_compare);
191 tpl_util_map_pointer_create(int bucket_bits)
193 return tpl_util_map_create(bucket_bits, __pointer_hash, NULL,
194 __pointer_key_compare);
198 tpl_util_map_destroy(tpl_util_map_t *map)
200 tpl_util_map_fini(map);
205 tpl_util_map_clear(tpl_util_map_t *map)
209 if (!map->buckets) return;
211 for (i = 0; i < map->bucket_size; i++) {
212 tpl_util_map_entry_t *curr = map->buckets[i];
215 tpl_util_map_entry_t *next = curr->next;
217 if (curr->free_func) curr->free_func(curr->data);
224 memset(map->buckets, 0x00, map->bucket_size * sizeof(tpl_util_map_entry_t *));
228 tpl_util_map_get(tpl_util_map_t *map, const tpl_util_key_t key)
230 tpl_util_map_entry_t *curr = *__get_bucket(map, key);
236 if (map->key_length_func) {
237 len0 = map->key_length_func(curr->key);
238 len1 = map->key_length_func(key);
241 if (map->key_compare_func(curr->key, len0, key, len1) == 0)
251 tpl_util_map_set(tpl_util_map_t *map, const tpl_util_key_t key, void *data,
252 tpl_free_func_t free_func)
254 tpl_util_map_entry_t **bucket = __get_bucket(map, key);
255 tpl_util_map_entry_t *curr = *bucket;
256 tpl_util_map_entry_t *prev = NULL;
259 /* Find existing entry for the key. */
264 if (map->key_length_func) {
265 len0 = map->key_length_func(curr->key);
266 len1 = map->key_length_func(key);
269 if (map->key_compare_func(curr->key, len0, key, len1) == 0) {
270 /* Free previous data. */
271 if (curr->free_func) curr->free_func(curr->data);
276 curr->free_func = free_func;
279 if (prev) prev->next = curr->next;
280 else *bucket = curr->next;
293 /* Nothing to delete. */
297 /* Allocate a new entry. */
298 if (map->key_length_func) key_length = map->key_length_func(key);
300 curr = malloc(sizeof(tpl_util_map_entry_t) + key_length);
301 TPL_CHECK_ON_FALSE_RETURN(curr);
303 if (key_length > 0) {
304 memcpy(curr + 1, key.ptr, key_length);
305 curr->key.ptr = (void *)(curr + 1);
311 curr->free_func = free_func;
313 /* Insert at the head of the bucket. */
314 curr->next = *bucket;