code.delx.au - pulseaudio/blob - polyp/hashmap.c

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