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