src/shl_hashtable.h

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