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 } 339
