]> git.meshlink.io Git - catta/blob - avahi-core/hashmap.c
0c44d4ff5920d2439744bc6f04e437f459015f4b
[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(e);
73
74     idx = m->hash_func(e->key) % HASH_MAP_SIZE;
75
76     AVAHI_LLIST_REMOVE(Entry, bucket, m->entries[idx], e);
77     AVAHI_LLIST_REMOVE(Entry, entries, m->entries_list, e);
78
79     if (m->key_free_func)
80         m->key_free_func(e->key);
81     if (m->value_free_func && !stolen)
82         m->value_free_func(e->value);
83
84     avahi_free(e);
85 }
86
87 AvahiHashmap* avahi_hashmap_new(AvahiHashFunc hash_func, AvahiEqualFunc equal_func, AvahiFreeFunc key_free_func, AvahiFreeFunc value_free_func) {
88     AvahiHashmap *m;
89     
90     assert(hash_func);
91     assert(equal_func);
92
93     if (!(m = avahi_new(AvahiHashmap, 1)))
94         return NULL;
95
96     m->hash_func = hash_func;
97     m->equal_func = equal_func;
98     m->key_free_func = key_free_func;
99     m->value_free_func = value_free_func;
100
101     memset(m->entries, 0, sizeof(m->entries));
102
103     AVAHI_LLIST_HEAD_INIT(Entry, m->entries_list);
104     
105     return m;
106 }
107
108 void avahi_hashmap_free(AvahiHashmap *m) {
109     assert(m);
110
111     while (m->entries_list)
112         entry_free(m, m->entries_list, 0);
113     
114     avahi_free(m);
115 }
116
117 void* avahi_hashmap_lookup(AvahiHashmap *m, const void *key) {
118     Entry *e;
119     
120     assert(m);
121
122     if (!(e = entry_get(m, key)))
123         return NULL;
124
125     return e->value;
126 }
127
128 void* avahi_hashmap_steal(AvahiHashmap *m, const void *key) {
129     Entry *e;
130     void *v;
131     
132     assert(m);
133
134     if (!(e = entry_get(m, key)))
135         return NULL;
136
137     v = e->value;
138     entry_free(m, e, 1);
139     return v;
140 }
141
142 int avahi_hashmap_insert(AvahiHashmap *m, void *key, void *value) {
143     unsigned idx;
144     Entry *e;
145
146     assert(m);
147
148     if ((e = entry_get(m, key))) {
149         if (m->key_free_func)
150             m->key_free_func(key);
151         if (m->value_free_func)
152             m->value_free_func(value);
153         
154         return 1;
155     }
156
157     if (!(e = avahi_new(Entry, 1)))
158         return -1;
159
160     e->hashmap = m;
161     e->key = key;
162     e->value = value;
163
164     AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e);
165
166     idx = m->hash_func(key) % HASH_MAP_SIZE;
167     AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
168         
169     return 0;
170 }
171
172
173 int avahi_hashmap_replace(AvahiHashmap *m, void *key, void *value) {
174     unsigned idx;
175     Entry *e;
176
177     assert(m);
178
179     if ((e = entry_get(m, key))) {
180         if (m->key_free_func)
181             m->key_free_func(e->key);
182         if (m->value_free_func)
183             m->value_free_func(e->value);
184
185         e->key = key;
186         e->value = value;
187             
188         return 1;
189     }
190
191     if (!(e = avahi_new(Entry, 1)))
192         return -1;
193
194     e->hashmap = m;
195     e->key = key;
196     e->value = value;
197
198     AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e);
199
200     idx = m->hash_func(key) % HASH_MAP_SIZE;
201     AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
202         
203     return 0;
204 }
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 unsigned avahi_string_hash(const void *data) {
219     const char *p = data;
220     unsigned hash = 0;
221
222     for (; *p; p++)
223         hash = 31 * hash + *p;
224
225     return hash;
226 }
227
228 int avahi_string_equal(const void *a, const void *b) {
229     const char *p = a, *q = b;
230
231     return strcmp(p, q) == 0;
232 }
233
234 unsigned avahi_domain_hash(const void *data) {
235     unsigned hash = 0;
236     const char *s;
237     
238     for (;;) {
239         char c[65];
240
241         if (!avahi_unescape_label(&s, c, sizeof(c)))
242             return hash;
243
244         if (!c[0])
245             continue;
246         
247         hash += avahi_string_hash(avahi_strdown(c));
248     }
249 }