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