Imported Upstream version 1.2.0upstream/1.2.0

1 files changed, 92 insertions, 92 deletions

diff --git a/src/avl.c b/src/avl.c
index fd4fb1420..067b0b361 100644
--- a/src/avl.c
+++ b/src/avl.c
@@ -19,9 +19,6 @@
 #include "avl.h"
 #include "log.h"
 
-/* Private methods */
-int _avl_removeroot(avl_tree* t);
-
 /* Swing to the left
  * Warning: no balance maintainance
  */
@@ -69,7 +66,7 @@ void avl_nasty(avl* root) {
  * 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) {
+int avl_insert(avl_tree* t, avl* a) {
 	/* initialize */
 	a->left = 0;
 	a->right = 0;
@@ -86,7 +83,7 @@ int _avl_insert(avl_tree* t, avl* a) {
 			avl_tree left_subtree;
 			left_subtree.root = t->root->left;
 			left_subtree.compar = t->compar;
-			if (_avl_insert(&left_subtree, a)) {
+			if (avl_insert(&left_subtree, a)) {
 				switch (t->root->balance--) {
 				case 1:
 					return 0;
@@ -117,7 +114,7 @@ int _avl_insert(avl_tree* t, avl* a) {
 			avl_tree right_subtree;
 			right_subtree.root = t->root->right;
 			right_subtree.compar = t->compar;
-			if (_avl_insert(&right_subtree, a)) {
+			if (avl_insert(&right_subtree, a)) {
 				switch (t->root->balance++) {
 				case -1:
 					return 0;
@@ -144,36 +141,16 @@ int _avl_insert(avl_tree* t, avl* a) {
 		}
 	}
 }
-int avl_insert(avl_tree* t, avl* a) {
-#ifndef AVL_WITHOUT_PTHREADS
-#ifdef AVL_LOCK_WITH_MUTEX
-	pthread_mutex_lock(&t->mutex);
-#else
-	pthread_rwlock_wrlock(&t->rwlock);
-#endif
-#endif /* AVL_WITHOUT_PTHREADS */
-
-	int ret = _avl_insert(t, a);
-
-#ifndef AVL_WITHOUT_PTHREADS
-#ifdef AVL_LOCK_WITH_MUTEX
-	pthread_mutex_unlock(&t->mutex);
-#else
-	pthread_rwlock_unlock(&t->rwlock);
-#endif
-#endif /* AVL_WITHOUT_PTHREADS */
-	return ret;
-}
 
 /* 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 avl_remove(avl_tree* t, avl* a) {
 	int b;
 	if (t->root == a)
-		return _avl_removeroot(t);
+		return avl_removeroot(t);
 	b = t->compar(t->root, a);
 	if (b >= 0) {
 		/* remove from the left subtree */
@@ -181,7 +158,7 @@ int _avl_remove(avl_tree* t, avl* a) {
 		avl_tree left_subtree;
 		if ((left_subtree.root = t->root->left)) {
 			left_subtree.compar = t->compar;
-			ch = _avl_remove(&left_subtree, a);
+			ch = avl_remove(&left_subtree, a);
 			t->root->left = left_subtree.root;
 			if (ch) {
 				switch (t->root->balance++) {
@@ -215,7 +192,7 @@ int _avl_remove(avl_tree* t, avl* a) {
 		avl_tree right_subtree;
 		if ((right_subtree.root = t->root->right)) {
 			right_subtree.compar = t->compar;
-			ch = _avl_remove(&right_subtree, a);
+			ch = avl_remove(&right_subtree, a);
 			t->root->right = right_subtree.root;
 			if (ch) {
 				switch (t->root->balance--) {
@@ -246,31 +223,10 @@ int _avl_remove(avl_tree* t, avl* a) {
 	return 0;
 }
 
-int avl_remove(avl_tree* t, avl* a) {
-#ifndef AVL_WITHOUT_PTHREADS
-#ifdef AVL_LOCK_WITH_MUTEX
-	pthread_mutex_lock(&t->mutex);
-#else
-	pthread_rwlock_wrlock(&t->rwlock);
-#endif
-#endif /* AVL_WITHOUT_PTHREADS */
-
-	int ret = _avl_remove(t, a);
-
-#ifndef AVL_WITHOUT_PTHREADS
-#ifdef AVL_LOCK_WITH_MUTEX
-	pthread_mutex_unlock(&t->mutex);
-#else
-	pthread_rwlock_unlock(&t->rwlock);
-#endif
-#endif /* AVL_WITHOUT_PTHREADS */
-	return ret;
-}
-
 /* Remove the root of the AVL tree t
  * Warning: dumps core if t is empty
  */
-int _avl_removeroot(avl_tree* t) {
+int avl_removeroot(avl_tree* t) {
 	int ch;
 	avl* a;
 	if (!t->root->left) {
@@ -296,7 +252,7 @@ int _avl_removeroot(avl_tree* t) {
 		while (a->left)
 			a = a->left;
 	}
-	ch = _avl_remove(t, a);
+	ch = avl_remove(t, a);
 	a->left = t->root->left;
 	a->right = t->root->right;
 	a->balance = t->root->balance;
@@ -306,33 +262,12 @@ int _avl_removeroot(avl_tree* t) {
 	return 0;
 }
 
-int avl_removeroot(avl_tree* t) {
-#ifndef AVL_WITHOUT_PTHREADS
-#ifdef AVL_LOCK_WITH_MUTEX
-	pthread_mutex_lock(&t->mutex);
-#else
-	pthread_rwlock_wrlock(&t->rwlock);
-#endif
-#endif /* AVL_WITHOUT_PTHREADS */
-
-	int ret = _avl_removeroot(t);
-
-#ifndef AVL_WITHOUT_PTHREADS
-#ifdef AVL_LOCK_WITH_MUTEX
-	pthread_mutex_unlock(&t->mutex);
-#else
-	pthread_rwlock_unlock(&t->rwlock);
-#endif
-#endif /* AVL_WITHOUT_PTHREADS */
-	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*), avl** ret) {
+int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
 	int x, c = 0;
 	if (!t->root)
 		return 0;
@@ -349,7 +284,7 @@ int _avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
 		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 (!(c = avl_range(&left_subtree, a, b, iter, ret)))
 				if (x > 0)
 					return 0;
 		}
@@ -366,7 +301,7 @@ int _avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
 		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 (!(c = avl_range(&right_subtree, a, b, iter, ret)))
 				if (x < 0)
 					return 0;
 		}
@@ -374,17 +309,57 @@ int _avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
 	return c;
 }
 
-int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
+/* high performance searching - by ktsaou */
+avl *avl_search(avl_tree *t, avl *a) {
+	avl *root = t->root;
+
+	while(root) {
+		int x = t->compar(root, a);
+
+		if(x > 0) {
+			root = root->left;
+			continue;
+		}
+
+		if(x < 0) {
+			root = root->right;
+			continue;
+		}
+
+		return root;
+	}
+
+	return NULL;
+}
+
+void avl_init(avl_tree *t, int (*compar)(void *a, void *b)) {
+	t->root = NULL;
+	t->compar = compar;
+}
+
+/* ------------------------------------------------------------------------- */
+
+void avl_read_lock(avl_tree_lock *t) {
 #ifndef AVL_WITHOUT_PTHREADS
 #ifdef AVL_LOCK_WITH_MUTEX
 	pthread_mutex_lock(&t->mutex);
 #else
-	pthread_rwlock_wrlock(&t->rwlock);
+	pthread_rwlock_rdlock(&t->rwlock);
 #endif
 #endif /* AVL_WITHOUT_PTHREADS */
+}
 
-	int ret2 = _avl_range(t, a, b, iter, ret);
+void avl_write_lock(avl_tree_lock *t) {
+#ifndef AVL_WITHOUT_PTHREADS
+#ifdef AVL_LOCK_WITH_MUTEX
+	pthread_mutex_lock(&t->mutex);
+#else
+	pthread_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
 	pthread_mutex_unlock(&t->mutex);
@@ -392,21 +367,12 @@ int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
 	pthread_rwlock_unlock(&t->rwlock);
 #endif
 #endif /* AVL_WITHOUT_PTHREADS */
-
-	return ret2;
 }
 
-/* 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);
-}
+/* ------------------------------------------------------------------------- */
 
-void avl_init(avl_tree* t, int (*compar)(void* a, void* b)) {
-	t->root = NULL;
-	t->compar = compar;
+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;
@@ -421,5 +387,39 @@ void avl_init(avl_tree* t, int (*compar)(void* a, void* b)) {
 		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;
+}
+
+int avl_range_lock(avl_tree_lock *t, avl *a, avl *b, int (*iter)(avl *), avl **ret) {
+	avl_read_lock(t);
+	int ret2 = avl_range(&t->avl_tree, a, b, iter, ret);
+	avl_unlock(t);
+	return ret2;
+}
 
+int avl_removeroot_lock(avl_tree_lock *t) {
+	avl_write_lock(t);
+	int ret = avl_removeroot(&t->avl_tree);
+	avl_unlock(t);
+	return ret;
+}
+
+int avl_remove_lock(avl_tree_lock *t, avl *a) {
+	avl_write_lock(t);
+	int ret = avl_remove(&t->avl_tree, a);
+	avl_unlock(t);
+	return ret;
+}
+
+int avl_insert_lock(avl_tree_lock *t, avl *a) {
+	avl_write_lock(t);
+	int ret = avl_insert(&t->avl_tree, a);
+	avl_unlock(t);
+	return ret;
 }