htable.h 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162
  1. /**
  2. * Hash table implementation.
  3. *
  4. * This code is hack...ahem, built upon Klib:
  5. * https://github.com/attractivechaos/klib/blob/master/khash.h
  6. *
  7. * After trying several hash map implementations, none met all the requirements
  8. * (small, single-file; accept arbitrarily-sized elements; not an unsightly
  9. * macro mess; reasonably fast), so I decided to expand a KLib macro and adapt
  10. * it to a data type agnostic model.
  11. *
  12. * This table stores keys and optionally values as unspecified null pointers of
  13. * arbitrary, but fixed, data sizes. For small keys / values of unusual size,
  14. * this is convenient because it avoids creating (and having to manage) a
  15. * pointer for each key and value. Data are all stored inline. The data types
  16. * are set by casting on retrieval.
  17. *
  18. * For larger or variably-sized keys or values, or ones that are not convenient
  19. * to copy into the table, pointers can obviously be used by specifying ptr_t
  20. * key and/or value size.
  21. */
  22. #ifndef _LSUP_HTABLE_H
  23. #define _LSUP_HTABLE_H
  24. #include "core.h"
  25. // Max number of entries in the table. With HTABLE_BIG_SIZE, it is SIZE_MAX.
  26. // Otherwise, UINT_MAX (4,294,967,295).
  27. #ifdef HTABLE_BIG_SIZE
  28. typedef size_t htsize_t;
  29. #define HTSIZE_MAX SIZE_MAX
  30. #else
  31. typedef uint32_t htsize_t;
  32. #define HTSIZE_MAX UINT32_MAX
  33. #endif
  34. // Size of key entries. With HTABLE_BIG_KEY it is 65535 (64Kb). Otherwise,
  35. // it is 256 bytes.
  36. #ifdef HTABLE_BIG_KEY
  37. typedef uint16_t ksize_t;
  38. #else
  39. typedef uint8_t ksize_t;
  40. #endif
  41. // Size of value entries. With HTABLE_BIG_KEY it is 65535 (64Kb). Otherwise,
  42. // it is 256 bytes. For values that may be larger than 64 Kb, use pointers.
  43. #ifdef HTABLE_BIG_VAL
  44. typedef uint16_t vsize_t;
  45. #else
  46. typedef uint8_t vsize_t;
  47. #endif
  48. typedef enum {
  49. HTABLE_NOCOPY = 1 << 0,
  50. HTABLE_IS_SET = 1 << 1,
  51. } LSUP_HTFlag;
  52. /**
  53. * Key hashing function.
  54. *
  55. * Takes a void pointer, a key length and a seed.
  56. */
  57. typedef uint64_t (*key_hash_fn_t)(
  58. const void *key, ksize_t size, uint64_t seed);
  59. /**
  60. * Key equality function (true: keys are equal).
  61. *
  62. * Takes two void pointers and a key length (which is constant within the
  63. * hash table).
  64. */
  65. typedef bool (*key_eq_fn_t)(const void *a, const void *b, ksize_t size);
  66. /**
  67. * Hash table type.
  68. *
  69. * Supports up to UINT_MAX entries (~4 billions on most modern machines).
  70. *
  71. * If compiled with -DHTABLE_BIG_SIZE it supports up to size_t entries
  72. * for extremely large in-memory graphs.
  73. */
  74. typedef struct htable_t LSUP_HTable;
  75. extern LSUP_HTable *LSUP_htable_new(
  76. htsize_t size, ksize_t ksize, vsize_t vsize,
  77. key_hash_fn_t key_hash_fn, key_eq_fn_t key_eq_fn, unsigned flags);
  78. extern int LSUP_htable_resize(LSUP_HTable *ht, htsize_t newsize);
  79. extern htsize_t LSUP_htable_capacity(LSUP_HTable *ht);
  80. extern htsize_t LSUP_htable_size(LSUP_HTable *ht);
  81. extern int LSUP_htable_insert(LSUP_HTable *ht, const void *key, void *val);
  82. extern int LSUP_htable_put(LSUP_HTable *ht, const void *key, void *val);
  83. /**
  84. * @brief Test the existence of a given key and find its value.
  85. *
  86. * @param LSUP_HTable ht[in]: Hash table or set.
  87. *
  88. * @param const void *key[in]: Key to look up.
  89. *
  90. * @param void *val[out]: Pointer to be set to the address of the value found
  91. * at the key address, if any. If NULL is passed, or if the hash table is a
  92. * set, the value is never populated.
  93. *
  94. * @return int: LSUP_OK if the key is found; LSUP_NORESULT if the key is not
  95. * found; a negative value on error.
  96. */
  97. extern int LSUP_htable_get(
  98. const LSUP_HTable *ht, const void *key, void **valp);
  99. /*
  100. * Remove the given key.
  101. *
  102. * @param LSUP_HTable ht[in]: Hash table or set.
  103. *
  104. * @param const void *key[in]: Key to remove.
  105. *
  106. * @return int: LSUP_OK if the key was removed; LSUP_NOACTION if it was not
  107. * found.
  108. *
  109. */
  110. extern int LSUP_htable_del(LSUP_HTable *ht, const void *key);
  111. /**
  112. * Iterate over a hashmap or set.
  113. *
  114. * @param LSUP_HTable ht[in]: Hash table or set.
  115. *
  116. * @param htsize_t *cur[in]: an integer used as a cursor. Each successful
  117. * iteration of the function increases this value by 1. So the correct use
  118. * for this is to initialize a htsize_t variable to zero and passing its
  119. * pointer in a loop until necessary.
  120. *
  121. * @param void *key[out]: Pointer to be populated with the next key found.
  122. *
  123. * @param void **valp[out]: Pointer to the found value address. This can be
  124. * used as a normal lvalue. It may be NULL for sets or if the value is not
  125. * needed.
  126. *
  127. * @return int: LSUP_OK if the key is found; LSUP_END if the end of the data
  128. * is reached.
  129. */
  130. extern int LSUP_htable_iter(
  131. LSUP_HTable *ht, htsize_t *cur, void **keyp, void **valp);
  132. /*
  133. * Free the memory used by the hash table.
  134. *
  135. * => It is the responsibility of the caller to remove elements if needed.
  136. */
  137. extern void LSUP_htable_done(LSUP_HTable *ht);
  138. extern void LSUP_htable_free(LSUP_HTable *ht);
  139. #endif