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 void pa_hashmap_remove_all(pa_hashmap *h) {
 211     pa_assert(h);
 212
 213     while (h->iterate_list_head) {
 214         void *data;
 215         data = h->iterate_list_head->value;
 216         remove_entry(h, h->iterate_list_head);
 217
 218         if (h->value_free_func)
 219             h->value_free_func(data);
 220     }
 221 }
 222
 223 void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
 224     struct hashmap_entry *e;
 225
 226     pa_assert(h);
 227     pa_assert(state);
 228
 229     if (*state == (void*) -1)
 230         goto at_end;
 231
 232     if (!*state && !h->iterate_list_head)
 233         goto at_end;
 234
 235     e = *state ? *state : h->iterate_list_head;
 236
 237     if (e->iterate_next)
 238         *state = e->iterate_next;
 239     else
 240         *state = (void*) -1;
 241
 242     if (key)
 243         *key = e->key;
 244
 245     return e->value;
 246
 247 at_end:
 248     *state = (void *) -1;
 249
 250     if (key)
 251         *key = NULL;
 252
 253     return NULL;
 254 }
 255
 256 void *pa_hashmap_iterate_backwards(pa_hashmap *h, void **state, const void **key) {
 257     struct hashmap_entry *e;
 258
 259     pa_assert(h);
 260     pa_assert(state);
 261
 262     if (*state == (void*) -1)
 263         goto at_beginning;
 264
 265     if (!*state && !h->iterate_list_tail)
 266         goto at_beginning;
 267
 268     e = *state ? *state : h->iterate_list_tail;
 269
 270     if (e->iterate_previous)
 271         *state = e->iterate_previous;
 272     else
 273         *state = (void*) -1;
 274
 275     if (key)
 276         *key = e->key;
 277
 278     return e->value;
 279
 280 at_beginning:
 281     *state = (void *) -1;
 282
 283     if (key)
 284         *key = NULL;
 285
 286     return NULL;
 287 }
 288
 289 void* pa_hashmap_first(pa_hashmap *h) {
 290     pa_assert(h);
 291
 292     if (!h->iterate_list_head)
 293         return NULL;
 294
 295     return h->iterate_list_head->value;
 296 }
 297
 298 void* pa_hashmap_last(pa_hashmap *h) {
 299     pa_assert(h);
 300
 301     if (!h->iterate_list_tail)
 302         return NULL;
 303
 304     return h->iterate_list_tail->value;
 305 }
 306
 307 void* pa_hashmap_steal_first(pa_hashmap *h) {
 308     void *data;
 309
 310     pa_assert(h);
 311
 312     if (!h->iterate_list_head)
 313         return NULL;
 314
 315     data = h->iterate_list_head->value;
 316     remove_entry(h, h->iterate_list_head);
 317
 318     return data;
 319 }
 320
 321 unsigned pa_hashmap_size(pa_hashmap *h) {
 322     pa_assert(h);
 323
 324     return h->n_entries;
 325 }
 326
 327 bool pa_hashmap_isempty(pa_hashmap *h) {
 328     pa_assert(h);
 329
 330     return h->n_entries == 0;
 331 }