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
35struct 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
43struct 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
56PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
57
58pa_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
75pa_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
79static 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
115void pa_hashmap_free(pa_hashmap *h) {
116    pa_assert(h);
117
118    pa_hashmap_remove_all(h);
119    pa_xfree(h);
120}
121
122static 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
134int 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
176void* 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
190void* 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
208int 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
221void 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
234void *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
258at_end:
259    *state = (void *) -1;
260
261    if (key)
262        *key = NULL;
263
264    return NULL;
265}
266
267void *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
291at_beginning:
292    *state = (void *) -1;
293
294    if (key)
295        *key = NULL;
296
297    return NULL;
298}
299
300void* 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
309void* 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
318void* 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
332unsigned pa_hashmap_size(const pa_hashmap *h) {
333    pa_assert(h);
334
335    return h->n_entries;
336}
337
338bool pa_hashmap_isempty(const pa_hashmap *h) {
339    pa_assert(h);
340
341    return h->n_entries == 0;
342}
343