| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | #ifndef NETDATA_SIMPLE_HASHTABLE_H |
| 4 | #define NETDATA_SIMPLE_HASHTABLE_H |
| 5 | |
| 6 | typedef uint64_t SIMPLE_HASHTABLE_HASH; |
| 7 | #define SIMPLE_HASHTABLE_HASH_SECOND_HASH_SHIFTS 32 |
| 8 | |
| 9 | /* |
| 10 | * CONFIGURATION |
| 11 | * |
| 12 | * SIMPLE_HASHTABLE_NAME |
| 13 | * The name of the hashtable - all functions and defines will have this name appended |
| 14 | * Example: #define SIMPLE_HASHTABLE_NAME _FACET_KEY |
| 15 | * |
| 16 | * SIMPLE_HASHTABLE_VALUE_TYPE and SIMPLE_HASHTABLE_KEY_TYPE |
| 17 | * The data types of values and keys - optional - setting them will enable strict type checking by the compiler. |
| 18 | * If undefined, they both default to void. |
| 19 | * |
| 20 | * SIMPLE_HASHTABLE_SORT_FUNCTION |
| 21 | * A function name that accepts 2x values and compares them for sorting (returning -1, 0, 1). |
| 22 | * When set, the hashtable will maintain an always sorted array of the values in the hashtable. |
| 23 | * Do not use this for non-static hashtables. So, if your data is changing all the time, this can make the |
| 24 | * hashtable quite slower (it memmove()s an array of pointers to keep it sorted, on every single change). |
| 25 | * |
| 26 | * SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION and SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION |
| 27 | * The hashtable can either compare just hashes (the default), or hashes and keys (when these are set). |
| 28 | * Both need to be set for this feature to be enabled. |
| 29 | * |
| 30 | * - SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION |
| 31 | * The name of a function accepting SIMPLE_HASHTABLE_VALUE_TYPE pointer. |
| 32 | * It should return a pointer to SIMPLE_HASHTABLE_KEY_TYPE. |
| 33 | * This function is called prior to SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION to extract the key from a value. |
| 34 | * It is also called during hashtable resize, to rehash all values in the hashtable. |
| 35 | * |
| 36 | * - SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION |
| 37 | * The name of a function accepting 2x SIMPLE_HASHTABLE_KEY_TYPE pointers. |
| 38 | * It should return true when the keys match. |
| 39 | * This function is only called when the hashes match, to verify that the keys also match. |
| 40 | * |
| 41 | * SIMPLE_HASHTABLE_SAMPLE_IMPLEMENTATION |
| 42 | * If defined, 3x functions will be injected for easily working with the hashtable. |
| 43 | * |
| 44 | */ |
| 45 | |
| 46 | |
| 47 | #ifndef SIMPLE_HASHTABLE_NAME |
| 48 | #define SIMPLE_HASHTABLE_NAME |
| 49 | #endif |
| 50 | |
| 51 | #ifndef SIMPLE_HASHTABLE_VALUE_TYPE |
| 52 | #define SIMPLE_HASHTABLE_VALUE_TYPE void * |
| 53 | #endif |
| 54 | |
| 55 | #ifndef SIMPLE_HASHTABLE_KEY_TYPE |
| 56 | #define SIMPLE_HASHTABLE_KEY_TYPE void |
| 57 | #endif |
| 58 | |
| 59 | #ifndef SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION |
| 60 | #undef SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION |
| 61 | #endif |
| 62 | |
| 63 | // check during compilation |
| 64 | _Static_assert(sizeof(SIMPLE_HASHTABLE_VALUE_TYPE) <= sizeof(uint64_t), |
| 65 | "simple hashtable value cannot be bigger than 8 bytes"); |
| 66 | |
| 67 | #if defined(SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION) |
| 68 | static inline SIMPLE_HASHTABLE_KEY_TYPE *SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION(SIMPLE_HASHTABLE_VALUE_TYPE); |
| 69 | #endif |
| 70 | |
| 71 | #if defined(SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION) |
| 72 | static inline bool SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION(SIMPLE_HASHTABLE_KEY_TYPE *, SIMPLE_HASHTABLE_KEY_TYPE *); |
| 73 | #endif |
| 74 | |
| 75 | // First layer of macro for token concatenation |
| 76 | #ifndef CONCAT_INDIRECT |
| 77 | #define CONCAT_INDIRECT(a, b) a ## b |
| 78 | #endif |
| 79 | // Second layer of macro, which ensures proper expansion |
| 80 | #ifndef CONCAT |
| 81 | #define CONCAT(a, b) CONCAT_INDIRECT(a, b) |
| 82 | #endif |
| 83 | |
| 84 | // define names for all structures and structures |
| 85 | #define simple_hashtable_init_named CONCAT(simple_hashtable_init, SIMPLE_HASHTABLE_NAME) |
| 86 | #define simple_hashtable_destroy_named CONCAT(simple_hashtable_destroy, SIMPLE_HASHTABLE_NAME) |
| 87 | |
| 88 | #define simple_hashtable_slot_named CONCAT(simple_hashtable_slot, SIMPLE_HASHTABLE_NAME) |
| 89 | #define SIMPLE_HASHTABLE_SLOT_NAMED CONCAT(SIMPLE_HASHTABLE_SLOT, SIMPLE_HASHTABLE_NAME) |
| 90 | #define simple_hashtable_named CONCAT(simple_hashtable, SIMPLE_HASHTABLE_NAME) |
| 91 | #define SIMPLE_HASHTABLE_NAMED CONCAT(SIMPLE_HASHTABLE, SIMPLE_HASHTABLE_NAME) |
| 92 | #define simple_hashtable_resize_named CONCAT(simple_hashtable_resize, SIMPLE_HASHTABLE_NAME) |
| 93 | #define simple_hashtable_can_use_slot_named CONCAT(simple_hashtable_keys_match, SIMPLE_HASHTABLE_NAME) |
| 94 | #define simple_hashtable_get_slot_named CONCAT(simple_hashtable_get_slot, SIMPLE_HASHTABLE_NAME) |
| 95 | #define simple_hashtable_del_slot_named CONCAT(simple_hashtable_del_slot, SIMPLE_HASHTABLE_NAME) |
| 96 | #define simple_hashtable_set_slot_named CONCAT(simple_hashtable_set_slot, SIMPLE_HASHTABLE_NAME) |
| 97 | #define simple_hashtable_first_read_only_named CONCAT(simple_hashtable_first_read_only, SIMPLE_HASHTABLE_NAME) |
| 98 | #define simple_hashtable_next_read_only_named CONCAT(simple_hashtable_next_read_only, SIMPLE_HASHTABLE_NAME) |
| 99 | |
| 100 | #define simple_hashtable_sorted_binary_search_named CONCAT(simple_hashtable_sorted_binary_search, SIMPLE_HASHTABLE_NAME) |
| 101 | #define simple_hashtable_add_value_sorted_named CONCAT(simple_hashtable_add_value_sorted, SIMPLE_HASHTABLE_NAME) |
| 102 | #define simple_hashtable_del_value_sorted_named CONCAT(simple_hashtable_del_value_sorted, SIMPLE_HASHTABLE_NAME) |
| 103 | #define simple_hashtable_replace_value_sorted_named CONCAT(simple_hashtable_replace_value_sorted, SIMPLE_HASHTABLE_NAME) |
| 104 | #define simple_hashtable_sorted_array_first_read_only_named CONCAT(simple_hashtable_sorted_array_first_read_only, SIMPLE_HASHTABLE_NAME) |
| 105 | #define simple_hashtable_sorted_array_next_read_only_named CONCAT(simple_hashtable_sorted_array_next_read_only, SIMPLE_HASHTABLE_NAME) |
| 106 | |
| 107 | typedef struct simple_hashtable_slot_named { |
| 108 | SIMPLE_HASHTABLE_HASH hash; |
| 109 | union { |
| 110 | SIMPLE_HASHTABLE_VALUE_TYPE data; |
| 111 | uint64_t v; // make sure it is always 64bit (required to store our deleted or usernull values) |
| 112 | }; |
| 113 | } SIMPLE_HASHTABLE_SLOT_NAMED; |
| 114 | |
| 115 | typedef struct simple_hashtable_named { |
| 116 | size_t resizes; |
| 117 | size_t searches; |
| 118 | size_t collisions; |
| 119 | size_t additions; |
| 120 | size_t deletions; |
| 121 | size_t deleted; |
| 122 | size_t used; |
| 123 | size_t size; |
| 124 | bool needs_cleanup; |
| 125 | SIMPLE_HASHTABLE_SLOT_NAMED *hashtable; |
| 126 | |
| 127 | #ifdef SIMPLE_HASHTABLE_SORT_FUNCTION |
| 128 | struct { |
| 129 | size_t used; |
| 130 | size_t size; |
| 131 | SIMPLE_HASHTABLE_VALUE_TYPE *array; |
| 132 | } sorted; |
| 133 | #endif |
| 134 | } SIMPLE_HASHTABLE_NAMED; |
| 135 | |
| 136 | #ifdef SIMPLE_HASHTABLE_SORT_FUNCTION |
| 137 | static inline size_t simple_hashtable_sorted_binary_search_named(SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_VALUE_TYPE value) { |
| 138 | size_t left = 0, right = ht->sorted.used; |
| 139 | |
| 140 | while (left < right) { |
| 141 | size_t mid = left + (right - left) / 2; |
| 142 | if (SIMPLE_HASHTABLE_SORT_FUNCTION(ht->sorted.array[mid], value) < 0) |
| 143 | left = mid + 1; |
| 144 | else |
| 145 | right = mid; |
| 146 | } |
| 147 | |
| 148 | return left; |
| 149 | } |
| 150 | |
| 151 | static inline void simple_hashtable_add_value_sorted_named(SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_VALUE_TYPE value) { |
| 152 | size_t index = simple_hashtable_sorted_binary_search_named(ht, value); |
| 153 | |
| 154 | // Ensure there's enough space in the sorted array |
| 155 | if (ht->sorted.used >= ht->sorted.size) { |
| 156 | size_t size = ht->sorted.size ? ht->sorted.size * 2 : 64; |
| 157 | SIMPLE_HASHTABLE_VALUE_TYPE *array = mallocz(size * sizeof(SIMPLE_HASHTABLE_VALUE_TYPE)); |
| 158 | if(ht->sorted.array) { |
| 159 | memcpy(array, ht->sorted.array, ht->sorted.size * sizeof(SIMPLE_HASHTABLE_VALUE_TYPE)); |
| 160 | freez(ht->sorted.array); |
| 161 | } |
| 162 | ht->sorted.array = array; |
| 163 | ht->sorted.size = size; |
| 164 | } |
| 165 | |
| 166 | // Use memmove to shift elements and create space for the new element |
| 167 | memmove(&ht->sorted.array[index + 1], &ht->sorted.array[index], (ht->sorted.used - index) * sizeof(SIMPLE_HASHTABLE_VALUE_TYPE)); |
| 168 | |
| 169 | ht->sorted.array[index] = value; |
| 170 | ht->sorted.used++; |
| 171 | } |
| 172 | |
| 173 | static inline void simple_hashtable_del_value_sorted_named(SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_VALUE_TYPE value) { |
| 174 | size_t index = simple_hashtable_sorted_binary_search_named(ht, value); |
| 175 | |
| 176 | // Check if the value exists at the found index |
| 177 | assert(index < ht->sorted.used && ht->sorted.array[index] == value); |
| 178 | |
| 179 | // Use memmove to shift elements and close the gap |
| 180 | memmove(&ht->sorted.array[index], &ht->sorted.array[index + 1], (ht->sorted.used - index - 1) * sizeof(SIMPLE_HASHTABLE_VALUE_TYPE)); |
| 181 | ht->sorted.used--; |
| 182 | } |
| 183 | |
| 184 | static inline void simple_hashtable_replace_value_sorted_named(SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_VALUE_TYPE old_value, SIMPLE_HASHTABLE_VALUE_TYPE new_value) { |
| 185 | if(new_value == old_value) |
| 186 | return; |
| 187 | |
| 188 | size_t old_value_index = simple_hashtable_sorted_binary_search_named(ht, old_value); |
| 189 | assert(old_value_index < ht->sorted.used && ht->sorted.array[old_value_index] == old_value); |
| 190 | |
| 191 | int r = SIMPLE_HASHTABLE_SORT_FUNCTION(old_value, new_value); |
| 192 | if(r == 0) { |
| 193 | // Same value, so use the same index |
| 194 | ht->sorted.array[old_value_index] = new_value; |
| 195 | return; |
| 196 | } |
| 197 | |
| 198 | size_t new_value_index = simple_hashtable_sorted_binary_search_named(ht, new_value); |
| 199 | if(old_value_index == new_value_index) { |
| 200 | // Not the same value, but still at the same index |
| 201 | ht->sorted.array[old_value_index] = new_value; |
| 202 | return; |
| 203 | } |
| 204 | else if (old_value_index < new_value_index) { |
| 205 | // The old value is before the new value |
| 206 | size_t shift_start = old_value_index + 1; |
| 207 | size_t shift_end = new_value_index - 1; |
| 208 | size_t shift_size = shift_end - old_value_index; |
| 209 | |
| 210 | memmove(&ht->sorted.array[old_value_index], &ht->sorted.array[shift_start], shift_size * sizeof(SIMPLE_HASHTABLE_VALUE_TYPE)); |
| 211 | ht->sorted.array[shift_end] = new_value; |
| 212 | } |
| 213 | else { |
| 214 | // The old value is after the new value |
| 215 | size_t shift_start = new_value_index; |
| 216 | size_t shift_end = old_value_index; |
| 217 | size_t shift_size = shift_end - new_value_index; |
| 218 | |
| 219 | memmove(&ht->sorted.array[new_value_index + 1], &ht->sorted.array[shift_start], shift_size * sizeof(SIMPLE_HASHTABLE_VALUE_TYPE)); |
| 220 | ht->sorted.array[new_value_index] = new_value; |
| 221 | } |
| 222 | } |
| 223 | |
| 224 | static inline SIMPLE_HASHTABLE_VALUE_TYPE *simple_hashtable_sorted_array_first_read_only_named(SIMPLE_HASHTABLE_NAMED *ht) { |
| 225 | if (ht->sorted.used > 0) { |
| 226 | return &ht->sorted.array[0]; |
| 227 | } |
| 228 | return NULL; |
| 229 | } |
| 230 | |
| 231 | static inline SIMPLE_HASHTABLE_VALUE_TYPE *simple_hashtable_sorted_array_next_read_only_named(SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_VALUE_TYPE *last) { |
| 232 | if (!last) return NULL; |
| 233 | |
| 234 | // Calculate the current position in the sorted array |
| 235 | size_t currentIndex = last - ht->sorted.array; |
| 236 | |
| 237 | // Proceed to the next element if it exists |
| 238 | if (currentIndex + 1 < ht->sorted.used) { |
| 239 | return &ht->sorted.array[currentIndex + 1]; |
| 240 | } |
| 241 | |
| 242 | // If no more elements, return NULL |
| 243 | return NULL; |
| 244 | } |
| 245 | |
| 246 | #define SIMPLE_HASHTABLE_SORTED_FOREACH_READ_ONLY(ht, var, type, name) \ |
| 247 | for (type **(var) = simple_hashtable_sorted_array_first_read_only ## name(ht); \ |
| 248 | var; \ |
| 249 | (var) = simple_hashtable_sorted_array_next_read_only ## name(ht, var)) |
| 250 | |
| 251 | #define SIMPLE_HASHTABLE_SORTED_FOREACH_READ_ONLY_VALUE(var) (*(var)) |
| 252 | |
| 253 | #else |
| 254 | static inline void simple_hashtable_add_value_sorted_named(SIMPLE_HASHTABLE_NAMED *ht __maybe_unused, SIMPLE_HASHTABLE_VALUE_TYPE value __maybe_unused) { ; } |
| 255 | static inline void simple_hashtable_del_value_sorted_named(SIMPLE_HASHTABLE_NAMED *ht __maybe_unused, SIMPLE_HASHTABLE_VALUE_TYPE value __maybe_unused) { ; } |
| 256 | static inline void simple_hashtable_replace_value_sorted_named(SIMPLE_HASHTABLE_NAMED *ht __maybe_unused, SIMPLE_HASHTABLE_VALUE_TYPE old_value __maybe_unused, SIMPLE_HASHTABLE_VALUE_TYPE new_value __maybe_unused) { ; } |
| 257 | #endif |
| 258 | |
| 259 | static inline void simple_hashtable_init_named(SIMPLE_HASHTABLE_NAMED *ht, size_t size) { |
| 260 | memset(ht, 0, sizeof(*ht)); |
| 261 | ht->size = size; |
| 262 | ht->hashtable = callocz(ht->size, sizeof(*ht->hashtable)); |
| 263 | } |
| 264 | |
| 265 | static inline void simple_hashtable_destroy_named(SIMPLE_HASHTABLE_NAMED *ht) { |
| 266 | #ifdef SIMPLE_HASHTABLE_SORT_FUNCTION |
| 267 | freez(ht->sorted.array); |
| 268 | #endif |
| 269 | |
| 270 | freez(ht->hashtable); |
| 271 | memset(ht, 0, sizeof(*ht)); |
| 272 | } |
| 273 | |
| 274 | static inline void simple_hashtable_resize_named(SIMPLE_HASHTABLE_NAMED *ht); |
| 275 | |
| 276 | #define simple_hashtable_data_unset ((uint64_t)0) |
| 277 | #define simple_hashtable_data_deleted ((uint64_t)UINT64_MAX) |
| 278 | #define simple_hashtable_data_usernull ((uint64_t)(UINT64_MAX - 1)) |
| 279 | #define simple_hashtable_is_slot_unset(sl) ((sl)->v == simple_hashtable_data_unset) |
| 280 | #define simple_hashtable_is_slot_deleted(sl) ((sl)->v == simple_hashtable_data_deleted) |
| 281 | #define simple_hashtable_is_slot_usernull(sl) ((sl)->v == simple_hashtable_data_usernull) |
| 282 | #define SIMPLE_HASHTABLE_SLOT_DATA(sl) \ |
| 283 | ((simple_hashtable_is_slot_unset(sl) || simple_hashtable_is_slot_deleted(sl) || simple_hashtable_is_slot_usernull(sl)) \ |
| 284 | ? (typeof((sl)->data))0 \ |
| 285 | : (sl)->data) |
| 286 | |
| 287 | static inline bool simple_hashtable_can_use_slot_named( |
| 288 | SIMPLE_HASHTABLE_SLOT_NAMED *sl, SIMPLE_HASHTABLE_HASH hash, |
| 289 | SIMPLE_HASHTABLE_KEY_TYPE *key __maybe_unused) { |
| 290 | |
| 291 | if(simple_hashtable_is_slot_unset(sl)) |
| 292 | return true; |
| 293 | |
| 294 | if(simple_hashtable_is_slot_deleted(sl)) |
| 295 | return false; |
| 296 | |
| 297 | if(sl->hash == hash) { |
| 298 | #if defined(SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION) && defined(SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION) |
| 299 | return SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION(SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION(SIMPLE_HASHTABLE_SLOT_DATA(sl)), key); |
| 300 | #else |
| 301 | return true; |
| 302 | #endif |
| 303 | } |
| 304 | |
| 305 | return false; |
| 306 | } |
| 307 | |
| 308 | #define SIMPLE_HASHTABLE_NEEDS_RESIZE(ht) ((ht)->size <= ((ht)->used - (ht)->deleted) << 1 || (ht)->used >= (ht)->size) |
| 309 | |
| 310 | // IMPORTANT: the pointer returned by this call is valid up to the next call of this function (or the resize one). |
| 311 | // If you need to cache something, cache the hash, not the slot pointer. |
| 312 | static inline SIMPLE_HASHTABLE_SLOT_NAMED *simple_hashtable_get_slot_named( |
| 313 | SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_HASH hash, |
| 314 | SIMPLE_HASHTABLE_KEY_TYPE *key, bool resize) { |
| 315 | |
| 316 | // This function finds the requested hash and key in the hashtable. |
| 317 | // It uses a second version of the hash in case of collisions, and then linear probing. |
| 318 | // It may resize the hashtable if it is more than 50% full. |
| 319 | |
| 320 | // Deleted items remain in the hashtable, but they are marked as DELETED. |
| 321 | // Reuse of DELETED slots happens only if the slot to be returned is UNSET. |
| 322 | // So, when looking up for an item, it tries to find it, assuming DELETED |
| 323 | // slots are occupied. If the item to be returned is UNSET, and it has |
| 324 | // encountered a DELETED slot, it returns the DELETED one instead of the UNSET. |
| 325 | |
| 326 | ht->searches++; |
| 327 | |
| 328 | size_t slot; |
| 329 | SIMPLE_HASHTABLE_SLOT_NAMED *sl; |
| 330 | SIMPLE_HASHTABLE_SLOT_NAMED *deleted; |
| 331 | |
| 332 | slot = hash % ht->size; |
| 333 | sl = &ht->hashtable[slot]; |
| 334 | deleted = simple_hashtable_is_slot_deleted(sl) ? sl : NULL; |
| 335 | if(likely(simple_hashtable_can_use_slot_named(sl, hash, key))) |
| 336 | return (simple_hashtable_is_slot_unset(sl) && deleted) ? deleted : sl; |
| 337 | |
| 338 | ht->collisions++; |
| 339 | |
| 340 | if(unlikely(resize && (ht->needs_cleanup || SIMPLE_HASHTABLE_NEEDS_RESIZE(ht)))) { |
| 341 | simple_hashtable_resize_named(ht); |
| 342 | deleted = NULL; // our deleted pointer is not valid anymore |
| 343 | |
| 344 | slot = hash % ht->size; |
| 345 | sl = &ht->hashtable[slot]; |
| 346 | if(likely(simple_hashtable_can_use_slot_named(sl, hash, key))) |
| 347 | return sl; |
| 348 | |
| 349 | ht->collisions++; |
| 350 | } |
| 351 | |
| 352 | slot = ((hash >> SIMPLE_HASHTABLE_HASH_SECOND_HASH_SHIFTS) + 1) % ht->size; |
| 353 | sl = &ht->hashtable[slot]; |
| 354 | deleted = (!deleted && simple_hashtable_is_slot_deleted(sl)) ? sl : deleted; |
| 355 | |
| 356 | // Linear probing until we find it |
| 357 | SIMPLE_HASHTABLE_SLOT_NAMED *sl_started = sl; |
| 358 | size_t collisions_started = ht->collisions; |
| 359 | while (!simple_hashtable_can_use_slot_named(sl, hash, key)) { |
| 360 | slot = (slot + 1) % ht->size; // Wrap around if necessary |
| 361 | sl = &ht->hashtable[slot]; |
| 362 | deleted = (!deleted && simple_hashtable_is_slot_deleted(sl)) ? sl : deleted; |
| 363 | ht->collisions++; |
| 364 | |
| 365 | if(sl == sl_started) { |
| 366 | if(deleted) { |
| 367 | // we looped through all items, and we didn't find a free slot, |
| 368 | // but we have found a deleted slot, so return it. |
| 369 | return deleted; |
| 370 | } |
| 371 | else if(resize) { |
| 372 | // the hashtable is full, without any deleted slots. |
| 373 | // we need to resize it now. |
| 374 | simple_hashtable_resize_named(ht); |
| 375 | return simple_hashtable_get_slot_named(ht, hash, key, false); |
| 376 | } |
| 377 | else { |
| 378 | // the hashtable is full, but resize is false. |
| 379 | // this should never happen. |
| 380 | assert(sl != sl_started); |
| 381 | } |
| 382 | } |
| 383 | } |
| 384 | |
| 385 | if((ht->collisions - collisions_started) > (ht->size / 2) && ht->deleted >= (ht->size / 3)) { |
| 386 | // we traversed through half of the hashtable to find a slot, |
| 387 | // but we have more than 1/3 deleted items |
| 388 | ht->needs_cleanup = true; |
| 389 | } |
| 390 | |
| 391 | return (simple_hashtable_is_slot_unset(sl) && deleted) ? deleted : sl; |
| 392 | } |
| 393 | |
| 394 | static inline bool simple_hashtable_del_slot_named(SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_SLOT_NAMED *sl) { |
| 395 | if(simple_hashtable_is_slot_unset(sl) || simple_hashtable_is_slot_deleted(sl)) |
| 396 | return false; |
| 397 | |
| 398 | ht->deletions++; |
| 399 | ht->deleted++; |
| 400 | |
| 401 | simple_hashtable_del_value_sorted_named(ht, SIMPLE_HASHTABLE_SLOT_DATA(sl)); |
| 402 | |
| 403 | sl->v = simple_hashtable_data_deleted; |
| 404 | return true; |
| 405 | } |
| 406 | |
| 407 | static inline void simple_hashtable_set_slot_named( |
| 408 | SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_SLOT_NAMED *sl, |
| 409 | SIMPLE_HASHTABLE_HASH hash, SIMPLE_HASHTABLE_VALUE_TYPE data) { |
| 410 | |
| 411 | uint64_t v; |
| 412 | if(unlikely(data == (SIMPLE_HASHTABLE_VALUE_TYPE)0)) |
| 413 | v = simple_hashtable_data_usernull; |
| 414 | else { |
| 415 | #ifdef SIMPLE_HASHTABLE_VALUE_TYPE_IS_NOT_POINTER |
| 416 | v = (uint64_t)data; |
| 417 | #else |
| 418 | v = (uint64_t)(uintptr_t)data; |
| 419 | #endif |
| 420 | } |
| 421 | |
| 422 | if(unlikely(v == simple_hashtable_data_unset || v == simple_hashtable_data_deleted)) { |
| 423 | // the new value is unset or deleted, |
| 424 | // mark the slot as deleted (updating the sorted array as necessary) |
| 425 | simple_hashtable_del_slot_named(ht, sl); |
| 426 | return; |
| 427 | } |
| 428 | |
| 429 | if(likely(simple_hashtable_is_slot_unset(sl))) { |
| 430 | // the slot is empty, |
| 431 | // add the new value to the sorted array (when sorting is requested) |
| 432 | simple_hashtable_add_value_sorted_named(ht, data); |
| 433 | ht->used++; |
| 434 | } |
| 435 | |
| 436 | else if(unlikely(simple_hashtable_is_slot_deleted(sl))) { |
| 437 | // the slot is deleted, |
| 438 | // add the new value to the sorted array (when sorting is requested) |
| 439 | simple_hashtable_add_value_sorted_named(ht, data); |
| 440 | ht->deleted--; |
| 441 | } |
| 442 | |
| 443 | else { |
| 444 | // the slot is occupied, |
| 445 | // replace the old value with the new value in the sorted array (when sorting is requested) |
| 446 | simple_hashtable_replace_value_sorted_named(ht, SIMPLE_HASHTABLE_SLOT_DATA(sl), data); |
| 447 | } |
| 448 | |
| 449 | // update the slot with the new value |
| 450 | sl->hash = hash; |
| 451 | sl->v = v; |
| 452 | |
| 453 | ht->additions++; |
| 454 | } |
| 455 | |
| 456 | // IMPORTANT |
| 457 | // this call invalidates all SIMPLE_HASHTABLE_SLOT_NAMED pointers |
| 458 | static inline void simple_hashtable_resize_named(SIMPLE_HASHTABLE_NAMED *ht) { |
| 459 | SIMPLE_HASHTABLE_SLOT_NAMED *old = ht->hashtable; |
| 460 | size_t old_size = ht->size; |
| 461 | |
| 462 | size_t new_size = ht->size; |
| 463 | |
| 464 | if(SIMPLE_HASHTABLE_NEEDS_RESIZE(ht)) |
| 465 | new_size = (ht->size << 1) - ((ht->size > 16) ? 1 : 0); |
| 466 | |
| 467 | ht->resizes++; |
| 468 | ht->size = new_size; |
| 469 | ht->hashtable = callocz(new_size, sizeof(*ht->hashtable)); |
| 470 | size_t used = 0; |
| 471 | for(size_t i = 0 ; i < old_size ; i++) { |
| 472 | SIMPLE_HASHTABLE_SLOT_NAMED *slot = &old[i]; |
| 473 | if(simple_hashtable_is_slot_unset(slot) || simple_hashtable_is_slot_deleted(slot)) |
| 474 | continue; |
| 475 | |
| 476 | SIMPLE_HASHTABLE_KEY_TYPE *key = NULL; |
| 477 | |
| 478 | #if defined(SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION) && defined(SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION) |
| 479 | SIMPLE_HASHTABLE_VALUE_TYPE value = SIMPLE_HASHTABLE_SLOT_DATA(slot); |
| 480 | key = SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION(value); |
| 481 | #endif |
| 482 | |
| 483 | SIMPLE_HASHTABLE_SLOT_NAMED *slot2 = simple_hashtable_get_slot_named(ht, slot->hash, key, false); |
| 484 | *slot2 = *slot; |
| 485 | used++; |
| 486 | } |
| 487 | |
| 488 | assert(used == ht->used - ht->deleted); |
| 489 | |
| 490 | ht->used = used; |
| 491 | ht->deleted = 0; |
| 492 | ht->needs_cleanup = false; |
| 493 | |
| 494 | freez(old); |
| 495 | } |
| 496 | |
| 497 | // ---------------------------------------------------------------------------- |
| 498 | // hashtable traversal, in read-only mode |
| 499 | // the hashtable should not be modified while the traversal is taking place |
| 500 | |
| 501 | static inline SIMPLE_HASHTABLE_SLOT_NAMED *simple_hashtable_first_read_only_named(SIMPLE_HASHTABLE_NAMED *ht) { |
| 502 | for(size_t i = 0; i < ht->size ;i++) { |
| 503 | SIMPLE_HASHTABLE_SLOT_NAMED *sl = &ht->hashtable[i]; |
| 504 | if(!simple_hashtable_is_slot_unset(sl) && !simple_hashtable_is_slot_deleted(sl)) |
| 505 | return sl; |
| 506 | } |
| 507 | |
| 508 | return NULL; |
| 509 | } |
| 510 | |
| 511 | static inline SIMPLE_HASHTABLE_SLOT_NAMED *simple_hashtable_next_read_only_named(SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_SLOT_NAMED *last) { |
| 512 | if (!last) return NULL; |
| 513 | |
| 514 | // Calculate the current position in the array |
| 515 | size_t index = last - ht->hashtable; |
| 516 | |
| 517 | // Iterate over the hashtable starting from the next element |
| 518 | for (size_t i = index + 1; i < ht->size; i++) { |
| 519 | SIMPLE_HASHTABLE_SLOT_NAMED *sl = &ht->hashtable[i]; |
| 520 | if (!simple_hashtable_is_slot_unset(sl) && !simple_hashtable_is_slot_deleted(sl)) { |
| 521 | return sl; |
| 522 | } |
| 523 | } |
| 524 | |
| 525 | // If no more data slots are found, return NULL |
| 526 | return NULL; |
| 527 | } |
| 528 | |
| 529 | #define SIMPLE_HASHTABLE_FOREACH_READ_ONLY(ht, var, name) \ |
| 530 | for(struct simple_hashtable_slot ## name *(var) = simple_hashtable_first_read_only ## name(ht); \ |
| 531 | var; \ |
| 532 | (var) = simple_hashtable_next_read_only ## name(ht, var)) |
| 533 | |
| 534 | #define SIMPLE_HASHTABLE_FOREACH_READ_ONLY_VALUE(var) SIMPLE_HASHTABLE_SLOT_DATA(var) |
| 535 | |
| 536 | // ---------------------------------------------------------------------------- |
| 537 | // high level implementation |
| 538 | |
| 539 | #ifdef SIMPLE_HASHTABLE_SAMPLE_IMPLEMENTATION |
| 540 | |
| 541 | #ifndef XXH_INLINE_ALL |
| 542 | #define XXH_INLINE_ALL |
| 543 | #endif |
| 544 | #include "../xxHash/xxhash.h" |
| 545 | |
| 546 | #define simple_hashtable_set_named CONCAT(simple_hashtable_set, SIMPLE_HASHTABLE_NAME) |
| 547 | #define simple_hashtable_get_named CONCAT(simple_hashtable_get, SIMPLE_HASHTABLE_NAME) |
| 548 | #define simple_hashtable_del_named CONCAT(simple_hashtable_del, SIMPLE_HASHTABLE_NAME) |
| 549 | |
| 550 | static inline SIMPLE_HASHTABLE_VALUE_TYPE simple_hashtable_set_named(SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_KEY_TYPE *key, size_t key_len, SIMPLE_HASHTABLE_VALUE_TYPE data) { |
| 551 | XXH64_hash_t hash = XXH3_64bits((void *)key, key_len); |
| 552 | SIMPLE_HASHTABLE_SLOT_NAMED *sl = simple_hashtable_get_slot_named(ht, hash, key, true); |
| 553 | simple_hashtable_set_slot_named(ht, sl, hash, data); |
| 554 | return SIMPLE_HASHTABLE_SLOT_DATA(sl); |
| 555 | } |
| 556 | |
| 557 | static inline SIMPLE_HASHTABLE_VALUE_TYPE simple_hashtable_get_named(SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_KEY_TYPE *key, size_t key_len) { |
| 558 | XXH64_hash_t hash = XXH3_64bits((void *)key, key_len); |
| 559 | SIMPLE_HASHTABLE_SLOT_NAMED *sl = simple_hashtable_get_slot_named(ht, hash, key, true); |
| 560 | return SIMPLE_HASHTABLE_SLOT_DATA(sl); |
| 561 | } |
| 562 | |
| 563 | static inline bool simple_hashtable_del_named(SIMPLE_HASHTABLE_NAMED *ht, SIMPLE_HASHTABLE_KEY_TYPE *key, size_t key_len) { |
| 564 | XXH64_hash_t hash = XXH3_64bits((void *)key, key_len); |
| 565 | SIMPLE_HASHTABLE_SLOT_NAMED *sl = simple_hashtable_get_slot_named(ht, hash, key, true); |
| 566 | return simple_hashtable_del_slot_named(ht, sl); |
| 567 | } |
| 568 | |
| 569 | #endif // SIMPLE_HASHTABLE_SAMPLE_IMPLEMENTATION |
| 570 | |
| 571 | // ---------------------------------------------------------------------------- |
| 572 | // Clear the preprocessor defines of simple_hashtable.h |
| 573 | // allowing simple_hashtable.h to be included multiple times |
| 574 | // with different configuration each time. |
| 575 | |
| 576 | #include "simple_hashtable_undef.h" |
| 577 | |
| 578 | #endif //NETDATA_SIMPLE_HASHTABLE_H |