]> git.meshlink.io Git - catta/blob - avahi-core/hashmap.c
9b55bd316bcc258604443d902918f2f5b29c383a
[catta] / avahi-core / hashmap.c
1 /***
2   This file is part of avahi.
3
4   avahi 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.
8
9   avahi 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.
13
14   You should have received a copy of the GNU Lesser General Public
15   License along with avahi; if not, write to the Free Software
16   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
17   USA.
18 ***/
19
20 #ifdef HAVE_CONFIG_H
21 #include <config.h>
22 #endif
23
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include <avahi-common/llist.h>
28 #include <avahi-common/domain.h>
29 #include <avahi-common/malloc.h>
30
31 #include "hashmap.h"
32 #include "util.h"
33
34 #define HASH_MAP_SIZE 123
35
36 typedef struct Entry Entry;
37 struct Entry {
38     AvahiHashmap *hashmap;
39     void *key;
40     void *value;
41
42     AVAHI_LLIST_FIELDS(Entry, bucket);
43     AVAHI_LLIST_FIELDS(Entry, entries);
44 };
45
46 struct AvahiHashmap {
47     AvahiHashFunc hash_func;
48     AvahiEqualFunc equal_func;
49     AvahiFreeFunc key_free_func, value_free_func;
50
51     Entry *entries[HASH_MAP_SIZE];
52     AVAHI_LLIST_HEAD(Entry, entries_list);
53 };
54
55 static Entry* entry_get(AvahiHashmap *m, const void *key) {
56     unsigned idx;
57     Entry *e;
58
59     idx = m->hash_func(key) % HASH_MAP_SIZE;
60
61     for (e = m->entries[idx]; e; e = e->bucket_next)
62         if (m->equal_func(key, e->key))
63             return e;
64
65     return NULL;
66 }
67
68 static void entry_free(AvahiHashmap *m, Entry *e, int stolen) {
69     unsigned idx;
70     assert(m);
71     assert(e);
72
73     idx = m->hash_func(e->key) % HASH_MAP_SIZE;
74
75     AVAHI_LLIST_REMOVE(Entry, bucket, m->entries[idx], e);
76     AVAHI_LLIST_REMOVE(Entry, entries, m->entries_list, e);
77
78     if (m->key_free_func)
79         m->key_free_func(e->key);
80     if (m->value_free_func && !stolen)
81         m->value_free_func(e->value);
82
83     avahi_free(e);
84 }
85
86 AvahiHashmap* avahi_hashmap_new(AvahiHashFunc hash_func, AvahiEqualFunc equal_func, AvahiFreeFunc key_free_func, AvahiFreeFunc value_free_func) {
87     AvahiHashmap *m;
88
89     assert(hash_func);
90     assert(equal_func);
91
92     if (!(m = avahi_new0(AvahiHashmap, 1)))
93         return NULL;
94
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;
99
100     AVAHI_LLIST_HEAD_INIT(Entry, m->entries_list);
101
102     return m;
103 }
104
105 void avahi_hashmap_free(AvahiHashmap *m) {
106     assert(m);
107
108     while (m->entries_list)
109         entry_free(m, m->entries_list, 0);
110
111     avahi_free(m);
112 }
113
114 void* avahi_hashmap_lookup(AvahiHashmap *m, const void *key) {
115     Entry *e;
116
117     assert(m);
118
119     if (!(e = entry_get(m, key)))
120         return NULL;
121
122     return e->value;
123 }
124
125 int avahi_hashmap_insert(AvahiHashmap *m, void *key, void *value) {
126     unsigned idx;
127     Entry *e;
128
129     assert(m);
130
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);
136
137         return 1;
138     }
139
140     if (!(e = avahi_new(Entry, 1)))
141         return -1;
142
143     e->hashmap = m;
144     e->key = key;
145     e->value = value;
146
147     AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e);
148
149     idx = m->hash_func(key) % HASH_MAP_SIZE;
150     AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
151
152     return 0;
153 }
154
155
156 int avahi_hashmap_replace(AvahiHashmap *m, void *key, void *value) {
157     unsigned idx;
158     Entry *e;
159
160     assert(m);
161
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);
167
168         e->key = key;
169         e->value = value;
170
171         return 1;
172     }
173
174     if (!(e = avahi_new(Entry, 1)))
175         return -1;
176
177     e->hashmap = m;
178     e->key = key;
179     e->value = value;
180
181     AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e);
182
183     idx = m->hash_func(key) % HASH_MAP_SIZE;
184     AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
185
186     return 0;
187 }
188
189 void avahi_hashmap_remove(AvahiHashmap *m, const void *key) {
190     Entry *e;
191
192     assert(m);
193
194     if (!(e = entry_get(m, key)))
195         return;
196
197     entry_free(m, e, 0);
198 }
199
200 void avahi_hashmap_foreach(AvahiHashmap *m, AvahiHashmapForeachCallback callback, void *userdata) {
201     Entry *e, *next;
202     assert(m);
203     assert(callback);
204
205     for (e = m->entries_list; e; e = next) {
206         next = e->entries_next;
207
208         callback(e->key, e->value, userdata);
209     }
210 }
211
212 unsigned avahi_string_hash(const void *data) {
213     const char *p = data;
214     unsigned hash = 0;
215
216     assert(p);
217
218     for (; *p; p++)
219         hash = 31 * hash + *p;
220
221     return hash;
222 }
223
224 int avahi_string_equal(const void *a, const void *b) {
225     const char *p = a, *q = b;
226
227     assert(p);
228     assert(q);
229
230     return strcmp(p, q) == 0;
231 }
232
233 unsigned avahi_int_hash(const void *data) {
234     const int *i = data;
235
236     assert(i);
237
238     return (unsigned) *i;
239 }
240
241 int avahi_int_equal(const void *a, const void *b) {
242     const int *_a = a, *_b = b;
243
244     assert(_a);
245     assert(_b);
246
247     return *_a == *_b;
248 }