X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=libraries%2Flibavl%2Favl.c;h=bd0ede4d66b1cb2c6a52aea333e4024cd8a32f29;hb=c1a257a83f3d8b9565238b5f9b8cad39a6194f63;hp=7de1e1cbb770dde582101ad9ae1bee3dc60824a6;hpb=7e6ad5100c2702b1d56a285bdfb341ddf38c0d76;p=openldap

diff --git a/libraries/libavl/avl.c b/libraries/libavl/avl.c
index 7de1e1cbb7..bd0ede4d66 100644
--- a/libraries/libavl/avl.c
+++ b/libraries/libavl/avl.c
@@ -1,4 +1,9 @@
 /* avl.c - routines to implement an avl tree */
+/* $OpenLDAP$ */
+/*
+ * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved.
+ * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
+ */
 /*
  * Copyright (c) 1993 Regents of the University of Michigan.
  * All rights reserved.
@@ -13,21 +18,23 @@
 
 #include "portable.h"
 
-#ifndef lint
-static char copyright[] = "@(#) Copyright (c) 1993 Regents of the University of Michigan.\nAll rights reserved.\n";
-static char avl_version[] = "AVL library version 1.0\n";
-#endif
-
 #include <stdio.h>
-#include <stdlib.h>
-#include <sys/types.h>
+#include <ac/stdlib.h>
 
+#ifdef CSRIMALLOC
+#define ber_memalloc malloc
+#define ber_memrealloc realloc
+#else
+#include "lber.h"
+#endif
+
+#define AVL_INTERNAL
 #include "avl.h"
 
 #define ROTATERIGHT(x)	{ \
 	Avlnode *tmp;\
 	if ( *(x) == NULL || (*(x))->avl_left == NULL ) {\
-		(void) printf("RR error\n"); exit(1); \
+		(void) fputs("RR error\n", stderr); exit( EXIT_FAILURE ); \
 	}\
 	tmp = (*(x))->avl_left;\
 	(*(x))->avl_left = tmp->avl_right;\
@@ -37,11 +44,11 @@ static char avl_version[] = "AVL library version 1.0\n";
 #define ROTATELEFT(x)	{ \
 	Avlnode *tmp;\
 	if ( *(x) == NULL || (*(x))->avl_right == NULL ) {\
-		(void) printf("RL error\n"); exit(1); \
+		(void) fputs("RL error\n", stderr); exit( EXIT_FAILURE ); \
 	}\
 	tmp = (*(x))->avl_right;\
 	(*(x))->avl_right = tmp->avl_left;\
-	tmp->avl_left = *x;\
+	tmp->avl_left = *(x);\
 	*(x) = tmp;\
 }
 
@@ -53,10 +60,10 @@ static char avl_version[] = "AVL library version 1.0\n";
 static int
 ravl_insert(
     Avlnode	**iroot,
-    caddr_t	data,
+    void*	data,
     int		*taller,
-    IFP		fcmp,			/* comparison function */
-    IFP		fdup,			/* function to call for duplicates */
+    AVL_CMP		fcmp,			/* comparison function */
+    AVL_DUP		fdup,			/* function to call for duplicates */
     int		depth
 )
 {
@@ -64,7 +71,7 @@ ravl_insert(
 	Avlnode	*l, *r;
 
 	if ( *iroot == 0 ) {
-		if ( (*iroot = (Avlnode *) malloc( sizeof( Avlnode ) ))
+		if ( (*iroot = (Avlnode *) ber_memalloc( sizeof( Avlnode ) ))
 		    == NULL ) {
 			return( -1 );
 		}
@@ -206,7 +213,7 @@ ravl_insert(
  */
 
 int
-avl_insert( Avlnode **root, caddr_t data, IFP fcmp, IFP fdup )
+avl_insert( Avlnode **root, void* data, AVL_CMP fcmp, AVL_DUP fdup )
 {
 	int	taller;
 
@@ -348,12 +355,12 @@ left_balance( Avlnode **root )
  * rebalancing.
  */
 
-static caddr_t
-ravl_delete( Avlnode **root, caddr_t data, IFP fcmp, int *shorter )
+static void*
+ravl_delete( Avlnode **root, void* data, AVL_CMP fcmp, int *shorter )
 {
 	int	shortersubtree = 0;
 	int	cmp;
-	caddr_t	savedata;
+	void*	savedata;
 	Avlnode	*minnode, *savenode;
 
 	if ( *root == NULLAVL )
@@ -437,8 +444,8 @@ ravl_delete( Avlnode **root, caddr_t data, IFP fcmp, int *shorter )
  * the avl tree rooted at root.
  */
 
-caddr_t
-avl_delete( Avlnode **root, caddr_t data, IFP fcmp )
+void*
+avl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
 {
 	int	shorter;
 
@@ -446,7 +453,7 @@ avl_delete( Avlnode **root, caddr_t data, IFP fcmp )
 }
 
 static int
-avl_inapply( Avlnode *root, IFP fn, caddr_t arg, int stopflag )
+avl_inapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
 {
 	if ( root == 0 )
 		return( AVL_NOMORE );
@@ -466,7 +473,7 @@ avl_inapply( Avlnode *root, IFP fn, caddr_t arg, int stopflag )
 }
 
 static int
-avl_postapply( Avlnode *root, IFP fn, caddr_t arg, int stopflag )
+avl_postapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
 {
 	if ( root == 0 )
 		return( AVL_NOMORE );
@@ -485,7 +492,7 @@ avl_postapply( Avlnode *root, IFP fn, caddr_t arg, int stopflag )
 }
 
 static int
-avl_preapply( Avlnode *root, IFP fn, caddr_t arg, int stopflag )
+avl_preapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
 {
 	if ( root == 0 )
 		return( AVL_NOMORE );
@@ -513,7 +520,7 @@ avl_preapply( Avlnode *root, IFP fn, caddr_t arg, int stopflag )
  */
 
 int
-avl_apply( Avlnode *root, IFP fn, caddr_t arg, int stopflag, int type )
+avl_apply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag, int type )
 {
 	switch ( type ) {
 	case AVL_INORDER:
@@ -544,11 +551,11 @@ avl_apply( Avlnode *root, IFP fn, caddr_t arg, int stopflag, int type )
 int
 avl_prefixapply(
     Avlnode	*root,
-    caddr_t	data,
-    IFP		fmatch,
-    caddr_t	marg,
-    IFP		fcmp,
-    caddr_t	carg,
+    void*	data,
+    AVL_CMP		fmatch,
+    void*	marg,
+    AVL_CMP		fcmp,
+    void*	carg,
     int		stopflag
 )
 {
@@ -557,7 +564,7 @@ avl_prefixapply(
 	if ( root == 0 )
 		return( AVL_NOMORE );
 
-	cmp = (*fcmp)( data, root->avl_data, carg );
+	cmp = (*fcmp)( data, root->avl_data /* , carg */);
 	if ( cmp == 0 ) {
 		if ( (*fmatch)( root->avl_data, marg ) == stopflag )
 			return( stopflag );
@@ -593,7 +600,7 @@ avl_prefixapply(
  */
 
 int
-avl_free( Avlnode *root, IFP dfree )
+avl_free( Avlnode *root, AVL_FREE dfree )
 {
 	int	nleft, nright;
 
@@ -609,6 +616,7 @@ avl_free( Avlnode *root, IFP dfree )
 
 	if ( dfree )
 		(*dfree)( root->avl_data );
+	free( root );
 
 	return( nleft + nright + 1 );
 }
@@ -620,8 +628,8 @@ avl_free( Avlnode *root, IFP dfree )
  * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
  */
 
-caddr_t
-avl_find( Avlnode *root, caddr_t data, IFP fcmp )
+void*
+avl_find( Avlnode *root, const void* data, AVL_CMP fcmp )
 {
 	int	cmp;
 
@@ -642,10 +650,10 @@ avl_find( Avlnode *root, caddr_t data, IFP fcmp )
  * they match, non-zero otherwise.
  */
 
-caddr_t
-avl_find_lin( Avlnode *root, caddr_t data, IFP fcmp )
+void*
+avl_find_lin( Avlnode *root, const void* data, AVL_CMP fcmp )
 {
-	caddr_t	res;
+	void*	res;
 
 	if ( root == 0 )
 		return( NULL );
@@ -664,7 +672,9 @@ avl_find_lin( Avlnode *root, caddr_t data, IFP fcmp )
 		return( avl_find_lin( root->avl_right, data, fcmp ) );
 }
 
-static caddr_t	*avl_list;
+/* NON-REENTRANT INTERFACE */
+
+static void*	*avl_list;
 static int	avl_maxlist;
 static int	avl_nextlist;
 
@@ -672,18 +682,18 @@ static int	avl_nextlist;
 
 /* ARGSUSED */
 static int
-avl_buildlist( caddr_t data, int arg )
+avl_buildlist( void* data, void* arg )
 {
 	static int	slots;
 
-	if ( avl_list == (caddr_t *) 0 ) {
-		avl_list = (caddr_t *) malloc(AVL_GRABSIZE * sizeof(caddr_t));
+	if ( avl_list == (void* *) 0 ) {
+		avl_list = (void* *) ber_memalloc(AVL_GRABSIZE * sizeof(void*));
 		slots = AVL_GRABSIZE;
 		avl_maxlist = 0;
 	} else if ( avl_maxlist == slots ) {
 		slots += AVL_GRABSIZE;
-		avl_list = (caddr_t *) realloc( (char *) avl_list,
-		    (unsigned) slots * sizeof(caddr_t));
+		avl_list = (void* *) ber_memrealloc( (char *) avl_list,
+		    (unsigned) slots * sizeof(void*));
 	}
 
 	avl_list[ avl_maxlist++ ] = data;
@@ -703,12 +713,12 @@ avl_buildlist( caddr_t data, int arg )
  * different trees) cannot be active at once.
  */
 
-caddr_t
+void*
 avl_getfirst( Avlnode *root )
 {
 	if ( avl_list ) {
 		free( (char *) avl_list);
-		avl_list = (caddr_t *) 0;
+		avl_list = (void* *) 0;
 	}
 	avl_maxlist = 0;
 	avl_nextlist = 0;
@@ -716,34 +726,37 @@ avl_getfirst( Avlnode *root )
 	if ( root == 0 )
 		return( 0 );
 
-	(void) avl_apply( root, avl_buildlist, (caddr_t) 0, -1, AVL_INORDER );
+	(void) avl_apply( root, avl_buildlist, (void*) 0, -1, AVL_INORDER );
 
 	return( avl_list[ avl_nextlist++ ] );
 }
 
-caddr_t
+void*
 avl_getnext( void )
 {
 	if ( avl_list == 0 )
 		return( 0 );
 
 	if ( avl_nextlist == avl_maxlist ) {
-		free( (caddr_t) avl_list);
-		avl_list = (caddr_t *) 0;
+		free( (void*) avl_list);
+		avl_list = (void* *) 0;
 		return( 0 );
 	}
 
 	return( avl_list[ avl_nextlist++ ] );
 }
 
+/* end non-reentrant code */
+
+
 int
-avl_dup_error( void )
+avl_dup_error( void* left, void* right )
 {
 	return( -1 );
 }
 
 int
-avl_dup_ok( void )
+avl_dup_ok( void* left, void* right )
 {
 	return( 0 );
 }