shared/hash.c

   1 /*
   2  * libkmod - interface to kernel module operations
   3  *
   4  * Copyright (C) 2011-2013  ProFUSION embedded systems
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  */
  20
  21 #include <errno.h>
  22 #include <inttypes.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #include <shared/hash.h>
  27 #include <shared/util.h>
  28
  29 struct hash_entry {
  30         const char *key;
  31         const void *value;
  32 };
  33
  34 struct hash_bucket {
  35         struct hash_entry *entries;
  36         unsigned int used;
  37         unsigned int total;
  38 };
  39
  40 struct hash {
  41         unsigned int count;
  42         unsigned int step;
  43         unsigned int n_buckets;
  44         void (*free_value)(void *value);
  45         struct hash_bucket buckets[];
  46 };
  47
  48 struct hash *hash_new(unsigned int n_buckets,
  49                                         void (*free_value)(void *value))
  50 {
  51         struct hash *hash;
  52
  53         n_buckets = ALIGN_POWER2(n_buckets);
  54         hash = calloc(1, sizeof(struct hash) +
  55                       n_buckets * sizeof(struct hash_bucket));
  56         if (hash == NULL)
  57                 return NULL;
  58         hash->n_buckets = n_buckets;
  59         hash->free_value = free_value;
  60         hash->step = n_buckets / 32;
  61         if (hash->step == 0)
  62                 hash->step = 4;
  63         else if (hash->step > 64)
  64                 hash->step = 64;
  65         return hash;
  66 }
  67
  68 void hash_free(struct hash *hash)
  69 {
  70         struct hash_bucket *bucket, *bucket_end;
  71
  72         if (hash == NULL)
  73                 return;
  74
  75         bucket = hash->buckets;
  76         bucket_end = bucket + hash->n_buckets;
  77         for (; bucket < bucket_end; bucket++) {
  78                 if (hash->free_value) {
  79                         struct hash_entry *entry, *entry_end;
  80                         entry = bucket->entries;
  81                         entry_end = entry + bucket->used;
  82                         for (; entry < entry_end; entry++)
  83                                 hash->free_value((void *)entry->value);
  84                 }
  85                 free(bucket->entries);
  86         }
  87         free(hash);
  88 }
  89
  90 static inline unsigned int hash_superfast(const char *key, unsigned int len)
  91 {
  92         /* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html)
  93          * used by WebCore (http://webkit.org/blog/8/hashtables-part-2/)
  94          * EFL's eina and possible others.
  95          */
  96         unsigned int tmp, hash = len, rem = len & 3;
  97
  98         len /= 4;
  99
 100         /* Main loop */
 101         for (; len > 0; len--) {
 102                 hash += get_unaligned((uint16_t *) key);
 103                 tmp = (get_unaligned((uint16_t *)(key + 2)) << 11) ^ hash;
 104                 hash = (hash << 16) ^ tmp;
 105                 key += 4;
 106                 hash += hash >> 11;
 107         }
 108
 109         /* Handle end cases */
 110         switch (rem) {
 111         case 3:
 112                 hash += get_unaligned((uint16_t *) key);
 113                 hash ^= hash << 16;
 114                 hash ^= key[2] << 18;
 115                 hash += hash >> 11;
 116                 break;
 117
 118         case 2:
 119                 hash += get_unaligned((uint16_t *) key);
 120                 hash ^= hash << 11;
 121                 hash += hash >> 17;
 122                 break;
 123
 124         case 1:
 125                 hash += *key;
 126                 hash ^= hash << 10;
 127                 hash += hash >> 1;
 128         }
 129
 130         /* Force "avalanching" of final 127 bits */
 131         hash ^= hash << 3;
 132         hash += hash >> 5;
 133         hash ^= hash << 4;
 134         hash += hash >> 17;
 135         hash ^= hash << 25;
 136         hash += hash >> 6;
 137
 138         return hash;
 139 }
 140
 141 /*
 142  * add or replace key in hash map.
 143  *
 144  * none of key or value are copied, just references are remembered as is,
 145  * make sure they are live while pair exists in hash!
 146  */
 147 int hash_add(struct hash *hash, const char *key, const void *value)
 148 {
 149         unsigned int keylen = strlen(key);
 150         unsigned int hashval = hash_superfast(key, keylen);
 151         unsigned int pos = hashval & (hash->n_buckets - 1);
 152         struct hash_bucket *bucket = hash->buckets + pos;
 153         struct hash_entry *entry, *entry_end;
 154
 155         if (bucket->used + 1 >= bucket->total) {
 156                 unsigned new_total = bucket->total + hash->step;
 157                 size_t size = new_total * sizeof(struct hash_entry);
 158                 struct hash_entry *tmp = realloc(bucket->entries, size);
 159                 if (tmp == NULL)
 160                         return -errno;
 161                 bucket->entries = tmp;
 162                 bucket->total = new_total;
 163         }
 164
 165         entry = bucket->entries;
 166         entry_end = entry + bucket->used;
 167         for (; entry < entry_end; entry++) {
 168                 int c = strcmp(key, entry->key);
 169                 if (c == 0) {
 170                         if (hash->free_value)
 171                                 hash->free_value((void *)entry->value);
 172                         entry->key = key;
 173                         entry->value = value;
 174                         return 0;
 175                 } else if (c < 0) {
 176                         memmove(entry + 1, entry,
 177                                 (entry_end - entry) * sizeof(struct hash_entry));
 178                         break;
 179                 }
 180         }
 181
 182         entry->key = key;
 183         entry->value = value;
 184         bucket->used++;
 185         hash->count++;
 186         return 0;
 187 }
 188
 189 /* similar to hash_add(), but fails if key already exists */
 190 int hash_add_unique(struct hash *hash, const char *key, const void *value)
 191 {
 192         unsigned int keylen = strlen(key);
 193         unsigned int hashval = hash_superfast(key, keylen);
 194         unsigned int pos = hashval & (hash->n_buckets - 1);
 195         struct hash_bucket *bucket = hash->buckets + pos;
 196         struct hash_entry *entry, *entry_end;
 197
 198         if (bucket->used + 1 >= bucket->total) {
 199                 unsigned new_total = bucket->total + hash->step;
 200                 size_t size = new_total * sizeof(struct hash_entry);
 201                 struct hash_entry *tmp = realloc(bucket->entries, size);
 202                 if (tmp == NULL)
 203                         return -errno;
 204                 bucket->entries = tmp;
 205                 bucket->total = new_total;
 206         }
 207
 208         entry = bucket->entries;
 209         entry_end = entry + bucket->used;
 210         for (; entry < entry_end; entry++) {
 211                 int c = strcmp(key, entry->key);
 212                 if (c == 0)
 213                         return -EEXIST;
 214                 else if (c < 0) {
 215                         memmove(entry + 1, entry,
 216                                 (entry_end - entry) * sizeof(struct hash_entry));
 217                         break;
 218                 }
 219         }
 220
 221         entry->key = key;
 222         entry->value = value;
 223         bucket->used++;
 224         hash->count++;
 225         return 0;
 226 }
 227
 228 static int hash_entry_cmp(const void *pa, const void *pb)
 229 {
 230         const struct hash_entry *a = pa;
 231         const struct hash_entry *b = pb;
 232         return strcmp(a->key, b->key);
 233 }
 234
 235 void *hash_find(const struct hash *hash, const char *key)
 236 {
 237         unsigned int keylen = strlen(key);
 238         unsigned int hashval = hash_superfast(key, keylen);
 239         unsigned int pos = hashval & (hash->n_buckets - 1);
 240         const struct hash_bucket *bucket = hash->buckets + pos;
 241         const struct hash_entry se = {
 242                 .key = key,
 243                 .value = NULL
 244         };
 245         const struct hash_entry *entry = bsearch(
 246                 &se, bucket->entries, bucket->used,
 247                 sizeof(struct hash_entry), hash_entry_cmp);
 248         if (entry == NULL)
 249                 return NULL;
 250         return (void *)entry->value;
 251 }
 252
 253 int hash_del(struct hash *hash, const char *key)
 254 {
 255         unsigned int keylen = strlen(key);
 256         unsigned int hashval = hash_superfast(key, keylen);
 257         unsigned int pos = hashval & (hash->n_buckets - 1);
 258         unsigned int steps_used, steps_total;
 259         struct hash_bucket *bucket = hash->buckets + pos;
 260         struct hash_entry *entry, *entry_end;
 261         const struct hash_entry se = {
 262                 .key = key,
 263                 .value = NULL
 264         };
 265
 266         entry = bsearch(&se, bucket->entries, bucket->used,
 267                 sizeof(struct hash_entry), hash_entry_cmp);
 268         if (entry == NULL)
 269                 return -ENOENT;
 270
 271         if (hash->free_value)
 272                 hash->free_value((void *)entry->value);
 273
 274         entry_end = bucket->entries + bucket->used;
 275         memmove(entry, entry + 1,
 276                 (entry_end - entry) * sizeof(struct hash_entry));
 277
 278         bucket->used--;
 279         hash->count--;
 280
 281         steps_used = bucket->used / hash->step;
 282         steps_total = bucket->total / hash->step;
 283         if (steps_used + 1 < steps_total) {
 284                 size_t size = (steps_used + 1) *
 285                         hash->step * sizeof(struct hash_entry);
 286                 struct hash_entry *tmp = realloc(bucket->entries, size);
 287                 if (tmp) {
 288                         bucket->entries = tmp;
 289                         bucket->total = (steps_used + 1) * hash->step;
 290                 }
 291         }
 292
 293         return 0;
 294 }
 295
 296 unsigned int hash_get_count(const struct hash *hash)
 297 {
 298         return hash->count;
 299 }
 300
 301 void hash_iter_init(const struct hash *hash, struct hash_iter *iter)
 302 {
 303         iter->hash = hash;
 304         iter->bucket = 0;
 305         iter->entry = -1;
 306 }
 307
 308 bool hash_iter_next(struct hash_iter *iter, const char **key,
 309                                                         const void **value)
 310 {
 311         const struct hash_bucket *b = iter->hash->buckets + iter->bucket;
 312         const struct hash_entry *e;
 313
 314         iter->entry++;
 315
 316         if (iter->entry >= b->used) {
 317                 iter->entry = 0;
 318
 319                 for (iter->bucket++; iter->bucket < iter->hash->n_buckets;
 320                                                         iter->bucket++) {
 321                         b = iter->hash->buckets + iter->bucket;
 322
 323                         if (b->used > 0)
 324                                 break;
 325                 }
 326
 327                 if (iter->bucket >= iter->hash->n_buckets)
 328                         return false;
 329         }
 330
 331         e = b->entries + iter->entry;
 332
 333         if (value != NULL)
 334                 *value = e->value;
 335         if (key != NULL)
 336                 *key = e->key;
 337
 338         return true;
 339 }