/*
* Borrowed from libkmod - interface to kernel module operations
*
* Copyright (C) 2011-2013 ProFUSION embedded systems
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, see <http://www.gnu.org/licenses/>.
*/
#include <errno.h>
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>
#include "hash.h"
/* endianess and alignments */
/* taken from kmod shared/util.h */
/* ************************************************************************ */
#define get_unaligned(ptr) \
({ \
struct __attribute__((packed)) { \
typeof(*(ptr)) __v; \
} *__p = (typeof(__p)) (ptr); \
__p->__v; \
})
#define put_unaligned(val, ptr) \
do { \
struct __attribute__((packed)) { \
typeof(*(ptr)) __v; \
} *__p = (typeof(__p)) (ptr); \
__p->__v = (val); \
} while (0)
static inline unsigned int ALIGN_POWER2(unsigned int u)
{
return 1 << ((sizeof(u) * 8) - __builtin_clz(u - 1));
}
static inline size_t min(size_t a, size_t b)
{
return a < b ? a : b;
}
struct hash_entry {
const char *key;
size_t keylen;
const void *value;
};
struct hash_bucket {
struct hash_entry *entries;
unsigned int used;
unsigned int total;
};
struct hash {
unsigned int count;
unsigned int step;
unsigned int n_buckets;
void (*free_value)(void *value);
struct hash_bucket buckets[];
};
static inline int hash_key_cmp(const char *key1, size_t size1,
const char *key2, size_t size2)
{
int rc;
size_t size;
size = min(size1, size2);
rc = memcmp(key1, key2, size);
if (rc != 0)
return rc;
return (int)(size1 - size2);
}
struct hash *hash_new(unsigned int n_buckets,
void (*free_value)(void *value))
{
struct hash *hash;
n_buckets = ALIGN_POWER2(n_buckets);
hash = calloc(1, sizeof(struct hash) +
n_buckets * sizeof(struct hash_bucket));
if (hash == NULL)
return NULL;
hash->n_buckets = n_buckets;
hash->free_value = free_value;
hash->step = n_buckets / 32;
if (hash->step == 0)
hash->step = 4;
else if (hash->step > 64)
hash->step = 64;
return hash;
}
void hash_free(struct hash *hash)
{
struct hash_bucket *bucket, *bucket_end;
if (hash == NULL)
return;
bucket = hash->buckets;
bucket_end = bucket + hash->n_buckets;
for (; bucket < bucket_end; bucket++) {
if (hash->free_value) {
struct hash_entry *entry, *entry_end;
entry = bucket->entries;
entry_end = entry + bucket->used;
for (; entry < entry_end; entry++)
hash->free_value((void *)entry->value);
}
free(bucket->entries);
}
free(hash);
}
static inline unsigned int hash_superfast(const char *key, unsigned int len)
{
/* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html)
* used by WebCore (http://webkit.org/blog/8/hashtables-part-2/)
* EFL's eina and possible others.
*/
unsigned int tmp, hash = len, rem = len & 3;
len /= 4;
/* Main loop */
for (; len > 0; len--) {
hash += get_unaligned((uint16_t *) key);
tmp = (get_unaligned((uint16_t *)(key + 2)) << 11) ^ hash;
hash = (hash << 16) ^ tmp;
key += 4;
hash += hash >> 11;
}
/* Handle end cases */
switch (rem) {
case 3:
hash += get_unaligned((uint16_t *) key);
hash ^= hash << 16;
hash ^= key[2] << 18;
hash += hash >> 11;
break;
case 2:
hash += get_unaligned((uint16_t *) key);
hash ^= hash << 11;
hash += hash >> 17;
break;
case 1:
hash += *key;
hash ^= hash << 10;
hash += hash >> 1;
}
/* Force "avalanching" of final 127 bits */
hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 4;
hash += hash >> 17;
hash ^= hash << 25;
hash += hash >> 6;
return hash;
}
/*
* add or replace key in hash map.
*
* none of key or value are copied, just references are remembered as is,
* make sure they are live while pair exists in hash!
*/
int hash_add_bin(struct hash *hash,
const char *key, size_t keylen, const void *value)
{
unsigned int hashval = hash_superfast(key, keylen);
unsigned int pos = hashval & (hash->n_buckets - 1);
struct hash_bucket *bucket = hash->buckets + pos;
struct hash_entry *entry, *entry_end;
if (bucket->used + 1 >= bucket->total) {
unsigned new_total = bucket->total + hash->step;
size_t size = new_total * sizeof(struct hash_entry);
struct hash_entry *tmp = realloc(bucket->entries, size);
if (tmp == NULL)
return -errno;
bucket->entries = tmp;
bucket->total = new_total;
}
entry = bucket->entries;
entry_end = entry + bucket->used;
for (; entry < entry_end; entry++) {
int c = hash_key_cmp(key, keylen, entry->key, entry->keylen);
if (c == 0) {
if (hash->free_value)
hash->free_value((void *)entry->value);
entry->key = key;
entry->keylen = keylen;
entry->value = value;
return 0;
} else if (c < 0) {
memmove(entry + 1, entry,
(entry_end - entry) * sizeof(struct hash_entry));
break;
}
}
entry->key = key;
entry->keylen = keylen;
entry->value = value;
bucket->used++;
hash->count++;
return 0;
}
/* similar to hash_add(), but fails if key already exists */
int hash_add_unique_bin(struct hash *hash,
const char *key, size_t keylen, const void *value)
{
unsigned int hashval = hash_superfast(key, keylen);
unsigned int pos = hashval & (hash->n_buckets - 1);
struct hash_bucket *bucket = hash->buckets + pos;
struct hash_entry *entry, *entry_end;
if (bucket->used + 1 >= bucket->total) {
unsigned new_total = bucket->total + hash->step;
size_t size = new_total * sizeof(struct hash_entry);
struct hash_entry *tmp = realloc(bucket->entries, size);
if (tmp == NULL)
return -errno;
bucket->entries = tmp;
bucket->total = new_total;
}
entry = bucket->entries;
entry_end = entry + bucket->used;
for (; entry < entry_end; entry++) {
int c = hash_key_cmp(key, keylen, entry->key, entry->keylen);
if (c == 0)
return -EEXIST;
else if (c < 0) {
memmove(entry + 1, entry,
(entry_end - entry) * sizeof(struct hash_entry));
break;
}
}
entry->key = key;
entry->keylen = keylen;
entry->value = value;
bucket->used++;
hash->count++;
return 0;
}
static int hash_entry_cmp(const void *pa, const void *pb)
{
const struct hash_entry *a = pa;
const struct hash_entry *b = pb;
return hash_key_cmp(a->key, a->keylen, b->key, b->keylen);
}
void *hash_find_bin(const struct hash *hash, const char *key, size_t keylen)
{
unsigned int hashval = hash_superfast(key, keylen);
unsigned int pos = hashval & (hash->n_buckets - 1);
const struct hash_bucket *bucket = hash->buckets + pos;
const struct hash_entry se = {
.key = key,
.keylen = keylen,
.value = NULL
};
const struct hash_entry *entry = bsearch(
&se, bucket->entries, bucket->used,
sizeof(struct hash_entry), hash_entry_cmp);
if (entry == NULL)
return NULL;
return (void *)entry->value;
}
int hash_del_bin(struct hash *hash, const char *key, size_t keylen)
{
unsigned int hashval = hash_superfast(key, keylen);
unsigned int pos = hashval & (hash->n_buckets - 1);
unsigned int steps_used, steps_total;
struct hash_bucket *bucket = hash->buckets + pos;
struct hash_entry *entry, *entry_end;
const struct hash_entry se = {
.key = key,
.keylen = keylen,
.value = NULL
};
entry = bsearch(&se, bucket->entries, bucket->used,
sizeof(struct hash_entry), hash_entry_cmp);
if (entry == NULL)
return -ENOENT;
if (hash->free_value)
hash->free_value((void *)entry->value);
entry_end = bucket->entries + bucket->used;
memmove(entry, entry + 1,
(entry_end - entry) * sizeof(struct hash_entry));
bucket->used--;
hash->count--;
steps_used = bucket->used / hash->step;
steps_total = bucket->total / hash->step;
if (steps_used + 1 < steps_total) {
size_t size = (steps_used + 1) *
hash->step * sizeof(struct hash_entry);
struct hash_entry *tmp = realloc(bucket->entries, size);
if (tmp) {
bucket->entries = tmp;
bucket->total = (steps_used + 1) * hash->step;
}
}
return 0;
}
unsigned int hash_get_count(const struct hash *hash)
{
return hash->count;
}
void hash_iter_init(const struct hash *hash, struct hash_iter *iter)
{
iter->hash = hash;
iter->bucket = 0;
iter->entry = -1;
}
bool hash_iter_next_bin(struct hash_iter *iter, const char **key,
size_t *keylen,
const void **value)
{
const struct hash_bucket *b = iter->hash->buckets + iter->bucket;
const struct hash_entry *e;
iter->entry++;
if (iter->entry >= b->used) {
iter->entry = 0;
for (iter->bucket++; iter->bucket < iter->hash->n_buckets;
iter->bucket++) {
b = iter->hash->buckets + iter->bucket;
if (b->used > 0)
break;
}
if (iter->bucket >= iter->hash->n_buckets)
return false;
}
e = b->entries + iter->entry;
if (value != NULL)
*value = e->value;
if (key != NULL)
*key = e->key;
if (keylen != NULL)
*keylen = e->keylen;
return true;
}