toys/simple-http-server-c/source/hashtable.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
#include <time.h>

#include "hashtable.h"

#include "xxhash.h"

#if defined(__x86_64__) || defined(_WIN64)
#define XXHASH(a, b, c) XXH64(a, b, c)
#define XXHHashType XXH64_hash_t
#else
#define XXHASH(a, b, c) XXH32(a, b, c)
#define XXHHashType XXH32_hash_t
#endif

#define MAX_NUMS 0x80000000U
#if !defined(UINT32_MAX)
#define UINT32_MAX 0xffffffffU
#endif /* !UINT32_MAX */

#define MAX_LOAD_FACTOR (1.0f)
#define DEFAULT_CAPACITY (8)
#define INDEX(hash, cap) ((uint32_t)((hash) & ((cap) - 1)))

static int DefaultKeyCompare(const void *k1, uint32_t kl1, const void *k2, uint32_t kl2)
{
    return ((kl1 == kl2) && !memcmp(k1, k2, kl1));
}

static uint32_t RoundUp(uint32_t n)
{
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return ++n;
}

static void* HashTable_Duplicate(const void* src, size_t len)
{
    void* data = malloc(len);

    if (!data)
    {
        return NULL;
    }

    memcpy(data, src, len);
    return data;
}

#define HashTable_Calloc(len) calloc(len, 1)

static HashTableElement* HashTableElement_Alloc(HashTable *o, const void *key, uint32_t kl, void *val, uint32_t vl)
{
    HashTableElement* element = (HashTableElement *)HashTable_Calloc(sizeof(HashTableElement));
    element->key = HashTable_Duplicate(key, kl);
    if (o->table_mode == kCopyMode)
    {
        element->val = HashTable_Duplicate(val, vl);
    }
    else
    {
        element->val = val;
    }

    element->vl = vl;
    element->kl = kl;
    element->next = NULL;

    return element;
}

static void HashTableElement_Free(HashTableElement *o, TableMode tmode)
{
    if (tmode == kCopyMode)
    {
        free(o->val);
    }

    free(o->key);
    free(o);
}

static void DataStore_Delete(TableMode tmode, HashTableElement **data_store, uint32_t capacity)
{
    for (uint32_t i = 0; i < capacity; ++i)
    {
        while (data_store[i])
        {
            HashTableElement *temp = data_store[i];
            data_store[i] = data_store[i]->next;
            HashTableElement_Free(temp, tmode);
        }
    }
}

HashTable* HashTable_New(uint32_t n, TableMode mode)
{
    HashTable *o = (HashTable *)HashTable_Calloc(sizeof(HashTable));

    if (n >= MAX_NUMS)
    {
        o->tables[0].tc = MAX_NUMS;
    }
    else if(n <= DEFAULT_CAPACITY)
    {
        o->tables[0].tc = DEFAULT_CAPACITY;
    }
    else
    {
        o->tables[0].tc = RoundUp(n);
    }

    o->max = (uint32_t)((double)nh->tbs[0].tc * MAX_LOAD_FACTOR);
    o->min = o->max >> 3;
    o->tables[0].ds = (HashTableElement **)HashTable_Calloc(o->tables[0].tc * sizeof(void*));
    o->tables[1].ds = NULL;
    o->tables[1].tc = 0;
    o->kc = DefaultKeyCompare;
    o->rehashidx = 0;
    o->used = 0;
    o->mode = tmode;
    o->seed = (uint32_t)time(0);

    return o;
}

void HashTable_Delete(HashTable *o)
{
    DataStore_Delete(o->table_mode, &o->tables[0].ds[o->rehashidx], o->tables[0].tc - o->rehashidx);

    if (o->tables[1].ds)
    {
        DataStore_Delete(o->table_mode, o->tables[1].ds, o->tables[1].tc);
    }

    free(o);
}

static void MoveElements(HashTable *o, uint32_t count)
{
    HashTableElement *ftemp;
    while (o->rehashidx < o->tbs[0].tc)
    {
        if (!(ftemp = o->tables[0].ds[o->rehashidx]))
        {
            o->rehashidx++;
            continue;
        }

        uint32_t rehash_key = INDEX(XXHASH(ftemp->key, ftemp->kl, o->seed), o->tables[1].tc);
        HashTableElement *stemp = o->tables[1].ds[rehash_key];

        o->tables[1].ds[rehash_key] = o->tables[0].ds[o->rehashidx];
        o->tables[0].ds[o->rehashidx] = ftemp->next;
        o->tables[1].ds[rehash_key]->next = stemp;

        if (--count == 0) return;
    }

    free(o->tables[0].ds);
    o->tables[0].ds = o->tables[1].ds;
    o->tables[0].tc = o->tables[1].tc;
    o->tables[1].tc = 0;
    o->max = (uint32_t)((double)o->tables[0].tc * MAX_LOAD_FACTOR);
    o->min = o->max >> 3;
    o->tbs[1].ds = NULL;
    o->rehashidx = 0;
}

static void GetTables(HashTable* o, const void* key, uint32_t kl, HashTableElement** ht, uint32_t* h)
{
    if (table->tbs[1].ds)
    {
        MoveElements(table, 2);
    }

    XXHHashType hash = XXHASH(key, kl, o->seed);
    h[0] = INDEX(hash, o->tables[0].tc);
    ht[0] = o->tables[0].ds[h[0]];

    if (o->tables[1].ds)
    {
        h[1] = INDEX(hash, o->tables[1].tc);
        ht[1] = o->tables[1].ds[h[1]];
    }
}

