Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 1 | /* |
| 2 | * libkmod - interface to kernel module operations |
| 3 | * |
Lucas De Marchi | e6b0e49 | 2013-01-16 11:27:21 -0200 | [diff] [blame] | 4 | * Copyright (C) 2011-2013 ProFUSION embedded systems |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 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 |
Lucas De Marchi | cb451f3 | 2011-12-12 18:24:35 -0200 | [diff] [blame] | 8 | * License as published by the Free Software Foundation; either |
| 9 | * version 2.1 of the License, or (at your option) any later version. |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 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 |
Lucas De Marchi | dea2dfe | 2014-12-25 23:32:03 -0200 | [diff] [blame] | 17 | * License along with this library; if not, see <http://www.gnu.org/licenses/>. |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 18 | */ |
| 19 | |
Lucas De Marchi | c2e4286 | 2014-10-03 01:41:42 -0300 | [diff] [blame] | 20 | #include <errno.h> |
Lucas De Marchi | 0db718e | 2014-10-03 00:29:18 -0300 | [diff] [blame] | 21 | #include <inttypes.h> |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 22 | #include <stdlib.h> |
| 23 | #include <string.h> |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 24 | |
Lucas De Marchi | 0db718e | 2014-10-03 00:29:18 -0300 | [diff] [blame] | 25 | #include <shared/hash.h> |
| 26 | #include <shared/util.h> |
| 27 | |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 28 | struct hash_entry { |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 29 | const char *key; |
| 30 | const void *value; |
| 31 | }; |
| 32 | |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 33 | struct hash_bucket { |
| 34 | struct hash_entry *entries; |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 35 | unsigned int used; |
| 36 | unsigned int total; |
| 37 | }; |
| 38 | |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 39 | struct hash { |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 40 | unsigned int count; |
| 41 | unsigned int step; |
| 42 | unsigned int n_buckets; |
| 43 | void (*free_value)(void *value); |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 44 | struct hash_bucket buckets[]; |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 45 | }; |
| 46 | |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 47 | struct hash *hash_new(unsigned int n_buckets, |
Lucas De Marchi | c35347f | 2011-12-12 10:48:02 -0200 | [diff] [blame] | 48 | void (*free_value)(void *value)) |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 49 | { |
Lucas De Marchi | 82fc7d9 | 2013-08-22 01:36:45 -0300 | [diff] [blame] | 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)); |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 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 | |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 67 | void hash_free(struct hash *hash) |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 68 | { |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 69 | struct hash_bucket *bucket, *bucket_end; |
Dave Reisner | 4f17bb0 | 2012-01-04 19:05:04 -0500 | [diff] [blame] | 70 | |
| 71 | if (hash == NULL) |
| 72 | return; |
| 73 | |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 74 | bucket = hash->buckets; |
| 75 | bucket_end = bucket + hash->n_buckets; |
| 76 | for (; bucket < bucket_end; bucket++) { |
| 77 | if (hash->free_value) { |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 78 | struct hash_entry *entry, *entry_end; |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 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; |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 96 | |
| 97 | len /= 4; |
| 98 | |
| 99 | /* Main loop */ |
| 100 | for (; len > 0; len--) { |
Lucas De Marchi | af9080d | 2012-05-21 20:43:39 -0300 | [diff] [blame] | 101 | hash += get_unaligned((uint16_t *) key); |
| 102 | tmp = (get_unaligned((uint16_t *)(key + 2)) << 11) ^ hash; |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 103 | hash = (hash << 16) ^ tmp; |
Ambroz Bizjak | a2c7d3e | 2012-02-03 18:15:01 -0200 | [diff] [blame] | 104 | key += 4; |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 105 | hash += hash >> 11; |
| 106 | } |
| 107 | |
| 108 | /* Handle end cases */ |
| 109 | switch (rem) { |
| 110 | case 3: |
Lucas De Marchi | af9080d | 2012-05-21 20:43:39 -0300 | [diff] [blame] | 111 | hash += get_unaligned((uint16_t *) key); |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 112 | hash ^= hash << 16; |
| 113 | hash ^= key[2] << 18; |
| 114 | hash += hash >> 11; |
| 115 | break; |
| 116 | |
| 117 | case 2: |
Lucas De Marchi | af9080d | 2012-05-21 20:43:39 -0300 | [diff] [blame] | 118 | hash += get_unaligned((uint16_t *) key); |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 119 | hash ^= hash << 11; |
| 120 | hash += hash >> 17; |
| 121 | break; |
| 122 | |
| 123 | case 1: |
Ambroz Bizjak | a2c7d3e | 2012-02-03 18:15:01 -0200 | [diff] [blame] | 124 | hash += *key; |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 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 | */ |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 146 | int hash_add(struct hash *hash, const char *key, const void *value) |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 147 | { |
| 148 | unsigned int keylen = strlen(key); |
| 149 | unsigned int hashval = hash_superfast(key, keylen); |
Lucas De Marchi | 82fc7d9 | 2013-08-22 01:36:45 -0300 | [diff] [blame] | 150 | unsigned int pos = hashval & (hash->n_buckets - 1); |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 151 | struct hash_bucket *bucket = hash->buckets + pos; |
| 152 | struct hash_entry *entry, *entry_end; |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 153 | |
| 154 | if (bucket->used + 1 >= bucket->total) { |
| 155 | unsigned new_total = bucket->total + hash->step; |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 156 | size_t size = new_total * sizeof(struct hash_entry); |
| 157 | struct hash_entry *tmp = realloc(bucket->entries, size); |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 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) { |
Leandro Pereira | 1faec2c | 2012-10-12 12:28:56 -0300 | [diff] [blame] | 169 | if (hash->free_value) |
| 170 | hash->free_value((void *)entry->value); |
Lukas Anzinger | 86e19e9 | 2014-05-18 18:40:19 +0200 | [diff] [blame] | 171 | entry->key = key; |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 172 | entry->value = value; |
| 173 | return 0; |
| 174 | } else if (c < 0) { |
| 175 | memmove(entry + 1, entry, |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 176 | (entry_end - entry) * sizeof(struct hash_entry)); |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 177 | break; |
| 178 | } |
| 179 | } |
| 180 | |
| 181 | entry->key = key; |
| 182 | entry->value = value; |
| 183 | bucket->used++; |
| 184 | hash->count++; |
| 185 | return 0; |
| 186 | } |
| 187 | |
Lucas De Marchi | d707380 | 2011-12-27 12:20:35 -0200 | [diff] [blame] | 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); |
Lucas De Marchi | 82fc7d9 | 2013-08-22 01:36:45 -0300 | [diff] [blame] | 193 | unsigned int pos = hashval & (hash->n_buckets - 1); |
Lucas De Marchi | d707380 | 2011-12-27 12:20:35 -0200 | [diff] [blame] | 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 | |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 227 | static int hash_entry_cmp(const void *pa, const void *pb) |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 228 | { |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 229 | const struct hash_entry *a = pa; |
| 230 | const struct hash_entry *b = pb; |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 231 | return strcmp(a->key, b->key); |
| 232 | } |
| 233 | |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 234 | void *hash_find(const struct hash *hash, const char *key) |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 235 | { |
| 236 | unsigned int keylen = strlen(key); |
| 237 | unsigned int hashval = hash_superfast(key, keylen); |
Lucas De Marchi | 82fc7d9 | 2013-08-22 01:36:45 -0300 | [diff] [blame] | 238 | unsigned int pos = hashval & (hash->n_buckets - 1); |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 239 | const struct hash_bucket *bucket = hash->buckets + pos; |
| 240 | const struct hash_entry se = { |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 241 | .key = key, |
| 242 | .value = NULL |
| 243 | }; |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 244 | const struct hash_entry *entry = bsearch( |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 245 | &se, bucket->entries, bucket->used, |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 246 | sizeof(struct hash_entry), hash_entry_cmp); |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 247 | if (entry == NULL) |
| 248 | return NULL; |
| 249 | return (void *)entry->value; |
| 250 | } |
| 251 | |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 252 | int hash_del(struct hash *hash, const char *key) |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 253 | { |
| 254 | unsigned int keylen = strlen(key); |
| 255 | unsigned int hashval = hash_superfast(key, keylen); |
Lucas De Marchi | 82fc7d9 | 2013-08-22 01:36:45 -0300 | [diff] [blame] | 256 | unsigned int pos = hashval & (hash->n_buckets - 1); |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 257 | unsigned int steps_used, steps_total; |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 258 | struct hash_bucket *bucket = hash->buckets + pos; |
| 259 | struct hash_entry *entry, *entry_end; |
| 260 | const struct hash_entry se = { |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 261 | .key = key, |
| 262 | .value = NULL |
| 263 | }; |
| 264 | |
| 265 | entry = bsearch(&se, bucket->entries, bucket->used, |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 266 | sizeof(struct hash_entry), hash_entry_cmp); |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 267 | if (entry == NULL) |
| 268 | return -ENOENT; |
| 269 | |
Leandro Pereira | 1faec2c | 2012-10-12 12:28:56 -0300 | [diff] [blame] | 270 | if (hash->free_value) |
| 271 | hash->free_value((void *)entry->value); |
| 272 | |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 273 | entry_end = bucket->entries + bucket->used; |
| 274 | memmove(entry, entry + 1, |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 275 | (entry_end - entry) * sizeof(struct hash_entry)); |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 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) * |
Lucas De Marchi | 822913d | 2011-12-27 12:13:54 -0200 | [diff] [blame] | 284 | hash->step * sizeof(struct hash_entry); |
| 285 | struct hash_entry *tmp = realloc(bucket->entries, size); |
Gustavo Sverzut Barbieri | 7db0865 | 2011-12-05 00:17:37 -0200 | [diff] [blame] | 286 | if (tmp) { |
| 287 | bucket->entries = tmp; |
| 288 | bucket->total = (steps_used + 1) * hash->step; |
| 289 | } |
| 290 | } |
| 291 | |
| 292 | return 0; |
| 293 | } |
Lucas De Marchi | d707380 | 2011-12-27 12:20:35 -0200 | [diff] [blame] | 294 | |
| 295 | unsigned int hash_get_count(const struct hash *hash) |
| 296 | { |
| 297 | return hash->count; |
| 298 | } |
Lucas De Marchi | 8d1278d | 2011-12-27 13:27:01 -0200 | [diff] [blame] | 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 | } |