diff options
Diffstat (limited to 'libnetdata/dictionary/dictionary.c')
| -rw-r--r-- | libnetdata/dictionary/dictionary.c | 1264 |
1 files changed, 1109 insertions, 155 deletions
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; } |