code.delx.au - pulseaudio/blob - src/pulsecore/hashmap.c

   1 /***
   2   This file is part of PulseAudio.
   3
   4   Copyright 2004-2006 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 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
  31 #include <pulsecore/idxset.h>
  32 #include <pulsecore/log.h>
  33 #include <pulsecore/flist.h>
  34 #include <pulsecore/macro.h>
  35
  36 #include "hashmap.h"
  37
  38 #define BUCKETS 127
  39
  40 struct hashmap_entry {
  41     struct hashmap_entry *next, *previous, *bucket_next, *bucket_previous;
  42     unsigned hash;
  43     const void *key;
  44     void *value;
  45 };
  46
  47 struct pa_hashmap {
  48     unsigned size;
  49     struct hashmap_entry **data;
  50     struct hashmap_entry *first_entry;
  51
  52     unsigned n_entries;
  53     pa_hash_func_t hash_func;
  54     pa_compare_func_t compare_func;
  55 };
  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_xnew(pa_hashmap, 1);
  63     h->data = pa_xnew0(struct hashmap_entry*, h->size = BUCKETS);
  64     h->first_entry = NULL;
  65     h->n_entries = 0;
  66     h->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
  67     h->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
  68
  69     return h;
  70 }
  71
  72 static void remove_entry(pa_hashmap *h, struct hashmap_entry *e) {
  73     pa_assert(h);
  74     pa_assert(e);
  75
  76     if (e->next)
  77         e->next->previous = e->previous;
  78     if (e->previous)
  79         e->previous->next = e->next;
  80     else
  81         h->first_entry = e->next;
  82
  83     if (e->bucket_next)
  84         e->bucket_next->bucket_previous = e->bucket_previous;
  85     if (e->bucket_previous)
  86         e->bucket_previous->bucket_next = e->bucket_next;
  87     else {
  88         pa_assert(e->hash < h->size);
  89         h->data[e->hash] = e->bucket_next;
  90     }
  91
  92     if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
  93         pa_xfree(e);
  94
  95     h->n_entries--;
  96 }
  97
  98 void pa_hashmap_free(pa_hashmap*h, void (*free_func)(void *p, void *userdata), void *userdata) {
  99     pa_assert(h);
 100
 101     while (h->first_entry) {
 102         if (free_func)
 103             free_func(h->first_entry->value, userdata);
 104         remove_entry(h, h->first_entry);
 105     }
 106
 107     pa_xfree(h->data);
 108     pa_xfree(h);
 109 }
 110
 111 static struct hashmap_entry *get(pa_hashmap *h, unsigned hash, const void *key) {
 112     struct hashmap_entry *e;
 113     pa_assert(h);
 114     pa_assert(hash < h->size);
 115
 116     for (e = h->data[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     pa_assert(h);
 127
 128     hash = h->hash_func(key) % h->size;
 129
 130     if ((e = get(h, hash, key)))
 131         return -1;
 132
 133     if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
 134         e = pa_xnew(struct hashmap_entry, 1);
 135
 136     e->hash = hash;
 137     e->key = key;
 138     e->value = value;
 139
 140     e->previous = NULL;
 141     e->next = h->first_entry;
 142     if (h->first_entry)
 143         h->first_entry->previous = e;
 144     h->first_entry = e;
 145
 146     e->bucket_previous = NULL;
 147     e->bucket_next = h->data[hash];
 148     if (h->data[hash])
 149         h->data[hash]->bucket_previous = e;
 150     h->data[hash] = e;
 151
 152     h->n_entries ++;
 153     return 0;
 154 }
 155
 156 void* pa_hashmap_get(pa_hashmap *h, const void *key) {
 157     unsigned hash;
 158     struct hashmap_entry *e;
 159
 160     pa_assert(h);
 161
 162     hash = h->hash_func(key) % h->size;
 163
 164     if (!(e = get(h, hash, key)))
 165         return NULL;
 166
 167     return e->value;
 168 }
 169
 170 void* pa_hashmap_remove(pa_hashmap *h, const void *key) {
 171     struct hashmap_entry *e;
 172     unsigned hash;
 173     void *data;
 174
 175     pa_assert(h);
 176
 177     hash = h->hash_func(key) % h->size;
 178
 179     if (!(e = get(h, hash, key)))
 180         return NULL;
 181
 182     data = e->value;
 183     remove_entry(h, e);
 184     return data;
 185 }
 186
 187 unsigned pa_hashmap_size(pa_hashmap *h) {
 188     return h->n_entries;
 189 }
 190
 191 void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
 192     struct hashmap_entry *e;
 193
 194     pa_assert(h);
 195     pa_assert(state);
 196
 197     if (*state == (void*) -1)
 198         goto at_end;
 199
 200     if ((!*state && !h->first_entry))
 201         goto at_end;
 202
 203     e = *state ? *state : h->first_entry;
 204
 205     if (e->next)
 206         *state = e->next;
 207     else
 208         *state = (void*) -1;
 209
 210     if (key)
 211         *key = e->key;
 212
 213     return e->value;
 214
 215 at_end:
 216     *state = (void *) -1;
 217
 218     if (key)
 219         *key = NULL;
 220
 221     return NULL;
 222 }
 223
 224 void* pa_hashmap_steal_first(pa_hashmap *h) {
 225     void *data;
 226
 227     pa_assert(h);
 228
 229     if (!h->first_entry)
 230         return NULL;
 231
 232     data = h->first_entry->value;
 233     remove_entry(h, h->first_entry);
 234     return data;
 235 }
 236
 237 void *pa_hashmap_get_first(pa_hashmap *h) {
 238     pa_assert(h);
 239
 240     if (!h->first_entry)
 241         return NULL;
 242
 243     return h->first_entry->value;
 244 }