hashtab.c

   1 /*
   2  * Copyright (c) 2015 Mohamed Aslan <maslan@sce.carleton.ca>
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #include <stdio.h>
  18 #include <stdint.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21
  22 #include "hashtab.h"
  23
  24
  25 #define KV_USED         (1 << 0)
  26
  27
  28 struct hashtab_kv {
  29         void *key;
  30         void *val;
  31         size_t key_size;
  32         size_t val_size;
  33         uint8_t flags;
  34 };
  35
  36 static uint32_t
  37 pjw_hash(void *key, size_t size)
  38 {
  39         int i;
  40         uint8_t *ptr = (uint8_t *) key;
  41         uint32_t h = 0, hi;
  42
  43         for (i = 0; i < size; i++) {
  44                 h = (h << 4) + ptr[i];
  45                 if ((hi = h & 0xf0000000))
  46                         h ^= hi >> 24;
  47                 hi &= ~hi;
  48         }
  49         return h;
  50 }
  51
  52 static int
  53 alloc(struct hashtab *ht, void *key, size_t size, size_t *idx)
  54 {
  55         size_t i = 0;
  56         size_t h;
  57
  58         h = ht->hash(key, size) % ht->size;
  59         while (i++ < ht->size) {
  60                 if (!(ht->kv[h].flags & KV_USED)) {     /* 1. empty slot */
  61                         *idx = h;
  62                         return 1;
  63                 }
  64                 if (ht->kv[h].key_size == size) {       /* 2. used by the same
  65                                                          * key */
  66                         if (!(memcmp(ht->kv[h].key, key, size))) {
  67                                 *idx = h;
  68                                 return 1;
  69                         }
  70                 }
  71                 h = (h + 1) % ht->size; /* 3. used by a different key */
  72         }
  73         return 0;
  74 }
  75
  76 static int
  77 lookup(struct hashtab *ht, void *key, size_t size, size_t *idx)
  78 {
  79         size_t i = 0;
  80         size_t h;
  81
  82         h = ht->hash(key, size) % ht->size;
  83         while (i++ < ht->size) {
  84                 if (ht->kv[h].key_size == size) {
  85                         if (!(memcmp(ht->kv[h].key, key, size))) {
  86                                 *idx = h;
  87                                 return 1;
  88                         }
  89                 }
  90                 h = (h + 1) % ht->size;
  91         }
  92         return 0;
  93 }
  94
  95 static void
  96 put(struct hashtab *ht, size_t idx, void *key, size_t ksize, void *val,
  97     size_t vsize)
  98 {
  99         ht->kv[idx].key = malloc(ksize);
 100         ht->kv[idx].key_size = ksize;
 101         ht->kv[idx].val = malloc(vsize);
 102         ht->kv[idx].val_size = vsize;
 103         memcpy(ht->kv[idx].key, key, ksize);
 104         memcpy(ht->kv[idx].val, val, vsize);
 105         ht->kv[idx].flags |= KV_USED;
 106 }
 107
 108 static void
 109 get(struct hashtab *ht, size_t idx, void **val, size_t *size)
 110 {
 111         *val = ht->kv[idx].val;
 112         *size = ht->kv[idx].val_size;
 113 }
 114
 115 static void
 116 del(struct hashtab *ht, size_t idx)
 117 {
 118         free(ht->kv[idx].key);
 119         free(ht->kv[idx].val);
 120         memset(&ht->kv[idx], 0, sizeof(struct hashtab_kv));
 121 }
 122
 123 int
 124 hashtab_init(struct hashtab *ht, uint8_t size, struct hashtab_options *opts)
 125 {
 126         if (ht == NULL)
 127                 return 0;
 128         if (size < HTMIN || size > HTMAX)
 129                 return 0;
 130         ht->size = 1UL << size;
 131         ht->kv = (struct hashtab_kv *) calloc(ht->size,
 132             sizeof(struct hashtab_kv));
 133         ht->hash = pjw_hash;
 134         return 1;
 135 }
 136
 137 int
 138 hashtab_first(struct hashtab *ht, size_t *iter)
 139 {
 140         if (ht == NULL || iter == NULL)
 141                 return 0;
 142         for (*iter = 0; *iter < ht->size; (*iter)++) {
 143                 if (!(ht->kv[*iter].flags & KV_USED))
 144                         continue;
 145                 return 1;
 146         }
 147         return 0;
 148 }
 149
 150 int
 151 hashtab_next(struct hashtab *ht, size_t *iter)
 152 {
 153         if (ht == NULL || iter == NULL)
 154                 return 0;
 155         for ((*iter)++; *iter < ht->size; (*iter)++) {
 156                 if (!(ht->kv[*iter].flags & KV_USED))
 157                         continue;
 158                 return 1;
 159         }
 160         return 0;
 161 }
 162
 163 int
 164 hashtab_at(struct hashtab *ht, size_t iter, void **key, size_t *ksize,
 165     void **val, size_t *vsize)
 166 {
 167         if (ht == NULL || key == NULL || ksize == NULL || val == NULL ||
 168             vsize == NULL)
 169                 return 0;
 170         if (iter >= ht->size)
 171                 return 0;
 172         if (!(ht->kv[iter].flags & KV_USED))
 173                 return 0;
 174         *key = ht->kv[iter].key;
 175         *ksize = ht->kv[iter].key_size;
 176         *val = ht->kv[iter].val;
 177         *vsize = ht->kv[iter].val_size;
 178         return 1;
 179 }
 180
 181 int
 182 hashtab_put(struct hashtab *ht, void *key, size_t ksize, void *val,
 183     size_t vsize)
 184 {
 185         size_t idx;
 186
 187         if (ht == NULL)
 188                 return 0;
 189         if (!alloc(ht, key, ksize, &idx))
 190                 return 0;
 191         put(ht, idx, key, ksize, val, vsize);
 192         return 1;
 193 }
 194
 195 int
 196 hashtab_get(struct hashtab *ht, void *key, size_t ksize, void **val,
 197     size_t *vsize)
 198 {
 199         size_t idx;
 200
 201         if (ht == NULL || val == NULL || vsize == NULL)
 202                 return 0;
 203         if (!lookup(ht, key, ksize, &idx))
 204                 return 0;
 205         get(ht, idx, val, vsize);
 206         return 1;
 207 }
 208
 209 int
 210 hashtab_del(struct hashtab *ht, void *key, size_t size)
 211 {
 212         size_t idx;
 213
 214         if (ht == NULL)
 215                 return 0;
 216         if (!lookup(ht, key, size, &idx))
 217                 return 0;
 218         del(ht, idx);
 219         return 1;
 220 }