ITS#8625 Separate Avlnode and TAvlnode types

Switch AVL_CHILD/AVL_THREAD values and set Avlnode bits to AVL_CHILD for
better compatibility between avl and tavl as suggested by Howard.

diff --git a/include/avl.h b/include/avl.h
index 677241e686b60d3926aa49afb851c21571959d32..e697ab6e31b92d9cb85e2ab775cafb3f886a4539 100644 (file)
--- a/include/avl.h
+++ b/include/avl.h
@@ -50,9 +50,16 @@ struct avlnode {
 #define avl_lbit       avl_bits[0]
 #define avl_rbit       avl_bits[1]
 
-#ifdef AVL_INTERNAL
+typedef struct tavlnode TAvlnode;
 
-#define NULLAVL        ((Avlnode *) NULL)
+struct tavlnode {
+       void*           avl_data;
+       struct tavlnode *avl_link[2];
+       char            avl_bits[2];
+       signed char             avl_bf;
+};
+
+#ifdef AVL_INTERNAL
 
 /* balance factor values */
 #define LH     (-1)
@@ -62,8 +69,8 @@ struct avlnode {
 #define avl_bf2str(bf) ((bf) == -1 ? "LH" : (bf) == 0 ? "EH" : (bf) == 1 ? "RH" : "(unknown)" )
 
 /* thread bits */
-#define        AVL_THREAD      0
-#define        AVL_CHILD       1
+#define        AVL_CHILD       0
+#define        AVL_THREAD      1
 
 /* avl routines */
 #define avl_getone(x)  ((x) == 0 ? 0 : (x)->avl_data)
@@ -120,31 +127,31 @@ LDAP_AVL_F( int )
 avl_prefixapply LDAP_P((Avlnode *, void*, AVL_CMP, void*, AVL_CMP, void*, int));
 
 LDAP_AVL_F( int )
-tavl_free LDAP_P(( Avlnode *root, AVL_FREE dfree ));
+tavl_free LDAP_P(( TAvlnode *root, AVL_FREE dfree ));
 
 LDAP_AVL_F( int )
-tavl_insert LDAP_P((Avlnode **, void*, AVL_CMP, AVL_DUP));
+tavl_insert LDAP_P((TAvlnode **, void*, AVL_CMP, AVL_DUP));
 
 LDAP_AVL_F( void* )
-tavl_delete LDAP_P((Avlnode **, void*, AVL_CMP));
+tavl_delete LDAP_P((TAvlnode **, void*, AVL_CMP));
 
 LDAP_AVL_F( void* )
-tavl_find LDAP_P((Avlnode *, const void*, AVL_CMP));
+tavl_find LDAP_P((TAvlnode *, const void*, AVL_CMP));
 
-LDAP_AVL_F( Avlnode* )
-tavl_find2 LDAP_P((Avlnode *, const void*, AVL_CMP));
+LDAP_AVL_F( TAvlnode* )
+tavl_find2 LDAP_P((TAvlnode *, const void*, AVL_CMP));
 
-LDAP_AVL_F( Avlnode* )
-tavl_find3 LDAP_P((Avlnode *, const void*, AVL_CMP, int *ret));
+LDAP_AVL_F( TAvlnode* )
+tavl_find3 LDAP_P((TAvlnode *, const void*, AVL_CMP, int *ret));
 
 #define        TAVL_DIR_LEFT   0
 #define        TAVL_DIR_RIGHT  1
 
-LDAP_AVL_F( Avlnode* )
-tavl_end LDAP_P((Avlnode *, int direction ));
+LDAP_AVL_F( TAvlnode* )
+tavl_end LDAP_P((TAvlnode *, int direction));
 
-LDAP_AVL_F( Avlnode* )
-tavl_next LDAP_P((Avlnode *, int direction ));
+LDAP_AVL_F( TAvlnode* )
+tavl_next LDAP_P((TAvlnode *, int direction));
 
 /* apply traversal types */
 #define AVL_PREORDER   1

diff --git a/libraries/liblutil/avl.c b/libraries/liblutil/avl.c
index d38ddcaeb708d6aa57af382cd0ef84caa764f8d7..f05721ce168ef485f48c636c3b1e7977f6f3b296 100644 (file)
--- a/libraries/liblutil/avl.c
+++ b/libraries/liblutil/avl.c
@@ -81,6 +81,7 @@ avl_insert( Avlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
                }
                r->avl_link[0] = r->avl_link[1] = NULL;
                r->avl_data = data;
+               r->avl_bits[0] = r->avl_bits[1] = AVL_CHILD;
                r->avl_bf = EH;
                *root = r;
 
@@ -105,6 +106,7 @@ avl_insert( Avlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
                        }
                        q->avl_link[0] = q->avl_link[1] = NULL;
                        q->avl_data = data;
+                       q->avl_bits[0] = q->avl_bits[1] = AVL_CHILD;
                        q->avl_bf = EH;
 
                        p->avl_link[cmp] = q;

diff --git a/libraries/liblutil/tavl.c b/libraries/liblutil/tavl.c
index 6fd91b080d94c34a0e43f41964b5ab5e1940f68a..5723b519ef6be8e6bbef1ceb70cce440ba19266f 100644 (file)
--- a/libraries/liblutil/tavl.c
+++ b/libraries/liblutil/tavl.c
@@ -60,13 +60,13 @@ static const int avl_bfs[] = {LH, RH};
  * NOTE: this routine may malloc memory
  */
 int
-tavl_insert( Avlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
+tavl_insert( TAvlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
 {
-    Avlnode *t, *p, *s, *q, *r;
+    TAvlnode *t, *p, *s, *q, *r;
     int a, cmp, ncmp;
 
        if ( *root == NULL ) {
-               if (( r = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) {
+               if (( r = (TAvlnode *) ber_memalloc( sizeof( TAvlnode ))) == NULL ) {
                        return( -1 );
                }
                r->avl_link[0] = r->avl_link[1] = NULL;
@@ -91,7 +91,7 @@ tavl_insert( Avlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
                q = avl_child( p, cmp );
                if (q == NULL) {
                        /* insert */
-                       if (( q = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) {
+                       if (( q = (TAvlnode *) ber_memalloc( sizeof( TAvlnode ))) == NULL ) {
                                return( -1 );
                        }
                        q->avl_link[cmp] = p->avl_link[cmp];
@@ -187,13 +187,13 @@ tavl_insert( Avlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
 }
 
 void*
-tavl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
+tavl_delete( TAvlnode **root, void* data, AVL_CMP fcmp )
 {
-       Avlnode *p, *q, *r, *top;
+       TAvlnode *p, *q, *r, *top;
        int side, side_bf, shorter, nside = -1;
 
        /* parent stack */
-       Avlnode *pptr[MAX_TREE_DEPTH];
+       TAvlnode *pptr[MAX_TREE_DEPTH];
        unsigned char pdir[MAX_TREE_DEPTH];
        int depth = 0;
 
@@ -424,7 +424,7 @@ tavl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
  */
 
 int
-tavl_free( Avlnode *root, AVL_FREE dfree )
+tavl_free( TAvlnode *root, AVL_FREE dfree )
 {
        int     nleft, nright;
 
@@ -450,15 +450,15 @@ tavl_free( Avlnode *root, AVL_FREE dfree )
  */
 
 /*
- * tavl_find2 - returns Avlnode instead of data pointer.
- * tavl_find3 - as above, but returns Avlnode even if no match is found.
+ * tavl_find2 - returns TAvlnode instead of data pointer.
+ * tavl_find3 - as above, but returns TAvlnode 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 )
+TAvlnode *
+tavl_find3( TAvlnode *root, const void *data, AVL_CMP fcmp, int *ret )
 {
        int     cmp = -1, dir;
-       Avlnode *prev = root;
+       TAvlnode *prev = root;
 
        while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
                prev = root;
@@ -469,8 +469,8 @@ tavl_find3( Avlnode *root, const void *data, AVL_CMP fcmp, int *ret )
        return root ? root : prev;
 }
 
-Avlnode *
-tavl_find2( Avlnode *root, const void *data, AVL_CMP fcmp )
+TAvlnode *
+tavl_find2( TAvlnode *root, const void *data, AVL_CMP fcmp )
 {
        int     cmp;
 
@@ -482,7 +482,7 @@ tavl_find2( Avlnode *root, const void *data, AVL_CMP fcmp )
 }
 
 void*
-tavl_find( Avlnode *root, const void* data, AVL_CMP fcmp )
+tavl_find( TAvlnode *root, const void* data, AVL_CMP fcmp )
 {
        int     cmp;
 
@@ -495,8 +495,8 @@ tavl_find( Avlnode *root, const void* data, AVL_CMP fcmp )
 }
 
 /* Return the leftmost or rightmost node in the tree */
-Avlnode *
-tavl_end( Avlnode *root, int dir )
+TAvlnode *
+tavl_end( TAvlnode *root, int dir )
 {
        if ( root ) {
                while ( root->avl_bits[dir] == AVL_CHILD )
@@ -506,8 +506,8 @@ tavl_end( Avlnode *root, int dir )
 }
 
 /* Return the next node in the given direction */
-Avlnode *
-tavl_next( Avlnode *root, int dir )
+TAvlnode *
+tavl_next( TAvlnode *root, int dir )
 {
        if ( root ) {
                int c = root->avl_bits[dir];

diff --git a/libraries/liblutil/testtavl.c b/libraries/liblutil/testtavl.c
index 17eae64e9430aaf5783e5aa68bb3fa623e7a41a4..51ec05b45698b6fbd0a2ce5d9a3b2d136741371d 100644 (file)
--- a/libraries/liblutil/testtavl.c
+++ b/libraries/liblutil/testtavl.c
@@ -39,14 +39,14 @@
 #define AVL_INTERNAL
 #include "avl.h"
 
-static void ravl_print LDAP_P(( Avlnode *root, int depth, int thread ));
-static void myprint LDAP_P(( Avlnode *root ));
+static void ravl_print LDAP_P(( TAvlnode *root, int depth, int thread ));
+static void myprint LDAP_P(( TAvlnode *root ));
 static int avl_strcmp LDAP_P(( const void *s, const void *t ));
 
 int
 main( int argc, char **argv )
 {
-       Avlnode *tree = NULL, *n;
+       TAvlnode        *tree = NULL, *n;
        char    command[ 10 ];
        char    name[ 80 ];
        char    *p;
@@ -115,7 +115,7 @@ main( int argc, char **argv )
 static const char bfc_array[] = "\\-/";
 static const char *bfcs = bfc_array+1;
 
-static void ravl_print( Avlnode *root, int depth, int thread )
+static void ravl_print( TAvlnode *root, int depth, int thread )
 {
        int     i;
 
@@ -140,7 +140,7 @@ static void ravl_print( Avlnode *root, int depth, int thread )
        ravl_print( root->avl_link[0], depth+1, root->avl_bits[0] == AVL_THREAD );
 }
 
-static void myprint( Avlnode *root )
+static void myprint( TAvlnode *root )
 {
        printf( "********\n" );
 

diff --git a/servers/slapd/back-mdb/back-mdb.h b/servers/slapd/back-mdb/back-mdb.h
index 9575359415ca271cbb5e7bffcf1b7ddb8e3fac61..9d357fa87bf72c9e5ebc72c0d27762a280779fc1 100644 (file)
--- a/servers/slapd/back-mdb/back-mdb.h
+++ b/servers/slapd/back-mdb/back-mdb.h
@@ -141,7 +141,7 @@ typedef struct mdb_attrinfo {
 #ifdef LDAP_COMP_MATCH
        ComponentReference* ai_cr; /*component indexing*/
 #endif
-       Avlnode *ai_root;               /* for tools */
+       TAvlnode *ai_root;              /* for tools */
        MDB_cursor *ai_cursor;  /* for tools */
        int ai_idx;     /* position in AI array */
        MDB_dbi ai_dbi;

diff --git a/servers/slapd/back-mdb/tools.c b/servers/slapd/back-mdb/tools.c
index b69237d8a6b871e21f121ea6b08bd2a3c7778283..d898c9d293997973c8017c7d90842c5fbb4dcfca 100644 (file)
--- a/servers/slapd/back-mdb/tools.c
+++ b/servers/slapd/back-mdb/tools.c
@@ -1406,7 +1406,7 @@ int mdb_tool_idl_add(
        dbi = ai->ai_dbi;
        for (i=0; keys[i].bv_val; i++) {
        itmp.kstr = keys[i];
-       ic = tavl_find( (Avlnode *)ai->ai_root, &itmp, mdb_tool_idl_cmp );
+       ic = tavl_find( ai->ai_root, &itmp, mdb_tool_idl_cmp );
 
        /* No entry yet, create one */
        if ( !ic ) {
@@ -1428,7 +1428,7 @@ int mdb_tool_idl_add(
                ic->count = 0;
                ic->offset = 0;
                ic->flags = 0;
-               tavl_insert( (Avlnode **)&ai->ai_root, ic, mdb_tool_idl_cmp,
+               tavl_insert( &ai->ai_root, ic, mdb_tool_idl_cmp,
                        avl_dup_error );
 
                /* load existing key count here */

diff --git a/servers/slapd/overlays/pcache.c b/servers/slapd/overlays/pcache.c
index cebf878d70512d4d62f8fd8f7166a97e88a4968f..472e61fcf6ac6da8ef40f070049550f1bdec06ba 100644 (file)
--- a/servers/slapd/overlays/pcache.c
+++ b/servers/slapd/overlays/pcache.c
@@ -65,7 +65,7 @@ typedef struct Query_s {
 struct query_template_s;
 
 typedef struct Qbase_s {
-       Avlnode *scopes[4];             /* threaded AVL trees of cached queries */
+       TAvlnode *scopes[4];            /* threaded AVL trees of cached queries */
        struct berval base;
        int queries;
 } Qbase;
@@ -1272,14 +1272,14 @@ typedef struct fstack {
 } fstack;
 
 static CachedQuery *
-find_filter( Operation *op, Avlnode *root, Filter *inputf, Filter *first )
+find_filter( Operation *op, TAvlnode *root, Filter *inputf, Filter *first )
 {
        Filter* fs;
        Filter* fi;
        MatchingRule* mrule = NULL;
        int res=0, eqpass= 0;
        int ret, rc, dir;
-       Avlnode *ptr;
+       TAvlnode *ptr;
        CachedQuery cq, *qc;
        fstack *stack = NULL, *fsp;
 

diff --git a/servers/slapd/overlays/sssvlv.c b/servers/slapd/overlays/sssvlv.c
index 8df3bf732f234a48c409f3c2be2d519a3859f4b7..3f918d2c817708573bc83393cf5bee6f95764ce8 100644 (file)
--- a/servers/slapd/overlays/sssvlv.c
+++ b/servers/slapd/overlays/sssvlv.c
@@ -105,7 +105,7 @@ typedef struct sssvlv_info
 
 typedef struct sort_op
 {
-       Avlnode *so_tree;
+       TAvlnode *so_tree;
        sort_ctrl *so_ctrl;
        sssvlv_info *so_info;
        int so_paged;
@@ -398,7 +398,7 @@ static void free_sort_op( Connection *conn, sort_op *so )
        int sess_id;
        if ( so->so_tree ) {
                if ( so->so_paged > SLAP_CONTROL_IGNORED ) {
-                       Avlnode *cur_node, *next_node;
+                       TAvlnode *cur_node, *next_node;
                        cur_node = so->so_tree;
                        while ( cur_node ) {
                                next_node = tavl_next( cur_node, TAVL_DIR_RIGHT );
@@ -441,7 +441,7 @@ static void send_list(
        SlapReply               *rs,
        sort_op                 *so)
 {
-       Avlnode *cur_node, *tmp_node;
+       TAvlnode *cur_node, *tmp_node;
        vlv_ctrl *vc = op->o_controls[vlv_cid];
        int i, j, dir, rc;
        BackendDB *be;
@@ -594,8 +594,8 @@ range_err:
 
 static void send_page( Operation *op, SlapReply *rs, sort_op *so )
 {
-       Avlnode         *cur_node               = so->so_tree;
-       Avlnode         *next_node              = NULL;
+       TAvlnode *cur_node = so->so_tree;
+       TAvlnode *next_node = NULL;
        BackendDB *be = op->o_bd;
        Entry *e;
        int rc;
@@ -659,7 +659,7 @@ static void send_entry(
                        send_list( op, rs, so );
                } else {
                        /* Get the first node to send */
-                       Avlnode *start_node = tavl_end(so->so_tree, TAVL_DIR_LEFT);
+                       TAvlnode *start_node = tavl_end(so->so_tree, TAVL_DIR_LEFT);
                        so->so_tree = start_node;
 
                        if ( so->so_paged <= SLAP_CONTROL_IGNORED ) {

diff --git a/servers/slapd/overlays/translucent.c b/servers/slapd/overlays/translucent.c
index e368d4425feda65b494f2a6d98002749a122c15a..c73531495a046ef5b7694f7b1fd650d1aa453e25 100644 (file)
--- a/servers/slapd/overlays/translucent.c
+++ b/servers/slapd/overlays/translucent.c
@@ -766,7 +766,7 @@ typedef struct trans_ctx {
        BackendDB *db;
        slap_overinst *on;
        Filter *orig;
-       Avlnode *list;
+       TAvlnode *list;
        int step;
        int slimit;
        AttributeName *attrs;
@@ -1135,7 +1135,7 @@ static int translucent_search(Operation *op, SlapReply *rs) {
        /* Send out anything remaining on the list and finish */
        if ( tc.step & USE_LIST ) {
                if ( tc.list ) {
-                       Avlnode *av;
+                       TAvlnode *av;
 
                        av = tavl_end( tc.list, TAVL_DIR_LEFT );
                        while ( av ) {