add ifdefs for SASL_GSS_CREDS to accomodate ancient Cyrus SASL

[openldap] / libraries / liblutil / tavl.c

diff --git a/libraries/liblutil/tavl.c b/libraries/liblutil/tavl.c
index 923356c2ea73436f30e698d13edb0df8d97e73fc..f1a8f71967fa423ab578cfddfba47bf7536fcfa1 100644 (file)
--- 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-2010 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};
 
 /*
@@ -185,12 +189,12 @@ tavl_insert( Avlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
 void*
 tavl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
 {
-       Avlnode *p, *q, *r, *s, *top;
-       int side, side_bf, shorter, nside;
+       Avlnode *p, *q, *r, *top;
+       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 )
@@ -220,16 +224,48 @@ tavl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
 
                /* find the immediate predecessor <q> */
                q = p->avl_link[0];
-               pdir[depth] = 0;
-               pptr[depth++] = p;
+               side = depth;
+               pdir[depth++] = 0;
                while (q->avl_bits[1] == AVL_CHILD && q->avl_link[1]) {
                        pdir[depth] = 1;
                        pptr[depth++] = q;
                        q = q->avl_link[1];
                }
-               /* swap */
-               p->avl_data = q->avl_data;
-               p = q;
+               /* swap links */
+               r = p->avl_link[0];
+               p->avl_link[0] = q->avl_link[0];
+               q->avl_link[0] = r;
+
+               q->avl_link[1] = p->avl_link[1];
+               p->avl_link[1] = q;
+
+               p->avl_bits[0] = q->avl_bits[0];
+               p->avl_bits[1] = q->avl_bits[1];
+               q->avl_bits[0] = q->avl_bits[1] = AVL_CHILD;
+
+               q->avl_bf = p->avl_bf;
+
+               /* fix stack positions: old parent of p points to q */
+               pptr[side] = q;
+               if ( side ) {
+                       r = pptr[side-1];
+                       r->avl_link[pdir[side-1]] = q;
+               } else {
+                       *root = q;
+               }
+               /* new parent of p points to p */
+               if ( depth-side > 1 ) {
+                       r = pptr[depth-1];
+                       r->avl_link[1] = p;
+               } else {
+                       q->avl_link[0] = p;
+               }
+
+               /* fix right subtree: successor of p points to q */
+               r = q->avl_link[1];
+               while ( r->avl_bits[0] == AVL_CHILD && r->avl_link[0] )
+                       r = r->avl_link[0];
+               r->avl_link[0] = q;
        }
 
        /* now <p> has at most one child, get it */
@@ -252,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;
@@ -263,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;
        }
@@ -411,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 )
 {