lsup_rdf/include/htable.h

/**
 * Hash table implementation.
 *
 * This code is hack...ahem, built upon rhashmap:
 * https://github.com/rmind/rhashmap
 *
 * After trying several hash map implementations, none met all the requirements
 * (small, single-file; accept arbitrarily-sized elements; no undebuggable
 * macro spaghetti; reasonably fast), so I decided to expand an existing
 * library and adapt it to a data type agnostic model.
 *
 * This table stores keys and optionally values in a contiguous array 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. 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 "core.h"

/* Max number of entries in the table and hash size. */

/*
 * This allows a table size limited to size_t, which is probably much more than
 * any current system would want to handle in memory.
 */
#if defined(HTABLE_HUGE_SIZE)
typedef size_t ht_hash_t;
typedef size_t htsize_t;
#define HTSIZE_MAX SIZE_MAX

/*
 * This allows max UINT_MAX entries (4,294,967,295) and a large hash size to
 * take full advantage of a very large table.
 */
#elif defined(HTABLE_BIG_SIZE)
typedef size_t ht_hash_t;
typedef uint32_t htsize_t;
#define HTSIZE_MAX UINT32_MAX

/*
 * This allows max UINT_MAX entries but the hash size is smaller, thus it is
 * only recommended for up to a few million entries.
 */
#else
typedef uint32_t ht_hash_t;
typedef uint32_t htsize_t;
#define HTSIZE_MAX UINT32_MAX
#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_VAL 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


/**
 * 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.
 *
 * By default it should keep a good performance up to a few million entries
 * due to its small hash size.
 *
 * If compiled with -DHTABLE_BIG_SIZE it supports up to UINT_MAX entries (~4
 * billions on most modern machines) for very large in-memory graphs.
 *
 * If compiled with -DHTABLE_HUGE_SIZE it supports up to SIZE_MAX entries
 * (probably more then you will ever want to load in memory).
 */
typedef struct htable_t LSUP_HTable;

LSUP_rc
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, LSUP_HTable **ht);

LSUP_rc
LSUP_htable_copy(const LSUP_HTable *src, LSUP_HTable **dest);

LSUP_rc
LSUP_htable_resize(LSUP_HTable *ht, htsize_t newsize);

htsize_t
LSUP_htable_capacity(LSUP_HTable *ht);

htsize_t
LSUP_htable_size(LSUP_HTable *ht);

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

LSUP_rc
LSUP_htable_put(LSUP_HTable *ht, const void *key, const 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 *val[out]: Pointer to be set to the address of the value found
 * at the key address, if any. The memory pointed to is owned by the hash
 * table. If NULL is passed, or if the hash table is a set, the value is never
 * populated.
 *
 * @return int: LSUP_OK if the key is found; LSUP_NORESULT if the key is not
 *  found; a negative value on error.
 */
LSUP_rc
LSUP_htable_get(const LSUP_HTable *ht, const void *key, void **val);

/*
 * 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.
 *
 */
LSUP_rc
LSUP_htable_remove(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.
 */
LSUP_rc
LSUP_htable_iter(LSUP_HTable *ht, htsize_t *cur, void **keyp, void **valp);

/*
 * Free the memory used by the hash table.
 *
 * It is the responsibility of the caller to free data pointed to if pointers
 * were used for keys or values.
 */
void LSUP_htable_free(LSUP_HTable *ht);

#endif