1 /***
2 This file is part of PulseAudio.
3
4 Copyright 2004-2008 Lennart Poettering
5
6 PulseAudio is free software; you can redistribute it and/or modify
7 it under the terms of the GNU Lesser General Public License as published
8 by the Free Software Foundation; either version 2.1 of the License,
9 or (at your option) any later version.
10
11 PulseAudio is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
15
16 You should have received a copy of the GNU Lesser General Public License
17 along with PulseAudio; if not, see <http://www.gnu.org/licenses/>.
18 ***/
19
20 #ifdef HAVE_CONFIG_H
21 #include <config.h>
22 #endif
23
24 #include <stdlib.h>
25
26 #include <pulse/xmalloc.h>
27 #include <pulsecore/idxset.h>
28 #include <pulsecore/flist.h>
29 #include <pulsecore/macro.h>
30
31 #include "hashmap.h"
32
33 #define NBUCKETS 127
34
35 struct hashmap_entry {
36 void *key;
37 void *value;
38
39 struct hashmap_entry *bucket_next, *bucket_previous;
40 struct hashmap_entry *iterate_next, *iterate_previous;
41 };
42
43 struct pa_hashmap {
44 pa_hash_func_t hash_func;
45 pa_compare_func_t compare_func;
46
47 pa_free_cb_t key_free_func;
48 pa_free_cb_t value_free_func;
49
50 struct hashmap_entry *iterate_list_head, *iterate_list_tail;
51 unsigned n_entries;
52 };
53
54 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + PA_ALIGN(sizeof(pa_hashmap))))
55
56 PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
57
pa_hashmap_new_full(pa_hash_func_t hash_func,pa_compare_func_t compare_func,pa_free_cb_t key_free_func,pa_free_cb_t value_free_func)58 pa_hashmap *pa_hashmap_new_full(pa_hash_func_t hash_func, pa_compare_func_t compare_func, pa_free_cb_t key_free_func, pa_free_cb_t value_free_func) {
59 pa_hashmap *h;
60
61 h = pa_xmalloc0(PA_ALIGN(sizeof(pa_hashmap)) + NBUCKETS*sizeof(struct hashmap_entry*));
62
63 h->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
64 h->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
65
66 h->key_free_func = key_free_func;
67 h->value_free_func = value_free_func;
68
69 h->n_entries = 0;
70 h->iterate_list_head = h->iterate_list_tail = NULL;
71
72 return h;
73 }
74
pa_hashmap_new(pa_hash_func_t hash_func,pa_compare_func_t compare_func)75 pa_hashmap *pa_hashmap_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
76 return pa_hashmap_new_full(hash_func, compare_func, NULL, NULL);
77 }
78
remove_entry(pa_hashmap * h,struct hashmap_entry * e)79 static void remove_entry(pa_hashmap *h, struct hashmap_entry *e) {
80 pa_assert(h);
81 pa_assert(e);
82
83 /* Remove from iteration list */
84 if (e->iterate_next)
85 e->iterate_next->iterate_previous = e->iterate_previous;
86 else
87 h->iterate_list_tail = e->iterate_previous;
88
89 if (e->iterate_previous)
90 e->iterate_previous->iterate_next = e->iterate_next;
91 else
92 h->iterate_list_head = e->iterate_next;
93
94 /* Remove from hash table bucket list */
95 if (e->bucket_next)
96 e->bucket_next->bucket_previous = e->bucket_previous;
97
98 if (e->bucket_previous)
99 e->bucket_previous->bucket_next = e->bucket_next;
100 else {
101 unsigned hash = h->hash_func(e->key) % NBUCKETS;
102 BY_HASH(h)[hash] = e->bucket_next;
103 }
104
105 if (h->key_free_func)
106 h->key_free_func(e->key);
107
108 if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
109 pa_xfree(e);
110
111 pa_assert(h->n_entries >= 1);
112 h->n_entries--;
113 }
114
pa_hashmap_free(pa_hashmap * h)115 void pa_hashmap_free(pa_hashmap *h) {
116 pa_assert(h);
117
118 pa_hashmap_remove_all(h);
119 pa_xfree(h);
120 }
121
hash_scan(const pa_hashmap * h,unsigned hash,const void * key)122 static struct hashmap_entry *hash_scan(const pa_hashmap *h, unsigned hash, const void *key) {
123 struct hashmap_entry *e;
124 pa_assert(h);
125 pa_assert(hash < NBUCKETS);
126
127 for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
128 if (h->compare_func(e->key, key) == 0)
129 return e;
130
131 return NULL;
132 }
133
pa_hashmap_put(pa_hashmap * h,void * key,void * value)134 int pa_hashmap_put(pa_hashmap *h, void *key, void *value) {
135 struct hashmap_entry *e;
136 unsigned hash;
137
138 pa_assert(h);
139
140 hash = h->hash_func(key) % NBUCKETS;
141
142 if (hash_scan(h, hash, key))
143 return -1;
144
145 if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
146 e = pa_xnew(struct hashmap_entry, 1);
147
148 e->key = key;
149 e->value = value;
150
151 /* Insert into hash table */
152 e->bucket_next = BY_HASH(h)[hash];
153 e->bucket_previous = NULL;
154 if (BY_HASH(h)[hash])
155 BY_HASH(h)[hash]->bucket_previous = e;
156 BY_HASH(h)[hash] = e;
157
158 /* Insert into iteration list */
159 e->iterate_previous = h->iterate_list_tail;
160 e->iterate_next = NULL;
161 if (h->iterate_list_tail) {
162 pa_assert(h->iterate_list_head);
163 h->iterate_list_tail->iterate_next = e;
164 } else {
165 pa_assert(!h->iterate_list_head);
166 h->iterate_list_head = e;
167 }
168 h->iterate_list_tail = e;
169
170 h->n_entries++;
171 pa_assert(h->n_entries >= 1);
172
173 return 0;
174 }
175
pa_hashmap_get(const pa_hashmap * h,const void * key)176 void* pa_hashmap_get(const pa_hashmap *h, const void *key) {
177 unsigned hash;
178 struct hashmap_entry *e;
179
180 pa_assert(h);
181
182 hash = h->hash_func(key) % NBUCKETS;
183
184 if (!(e = hash_scan(h, hash, key)))
185 return NULL;
186
187 return e->value;
188 }
189
pa_hashmap_remove(pa_hashmap * h,const void * key)190 void* pa_hashmap_remove(pa_hashmap *h, const void *key) {
191 struct hashmap_entry *e;
192 unsigned hash;
193 void *data;
194
195 pa_assert(h);
196
197 hash = h->hash_func(key) % NBUCKETS;
198
199 if (!(e = hash_scan(h, hash, key)))
200 return NULL;
201
202 data = e->value;
203 remove_entry(h, e);
204
205 return data;
206 }
207
pa_hashmap_remove_and_free(pa_hashmap * h,const void * key)208 int pa_hashmap_remove_and_free(pa_hashmap *h, const void *key) {
209 void *data;
210
211 pa_assert(h);
212
213 data = pa_hashmap_remove(h, key);
214
215 if (data && h->value_free_func)
216 h->value_free_func(data);
217
218 return data ? 0 : -1;
219 }
220
pa_hashmap_remove_all(pa_hashmap * h)221 void pa_hashmap_remove_all(pa_hashmap *h) {
222 pa_assert(h);
223
224 while (h->iterate_list_head) {
225 void *data;
226 data = h->iterate_list_head->value;
227 remove_entry(h, h->iterate_list_head);
228
229 if (h->value_free_func)
230 h->value_free_func(data);
231 }
232 }
233
pa_hashmap_iterate(const pa_hashmap * h,void ** state,const void ** key)234 void *pa_hashmap_iterate(const pa_hashmap *h, void **state, const void **key) {
235 struct hashmap_entry *e;
236
237 pa_assert(h);
238 pa_assert(state);
239
240 if (*state == (void*) -1)
241 goto at_end;
242
243 if (!*state && !h->iterate_list_head)
244 goto at_end;
245
246 e = *state ? *state : h->iterate_list_head;
247
248 if (e->iterate_next)
249 *state = e->iterate_next;
250 else
251 *state = (void*) -1;
252
253 if (key)
254 *key = e->key;
255
256 return e->value;
257
258 at_end:
259 *state = (void *) -1;
260
261 if (key)
262 *key = NULL;
263
264 return NULL;
265 }
266
pa_hashmap_iterate_backwards(const pa_hashmap * h,void ** state,const void ** key)267 void *pa_hashmap_iterate_backwards(const pa_hashmap *h, void **state, const void **key) {
268 struct hashmap_entry *e;
269
270 pa_assert(h);
271 pa_assert(state);
272
273 if (*state == (void*) -1)
274 goto at_beginning;
275
276 if (!*state && !h->iterate_list_tail)
277 goto at_beginning;
278
279 e = *state ? *state : h->iterate_list_tail;
280
281 if (e->iterate_previous)
282 *state = e->iterate_previous;
283 else
284 *state = (void*) -1;
285
286 if (key)
287 *key = e->key;
288
289 return e->value;
290
291 at_beginning:
292 *state = (void *) -1;
293
294 if (key)
295 *key = NULL;
296
297 return NULL;
298 }
299
pa_hashmap_first(const pa_hashmap * h)300 void* pa_hashmap_first(const pa_hashmap *h) {
301 pa_assert(h);
302
303 if (!h->iterate_list_head)
304 return NULL;
305
306 return h->iterate_list_head->value;
307 }
308
pa_hashmap_last(const pa_hashmap * h)309 void* pa_hashmap_last(const pa_hashmap *h) {
310 pa_assert(h);
311
312 if (!h->iterate_list_tail)
313 return NULL;
314
315 return h->iterate_list_tail->value;
316 }
317
pa_hashmap_steal_first(pa_hashmap * h)318 void* pa_hashmap_steal_first(pa_hashmap *h) {
319 void *data;
320
321 pa_assert(h);
322
323 if (!h->iterate_list_head)
324 return NULL;
325
326 data = h->iterate_list_head->value;
327 remove_entry(h, h->iterate_list_head);
328
329 return data;
330 }
331
pa_hashmap_size(const pa_hashmap * h)332 unsigned pa_hashmap_size(const pa_hashmap *h) {
333 pa_assert(h);
334
335 return h->n_entries;
336 }
337
pa_hashmap_isempty(const pa_hashmap * h)338 bool pa_hashmap_isempty(const pa_hashmap *h) {
339 pa_assert(h);
340
341 return h->n_entries == 0;
342 }
343