From be1c7e50e1e8809ea56f2c9d472eccd8ffd73a97 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 04:57:58 +0200 Subject: Adding upstream version 1.44.3. Signed-off-by: Daniel Baumann --- libnetdata/avl/Makefile.am | 8 + libnetdata/avl/README.md | 21 +++ libnetdata/avl/avl.c | 405 +++++++++++++++++++++++++++++++++++++++++++++ libnetdata/avl/avl.h | 86 ++++++++++ 4 files changed, 520 insertions(+) create mode 100644 libnetdata/avl/Makefile.am create mode 100644 libnetdata/avl/README.md create mode 100644 libnetdata/avl/avl.c create mode 100644 libnetdata/avl/avl.h (limited to 'libnetdata/avl') diff --git a/libnetdata/avl/Makefile.am b/libnetdata/avl/Makefile.am new file mode 100644 index 00000000..161784b8 --- /dev/null +++ b/libnetdata/avl/Makefile.am @@ -0,0 +1,8 @@ +# 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/avl/README.md b/libnetdata/avl/README.md new file mode 100644 index 00000000..94c0f634 --- /dev/null +++ b/libnetdata/avl/README.md @@ -0,0 +1,21 @@ + + +# AVL + +AVL is a library indexing objects in B-Trees. + +`avl_insert()`, `avl_remove()` and `avl_search()` are adaptations +of the AVL algorithm found in `libavl` v2.0.3, so that they do not +use any memory allocations and their memory footprint is optimized +(by eliminating non-necessary data members). + +In addition to the above, this version of AVL, provides versions using locks +and traversal functions. + diff --git a/libnetdata/avl/avl.c b/libnetdata/avl/avl.c new file mode 100644 index 00000000..eef4c311 --- /dev/null +++ b/libnetdata/avl/avl.c @@ -0,0 +1,405 @@ +// SPDX-License-Identifier: LGPL-3.0-or-later + +#include "../libnetdata.h" + +/* ------------------------------------------------------------------------- */ +/* + * avl_insert(), avl_remove() and avl_search() + * are adaptations (by Costa Tsaousis) of the AVL algorithm found in libavl + * v2.0.3, so that they do not use any memory allocations and their memory + * footprint is optimized (by eliminating non-necessary data members). + * + * libavl - library for manipulation of binary trees. + * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004 Free Software + * Foundation, Inc. +*/ + + +/* Search |tree| for an item matching |item|, and return it if found. + Otherwise return |NULL|. */ +avl_t *avl_search(avl_tree_type *tree, avl_t *item) { + avl_t *p; + + // assert (tree != NULL && item != NULL); + + for (p = tree->root; p != NULL; ) { + int cmp = tree->compar(item, p); + + if (cmp < 0) + p = p->avl_link[0]; + else if (cmp > 0) + p = p->avl_link[1]; + else /* |cmp == 0| */ + return p; + } + + return NULL; +} + +/* Inserts |item| into |tree| and returns a pointer to |item|'s address. + If a duplicate item is found in the tree, + returns a pointer to the duplicate without inserting |item|. + */ +avl_t *avl_insert(avl_tree_type *tree, avl_t *item) { + avl_t *y, *z; /* Top node to update balance factor, and parent. */ + avl_t *p, *q; /* Iterator, and parent. */ + avl_t *n; /* Newly inserted node. */ + avl_t *w; /* New root of rebalanced subtree. */ + unsigned char dir; /* Direction to descend. */ + + unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */ + int k = 0; /* Number of cached results. */ + + // assert(tree != NULL && item != NULL); + + z = (avl_t *) &tree->root; + y = tree->root; + dir = 0; + for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) { + int cmp = tree->compar(item, p); + if (cmp == 0) + return p; + + if (p->avl_balance != 0) + z = q, y = p, k = 0; + da[k++] = dir = (unsigned char)(cmp > 0); + } + + n = q->avl_link[dir] = item; + + // tree->avl_count++; + n->avl_link[0] = n->avl_link[1] = NULL; + n->avl_balance = 0; + if (y == NULL) return n; + + for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++) + if (da[k] == 0) + p->avl_balance--; + else + p->avl_balance++; + + if (y->avl_balance == -2) { + avl_t *x = y->avl_link[0]; + if (x->avl_balance == -1) { + w = x; + y->avl_link[0] = x->avl_link[1]; + x->avl_link[1] = y; + x->avl_balance = y->avl_balance = 0; + } + else { + // assert (x->avl_balance == +1); + w = x->avl_link[1]; + x->avl_link[1] = w->avl_link[0]; + w->avl_link[0] = x; + y->avl_link[0] = w->avl_link[1]; + w->avl_link[1] = y; + if (w->avl_balance == -1) + x->avl_balance = 0, y->avl_balance = +1; + else if (w->avl_balance == 0) + x->avl_balance = y->avl_balance = 0; + else /* |w->avl_balance == +1| */ + x->avl_balance = -1, y->avl_balance = 0; + w->avl_balance = 0; + } + } + else if (y->avl_balance == +2) { + avl_t *x = y->avl_link[1]; + if (x->avl_balance == +1) { + w = x; + y->avl_link[1] = x->avl_link[0]; + x->avl_link[0] = y; + x->avl_balance = y->avl_balance = 0; + } + else { + // assert (x->avl_balance == -1); + w = x->avl_link[0]; + x->avl_link[0] = w->avl_link[1]; + w->avl_link[1] = x; + y->avl_link[1] = w->avl_link[0]; + w->avl_link[0] = y; + if (w->avl_balance == +1) + x->avl_balance = 0, y->avl_balance = -1; + else if (w->avl_balance == 0) + x->avl_balance = y->avl_balance = 0; + else /* |w->avl_balance == -1| */ + x->avl_balance = +1, y->avl_balance = 0; + w->avl_balance = 0; + } + } + else return n; + + z->avl_link[y != z->avl_link[0]] = w; + + // tree->avl_generation++; + return n; +} + +/* Deletes from |tree| and returns an item matching |item|. + Returns a null pointer if no matching item found. */ +avl_t *avl_remove(avl_tree_type *tree, avl_t *item) { + /* Stack of nodes. */ + avl_t *pa[AVL_MAX_HEIGHT]; /* Nodes. */ + unsigned char da[AVL_MAX_HEIGHT]; /* |avl_link[]| indexes. */ + int k; /* Stack pointer. */ + + avl_t *p; /* Traverses tree to find node to delete. */ + int cmp; /* Result of comparison between |item| and |p|. */ + + // assert (tree != NULL && item != NULL); + + k = 0; + p = (avl_t *) &tree->root; + for(cmp = -1; cmp != 0; cmp = tree->compar(item, p)) { + unsigned char dir = (unsigned char)(cmp > 0); + + pa[k] = p; + da[k++] = dir; + + p = p->avl_link[dir]; + if(p == NULL) return NULL; + } + + item = p; + + if (p->avl_link[1] == NULL) + pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0]; + else { + avl_t *r = p->avl_link[1]; + if (r->avl_link[0] == NULL) { + r->avl_link[0] = p->avl_link[0]; + r->avl_balance = p->avl_balance; + pa[k - 1]->avl_link[da[k - 1]] = r; + da[k] = 1; + pa[k++] = r; + } + else { + avl_t *s; + int j = k++; + + for (;;) { + da[k] = 0; + pa[k++] = r; + s = r->avl_link[0]; + if (s->avl_link[0] == NULL) break; + + r = s; + } + + s->avl_link[0] = p->avl_link[0]; + r->avl_link[0] = s->avl_link[1]; + s->avl_link[1] = p->avl_link[1]; + s->avl_balance = p->avl_balance; + + pa[j - 1]->avl_link[da[j - 1]] = s; + da[j] = 1; + pa[j] = s; + } + } + + // assert (k > 0); + while (--k > 0) { + avl_t *y = pa[k]; + + if (da[k] == 0) { + y->avl_balance++; + if (y->avl_balance == +1) break; + else if (y->avl_balance == +2) { + avl_t *x = y->avl_link[1]; + if (x->avl_balance == -1) { + avl_t *w; + // assert (x->avl_balance == -1); + w = x->avl_link[0]; + x->avl_link[0] = w->avl_link[1]; + w->avl_link[1] = x; + y->avl_link[1] = w->avl_link[0]; + w->avl_link[0] = y; + if (w->avl_balance == +1) + x->avl_balance = 0, y->avl_balance = -1; + else if (w->avl_balance == 0) + x->avl_balance = y->avl_balance = 0; + else /* |w->avl_balance == -1| */ + x->avl_balance = +1, y->avl_balance = 0; + w->avl_balance = 0; + pa[k - 1]->avl_link[da[k - 1]] = w; + } + else { + y->avl_link[1] = x->avl_link[0]; + x->avl_link[0] = y; + pa[k - 1]->avl_link[da[k - 1]] = x; + if (x->avl_balance == 0) { + x->avl_balance = -1; + y->avl_balance = +1; + break; + } + else x->avl_balance = y->avl_balance = 0; + } + } + } + else + { + y->avl_balance--; + if (y->avl_balance == -1) break; + else if (y->avl_balance == -2) { + avl_t *x = y->avl_link[0]; + if (x->avl_balance == +1) { + avl_t *w; + // assert (x->avl_balance == +1); + w = x->avl_link[1]; + x->avl_link[1] = w->avl_link[0]; + w->avl_link[0] = x; + y->avl_link[0] = w->avl_link[1]; + w->avl_link[1] = y; + if (w->avl_balance == -1) + x->avl_balance = 0, y->avl_balance = +1; + else if (w->avl_balance == 0) + x->avl_balance = y->avl_balance = 0; + else /* |w->avl_balance == +1| */ + x->avl_balance = -1, y->avl_balance = 0; + w->avl_balance = 0; + pa[k - 1]->avl_link[da[k - 1]] = w; + } + else { + y->avl_link[0] = x->avl_link[1]; + x->avl_link[1] = y; + pa[k - 1]->avl_link[da[k - 1]] = x; + if (x->avl_balance == 0) { + x->avl_balance = +1; + y->avl_balance = -1; + break; + } + else x->avl_balance = y->avl_balance = 0; + } + } + } + } + + // tree->avl_count--; + // tree->avl_generation++; + return item; +} + +/* ------------------------------------------------------------------------- */ +// below are functions by (C) Costa Tsaousis + +// --------------------------- +// traversing + +int avl_walker(avl_t *node, int (*callback)(void * /*entry*/, void * /*data*/), void *data) { + int total = 0, ret = 0; + + if(node->avl_link[0]) { + ret = avl_walker(node->avl_link[0], callback, data); + if(ret < 0) return ret; + total += ret; + } + + ret = callback(node, data); + if(ret < 0) return ret; + total += ret; + + if(node->avl_link[1]) { + ret = avl_walker(node->avl_link[1], callback, data); + if (ret < 0) return ret; + total += ret; + } + + return total; +} + +int avl_traverse(avl_tree_type *tree, int (*callback)(void * /*entry*/, void * /*data*/), void *data) { + if(tree->root) + return avl_walker(tree->root, callback, data); + else + return 0; +} + +// --------------------------- +// locks + +static inline void avl_read_lock(avl_tree_lock *t) { +#if defined(AVL_LOCK_WITH_RWLOCK) + netdata_rwlock_rdlock(&t->rwlock); +#else + rw_spinlock_read_lock(&t->rwlock); +#endif +} + +static inline void avl_write_lock(avl_tree_lock *t) { +#if defined(AVL_LOCK_WITH_RWLOCK) + netdata_rwlock_wrlock(&t->rwlock); +#else + rw_spinlock_write_lock(&t->rwlock); +#endif +} + +static inline void avl_read_unlock(avl_tree_lock *t) { +#if defined(AVL_LOCK_WITH_RWLOCK) + netdata_rwlock_unlock(&t->rwlock); +#else + rw_spinlock_read_unlock(&t->rwlock); +#endif +} + +static inline void avl_write_unlock(avl_tree_lock *t) { +#if defined(AVL_LOCK_WITH_RWLOCK) + netdata_rwlock_unlock(&t->rwlock); +#else + rw_spinlock_write_unlock(&t->rwlock); +#endif +} + +// --------------------------- +// operations with locking + +void avl_init_lock(avl_tree_lock *tree, int (*compar)(void * /*a*/, void * /*b*/)) { + avl_init(&tree->avl_tree, compar); + +#if defined(AVL_LOCK_WITH_RWLOCK) + if(netdata_rwlock_init(&tree->rwlock) != 0) + fatal("Failed to initialize AVL rwlock"); +#else + rw_spinlock_init(&tree->rwlock); +#endif +} + +void avl_destroy_lock(avl_tree_lock *tree __maybe_unused) { +#if defined(AVL_LOCK_WITH_RWLOCK) + if(netdata_rwlock_destroy(&tree->rwlock) != 0) + fatal("Failed to destroy AVL rwlock"); +#endif +} + +avl_t *avl_search_lock(avl_tree_lock *tree, avl_t *item) { + avl_read_lock(tree); + avl_t *ret = avl_search(&tree->avl_tree, item); + avl_read_unlock(tree); + return ret; +} + +avl_t * avl_remove_lock(avl_tree_lock *tree, avl_t *item) { + avl_write_lock(tree); + avl_t *ret = avl_remove(&tree->avl_tree, item); + avl_write_unlock(tree); + return ret; +} + +avl_t *avl_insert_lock(avl_tree_lock *tree, avl_t *item) { + avl_write_lock(tree); + avl_t * ret = avl_insert(&tree->avl_tree, item); + avl_write_unlock(tree); + return ret; +} + +int avl_traverse_lock(avl_tree_lock *tree, int (*callback)(void * /*entry*/, void * /*data*/), void *data) { + avl_read_lock(tree); + int ret = avl_traverse(&tree->avl_tree, callback, data); + avl_read_unlock(tree); + return ret; +} + +void avl_init(avl_tree_type *tree, int (*compar)(void * /*a*/, void * /*b*/)) { + tree->root = NULL; + tree->compar = compar; +} + +// ------------------ diff --git a/libnetdata/avl/avl.h b/libnetdata/avl/avl.h new file mode 100644 index 00000000..595d6ec6 --- /dev/null +++ b/libnetdata/avl/avl.h @@ -0,0 +1,86 @@ +// SPDX-License-Identifier: LGPL-3.0-or-later + +#ifndef _AVL_H +#define _AVL_H 1 + +#include "../libnetdata.h" + +/* Maximum AVL tree height. */ +#ifndef AVL_MAX_HEIGHT +#define AVL_MAX_HEIGHT 92 +#endif + +#if defined(AVL_LOCK_WITH_RWLOCK) +#define AVL_LOCK_INITIALIZER NETDATA_RWLOCK_INITIALIZER +#else +#define AVL_LOCK_INITIALIZER NETDATA_RW_SPINLOCK_INITIALIZER +#endif + +/* Data structures */ + +/* One element of the AVL tree */ +typedef struct avl_element { + struct avl_element *avl_link[2]; /* Subtrees. */ + signed char avl_balance; /* Balance factor. */ +} avl_t; + +typedef struct __attribute__((packed)) avl_element_packed { + struct avl_element *avl_link[2]; /* Subtrees. */ + signed char avl_balance; /* Balance factor. */ +} avl_t_packed; + +/* An AVL tree */ +typedef struct avl_tree_type { + avl_t *root; + int (*compar)(void *a, void *b); +} avl_tree_type; + +typedef struct avl_tree_lock { + avl_tree_type avl_tree; + +#if defined(AVL_LOCK_WITH_RWLOCK) + netdata_rwlock_t rwlock; +#else + RW_SPINLOCK rwlock; +#endif +} avl_tree_lock; + +/* Public methods */ + +/* Insert element a into the AVL tree t + * returns the added element a, or a pointer the + * element that is equal to a (as returned by t->compar()) + * a is linked directly to the tree, so it has to + * be properly allocated by the caller. + */ +avl_t *avl_insert_lock(avl_tree_lock *tree, avl_t *item) NEVERNULL WARNUNUSED; +avl_t *avl_insert(avl_tree_type *tree, avl_t *item) NEVERNULL WARNUNUSED; + +/* Remove an element a from the AVL tree t + * returns a pointer to the removed element + * or NULL if an element equal to a is not found + * (equal as returned by t->compar()) + */ +avl_t *avl_remove_lock(avl_tree_lock *tree, avl_t *item) WARNUNUSED; +avl_t *avl_remove(avl_tree_type *tree, avl_t *item) WARNUNUSED; + +/* Find the element into the tree that equal to a + * (equal as returned by t->compar()) + * returns NULL is no element is equal to a + */ +avl_t *avl_search_lock(avl_tree_lock *tree, avl_t *item); +avl_t *avl_search(avl_tree_type *tree, avl_t *item); + +/* Initialize the avl_tree_lock + */ +void avl_init_lock(avl_tree_lock *tree, int (*compar)(void *a, void *b)); +void avl_init(avl_tree_type *tree, int (*compar)(void *a, void *b)); + +/* Destroy the avl_tree_lock locks + */ +void avl_destroy_lock(avl_tree_lock *tree); + +int avl_traverse_lock(avl_tree_lock *tree, int (*callback)(void *entry, void *data), void *data); +int avl_traverse(avl_tree_type *tree, int (*callback)(void *entry, void *data), void *data); + +#endif /* avl.h */ -- cgit v1.2.3