4 This file is part of PulseAudio.
6 Copyright 2004-2006 Lennart Poettering
8 PulseAudio is free software; you can redistribute it and/or modify
9 it under the terms of the GNU Lesser General Public License as published
10 by the Free Software Foundation; either version 2 of the License,
11 or (at your option) any later version.
13 PulseAudio is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU Lesser General Public License
19 along with PulseAudio; if not, write to the Free Software
20 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
31 #include <pulse/xmalloc.h>
33 #include <pulsecore/idxset.h>
34 #include <pulsecore/log.h>
35 #include <pulsecore/flist.h>
36 #include <pulsecore/macro.h>
42 struct hashmap_entry
{
43 struct hashmap_entry
*next
, *previous
, *bucket_next
, *bucket_previous
;
51 struct hashmap_entry
**data
;
52 struct hashmap_entry
*first_entry
;
55 pa_hash_func_t hash_func
;
56 pa_compare_func_t compare_func
;
59 PA_STATIC_FLIST_DECLARE(entries
, 0, pa_xfree
);
61 pa_hashmap
*pa_hashmap_new(pa_hash_func_t hash_func
, pa_compare_func_t compare_func
) {
64 h
= pa_xnew(pa_hashmap
, 1);
65 h
->data
= pa_xnew0(struct hashmap_entry
*, h
->size
= BUCKETS
);
66 h
->first_entry
= NULL
;
68 h
->hash_func
= hash_func
? hash_func
: pa_idxset_trivial_hash_func
;
69 h
->compare_func
= compare_func
? compare_func
: pa_idxset_trivial_compare_func
;
74 static void remove_entry(pa_hashmap
*h
, struct hashmap_entry
*e
) {
79 e
->next
->previous
= e
->previous
;
81 e
->previous
->next
= e
->next
;
83 h
->first_entry
= e
->next
;
86 e
->bucket_next
->bucket_previous
= e
->bucket_previous
;
87 if (e
->bucket_previous
)
88 e
->bucket_previous
->bucket_next
= e
->bucket_next
;
90 pa_assert(e
->hash
< h
->size
);
91 h
->data
[e
->hash
] = e
->bucket_next
;
94 if (pa_flist_push(PA_STATIC_FLIST_GET(entries
), e
) < 0)
100 void pa_hashmap_free(pa_hashmap
*h
, void (*free_func
)(void *p
, void *userdata
), void *userdata
) {
103 while (h
->first_entry
) {
105 free_func(h
->first_entry
->value
, userdata
);
106 remove_entry(h
, h
->first_entry
);
113 static struct hashmap_entry
*get(pa_hashmap
*h
, unsigned hash
, const void *key
) {
114 struct hashmap_entry
*e
;
116 pa_assert(hash
< h
->size
);
118 for (e
= h
->data
[hash
]; e
; e
= e
->bucket_next
)
119 if (h
->compare_func(e
->key
, key
) == 0)
125 int pa_hashmap_put(pa_hashmap
*h
, const void *key
, void *value
) {
126 struct hashmap_entry
*e
;
130 hash
= h
->hash_func(key
) % h
->size
;
132 if ((e
= get(h
, hash
, key
)))
135 if (!(e
= pa_flist_pop(PA_STATIC_FLIST_GET(entries
))))
136 e
= pa_xnew(struct hashmap_entry
, 1);
143 e
->next
= h
->first_entry
;
145 h
->first_entry
->previous
= e
;
148 e
->bucket_previous
= NULL
;
149 e
->bucket_next
= h
->data
[hash
];
151 h
->data
[hash
]->bucket_previous
= e
;
158 void* pa_hashmap_get(pa_hashmap
*h
, const void *key
) {
160 struct hashmap_entry
*e
;
164 hash
= h
->hash_func(key
) % h
->size
;
166 if (!(e
= get(h
, hash
, key
)))
172 void* pa_hashmap_remove(pa_hashmap
*h
, const void *key
) {
173 struct hashmap_entry
*e
;
179 hash
= h
->hash_func(key
) % h
->size
;
181 if (!(e
= get(h
, hash
, key
)))
189 unsigned pa_hashmap_size(pa_hashmap
*h
) {
193 void *pa_hashmap_iterate(pa_hashmap
*h
, void **state
, const void **key
) {
194 struct hashmap_entry
*e
;
199 if (*state
== (void*) -1)
202 if ((!*state
&& !h
->first_entry
))
205 e
= *state
? *state
: h
->first_entry
;
218 *state
= (void *) -1;
226 void* pa_hashmap_steal_first(pa_hashmap
*h
) {
234 data
= h
->first_entry
->value
;
235 remove_entry(h
, h
->first_entry
);
239 void *pa_hashmap_get_first(pa_hashmap
*h
) {
245 return h
->first_entry
->value
;