oa_hash.h

Go to the documentation of this file.

#ifndef OA_HASH_H
#define OA_HASH_H
 
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */
 
#ifdef OA_HASH_STATIC
#define OA_HASH_API static
#else
#define OA_HASH_API extern
#endif /* OA_HASH_STATIC */
 
#include <stddef.h>
 
enum oa_hash_entry_state {
    OA_HASH_ENTRY_EMPTY = 0, 
    OA_HASH_ENTRY_OCCUPIED, 
    OA_HASH_ENTRY_DELETED 
};
 
struct oa_hash_entry {
    enum oa_hash_entry_state state; 
    struct {
        const char *buf; 
        size_t length; 
    } key;
    void *value; 
};
 
#define __OA_HASH_ATTRS_const                                                 \
    const size_t length;                             \
    const size_t capacity;                      \
    const struct oa_hash_entry *buckets 
#define __OA_HASH_ATTRS_mut                                                   \
    size_t length;                                   \
    size_t capacity;                            \
    struct oa_hash_entry *buckets 
#define OA_HASH_ATTRS(_qualifier) __OA_HASH_ATTRS_##_qualifier
 
struct oa_hash {
    OA_HASH_ATTRS(mut);
};
 
OA_HASH_API void oa_hash_init(struct oa_hash *ht,
                              struct oa_hash_entry buckets[],
                              const size_t capacity);
 
OA_HASH_API void oa_hash_cleanup(struct oa_hash *ht);
 
OA_HASH_API const struct oa_hash_entry *oa_hash_get_entry(
    const struct oa_hash *ht, const char key[], const size_t len);
 
OA_HASH_API void *oa_hash_get(const struct oa_hash *ht,
                              const char key[],
                              const size_t len);
 
OA_HASH_API const struct oa_hash_entry *oa_hash_set_entry(struct oa_hash *ht,
                                                          const char key[],
                                                          const size_t len,
                                                          void *value);
 
OA_HASH_API void *oa_hash_set(struct oa_hash *ht,
                              const char key[],
                              const size_t len,
                              void *value);
 
OA_HASH_API int oa_hash_remove(struct oa_hash *ht,
                               const char key[],
                               const size_t len);
 
OA_HASH_API struct oa_hash_entry *oa_hash_rehash(
    struct oa_hash *ht,
    struct oa_hash_entry new_buckets[],
    const size_t new_capacity);
 
#ifndef OA_HASH_HEADER
 
#include <string.h>
#include <stdint.h>
 
OA_HASH_API void
oa_hash_init(struct oa_hash *ht,
             struct oa_hash_entry buckets[],
             const size_t capacity)
{
    memset(buckets, 0, sizeof(struct oa_hash_entry) * capacity);
    ht->buckets = buckets;
    ht->length = 0;
    ht->capacity = capacity;
}
 
OA_HASH_API void
oa_hash_cleanup(struct oa_hash *ht)
{
    if (!ht) return;
 
    ht->length = 0;
    ht->capacity = 0;
    ht->buckets = NULL;
}
 
static size_t
_oa_hash_genhash(const char key[], size_t len, const size_t capacity)
{
    const unsigned char *str = (const unsigned char *)key;
    unsigned long hash = 5381; /* DJB2 initial value */
 
    if (!key || !capacity) return 0;
 
    while (len--) {
        hash = ((hash & 0x7fffffff) << 5) + hash + *str++;
    }
    return hash % capacity;
}
 
OA_HASH_API const struct oa_hash_entry *
oa_hash_get_entry(const struct oa_hash *ht, const char key[], const size_t len)
{
    const size_t start_slot = _oa_hash_genhash(key, len, ht->capacity);
    size_t slot = start_slot;
 
    if (!len || !ht->capacity) return NULL;
 
    do {
        struct oa_hash_entry *entry = &ht->buckets[slot];
 
        if (entry->state == OA_HASH_ENTRY_EMPTY) {
            return NULL;
        }
 
        if (entry->state == OA_HASH_ENTRY_OCCUPIED && len == entry->key.length
            && 0 == memcmp(entry->key.buf, key, len))
        {
            return entry;
        }
 
        slot = (slot + 1) % ht->capacity;
    } while (slot != start_slot);
 
    return NULL;
}
 
