4 * Copyright (c) 2011-2012 David Herrmann <dh.herrmann@googlemail.com>
5 * Copyright (c) 2011 University of Tuebingen
7 * Permission is hereby granted, free of charge, to any person obtaining
8 * a copy of this software and associated documentation files
9 * (the "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sublicense, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
15 * The above copyright notice and this permission notice shall be included
16 * in all copies or substantial portions of the Software.
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
21 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
22 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
28 * A dynamic hash table implementation
31 #ifndef SHL_HASHTABLE_H
32 #define SHL_HASHTABLE_H
39 #include "external/htable.h"
43 typedef unsigned int (*shl_hash_cb) (const void *data);
44 typedef bool (*shl_equal_cb) (const void *data1, const void *data2);
45 typedef void (*shl_free_cb) (void *data);
47 struct shl_hashentry {
52 struct shl_hashtable {
55 shl_equal_cb equal_cb;
57 shl_free_cb free_value;
60 static inline unsigned int shl_direct_hash(const void *data)
62 return (unsigned int)(unsigned long)data;
65 static inline bool shl_direct_equal(const void *data1, const void *data2)
67 return data1 == data2;
70 static size_t shl_rehash(const void *ele, void *priv)
72 struct shl_hashtable *tbl = priv;
73 const struct shl_hashentry *ent = ele;
75 return tbl->hash_cb(ent->key);
78 static inline int shl_hashtable_new(struct shl_hashtable **out,
80 shl_equal_cb equal_cb,
82 shl_free_cb free_value)
84 struct shl_hashtable *tbl;
86 if (!out || !hash_cb || !equal_cb)
89 tbl = malloc(sizeof(*tbl));
92 memset(tbl, 0, sizeof(*tbl));
93 tbl->hash_cb = hash_cb;
94 tbl->equal_cb = equal_cb;
95 tbl->free_key = free_key;
96 tbl->free_value = free_value;
98 htable_init(&tbl->tbl, shl_rehash, tbl);
104 static inline void shl_hashtable_free(struct shl_hashtable *tbl)
106 struct htable_iter i;
107 struct shl_hashentry *entry;
112 for (entry = htable_first(&tbl->tbl, &i);
114 entry = htable_next(&tbl->tbl, &i)) {
115 htable_delval(&tbl->tbl, &i);
117 tbl->free_key(entry->key);
119 tbl->free_value(entry->value);
123 htable_clear(&tbl->tbl);
127 static inline int shl_hashtable_insert(struct shl_hashtable *tbl, void *key,
130 struct shl_hashentry *entry;
136 entry = malloc(sizeof(*entry));
140 entry->value = value;
142 hash = tbl->hash_cb(key);
144 if (!htable_add(&tbl->tbl, hash, entry)) {
152 static inline void shl_hashtable_remove(struct shl_hashtable *tbl, void *key)
154 struct htable_iter i;
155 struct shl_hashentry *entry;
161 hash = tbl->hash_cb(key);
163 for (entry = htable_firstval(&tbl->tbl, &i, hash);
165 entry = htable_nextval(&tbl->tbl, &i, hash)) {
166 if (tbl->equal_cb(key, entry->key)) {
167 htable_delval(&tbl->tbl, &i);
173 static inline bool shl_hashtable_find(struct shl_hashtable *tbl, void **out,
176 struct htable_iter i;
177 struct shl_hashentry *entry;
183 hash = tbl->hash_cb(key);
185 for (entry = htable_firstval(&tbl->tbl, &i, hash);
187 entry = htable_nextval(&tbl->tbl, &i, hash)) {
188 if (tbl->equal_cb(key, entry->key)) {
198 #endif /* SHL_HASHTABLE_H */