From 1e6c93250172946eeb38e94a92a1fd12c9d3011e Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 7 Nov 2018 13:22:44 +0100 Subject: Merging upstream version 1.11.0+dfsg. Signed-off-by: Daniel Baumann --- src/avl.c | 403 -------------------------------------------------------------- 1 file changed, 403 deletions(-) delete mode 100644 src/avl.c (limited to 'src/avl.c') diff --git a/src/avl.c b/src/avl.c deleted file mode 100644 index a2c6911e7..000000000 --- a/src/avl.c +++ /dev/null @@ -1,403 +0,0 @@ -#include "common.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. - * GNU Lesser General Public License -*/ - - -/* Search |tree| for an item matching |item|, and return it if found. - Otherwise return |NULL|. */ -avl *avl_search(avl_tree *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 *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. */ - int 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 = (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 *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)) { - int dir = (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 *t, int (*callback)(void *entry, void *data), void *data) { - if(t->root) - return avl_walker(t->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 *t, int (*compar)(void *a, void *b)) { - avl_init(&t->avl_tree, compar); - -#ifndef AVL_WITHOUT_PTHREADS - int lock; - -#ifdef AVL_LOCK_WITH_MUTEX - lock = netdata_mutex_init(&t->mutex, NULL); -#else - lock = netdata_rwlock_init(&t->rwlock); -#endif - - if(lock != 0) - fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock); - -#endif /* AVL_WITHOUT_PTHREADS */ -} - -avl *avl_search_lock(avl_tree_lock *t, avl *a) { - avl_read_lock(t); - avl *ret = avl_search(&t->avl_tree, a); - avl_unlock(t); - return ret; -} - -avl * avl_remove_lock(avl_tree_lock *t, avl *a) { - avl_write_lock(t); - avl *ret = avl_remove(&t->avl_tree, a); - avl_unlock(t); - return ret; -} - -avl *avl_insert_lock(avl_tree_lock *t, avl *a) { - avl_write_lock(t); - avl * ret = avl_insert(&t->avl_tree, a); - avl_unlock(t); - return ret; -} - -int avl_traverse_lock(avl_tree_lock *t, int (*callback)(void *entry, void *data), void *data) { - int ret; - avl_read_lock(t); - ret = avl_traverse(&t->avl_tree, callback, data); - avl_unlock(t); - return ret; -} - -void avl_init(avl_tree *t, int (*compar)(void *a, void *b)) { - t->root = NULL; - t->compar = compar; -} - -// ------------------ \ No newline at end of file -- cgit v1.2.3