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

   1 /* $Id$ */
   2
   3 /***
   4   This file is part of PulseAudio.
   5
   6   Copyright 2004-2006 Lennart Poettering
   7
   8   PulseAudio is free software; you can redistribute it and/or modify
   9   it under the terms of the GNU Lesser General Public License as published
  10   by the Free Software Foundation; either version 2 of the License,
  11   or (at your option) any later version.
  12
  13   PulseAudio is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with PulseAudio; if not, write to the Free Software
  20   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  21   USA.
  22 ***/
  23
  24 #ifdef HAVE_CONFIG_H
  25 #include <config.h>
  26 #endif
  27
  28 #include <stdlib.h>
  29 #include <string.h>
  30
  31 #include <pulse/xmalloc.h>
  32
  33 #include <pulsecore/idxset.h>
  34 #include <pulsecore/log.h>
  35 #include <pulsecore/flist.h>
  36 #include <pulsecore/macro.h>
  37
  38 #include "hashmap.h"
  39
  40 #define BUCKETS 127
  41
  42 struct hashmap_entry {
  43     struct hashmap_entry *next, *previous, *bucket_next, *bucket_previous;
  44     unsigned hash;
  45     const void *key;
  46     void *value;
  47 };
  48
  49 struct pa_hashmap {
  50     unsigned size;
  51     struct hashmap_entry **data;
  52     struct hashmap_entry *first_entry;
  53
  54     unsigned n_entries;
  55     pa_hash_func_t hash_func;
  56     pa_compare_func_t compare_func;
  57 };
  58
  59 PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
  60
  61 pa_hashmap *pa_hashmap_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
  62     pa_hashmap *h;
  63
  64     h = pa_xnew(pa_hashmap, 1);
  65     h->data = pa_xnew0(struct hashmap_entry*, h->size = BUCKETS);
  66     h->first_entry = NULL;
  67     h->n_entries = 0;
  68     h->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
  69     h->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
  70
  71     return h;
  72 }
  73
  74 static void remove_entry(pa_hashmap *h, struct hashmap_entry *e) {
  75     pa_assert(h);
  76     pa_assert(e);
  77
  78     if (e->next)
  79         e->next->previous = e->previous;
  80     if (e->previous)
  81         e->previous->next = e->next;
  82     else
  83         h->first_entry = e->next;
  84
  85     if (e->bucket_next)
  86         e->bucket_next->bucket_previous = e->bucket_previous;
  87     if (e->bucket_previous)
  88         e->bucket_previous->bucket_next = e->bucket_next;
  89     else {
  90         pa_assert(e->hash < h->size);
  91         h->data[e->hash] = e->bucket_next;
  92     }
  93
  94     if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
  95         pa_xfree(e);
  96
  97     h->n_entries--;
  98 }
  99
 100 void pa_hashmap_free(pa_hashmap*h, void (*free_func)(void *p, void *userdata), void *userdata) {
 101     pa_assert(h);
 102
 103     while (h->first_entry) {
 104         if (free_func)
 105             free_func(h->first_entry->value, userdata);
 106         remove_entry(h, h->first_entry);
 107     }
 108
 109     pa_xfree(h->data);
 110     pa_xfree(h);
 111 }
 112
 113 static struct hashmap_entry *get(pa_hashmap *h, unsigned hash, const void *key) {
 114     struct hashmap_entry *e;
 115     pa_assert(h);
 116     pa_assert(hash < h->size);
 117
 118     for (e = h->data[hash]; e; e = e->bucket_next)
 119         if (h->compare_func(e->key, key) == 0)
 120             return e;
 121
 122     return NULL;
 123 }
 124
 125 int pa_hashmap_put(pa_hashmap *h, const void *key, void *value) {
 126     struct hashmap_entry *e;
 127     unsigned hash;
 128     pa_assert(h);
 129
 130     hash = h->hash_func(key) % h->size;
 131
 132     if ((e = get(h, hash, key)))
 133         return -1;
 134
 135     if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
 136         e = pa_xnew(struct hashmap_entry, 1);
 137
 138     e->hash = hash;
 139     e->key = key;
 140     e->value = value;
 141
 142     e->previous = NULL;
 143     e->next = h->first_entry;
 144     if (h->first_entry)
 145         h->first_entry->previous = e;
 146     h->first_entry = e;
 147
 148     e->bucket_previous = NULL;
 149     e->bucket_next = h->data[hash];
 150     if (h->data[hash])
 151         h->data[hash]->bucket_previous = e;
 152     h->data[hash] = e;
 153
 154     h->n_entries ++;
 155     return 0;
 156 }
 157
 158 void* pa_hashmap_get(pa_hashmap *h, const void *key) {
 159     unsigned hash;
 160     struct hashmap_entry *e;
 161
 162     pa_assert(h);
 163
 164     hash = h->hash_func(key) % h->size;
 165
 166     if (!(e = get(h, hash, key)))
 167         return NULL;
 168
 169     return e->value;
 170 }
 171
 172 void* pa_hashmap_remove(pa_hashmap *h, const void *key) {
 173     struct hashmap_entry *e;
 174     unsigned hash;
 175     void *data;
 176
 177     pa_assert(h);
 178
 179     hash = h->hash_func(key) % h->size;
 180
 181     if (!(e = get(h, hash, key)))
 182         return NULL;
 183
 184     data = e->value;
 185     remove_entry(h, e);
 186     return data;
 187 }
 188
 189 unsigned pa_hashmap_size(pa_hashmap *h) {
 190     return h->n_entries;
 191 }
 192
 193 void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
 194     pa_assert(h);
 195     pa_assert(state);
 196
 197     if (!*state)
 198         *state = h->first_entry;
 199     else
 200         *state = ((struct hashmap_entry*) *state)->next;
 201
 202     if (!*state) {
 203         if (key)
 204             *key = NULL;
 205         return NULL;
 206     }
 207
 208     if (key)
 209         *key = ((struct hashmap_entry*) *state)->key;
 210
 211     return ((struct hashmap_entry*) *state)->value;
 212 }
 213
 214 void* pa_hashmap_steal_first(pa_hashmap *h) {
 215     void *data;
 216
 217     pa_assert(h);
 218
 219     if (!h->first_entry)
 220         return NULL;
 221
 222     data = h->first_entry->value;
 223     remove_entry(h, h->first_entry);
 224     return data;
 225 }
 226
 227 void *pa_hashmap_get_first(pa_hashmap *h) {
 228     pa_assert(h);
 229
 230     if (!h->first_entry)
 231         return NULL;
 232
 233     return h->first_entry->value;
 234 }