src/pulsecore/hashmap.c

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