| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | #ifndef NETDATA_DICTIONARY_HASHTABLE_H |
| 4 | #define NETDATA_DICTIONARY_HASHTABLE_H |
| 5 | |
| 6 | #include "dictionary-internals.h" |
| 7 | |
| 8 | // ---------------------------------------------------------------------------- |
| 9 | // hashtable operations with simple hashtable |
| 10 | |
| 11 | //static inline bool compare_keys(void *key1, void *key2) { |
| 12 | // const char *k1 = key1; |
| 13 | // const char *k2 = key2; |
| 14 | // return strcmp(k1, k2) == 0; |
| 15 | //} |
| 16 | // |
| 17 | //static inline void *item_to_key(DICTIONARY_ITEM *item) { |
| 18 | // return (void *)item_get_name(item); |
| 19 | //} |
| 20 | // |
| 21 | //#define SIMPLE_HASHTABLE_VALUE_TYPE DICTIONARY_ITEM |
| 22 | //#define SIMPLE_HASHTABLE_NAME _DICTIONARY |
| 23 | //#define SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION item_to_key |
| 24 | //#define SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION compare_keys |
| 25 | //#include "..//simple_hashtable.h" |
| 26 | |
| 27 | //static inline size_t hashtable_init_hashtable(DICTIONARY *dict) { |
| 28 | // SIMPLE_HASHTABLE_DICTIONARY *ht = callocz(1, sizeof(*ht)); |
| 29 | // simple_hashtable_init_DICTIONARY(ht, 4); |
| 30 | // dict->index.JudyHSArray = ht; |
| 31 | // return 0; |
| 32 | //} |
| 33 | // |
| 34 | //static inline size_t hashtable_destroy_hashtable(DICTIONARY *dict) { |
| 35 | // SIMPLE_HASHTABLE_DICTIONARY *ht = dict->index.JudyHSArray; |
| 36 | // if(unlikely(!ht)) return 0; |
| 37 | // |
| 38 | // size_t mem = sizeof(*ht) + ht->size * sizeof(SIMPLE_HASHTABLE_SLOT_DICTIONARY); |
| 39 | // simple_hashtable_destroy_DICTIONARY(ht); |
| 40 | // freez(ht); |
| 41 | // dict->index.JudyHSArray = NULL; |
| 42 | // |
| 43 | // return mem; |
| 44 | //} |
| 45 | // |
| 46 | //static inline void *hashtable_insert_hashtable(DICTIONARY *dict, const char *name, size_t name_len) { |
| 47 | // SIMPLE_HASHTABLE_DICTIONARY *ht = dict->index.JudyHSArray; |
| 48 | // |
| 49 | // char key[name_len+1]; |
| 50 | // memcpy(key, name, name_len); |
| 51 | // key[name_len] = '\0'; |
| 52 | // |
| 53 | // XXH64_hash_t hash = XXH3_64bits(name, name_len); |
| 54 | // SIMPLE_HASHTABLE_SLOT_DICTIONARY *sl = simple_hashtable_get_slot_DICTIONARY(ht, hash, key, true); |
| 55 | // sl->hash = hash; // we will need it in insert later - it is ok to overwrite - it is the same already |
| 56 | // return sl; |
| 57 | //} |
| 58 | // |
| 59 | //static inline DICTIONARY_ITEM *hashtable_insert_handle_to_item_hashtable(DICTIONARY *dict, void *handle) { |
| 60 | // (void)dict; |
| 61 | // SIMPLE_HASHTABLE_SLOT_DICTIONARY *sl = handle; |
| 62 | // DICTIONARY_ITEM *item = SIMPLE_HASHTABLE_SLOT_DATA(sl); |
| 63 | // return item; |
| 64 | //} |
| 65 | // |
| 66 | //static inline void hashtable_set_item_hashtable(DICTIONARY *dict, void *handle, DICTIONARY_ITEM *item) { |
| 67 | // SIMPLE_HASHTABLE_DICTIONARY *ht = dict->index.JudyHSArray; |
| 68 | // SIMPLE_HASHTABLE_SLOT_DICTIONARY *sl = handle; |
| 69 | // simple_hashtable_set_slot_DICTIONARY(ht, sl, sl->hash, item); |
| 70 | //} |
| 71 | // |
| 72 | //static inline int hashtable_delete_hashtable(DICTIONARY *dict, const char *name, size_t name_len, DICTIONARY_ITEM *item_to_delete) { |
| 73 | // (void)item_to_delete; |
| 74 | // SIMPLE_HASHTABLE_DICTIONARY *ht = dict->index.JudyHSArray; |
| 75 | // |
| 76 | // char key[name_len+1]; |
| 77 | // memcpy(key, name, name_len); |
| 78 | // key[name_len] = '\0'; |
| 79 | // |
| 80 | // XXH64_hash_t hash = XXH3_64bits(name, name_len); |
| 81 | // SIMPLE_HASHTABLE_SLOT_DICTIONARY *sl = simple_hashtable_get_slot_DICTIONARY(ht, hash, key, false); |
| 82 | // DICTIONARY_ITEM *item = SIMPLE_HASHTABLE_SLOT_DATA(sl); |
| 83 | // if(!item) return 0; // return not-found |
| 84 | // |
| 85 | // simple_hashtable_del_slot_DICTIONARY(ht, sl); |
| 86 | // return 1; // return deleted |
| 87 | //} |
| 88 | // |
| 89 | //static inline DICTIONARY_ITEM *hashtable_get_hashtable(DICTIONARY *dict, const char *name, size_t name_len) { |
| 90 | // SIMPLE_HASHTABLE_DICTIONARY *ht = dict->index.JudyHSArray; |
| 91 | // if(unlikely(!ht)) return NULL; |
| 92 | // |
| 93 | // char key[name_len+1]; |
| 94 | // memcpy(key, name, name_len); |
| 95 | // key[name_len] = '\0'; |
| 96 | // |
| 97 | // XXH64_hash_t hash = XXH3_64bits(name, name_len); |
| 98 | // SIMPLE_HASHTABLE_SLOT_DICTIONARY *sl = simple_hashtable_get_slot_DICTIONARY(ht, hash, key, true); |
| 99 | // return SIMPLE_HASHTABLE_SLOT_DATA(sl); |
| 100 | //} |
| 101 | |
| 102 | // ---------------------------------------------------------------------------- |
| 103 | // hashtable operations with Judy |
| 104 | |
| 105 | static inline size_t hashtable_init_judy(DICTIONARY *dict) { |
| 106 | dict->index.JudyHSArray = NULL; |
| 107 | return 0; |
| 108 | } |
| 109 | |
| 110 | static inline size_t hashtable_destroy_judy(DICTIONARY *dict) { |
| 111 | if(unlikely(!dict->index.JudyHSArray)) return 0; |
| 112 | |
| 113 | pointer_destroy_index(dict); |
| 114 | |
| 115 | JudyAllocThreadPulseReset(); |
| 116 | |
| 117 | JError_t J_Error; |
| 118 | Word_t ret = JudyHSFreeArray(&dict->index.JudyHSArray, &J_Error); |
| 119 | |
| 120 | __atomic_add_fetch(&dict->stats->memory.index, JudyAllocThreadPulseGetAndReset(), __ATOMIC_RELAXED); |
| 121 | |
| 122 | if(unlikely(ret == (Word_t) JERR)) { |
| 123 | netdata_log_error("DICTIONARY: Cannot destroy JudyHS, JU_ERRNO_* == %u, ID == %d", |
| 124 | JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); |
| 125 | } |
| 126 | |
| 127 | netdata_log_debug(D_DICTIONARY, "Dictionary: hash table freed %lu bytes", ret); |
| 128 | |
| 129 | dict->index.JudyHSArray = NULL; |
| 130 | return (size_t)ret; |
| 131 | } |
| 132 | |
| 133 | static inline void *hashtable_insert_judy(DICTIONARY *dict, const char *name, size_t name_len) { |
| 134 | JudyAllocThreadPulseReset(); |
| 135 | |
| 136 | JError_t J_Error; |
| 137 | Pvoid_t *Rc = JudyHSIns(&dict->index.JudyHSArray, (void *)name, name_len, &J_Error); |
| 138 | |
| 139 | __atomic_add_fetch(&dict->stats->memory.index, JudyAllocThreadPulseGetAndReset(), __ATOMIC_RELAXED); |
| 140 | |
| 141 | if (unlikely(Rc == PJERR)) { |
| 142 | netdata_log_error("DICTIONARY: Cannot insert entry with name '%s' to JudyHS, JU_ERRNO_* == %u, ID == %d", |
| 143 | name, JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); |
| 144 | } |
| 145 | |
| 146 | // if *Rc == 0, new item added to the array |
| 147 | // otherwise the existing item value is returned in *Rc |
| 148 | |
| 149 | // we return a pointer to a pointer, so that the caller can |
| 150 | // put anything needed at the value of the index. |
| 151 | // The pointer to pointer we return has to be used before |
| 152 | // any other operation that may change the index (insert/delete). |
| 153 | return (void *)Rc; |
| 154 | } |
| 155 | |
| 156 | static inline DICTIONARY_ITEM *hashtable_insert_handle_to_item_judy(DICTIONARY *dict, void *handle) { |
| 157 | (void)dict; |
| 158 | DICTIONARY_ITEM **item_pptr = handle; |
| 159 | return *item_pptr; |
| 160 | } |
| 161 | |
| 162 | static inline void hashtable_set_item_judy(DICTIONARY *dict, void *handle, DICTIONARY_ITEM *item) { |
| 163 | (void)dict; |
| 164 | DICTIONARY_ITEM **item_pptr = handle; |
| 165 | *item_pptr = item; |
| 166 | } |
| 167 | |
| 168 | static inline int hashtable_delete_judy(DICTIONARY *dict, const char *name, size_t name_len, DICTIONARY_ITEM *item) { |
| 169 | (void)item; |
| 170 | if(unlikely(!dict->index.JudyHSArray)) return 0; |
| 171 | |
| 172 | JudyAllocThreadPulseReset(); |
| 173 | |
| 174 | JError_t J_Error; |
| 175 | int ret = JudyHSDel(&dict->index.JudyHSArray, (void *)name, name_len, &J_Error); |
| 176 | |
| 177 | __atomic_add_fetch(&dict->stats->memory.index, JudyAllocThreadPulseGetAndReset(), __ATOMIC_RELAXED); |
| 178 | |
| 179 | if(unlikely(ret == JERR)) { |
| 180 | netdata_log_error("DICTIONARY: Cannot delete entry with name '%s' from JudyHS, JU_ERRNO_* == %u, ID == %d", |
| 181 | name, |
| 182 | JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); |
| 183 | return 0; |
| 184 | } |
| 185 | |
| 186 | // Hey, this is problematic! We need the value back, not just an int with a status! |
| 187 | // https://sourceforge.net/p/judy/feature-requests/23/ |
| 188 | |
| 189 | if(unlikely(ret == 0)) { |
| 190 | // not found in the dictionary |
| 191 | return 0; |
| 192 | } |
| 193 | else { |
| 194 | // found and deleted from the dictionary |
| 195 | return 1; |
| 196 | } |
| 197 | } |
| 198 | |
| 199 | static inline DICTIONARY_ITEM *hashtable_get_judy(DICTIONARY *dict, const char *name, size_t name_len) { |
| 200 | if(unlikely(!dict->index.JudyHSArray)) return NULL; |
| 201 | |
| 202 | Pvoid_t *Rc; |
| 203 | Rc = JudyHSGet(dict->index.JudyHSArray, (void *)name, name_len); |
| 204 | if(likely(Rc)) { |
| 205 | // found in the hash table |
| 206 | pointer_check(dict, (DICTIONARY_ITEM *)*Rc); |
| 207 | return (DICTIONARY_ITEM *)*Rc; |
| 208 | } |
| 209 | else { |
| 210 | // not found in the hash table |
| 211 | return NULL; |
| 212 | } |
| 213 | } |
| 214 | |
| 215 | // -------------------------------------------------------------------------------------------------------------------- |
| 216 | // select the right hashtable |
| 217 | |
| 218 | static inline size_t hashtable_init_unsafe(DICTIONARY *dict) { |
| 219 | return hashtable_init_judy(dict); |
| 220 | // if(dict->options & DICT_OPTION_INDEX_JUDY) |
| 221 | // return hashtable_init_judy(dict); |
| 222 | // else |
| 223 | // return hashtable_init_hashtable(dict); |
| 224 | } |
| 225 | |
| 226 | static inline size_t hashtable_destroy_unsafe(DICTIONARY *dict) { |
| 227 | pointer_destroy_index(dict); |
| 228 | |
| 229 | // if(dict->options & DICT_OPTION_INDEX_JUDY) |
| 230 | return hashtable_destroy_judy(dict); |
| 231 | // else |
| 232 | // return hashtable_destroy_hashtable(dict); |
| 233 | } |
| 234 | |
| 235 | static inline void *hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { |
| 236 | return hashtable_insert_judy(dict, name, name_len); |
| 237 | // if(dict->options & DICT_OPTION_INDEX_JUDY) |
| 238 | // return hashtable_insert_judy(dict, name, name_len); |
| 239 | // else |
| 240 | // return hashtable_insert_hashtable(dict, name, name_len); |
| 241 | } |
| 242 | |
| 243 | static inline DICTIONARY_ITEM *hashtable_insert_handle_to_item_unsafe(DICTIONARY *dict, void *handle) { |
| 244 | return hashtable_insert_handle_to_item_judy(dict, handle); |
| 245 | // if(dict->options & DICT_OPTION_INDEX_JUDY) |
| 246 | // return hashtable_insert_handle_to_item_judy(dict, handle); |
| 247 | // else |
| 248 | // return hashtable_insert_handle_to_item_hashtable(dict, handle); |
| 249 | } |
| 250 | |
| 251 | static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, DICTIONARY_ITEM *item) { |
| 252 | return hashtable_delete_judy(dict, name, name_len, item); |
| 253 | // if(dict->options & DICT_OPTION_INDEX_JUDY) |
| 254 | // return hashtable_delete_judy(dict, name, name_len, item); |
| 255 | // else |
| 256 | // return hashtable_delete_hashtable(dict, name, name_len, item); |
| 257 | } |
| 258 | |
| 259 | static inline DICTIONARY_ITEM *hashtable_get_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { |
| 260 | DICTIONARY_STATS_SEARCHES_PLUS1(dict); |
| 261 | |
| 262 | DICTIONARY_ITEM *item; |
| 263 | |
| 264 | item = hashtable_get_judy(dict, name, name_len); |
| 265 | // if(dict->options & DICT_OPTION_INDEX_JUDY) |
| 266 | // item = hashtable_get_judy(dict, name, name_len); |
| 267 | // else |
| 268 | // item = hashtable_get_hashtable(dict, name, name_len); |
| 269 | |
| 270 | if(item) |
| 271 | pointer_check(dict, item); |
| 272 | |
| 273 | return item; |
| 274 | } |
| 275 | |
| 276 | static inline void hashtable_set_item_unsafe(DICTIONARY *dict, void *handle, DICTIONARY_ITEM *item) { |
| 277 | hashtable_set_item_judy(dict, handle, item); |
| 278 | // if(dict->options & DICT_OPTION_INDEX_JUDY) |
| 279 | // hashtable_set_item_judy(dict, handle, item); |
| 280 | // else |
| 281 | // hashtable_set_item_hashtable(dict, handle, item); |
| 282 | } |
| 283 | |
| 284 | #endif //NETDATA_DICTIONARY_HASHTABLE_H |