X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;ds=sidebyside;f=libraries%2Fliblutil%2Favl.c;h=c95d26a24623c173d068ff3ce8a17b044de326d3;hb=3dadeb3efe31c72dacc2e0e11ee25c271dffe44d;hp=fecb8d2faa80fd1e935cff932a390f94951731a6;hpb=dee98ccd471d768eb22fa533b7f4fe25e2b96c76;p=openldap

diff --git a/libraries/liblutil/avl.c b/libraries/liblutil/avl.c
index fecb8d2faa..c95d26a246 100644
--- a/libraries/liblutil/avl.c
+++ b/libraries/liblutil/avl.c
@@ -2,7 +2,7 @@
 /* $OpenLDAP$ */
 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
  *
- * Copyright 1998-2005 The OpenLDAP Foundation.
+ * Copyright 1998-2010 The OpenLDAP Foundation.
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -34,6 +34,7 @@
 
 #include "portable.h"
 
+#include <limits.h>
 #include <stdio.h>
 #include <ac/stdlib.h>
 
@@ -48,6 +49,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};
 
 /*
@@ -180,8 +184,8 @@ avl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
 	int side, side_bf, shorter, nside;
 
 	/* 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 )
@@ -230,14 +234,13 @@ avl_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 > 1 ) {
+		if ( depth-side > 1 ) {
 			r = pptr[depth-1];
 			r->avl_link[1] = p;
 		} else {
@@ -246,7 +249,7 @@ avl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
 	}
 
 	/* now <p> has at most one child, get it */
-	q = p->avl_link[0];
+	q = p->avl_link[0] ? p->avl_link[0] : p->avl_link[1];
 
 	ber_memfree( p );
 
@@ -528,10 +531,8 @@ avl_find2( Avlnode *root, const void *data, AVL_CMP fcmp )
 	int	cmp;
 
 	while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
-		if ( cmp < 0 )
-			root = root->avl_left;
-		else
-			root = root->avl_right;
+		cmp = cmp > 0;
+		root = root->avl_link[cmp];
 	}
 	return root;
 }
@@ -542,10 +543,8 @@ avl_find( Avlnode *root, const void* data, AVL_CMP fcmp )
 	int	cmp;
 
 	while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
-		if ( cmp < 0 )
-			root = root->avl_left;
-		else
-			root = root->avl_right;
+		cmp = cmp > 0;
+		root = root->avl_link[cmp];
 	}
 
 	return( root ? root->avl_data : 0 );