diff options
Diffstat (limited to 'libnetdata/dictionary/dictionary.h')
| -rw-r--r-- | libnetdata/dictionary/dictionary.h | 197 |
1 files changed, 169 insertions, 28 deletions
diff --git a/libnetdata/dictionary/dictionary.h b/libnetdata/dictionary/dictionary.h index 76213887e..356bf1895 100644 --- a/libnetdata/dictionary/dictionary.h +++ b/libnetdata/dictionary/dictionary.h @@ -5,45 +5,186 @@ #include "../libnetdata.h" -struct dictionary_stats { - unsigned long long inserts; - unsigned long long deletes; - unsigned long long searches; - unsigned long long entries; -}; -typedef struct name_value { - avl_t avl_node; // the index - this has to be first! +/* + * Netdata DICTIONARY features: + * + * CLONE or LINK + * Names and Values in the dictionary can be cloned or linked. + * In clone mode, the dictionary does all the memory management. + * The default is clone for both names and values. + * Set DICTIONARY_FLAG_NAME_LINK_DONT_CLONE to link names. + * Set DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE to link names. + * + * ORDERED + * Items are ordered in the order they are added (new items are appended at the end). + * You may reverse the order by setting the flag DICTIONARY_FLAG_ADD_IN_FRONT. + * + * LOOKUP + * The dictionary uses JudyHS to maintain a very fast randomly accessible hash table. + * + * MULTI-THREADED and SINGLE-THREADED + * Each dictionary may be single threaded (no locks), or multi-threaded (multiple readers or one writer). + * The default is multi-threaded. Add the flag DICTIONARY_FLAG_SINGLE_THREADED for single-threaded. + * + * WALK-THROUGH and FOREACH traversal + * The dictionary can be traversed on read or write mode, either with a callback (walkthrough) or with + * a loop (foreach). + * + * In write mode traversal, the caller may delete only the current item, but may add as many items as needed. + * + */ - uint32_t hash; // a simple hash to speed up searching - // we first compare hashes, and only if the hashes are equal we do string comparisons +#ifndef DICTIONARY_INTERNALS +typedef void DICTIONARY; +#endif - char *name; - void *value; -} NAME_VALUE; +typedef enum dictionary_flags { + DICTIONARY_FLAG_NONE = 0, // the default is the opposite of all below + DICTIONARY_FLAG_SINGLE_THREADED = (1 << 0), // don't use any locks (default: use locks) + DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE = (1 << 1), // don't copy the value, just point to the one provided (default: copy) + DICTIONARY_FLAG_NAME_LINK_DONT_CLONE = (1 << 2), // don't copy the name, just point to the one provided (default: copy) + DICTIONARY_FLAG_WITH_STATISTICS = (1 << 3), // maintain statistics about dictionary operations (default: disabled) + DICTIONARY_FLAG_DONT_OVERWRITE_VALUE = (1 << 4), // don't overwrite values of dictionary items (default: overwrite) + DICTIONARY_FLAG_ADD_IN_FRONT = (1 << 5), // add dictionary items at the front of the linked list (default: at the end) + DICTIONARY_FLAG_RESERVED1 = (1 << 6), // this is reserved for DICTIONARY_FLAG_REFERENCE_COUNTERS +} DICTIONARY_FLAGS; -typedef struct dictionary { - avl_tree_type values_index; +// Create a dictionary +extern DICTIONARY *dictionary_create(DICTIONARY_FLAGS flags); - uint8_t flags; +// an insert callback to be called just after an item is added to the dictionary +// this callback is called while the dictionary is write locked! +extern void dictionary_register_insert_callback(DICTIONARY *dict, void (*ins_callback)(const char *name, void *value, void *data), void *data); - struct dictionary_stats *stats; - netdata_rwlock_t *rwlock; -} DICTIONARY; +// a delete callback to be called just before an item is deleted forever +// this callback is called while the dictionary is write locked! +extern void dictionary_register_delete_callback(DICTIONARY *dict, void (*del_callback)(const char *name, void *value, void *data), void *data); -#define DICTIONARY_FLAG_DEFAULT 0x00000000 -#define DICTIONARY_FLAG_SINGLE_THREADED 0x00000001 -#define DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE 0x00000002 -#define DICTIONARY_FLAG_NAME_LINK_DONT_CLONE 0x00000004 -#define DICTIONARY_FLAG_WITH_STATISTICS 0x00000008 +// a merge callback to be called when DICTIONARY_FLAG_DONT_OVERWRITE_VALUE +// and an item is already found in the dictionary - the dictionary does nothing else in this case +// the old_value will remain in the dictionary - the new_value is ignored +extern void dictionary_register_conflict_callback(DICTIONARY *dict, void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data), void *data); -extern DICTIONARY *dictionary_create(uint8_t flags); -extern void dictionary_destroy(DICTIONARY *dict); +// Destroy a dictionary +// returns the number of bytes freed +// the returned value will not include name and value sizes if DICTIONARY_FLAG_WITH_STATISTICS is not set +extern size_t dictionary_destroy(DICTIONARY *dict); + +// Set an item in the dictionary +// - if an item with the same name does not exist, create one +// - if an item with the same name exists, then: +// a) if DICTIONARY_FLAG_DONT_OVERWRITE_VALUE is set, just return the existing value (ignore the new value) +// else b) reset the value to the new value passed at the call +// +// When DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE is set, the value is linked, otherwise it is copied +// When DICTIONARY_FLAG_NAME_LINK_DONT_CLONE is set, the name is linked, otherwise it is copied +// +// When neither DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE nor DICTIONARY_FLAG_NAME_LINK_DONT_CLONE are set, all the +// memory management for names and values is done by the dictionary. +// +// Passing NULL as value, the dictionary will callocz() the newly allocated value, otherwise it will copy it. +// Passing 0 as value_len, the dictionary will set the value to NULL (no allocations for value will be made). extern void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len) NEVERNULL; + +// Get an item from the dictionary +// If it returns NULL, the item is not found extern void *dictionary_get(DICTIONARY *dict, const char *name); + +// Delete an item from the dictionary +// returns 0 if the item was found and has been deleted +// returns -1 if the item was not found in the index extern int dictionary_del(DICTIONARY *dict, const char *name); -extern int dictionary_get_all(DICTIONARY *dict, int (*callback)(void *entry, void *d), void *data); -extern int dictionary_get_all_name_value(DICTIONARY *dict, int (*callback)(char *name, void *entry, void *d), void *data); +// UNSAFE functions, without locks +// to be used when the user is traversing with the right lock type +// Read lock is acquired by dictionary_walktrhough_read() and dfe_start_read() +// Write lock is acquired by dictionary_walktrhough_write() and dfe_start_write() +// For code readability, please use these macros: +#define dictionary_get_having_read_lock(dict, name) dictionary_get_unsafe(dict, name) +#define dictionary_get_having_write_lock(dict, name) dictionary_get_unsafe(dict, name) +#define dictionary_set_having_write_lock(dict, name, value, value_len) dictionary_set_unsafe(dict, name, value, value_len) +#define dictionary_del_having_write_lock(dict, name) dictionary_del_unsafe(dict, name) + +extern void *dictionary_get_unsafe(DICTIONARY *dict, const char *name); +extern void *dictionary_set_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len); +extern int dictionary_del_unsafe(DICTIONARY *dict, const char *name); + +// Traverse (walk through) the items of the dictionary. +// The order of traversal is currently the order of insertion. +// +// The callback function may return a negative number to stop the traversal, +// in which case that negative value is returned to the caller. +// +// If all callback calls return zero or positive numbers, the sum of all of +// them is returned to the caller. +// +// You cannot alter the dictionary from inside a dictionary_walkthrough_read() - deadlock! +// You can only delete the current item from inside a dictionary_walkthrough_write() - you can add as many as you want. +// +#define dictionary_walkthrough_read(dict, callback, data) dictionary_walkthrough_rw(dict, 'r', callback, data) +#define dictionary_walkthrough_write(dict, callback, data) dictionary_walkthrough_rw(dict, 'w', callback, data) +extern int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const char *name, void *value, void *data), void *data); + +// Traverse with foreach +// +// Use like this: +// +// DICTFE dfe = {}; +// for(MY_ITEM *item = dfe_start_read(&dfe, dict); item ; item = dfe_next(&dfe)) { +// // do things with the item and its dfe.name +// } +// dfe_done(&dfe); +// +// You cannot alter the dictionary from within a dfe_read_start() - deadlock! +// You can only delete the current item from inside a dfe_start_write() - you can add as many as you want. +// + +#ifdef DICTIONARY_INTERNALS +#define DICTFE_CONST +#else +#define DICTFE_CONST const +#endif + +typedef DICTFE_CONST struct dictionary_foreach { + DICTFE_CONST char *name; // the dictionary name of the last item used + void *value; // the dictionary value of the last item used + // same as the return value of dictfe_start() and dictfe_next() + + // the following are for internal use only - to keep track of the point we are + usec_t started_ut; // the time the caller started iterating (now_realtime_usec()) + DICTIONARY *dict; // the dictionary upon we work + void *last_position_index; // the internal position index, to remember the position we are at + void *next_position_index; // the internal position index, of the next item +} DICTFE; + +#define dfe_start_read(dict, value) dfe_start_rw(dict, value, 'r') +#define dfe_start_write(dict, value) dfe_start_rw(dict, value, 'w') +#define dfe_start_rw(dict, value, mode) \ + do { \ + DICTFE value ## _dfe = {}; \ + const char *value ## _name; (void)(value ## _name); \ + for((value) = dictionary_foreach_start_rw(&value ## _dfe, (dict), (mode)), ( value ## _name ) = value ## _dfe.name; \ + (value) ;\ + (value) = dictionary_foreach_next(&value ## _dfe), ( value ## _name ) = value ## _dfe.name) + +#define dfe_done(value) \ + dictionary_foreach_done(&value ## _dfe); \ + } while(0) + +extern void * dictionary_foreach_start_rw(DICTFE *dfe, DICTIONARY *dict, char rw); +extern void * dictionary_foreach_next(DICTFE *dfe); +extern usec_t dictionary_foreach_done(DICTFE *dfe); + +// Get statistics about the dictionary +// If DICTIONARY_FLAG_WITH_STATISTICS is not set, these return zero +extern size_t dictionary_stats_allocated_memory(DICTIONARY *dict); +extern size_t dictionary_stats_entries(DICTIONARY *dict); +extern size_t dictionary_stats_inserts(DICTIONARY *dict); +extern size_t dictionary_stats_searches(DICTIONARY *dict); +extern size_t dictionary_stats_deletes(DICTIONARY *dict); +extern size_t dictionary_stats_resets(DICTIONARY *dict); + +extern int dictionary_unittest(size_t entries); #endif /* NETDATA_DICTIONARY_H */ |