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