Branch data Line data Source code
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, 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 : :
28 : : #include <pulse/xmalloc.h>
29 : : #include <pulsecore/idxset.h>
30 : : #include <pulsecore/flist.h>
31 : : #include <pulsecore/macro.h>
32 : :
33 : : #include "hashmap.h"
34 : :
35 : : #define NBUCKETS 127
36 : :
37 : : struct hashmap_entry {
38 : : const void *key;
39 : : void *value;
40 : :
41 : : struct hashmap_entry *bucket_next, *bucket_previous;
42 : : struct hashmap_entry *iterate_next, *iterate_previous;
43 : : };
44 : :
45 : : struct pa_hashmap {
46 : : pa_hash_func_t hash_func;
47 : : pa_compare_func_t compare_func;
48 : :
49 : : struct hashmap_entry *iterate_list_head, *iterate_list_tail;
50 : : unsigned n_entries;
51 : : };
52 : :
53 : : #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + PA_ALIGN(sizeof(pa_hashmap))))
54 : :
55 [ - + ][ # # ]: 150 : PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
56 : :
57 : 43 : pa_hashmap *pa_hashmap_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
58 : : pa_hashmap *h;
59 : :
60 : 43 : h = pa_xmalloc0(PA_ALIGN(sizeof(pa_hashmap)) + NBUCKETS*sizeof(struct hashmap_entry*));
61 : :
62 [ + + ]: 43 : h->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
63 [ + + ]: 43 : h->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
64 : :
65 : 43 : h->n_entries = 0;
66 : 43 : h->iterate_list_head = h->iterate_list_tail = NULL;
67 : :
68 : 43 : return h;
69 : : }
70 : :
71 : 60 : static void remove_entry(pa_hashmap *h, struct hashmap_entry *e) {
72 [ - + ]: 60 : pa_assert(h);
73 [ - + ]: 60 : pa_assert(e);
74 : :
75 : : /* Remove from iteration list */
76 [ + + ]: 60 : if (e->iterate_next)
77 : 17 : e->iterate_next->iterate_previous = e->iterate_previous;
78 : : else
79 : 43 : h->iterate_list_tail = e->iterate_previous;
80 : :
81 [ - + ]: 60 : if (e->iterate_previous)
82 : 0 : e->iterate_previous->iterate_next = e->iterate_next;
83 : : else
84 : 60 : h->iterate_list_head = e->iterate_next;
85 : :
86 : : /* Remove from hash table bucket list */
87 [ - + ]: 60 : if (e->bucket_next)
88 : 0 : e->bucket_next->bucket_previous = e->bucket_previous;
89 : :
90 [ - + ]: 60 : if (e->bucket_previous)
91 : 0 : e->bucket_previous->bucket_next = e->bucket_next;
92 : : else {
93 : 60 : unsigned hash = h->hash_func(e->key) % NBUCKETS;
94 : 60 : BY_HASH(h)[hash] = e->bucket_next;
95 : : }
96 : :
97 [ - + ]: 60 : if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
98 : 0 : pa_xfree(e);
99 : :
100 [ - + ]: 60 : pa_assert(h->n_entries >= 1);
101 : 60 : h->n_entries--;
102 : 60 : }
103 : :
104 : 43 : void pa_hashmap_free(pa_hashmap*h, pa_free2_cb_t free_cb, void *userdata) {
105 [ + - ]: 43 : pa_assert(h);
106 : :
107 [ + + ]: 45 : while (h->iterate_list_head) {
108 : : void *data;
109 : 2 : data = h->iterate_list_head->value;
110 : 2 : remove_entry(h, h->iterate_list_head);
111 : :
112 [ + - ]: 2 : if (free_cb)
113 : 45 : free_cb(data, userdata);
114 : : }
115 : :
116 : 43 : pa_xfree(h);
117 : 43 : }
118 : :
119 : 204 : static struct hashmap_entry *hash_scan(pa_hashmap *h, unsigned hash, const void *key) {
120 : : struct hashmap_entry *e;
121 [ - + ]: 204 : pa_assert(h);
122 [ - + ]: 204 : pa_assert(hash < NBUCKETS);
123 : :
124 [ + + ]: 288 : for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
125 [ - + ]: 84 : if (h->compare_func(e->key, key) == 0)
126 : : return e;
127 : :
128 : : return NULL;
129 : : }
130 : :
131 : 60 : int pa_hashmap_put(pa_hashmap *h, const void *key, void *value) {
132 : : struct hashmap_entry *e;
133 : : unsigned hash;
134 : :
135 [ - + ]: 60 : pa_assert(h);
136 : :
137 : 60 : hash = h->hash_func(key) % NBUCKETS;
138 : :
139 [ + - ]: 60 : if (hash_scan(h, hash, key))
140 : : return -1;
141 : :
142 [ + + ]: 60 : if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
143 : 14 : e = pa_xnew(struct hashmap_entry, 1);
144 : :
145 : 60 : e->key = key;
146 : 60 : e->value = value;
147 : :
148 : : /* Insert into hash table */
149 : 60 : e->bucket_next = BY_HASH(h)[hash];
150 : 60 : e->bucket_previous = NULL;
151 [ - + ]: 60 : if (BY_HASH(h)[hash])
152 : 0 : BY_HASH(h)[hash]->bucket_previous = e;
153 : 60 : BY_HASH(h)[hash] = e;
154 : :
155 : : /* Insert into iteration list */
156 : 60 : e->iterate_previous = h->iterate_list_tail;
157 : 60 : e->iterate_next = NULL;
158 [ + + ]: 60 : if (h->iterate_list_tail) {
159 [ - + ]: 17 : pa_assert(h->iterate_list_head);
160 : 17 : h->iterate_list_tail->iterate_next = e;
161 : : } else {
162 [ - + ]: 43 : pa_assert(!h->iterate_list_head);
163 : 43 : h->iterate_list_head = e;
164 : : }
165 : 60 : h->iterate_list_tail = e;
166 : :
167 : 60 : h->n_entries++;
168 [ - + ]: 60 : pa_assert(h->n_entries >= 1);
169 : :
170 : : return 0;
171 : : }
172 : :
173 : 127 : void* pa_hashmap_get(pa_hashmap *h, const void *key) {
174 : : unsigned hash;
175 : : struct hashmap_entry *e;
176 : :
177 [ - + ]: 127 : pa_assert(h);
178 : :
179 : 127 : hash = h->hash_func(key) % NBUCKETS;
180 : :
181 [ + + ]: 127 : if (!(e = hash_scan(h, hash, key)))
182 : : return NULL;
183 : :
184 : 127 : return e->value;
185 : : }
186 : :
187 : 17 : void* pa_hashmap_remove(pa_hashmap *h, const void *key) {
188 : : struct hashmap_entry *e;
189 : : unsigned hash;
190 : : void *data;
191 : :
192 [ - + ]: 17 : pa_assert(h);
193 : :
194 : 17 : hash = h->hash_func(key) % NBUCKETS;
195 : :
196 [ + - ]: 17 : if (!(e = hash_scan(h, hash, key)))
197 : : return NULL;
198 : :
199 : 17 : data = e->value;
200 : 17 : remove_entry(h, e);
201 : :
202 : 17 : return data;
203 : : }
204 : :
205 : 53 : void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
206 : : struct hashmap_entry *e;
207 : :
208 [ - + ]: 53 : pa_assert(h);
209 [ - + ]: 53 : pa_assert(state);
210 : :
211 [ + + ]: 53 : if (*state == (void*) -1)
212 : : goto at_end;
213 : :
214 [ + + ][ + - ]: 39 : if (!*state && !h->iterate_list_head)
215 : : goto at_end;
216 : :
217 [ + + ]: 39 : e = *state ? *state : h->iterate_list_head;
218 : :
219 [ + + ]: 39 : if (e->iterate_next)
220 : 17 : *state = e->iterate_next;
221 : : else
222 : 22 : *state = (void*) -1;
223 : :
224 [ - + ]: 39 : if (key)
225 : 0 : *key = e->key;
226 : :
227 : 39 : return e->value;
228 : :
229 : : at_end:
230 : 14 : *state = (void *) -1;
231 : :
232 [ - + ]: 14 : if (key)
233 : 53 : *key = NULL;
234 : :
235 : : return NULL;
236 : : }
237 : :
238 : 0 : void *pa_hashmap_iterate_backwards(pa_hashmap *h, void **state, const void **key) {
239 : : struct hashmap_entry *e;
240 : :
241 [ # # ]: 0 : pa_assert(h);
242 [ # # ]: 0 : pa_assert(state);
243 : :
244 [ # # ]: 0 : if (*state == (void*) -1)
245 : : goto at_beginning;
246 : :
247 [ # # ][ # # ]: 0 : if (!*state && !h->iterate_list_tail)
248 : : goto at_beginning;
249 : :
250 [ # # ]: 0 : e = *state ? *state : h->iterate_list_tail;
251 : :
252 [ # # ]: 0 : if (e->iterate_previous)
253 : 0 : *state = e->iterate_previous;
254 : : else
255 : 0 : *state = (void*) -1;
256 : :
257 [ # # ]: 0 : if (key)
258 : 0 : *key = e->key;
259 : :
260 : 0 : return e->value;
261 : :
262 : : at_beginning:
263 : 0 : *state = (void *) -1;
264 : :
265 [ # # ]: 0 : if (key)
266 : 0 : *key = NULL;
267 : :
268 : : return NULL;
269 : : }
270 : :
271 : 8 : void* pa_hashmap_first(pa_hashmap *h) {
272 [ - + ]: 8 : pa_assert(h);
273 : :
274 [ - + ]: 8 : if (!h->iterate_list_head)
275 : : return NULL;
276 : :
277 : 8 : return h->iterate_list_head->value;
278 : : }
279 : :
280 : 0 : void* pa_hashmap_last(pa_hashmap *h) {
281 [ # # ]: 0 : pa_assert(h);
282 : :
283 [ # # ]: 0 : if (!h->iterate_list_tail)
284 : : return NULL;
285 : :
286 : 0 : return h->iterate_list_tail->value;
287 : : }
288 : :
289 : 66 : void* pa_hashmap_steal_first(pa_hashmap *h) {
290 : : void *data;
291 : :
292 [ - + ]: 66 : pa_assert(h);
293 : :
294 [ + + ]: 66 : if (!h->iterate_list_head)
295 : : return NULL;
296 : :
297 : 41 : data = h->iterate_list_head->value;
298 : 41 : remove_entry(h, h->iterate_list_head);
299 : :
300 : 66 : return data;
301 : : }
302 : :
303 : 24 : unsigned pa_hashmap_size(pa_hashmap *h) {
304 [ - + ]: 24 : pa_assert(h);
305 : :
306 : 24 : return h->n_entries;
307 : : }
308 : :
309 : 0 : pa_bool_t pa_hashmap_isempty(pa_hashmap *h) {
310 [ # # ]: 0 : pa_assert(h);
311 : :
312 : 0 : return h->n_entries == 0;
313 : : }
|
