2 This file is part of catta.
4 catta is free software; you can redistribute it and/or modify it
5 under the terms of the GNU Lesser General Public License as
6 published by the Free Software Foundation; either version 2.1 of the
7 License, or (at your option) any later version.
9 catta is distributed in the hope that it will be useful, but WITHOUT
10 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
11 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
12 Public License for more details.
14 You should have received a copy of the GNU Lesser General Public
15 License along with catta; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
27 #include <catta/llist.h>
28 #include <catta/domain.h>
29 #include <catta/malloc.h>
34 #define HASH_MAP_SIZE 123
36 typedef struct Entry Entry;
38 CattaHashmap *hashmap;
42 CATTA_LLIST_FIELDS(Entry, bucket);
43 CATTA_LLIST_FIELDS(Entry, entries);
47 CattaHashFunc hash_func;
48 CattaEqualFunc equal_func;
49 CattaFreeFunc key_free_func, value_free_func;
51 Entry *entries[HASH_MAP_SIZE];
52 CATTA_LLIST_HEAD(Entry, entries_list);
55 static Entry* entry_get(CattaHashmap *m, const void *key) {
59 idx = m->hash_func(key) % HASH_MAP_SIZE;
61 for (e = m->entries[idx]; e; e = e->bucket_next)
62 if (m->equal_func(key, e->key))
68 static void entry_free(CattaHashmap *m, Entry *e, int stolen) {
73 idx = m->hash_func(e->key) % HASH_MAP_SIZE;
75 CATTA_LLIST_REMOVE(Entry, bucket, m->entries[idx], e);
76 CATTA_LLIST_REMOVE(Entry, entries, m->entries_list, e);
79 m->key_free_func(e->key);
80 if (m->value_free_func && !stolen)
81 m->value_free_func(e->value);
86 CattaHashmap* catta_hashmap_new(CattaHashFunc hash_func, CattaEqualFunc equal_func, CattaFreeFunc key_free_func, CattaFreeFunc value_free_func) {
92 if (!(m = catta_new0(CattaHashmap, 1)))
95 m->hash_func = hash_func;
96 m->equal_func = equal_func;
97 m->key_free_func = key_free_func;
98 m->value_free_func = value_free_func;
100 CATTA_LLIST_HEAD_INIT(Entry, m->entries_list);
105 void catta_hashmap_free(CattaHashmap *m) {
108 while (m->entries_list)
109 entry_free(m, m->entries_list, 0);
114 void* catta_hashmap_lookup(CattaHashmap *m, const void *key) {
119 if (!(e = entry_get(m, key)))
125 int catta_hashmap_insert(CattaHashmap *m, void *key, void *value) {
131 if ((e = entry_get(m, key))) {
132 if (m->key_free_func)
133 m->key_free_func(key);
134 if (m->value_free_func)
135 m->value_free_func(value);
140 if (!(e = catta_new(Entry, 1)))
147 CATTA_LLIST_PREPEND(Entry, entries, m->entries_list, e);
149 idx = m->hash_func(key) % HASH_MAP_SIZE;
150 CATTA_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
156 int catta_hashmap_replace(CattaHashmap *m, void *key, void *value) {
162 if ((e = entry_get(m, key))) {
163 if (m->key_free_func)
164 m->key_free_func(e->key);
165 if (m->value_free_func)
166 m->value_free_func(e->value);
174 if (!(e = catta_new(Entry, 1)))
181 CATTA_LLIST_PREPEND(Entry, entries, m->entries_list, e);
183 idx = m->hash_func(key) % HASH_MAP_SIZE;
184 CATTA_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
189 void catta_hashmap_remove(CattaHashmap *m, const void *key) {
194 if (!(e = entry_get(m, key)))
200 void catta_hashmap_foreach(CattaHashmap *m, CattaHashmapForeachCallback callback, void *userdata) {
205 for (e = m->entries_list; e; e = next) {
206 next = e->entries_next;
208 callback(e->key, e->value, userdata);
212 unsigned catta_string_hash(const void *data) {
213 const char *p = data;
219 hash = 31 * hash + *p;
224 int catta_string_equal(const void *a, const void *b) {
225 const char *p = a, *q = b;
230 return strcmp(p, q) == 0;
233 unsigned catta_int_hash(const void *data) {
238 return (unsigned) *i;
241 int catta_int_equal(const void *a, const void *b) {
242 const int *_a = a, *_b = b;