From 2d97c1cae1117629e372aa72a0f81d6ad03907bb Mon Sep 17 00:00:00 2001 From: Howard Chu Date: Fri, 19 May 2006 15:24:16 +0000 Subject: [PATCH] ITS#4549 add tavl_find3() to return closest match --- include/avl.h | 3 +++ libraries/liblutil/tavl.c | 20 ++++++++++++++++++++ 2 files changed, 23 insertions(+) diff --git a/include/avl.h b/include/avl.h index 05315377c0..7b1bafb14e 100644 --- a/include/avl.h +++ b/include/avl.h @@ -134,6 +134,9 @@ tavl_find LDAP_P((Avlnode *, const void*, AVL_CMP)); LDAP_AVL_F( Avlnode* ) tavl_find2 LDAP_P((Avlnode *, const void*, AVL_CMP)); +LDAP_AVL_F( Avlnode* ) +tavl_find3 LDAP_P((Avlnode *, const void*, AVL_CMP, int *ret)); + #define TAVL_DIR_LEFT 0 #define TAVL_DIR_RIGHT 1 diff --git a/libraries/liblutil/tavl.c b/libraries/liblutil/tavl.c index f4a8d84e53..0e7283c554 100644 --- a/libraries/liblutil/tavl.c +++ b/libraries/liblutil/tavl.c @@ -443,6 +443,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 return the last comparison result in ret. + */ +Avlnode * +tavl_find3( Avlnode *root, const void *data, AVL_CMP fcmp, int *ret ) +{ + int cmp, dir; + Avlnode *prev; + + 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 ) { -- 2.39.5