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 #include <string.h>
  28
  29 #include <pulse/xmalloc.h>
  30 #include <pulsecore/idxset.h>
  31 #include <pulsecore/log.h>
  32 #include <pulsecore/flist.h>
  33 #include <pulsecore/macro.h>
  34
  35 #include "hashmap.h"
  36
  37 #define NBUCKETS 127
  38
  39 struct hashmap_entry {
  40     const void *key;
  41     void *value;
  42
  43     struct hashmap_entry *bucket_next, *bucket_previous;
  44     struct hashmap_entry *iterate_next, *iterate_previous;
  45 };
  46
  47 struct pa_hashmap {
  48     pa_hash_func_t hash_func;
  49     pa_compare_func_t compare_func;
  50
  51     struct hashmap_entry *iterate_list_head, *iterate_list_tail;
  52     unsigned n_entries;
  53 };
  54
  55 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + PA_ALIGN(sizeof(pa_hashmap))))
  56
  57 PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
  58
  59 pa_hashmap *pa_hashmap_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
  60     pa_hashmap *h;
  61
  62     h = pa_xmalloc0(PA_ALIGN(sizeof(pa_hashmap)) + NBUCKETS*sizeof(struct hashmap_entry*));
  63
  64     h->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
  65     h->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
  66
  67     h->n_entries = 0;
  68     h->iterate_list_head = h->iterate_list_tail = NULL;
  69
  70     return h;
  71 }
  72
  73 static void remove_entry(pa_hashmap *h, struct hashmap_entry *e) {
  74     pa_assert(h);
  75     pa_assert(e);
  76
  77     /* Remove from iteration list */
  78     if (e->iterate_next)
  79         e->iterate_next->iterate_previous = e->iterate_previous;
  80     else
  81         h->iterate_list_tail = e->iterate_previous;
  82
  83     if (e->iterate_previous)
  84         e->iterate_previous->iterate_next = e->iterate_next;
  85     else
  86         h->iterate_list_head = e->iterate_next;
  87
  88     /* Remove from hash table bucket list */
  89     if (e->bucket_next)
  90         e->bucket_next->bucket_previous = e->bucket_previous;
  91
  92     if (e->bucket_previous)
  93         e->bucket_previous->bucket_next = e->bucket_next;
  94     else {
  95         unsigned hash = h->hash_func(e->key) % NBUCKETS;
  96         BY_HASH(h)[hash] = e->bucket_next;
  97     }
  98
  99     if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
 100         pa_xfree(e);
 101
 102     pa_assert(h->n_entries >= 1);
 103     h->n_entries--;
 104 }
 105
 106 void pa_hashmap_free(pa_hashmap*h, pa_free2_cb_t free_cb, void *userdata) {
 107     pa_assert(h);
 108
 109     while (h->iterate_list_head) {
 110         void *data;
 111         data = h->iterate_list_head->value;
 112         remove_entry(h, h->iterate_list_head);
 113
 114         if (free_cb)
 115             free_cb(data, userdata);
 116     }
 117
 118     pa_xfree(h);
 119 }
 120
 121 static struct hashmap_entry *hash_scan(pa_hashmap *h, unsigned hash, const void *key) {
 122     struct hashmap_entry *e;
 123     pa_assert(h);
 124     pa_assert(hash < NBUCKETS);
 125
 126     for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 127         if (h->compare_func(e->key, key) == 0)
 128             return e;
 129
 130     return NULL;
 131 }
 132
 133 int pa_hashmap_put(pa_hashmap *h, const void *key, void *value) {
 134     struct hashmap_entry *e;
 135     unsigned hash;
 136
 137     pa_assert(h);
 138
 139     hash = h->hash_func(key) % NBUCKETS;
 140
 141     if (hash_scan(h, hash, key))
 142         return -1;
 143
 144     if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
 145         e = pa_xnew(struct hashmap_entry, 1);
 146
 147     e->key = key;
 148     e->value = value;
 149
 150     /* Insert into hash table */
 151     e->bucket_next = BY_HASH(h)[hash];
 152     e->bucket_previous = NULL;
 153     if (BY_HASH(h)[hash])
 154         BY_HASH(h)[hash]->bucket_previous = e;
 155     BY_HASH(h)[hash] = e;
 156
 157     /* Insert into iteration list */
 158     e->iterate_previous = h->iterate_list_tail;
 159     e->iterate_next = NULL;
 160     if (h->iterate_list_tail) {
 161         pa_assert(h->iterate_list_head);
 162         h->iterate_list_tail->iterate_next = e;
 163     } else {
 164         pa_assert(!h->iterate_list_head);
 165         h->iterate_list_head = e;
 166     }
 167     h->iterate_list_tail = e;
 168
 169     h->n_entries++;
 170     pa_assert(h->n_entries >= 1);
 171
 172     return 0;
 173 }
 174
 175 void* pa_hashmap_get(pa_hashmap *h, const void *key) {
 176     unsigned hash;
 177     struct hashmap_entry *e;
 178
 179     pa_assert(h);
 180
 181     hash = h->hash_func(key) % NBUCKETS;
 182
 183     if (!(e = hash_scan(h, hash, key)))
 184         return NULL;
 185
 186     return e->value;
 187 }
 188
 189 void* pa_hashmap_remove(pa_hashmap *h, const void *key) {
 190     struct hashmap_entry *e;
 191     unsigned hash;
 192     void *data;
 193
 194     pa_assert(h);
 195
 196     hash = h->hash_func(key) % NBUCKETS;
 197
 198     if (!(e = hash_scan(h, hash, key)))
 199         return NULL;
 200
 201     data = e->value;
 202     remove_entry(h, e);
 203
 204     return data;
 205 }
 206
 207 void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
 208     struct hashmap_entry *e;
 209
 210     pa_assert(h);
 211     pa_assert(state);
 212
 213     if (*state == (void*) -1)
 214         goto at_end;
 215
 216     if (!*state && !h->iterate_list_head)
 217         goto at_end;
 218
 219     e = *state ? *state : h->iterate_list_head;
 220
 221     if (e->iterate_next)
 222         *state = e->iterate_next;
 223     else
 224         *state = (void*) -1;
 225
 226     if (key)
 227         *key = e->key;
 228
 229     return e->value;
 230
 231 at_end:
 232     *state = (void *) -1;
 233
 234     if (key)
 235         *key = NULL;
 236
 237     return NULL;
 238 }
 239
 240 void *pa_hashmap_iterate_backwards(pa_hashmap *h, void **state, const void **key) {
 241     struct hashmap_entry *e;
 242
 243     pa_assert(h);
 244     pa_assert(state);
 245
 246     if (*state == (void*) -1)
 247         goto at_beginning;
 248
 249     if (!*state && !h->iterate_list_tail)
 250         goto at_beginning;
 251
 252     e = *state ? *state : h->iterate_list_tail;
 253
 254     if (e->iterate_previous)
 255         *state = e->iterate_previous;
 256     else
 257         *state = (void*) -1;
 258
 259     if (key)
 260         *key = e->key;
 261
 262     return e->value;
 263
 264 at_beginning:
 265     *state = (void *) -1;
 266
 267     if (key)
 268         *key = NULL;
 269
 270     return NULL;
 271 }
 272
 273 void* pa_hashmap_first(pa_hashmap *h) {
 274     pa_assert(h);
 275
 276     if (!h->iterate_list_head)
 277         return NULL;
 278
 279     return h->iterate_list_head->value;
 280 }
 281
 282 void* pa_hashmap_last(pa_hashmap *h) {
 283     pa_assert(h);
 284
 285     if (!h->iterate_list_tail)
 286         return NULL;
 287
 288     return h->iterate_list_tail->value;
 289 }
 290
 291 void* pa_hashmap_steal_first(pa_hashmap *h) {
 292     void *data;
 293
 294     pa_assert(h);
 295
 296     if (!h->iterate_list_head)
 297         return NULL;
 298
 299     data = h->iterate_list_head->value;
 300     remove_entry(h, h->iterate_list_head);
 301
 302     return data;
 303 }
 304
 305 unsigned pa_hashmap_size(pa_hashmap *h) {
 306     pa_assert(h);
 307
 308     return h->n_entries;
 309 }
 310
 311 pa_bool_t pa_hashmap_isempty(pa_hashmap *h) {
 312     pa_assert(h);
 313
 314     return h->n_entries == 0;
 315 }