Dictionary with JudyHS and double linked list (#13032)

* dictionary internals isolation

* more dictionary cleanups

* added unit test

* we should use DICT internally

* disable cups in cmake

* implement DICTIONARY with Judy arrays

* operational JUDY implementation

* JUDY cleanup

* JUDY summary added

* JudyHS implementation with double linked list

* test negative searches too

* optimize destruction

* optimize set to insert first without lookup

* updated stats

* code cleanup; better organization; updated info

* more code cleanup and commenting

* more cleanup, renames and comments

* fix rename

* more cleanups

* use Judy.h from system paths

* added foreach traversal; added flag to add item in front; isolated locks to their own functions; destruction returns the number of bytes freed

* more comments; flags are now 16-bit

* completed unittesting

* addressed comments and added reference counters maintainance

* added unittest in main; tested removal of items in front, back and middle

* added read/write walkthrough and foreach; allowed walkthrough and foreach in write mode to delete the current element (used by cups.plugin); referenced counters removed from the API

* DICTFE.name should be const too

* added API calls for exposing all statistics

* dictionary flags as enum and reference counters as atomic operations

* more comments; improved error handling at unit tests

* added functions to allow unsafe access while traversing the dictionary with locks in place

* check for libcups in cmake

* added delete callback; implemented statsd with this dictionary

* added missing dfe_done()

* added alternative implementation with AVL

* added documentation

* added comments and warning about AVL

* dictionary walktrhough on new code

* simplified foreach; updated docs

* updated docs

* AVL is much faster without hashes

* AVL should follow DBENGINE

3 files changed, 1467 insertions, 199 deletions

diff --git a/libnetdata/dictionary/README.md b/libnetdata/dictionary/README.md
index 6049c7f66d..25d654d718 100644
--- a/libnetdata/dictionary/README.md
+++ b/libnetdata/dictionary/README.md
@@ -2,4 +2,205 @@
 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, two callback functions can be registered:
+
+   1.`dictionary_register_insert_callback()` that will be called just after the insertion of an item to the dictionary (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 (but while the dictionary is write-locked - if locking is enabled).
+
+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 320d348163..bc1e872cbd 100644
--- a/libnetdata/dictionary/dictionary.c
+++ b/libnetdata/dictionary/dictionary.c
@@ -1,226 +1,754 @@
 // 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;
+
+    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;
+}
+
 // ----------------------------------------------------------------------------
-// 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;
+}
+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;
 }
-static inline void NETDATA_DICTIONARY_STATS_SEARCHES_PLUS1(DICTIONARY *dict) {
-    if(likely(dict->stats))
+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;
+    }
 
-static NAME_VALUE *dictionary_name_value_create_nolock(DICTIONARY *dict, const char *name, void *value, size_t value_len, uint32_t hash) {
+    if(dict->flags & DICTIONARY_FLAG_ADD_IN_FRONT) {
+        // add it at the beginning
+        nv->prev = NULL;
+        nv->next = dict->first_item;
+
+        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) {
-