lsup_rdf/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 <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include "include/core.h"

#ifdef LSUP_BIG_HTABLE
typedef size_t ht_size_t;
#else
typedef uint32_t ht_size_t;
#endif

/**
 * Key hashing function.
 *
 * Takes a void pointer. The key length is calculated from the ksize value in
 * the table.
 */
typedef uint64_t (*key_hash_fn_t)(const void *key);

/**
 * Key equality function (true: keys are equal).
 *
 * Takes two void pointers. The key lengths are calculated from the ksize value
 * in the table.
 */
typedef bool (*key_eq_fn_t)(const void *a, const void *b);

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

extern int LSUP_htable_init(
        LSUP_HTable *ht, ht_size_t size, uint32_t ksize, uint32_t vsize,
        key_hash_fn_t key_hash_fn, key_eq_fn_t key_eq_fn);

extern void LSUP_htable_done(LSUP_HTable *ht);

extern ht_size_t LSUP_htable_get(const LSUP_HTable *ht, void *key);

extern ht_size_t LSUP_htable_put(LSUP_HTable *h, void *key, int *ret);

extern void LSUP_htable_del(LSUP_HTable *h, khint_t x);

#endif