/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* util/support/hash.c - hash table implementation */
/*
* Copyright (C) 2018 by the Massachusetts Institute of Technology.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
* OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "k5-platform.h"
#include "k5-hashtab.h"
#include "k5-queue.h"
struct entry {
const void *key;
size_t klen;
void *val;
K5_SLIST_ENTRY(entry) next;
};
struct k5_hashtab {
uint64_t k0;
uint64_t k1;
size_t nbuckets;
size_t nentries;
K5_SLIST_HEAD(bucket_list, entry) *buckets;
};
/* Return x rotated to the left by r bits. */
static inline uint64_t
rotl64(uint64_t x, int r)
{
return (x << r) | (x >> (64 - r));
}
static inline void
sipround(uint64_t *v0, uint64_t *v1, uint64_t *v2, uint64_t *v3)
{
*v0 += *v1;
*v2 += *v3;
*v1 = rotl64(*v1, 13) ^ *v0;
*v3 = rotl64(*v3, 16) ^ *v2;
*v0 = rotl64(*v0, 32);
*v2 += *v1;
*v0 += *v3;
*v1 = rotl64(*v1, 17) ^ *v2;
*v3 = rotl64(*v3, 21) ^ *v0;
*v2 = rotl64(*v2, 32);
}
/* SipHash-2-4 from https://131002.net/siphash/siphash.pdf (Jean-Philippe
* Aumasson and Daniel J. Bernstein) */
static uint64_t
siphash24(const uint8_t *data, size_t len, uint64_t k0, uint64_t k1)
{
uint64_t v0 = k0 ^ 0x736F6D6570736575;
uint64_t v1 = k1 ^ 0x646F72616E646F6D;
uint64_t v2 = k0 ^ 0x6C7967656E657261;
uint64_t v3 = k1 ^ 0x7465646279746573;
uint64_t mi;
const uint8_t *p, *end = data + (len - len % 8);
uint8_t last[8] = { 0 };
/* Process each full 8-byte chunk of data. */
for (p = data; p < end; p += 8) {
mi = load_64_le(p);
v3 ^= mi;
sipround(&v0, &v1, &v2, &v3);
sipround(&v0, &v1, &v2, &v3);
v0 ^= mi;
}
/* Process the last 0-7 bytes followed by the length mod 256. */
memcpy(last, end, len % 8);
last[7] = len & 0xFF;
mi = load_64_le(last);
v3 ^= mi;
sipround(&v0, &v1, &v2, &v3);
sipround(&v0, &v1, &v2, &v3);
v0 ^= mi;
/* Finalize. */
v2 ^= 0xFF;
sipround(&v0, &v1, &v2, &v3);
sipround(&v0, &v1, &v2, &v3);
sipround(&v0, &v1, &v2, &v3);
sipround(&v0, &v1, &v2, &v3);
return v0 ^ v1 ^ v2 ^ v3;
}
uint64_t
k5_siphash24(const uint8_t *data, size_t len,
const uint8_t seed[K5_HASH_SEED_LEN])
{
uint64_t k0 = load_64_le(seed), k1 = load_64_le(seed + 8);
return siphash24(data, len, k0, k1);
}
int
k5_hashtab_create(const uint8_t seed[K5_HASH_SEED_LEN], size_t initial_buckets,
struct k5_hashtab **ht_out)
{
struct k5_hashtab *ht;
*ht_out = NULL;
ht = malloc(sizeof(*ht));
if (ht == NULL)
return ENOMEM;
if (seed != NULL) {
ht->k0 = load_64_le(seed);
ht->k1 = load_64_le(seed + 8);
} else {
ht->k0 = ht->k1 = 0;
}
ht->nbuckets = (initial_buckets > 0) ? initial_buckets : 64;
ht->nentries = 0;
ht->buckets = calloc(ht->nbuckets, sizeof(*ht->buckets));
if (ht->buckets == NULL) {
free(ht);
return ENOMEM;
}
*ht_out = ht;
return 0;
}
void
k5_hashtab_free(struct k5_hashtab *ht)
{
size_t i;
struct entry *ent;
for (i = 0; i < ht->nbuckets; i++) {
while (!K5_SLIST_EMPTY(&ht->buckets[i])) {
ent = K5_SLIST_FIRST(&ht->buckets[i]);
K5_SLIST_REMOVE_HEAD(&ht->buckets[i], next);
free(ent);
}
}
free(ht->buckets);
free(ht);
}
static int
resize_table(struct k5_hashtab *ht)
{
size_t i, j, newsize = ht->nbuckets * 2;
struct bucket_list *newbuckets;
struct entry *ent;
newbuckets = calloc(newsize, sizeof(*newbuckets));
if (newbuckets == NULL)
return ENOMEM;
/* Rehash all the entries into the new buckets. */
for (i = 0; i < ht->nbuckets; i++) {
while (!K5_SLIST_EMPTY(&ht->buckets[i])) {
ent = K5_SLIST_FIRST(&ht->buckets[i]);
j = siphash24(ent->key, ent->klen, ht->k0, ht->k1) % newsize;
K5_SLIST_REMOVE_HEAD(&ht->buckets[i], next);
K5_SLIST_INSERT_HEAD(&newbuckets[j], ent, next);
}
}
free(ht->buckets);
ht->buckets = newbuckets;
ht->nbuckets = newsize;
return 0;
}
int
k5_hashtab_add(struct k5_hashtab *ht, const void *key, size_t klen, void *val)
{
size_t i;
struct entry *ent;
if (ht->nentries == ht->nbuckets) {
if (resize_table(ht) != 0)
return ENOMEM;
}
ent = malloc(sizeof(*ent));
if (ent == NULL)
return ENOMEM;
ent->key = key;
ent->klen = klen;
ent->val = val;
i = siphash24(key, klen, ht->k0, ht->k1) % ht->nbuckets;
K5_SLIST_INSERT_HEAD(&ht->buckets[i], ent, next);
ht->nentries++;
return 0;
}
int
k5_hashtab_remove(struct k5_hashtab *ht, const void *key, size_t klen)
{
size_t i;
struct entry *ent;
i = siphash24(key, klen, ht->k0, ht->k1) % ht->nbuckets;
K5_SLIST_FOREACH(ent, &ht->buckets[i], next) {
if (ent->klen == klen && memcmp(ent->key, key, klen) == 0) {
K5_SLIST_REMOVE(&ht->buckets[i], ent, entry, next);
free(ent);
ht->nentries--;
return 1;
}
}
return 0;
}
void *
k5_hashtab_get(struct k5_hashtab *ht, const void *key, size_t klen)
{
size_t i;
struct entry *ent;
i = siphash24(key, klen, ht->k0, ht->k1) % ht->nbuckets;
K5_SLIST_FOREACH(ent, &ht->buckets[i], next) {
if (ent->klen == klen && memcmp(ent->key, key, klen) == 0)
return ent->val;
}
return NULL;
}