src/pulsecore/hashmap.c

   1 /* $Id$ */
   2
   3 /***
   4   This file is part of PulseAudio.
   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 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 <assert.h>
  28 #include <string.h>
  29
  30 #include <pulse/xmalloc.h>
  31
  32 #include <pulsecore/idxset.h>
  33 #include <pulsecore/log.h>
  34
  35 #include "hashmap.h"
  36
  37 #define BUCKETS 127
  38
  39 struct hashmap_entry {
  40     struct hashmap_entry *next, *previous, *bucket_next, *bucket_previous;
  41     unsigned hash;
  42     const void *key;
  43     void *value;
  44 };
  45
  46 struct pa_hashmap {
  47     unsigned size;
  48     struct hashmap_entry **data;
  49     struct hashmap_entry *first_entry;
  50
  51     unsigned n_entries;
  52     pa_hash_func_t hash_func;
  53     pa_compare_func_t compare_func;
  54 };
  55
  56 pa_hashmap *pa_hashmap_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
  57     pa_hashmap *h;
  58
  59     h = pa_xnew(pa_hashmap, 1);
  60     h->data = pa_xnew0(struct hashmap_entry*, h->size = BUCKETS);
  61     h->first_entry = NULL;
  62     h->n_entries = 0;
  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     return h;
  67 }
  68
  69 static void remove(pa_hashmap *h, struct hashmap_entry *e) {
  70     assert(h);
  71     assert(e);
  72
  73     if (e->next)
  74         e->next->previous = e->previous;
  75     if (e->previous)
  76         e->previous->next = e->next;
  77     else
  78         h->first_entry = e->next;
  79
  80     if (e->bucket_next)
  81         e->bucket_next->bucket_previous = e->bucket_previous;
  82     if (e->bucket_previous)
  83         e->bucket_previous->bucket_next = e->bucket_next;
  84     else {
  85         assert(e->hash < h->size);
  86         h->data[e->hash] = e->bucket_next;
  87     }
  88
  89     pa_xfree(e);
  90     h->n_entries--;
  91 }
  92
  93 void pa_hashmap_free(pa_hashmap*h, void (*free_func)(void *p, void *userdata), void *userdata) {
  94     assert(h);
  95
  96     while (h->first_entry) {
  97         if (free_func)
  98             free_func(h->first_entry->value, userdata);
  99         remove(h, h->first_entry);
 100     }
 101
 102     pa_xfree(h->data);
 103     pa_xfree(h);
 104 }
 105
 106 static struct hashmap_entry *get(pa_hashmap *h, unsigned hash, const void *key) {
 107     struct hashmap_entry *e;
 108     assert(h);
 109     assert(hash < h->size);
 110
 111     for (e = h->data[hash]; e; e = e->bucket_next)
 112         if (h->compare_func(e->key, key) == 0)
 113             return e;
 114
 115     return NULL;
 116 }
 117
 118 int pa_hashmap_put(pa_hashmap *h, const void *key, void *value) {
 119     struct hashmap_entry *e;
 120     unsigned hash;
 121     assert(h);
 122
 123     hash = h->hash_func(key) % h->size;
 124
 125     if ((e = get(h, hash, key)))
 126         return -1;
 127
 128     e = pa_xnew(struct hashmap_entry, 1);
 129     e->hash = hash;
 130     e->key = key;
 131     e->value = value;
 132
 133     e->previous = NULL;
 134     e->next = h->first_entry;
 135     if (h->first_entry)
 136         h->first_entry->previous = e;
 137     h->first_entry = e;
 138
 139     e->bucket_previous = NULL;
 140     e->bucket_next = h->data[hash];
 141     if (h->data[hash])
 142         h->data[hash]->bucket_previous = e;
 143     h->data[hash] = e;
 144
 145     h->n_entries ++;
 146     return 0;
 147 }
 148
 149 void* pa_hashmap_get(pa_hashmap *h, const void *key) {
 150     unsigned hash;
 151     struct hashmap_entry *e;
 152
 153     assert(h);
 154
 155     hash = h->hash_func(key) % h->size;
 156
 157     if (!(e = get(h, hash, key)))
 158         return NULL;
 159
 160     return e->value;
 161 }
 162
 163 void* pa_hashmap_remove(pa_hashmap *h, const void *key) {
 164     struct hashmap_entry *e;
 165     unsigned hash;
 166     void *data;
 167
 168     assert(h);
 169
 170     hash = h->hash_func(key) % h->size;
 171
 172     if (!(e = get(h, hash, key)))
 173         return NULL;
 174
 175     data = e->value;
 176     remove(h, e);
 177     return data;
 178 }
 179
 180 unsigned pa_hashmap_size(pa_hashmap *h) {
 181     return h->n_entries;
 182 }
 183
 184 void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
 185     assert(h);
 186     assert(state);
 187
 188     if (!*state)
 189         *state = h->first_entry;
 190     else
 191         *state = ((struct hashmap_entry*) *state)->next;
 192
 193     if (!*state) {
 194         if (key)
 195             *key = NULL;
 196         return NULL;
 197     }
 198
 199     if (key)
 200         *key = ((struct hashmap_entry*) *state)->key;
 201
 202     return ((struct hashmap_entry*) *state)->value;
 203 }
 204
 205 void* pa_hashmap_steal_first(pa_hashmap *h) {
 206     void *data;
 207
 208     assert(h);
 209
 210     if (!h->first_entry)
 211         return NULL;
 212
 213     data = h->first_entry->value;
 214     remove(h, h->first_entry);
 215     return data;
 216 }
 217
 218 void *pa_hashmap_get_first(pa_hashmap *h) {
 219     assert(h);
 220
 221     if (!h->first_entry)
 222         return NULL;
 223
 224     return h->first_entry->value;
 225 }