X-Git-Url: https://arthur.barton.de/gitweb/?a=blobdiff_plain;f=src%2Favl.c;h=0ea119a7c8cd9bfd5a251cf3213a749cce8488f6;hb=8679670bdbe3c5928ec2e266d9c72e1a758fdf37;hp=9cc72283d84dad626a883127da3031a37d423bb1;hpb=76eafaa8cdae91d6c7447ccfbae63f152aaa0767;p=netdata.git

diff --git a/src/avl.c b/src/avl.c
old mode 100755
new mode 100644
index 9cc72283..0ea119a7
--- a/src/avl.c
+++ b/src/avl.c
@@ -1,353 +1,400 @@
+#include "common.h"
+
+/* ------------------------------------------------------------------------- */
 /*
- * ANSI C Library for maintainance of AVL Balanced Trees
- *
- * ref.:
- *  G. M. Adelson-Velskij & E. M. Landis
- *  Doklady Akad. Nauk SSSR 146 (1962), 263-266
- *
- * see also:
- *  D. E. Knuth: The Art of Computer Programming Vol.3 (Sorting and Searching)
- *
- * (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
- * Released under GNU General Public License (GPL) version 2
+ * 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
+*/
 
-#ifdef HAVE_CONFIG_H
-#include <config.h>
-#endif
-#include "avl.h"
 
-/* Private methods */
-int _avl_removeroot(avl_tree* t);
+/* 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;
 
-/* Swing to the left
- * Warning: no balance maintainance
- */
-void avl_swl(avl** root) {
-	avl* a = *root;
-	avl* b = a->right;
-	*root = b;
-	a->right = b->left;
-	b->left = a;
+    // 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;
 }
 
-/* Swing to the right
- * Warning: no balance maintainance
+/* 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|.
  */
-void avl_swr(avl** root) {
-	avl* a = *root;
-	avl* b = a->left;
-	*root = b;
-	a->left = b->right;
-	b->right = a;
+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;
 }
 
