A simple hash table inspired from Lua's ltable.c

hashtable.c

#include "hashtable.h"


#include <stdlib.h>
#include <string.h>


#define ht_isfree(node) ((node)->key == HT_NOKEY)

#define ht_keysize(ht, n)    (sizeof(HashKey)+ht->vsize)*(n)
#define ht_rawslot(ht, p, i) (HashKey*)((char*)(p) + ht_keysize(ht, i))
#define ht_slot(ht, i)  ht_rawslot(ht, (ht)->table, i)
#define ht_lastslot(ht) ht_slot(ht, (1<<(ht)->lsize)-1)

void ht_init(HashTable *ht, size_t objsize) {
    ht->vsize = objsize;
    ht->lsize = 0;
    ht->n     = 0;
    ht->lastfree = NULL;
    ht->table = NULL;
}

void ht_reset(HashTable *ht) {
    size_t i, size = (1<<ht->lsize);
    HashKey *slot = ht->table;
    for (i = 0; i < size; ++i) {
        slot->next = NULL;
        slot->key  = HT_NOKEY;
        slot = ht_rawslot(ht, slot, 1);
    }
    ht->n = 0;
    ht->lastfree = ht_lastslot(ht);
}

void ht_cleanup(HashTable *ht) {
    free(ht->table);
    ht_init(ht, ht->vsize);
}

int ht_resize(HashTable *ht, size_t newlsize) {
    size_t i, size = ht->lsize == 0 ? 0 : 1<<ht->lsize;
    HashKey *oldtable = ht->table;
    HashKey *newtable;
    if (1<<newlsize < ht->n)
        return 0;
    newtable = (HashKey*)malloc(ht_keysize(ht, 1<<newlsize));
    if (newtable == NULL)
        return 0;
    ht->table = newtable;
    ht->lsize = newlsize;
    ht_reset(ht);
    for (i = 0; i < size; ++i) {
        HashKey *oldkey = ht_rawslot(ht, oldtable, i);
        if (!ht_isfree(oldkey)) {
            void *p = ht_newkey(ht, oldkey->key);
            memcpy(p, oldkey+1, ht->vsize);
        }
    }
    free(oldtable);
    return 1;
}

static HashKey *mainposition(HashTable *ht, ht_Key key) {
    return ht_slot(ht, key&((1<<ht->lsize)-1));
}

static HashKey *findfree(HashTable *ht) {
    while (ht->table < ht->lastfree) {
        HashKey *prev = ht_rawslot(ht, ht->lastfree, -1);
        if (ht_isfree(ht->lastfree)) {
            HashKey *res = ht->lastfree;
            ht->lastfree = prev;
            return res;
        }
        ht->lastfree = prev;
    }
    return NULL;
}

void *ht_newkey(HashTable *ht, ht_Key key) {
    HashKey *mp = mainposition(ht, key);
    if (key == HT_NOKEY) return NULL;
    /* main position is taken? */
    if (!mp || !ht_isfree(mp)) {
        HashKey *n, *othern;
        n = findfree(ht); /* find a free node */
        if (n == NULL) { /* can not find one? rehash all */
            int res = 0;
            if (ht->n < (1<<ht->lsize)/2)
                res = ht_resize(ht, ht->lsize);
            else
                res = ht_resize(ht, ht->lsize+1);
            if (res == 0) /* resize failure? */
                return NULL;
            /* otherwise, retry */
            return ht_newkey(ht, key);
        }
        othern = mainposition(ht, mp->key);
        if (othern != mp) { /* is colliding node out of its main position? */
            /* yes; move colliding node into free position */
            while (othern->next != mp) othern = othern->next;
            othern->next = n;
            memcpy(n, mp, ht_keysize(ht, 1));
            mp->next = NULL;
        }
        else {  /* colliding node is in its own main position */
            /* new node will go into free position */
            n->next = mp->next;  /* chain new position */
            mp->next = n;
            mp = n;
        }
    }
    ++ht->n;
    mp->key = key;
    return mp + 1;
}

