diff options
Diffstat (limited to 'libnetdata/dictionary')
| -rw-r--r-- | libnetdata/dictionary/README.md | 202 | ||||
| -rw-r--r-- | libnetdata/dictionary/dictionary.c | 1264 | ||||
| -rw-r--r-- | libnetdata/dictionary/dictionary.h | 197 |
3 files changed, 1480 insertions, 183 deletions
diff --git a/libnetdata/dictionary/README.md b/libnetdata/dictionary/README.md index 6049c7f66..28d0cfbbd 100644 --- a/libnetdata/dictionary/README.md +++ b/libnetdata/dictionary/README.md @@ -2,4 +2,206 @@ custom_edit_url: https://github.com/netdata/netdata/edit/master/libnetdata/dictionary/README.md --> +# Dictionaries +Netdata dictionaries associate a `name` with a `value`: + +- A `name` can be any string. +- A `value` can be anything. + +Such a pair of a `name` and a `value` consists of an `item` or an `entry` in the dictionary. + +Dictionaries provide an interface to: + +- **Add** an item to the dictionary +- **Get** an item from the dictionary (provided its `name`) +- **Delete** an item from the dictionary (provided its `name`) +- **Traverse** the list of items in the dictionary + +Dictionaries are **ordered**, meaning that the order they have been added is preserved while traversing them. The caller may reverse this order by passing the flag `DICTIONARY_FLAG_ADD_IN_FRONT` when creating the dictionary. + +Dictionaries guarantee **uniqueness** of all items added to them, meaning that only one item with a given name can exist in the dictionary at any given time. + +Dictionaries are extremely fast in all operations. They are indexing the keys with `JudyHS` and they utilize a double-linked-list for the traversal operations. Deletion is the most expensive operation, usually somewhat slower than insertion. + +## Memory management + +Dictionaries come with 2 memory management options: + +- **Clone** (copy) the name and/or the value to memory allocated by the dictionary. +- **Link** the name and/or the value, without allocating any memory about them. + +In **clone** mode, the dictionary guarantees that all operations on the dictionary items will automatically take care of the memory used by the name and/or the value. In case the value is an object needs to have user allocated memory, the following callback functions can be registered: + + 1.`dictionary_register_insert_callback()` that will be called just after the insertion of an item to the dictionary, or after the replacement of the value of a dictionary item (but while the dictionary is write-locked - if locking is enabled). + 2. `dictionary_register_delete_callback()` that will be called just prior to the deletion of an item from the dictionary, or prior to the replacement of the value of a dictionary item (but while the dictionary is write-locked - if locking is enabled). + 3. `dictionary_register_conflict_callback()` that will be called when `DICTIONARY_FLAG_DONT_OVERWRITE_VALUE` is set and another value is attempted to be inserted for the same key. + +In **link** mode, the name and/or the value are just linked to the dictionary item, and it is the user's responsibility to free the memory used after an item is deleted from the dictionary. + +By default, **clone** mode is used for both the name and the value. + +To use **link** mode for names, add `DICTIONARY_FLAG_NAME_LINK_DONT_CLONE` to the flags when creating the dictionary. + +To use **link** mode for values, add `DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE` to the flags when creating the dictionary. + +## Locks + +The dictionary allows both **single-threaded** operation (no locks - faster) and **multi-threaded** operation utilizing a read-write lock. + +The default is **multi-threaded**. To enable **single-threaded** add `DICTIONARY_FLAG_SINGLE_THREADED` to the flags when creating the dictionary. + +## Hash table operations + +The dictionary supports the following operations supported by the hash table: + +- `dictionary_set()` to add an item to the dictionary, or change its value. +- `dictionary_get()` to get an item from the dictionary. +- `dictionary_del()` to delete an item from the dictionary. + +## Creation and destruction + +Use `dictionary_create()` to create a dictionary. + +Use `dictionary_destroy()` to destroy a dictionary. When destroyed, a dictionary frees all the memory it has allocated on its own. The exception is the registration of a deletion callback function that can be called on deletion of an item, which may free additional resources. + +### dictionary_set() + +This call is used to: + +- **add** an item to the dictionary. +- **reset** the value of an existing item in the dictionary. + +If **resetting** is not desired, add `DICTIONARY_FLAG_DONT_OVERWRITE_VALUE` to the flags when creating the dictionary. In this case, `dictionary_set()` will return the value of the original item found in the dictionary instead of resetting it and the value passed to the call will be ignored. + +For **multi-threaded** operation, the `dictionary_set()` calls get an exclusive write lock on the dictionary. + +The format is: + +```c +value = dictionary_set(dict, name, value, value_len); +``` + +Where: + +* `dict` is a pointer to the dictionary previously created. +* `name` is a pointer to a string to be used as the key of this item. The name must not be `NULL` and must not be an empty string `""`. +* `value` is a pointer to the value associated with this item. In **clone** mode, if `value` is `NULL`, a new memory allocation will be made of `value_len` size and will be initialized to zero. +* `value_len` is the size of the `value` data. If `value_len` is zero, no allocation will be done and the dictionary item will permanently have the `NULL` value. + +> **IMPORTANT**<br/>There is also an **unsafe** version (without locks) of this call. This is to be used when traversing the dictionary. It should never be called without an active lock on the dictionary, which can only be acquired while traversing. + +### dictionary_get() + +This call is used to get the value of an item, given its name. It utilizes the JudyHS hash table for making the lookup. + +For **multi-threaded** operation, the `dictionary_get()` call gets a shared read lock on the dictionary. + +The format is: + +```c +value = dictionary_get(dict, name); +``` + +Where: + +* `dict` is a pointer to the dictionary previously created. +* `name` is a pointer to a string to be used as the key of this item. The name must not be `NULL` and must not be an empty string `""`. + +> **IMPORTANT**<br/>There is also an **unsafe** version (without locks) of this call. This is to be used when traversing the dictionary. It should never be called without an active lock on the dictionary, which can only be acquired while traversing. + +### dictionary_del() + +This call is used to delete an item from the dictionary, given its name. + +If there is a delete callback registered to the dictionary (`dictionary_register_delete_callback()`), it is called prior to the actual deletion of the item. + +For **multi-threaded** operation, the `dictionary_del()` calls get an exclusive write lock on the dictionary. + +The format is: + +```c +value = dictionary_del(dict, name); +``` + +Where: + +* `dict` is a pointer to the dictionary previously created. +* `name` is a pointer to a string to be used as the key of this item. The name must not be `NULL` and must not be an empty string `""`. + +> **IMPORTANT**<br/>There is also an **unsafe** version (without locks) of this call. This is to be used when traversing the dictionary, to delete the current item. It should never be called without an active lock on the dictionary, which can only be acquired while traversing. + +## Traversal + +Dictionaries offer 2 ways to traverse the entire dictionary: + +- **walkthrough**, implemented by setting a callback function to be called for every item. +- **foreach**, a way to traverse the dictionary with a for-next loop. + +Both of these methods are available in **read** or **write** mode. In **read** mode only lookups are allowed to the dictionary. In **write** both lookups but also deletion of the currently working item is also allowed. + +While traversing the dictionary with any of these methods, all calls to the dictionary have to use the `_unsafe` versions of the function calls, otherwise deadlock may arise. + +> **IMPORTANT**<br/>The dictionary itself does not check to ensure that a user is actually using the right lock mode (read or write) while traversing the dictionary for each of the unsafe calls. + +### walkthrough (callback) + +There are 2 calls: + +- `dictionary_walkthrough_read()` that acquires a shared read lock, and it calls a callback function for every item of the dictionary. The callback function may use the unsafe versions of the `dictionary_get()` calls to lookup other items in the dictionary, but it should not add or remove item from the dictionary. +- `dictionary_walkthrough_write()` that acquires an exclusive write lock, and it calls a callback function for every item of the dictionary. This is to be used when items need to be added to the dictionary, or when the current item may need to be deleted. If the callback function deletes any other items, the behavior may be undefined (actually, the item next to the one currently working should not be deleted - a pointer to it is held by the traversal function to move on traversing the dictionary). + +The items are traversed in the same order they have been added to the dictionary (or the reverse order if the flag `DICTIONARY_FLAG_ADD_IN_FRONT` is set during dictionary creation). + +The callback function returns an `int`. If this value is negative, traversal of the dictionary is stopped immediately and the negative value is returned to the caller. If the returned value of all callbacks is zero or positive, the walkthrough functions return the sum of the return values of all callbacks. So, if you are just interested to know how many items fall into some condition, write a callback function that returns 1 when the item satisfies that condition and 0 when it does not and the walkthrough function will return how many tested positive. + +### foreach (for-next loop) + +The following is a snippet of such a loop: + +```c +MY_ITEM *item; +dfe_start_read(dict, item) { + printf("hey, I got an item named '%s' with value ptr %08X", item_name, item); +} +dfe_done(item); +``` + +The `item` parameter gives the name of the pointer to be used while iterating the items. Any name is accepted. + +The `item_name` is a variable that is automatically created, by concatenating whatever is given as `item` and `_name`. So, if you call `dfe_start_read(dict, myvar)`, the name will be `myvar_name`. + +Both `dfe_start_read(dict, item)` and `dfe_done(item)` are together inside a `do { ... } while(0)` loop, so that the following will work: + +```c +MY_ITEM *item; + +if(x = 1) + // do { + dfe_start_read(dict, item) + printf("hey, I got an item named '%s' with value ptr %08X", item_name, item); + dfe_done(item); + // } while(0); +else + something else; +``` + +In the above, the `if(x)` condition will work as expected. It will do the foreach loop when x is 1, otherwise it will run `something else`. + +There are 2 versions of `dfe_start`: + +- `dfe_start_read()` that acquires a shared read lock to the dictionary. +- `dfe_start_write()` that acquires an exclusive write lock to the dictionary. + +While in the loop, depending on the read or write versions of `dfe_start`, the caller may lookup or manipulate the dictionary. The rules are the same with the walkthrough callback functions. + +PS: DFE is Dictionary For Each. + +## special multi-threaded lockless case + +Since the dictionary uses a hash table and a double linked list, if the contract between 2 threads is for one to use the hash table functions only (`set`, `get` - but no `del`) and the other to use the traversal ones only, the dictionary allows concurrent use without locks. + +This is currently used in statsd: + +- the data collection thread uses only `get` and `set`. It never uses `del`. New items are added at the front of the linked list (`DICTIONARY_FLAG_ADD_IN_FRONT`). +- the flushing thread is only traversing the dictionary up to the point it last traversed it (it uses a flag for that to know where it stopped last time). It never uses `get`, `set` or `del`. diff --git a/libnetdata/dictionary/dictionary.c b/libnetdata/dictionary/dictionary.c index b3dc3f371..42285037d 100644 --- a/libnetdata/dictionary/dictionary.c +++ b/libnetdata/dictionary/dictionary.c @@ -1,225 +1,772 @@ // SPDX-License-Identifier: GPL-3.0-or-later +// NOT TO BE USED BY USERS YET +#define DICTIONARY_FLAG_REFERENCE_COUNTERS (1 << 6) // maintain reference counter in walkthrough and foreach + +typedef struct dictionary DICTIONARY; +#define DICTIONARY_INTERNALS + #include "../libnetdata.h" +#ifndef ENABLE_DBENGINE +#define DICTIONARY_WITH_AVL +#warning Compiling DICTIONARY with an AVL index +#else +#define DICTIONARY_WITH_JUDYHS +#endif + +#ifdef DICTIONARY_WITH_JUDYHS +#include <Judy.h> +#endif + +/* + * This version uses JudyHS arrays to index the dictionary + * + * The following output is from the unit test, at the end of this file: + * + * This is the JudyHS version: + * + * 1000000 x dictionary_set() (dictionary size 0 entries, 0 KB)... + * 1000000 x dictionary_get(existing) (dictionary size 1000000 entries, 74001 KB)... + * 1000000 x dictionary_get(non-existing) (dictionary size 1000000 entries, 74001 KB)... + * Walking through the dictionary (dictionary size 1000000 entries, 74001 KB)... + * 1000000 x dictionary_del(existing) (dictionary size 1000000 entries, 74001 KB)... + * 1000000 x dictionary_set() (dictionary size 0 entries, 0 KB)... + * Destroying dictionary (dictionary size 1000000 entries, 74001 KB)... + * + * TIMINGS: + * adding 316027 usec, positive search 156740 usec, negative search 84524, walk through 15036 usec, deleting 361444, destroy 107394 usec + * + * This is from the JudySL version: + * + * Creating dictionary of 1000000 entries... + * Checking index of 1000000 entries... + * Walking 1000000 entries and checking name-value pairs... + * Created and checked 1000000 entries, found 0 errors - used 58376 KB of memory + * Destroying dictionary of 1000000 entries... + * Deleted 1000000 entries + * create 338975 usec, check 156080 usec, walk 80764 usec, destroy 444569 usec + * + * This is the AVL version: + * + * Creating dictionary of 1000000 entries... + * Checking index of 1000000 entries... + * Walking 1000000 entries and checking name-value pairs... + * Created and checked 1000000 entries, found 0 errors - used 89626 KB of memory + * Destroying dictionary of 1000000 entries... + * create 413892 usec, check 220006 usec, walk 34247 usec, destroy 98062 usec + * + * So, the JudySL is a lot slower to WALK and DESTROY (DESTROY does a WALK) + * It is slower, because for every item, JudySL copies the KEY/NAME to a + * caller supplied buffer (Index). So, by just walking over 1 million items, + * JudySL does 1 million strcpy() !!! + * + * It also seems that somehow JudySLDel() is unbelievably slow too! + * + */ + + +/* + * Every item in the dictionary has the following structure. + */ +typedef struct name_value { +#ifdef DICTIONARY_WITH_AVL + avl_t avl_node; +#endif + + struct name_value *next; // a double linked list to allow fast insertions and deletions + struct name_value *prev; + + char *name; // the name of the dictionary item + void *value; // the value of the dictionary item +} NAME_VALUE; + +/* + * When DICTIONARY_FLAG_WITH_STATISTICS is set, we need to keep track of all the memory + * we allocate and free. So, we need to keep track of the sizes of all names and values. + * We do this by overloading NAME_VALUE with the following additional fields. + */ + +typedef enum name_value_flags { + NAME_VALUE_FLAG_NONE = 0, + NAME_VALUE_FLAG_DELETED = (1 << 0), // this item is deleted +} NAME_VALUE_FLAGS; + +typedef struct name_value_with_stats { + NAME_VALUE name_value_data_here; // never used - just to put the lengths at the right position + + size_t name_len; // the size of the name, including the terminating zero + size_t value_len; // the size of the value (assumed binary) + + size_t refcount; // the reference counter + NAME_VALUE_FLAGS flags; // the flags for this item +} NAME_VALUE_WITH_STATS; + +struct dictionary_stats { + size_t inserts; + size_t deletes; + size_t searches; + size_t resets; + size_t entries; + size_t memory; +}; + +struct dictionary { + DICTIONARY_FLAGS flags; // the flags of the dictionary + + NAME_VALUE *first_item; // the double linked list base pointers + NAME_VALUE *last_item; + +#ifdef DICTIONARY_WITH_AVL + avl_tree_type values_index; + NAME_VALUE *hash_base; +#endif + +#ifdef DICTIONARY_WITH_JUDYHS + Pvoid_t JudyHSArray; // the hash table +#endif + + netdata_rwlock_t *rwlock; // the r/w lock when DICTIONARY_FLAG_SINGLE_THREADED is not set + + void (*ins_callback)(const char *name, void *value, void *data); + void *ins_callback_data; + + void (*del_callback)(const char *name, void *value, void *data); + void *del_callback_data; + + void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data); + void *conflict_callback_data; + + struct dictionary_stats *stats; // the statistics when DICTIONARY_FLAG_WITH_STATISTICS is set +}; + +void dictionary_register_insert_callback(DICTIONARY *dict, void (*ins_callback)(const char *name, void *value, void *data), void *data) { + dict->ins_callback = ins_callback; + dict->ins_callback_data = data; +} + +void dictionary_register_delete_callback(DICTIONARY *dict, void (*del_callback)(const char *name, void *value, void *data), void *data) { + dict->del_callback = del_callback; + dict->del_callback_data = data; +} + +void dictionary_register_conflict_callback(DICTIONARY *dict, void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data), void *data) { + dict->conflict_callback = conflict_callback; + dict->conflict_callback_data = data; +} + // ---------------------------------------------------------------------------- -// dictionary statistics +// dictionary statistics maintenance -static inline void NETDATA_DICTIONARY_STATS_INSERTS_PLUS1(DICTIONARY *dict) { - if(likely(dict->stats)) - dict->stats->inserts++; +size_t dictionary_stats_allocated_memory(DICTIONARY *dict) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) + return dict->stats->memory; + return 0; } -static inline void NETDATA_DICTIONARY_STATS_DELETES_PLUS1(DICTIONARY *dict) { - if(likely(dict->stats)) - dict->stats->deletes++; +size_t dictionary_stats_entries(DICTIONARY *dict) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) + return dict->stats->entries; + return 0; } -static inline void NETDATA_DICTIONARY_STATS_SEARCHES_PLUS1(DICTIONARY *dict) { - if(likely(dict->stats)) +size_t dictionary_stats_searches(DICTIONARY *dict) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) + return dict->stats->searches; + return 0; +} +size_t dictionary_stats_inserts(DICTIONARY *dict) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) + return dict->stats->inserts; + return 0; +} +size_t dictionary_stats_deletes(DICTIONARY *dict) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) + return dict->stats->deletes; + return 0; +} +size_t dictionary_stats_resets(DICTIONARY *dict) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) + return dict->stats->resets; + return 0; +} + +static inline void DICTIONARY_STATS_SEARCHES_PLUS1(DICTIONARY *dict) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) dict->stats->searches++; } -static inline void NETDATA_DICTIONARY_STATS_ENTRIES_PLUS1(DICTIONARY *dict) { - if(likely(dict->stats)) +static inline void DICTIONARY_STATS_ENTRIES_PLUS1(DICTIONARY *dict, size_t size) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { + dict->stats->inserts++; dict->stats->entries++; + dict->stats->memory += size; + } } -static inline void NETDATA_DICTIONARY_STATS_ENTRIES_MINUS1(DICTIONARY *dict) { - if(likely(dict->stats)) +static inline void DICTIONARY_STATS_ENTRIES_MINUS1(DICTIONARY *dict, size_t size) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { + dict->stats->deletes++; dict->stats->entries--; + dict->stats->memory -= size; + } +} +static inline void DICTIONARY_STATS_VALUE_RESETS_PLUS1(DICTIONARY *dict, size_t oldsize, size_t newsize) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { + dict->stats->resets++; + dict->stats->memory += newsize; + dict->stats->memory -= oldsize; + } } - // ---------------------------------------------------------------------------- // dictionary locks -static inline void dictionary_read_lock(DICTIONARY *dict) { - if(likely(dict->rwlock)) { +static inline size_t dictionary_lock_init(DICTIONARY *dict) { + if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { + dict->rwlock = mallocz(sizeof(netdata_rwlock_t)); + netdata_rwlock_init(dict->rwlock); + return sizeof(netdata_rwlock_t); + } + dict->rwlock = NULL; + return 0; +} + +static inline size_t dictionary_lock_free(DICTIONARY *dict) { + if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { + netdata_rwlock_destroy(dict->rwlock); + freez(dict->rwlock); + return sizeof(netdata_rwlock_t); + } + return 0; +} + +static inline void dictionary_lock_rlock(DICTIONARY *dict) { + if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { // debug(D_DICTIONARY, "Dictionary READ lock"); netdata_rwlock_rdlock(dict->rwlock); } } -static inline void dictionary_write_lock(DICTIONARY *dict) { - if(likely(dict->rwlock)) { +static inline void dictionary_lock_wrlock(DICTIONARY *dict) { + if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { // debug(D_DICTIONARY, "Dictionary WRITE lock"); netdata_rwlock_wrlock(dict->rwlock); } } static inline void dictionary_unlock(DICTIONARY *dict) { - if(likely(dict->rwlock)) { + if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { // debug(D_DICTIONARY, "Dictionary UNLOCK lock"); netdata_rwlock_unlock(dict->rwlock); } } +// ---------------------------------------------------------------------------- +// reference counters + +static inline size_t reference_counter_init(DICTIONARY *dict) { + (void)dict; + + // allocate memory required for reference counters + // return number of bytes + return 0; +} + +static inline size_t reference_counter_free(DICTIONARY *dict) { + (void)dict; + + // free memory required for reference counters + // return number of bytes + return 0; +} + +static void reference_counter_acquire(DICTIONARY *dict, NAME_VALUE *nv) { + if(unlikely(dict->flags & DICTIONARY_FLAG_REFERENCE_COUNTERS)) { + NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; + __atomic_fetch_add(&nvs->refcount, 1, __ATOMIC_SEQ_CST); + } +} + +static void reference_counter_release(DICTIONARY *dict, NAME_VALUE *nv) { + if(unlikely(dict->flags & DICTIONARY_FLAG_REFERENCE_COUNTERS)) { + NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; + __atomic_fetch_sub(&nvs->refcount, 1, __ATOMIC_SEQ_CST); + } +} + +static int reference_counter_mark_deleted(DICTIONARY *dict, NAME_VALUE *nv) { + if(unlikely(dict->flags & DICTIONARY_FLAG_REFERENCE_COUNTERS)) { + NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; + nvs->flags |= NAME_VALUE_FLAG_DELETED; + return 1; + } + return 0; +} // ---------------------------------------------------------------------------- -// avl index +// hash table +#ifdef DICTIONARY_WITH_AVL static int name_value_compare(void* a, void* b) { - if(((NAME_VALUE *)a)->hash < ((NAME_VALUE *)b)->hash) return -1; - else if(((NAME_VALUE *)a)->hash > ((NAME_VALUE *)b)->hash) return 1; - else return strcmp(((NAME_VALUE *)a)->name, ((NAME_VALUE *)b)->name); + return strcmp(((NAME_VALUE *)a)->name, ((NAME_VALUE *)b)->name); } -static inline NAME_VALUE *dictionary_name_value_index_find_nolock(DICTIONARY *dict, const char *name, uint32_t hash) { +static void hashtable_init_unsafe(DICTIONARY *dict) { + avl_init(&dict->values_index, name_value_compare); +} + +static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { + (void)dict; + return 0; +} + +static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, NAME_VALUE *nv) { + (void)name; + (void)name_len; + + if(unlikely(avl_remove(&(dict->values_index), (avl_t *)(nv)) != (avl_t *)nv)) + return 0; + + return 1; +} + +static inline NAME_VALUE *hashtable_get_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { + (void)name_len; + NAME_VALUE tmp; - tmp.hash = (hash)?hash:simple_hash(name); tmp.name = (char *)name; - - NETDATA_DICTIONARY_STATS_SEARCHES_PLUS1(dict); return (NAME_VALUE *)avl_search(&(dict->values_index), (avl_t *) &tmp); } +static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { + // AVL needs a NAME_VALUE to insert into the dictionary but we don't have it yet. + // So, the only thing we can do, is return an existing one if it is already there. + // Returning NULL will make the caller thing we added it, will allocate one + // and will call hashtable_inserted_name_value_unsafe(), at which we will do + // the actual indexing. + + dict->hash_base = hashtable_get_unsafe(dict, name, name_len); + return &dict->hash_base; +} + +static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, const char *name, size_t name_len, NAME_VALUE *nv) { + // we have our new NAME_VALUE object. + // Let's index it. + + (void)name; + (void)name_len; + + if(unlikely(avl_insert(&((dict)->values_index), (avl_t *)(nv)) != (avl_t *)nv)) + error("dictionary: INTERNAL ERROR: duplicate insertion to dictionary."); +} +#endif + +#ifdef DICTIONARY_WITH_JUDYHS +static void hashtable_init_unsafe(DICTIONARY *dict) { + dict->JudyHSArray = NULL; +} + +static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { + if(unlikely(!dict->JudyHSArray)) return 0; + + JError_t J_Error; + Word_t ret = JudyHSFreeArray(&dict->JudyHSArray, &J_Error); + if(unlikely(ret == (Word_t) JERR)) { + error("DICTIONARY: Cannot destroy JudyHS, JU_ERRNO_* == %u, ID == %d", + JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); + } + + debug(D_DICTIONARY, "Dictionary: hash table freed %lu bytes", ret); + + dict->JudyHSArray = NULL; + return (size_t)ret; +} + +static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { + JError_t J_Error; + Pvoid_t *Rc = JudyHSIns(&dict->JudyHSArray, (void *)name, name_len, &J_Error); + if (unlikely(Rc == PJERR)) { + fatal("DICTIONARY: Cannot insert entry with name '%s' to JudyHS, JU_ERRNO_* == %u, ID == %d", + name, JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); + } + + // if *Rc == 0, new item added to the array + // otherwise the existing item value is returned in *Rc + + // we return a pointer to a pointer, so that the caller can + // put anything needed at the value of the index. + // The pointer to pointer we return has to be used before + // any other operation that may change the index (insert/delete). + return (NAME_VALUE **)Rc; +} + +static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, NAME_VALUE *nv) { + (void)nv; + + if(unlikely(!dict->JudyHSArray)) return 0; + + JError_t J_Error; + int ret = JudyHSDel(&dict->JudyHSArray, (void *)name, name_len, &J_Error); + if(unlikely(ret == JERR)) { + error("DICTIONARY: Cannot delete entry with name '%s' from JudyHS, JU_ERRNO_* == %u, ID == %d", name, + JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); + return 0; + } + + // Hey, this is problematic! We need the value back, not just an int with a status! + // https://sourceforge.net/p/judy/feature-requests/23/ + + if(unlikely(ret == 0)) { + // not found in the dictionary + return 0; + } + else { + // found and deleted from the dictionary + return 1; + } +} + +static inline NAME_VALUE *hashtable_get_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { + if(unlikely(!dict->JudyHSArray)) return NULL; + + DICTIONARY_STATS_SEARCHES_PLUS1(dict); + + Pvoid_t *Rc; + Rc = JudyHSGet(dict->JudyHSArray, (void *)name, name_len); + if(likely(Rc)) { + // found in the hash table + return (NAME_VALUE *)*Rc; + } + else { + // not found in the hash table + return NULL; + } +} + +static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, const char *name, size_t name_len, NAME_VALUE *nv) { + (void)dict; + (void)name; + (void)name_len; + (void)nv; + ; +} + +#endif // DICTIONARY_WITH_JUDYHS + // ---------------------------------------------------------------------------- -// internal methods +// linked list management + +static inline void linkedlist_namevalue_link_unsafe(DICTIONARY *dict, NAME_VALUE *nv) { + if (unlikely(!dict->first_item)) { + // we are the only ones here + nv->next = NULL; + nv->prev = NULL; + dict->first_item = dict->last_item = nv; + return; + } + + if(dict->flags & DICTIONARY_FLAG_ADD_IN_FRONT) { + // add it at the beginning + nv->prev = NULL; + nv->next = dict->first_item; -static NAME_VALUE *dictionary_name_value_create_nolock(DICTIONARY *dict, const char *name, void *value, size_t value_len, uint32_t hash) { + if (likely(nv->next)) nv->next->prev = nv; + dict->first_item = nv; + } + else { + // add it at the end + nv->next = NULL; + nv->prev = dict->last_item; + + if (likely(nv->prev)) nv->prev->next = nv; + dict->last_item = nv; + } +} + +static inline void linkedlist_namevalue_unlink_unsafe(DICTIONARY *dict, NAME_VALUE *nv) { + if(nv->next) nv->next->prev = nv->prev; + if(nv->prev) nv->prev->next = nv->next; + if(dict->first_item == nv) dict->first_item = nv->next; + if(dict->last_item == nv) dict->last_item = nv->prev; +} + +// ---------------------------------------------------------------------------- +// NAME_VALUE methods + +static inline size_t namevalue_alloc_size(DICTIONARY *dict) { + return (dict->flags & DICTIONARY_FLAG_WITH_STATISTICS) ? sizeof(NAME_VALUE_WITH_STATS) : sizeof(NAME_VALUE); +} + +static inline size_t namevalue_get_namelen(DICTIONARY *dict, NAME_VALUE *nv) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { + NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; + return nvs->name_len; + } + return 0; +} +static inline size_t namevalue_get_valuelen(DICTIONARY *dict, NAME_VALUE *nv) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { + NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; + return nvs->value_len; + } + return 0; +} +static inline void namevalue_set_valuelen(DICTIONARY *dict, NAME_VALUE *nv, size_t value_len) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { + NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; + nvs->value_len = value_len; + } +} +static inline void namevalue_set_namevaluelen(DICTIONARY *dict, NAME_VALUE *nv, size_t name_len, size_t value_len) { + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { + NAME_VALUE_WITH_STATS *nvs = (NAME_VALUE_WITH_STATS *)nv; + nvs->name_len = name_len; + nvs->value_len = value_len; + } +} + +static NAME_VALUE *namevalue_create_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *value, size_t value_len) { debug(D_DICTIONARY, "Creating name value entry for name '%s'.", name); - NAME_VALUE *nv = callocz(1, sizeof(NAME_VALUE)); + size_t size = namevalue_alloc_size(dict); + NAME_VALUE *nv = mallocz(size); + size_t allocated = size; - if(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE) + namevalue_set_namevaluelen(dict, nv, name_len, value_len); + + if(likely(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE)) nv->name = (char *)name; else { - nv->name = strdupz(name); + nv->name = mallocz(name_len); + memcpy(nv->name, name, name_len); + allocated += name_len; } - nv->hash = (hash)?hash:simple_hash(nv->name); - - if(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE) + if(likely(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) nv->value = value; else { - nv->value = mallocz(value_len); - memcpy(nv->value, value, value_len); - } + if(likely(value_len)) { + if (value) { + // a value has been supplied + // copy it + nv->value = mallocz(value_len); + memcpy(nv->value, value, value_len); + } + else { + // no value has been supplied + // allocate a clear memory block + nv->value = callocz(1, value_len); + } + } + else { + // the caller want an item without any value + nv->value = NULL; + } - // index it - NETDATA_DICTIONARY_STATS_INSERTS_PLUS1(dict); - if(unlikely(avl_insert(&((dict)->values_index), (avl_t *)(nv)) != (avl_t *)nv)) - error("dictionary: INTERNAL ERROR: duplicate insertion to dictionary."); + allocated += value_len; + } - NETDATA_DICTIONARY_STATS_ENTRIES_PLUS1(dict); + DICTIONARY_STATS_ENTRIES_PLUS1(dict, allocated); return nv; } -static void dictionary_name_value_destroy_nolock(DICTIONARY *dict, NAME_VALUE *nv) { - debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", nv->name); +static void namevalue_reset_unsafe(DICTIONARY *dict, NAME_VALUE *nv, void *value, size_t value_len) { + debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", nv->name); - NETDATA_DICTIONARY_STATS_DELETES_PLUS1(dict); - if(unlikely(avl_remove(&(dict->values_index), (avl_t *)(nv)) != (avl_t *)nv)) - error("dictionary: INTERNAL ERROR: dictionary invalid removal of node."); + if(likely(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) { + debug(D_DICTIONARY, "Dictionary: linking value to '%s'", nv->name); + nv->value = value; + namevalue_set_valuelen(dict, nv, value_len); + } + else { + debug(D_DICTIONARY, "Dictionary: cloning value to '%s'", nv->name); + DICTIONARY_STATS_VALUE_RESETS_PLUS1(dict, namevalue_get_valuelen(dict, nv), value_len); + + void *old = nv->value; + void *new = mallocz(value_len); + memcpy(new, value, value_len); + nv->value = new; + namevalue_set_valuelen(dict, nv, value_len); + + debug(D_DICTIONARY, "Dictionary: freeing old value of '%s'", nv->name); + freez(old); + } +} - NETDATA_DICTIONARY_STATS_ENTRIES_MINUS1(dict); +static size_t namevalue_destroy_unsafe(DICTIONARY *dict, NAME_VALUE *nv) { + debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", nv->name); + + size_t freed = 0; - if(!(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) { - debug(D_REGISTRY, "Dictionary freeing value of '%s'", nv->name); + if(unlikely(!(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE))) { + debug(D_DICTIONARY, "Dictionary freeing value of '%s'", nv->name); freez(nv->value); + freed += namevalue_get_valuelen(dict, nv); } - if(!(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE)) { - debug(D_REGISTRY, "Dictionary freeing name '%s'", nv->name); + if(unlikely(!(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE))) { + debug(D_DICTIONARY, "Dictionary freeing name '%s'", nv->name); freez(nv->name); + freed += namevalue_get_namelen(dict, nv); } freez(nv); + freed += namevalue_alloc_size(dict); + + DICTIONARY_STATS_ENTRIES_MINUS1(dict, freed); + + return freed; } // ---------------------------------------------------------------------------- -// API - basic methods +// API - dictionary management -DICTIONARY *dictionary_create(uint8_t flags) { +DICTIONARY *dictionary_create(DICTIONARY_FLAGS flags) { debug(D_DICTIONARY, "Creating dictionary."); - DICTIONARY *dict = callocz(1, sizeof(DICTIONARY)); - - if(flags & DICTIONARY_FLAG_WITH_STATISTICS) - dict->stats = callocz(1, sizeof(struct dictionary_stats)); + if((flags & DICTIONARY_FLAG_REFERENCE_COUNTERS) && (flags & DICTIONARY_FLAG_SINGLE_THREADED)) { + error("DICTIONARY: requested reference counters on single threaded dictionary. Not adding reference counters."); + flags &= ~DICTIONARY_FLAG_REFERENCE_COUNTERS; + } - if(!(flags & DICTIONARY_FLAG_SINGLE_THREADED)) { - dict->rwlock = callocz(1, sizeof(netdata_rwlock_t)); - netdata_rwlock_init(dict->rwlock); + if(flags & DICTIONARY_FLAG_REFERENCE_COUNTERS) { + // we need statistics to allocate the extra NAME_VALUE attributes + flags |= DICTIONARY_FLAG_WITH_STATISTICS; } - avl_init(&dict->values_index, name_value_compare); + DICTIONARY *dict = callocz(1, sizeof(DICTIONARY)); + size_t allocated = sizeof(DICTIONARY); + dict->flags = flags; + dict->first_item = dict->last_item = NULL; + + allocated += dictionary_lock_init(dict); + allocated += reference_counter_init(dict); + + if(flags & DICTIONARY_FLAG_WITH_STATISTICS) { + dict->stats = callocz(1, sizeof(struct dictionary_stats)); + allocated += sizeof(struct dictionary_stats); + dict->stats->memory = allocated; + } + else + dict->stats = NULL; - return dict; + hashtable_init_unsafe(dict); + return (DICTIONARY *)dict; } -void dictionary_destroy(DICTIONARY *dict) { +size_t dictionary_destroy(DICTIONARY *dict) { debug(D_DICTIONARY, "Destroying dictionary."); - dictionary_write_lock(dict); + dictionary_lock_wrlock(dict); + + size_t freed = 0; + NAME_VALUE *nv = dict->first_item; + while (nv) { + // cache nv->next + // because we are going to free nv + NAME_VALUE *nvnext = nv->next; + freed += namevalue_destroy_unsafe(dict, nv); + nv = nvnext; + // to speed up destruction, we don't + // unlink nv from the linked-list here + } + + dict->first_item = NULL; + dict->last_item = NULL; - while(dict->values_index.root) - dictionary_name_value_destroy_nolock(dict, (NAME_VALUE *)dict->values_index.root); + // destroy the dictionary + freed += hashtable_destroy_unsafe(dict); dictionary_unlock(dict); + freed += dictionary_lock_free(dict); + freed += reference_counter_free(dict); - if(dict->stats) + if(unlikely(dict->flags & DICTIONARY_FLAG_WITH_STATISTICS)) { freez(dict->stats); - - if(dict->rwlock) { - netdata_rwlock_destroy(dict->rwlock); - freez(dict->rwlock); + dict->stats = NULL; + freed += sizeof(struct dictionary_stats); } freez(dict); + freed += sizeof(DICTIONARY); + + return freed; } // ---------------------------------------------------------------------------- +// API - items management -void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - debug(D_DICTIONARY, "SET dictionary entry with name '%s'.", name); - - uint32_t hash = simple_hash(name); +void *dictionary_set_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len) { + if(unlikely(!name || !*name)) { + error("Attempted to dictionary_set() a dictionary item without a name"); + return NULL; + } - dictionary_write_lock(dict); + size_t name_len = strlen(name) + 1; // we need the terminating null too - NAME_VALUE *nv = dictionary_name_value_index_find_nolock(dict, name, hash); - if(unlikely(!nv)) { - debug(D_DICTIONARY, "Dictionary entry with name '%s' not found. Creating a new one.", name); + debug(D_DICTIONARY, "SET dictionary entry with name '%s'.", name); - nv = dictionary_name_value_create_nolock(dict, name, value, value_len, hash); - if(unlikely(!nv)) - fatal("Cannot create name_value."); + // DISCUSSION: + // Is it better to gain a read-lock and do a hashtable_get_unsafe() + // before we write lock to do hashtable_insert_unsafe()? + // + // Probably this depends on the use case. + // For statsd for example that does dictionary_set() to update received values, + // it could be beneficial to do a get() before we insert(). + // + // But the caller has the option to do this on his/her own. + // So, let's do the fastest here and let the caller decide the flow of calls. + + NAME_VALUE *nv, **pnv = hashtable_insert_unsafe(dict, name, name_len); + if(likely(*pnv == 0)) { + // a new item added to the index + nv = *pnv = namevalue_create_unsafe(dict, name, name_len, value, value_len); + hashtable_inserted_name_value_unsafe(dict, name, name_len, nv); + linkedlist_namevalue_link_unsafe(dict, nv); + + if(dict->ins_callback) + dict->ins_callback(nv->name, nv->value, dict->ins_callback_data); } else { - debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", name); + // the item is already in the index + // so, either we will return the old one + // or overwrite the value, depending on dictionary flags - if(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE) { - debug(D_REGISTRY, "Dictionary: linking value to '%s'", name); - nv->value = value; - } - else { - debug(D_REGISTRY, "Dictionary: cloning value to '%s'", name); + nv = *pnv; + if(!(dict->flags & DICTIONARY_FLAG_DONT_OVERWRITE_VALUE)) { - // copy the new value without breaking - // any other thread accessing the same entry - void *new = mallocz(value_len), - *old = nv->value; + if(dict->del_callback) + dict->del_callback(nv->name, nv->value, dict->del_callback_data); - memcpy(new, value, value_len); - nv->value = new; + namevalue_reset_unsafe(dict, nv, value, value_len); - debug(D_REGISTRY, "Dictionary: freeing old value of '%s'", name); - freez(old); + if(dict->ins_callback) + dict->ins_callback(nv->name, nv->value, dict->ins_callback_data); } + else if(dict->conflict_callback) + dict->conflict_callback(nv->name, nv->value, value, dict->conflict_callback_data); } - dictionary_unlock(dict); - return nv->value; } -void *dictionary_get(DICTIONARY *dict, const char *name) { - debug(D_DICTIONARY, "GET dictionary entry with name '%s'.", name); - - dictionary_read_lock(dict); - NAME_VALUE *nv = dictionary_name_value_index_find_nolock(dict, name, 0); +void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len) { + dictionary_lock_wrlock(dict); + void *ret = dictionary_set_unsafe(dict, name, value, value_len); dictionary_unlock(dict); + return ret; +} +void *dictionary_get_unsafe(DICTIONARY *dict, const char *name) { + if(unlikely(!name || !*name)) { + error("Attempted to dictionary_get() without a name"); + return NULL; + } + + size_t name_len = strlen(name) + 1; // we need the terminating null too + + debug(D_DICTIONARY, "GET dictionary entry with name '%s'.", name); + + NAME_VALUE *nv = hashtable_get_unsafe(dict, name, name_len); if(unlikely(!nv)) { debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name); return NULL; @@ -229,101 +776,508 @@ void *dictionary_get(DICTIONARY *dict, const char *name) { return nv->value; } -int dictionary_del(DICTIONARY *dict, const char *name) { - int ret; +void *dictionary_get(DICTIONARY *dict, const char *name) { + dictionary_lock_rlock(dict); + void *ret = dictionary_get_unsafe(dict, name); + dictionary_unlock(dict); + return ret; +} + +int dictionary_del_unsafe(DICTIONARY *dict, const char *name) { + if(unlikely(!name || !*name)) { + error("Attempted to dictionary_det() without a name"); + return -1; + } + + size_t name_len = strlen(name) + 1; // we need the terminating null too debug(D_DICTIONARY, "DEL dictionary entry with name '%s'.", name); - dictionary_write_lock(dict); + // Unfortunately, the JudyHSDel() does not return the value of the + // item that was deleted, so we have to find it before we delete it, + // since we need to release our structures too. - NAME_VALUE *nv = dictionary_name_value_index_find_nolock(dict, name, 0); + int ret; + NAME_VALUE *nv = hashtable_get_unsafe(dict, name, name_len); if(unlikely(!nv)) { debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name); ret = -1; } else { debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name); - dictionary_name_value_destroy_nolock(dict, nv); + + if(hashtable_delete_unsafe(dict, name, name_len, nv) == 0) + error("DICTIONARY: INTERNAL ERROR: tried to delete item with name '%s' that is not in the index", name); + + if(!reference_counter_mark_deleted(dict, nv)) { + linkedlist_namevalue_unlink_unsafe(dict, nv); + + if(dict->del_callback) + dict->del_callback(nv->name, nv->value, dict->del_callback_data); + + namevalue_destroy_unsafe(dict, nv); + } ret = 0; } + return ret; +} +int dictionary_del(DICTIONARY *dict, const char *name) { + dictionary_lock_wrlock(dict); + int ret = dictionary_del_unsafe(dict, name); dictionary_unlock(dict); - return ret; } - // ---------------------------------------------------------------------------- -// API - walk through the dictionary -// the dictionary is locked for reading while this happens -// do not user other dictionary calls while walking the dictionary - deadlock! +// traversal with loop -static int dictionary_walker(avl_t *a, int (*callback)(void *entry, void *data), void *data) { - int total = 0, ret = 0; +void *dictionary_foreach_start_rw(DICTFE *dfe, DICTIONARY *dict, char rw) { + if(unlikely(!dfe || !dict)) return NULL; - if(a->avl_link[0]) { - ret = dictionary_walker(a->avl_link[0], callback, data); - if(ret < 0) return ret; - total += ret; + dfe->dict = dict; + dfe->started_ut = now_realtime_usec(); + + if(rw == 'r' || rw == 'R') + dictionary_lock_rlock(dict); + else + dictionary_lock_wrlock(dict); + + NAME_VALUE *nv = dict->first_item; + dfe->last_position_index = (void *)nv; + + if(likely(nv)) { + dfe->next_position_index = (void *)nv->next; + dfe->name = nv->name; + dfe->value = (void *)nv->value; + reference_counter_acquire(dict, nv); + } + else { + dfe->next_position_index = NULL; + dfe->name = NULL; + dfe->value = NULL; } - ret = callback(((NAME_VALUE *)a)->value, data); - if(ret < 0) return ret; - total += ret; + return dfe->value; +} + +void *dictionary_foreach_next(DICTFE *dfe) { + if(unlikely(!dfe || !dfe->dict)) return NULL; + + NAME_VALUE *nv = (NAME_VALUE *)dfe->last_position_index; + if(likely(nv)) + reference_counter_release(dfe->dict, nv); + + nv = dfe->last_position_index = dfe->next_position_index; + + if(likely(nv)) { + dfe->next_position_index = (void *)nv->next; + dfe->name = nv->name; + dfe->value = (void *)nv->value; - if(a->avl_link[1]) { - ret = dictionary_walker(a->avl_link[1], callback, data); - if (ret < 0) return ret; - total += ret; + reference_counter_acquire(dfe->dict, nv); + } + else { + dfe->next_position_index = NULL; + dfe->name = NULL; + dfe->value = NULL; } - return total; + return dfe->value; } -int dictionary_get_all(DICTIONARY *dict, int (*callback)(void *entry, void *data), void *data) { +usec_t dictionary_foreach_done(DICTFE *dfe) { + if(unlikely(!dfe || !dfe->dict)) return 0; + + NAME_VALUE *nv = (NAME_VALUE *)dfe->last_position_index; + if(nv) + reference_counter_release(dfe->dict, nv); + + dictionary_unlock((DICTIONARY *)dfe->dict); + dfe->dict = NULL; + dfe->last_position_index = NULL; + dfe->next_position_index = NULL; + dfe->name = NULL; + dfe->value = NULL; + + usec_t usec = now_realtime_usec() - dfe->started_ut; + dfe->started_ut = 0; + + return usec; +} + +// ---------------------------------------------------------------------------- +// API - walk through the dictionary +// the dictionary is locked for reading while this happens +// do not use other dictionary calls while walking the dictionary - deadlock! + +int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const char *name, void *entry, void *data), void *data) { + if(rw == 'r' || rw == 'R') + dictionary_lock_rlock(dict); + else + dictionary_lock_wrlock(dict); + + // written in such a way, that the callback can delete the active element + int ret = 0; + NAME_VALUE *nv = dict->first_item, *nv_next; + while(nv) { + nv_next = nv->next; + + reference_counter_acquire(dict, nv); + int r = callback(nv->name, nv->value, data); + reference_counter_release(dict, nv); + if(unlikely(r < 0)) { + ret = r; + break; + } - dictionary_read_lock(dict); + ret += r; - if(likely(dict->values_index.root)) - ret = dictionary_walker(dict->values_index.root, callback, data); + nv = nv_next; + } dictionary_unlock(dict); return ret; } -static int dictionary_walker_name_value(avl_t *a, int (*callback)(char *name, void *entry, void *data), void *data) { - int total = 0, ret = 0; +// ---------------------------------------------------------------------------- +// unit test - if(a->avl_link[0]) { - ret = dictionary_walker_name_value(a->avl_link[0], callback, data); - if(ret < 0) return ret; - total += ret; +static void dictionary_unittest_free_char_pp(char **pp, size_t entries) { + for(size_t i = 0; i < entries ;i++) + freez(pp[i]); + + freez(pp); +} + +static char **dictionary_unittest_generate_names(size_t entries) { + char **names = mallocz(sizeof(char *) * entries); + for(size_t i = 0; i < entries ;i++) { + char buf[25 + 1] = ""; + snprintfz(buf, 25, "name.%zu.0123456789.%zu \t !@#$%%^&*(),./[]{}\\|~`", i, entries / 2 + i); + names[i] = strdupz(buf); } + return names; +} - ret = callback(((NAME_VALUE *)a)->name, ((NAME_VALUE *)a)->value, data); - if(ret < 0) return ret; - total += ret; +static char **dictionary_unittest_generate_values(size_t entries) { + char **values = mallocz(sizeof(char *) * entries); + for(size_t i = 0; i < entries ;i++) { + char buf[25 + 1] = ""; + snprintfz(buf, 25, "value-%zu-0987654321.%zu%%^&*(),. \t !@#$/[]{}\\|~`", i, entries / 2 + i); + values[i] = strdupz(buf); + } + return values; +} - if(a->avl_link[1]) { - ret = dictionary_walker_name_value(a->avl_link[1], callback, data); - if (ret < 0) return ret; - total += ret; +static size_t dictionary_unittest_set_clone(DICTIONARY *dict, char **names, char **values, size_t entries) { + size_t errors = 0; + for(size_t i = 0; i < entries ;i++) { + size_t vallen = strlen(values[i]) + 1; + char *val = (char *)dictionary_set(dict, names[i], values[i], vallen); + if(val == values[i]) { fprintf(stderr, ">>> %s() returns reference to value\n", __FUNCTION__); errors++; } + if(!val || memcmp(val, values[i], vallen) != 0) { fprintf(stderr, ">>> %s() returns invalid value\n", __FUNCTION__); errors++; } } + return errors; +} - return total; +static size_t dictionary_unittest_set_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries) { + size_t errors = 0; + for(size_t i = 0; i < entries ;i++) { + size_t vallen = strlen(values[i]) + 1; + char *val = (char *)dictionary_set(dict, names[i], values[i], vallen); + if(val != values[i]) { fprintf(stderr, ">>> %s() returns invalid pointer to value\n", __FUNCTION__); errors++; } + } + return errors; } -int dictionary_get_all_name_value(DICTIONARY *dict, int (*callback)(char *name, void *entry, void *data), void *data) { - int ret = 0; +static size_t dictionary_unittest_get_clone(DICTIONARY *dict, char **names, char **values, size_t entries) { + size_t errors = 0; + for(size_t i = 0; i < entries ;i++) { + size_t vallen = strlen(values[i]) + 1; + char *val = (char *)dictionary_get(dict, names[i]); + if(val == values[i]) { fprintf(stderr, ">>> %s() returns reference to value\n", __FUNCTION__); errors++; } + if(!val || memcmp(val, values[i], vallen) != 0) { fprintf(stderr, ">>> %s() returns invalid value\n", __FUNCTION__); errors++; } + } + return errors; +} - dictionary_read_lock(dict); +static size_t dictionary_unittest_get_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries) { + size_t errors = 0; + for(size_t i = 0; i < entries ;i++) { + char *val = (char *)dictionary_get(dict, names[i]); + if(val != values[i]) { fprintf(stderr, ">>> %s() returns invalid pointer to value\n", __FUNCTION__); errors++; } + } + return errors; +} - if(likely(dict->values_index.root)) - ret = dictionary_walker_name_value(dict->values_index.root, callback, data); +static size_t dictionary_unittest_get_nonexisting(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)names; + size_t errors = 0; + for(size_t i = 0; i < entries ;i++) { + char *val = (char *)dictionary_get(dict, values[i]); + if(val) { fprintf(stderr, ">>> %s() returns non-existing item\n", __FUNCTION__); errors++; } + } + return errors; +} - dictionary_unlock(dict); +static size_t dictionary_unittest_del_nonexisting(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)names; + size_t errors = 0; + for(size_t i = 0; i < entries ;i++) { + int ret = dictionary_del(dict, values[i]); + if(ret != -1) { fprintf(stderr, ">>> %s() deleted non-existing item\n", __FUNCTION__); errors++; } + } + return errors; +} - return ret; +static size_t dictionary_unittest_del_existing(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)values; + size_t errors = 0; + + size_t forward_from = 0, forward_to = entries / 3; + size_t middle_from = forward_to, middle_to = entries * 2 / 3; + size_t backward_from = middle_to, backward_to = entries; + + for(size_t i = forward_from; i < forward_to ;i++) { + int ret = dictionary_del(dict, names[i]); + if(ret == -1) { fprintf(stderr, ">>> %s() didn't delete (forward) existing item\n", __FUNCTION__); errors++; } + } + + for(size_t i = middle_to - 1; i >= middle_from ;i--) { + int ret = dictionary_del(dict, names[i]); + if(ret == -1) { fprintf(stderr, ">>> %s() didn't delete (middle) existing item\n", __FUNCTION__); errors++; } + } + + for(size_t i = backward_to - 1; i >= backward_from ;i--) { + int ret = dictionary_del(dict, names[i]); + if(ret == -1) { fprintf(stderr, ">>> %s() didn't delete (backward) existing item\n", __FUNCTION__); errors++; } + } + + return errors; +} + +static size_t dictionary_unittest_reset_clone(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)values; + // set the name as value too + size_t errors = 0; + for(size_t i = 0; i < entries ;i++) { + size_t vallen = strlen(names[i]) + 1; + char *val = (char *)dictionary_set(dict, names[i], names[i], vallen); + if(val == names[i]) { fprintf(stderr, ">>> %s() returns reference to value\n", __FUNCTION__); errors++; } + if(!val || memcmp(val, names[i], vallen) != 0) { fprintf(stderr, ">>> %s() returns invalid value\n", __FUNCTION__); errors++; } + } + return errors; +} + +static size_t dictionary_unittest_reset_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)values; + // set the name as value too + size_t errors = 0; + for(size_t i = 0; i < entries ;i++) { + size_t vallen = strlen(names[i]) + 1; + char *val = (char *)dictionary_set(dict, names[i], names[i], vallen); + if(val != names[i]) { fprintf(stderr, ">>> %s() returns invalid pointer to value\n", __FUNCTION__); errors++; } + if(!val) { fprintf(stderr, ">>> %s() returns invalid value\n", __FUNCTION__); errors++; } + } + return errors; +} + +static size_t dictionary_unittest_reset_dont_overwrite_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries) { + // set the name as value too + size_t errors = 0; + for(size_t i = 0; i < entries ;i++) { + size_t vallen = strlen(names[i]) + 1; + char *val = (char *)dictionary_set(dict, names[i], names[i], vallen); + if(val != values[i]) { fprintf(stderr, ">>> %s() returns invalid pointer to value\n", __FUNCTION__); errors++; } + } + return errors; +} + +static int dictionary_unittest_walkthrough_callback(const char *name, void *value, void *data) { + (void)name; + (void)value; + (void)data; + return 1; +} + +static size_t dictionary_unittest_walkthrough(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)names; + (void)values; + int sum = dictionary_walkthrough_read(dict, dictionary_unittest_walkthrough_callback, NULL); + if(sum < (int)entries) return entries - sum; + else return sum - entries; +} + +static int dictionary_unittest_walkthrough_delete_this_callback(const char *name, void *value, void *data) { + (void)value; + + if(dictionary_del_having_write_lock((DICTIONARY *)data, name) == -1) + return 0; + + return 1; +} + +static size_t dictionary_unittest_walkthrough_delete_this(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)names; + (void)values; + int sum = dictionary_walkthrough_write(dict, dictionary_unittest_walkthrough_delete_this_callback, dict); + if(sum < (int)entries) return entries - sum; + else return sum - entries; +} + +static int dictionary_unittest_walkthrough_stop_callback(const char *name, void *value, void *data) { + (void)name; + (void)value; + (void)data; + return -1; +} + +static size_t dictionary_unittest_walkthrough_stop(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)names; + (void)values; + (void)entries; + int sum = dictionary_walkthrough_read(dict, dictionary_unittest_walkthrough_stop_callback, NULL); + if(sum != -1) return 1; + return 0; +} + +static size_t dictionary_unittest_foreach(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)names; + (void)values; + (void)entries; + size_t count = 0; + char *item; + dfe_start_read(dict, item) + count++; + dfe_done(item); + + if(count > entries) return count - entries; + return entries - count; +} + +static size_t dictionary_unittest_foreach_delete_this(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)names; + (void)values; + (void)entries; + size_t count = 0; + char *item; + dfe_start_write(dict, item) + if(dictionary_del_having_write_lock(dict, item_name) != -1) count++; + dfe_done(item); + + if(count > entries) return count - entries; + return entries - count; +} + +static size_t dictionary_unittest_destroy(DICTIONARY *dict, char **names, char **values, size_t entries) { + (void)names; + (void)values; + (void)entries; + size_t bytes = dictionary_destroy(dict); + fprintf(stderr, " %s() freed %zu bytes,", __FUNCTION__, bytes); + return 0; +} + +static usec_t dictionary_unittest_run_and_measure_time(DICTIONARY *dict, char *message, char **names, char **values, size_t entries, size_t *errors, size_t (*callback)(DICTIONARY *dict, char **names, char **values, size_t entries)) { + fprintf(stderr, "%-40s... ", message); + + usec_t started = now_realtime_usec(); + size_t errs = callback(dict, names, values, entries); + usec_t ended = now_realtime_usec(); + usec_t dt = ended - started; + + if(callback == dictionary_unittest_destroy) dict = NULL; + + fprintf(stderr, " %zu errors, %zu items in dictionary, %llu usec \n", errs, dict? dictionary_stats_entries(dict):0, dt); + *errors += errs; + return dt; +} + +void dictionary_unittest_clone(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) { + dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, errors, dictionary_unittest_set_clone); + dictionary_unittest_run_and_measure_time(dict, "getting entries", names, values, entries, errors, dictionary_unittest_get_clone); + dictionary_unittest_run_and_measure_time(dict, "getting non-existing entries", names, values, entries, errors, dictionary_unittest_get_nonexisting); + dictionary_unittest_run_and_measure_time(dict, "resetting entries", names, values, entries, errors, dictionary_unittest_reset_clone); + dictionary_unittest_run_and_measure_time(dict, "deleting non-existing entries", names, values, entries, errors, dictionary_unittest_del_nonexisting); + dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop", names, values, entries, errors, dictionary_unittest_foreach); + dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback", names, values, entries, errors, dictionary_unittest_walkthrough); + dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback stop", names, values, entries, errors, dictionary_unittest_walkthrough_stop); + dictionary_unittest_run_and_measure_time(dict, "deleting existing entries", names, values, entries, errors, dictionary_unittest_del_existing); + dictionary_unittest_run_and_measure_time(dict, "walking through empty", names, values, 0, errors, dictionary_unittest_walkthrough); + dictionary_unittest_run_and_measure_time(dict, "traverse foreach empty", names, values, 0, errors, dictionary_unittest_foreach); + dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, errors, dictionary_unittest_destroy); +} + +void dictionary_unittest_nonclone(DICTIONARY *dict, char **names, char **values, size_t entries, size_t *errors) { + dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, errors, dictionary_unittest_set_nonclone); + dictionary_unittest_run_and_measure_time(dict, "getting entries", names, values, entries, errors, dictionary_unittest_get_nonclone); + dictionary_unittest_run_and_measure_time(dict, "getting non-existing entries", names, values, entries, errors, dictionary_unittest_get_nonexisting); + dictionary_unittest_run_and_measure_time(dict, "resetting entries", names, values, entries, errors, dictionary_unittest_reset_nonclone); + dictionary_unittest_run_and_measure_time(dict, "deleting non-existing entries", names, values, entries, errors, dictionary_unittest_del_nonexisting); + dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop", names, values, entries, errors, dictionary_unittest_foreach); + dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback", names, values, entries, errors, dictionary_unittest_walkthrough); + dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback stop", names, values, entries, errors, dictionary_unittest_walkthrough_stop); + dictionary_unittest_run_and_measure_time(dict, "deleting existing entries", names, values, entries, errors, dictionary_unittest_del_existing); + dictionary_unittest_run_and_measure_time(dict, "walking through empty", names, values, 0, errors, dictionary_unittest_walkthrough); + dictionary_unittest_run_and_measure_time(dict, "traverse foreach empty", names, values, 0, errors, dictionary_unittest_foreach); + dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, errors, dictionary_unittest_destroy); +} + +int dictionary_unittest(size_t entries) { + if(entries < 10) entries = 10; + + DICTIONARY *dict; + size_t errors = 0; + + fprintf(stderr, "Generating %zu names and values...\n", entries); + char **names = dictionary_unittest_generate_names(entries); + char **values = dictionary_unittest_generate_values(entries); + + fprintf(stderr, "\nCreating dictionary single threaded, clone, %zu items\n", entries); + dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_WITH_STATISTICS); + dictionary_unittest_clone(dict, names, values, entries, &errors); + + fprintf(stderr, "\nCreating dictionary multi threaded, clone, %zu items\n", entries); + dict = dictionary_create(DICTIONARY_FLAG_WITH_STATISTICS); + dictionary_unittest_clone(dict, names, values, entries, &errors); + + fprintf(stderr, "\nCreating dictionary single threaded, non-clone, add-in-front options, %zu items\n", entries); + dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_WITH_STATISTICS|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_ADD_IN_FRONT); + dictionary_unittest_nonclone(dict, names, values, entries, &errors); + + fprintf(stderr, "\nCreating dictionary multi threaded, non-clone, add-in-front options, %zu items\n", entries); + dict = dictionary_create(DICTIONARY_FLAG_WITH_STATISTICS|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_ADD_IN_FRONT); + dictionary_unittest_nonclone(dict, names, values, entries, &errors); + + fprintf(stderr, "\nCreating dictionary single-threaded, non-clone, don't overwrite options, %zu items\n", entries); + dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_WITH_STATISTICS|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone); + dictionary_unittest_run_and_measure_time(dict, "resetting non-overwrite entries", names, values, entries, &errors, dictionary_unittest_reset_dont_overwrite_nonclone); + dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop", names, values, entries, &errors, dictionary_unittest_foreach); + dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback", names, values, entries, &errors, dictionary_unittest_walkthrough); + dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback stop", names, values, entries, &errors, dictionary_unittest_walkthrough_stop); + dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy); + + fprintf(stderr, "\nCreating dictionary multi-threaded, non-clone, don't overwrite options, %zu items\n", entries); + dict = dictionary_create(DICTIONARY_FLAG_WITH_STATISTICS|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone); + dictionary_unittest_run_and_measure_time(dict, "walkthrough write delete this", names, values, entries, &errors, dictionary_unittest_walkthrough_delete_this); + dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, &errors, dictionary_unittest_destroy); + + fprintf(stderr, "\nCreating dictionary multi-threaded, non-clone, don't overwrite options, %zu items\n", entries); + dict = dictionary_create(DICTIONARY_FLAG_WITH_STATISTICS|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone); + dictionary_unittest_run_and_measure_time(dict, "foreach write delete this", names, values, entries, &errors, dictionary_unittest_foreach_delete_this); + dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop empty", names, values, 0, &errors, dictionary_unittest_foreach); + dictionary_unittest_run_and_measure_time(dict, "walkthrough read callback empty", names, values, 0, &errors, dictionary_unittest_walkthrough); + dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, &errors, dictionary_unittest_destroy); + + dictionary_unittest_free_char_pp(names, entries); + dictionary_unittest_free_char_pp(values, entries); + + fprintf(stderr, "\n%zu errors found\n", errors); + return (int)errors; } 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 */ |