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