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