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