volksdata/include/htable.h

/**
 * Hash table implementation.
 *
 * This code is hack...ahem, built upon Klib:
 * https://github.com/attractivechaos/klib/blob/master/khash.h
 *
 * After trying several hash map implementations, none met all the requirements
 * (small, single-file; accept arbitrarily-sized elements; not an unsightly
 * macro mess; reasonably fast), so I decided to expand a KLib macro and adapt
 * it to a data type agnostic model.
 *
 * This table stores keys and optionally values as unspecified null pointers of
 * arbitrary, but fixed, data sizes. For small keys / values of unusual size,
 * this is convenient because it avoids creating (and having to manage) a
 * pointer for each key and value. Data are all stored inline. The data types
 * are set by casting on retrieval.
 *
 * For larger or variably-sized keys or values, or ones that are not convenient
 * to copy into the table, pointers can obviously be used by specifying ptr_t
 * key and/or value size.
 */

#ifndef _LSUP_HTABLE_H
#define _LSUP_HTABLE_H

#include <inttypes.h>
#include <stdbool.h>

#include "include/core.h"

// Max number of entries in the table. With HTABLE_BIG_SIZE, it is size_t.
// Otherwise, UINT_MAX (4,294,967,295).
#ifdef HTABLE_BIG_SIZE
typedef size_t htsize_t;
#else
typedef uint32_t htsize_t;
#endif

// Size of key entries. With HTABLE_BIG_KEY it is 65535 (64Kb). Otherwise,
// it is 256 bytes.
#ifdef HTABLE_BIG_KEY
typedef uint16_t ksize_t;
#else
typedef uint8_t ksize_t;
#endif

// Size of value entries. With HTABLE_BIG_KEY it is 65535 (64Kb). Otherwise,
// it is 256 bytes. For values that may be larger than 64 Kb, use pointers.
#ifdef HTABLE_BIG_VAL
typedef uint16_t vsize_t;
#else
typedef uint8_t vsize_t;
#endif


typedef enum {
    HTABLE_NOCOPY           = 1 << 0,
    HTABLE_IS_SET           = 1 << 1,
} LSUP_HTFlag;


/**
 * Key hashing function.
 *
 * Takes a void pointer, a key length and a seed.
 */
typedef uint64_t (*key_hash_fn_t)(
        const void *key, ksize_t size, uint64_t seed);

/**
 * Key equality function (true: keys are equal).
 *
 * Takes two void pointers and a key length (which is constant within the
 * hash table).
 */
typedef bool (*key_eq_fn_t)(const void *a, const void *b, ksize_t size);

/**
 * Hash table type.
 *
 * Supports up to UINT_MAX entries (~4 billions on most modern machines).
 *
 * If compiled with -DHTABLE_BIG_SIZE it supports up to size_t entries
 * for extremely large in-memory graphs.
 */
typedef struct htable_t LSUP_HTable;

extern int LSUP_htable_init(
        LSUP_HTable *ht, htsize_t size, ksize_t ksize, vsize_t vsize,
        key_hash_fn_t key_hash_fn, key_eq_fn_t key_eq_fn, unsigned flags);

extern LSUP_HTable *LSUP_htable_new(
        htsize_t size, ksize_t ksize, vsize_t vsize,
        key_hash_fn_t key_hash_fn, key_eq_fn_t key_eq_fn, unsigned flags);

extern int LSUP_htable_resize(LSUP_HTable *ht, htsize_t newsize);

extern htsize_t LSUP_htable_capacity(LSUP_HTable *ht);

extern htsize_t LSUP_htable_size(LSUP_HTable *ht);

extern int LSUP_htable_insert(LSUP_HTable *ht, const void *key, void *val);

extern int LSUP_htable_put(LSUP_HTable *ht, const void *key, void *val);

/**
 * @brief Test the existence of a given key and find its value.
 *
 * @param LSUP_HTable ht[in]: Hash table or set.
 *
 * @param const void *key[in]: Key to look up.
 *
 * @param void **valp[out]: Pointer to be populated with the address of the
 * value found at the key address, if any. If NULL is passed, or if the hash
 * table is a set, the value is never populated. This pointer may be used as an
 * lvalue.
 *
 * @return int: LSUP_OK if the key is found; LSUP_NORESULT if the key is not
 *  found; a negative value on error.
 */
extern int LSUP_htable_get(
        const LSUP_HTable *ht, const void *key, void **valp);

/*
 * Remove the given key.
 *
 * @param LSUP_HTable ht[in]: Hash table or set.
 *
 * @param const void *key[in]: Key to remove.
 *
 * @return int: LSUP_OK if the key was removed; LSUP_NOACTION if it was not
 *  found.
 *
 */
extern int LSUP_htable_del(LSUP_HTable *ht, const void *key);

/**
 * Iterate over a hashmap or set.
 *
 * @param LSUP_HTable ht[in]: Hash table or set.
 *
 * @param htsize_t *cur[in]: an integer used as a cursor. Each successful
 *  iteration of the function increases this value by 1. So the correct use
 *  for this is to initialize a htsize_t variable to zero and passing its
 *  pointer in a loop until necessary.
 *
 * @param void *key[out]: Pointer to be populated with the next key found.
 *
 * @param void **valp[out]: Pointer to the found value address. This can be
 *  used as a normal lvalue. It may be NULL for sets or if the value is not
 *  needed.
 *
 * @return int: LSUP_OK if the key is found; LSUP_END if the end of the data
 *  is reached.
 */
extern int LSUP_htable_iter(
        LSUP_HTable *ht, htsize_t *cur, void *key, void **valp);

/*
 * Free the memory used by the hash table.
 *
 * => It is the responsibility of the caller to remove elements if needed.
 */
extern void LSUP_htable_done(LSUP_HTable *ht);

extern void LSUP_htable_free(LSUP_HTable *ht);

#endif