code.delx.au - pulseaudio/blob - 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     unsigned (*hash_func) (const void *p);
  53     int (*compare_func) (const void*a, const void*b);
  54 };
  55
  56 pa_hashmap *pa_hashmap_new(unsigned (*hash_func) (const void *p), int (*compare_func) (const void*a, const void*b)) {
  57     pa_hashmap *h;
  58     h = pa_xmalloc(sizeof(pa_hashmap));
  59     h->data = pa_xmalloc0(sizeof(struct hashmap_entry*)*(h->size = BUCKETS));
  60     h->first_entry = NULL;
  61     h->n_entries = 0;
  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     return h;
  65 }
  66
  67 static void remove(pa_hashmap *h, struct hashmap_entry *e) {
  68     assert(e);
  69
  70     if (e->next)
  71         e->next->previous = e->previous;
  72     if (e->previous)
  73         e->previous->next = e->next;
  74     else
  75         h->first_entry = e->next;
  76
  77     if (e->bucket_next)
  78         e->bucket_next->bucket_previous = e->bucket_previous;
  79     if (e->bucket_previous)
  80         e->bucket_previous->bucket_next = e->bucket_next;
  81     else {
  82         assert(e->hash < h->size);
  83         h->data[e->hash] = e->bucket_next;
  84     }
  85
  86     pa_xfree(e);
  87     h->n_entries--;
  88 }
  89
  90 void pa_hashmap_free(pa_hashmap*h, void (*free_func)(void *p, void *userdata), void *userdata) {
  91     assert(h);
  92
  93     while (h->first_entry) {
  94         if (free_func)
  95             free_func(h->first_entry->value, userdata);
  96         remove(h, h->first_entry);
  97     }
  98
  99     pa_xfree(h->data);
 100     pa_xfree(h);
 101 }
 102
 103 static struct hashmap_entry *get(pa_hashmap *h, unsigned hash, const void *key) {
 104     struct hashmap_entry *e;
 105     assert(h && hash < h->size);
 106
 107     for (e = h->data[hash]; e; e = e->bucket_next)
 108         if (h->compare_func(e->key, key) == 0)
 109             return e;
 110
 111     return NULL;
 112 }
 113
 114 int pa_hashmap_put(pa_hashmap *h, const void *key, void *value) {
 115     struct hashmap_entry *e;
 116     unsigned hash;
 117     assert(h);
 118
 119     hash = h->hash_func(key) % h->size;
 120
 121     if ((e = get(h, hash, key)))
 122         return -1;
 123
 124     e = pa_xmalloc(sizeof(struct hashmap_entry));
 125     e->hash = hash;
 126     e->key = key;
 127     e->value = value;
 128
 129     e->previous = NULL;
 130     e->next = h->first_entry;
 131     if (h->first_entry)
 132         h->first_entry->previous = e;
 133     h->first_entry = e;
 134
 135     e->bucket_previous = NULL;
 136     e->bucket_next = h->data[hash];
 137     if (h->data[hash])
 138         h->data[hash]->bucket_previous = e;
 139     h->data[hash] = e;
 140
 141     h->n_entries ++;
 142     return 0;
 143 }
 144
 145 void* pa_hashmap_get(pa_hashmap *h, const void *key) {
 146     unsigned hash;
 147     struct hashmap_entry *e;
 148     assert(h && key);
 149
 150     hash = h->hash_func(key) % h->size;
 151
 152     if (!(e = get(h, hash, key)))
 153         return NULL;
 154
 155     return e->value;
 156 }
 157
 158 void* pa_hashmap_remove(pa_hashmap *h, const void *key) {
 159     struct hashmap_entry *e;
 160     unsigned hash;
 161     void *data;
 162     assert(h && key);
 163
 164     hash = h->hash_func(key) % h->size;
 165
 166     if (!(e = get(h, hash, key)))
 167         return NULL;
 168
 169     data = e->value;
 170     remove(h, e);
 171     return data;
 172 }
 173
 174 unsigned pa_hashmap_size(pa_hashmap *h) {
 175     return h->n_entries;
 176 }
 177
 178 void *pa_hashmap_iterate(pa_hashmap *h, void **state, const void **key) {
 179     assert(h && state);
 180
 181     if (!*state)
 182         *state = h->first_entry;
 183     else
 184         *state = ((struct hashmap_entry*) *state)->next;
 185
 186     if (!*state) {
 187         if (key)
 188             *key = NULL;
 189         return NULL;
 190     }
 191
 192     if (key)
 193         *key = ((struct hashmap_entry*) *state)->key;
 194
 195     return ((struct hashmap_entry*) *state)->value;
 196 }