/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
*
- * Copyright 2005 The OpenLDAP Foundation.
+ * Copyright 2005-2013 The OpenLDAP Foundation.
* Portions Copyright (c) 2005 by Howard Chu, Symas Corp.
* All rights reserved.
*
#include "portable.h"
+#include <limits.h>
#include <stdio.h>
#include <ac/stdlib.h>
#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};
/*
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 )
/* 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 */
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;
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;
}
* < 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 )
{