OA_HASH_API void *
oa_hash_get(const struct oa_hash *ht, const char key[], const size_t len)
{
    const struct oa_hash_entry *entry = oa_hash_get_entry(ht, key, len);
    return entry ? entry->value : NULL;
}
 
OA_HASH_API const struct oa_hash_entry *
oa_hash_set_entry(struct oa_hash *ht,
                  const char key[],
                  const size_t len,
                  void *value)
{
    const size_t start_slot = _oa_hash_genhash(key, len, ht->capacity);
    size_t slot = start_slot;
    size_t first_deleted = SIZE_MAX;
 
    if (!len || !ht->capacity) return NULL;
 
    do {
        struct oa_hash_entry *entry = &ht->buckets[slot];
 
        if (entry->state != OA_HASH_ENTRY_OCCUPIED) {
            if (first_deleted == SIZE_MAX
                && entry->state == OA_HASH_ENTRY_DELETED)
            {
                first_deleted = slot;
            }
            if (entry->state == OA_HASH_ENTRY_EMPTY) {
                slot = (first_deleted != SIZE_MAX) ? first_deleted : slot;
                entry = &ht->buckets[slot];
                entry->key.buf = (char *)key;
                entry->key.length = len;
                entry->value = value;
                entry->state = OA_HASH_ENTRY_OCCUPIED;
                ht->length++;
                return entry;
            }
        }
 
        if (entry->state == OA_HASH_ENTRY_OCCUPIED && len == entry->key.length
            && 0 == memcmp(entry->key.buf, key, len))
        {
            entry->value = value;
            return entry;
        }
 
        slot = (slot + 1) % ht->capacity;
    } while (slot != start_slot);
 
    return NULL;
}
 
OA_HASH_API void *
oa_hash_set(struct oa_hash *ht,
            const char key[],
            const size_t len,
            void *value)
{
    const struct oa_hash_entry *entry = oa_hash_set_entry(ht, key, len, value);
    return entry ? entry->value : NULL;
}
 
OA_HASH_API int
oa_hash_remove(struct oa_hash *ht, const char key[], const size_t len)
{
    const size_t start_slot = _oa_hash_genhash(key, len, ht->capacity);
    size_t slot = start_slot;
 
    if (!len || !ht->capacity) return 0;
 
    do {
        struct oa_hash_entry *entry = &ht->buckets[slot];
 
        if (entry->state == OA_HASH_ENTRY_EMPTY) {
            return 0;
        }
 
        if (entry->state == OA_HASH_ENTRY_OCCUPIED && len == entry->key.length
            && 0 == memcmp(entry->key.buf, key, len))
        {
            entry->state = OA_HASH_ENTRY_DELETED;
            ht->length--;
            return 1;
        }
 
        slot = (slot + 1) % ht->capacity;
    } while (slot != start_slot);
 
    return 0;
}
 
OA_HASH_API struct oa_hash_entry *
oa_hash_rehash(struct oa_hash *ht,
               struct oa_hash_entry new_buckets[],
               const size_t new_capacity)
{
    struct oa_hash_entry *old_buckets = ht->buckets;
    const size_t old_capacity = ht->capacity;
    const size_t old_length = ht->length;
    size_t i;
 
    if (!new_buckets || new_capacity <= old_capacity) return 0;
 
    memset(new_buckets, 0, sizeof(struct oa_hash_entry) * new_capacity);
 
    /* temporarily switch to new buckets */
    ht->buckets = new_buckets;
    ht->capacity = new_capacity;
    ht->length = 0;
 
    for (i = 0; i < old_capacity; ++i) {
        if (old_buckets[i].state == OA_HASH_ENTRY_OCCUPIED
            && !oa_hash_set_entry(ht, old_buckets[i].key.buf,
                                  old_buckets[i].key.length,
                                  old_buckets[i].value))
        {
            /* restore original state on failure */
            ht->buckets = old_buckets;
            ht->capacity = old_capacity;
            ht->length = old_length;
            return NULL;
        }
    }
    return old_buckets;
}
 
#endif /* OA_HASH_HEADER */
 
#ifdef __cplusplus
}
#endif /* __cplusplus */
 
#endif /* OA_HASH_H */