void* HashTable_Lookup(HashTable *o, const void *key, uint32_t kl)
{
    HashTableElement* temp[2] = { 0 };
    uint32_t hash_key[2] = { 0 };

    GetTables(o, key, kl, temp, hash_key);

    for (int i = 0; i < 2; ++i)
    {
        while (temp[i])
        {
            if (o->kc(temp[i]->key, temp[i]->kl, key, kl))
            {
                return temp[i]->val;
            }
            temp[i] = temp[i]->next;
        }
    }

    return NULL;
}

static void HashTable_Expand(Table* o, uint32_t new_size)
{
    o->ds = (HashTableElement **)HashTable_Calloc(new_size * sizeof(void*));
    o->tc = new_size;
}

static void ExpandIfNeeded(HashTable* o)
{
    if (!o->tables[1].ds && o->used > o->max && o->tables[0].tc != MAX_NUMS)
    {
        HashTable_Expand(&o->tables[1], o->tables[0].tc * 2);
    }
}

static void ReplaceElement(void** val, void* new_val, size_t len, TableMode mode)
{
    if (mode == kCopyMode)
    {
        free(*val);
        *val = HashTable_Duplicate(new_val, len);
    }
    else *val = new_val;
}

int HashTable_Set(Table *table, const void *key, uint32_t kl, void *val, uint32_t vl, SetMode smode)
{
    ExpandIfNeeded(table);
    ht_elem_t *prev = NULL, *temp[2] = { 0 };
    uint32_t hash_key[2] = { 0 };

    GetTables(table, key, kl, temp, hash_key);
    for (int i = 0; i < 2; ++i)
    {
        while (temp[i])
        {
            if (table->kc(temp[i]->key, temp[i]->kl, key, kl))
            {
                if (smode == MODE_2) return -1;
                ReplaceElement(&temp[i]->val, val, vl, table->mode);
                return 1;
            }
            prev = temp[i];
            temp[i] = temp[i]->next;
        }
    }

    table->used++;
    HashTableElement *element = Element_New(table, key, kl, val, vl);
    if (prev) {
        prev->next = element;
        return 0;
    }
    if (table->tbs[1].ds) table->tbs[1].ds[hash_key[1]] = element;
    else table->tbs[0].ds[hash_key[0]] = element;
    return 0;
}

static void _resize_if_needed(ht_t *table)
{
    if (!table->tbs[1].ds && table->used < table->ht_min && table->tbs[0].tc != DEFAULT_CAPACITY) {
        hash_table_expand(&table->tbs[1], table->tbs[0].tc / 2);
    }
}

int hash_table_remove(ht_t *table, const void *key, uint32_t kl)
{
    ht_elem_t *temp[2] = { 0 };
    uint32_t hash_key[2] = { 0 };
    get_tables(table, key, kl, temp, hash_key);
    for (int i = 0; i < 2; ++i) {
        if (!temp[i]) continue;
        ht_elem_t *prev = NULL, **ptemp = &table->tbs[i].ds[hash_key[i]];
        while (temp[i]) {
            if (table->kc(temp[i]->key, temp[i]->kl, key, kl)) {
                if (!prev) *ptemp = temp[i]->next;
                else prev->next = temp[i]->next;
                element_delete(table->mode, temp[i]);
                table->used--;
                _resize_if_needed(table);
                return 0;
            }
            prev = temp[i];
            temp[i] = temp[i]->next;
        }
    }
    return -1;
}

ht_elem_t* hash_table_elements(ht_t *table, tmode_t mode)
{
    if (table->used == 0) return NULL;
    /*<2A><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>*/
    ht_elem_t head = { 0 }, * ptmp = &head;
    for (uint32_t i = 0; i < 2; i++) {
        ht_elem_t **ds = table->tbs[i].ds;
        if (!ds) continue;
        for (uint32_t j = 0; j < table->tbs[i].tc; ++j) {
            ht_elem_t* p = ds[j];
            while (p) {
                ptmp->next = ht_dup(p, sizeof(ht_elem_t));
                ptmp->next->key = ht_dup(p->key, p->kl);
                if (mode == COPY_MODE) ptmp->next->val = ht_dup(p->val, p->vl);
                ptmp = ptmp->next;
                p = p->next;
            }
        }
    }
    return head.next;
}

void hash_table_remove_elements(ht_elem_t* elems, tmode_t tmode)
{
    ht_elem_t* p = elems;
    while (p)
    {
        free(p->key);
        if (tmode == COPY_MODE) free(p->val);
        p = p->next;
    }
    free(elems);
}

void hash_table_rehash(ht_t* table, uint32_t seed)
{
    if (table->used == 0) return;

    if (!table->tbs[1].ds) {
        table->seed = seed;
        hash_table_expand(&table->tbs[1], table->tbs[0].tc);
        move_elements(table, UINT32_MAX);
    }
    else
    {
        move_elements(table, UINT32_MAX);
        hash_table_rehash(table, seed);
    }
}

void hash_table_set_compare_func(ht_t* table, int (*kc_func)(const void*, uint32_t, const void*, uint32_t))
{
    table->kc = kc_func;
}