diff options
Diffstat (limited to 'libnetdata/avl')
| -rw-r--r-- | libnetdata/avl/Makefile.am | 8 | ||||
| -rw-r--r-- | libnetdata/avl/README.md | 17 | ||||
| -rw-r--r-- | libnetdata/avl/avl.c | 420 | ||||
| -rw-r--r-- | libnetdata/avl/avl.h | 92 |
4 files changed, 537 insertions, 0 deletions
diff --git a/libnetdata/avl/Makefile.am b/libnetdata/avl/Makefile.am new file mode 100644 index 0000000..161784b --- /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 0000000..2097be5 --- /dev/null +++ b/libnetdata/avl/README.md @@ -0,0 +1,17 @@ +<!-- +title: "AVL" +custom_edit_url: https://github.com/netdata/netdata/edit/master/libnetdata/avl/README.md +--> + +# 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 0000000..5219851 --- /dev/null +++ b/libnetdata/avl/avl.c @@ -0,0 +1,420 @@ +// 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 *avl_search(avl_tree_type *tree, avl *item) { + avl *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 *avl_insert(avl_tree_type *tree, avl *item) { + avl *y, *z; /* Top node to update balance factor, and parent. */ + avl *p, *q; /* Iterator, and parent. */ + avl *n; /* Newly inserted node. */ + avl *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 *) &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 *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 *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 *avl_remove(avl_tree_type *tree, avl *item) { + /* Stack of nodes. */ + avl *pa[AVL_MAX_HEIGHT]; /* Nodes. */ + unsigned char da[AVL_MAX_HEIGHT]; /* |avl_link[]| indexes. */ + int k; /* Stack pointer. */ + + avl *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 *) &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 *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 *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 *y = pa[k]; + + if (da[k] == 0) { + y->avl_balance++; + if (y->avl_balance == +1) break; + else if (y->avl_balance == +2) { + avl *x = y->avl_link[1]; + if (x->avl_balance == -1) { + avl *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 *x = y->avl_link[0]; + if (x->avl_balance == +1) { + avl *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 *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 + +void avl_read_lock(avl_tree_lock *t) { +#ifndef AVL_WITHOUT_PTHREADS +#ifdef AVL_LOCK_WITH_MUTEX + netdata_mutex_lock(&t->mutex); +#else + netdata_rwlock_rdlock(&t->rwlock); +#endif +#endif /* AVL_WITHOUT_PTHREADS */ +} + +void avl_write_lock(avl_tree_lock *t) { +#ifndef AVL_WITHOUT_PTHREADS +#ifdef AVL_LOCK_WITH_MUTEX + netdata_mutex_lock(&t->mutex); +#else + netdata_rwlock_wrlock(&t->rwlock); +#endif +#endif /* AVL_WITHOUT_PTHREADS */ +} + +void avl_unlock(avl_tree_lock *t) { +#ifndef AVL_WITHOUT_PTHREADS +#ifdef AVL_LOCK_WITH_MUTEX + netdata_mutex_unlock(&t->mutex); +#else + netdata_rwlock_unlock(&t->rwlock); +#endif +#endif /* AVL_WITHOUT_PTHREADS */ +} + +// --------------------------- +// operations with locking + +void avl_init_lock(avl_tree_lock *tree, int (*compar)(void * /*a*/, void * /*b*/)) { + avl_init(&tree->avl_tree, compar); + +#ifndef AVL_WITHOUT_PTHREADS + int lock; + +#ifdef AVL_LOCK_WITH_MUTEX + lock = netdata_mutex_init(&tree->mutex, NULL); +#else + lock = netdata_rwlock_init(&tree->rwlock); +#endif + + if(lock != 0) + fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock); + +#endif /* AVL_WITHOUT_PTHREADS */ +} + +void avl_destroy_lock(avl_tree_lock *tree) { +#ifndef AVL_WITHOUT_PTHREADS + int lock; + +#ifdef AVL_LOCK_WITH_MUTEX + lock = pthread_mutex_destroy(&tree->mutex); +#else + lock = pthread_rwlock_destroy(&tree->rwlock); +#endif + + if(lock != 0) + fatal("Failed to destroy AVL mutex/rwlock, error: %d", lock); + +#endif /* AVL_WITHOUT_PTHREADS */ +} + +avl *avl_search_lock(avl_tree_lock *tree, avl *item) { + avl_read_lock(tree); + avl *ret = avl_search(&tree->avl_tree, item); + avl_unlock(tree); + return ret; +} + +avl * avl_remove_lock(avl_tree_lock *tree, avl *item) { + avl_write_lock(tree); + avl *ret = avl_remove(&tree->avl_tree, item); + avl_unlock(tree); + return ret; +} + +avl *avl_insert_lock(avl_tree_lock *tree, avl *item) { + avl_write_lock(tree); + avl * ret = avl_insert(&tree->avl_tree, item); + avl_unlock(tree); + return ret; +} + +int avl_traverse_lock(avl_tree_lock *tree, int (*callback)(void * /*entry*/, void * /*data*/), void *data) { + int ret; + avl_read_lock(tree); + ret = avl_traverse(&tree->avl_tree, callback, data); + avl_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 0000000..32e3f27 --- /dev/null +++ b/libnetdata/avl/avl.h @@ -0,0 +1,92 @@ +// 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 + +#ifndef AVL_WITHOUT_PTHREADS +#include <pthread.h> + +// #define AVL_LOCK_WITH_MUTEX 1 + +#ifdef AVL_LOCK_WITH_MUTEX +#define AVL_LOCK_INITIALIZER NETDATA_MUTEX_INITIALIZER +#else /* AVL_LOCK_WITH_MUTEX */ +#define AVL_LOCK_INITIALIZER NETDATA_RWLOCK_INITIALIZER +#endif /* AVL_LOCK_WITH_MUTEX */ + +#else /* AVL_WITHOUT_PTHREADS */ +#define AVL_LOCK_INITIALIZER +#endif /* AVL_WITHOUT_PTHREADS */ + +/* Data structures */ + +/* One element of the AVL tree */ +typedef struct avl { + struct avl *avl_link[2]; /* Subtrees. */ + signed char avl_balance; /* Balance factor. */ +} avl; + +/* An AVL tree */ +typedef struct avl_tree_type { + avl *root; + int (*compar)(void *a, void *b); +} avl_tree_type; + +typedef struct avl_tree_lock { + avl_tree_type avl_tree; + +#ifndef AVL_WITHOUT_PTHREADS +#ifdef AVL_LOCK_WITH_MUTEX + netdata_mutex_t mutex; +#else /* AVL_LOCK_WITH_MUTEX */ + netdata_rwlock_t rwlock; +#endif /* AVL_LOCK_WITH_MUTEX */ +#endif /* AVL_WITHOUT_PTHREADS */ +} 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 *avl_insert_lock(avl_tree_lock *tree, avl *item) NEVERNULL WARNUNUSED; +avl *avl_insert(avl_tree_type *tree, avl *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 *avl_remove_lock(avl_tree_lock *tree, avl *item) WARNUNUSED; +avl *avl_remove(avl_tree_type *tree, avl *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 *avl_search_lock(avl_tree_lock *tree, avl *item); +avl *avl_search(avl_tree_type *tree, avl *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 */ |