hashtab.c

/* -*- 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;
}