1#include <stdbit.h>
2
3#include "include/pw.h"
4#include "src/pw_alloc.h"
5#include "src/types/hash_table.h"
6
7/****************************************************************
8 * hash table implementation
9 *
10 * Notes on indexes and naming conventions.
11 *
12 * In hash map we store indexes of key-value pair (named `kv_index`),
13 * not the index in kv_pairs array.
14 *
15 * key_index is the index of key in kv_pais array, suitable for passing to pw_array_get.
16 *
17 * So,
18 *
19 * value_index = key_index + 1
20 * kv_index = key_index / 2
21 */
22
23static uint8_t get_item_size(unsigned capacity)
24/*
25 * Return hash table item size for desired capacity.
26 *
27 * Index 0 in hash table means no item, so one byte is capable
28 * to index 255 items, not 256.
29 */
30{
31 uint8_t item_size = (UINT_WIDTH - __builtin_clz(capacity | 1) + 7) >> 3;
32 if (item_size == 3) {
33 item_size++;
34#if UINT_WIDTH > 32
35 } else if (item_size > 4) {
36 item_size = 8;
37#endif
38 }
39 return item_size;
40}
41
42#define HT_ITEM_METHODS(typename) \
43 static unsigned get_ht_item_##typename(_PwHashTable* ht, unsigned index) \
44 { \
45 return ((typename*) (ht->items))[index]; \
46 } \
47 static void set_ht_item_##typename(_PwHashTable* ht, unsigned index, unsigned value) \
48 { \
49 ((typename*) (ht->items))[index] = (typename) value; \
50 }
51
52HT_ITEM_METHODS(uint8_t)
53HT_ITEM_METHODS(uint16_t)
54HT_ITEM_METHODS(uint32_t)
55
56#if UINT_WIDTH > 32
57 HT_ITEM_METHODS(uint64_t)
58#endif
59
60[[nodiscard]] static inline unsigned round_capacity(unsigned capacity)
61/*
62 * round capacity up to the nearest power of two
63 */
64{
65 unsigned pwr = 1 << (UINT_WIDTH - stdc_leading_zeros(capacity));
66 if (capacity > pwr) {
67 pwr <<= 1;
68 }
69 return pwr;
70}
71
72void _pw_ht_free(uint16_t type_id, _PwHashTable* ht)
73{
74 unsigned ht_memsize = get_item_size(ht->capacity) * ht->capacity;
75 _pw_free(type_id, (void**) &ht->items, ht_memsize);
76}
77
78unsigned _pw_ht_lookup(_PwHashTable* ht, PwValuePtr key, _PwArray* array, unsigned increment, unsigned* ht_index)
79{
80 // index in the hash table is a hash of item ANDed with hash table bitmask
81 PwType_Hash index = pw_hash(key) & ht->hash_bitmask;
82 for (;;) {
83 // get item index in the array
84 unsigned item_index = ht->get_item(ht, index);
85
86 if (item_index == 0) {
87 // no matching entry
88 if (ht_index) {
89 *ht_index = index;
90 }
91 return UINT_MAX;
92 }
93
94 // make index 0-based
95 item_index--;
96
97 PwValuePtr item = _pw_array_items_ptr(array, item_index * increment);
98
99 // compare keys
100 if (_pw_equal(item, key)) {
101 // found key
102 if (ht_index) {
103 *ht_index = index;
104 }
105 return item_index;
106 }
107
108 // probe next item
109 index = (index + 1) & ht->hash_bitmask;
110 }
111}
112
113unsigned _pw_ht_set_item(_PwHashTable* ht, unsigned ht_index, unsigned item_index)
114{
115 for (;;) {
116 ht_index &= ht->hash_bitmask;
117 if (ht->get_item(ht, ht_index)) {
118 ht_index++;
119 } else {
120 ht->set_item(ht, ht_index, item_index + 1);
121 return ht_index;
122 }
123 }
124}
125
126void _pw_ht_delete_item(_PwHashTable* ht, unsigned ht_index, unsigned item_index, bool adjust)
127{
128 ht->set_item(ht, ht_index, 0);
129
130 if (adjust) {
131 // deleted item was not the last one in the array,
132 // decrement indexes in the hash table that are greater than index of the deleted item
133 unsigned threshold = item_index + 1; // indexes in hash table are 1-based
134 for (unsigned i = 0, n = ht->capacity; i < n; i++) {
135 item_index = ht->get_item(ht, i);
136 if (item_index > threshold) {
137 ht->set_item(ht, i, item_index - 1);
138 }
139 }
140 }
141}
142
143[[nodiscard]] bool _pw_ht_rebuild(uint16_t type_id, _PwHashTable* ht, _PwArray* array, unsigned increment)
144{
145 unsigned n = _pw_array_length(array) / increment;
146 unsigned array_capacity = _pw_array_capacity(array) / increment;
147 unsigned capacity = round_capacity(array_capacity);
148 unsigned quarter_cap = array_capacity >> 2;
149 while (capacity < array_capacity + quarter_cap) {
150 capacity <<= 1;
151 }
152
153 unsigned old_item_size = get_item_size(ht->capacity);
154 unsigned old_memsize = old_item_size * ht->capacity;
155
156 unsigned new_item_size = get_item_size(capacity);
157 unsigned new_memsize = new_item_size * capacity;
158
159 if (!_pw_realloc(type_id, (void**) &ht->items, old_memsize, new_memsize, false)) {
160 return false;
161 }
162 memset(ht->items, 0, new_memsize);
163
164 ht->item_size = new_item_size;
165 ht->capacity = capacity;
166 ht->hash_bitmask = capacity - 1;
167
168 switch (new_item_size) {
169 case 1:
170 ht->get_item = get_ht_item_uint8_t;
171 ht->set_item = set_ht_item_uint8_t;
172 break;
173 case 2:
174 ht->get_item = get_ht_item_uint16_t;
175 ht->set_item = set_ht_item_uint16_t;
176 break;
177 case 4:
178 ht->get_item = get_ht_item_uint32_t;
179 ht->set_item = set_ht_item_uint32_t;
180 break;
181#if UINT_WIDTH > 32
182 case 8:
183 ht->get_item = get_ht_item_uint64_t;
184 ht->set_item = set_ht_item_uint64_t;
185 break;
186#endif
187 default:
188 pw_panic("Bad item size");
189 }
190
191 // rebuild hash table
192 PwValuePtr item_ptr = _pw_array_items_ptr(array, 0);
193 for (unsigned i = 0; i < n; i++) {
194 _pw_ht_set_item(ht, pw_hash(item_ptr), i);
195 item_ptr += increment;
196 }
197 return true;
198}
199
200[[nodiscard]] bool _pw_ht_expand(_PwHashTable* ht, uint16_t type_id, _PwArray* array, unsigned increment)
201{
202 unsigned cap = _pw_array_capacity(array);
203 unsigned len = _pw_array_length(array);
204 if (cap == len) {
205 cap += increment;
206 }
207 cap /= increment;
208 unsigned quarter = cap >> 2;
209 if (cap + quarter <= ht->capacity) {
210 return true;
211 }
212 return _pw_ht_rebuild(type_id, ht, array, increment);
213}