// 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