src/shl_hashtable.h

   1 /*
   2  * shl - Dynamic Array
   3  *
   4  * Copyright (c) 2011-2012 David Herrmann <dh.herrmann@googlemail.com>
   5  * Copyright (c) 2011 University of Tuebingen
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining
   8  * a copy of this software and associated documentation files
   9  * (the "Software"), to deal in the Software without restriction, including
  10  * without limitation the rights to use, copy, modify, merge, publish,
  11  * distribute, sublicense, and/or sell copies of the Software, and to
  12  * permit persons to whom the Software is furnished to do so, subject to
  13  * the following conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be included
  16  * in all copies or substantial portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  21  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  22  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  */
  26
  27 /*
  28  * A dynamic hash table implementation
  29  */
  30
  31 #ifndef SHL_HASHTABLE_H
  32 #define SHL_HASHTABLE_H
  33
  34 #include <errno.h>
  35 #include <stdbool.h>
  36 #include <stddef.h>
  37 #include <stdint.h>
  38 #include <stdlib.h>
  39 #include "external/htable.h"
  40
  41 struct shl_hashtable;
  42
  43 typedef unsigned int (*shl_hash_cb) (const void *data);
  44 typedef bool (*shl_equal_cb) (const void *data1, const void *data2);
  45 typedef void (*shl_free_cb) (void *data);
  46
  47 struct shl_hashentry {
  48         void *key;
  49         void *value;
  50 };
  51
  52 struct shl_hashtable {
  53         struct htable tbl;
  54         shl_hash_cb hash_cb;
  55         shl_equal_cb equal_cb;
  56         shl_free_cb free_key;
  57         shl_free_cb free_value;
  58 };
  59
  60 static inline unsigned int shl_direct_hash(const void *data)
  61 {
  62         return (unsigned int)(unsigned long)data;
  63 }
  64
  65 static inline bool shl_direct_equal(const void *data1, const void *data2)
  66 {
  67         return data1 == data2;
  68 }
  69
  70 static size_t shl_rehash(const void *ele, void *priv)
  71 {
  72         struct shl_hashtable *tbl = priv;
  73         const struct shl_hashentry *ent = ele;
  74
  75         return tbl->hash_cb(ent->key);
  76 }
  77
  78 static inline int shl_hashtable_new(struct shl_hashtable **out,
  79                                     shl_hash_cb hash_cb,
  80                                     shl_equal_cb equal_cb,
  81                                     shl_free_cb free_key,
  82                                     shl_free_cb free_value)
  83 {
  84         struct shl_hashtable *tbl;
  85
  86         if (!out || !hash_cb || !equal_cb)
  87                 return -EINVAL;
  88
  89         tbl = malloc(sizeof(*tbl));
  90         if (!tbl)
  91                 return -ENOMEM;
  92         memset(tbl, 0, sizeof(*tbl));
  93         tbl->hash_cb = hash_cb;
  94         tbl->equal_cb = equal_cb;
  95         tbl->free_key = free_key;
  96         tbl->free_value = free_value;
  97
  98         htable_init(&tbl->tbl, shl_rehash, tbl);
  99
 100         *out = tbl;
 101         return 0;
 102 }
 103
 104 static inline void shl_hashtable_free(struct shl_hashtable *tbl)
 105 {
 106         struct htable_iter i;
 107         struct shl_hashentry *entry;
 108
 109         if (!tbl)
 110                 return;
 111
 112         for (entry = htable_first(&tbl->tbl, &i);
 113              entry;
 114              entry = htable_next(&tbl->tbl, &i)) {
 115                 htable_delval(&tbl->tbl, &i);
 116                 if (tbl->free_key)
 117                         tbl->free_key(entry->key);
 118                 if (tbl->free_value)
 119                         tbl->free_value(entry->value);
 120                 free(entry);
 121         }
 122
 123         htable_clear(&tbl->tbl);
 124         free(tbl);
 125 }
 126
 127 static inline int shl_hashtable_insert(struct shl_hashtable *tbl, void *key,
 128                                        void *value)
 129 {
 130         struct shl_hashentry *entry;
 131         size_t hash;
 132
 133         if (!tbl)
 134                 return -EINVAL;
 135
 136         entry = malloc(sizeof(*entry));
 137         if (!entry)
 138                 return -ENOMEM;
 139         entry->key = key;
 140         entry->value = value;
 141
 142         hash = tbl->hash_cb(key);
 143
 144         if (!htable_add(&tbl->tbl, hash, entry)) {
 145                 free(entry);
 146                 return -ENOMEM;
 147         }
 148
 149         return 0;
 150 }
 151
 152 static inline void shl_hashtable_remove(struct shl_hashtable *tbl, void *key)
 153 {
 154         struct htable_iter i;
 155         struct shl_hashentry *entry;
 156         size_t hash;
 157
 158         if (!tbl)
 159                 return;
 160
 161         hash = tbl->hash_cb(key);
 162
 163         for (entry = htable_firstval(&tbl->tbl, &i, hash);
 164              entry;
 165              entry = htable_nextval(&tbl->tbl, &i, hash)) {
 166                 if (tbl->equal_cb(key, entry->key)) {
 167                         htable_delval(&tbl->tbl, &i);
 168                         return;
 169                 }
 170         }
 171 }
 172
 173 static inline bool shl_hashtable_find(struct shl_hashtable *tbl, void **out,
 174                                       void *key)
 175 {
 176         struct htable_iter i;
 177         struct shl_hashentry *entry;
 178         size_t hash;
 179
 180         if (!tbl)
 181                 return false;
 182
 183         hash = tbl->hash_cb(key);
 184
 185         for (entry = htable_firstval(&tbl->tbl, &i, hash);
 186              entry;
 187              entry = htable_nextval(&tbl->tbl, &i, hash)) {
 188                 if (tbl->equal_cb(key, entry->key)) {
 189                         if (out)
 190                                 *out = entry->value;
 191                         return true;
 192                 }
 193         }
 194
 195         return false;
 196 }
 197
 198 #endif /* SHL_HASHTABLE_H */