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