123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190 |
- /**
- * 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
|