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