2 This file is part of PulseAudio.
4 Copyright 2004-2008 Lennart Poettering
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.
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.
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
28 #include <pulse/xmalloc.h>
29 #include <pulsecore/idxset.h>
30 #include <pulsecore/flist.h>
31 #include <pulsecore/macro.h>
37 struct hashmap_entry
{
41 struct hashmap_entry
*bucket_next
, *bucket_previous
;
42 struct hashmap_entry
*iterate_next
, *iterate_previous
;
46 pa_hash_func_t hash_func
;
47 pa_compare_func_t compare_func
;
49 pa_free_cb_t key_free_func
;
50 pa_free_cb_t value_free_func
;
52 struct hashmap_entry
*iterate_list_head
, *iterate_list_tail
;
56 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + PA_ALIGN(sizeof(pa_hashmap))))
58 PA_STATIC_FLIST_DECLARE(entries
, 0, pa_xfree
);
60 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
) {
63 h
= pa_xmalloc0(PA_ALIGN(sizeof(pa_hashmap
)) + NBUCKETS
*sizeof(struct hashmap_entry
*));
65 h
->hash_func
= hash_func
? hash_func
: pa_idxset_trivial_hash_func
;
66 h
->compare_func
= compare_func
? compare_func
: pa_idxset_trivial_compare_func
;
68 h
->key_free_func
= key_free_func
;
69 h
->value_free_func
= value_free_func
;
72 h
->iterate_list_head
= h
->iterate_list_tail
= NULL
;
77 pa_hashmap
*pa_hashmap_new(pa_hash_func_t hash_func
, pa_compare_func_t compare_func
) {
78 return pa_hashmap_new_full(hash_func
, compare_func
, NULL
, NULL
);
81 static void remove_entry(pa_hashmap
*h
, struct hashmap_entry
*e
) {
85 /* Remove from iteration list */
87 e
->iterate_next
->iterate_previous
= e
->iterate_previous
;
89 h
->iterate_list_tail
= e
->iterate_previous
;
91 if (e
->iterate_previous
)
92 e
->iterate_previous
->iterate_next
= e
->iterate_next
;
94 h
->iterate_list_head
= e
->iterate_next
;
96 /* Remove from hash table bucket list */
98 e
->bucket_next
->bucket_previous
= e
->bucket_previous
;
100 if (e
->bucket_previous
)
101 e
->bucket_previous
->bucket_next
= e
->bucket_next
;
103 unsigned hash
= h
->hash_func(e
->key
) % NBUCKETS
;
104 BY_HASH(h
)[hash
] = e
->bucket_next
;
107 if (h
->key_free_func
)
108 h
->key_free_func(e
->key
);
110 if (pa_flist_push(PA_STATIC_FLIST_GET(entries
), e
) < 0)
113 pa_assert(h
->n_entries
>= 1);
117 void pa_hashmap_free(pa_hashmap
*h
) {
120 pa_hashmap_remove_all(h
);
124 static struct hashmap_entry
*hash_scan(pa_hashmap
*h
, unsigned hash
, const void *key
) {
125 struct hashmap_entry
*e
;
127 pa_assert(hash
< NBUCKETS
);
129 for (e
= BY_HASH(h
)[hash
]; e
; e
= e
->bucket_next
)
130 if (h
->compare_func(e
->key
, key
) == 0)
136 int pa_hashmap_put(pa_hashmap
*h
, void *key
, void *value
) {
137 struct hashmap_entry
*e
;
142 hash
= h
->hash_func(key
) % NBUCKETS
;
144 if (hash_scan(h
, hash
, key
))
147 if (!(e
= pa_flist_pop(PA_STATIC_FLIST_GET(entries
))))
148 e
= pa_xnew(struct hashmap_entry
, 1);
153 /* Insert into hash table */
154 e
->bucket_next
= BY_HASH(h
)[hash
];
155 e
->bucket_previous
= NULL
;
156 if (BY_HASH(h
)[hash
])
157 BY_HASH(h
)[hash
]->bucket_previous
= e
;
158 BY_HASH(h
)[hash
] = e
;
160 /* Insert into iteration list */
161 e
->iterate_previous
= h
->iterate_list_tail
;
162 e
->iterate_next
= NULL
;
163 if (h
->iterate_list_tail
) {
164 pa_assert(h
->iterate_list_head
);
165 h
->iterate_list_tail
->iterate_next
= e
;
167 pa_assert(!h
->iterate_list_head
);
168 h
->iterate_list_head
= e
;
170 h
->iterate_list_tail
= e
;
173 pa_assert(h
->n_entries
>= 1);
178 void* pa_hashmap_get(pa_hashmap
*h
, const void *key
) {
180 struct hashmap_entry
*e
;
184 hash
= h
->hash_func(key
) % NBUCKETS
;
186 if (!(e
= hash_scan(h
, hash
, key
)))
192 void* pa_hashmap_remove(pa_hashmap
*h
, const void *key
) {
193 struct hashmap_entry
*e
;
199 hash
= h
->hash_func(key
) % NBUCKETS
;
201 if (!(e
= hash_scan(h
, hash
, key
)))
210 void pa_hashmap_remove_all(pa_hashmap
*h
) {
213 while (h
->iterate_list_head
) {
215 data
= h
->iterate_list_head
->value
;
216 remove_entry(h
, h
->iterate_list_head
);
218 if (h
->value_free_func
)
219 h
->value_free_func(data
);
223 void *pa_hashmap_iterate(pa_hashmap
*h
, void **state
, const void **key
) {
224 struct hashmap_entry
*e
;
229 if (*state
== (void*) -1)
232 if (!*state
&& !h
->iterate_list_head
)
235 e
= *state
? *state
: h
->iterate_list_head
;
238 *state
= e
->iterate_next
;
248 *state
= (void *) -1;
256 void *pa_hashmap_iterate_backwards(pa_hashmap
*h
, void **state
, const void **key
) {
257 struct hashmap_entry
*e
;
262 if (*state
== (void*) -1)
265 if (!*state
&& !h
->iterate_list_tail
)
268 e
= *state
? *state
: h
->iterate_list_tail
;
270 if (e
->iterate_previous
)
271 *state
= e
->iterate_previous
;
281 *state
= (void *) -1;
289 void* pa_hashmap_first(pa_hashmap
*h
) {
292 if (!h
->iterate_list_head
)
295 return h
->iterate_list_head
->value
;
298 void* pa_hashmap_last(pa_hashmap
*h
) {
301 if (!h
->iterate_list_tail
)
304 return h
->iterate_list_tail
->value
;
307 void* pa_hashmap_steal_first(pa_hashmap
*h
) {
312 if (!h
->iterate_list_head
)
315 data
= h
->iterate_list_head
->value
;
316 remove_entry(h
, h
->iterate_list_head
);
321 unsigned pa_hashmap_size(pa_hashmap
*h
) {
327 bool pa_hashmap_isempty(pa_hashmap
*h
) {
330 return h
->n_entries
== 0;