123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162 |
- /**
- * 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 "core.h"
- // Max number of entries in the table. With HTABLE_BIG_SIZE, it is SIZE_MAX.
- // Otherwise, UINT_MAX (4,294,967,295).
- #ifdef HTABLE_BIG_SIZE
- typedef size_t htsize_t;
- #define HTSIZE_MAX SIZE_MAX
- #else
- 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_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 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 *val[out]: Pointer to be set to 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.
- *
- * @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 **keyp, 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
|