X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=libraries%2Fliblutil%2Ftavl.c;h=a6a2bf4a5f88049850d340d6ded3cc9f948a748a;hb=198879bd5f1baa09e5dc7a951db980a932cd5db5;hp=70b4eda6f372064510e9e004084651e04423b5a9;hpb=55fa9241a40a8e05fbfe2e791d9a025e82ff011d;p=openldap

diff --git a/libraries/liblutil/tavl.c b/libraries/liblutil/tavl.c
index 70b4eda6f3..a6a2bf4a5f 100644
--- a/libraries/liblutil/tavl.c
+++ b/libraries/liblutil/tavl.c
@@ -2,7 +2,7 @@
 /* $OpenLDAP$ */
 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
  *
- * Copyright 2005 The OpenLDAP Foundation.
+ * Copyright 2005-2009 The OpenLDAP Foundation.
  * Portions Copyright (c) 2005 by Howard Chu, Symas Corp.
  * All rights reserved.
  *
@@ -21,6 +21,7 @@
 
 #include "portable.h"
 
+#include <limits.h>
 #include <stdio.h>
 #include <ac/stdlib.h>
 
@@ -35,6 +36,9 @@
 #define AVL_INTERNAL
 #include "avl.h"
 
+/* Maximum tree depth this host's address space could support */
+#define MAX_TREE_DEPTH	(sizeof(void *) * CHAR_BIT)
+
 static const int avl_bfs[] = {LH, RH};
 
 /*
@@ -186,11 +190,11 @@ void*
 tavl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
 {
 	Avlnode *p, *q, *r, *top;
-	int side, side_bf, shorter, nside;
+	int side, side_bf, shorter, nside = -1;
 
 	/* parent stack */
-	Avlnode *pptr[sizeof(void *)*8];
-	unsigned char pdir[sizeof(void *)*8];
+	Avlnode *pptr[MAX_TREE_DEPTH];
+	unsigned char pdir[MAX_TREE_DEPTH];
 	int depth = 0;
 
 	if ( *root == NULL )
@@ -244,17 +248,15 @@ tavl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
 		/* fix stack positions: old parent of p points to q */
 		pptr[side] = q;
 		if ( side ) {
-			--side;
-			r = pptr[side];
-			r->avl_link[pdir[side]] = q;
+			r = pptr[side-1];
+			r->avl_link[pdir[side-1]] = q;
 		} else {
 			*root = q;
 		}
 		/* new parent of p points to p */
-		if ( depth > 2 ) {
-			r = pptr[depth-2];
+		if ( depth-side > 1 ) {
+			r = pptr[depth-1];
 			r->avl_link[1] = p;
-			pptr[depth-1] = p;
 		} else {
 			q->avl_link[0] = p;
 		}
@@ -286,6 +288,13 @@ tavl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
 
 	ber_memfree( p );
 
+	/* Update child thread */
+	if ( q ) {
+		for ( ; q->avl_bits[nside] == AVL_CHILD && q->avl_link[nside];
+			q = q->avl_link[nside] ) ;
+		q->avl_link[nside] = r;
+	}
+	
 	if ( !depth ) {
 		*root = q;
 		return data;
@@ -297,12 +306,7 @@ tavl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
 	side = pdir[depth];
 	p->avl_link[side] = q;
 
-	/* Update child thread */
-	if ( q ) {
-		for ( ; q->avl_bits[nside] == AVL_CHILD && q->avl_link[nside];
-			q = q->avl_link[nside] ) ;
-		q->avl_link[nside] = r;
-	} else {
+	if ( !q ) {
 		p->avl_bits[side] = AVL_THREAD;
 		p->avl_link[side] = r;
 	}
@@ -445,6 +449,26 @@ tavl_free( Avlnode *root, AVL_FREE dfree )
  * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
  */
 
+/*
+ * tavl_find2 - returns Avlnode instead of data pointer.
+ * tavl_find3 - as above, but returns Avlnode even if no match is found.
+ *				also set *ret = last comparison result, or -1 if root == NULL.
+ */
+Avlnode *
+tavl_find3( Avlnode *root, const void *data, AVL_CMP fcmp, int *ret )
+{
+	int	cmp = -1, dir;
+	Avlnode *prev = root;
+
+	while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
+		prev = root;
+		dir = cmp > 0;
+		root = avl_child( root, dir );
+	}
+	*ret = cmp;
+	return root ? root : prev;
+}
+
 Avlnode *
 tavl_find2( Avlnode *root, const void *data, AVL_CMP fcmp )
 {