code.delx.au - pulseaudio/blob - 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, write to the Free Software
  18   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  19   USA.
  20 ***/
  21
  22 #ifdef HAVE_CONFIG_H
  23 #include <config.h>
  24 #endif
  25
  26 #include <stdlib.h>
  27
  28 #include <pulse/xmalloc.h>
  29 #include <pulsecore/idxset.h>
  30 #include <pulsecore/flist.h>
  31 #include <pulsecore/macro.h>
  32
  33 #include "hashmap.h"
  34
  35 #define NBUCKETS 127
  36
  37 struct hashmap_entry {
  38     void *key;
  39     void *value;
  40
  41     struct hashmap_entry *bucket_next, *bucket_previous;
  42     struct hashmap_entry *iterate_next, *iterate_previous;
  43 };
  44
  45 struct pa_hashmap {
  46     pa_hash_func_t hash_func;
  47     pa_compare_func_t compare_func;
  48
  49     pa_free_cb_t key_free_func;
  50     pa_free_cb_t value_free_func;
  51
  52     struct hashmap_entry *iterate_list_head, *iterate_list_tail;
  53     unsigned n_entries;
  54 };
  55
  56 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + PA_ALIGN(sizeof(pa_hashmap))))
  57
  58 PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
  59
  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) {
  61     pa_hashmap *h;
  62
  63     h = pa_xmalloc0(PA_ALIGN(sizeof(pa_hashmap)) + NBUCKETS*sizeof(struct hashmap_entry*));
  64
  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;
  67
  68     h->key_free_func = key_free_func;
  69     h->value_free_func = value_free_func;
  70
  71     h->n_entries = 0;
  72     h->iterate_list_head = h->iterate_list_tail = NULL;
  73
  74     return h;
  75 }
  76
  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);
  79 }
  80
  81 static void remove_entry(pa_hashmap *h, struct hashmap_entry *e) {
  82     pa_assert(h);
  83     pa_assert(e);
  84
  85     /* Remove from iteration list */
  86     if (e->iterate_next)
  87         e->iterate_next->iterate_previous = e->iterate_previous;
  88     else
  89         h->iterate_list_tail = e->iterate_previous;
  90
  91     if (e->iterate_previous)
  92         e->iterate_previous->iterate_next = e->iterate_next;
  93     else
  94         h->iterate_list_head = e->iterate_next;
  95
  96     /* Remove from hash table bucket list */
  97     if (e->bucket_next)
  98         e->bucket_next->bucket_previous = e->bucket_previous;
  99
 100     if (e->bucket_previous)
 101         e->bucket_previous->bucket_next = e->bucket_next;
 102     else {
 103         unsigned hash = h->hash_func(e->key) % NBUCKETS;
 104         BY_HASH(h)[hash] = e->bucket_next;
 105     }
 106
 107     if (h->key_free_func)
 108         h->key_free_func(e->key);
 109
 110     if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
 111         pa_xfree(e);
 112
 113     pa_assert(h->n_entries >= 1);
 114     h->n_entries--;
 115 }
 116
 117 void pa_hashmap_free(pa_hashmap *h) {
 118     pa_assert(h);
 119
 120     pa_hashmap_remove_all(h);
 121     pa_xfree(h);
 122 }
 123
 124 static struct hashmap_entry *hash_scan(pa_hashmap *h, unsigned hash, const void *key) {
 125     struct hashmap_entry *e;
 126     pa_assert(h);
 127     pa_assert(hash < NBUCKETS);
 128
 129     for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 130         if (h->compare_func(e->key, key) == 0)
 131             return e;
 132
 133     return NULL;
 134 }
 135
 136 int pa_hashmap_put(pa_hashmap *h, void *key, void *value) {
 137     struct hashmap_entry *e;
 138     unsigned hash;
 139
 140     pa_assert(h);
 141
 142     hash = h->hash_func(key) % NBUCKETS;
 143
 144     if (hash_scan(h, hash, key))
 145         return -1;
 146
 147     if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
 148         e = pa_xnew(struct hashmap_entry, 1);
 149
 150     e->key = key;
 151     e->value = value;
 152
 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;
 159
 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;
 166     } else {
 167         pa_assert(!h->iterate_list_head);
 168         h->iterate_list_head = e;
 169     }
 170     h->iterate_list_tail = e;
 171
 172     h->n_entries++;
 173     pa_assert(h->n_entries >= 1);
 174
 175     return 0;
 176 }
 177
 178 void* pa_hashmap_get(pa_hashmap *h, const void *key) {
 179     unsigned hash;
 180     struct hashmap_entry *e;
 181
 182     pa_assert(h);
 183
 184     hash = h->hash_func(key) % NBUCKETS;
 185
 186     if (!(e = hash_scan(h, hash, key)))
 187         return NULL;
 188
 189     return e->value;
 190 }
 191
 192 void* pa_hashmap_remove(pa_hashmap *h, const void *key) {
 193     struct hashmap_entry *e;
 194     unsigned hash;
 195     void *data;
 196
 197     pa_assert(h);
 198
 199     hash = h->hash_func(key) % NBUCKETS;
 200
 201     if (!(e = hash_scan(h, hash, key)))
 202         return NULL;
 203
 204     data = e->value;
 205     remove_entry(h, e);
 206
 207     return data;
 208 }
 209
 210 int pa_hashmap_remove_and_free(pa_hashmap *h, const void *key) {
 211     void *data;
 212
 213     pa_assert(h);
 214
 215     data = pa_hashmap_remove(h, key);
 216
 217     if (data && h->value_free_func)
 218         h->value_free_func(data);
 219
 220     return data ? 0 : -1;
 221 }
 222
 223 void pa_hashmap_remove_all(pa_hashmap *h) {
 224     pa_assert(h);
 225
 226     while (h->iterate_list_head) {
 227         void *data;
 228         data = h->iterate_list_head->value;
 229         remove_entry(h, h->iterate_list_head);
 230
 231         if (h->value_free_func)
 232             h->value_free_func(data);
 233     }
 234 }
 235
 236 void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
 237     struct hashmap_entry *e;
 238
 239     pa_assert(h);
 240     pa_assert(state);
 241
 242     if (*state == (void*) -1)
 243         goto at_end;
 244
 245     if (!*state && !h->iterate_list_head)
 246         goto at_end;
 247
 248     e = *state ? *state : h->iterate_list_head;
 249
 250     if (e->iterate_next)
 251         *state = e->iterate_next;
 252     else
 253         *state = (void*) -1;
 254
 255     if (key)
 256         *key = e->key;
 257
 258     return e->value;
 259
 260 at_end:
 261     *state = (void *) -1;
 262
 263     if (key)
 264         *key = NULL;
 265
 266     return NULL;
 267 }
 268
 269 void *pa_hashmap_iterate_backwards(pa_hashmap *h, void **state, const void **key) {
 270     struct hashmap_entry *e;
 271
 272     pa_assert(h);
 273     pa_assert(state);
 274
 275     if (*state == (void*) -1)
 276         goto at_beginning;
 277
 278     if (!*state && !h->iterate_list_tail)
 279         goto at_beginning;
 280
 281     e = *state ? *state : h->iterate_list_tail;
 282
 283     if (e->iterate_previous)
 284         *state = e->iterate_previous;
 285     else
 286         *state = (void*) -1;
 287
 288     if (key)
 289         *key = e->key;
 290
 291     return e->value;
 292
 293 at_beginning:
 294     *state = (void *) -1;
 295
 296     if (key)
 297         *key = NULL;
 298
 299     return NULL;
 300 }
 301
 302 void* pa_hashmap_first(pa_hashmap *h) {
 303     pa_assert(h);
 304
 305     if (!h->iterate_list_head)
 306         return NULL;
 307
 308     return h->iterate_list_head->value;
 309 }
 310
 311 void* pa_hashmap_last(pa_hashmap *h) {
 312     pa_assert(h);
 313
 314     if (!h->iterate_list_tail)
 315         return NULL;
 316
 317     return h->iterate_list_tail->value;
 318 }
 319
 320 void* pa_hashmap_steal_first(pa_hashmap *h) {
 321     void *data;
 322
 323     pa_assert(h);
 324
 325     if (!h->iterate_list_head)
 326         return NULL;
 327
 328     data = h->iterate_list_head->value;
 329     remove_entry(h, h->iterate_list_head);
 330
 331     return data;
 332 }
 333
 334 unsigned pa_hashmap_size(pa_hashmap *h) {
 335     pa_assert(h);
 336
 337     return h->n_entries;
 338 }
 339
 340 bool pa_hashmap_isempty(pa_hashmap *h) {
 341     pa_assert(h);
 342
 343     return h->n_entries == 0;
 344 }