-/* Balance maintainance after especially nasty swings
- */
-void avl_nasty(avl* root) {
-	switch (root->balance) {
-	case -1:
-		root->left->balance = 0;
-		root->right->balance = 1;
-		break;
-	case 1:
-		root->left->balance = -1;
-		root->right->balance = 0;
-		break;
-	case 0:
-		root->left->balance = 0;
-		root->right->balance = 0;
-	}
-	root->balance = 0;
+/* 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;
 }
 
-/* Public methods */
+/* ------------------------------------------------------------------------- */
+// below are functions by (C) Costa Tsaousis
 
-/* Insert element a into the AVL tree t
- * returns 1 if the depth of the tree has grown
- * Warning: do not insert elements already present
- */
-int _avl_insert(avl_tree* t, avl* a) {
-	/* initialize */
-	a->left = 0;
-	a->right = 0;
-	a->balance = 0;
-	/* insert into an empty tree */
-	if (!t->root) {
-		t->root = a;
-		return 1;
-	}
-
-	if (t->compar(t->root, a) > 0) {
-		/* insert into the left subtree */
-		if (t->root->left) {
-			avl_tree left_subtree;
-			left_subtree.root = t->root->left;
-			left_subtree.compar = t->compar;
-			if (_avl_insert(&left_subtree, a)) {
-				switch (t->root->balance--) {
-				case 1:
-					return 0;
-				case 0:
-					return 1;
-				}
-				if (t->root->left->balance < 0) {
-					avl_swr(&(t->root));
-					t->root->balance = 0;
-					t->root->right->balance = 0;
-				} else {
-					avl_swl(&(t->root->left));
-					avl_swr(&(t->root));
-					avl_nasty(t->root);
-				}
-			} else
-				t->root->left = left_subtree.root;
-			return 0;
-		} else {
-			t->root->left = a;
-			if (t->root->balance--)
-				return 0;
-			return 1;
-		}
-	} else {
-		/* insert into the right subtree */
-		if (t->root->right) {
-			avl_tree right_subtree;
-			right_subtree.root = t->root->right;
-			right_subtree.compar = t->compar;
-			if (_avl_insert(&right_subtree, a)) {
-				switch (t->root->balance++) {
-				case -1:
-					return 0;
-				case 0:
-					return 1;
-				}
-				if (t->root->right->balance > 0) {
-					avl_swl(&(t->root));
-					t->root->balance = 0;
-					t->root->left->balance = 0;
-				} else {
-					avl_swr(&(t->root->right));
-					avl_swl(&(t->root));
-					avl_nasty(t->root);
-				}
-			} else
-				t->root->right = right_subtree.root;
-			return 0;
-		} else {
-			t->root->right = a;
-			if (t->root->balance++)
-				return 0;
-			return 1;
-		}
-	}
+// ---------------------------
+// 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_insert(avl_tree* t, avl* a) {
-	pthread_rwlock_wrlock(&t->rwlock);
-	int ret = _avl_insert(t, a);
-	pthread_rwlock_unlock(&t->rwlock);
-	return ret;
+
+int avl_traverse(avl_tree *t, int (*callback)(void *entry, void *data), void *data) {
+    return avl_walker(t->root, callback, data);
 }
 
-/* Remove an element a from the AVL tree t
- * returns -1 if the depth of the tree has shrunk
- * Warning: if the element is not present in the tree,
- *          returns 0 as if it had been removed succesfully.
- */
-int _avl_remove(avl_tree* t, avl* a) {
-	int b;
-	if (t->root == a)
-		return _avl_removeroot(t);
-	b = t->compar(t->root, a);
-	if (b >= 0) {
-		/* remove from the left subtree */
-		int ch;
-		avl_tree left_subtree;
-		if ((left_subtree.root = t->root->left)) {
-			left_subtree.compar = t->compar;
-			ch = _avl_remove(&left_subtree, a);
-			t->root->left = left_subtree.root;
-			if (ch) {
-				switch (t->root->balance++) {
-				case -1:
-					return -1;
-				case 0:
-					return 0;
-				}
-				switch (t->root->right->balance) {
-				case 0:
-					avl_swl(&(t->root));
-					t->root->balance = -1;
-					t->root->left->balance = 1;
-					return 0;
-				case 1:
-					avl_swl(&(t->root));
-					t->root->balance = 0;
-					t->root->left->balance = 0;
-					return -1;
-				}
-				avl_swr(&(t->root->right));
-				avl_swl(&(t->root));
-				avl_nasty(t->root);
-				return -1;
-			}
-		}
-	}
-	if (b <= 0) {
-		/* remove from the right subtree */
-		int ch;
-		avl_tree right_subtree;
-		if ((right_subtree.root = t->root->right)) {
-			right_subtree.compar = t->compar;
-			ch = _avl_remove(&right_subtree, a);
-			t->root->right = right_subtree.root;
-			if (ch) {
-				switch (t->root->balance--) {
-				case 1:
-					return -1;
-				case 0:
-					return 0;
-				}
-				switch (t->root->left->balance) {
-				case 0:
-					avl_swr(&(t->root));
-					t->root->balance = 1;
-					t->root->right->balance = -1;
-					return 0;
-				case -1:
-					avl_swr(&(t->root));
-					t->root->balance = 0;
-					t->root->right->balance = 0;
-					return -1;
-				}
-				avl_swl(&(t->root->left));
-				avl_swr(&(t->root));
-				avl_nasty(t->root);
-				return -1;
-			}
-		}
-	}
-	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 */
 }
 
-int avl_remove(avl_tree* t, avl* a) {
-	pthread_rwlock_wrlock(&t->rwlock);
-	int ret = _avl_remove(t, a);
-	pthread_rwlock_unlock(&t->rwlock);
-	return ret;
+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 */
 }
 
-/* Remove the root of the AVL tree t
- * Warning: dumps core if t is empty
- */
-int _avl_removeroot(avl_tree* t) {
-	int ch;
-	avl* a;
-	if (!t->root->left) {
-		if (!t->root->right) {
-			t->root = 0;
-			return -1;
-		}
-		t->root = t->root->right;
-		return -1;
-	}
-	if (!t->root->right) {
-		t->root = t->root->left;
-		return -1;
-	}
-	if (t->root->balance < 0) {
-		/* remove from the left subtree */
-		a = t->root->left;
-		while (a->right)
-			a = a->right;
-	} else {
-		/* remove from the right subtree */
-		a = t->root->right;
-		while (a->left)
-			a = a->left;
-	}
-	ch = _avl_remove(t, a);
-	a->left = t->root->left;
-	a->right = t->root->right;
-	a->balance = t->root->balance;
-	t->root = a;
-	if (a->balance == 0)
-		return ch;
-	return 0;
+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 */
 }
 
-int avl_removeroot(avl_tree* t) {
-	pthread_rwlock_wrlock(&t->rwlock);
-	int ret = _avl_removeroot(t);
-	pthread_rwlock_unlock(&t->rwlock);
-	return ret;
+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;
 }
 
-/* Iterate through elements in t from a range between a and b (inclusive)
- * for each element calls iter(a) until it returns 0
- * returns the last value returned by iterator or 0 if there were no calls
- * Warning: a<=b must hold
- */
-int _avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl* a), avl** ret) {
-	int x, c = 0;
-	if (!t->root)
-		return 0;
-	x = t->compar(t->root, a);
-	if (a != b) {
-		if (x < 0) {
-			x = t->compar(t->root, b);
-			if (x > 0)
-				x = 0;
-		}
-	}
-	if (x >= 0) {
-		/* search in the left subtree */
-		avl_tree left_subtree;
-		if ((left_subtree.root = t->root->left)) {
-			left_subtree.compar = t->compar;
-			if (!(c = _avl_range(&left_subtree, a, b, iter, ret)))
-				if (x > 0)
-					return 0;
-		}
-	}
-	if (x == 0) {
-		if (!(c = iter(t->root))) {
-			if (ret)
-				*ret = t->root;
-			return 0;
-		}
-	}
-	if (x <= 0) {
-		/* search in the right subtree */
-		avl_tree right_subtree;
-		if ((right_subtree.root = t->root->right)) {
-			right_subtree.compar = t->compar;
-			if (!(c = _avl_range(&right_subtree, a, b, iter, ret)))
-				if (x < 0)
-					return 0;
-		}
-	}
-	return c;
+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;
 }
 
-int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl* a), avl** ret) {
-	pthread_rwlock_rdlock(&t->rwlock);
-	int ret2 = _avl_range(t, a, b, iter, ret);
-	pthread_rwlock_unlock(&t->rwlock);
-	return ret2;
+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;
 }
 
-/* Iterate through elements in t equal to a
- * for each element calls iter(a) until it returns 0
- * returns the last value returned by iterator or 0 if there were no calls
- */
-int avl_search(avl_tree* t, avl* a, int (*iter)(avl* a), avl** ret) {
-	return avl_range(t, a, a, iter, 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;
-	pthread_rwlock_init(&t->rwlock, NULL);
+void avl_init(avl_tree *t, int (*compar)(void *a, void *b)) {
+    t->root = NULL;
+    t->compar = compar;
 }
+
+// ------------------
\ No newline at end of file