1#pragma once
 2
 3/*
 4 * Hash table implementation for set and map types.
 5 */
 6
 7#include "src/types/array/array_internal.h"
 8
 9#ifdef __cplusplus
10extern "C" {
11#endif
12
13struct _PwHashTable;
14
15typedef unsigned (*_PwHtGet)(struct _PwHashTable* ht, unsigned index);
16typedef void     (*_PwHtSet)(struct _PwHashTable* ht, unsigned index, unsigned value);
17
18PW_STRUCT(_PwHashTable) {
19    PwType_Hash hash_bitmask;  // calculated from item_size
20    unsigned capacity;
21    uint8_t item_size;  // in bytes
22    _PwHtGet get_item;  // getter function for specific item size
23    _PwHtSet set_item;  // setter function for specific item size
24    uint8_t* items;     // items have variable size
25};
26
27[[nodiscard]] bool _pw_ht_init(uint16_t type_id, _PwHashTable* ht, unsigned capacity);
28
29void _pw_ht_free(uint16_t type_id, _PwHashTable* ht);
30
31unsigned _pw_ht_lookup(_PwHashTable* ht, PwValuePtr key, _PwArray* array, unsigned increment, unsigned* ht_index);
32/*
33 * Lookup key starting from index = hash(key).
34 *
35 * Return index of key in `array` or UINT_MAX if hash table has no item matching `key`.
36 *
37 * If `ht_index` is not `nullptr`: write index of hash table item at which lookup has stopped.
38 */
39
40unsigned _pw_ht_set_item(_PwHashTable* ht, unsigned ht_index, unsigned item_index);
41/*
42 * Assign `item_index` to `hash_table` at position `ht_index` & hash_bitmask.
43 * If the position is already occupied, try next one.
44 *
45 * Return ht_index, possibly updated.
46 */
47
48void _pw_ht_delete_item(_PwHashTable* ht, unsigned ht_index, unsigned item_index, bool adjust);
49/*
50 * Delete item from the hash table. If `adjust` is true, decrement items of the hash table that are greater
51 * than `item_index`.
52 */
53
54[[nodiscard]] bool _pw_ht_rebuild(uint16_t type_id, _PwHashTable* ht, _PwArray* array, unsigned increment);
55/*
56 * Rebuild hash table with elements of `array` spaced by `increment`.
57 * The hash table inherits capacity of `array` divided by `increment`
58 */
59
60[[nodiscard]] bool _pw_ht_expand(_PwHashTable* ht, uint16_t type_id, _PwArray* array, unsigned increment);
61/*
62 * Expand hash table if necessary to hold yet another element.
63 * This function tracks array capacity to avoid premature shrinking of the hash table.
64 */
65
66#ifdef __cplusplus
67}
68#endif