void *ht_get(HashTable *ht, ht_Key key) {
    if (key != HT_NOKEY) {
        HashKey *mp = mainposition(ht, key);
        while (mp) {
            if (mp->key == key)
                return mp + 1;
            mp = mp->next;
        }
    }
    return NULL;
}

void *ht_set(HashTable *ht, ht_Key key) {
    void *v = ht_get(ht, key);
    return v ? v : ht_newkey(ht, key);
}

void *ht_remove(HashTable *ht, ht_Key key) {
    if (key != HT_NOKEY) {
        HashKey *mp = mainposition(ht, key);
        while (mp) {
            if (mp->key == key) {
                mp->key = HT_NOKEY;
                return mp+1;
            }
            mp = mp->next;
        }
    }
    return NULL;
}

void *ht_iter(HashTable *ht, HashKey **pkey) {
    if (pkey == NULL) return NULL;
    if (*pkey == NULL)
        *pkey = ht->table;
    else {
        if (*pkey == ht_slot(ht, (1<<ht->lsize)-1))
            return NULL;
        *pkey = ht_rawslot(ht, *pkey, 1);
    }
    return *pkey == NULL ? NULL : *pkey + 1;
}

hashtable.h

#ifndef hashtable_h
#define hashtable_h

#include <stddef.h>

#define HT_NOKEY  ((ht_Key)(0))

typedef ptrdiff_t ht_Key;

typedef struct HashKey {
    struct HashKey *next;
    ht_Key key;
    /* hash value of this key */
} HashKey;

typedef struct HashTable {
    size_t vsize; /* value size */
    size_t lsize; /* log(size) */
    size_t n;     /* actually used slots */
    HashKey *lastfree;
    HashKey *table;
} HashTable;

void ht_init    (HashTable *ht, size_t objsize);
void ht_reset   (HashTable *ht);
void ht_cleanup (HashTable *ht);

int ht_resize (HashTable *ht, size_t newlsize);

void *ht_remove(HashTable *ht, ht_Key key);
void *ht_newkey(HashTable *ht, ht_Key key);
void *ht_get(HashTable *ht, ht_Key key);
void *ht_set(HashTable *ht, ht_Key key);

void *ht_iter(HashTable *ht, HashKey **pkey);


#endif /* hashtable_h */

test_hashtable.c

#include "hashtable.h"

#include <stdio.h>

int main(void)
{
    typedef int ht_Value;
    HashTable ht;
    ht_init(&ht, sizeof(ht_Value));
    *(ht_Value*)ht_newkey(&ht, 1) = 8;
    *(ht_Value*)ht_newkey(&ht, 2) = 7;
    *(ht_Value*)ht_newkey(&ht, 3) = 6;
    *(ht_Value*)ht_newkey(&ht, 4) = 5;
    *(ht_Value*)ht_newkey(&ht, 5) = 4;
    *(ht_Value*)ht_newkey(&ht, 6) = 3;
    *(ht_Value*)ht_newkey(&ht, 7) = 2;
    *(ht_Value*)ht_newkey(&ht, 8) = 1;
    size_t i;
    printf("print table: \n");
    for (i = 0; i < 10; ++i) {
        ht_Value *v = ht_get(&ht, i);
        if (v == NULL)
            printf("ht[%d] = nul\n", i);
        else
            printf("ht[%d] = %d\n", i, *v);
    }
    printf("remove ht[3]\n");
    ht_remove(&ht, 3);
    printf("print table: \n");
    for (i = 0; i < 10; ++i) {
        ht_Value *v = ht_get(&ht, i);
        if (v == NULL)
            printf("ht[%d] = nul\n", i);
        else
            printf("ht[%d] = %d\n", i, *v);
    }
    ht_cleanup(&ht);
    return 0;
}

/* cc: input+='hashtable.c' */