From 8d4f58e49b9dc7d3545651023a36729de773ad86 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Mon, 6 May 2024 03:22:31 +0200 Subject: Adding upstream version 1.12.0. Signed-off-by: Daniel Baumann --- libnetdata/dictionary/Makefile.am | 9 + libnetdata/dictionary/README.md | 2 + libnetdata/dictionary/dictionary.c | 329 +++++++++++++++++++++++++++++++++++++ libnetdata/dictionary/dictionary.h | 49 ++++++ 4 files changed, 389 insertions(+) create mode 100644 libnetdata/dictionary/Makefile.am create mode 100644 libnetdata/dictionary/README.md create mode 100644 libnetdata/dictionary/dictionary.c create mode 100644 libnetdata/dictionary/dictionary.h (limited to 'libnetdata/dictionary') diff --git a/libnetdata/dictionary/Makefile.am b/libnetdata/dictionary/Makefile.am new file mode 100644 index 0000000..1cb69ed --- /dev/null +++ b/libnetdata/dictionary/Makefile.am @@ -0,0 +1,9 @@ +# SPDX-License-Identifier: GPL-3.0-or-later + +AUTOMAKE_OPTIONS = subdir-objects +MAINTAINERCLEANFILES = $(srcdir)/Makefile.in + + +dist_noinst_DATA = \ + README.md \ + $(NULL) diff --git a/libnetdata/dictionary/README.md b/libnetdata/dictionary/README.md new file mode 100644 index 0000000..9c70522 --- /dev/null +++ b/libnetdata/dictionary/README.md @@ -0,0 +1,2 @@ + +[![analytics](https://www.google-analytics.com/collect?v=1&aip=1&t=pageview&_s=1&ds=github&dr=https%3A%2F%2Fgithub.com%2Fnetdata%2Fnetdata&dl=https%3A%2F%2Fmy-netdata.io%2Fgithub%2Flibnetdata%2Fdictionary%2FREADME&_u=MAC~&cid=5792dfd7-8dc4-476b-af31-da2fdb9f93d2&tid=UA-64295674-3)]() diff --git a/libnetdata/dictionary/dictionary.c b/libnetdata/dictionary/dictionary.c new file mode 100644 index 0000000..cfcf1fb --- /dev/null +++ b/libnetdata/dictionary/dictionary.c @@ -0,0 +1,329 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "../libnetdata.h" + +// ---------------------------------------------------------------------------- +// dictionary statistics + +static inline void NETDATA_DICTIONARY_STATS_INSERTS_PLUS1(DICTIONARY *dict) { + if(likely(dict->stats)) + dict->stats->inserts++; +} +static inline void NETDATA_DICTIONARY_STATS_DELETES_PLUS1(DICTIONARY *dict) { + if(likely(dict->stats)) + dict->stats->deletes++; +} +static inline void NETDATA_DICTIONARY_STATS_SEARCHES_PLUS1(DICTIONARY *dict) { + if(likely(dict->stats)) + dict->stats->searches++; +} +static inline void NETDATA_DICTIONARY_STATS_ENTRIES_PLUS1(DICTIONARY *dict) { + if(likely(dict->stats)) + dict->stats->entries++; +} +static inline void NETDATA_DICTIONARY_STATS_ENTRIES_MINUS1(DICTIONARY *dict) { + if(likely(dict->stats)) + dict->stats->entries--; +} + + +// ---------------------------------------------------------------------------- +// dictionary locks + +static inline void dictionary_read_lock(DICTIONARY *dict) { + if(likely(dict->rwlock)) { + // debug(D_DICTIONARY, "Dictionary READ lock"); + netdata_rwlock_rdlock(dict->rwlock); + } +} + +static inline void dictionary_write_lock(DICTIONARY *dict) { + if(likely(dict->rwlock)) { + // debug(D_DICTIONARY, "Dictionary WRITE lock"); + netdata_rwlock_wrlock(dict->rwlock); + } +} + +static inline void dictionary_unlock(DICTIONARY *dict) { + if(likely(dict->rwlock)) { + // debug(D_DICTIONARY, "Dictionary UNLOCK lock"); + netdata_rwlock_unlock(dict->rwlock); + } +} + + +// ---------------------------------------------------------------------------- +// avl index + +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); +} + +static inline NAME_VALUE *dictionary_name_value_index_find_nolock(DICTIONARY *dict, const char *name, uint32_t hash) { + 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 *) &tmp); +} + +// ---------------------------------------------------------------------------- +// internal methods + +static NAME_VALUE *dictionary_name_value_create_nolock(DICTIONARY *dict, const char *name, void *value, size_t value_len, uint32_t hash) { + debug(D_DICTIONARY, "Creating name value entry for name '%s'.", name); + + NAME_VALUE *nv = callocz(1, sizeof(NAME_VALUE)); + + if(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE) + nv->name = (char *)name; + else { + nv->name = strdupz(name); + } + + nv->hash = (hash)?hash:simple_hash(nv->name); + + if(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE) + nv->value = value; + else { + nv->value = mallocz(value_len); + memcpy(nv->value, value, value_len); + } + + // index it + NETDATA_DICTIONARY_STATS_INSERTS_PLUS1(dict); + if(unlikely(avl_insert(&((dict)->values_index), (avl *)(nv)) != (avl *)nv)) + error("dictionary: INTERNAL ERROR: duplicate insertion to dictionary."); + + NETDATA_DICTIONARY_STATS_ENTRIES_PLUS1(dict); + + 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); + + NETDATA_DICTIONARY_STATS_DELETES_PLUS1(dict); + if(unlikely(avl_remove(&(dict->values_index), (avl *)(nv)) != (avl *)nv)) + error("dictionary: INTERNAL ERROR: dictionary invalid removal of node."); + + NETDATA_DICTIONARY_STATS_ENTRIES_MINUS1(dict); + + if(!(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) { + debug(D_REGISTRY, "Dictionary freeing value of '%s'", nv->name); + freez(nv->value); + } + + if(!(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE)) { + debug(D_REGISTRY, "Dictionary freeing name '%s'", nv->name); + freez(nv->name); + } + + freez(nv); +} + +// ---------------------------------------------------------------------------- +// API - basic methods + +DICTIONARY *dictionary_create(uint8_t 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_SINGLE_THREADED)) { + dict->rwlock = callocz(1, sizeof(netdata_rwlock_t)); + netdata_rwlock_init(dict->rwlock); + } + + avl_init(&dict->values_index, name_value_compare); + dict->flags = flags; + + return dict; +} + +void dictionary_destroy(DICTIONARY *dict) { + debug(D_DICTIONARY, "Destroying dictionary."); + + dictionary_write_lock(dict); + + while(dict->values_index.root) + dictionary_name_value_destroy_nolock(dict, (NAME_VALUE *)dict->values_index.root); + + dictionary_unlock(dict); + + if(dict->stats) + freez(dict->stats); + + if(dict->rwlock) { + netdata_rwlock_destroy(dict->rwlock); + freez(dict->rwlock); + } + + freez(dict); +} + +// ---------------------------------------------------------------------------- + +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); + + dictionary_write_lock(dict); + + 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); + + nv = dictionary_name_value_create_nolock(dict, name, value, value_len, hash); + if(unlikely(!nv)) + fatal("Cannot create name_value."); + } + else { + debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", name); + + 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); + + // copy the new value without breaking + // any other thread accessing the same entry + void *new = mallocz(value_len), + *old = nv->value; + + memcpy(new, value, value_len); + nv->value = new; + + debug(D_REGISTRY, "Dictionary: freeing old value of '%s'", name); + freez(old); + } + } + + 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); + dictionary_unlock(dict); + + if(unlikely(!nv)) { + debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name); + return NULL; + } + + debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name); + return nv->value; +} + +int dictionary_del(DICTIONARY *dict, const char *name) { + int ret; + + debug(D_DICTIONARY, "DEL dictionary entry with name '%s'.", name); + + dictionary_write_lock(dict); + + NAME_VALUE *nv = dictionary_name_value_index_find_nolock(dict, name, 0); + 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); + ret = 0; + } + + 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! + +static int dictionary_walker(avl *a, int (*callback)(void *entry, void *data), void *data) { + int total = 0, ret = 0; + + if(a->avl_link[0]) { + ret = dictionary_walker(a->avl_link[0], callback, data); + if(ret < 0) return ret; + total += ret; + } + + ret = callback(((NAME_VALUE *)a)->value, data); + if(ret < 0) return ret; + total += ret; + + if(a->avl_link[1]) { + ret = dictionary_walker(a->avl_link[1], callback, data); + if (ret < 0) return ret; + total += ret; + } + + return total; +} + +int dictionary_get_all(DICTIONARY *dict, int (*callback)(void *entry, void *data), void *data) { + int ret = 0; + + dictionary_read_lock(dict); + + if(likely(dict->values_index.root)) + ret = dictionary_walker(dict->values_index.root, callback, data); + + dictionary_unlock(dict); + + return ret; +} + +static int dictionary_walker_name_value(avl *a, int (*callback)(char *name, void *entry, void *data), void *data) { + int total = 0, ret = 0; + + if(a->avl_link[0]) { + ret = dictionary_walker_name_value(a->avl_link[0], callback, data); + if(ret < 0) return ret; + total += ret; + } + + ret = callback(((NAME_VALUE *)a)->name, ((NAME_VALUE *)a)->value, data); + if(ret < 0) return ret; + total += ret; + + if(a->avl_link[1]) { + ret = dictionary_walker_name_value(a->avl_link[1], callback, data); + if (ret < 0) return ret; + total += ret; + } + + return total; +} + +int dictionary_get_all_name_value(DICTIONARY *dict, int (*callback)(char *name, void *entry, void *data), void *data) { + int ret = 0; + + dictionary_read_lock(dict); + + if(likely(dict->values_index.root)) + ret = dictionary_walker_name_value(dict->values_index.root, callback, data); + + dictionary_unlock(dict); + + return ret; +} diff --git a/libnetdata/dictionary/dictionary.h b/libnetdata/dictionary/dictionary.h new file mode 100644 index 0000000..9be261e --- /dev/null +++ b/libnetdata/dictionary/dictionary.h @@ -0,0 +1,49 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef NETDATA_DICTIONARY_H +#define NETDATA_DICTIONARY_H 1 + +#include "../libnetdata.h" + +struct dictionary_stats { + unsigned long long inserts; + unsigned long long deletes; + unsigned long long searches; + unsigned long long entries; +}; + +typedef struct name_value { + avl avl; // the index - this has to be first! + + uint32_t hash; // a simple hash to speed up searching + // we first compare hashes, and only if the hashes are equal we do string comparisons + + char *name; + void *value; +} NAME_VALUE; + +typedef struct dictionary { + avl_tree values_index; + + uint8_t flags; + + struct dictionary_stats *stats; + netdata_rwlock_t *rwlock; +} DICTIONARY; + +#define DICTIONARY_FLAG_DEFAULT 0x00000000 +#define DICTIONARY_FLAG_SINGLE_THREADED 0x00000001 +#define DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE 0x00000002 +#define DICTIONARY_FLAG_NAME_LINK_DONT_CLONE 0x00000004 +#define DICTIONARY_FLAG_WITH_STATISTICS 0x00000008 + +extern DICTIONARY *dictionary_create(uint8_t flags); +extern void dictionary_destroy(DICTIONARY *dict); +extern void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len) NEVERNULL; +extern void *dictionary_get(DICTIONARY *dict, const char *name); +extern int dictionary_del(DICTIONARY *dict, const char *name); + +extern int dictionary_get_all(DICTIONARY *dict, int (*callback)(void *entry, void *d), void *data); +extern int dictionary_get_all_name_value(DICTIONARY *dict, int (*callback)(char *name, void *entry, void *d), void *data); + +#endif /* NETDATA_DICTIONARY_H */ -- cgit v1.2.3