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
32 #include <pulse/xmalloc.h>
34 #include <pulsecore/idxset.h>
35 #include <pulsecore/log.h>
41 struct hashmap_entry {
42 struct hashmap_entry *next, *previous, *bucket_next, *bucket_previous;
50 struct hashmap_entry **data;
51 struct hashmap_entry *first_entry;
54 pa_hash_func_t hash_func;
55 pa_compare_func_t compare_func;
58 pa_hashmap *pa_hashmap_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
61 h = pa_xnew(pa_hashmap, 1);
62 h->data = pa_xnew0(struct hashmap_entry*, h->size = BUCKETS);
63 h->first_entry = NULL;
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;
71 static void remove(pa_hashmap *h, struct hashmap_entry *e) {
76 e->next->previous = e->previous;
78 e->previous->next = e->next;
80 h->first_entry = e->next;
83 e->bucket_next->bucket_previous = e->bucket_previous;
84 if (e->bucket_previous)
85 e->bucket_previous->bucket_next = e->bucket_next;
87 assert(e->hash < h->size);
88 h->data[e->hash] = e->bucket_next;
95 void pa_hashmap_free(pa_hashmap*h, void (*free_func)(void *p, void *userdata), void *userdata) {
98 while (h->first_entry) {
100 free_func(h->first_entry->value, userdata);
101 remove(h, h->first_entry);
108 static struct hashmap_entry *get(pa_hashmap *h, unsigned hash, const void *key) {
109 struct hashmap_entry *e;
111 assert(hash < h->size);
113 for (e = h->data[hash]; e; e = e->bucket_next)
114 if (h->compare_func(e->key, key) == 0)
120 int pa_hashmap_put(pa_hashmap *h, const void *key, void *value) {
121 struct hashmap_entry *e;
125 hash = h->hash_func(key) % h->size;
127 if ((e = get(h, hash, key)))
130 e = pa_xnew(struct hashmap_entry, 1);
136 e->next = h->first_entry;
138 h->first_entry->previous = e;
141 e->bucket_previous = NULL;
142 e->bucket_next = h->data[hash];
144 h->data[hash]->bucket_previous = e;
151 void* pa_hashmap_get(pa_hashmap *h, const void *key) {
153 struct hashmap_entry *e;
157 hash = h->hash_func(key) % h->size;
159 if (!(e = get(h, hash, key)))
165 void* pa_hashmap_remove(pa_hashmap *h, const void *key) {
166 struct hashmap_entry *e;
172 hash = h->hash_func(key) % h->size;
174 if (!(e = get(h, hash, key)))
182 unsigned pa_hashmap_size(pa_hashmap *h) {
186 void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
191 *state = h->first_entry;
193 *state = ((struct hashmap_entry*) *state)->next;
202 *key = ((struct hashmap_entry*) *state)->key;
204 return ((struct hashmap_entry*) *state)->value;
207 void* pa_hashmap_steal_first(pa_hashmap *h) {
215 data = h->first_entry->value;
216 remove(h, h->first_entry);
220 void *pa_hashmap_get_first(pa_hashmap *h) {
226 return h->first_entry->value;