]> git.meshlink.io Git - catta/blob - avahi-core/hashmap.c
CVE-2009-0758: Reflector creates packet storm on legacy unicast traffic
[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_new0(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     AVAHI_LLIST_HEAD_INIT(Entry, m->entries_list);
103     
104     return m;
105 }
106
107 void avahi_hashmap_free(AvahiHashmap *m) {
108     assert(m);
109
110     while (m->entries_list)
111         entry_free(m, m->entries_list, 0);
112     
113     avahi_free(m);
114 }
115
116 void* avahi_hashmap_lookup(AvahiHashmap *m, const void *key) {
117     Entry *e;
118     
119     assert(m);
120
121     if (!(e = entry_get(m, key)))
122         return NULL;
123
124     return e->value;
125 }
126
127 int avahi_hashmap_insert(AvahiHashmap *m, void *key, void *value) {
128     unsigned idx;
129     Entry *e;
130
131     assert(m);
132
133     if ((e = entry_get(m, key))) {
134         if (m->key_free_func)
135             m->key_free_func(key);
136         if (m->value_free_func)
137             m->value_free_func(value);
138         
139         return 1;
140     }
141
142     if (!(e = avahi_new(Entry, 1)))
143         return -1;
144
145     e->hashmap = m;
146     e->key = key;
147     e->value = value;
148
149     AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e);
150
151     idx = m->hash_func(key) % HASH_MAP_SIZE;
152     AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
153         
154     return 0;
155 }
156
157
158 int avahi_hashmap_replace(AvahiHashmap *m, void *key, void *value) {
159     unsigned idx;
160     Entry *e;
161
162     assert(m);
163
164     if ((e = entry_get(m, key))) {
165         if (m->key_free_func)
166             m->key_free_func(e->key);
167         if (m->value_free_func)
168             m->value_free_func(e->value);
169
170         e->key = key;
171         e->value = value;
172             
173         return 1;
174     }
175
176     if (!(e = avahi_new(Entry, 1)))
177         return -1;
178
179     e->hashmap = m;
180     e->key = key;
181     e->value = value;
182
183     AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e);
184
185     idx = m->hash_func(key) % HASH_MAP_SIZE;
186     AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
187         
188     return 0;
189 }
190
191 void avahi_hashmap_remove(AvahiHashmap *m, const void *key) {
192     Entry *e;
193     
194     assert(m);
195
196     if (!(e = entry_get(m, key)))
197         return;
198
199     entry_free(m, e, 0);
200 }
201
202 void avahi_hashmap_foreach(AvahiHashmap *m, AvahiHashmapForeachCallback callback, void *userdata) {
203     Entry *e, *next;
204     assert(m);
205     assert(callback);
206
207     for (e = m->entries_list; e; e = next) {
208         next = e->entries_next;
209
210         callback(e->key, e->value, userdata);
211     }
212 }
213
214 unsigned avahi_string_hash(const void *data) {
215     const char *p = data;
216     unsigned hash = 0;
217
218     assert(p);
219     
220     for (; *p; p++)
221         hash = 31 * hash + *p;
222
223     return hash;
224 }
225
226 int avahi_string_equal(const void *a, const void *b) {
227     const char *p = a, *q = b;
228
229     assert(p);
230     assert(q);
231     
232     return strcmp(p, q) == 0;
233 }
234
235 unsigned avahi_int_hash(const void *data) {
236     const int *i = data;
237
238     assert(i);
239     
240     return (unsigned) *i;
241 }
242
243 int avahi_int_equal(const void *a, const void *b) {
244     const int *_a = a, *_b = b;
245
246     assert(_a);
247     assert(_b);
248     
249     return *_a == *_b;
250 }