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