Home | History | Annotate | Line # | Download | only in libldap 
      1 /*	$NetBSD: tavl.c,v 1.3 2025/09/05 21:16:21 christos Exp $	*/
      2 
      3 /* avl.c - routines to implement an avl tree */
      4 /* $OpenLDAP$ */
      5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
      6  *
      7  * Copyright 2005-2024 The OpenLDAP Foundation.
      8  * Portions Copyright (c) 2005 by Howard Chu, Symas Corp.
      9  * All rights reserved.
     10  *
     11  * Redistribution and use in source and binary forms, with or without
     12  * modification, are permitted only as authorized by the OpenLDAP
     13  * Public License.
     14  *
     15  * A copy of this license is available in the file LICENSE in the
     16  * top-level directory of the distribution or, alternatively, at
     17  * <http://www.OpenLDAP.org/license.html>.
     18  */
     19 /* ACKNOWLEDGEMENTS:
     20  * This work was initially developed by Howard Chu for inclusion
     21  * in OpenLDAP software.
     22  */
     23 
     24 #include <sys/cdefs.h>
     25 __RCSID("$NetBSD: tavl.c,v 1.3 2025/09/05 21:16:21 christos Exp $");
     26 
     27 #include "portable.h"
     28 
     29 #include <limits.h>
     30 #include <stdio.h>
     31 #include <ac/stdlib.h>
     32 
     33 #ifdef CSRIMALLOC
     34 #define ber_memalloc malloc
     35 #define ber_memrealloc realloc
     36 #define ber_memfree free
     37 #else
     38 #include "lber.h"
     39 #endif
     40 
     41 #define AVL_INTERNAL
     42 #include "ldap_avl.h"
     43 
     44 /* Maximum tree depth this host's address space could support */
     45 #define MAX_TREE_DEPTH	(sizeof(void *) * CHAR_BIT)
     46 
     47 static const int avl_bfs[] = {LH, RH};
     48 
     49 /*
     50  * Threaded AVL trees - for fast in-order traversal of nodes.
     51  */
     52 /*
     53  * ldap_tavl_insert -- insert a node containing data data into the avl tree
     54  * with root root.  fcmp is a function to call to compare the data portion
     55  * of two nodes.  it should take two arguments and return <, >, or == 0,
     56  * depending on whether its first argument is <, >, or == its second
     57  * argument (like strcmp, e.g.).  fdup is a function to call when a duplicate
     58  * node is inserted.  it should return 0, or -1 and its return value
     59  * will be the return value from ldap_avl_insert in the case of a duplicate node.
     60  * the function will be called with the original node's data as its first
     61  * argument and with the incoming duplicate node's data as its second
     62  * argument.  this could be used, for example, to keep a count with each
     63  * node.
     64  *
     65  * NOTE: this routine may malloc memory
     66  */
     67 int
     68 ldap_tavl_insert( TAvlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
     69 {
     70     TAvlnode *t, *p, *s, *q, *r;
     71     int a, cmp, ncmp;
     72 
     73 	if ( *root == NULL ) {
     74 		if (( r = (TAvlnode *) ber_memalloc( sizeof( TAvlnode ))) == NULL ) {
     75 			return( -1 );
     76 		}
     77 		r->avl_link[0] = r->avl_link[1] = NULL;
     78 		r->avl_data = data;
     79 		r->avl_bf = EH;
     80 		r->avl_bits[0] = r->avl_bits[1] = AVL_THREAD;
     81 		*root = r;
     82 
     83 		return( 0 );
     84 	}
     85 
     86     t = NULL;
     87     s = p = *root;
     88 
     89 	/* find insertion point */
     90     while (1) {
     91 		cmp = fcmp( data, p->avl_data );
     92 		if ( cmp == 0 )
     93 			return (*fdup)( p->avl_data, data );
     94 
     95 		cmp = (cmp > 0);
     96 		q = ldap_avl_child( p, cmp );
     97 		if (q == NULL) {
     98 			/* insert */
     99 			if (( q = (TAvlnode *) ber_memalloc( sizeof( TAvlnode ))) == NULL ) {
    100 				return( -1 );
    101 			}
    102 			q->avl_link[cmp] = p->avl_link[cmp];
    103 			q->avl_link[!cmp] = p;
    104 			q->avl_data = data;
    105 			q->avl_bf = EH;
    106 			q->avl_bits[0] = q->avl_bits[1] = AVL_THREAD;
    107 
    108 			p->avl_link[cmp] = q;
    109 			p->avl_bits[cmp] = AVL_CHILD;
    110 			break;
    111 		} else if ( q->avl_bf ) {
    112 			t = p;
    113 			s = q;
    114 		}
    115 		p = q;
    116     }
    117 
    118     /* adjust balance factors */
    119     cmp = fcmp( data, s->avl_data ) > 0;
    120 	r = p = s->avl_link[cmp];
    121 	a = avl_bfs[cmp];
    122 
    123 	while ( p != q ) {
    124 		cmp = fcmp( data, p->avl_data ) > 0;
    125 		p->avl_bf = avl_bfs[cmp];
    126 		p = p->avl_link[cmp];
    127 	}
    128 
    129 	/* checks and balances */
    130 
    131 	if ( s->avl_bf == EH ) {
    132 		s->avl_bf = a;
    133 		return 0;
    134 	} else if ( s->avl_bf == -a ) {
    135 		s->avl_bf = EH;
    136 		return 0;
    137     } else if ( s->avl_bf == a ) {
    138 		cmp = (a > 0);
    139 		ncmp = !cmp;
    140 		if ( r->avl_bf == a ) {
    141 			/* single rotation */
    142 			p = r;
    143 			if ( r->avl_bits[ncmp] == AVL_THREAD ) {
    144 				r->avl_bits[ncmp] = AVL_CHILD;
    145 				s->avl_bits[cmp] = AVL_THREAD;
    146 			} else {
    147 				s->avl_link[cmp] = r->avl_link[ncmp];
    148 				r->avl_link[ncmp] = s;
    149 			}
    150 			s->avl_bf = 0;
    151 			r->avl_bf = 0;
    152 		} else if ( r->avl_bf == -a ) {
    153 			/* double rotation */
    154 			p = r->avl_link[ncmp];
    155 			if ( p->avl_bits[cmp] == AVL_THREAD ) {
    156 				p->avl_bits[cmp] = AVL_CHILD;
    157 				r->avl_bits[ncmp] = AVL_THREAD;
    158 			} else {
    159 				r->avl_link[ncmp] = p->avl_link[cmp];
    160 				p->avl_link[cmp] = r;
    161 			}
    162 			if ( p->avl_bits[ncmp] == AVL_THREAD ) {
    163 				p->avl_bits[ncmp] = AVL_CHILD;
    164 				s->avl_link[cmp] = p;
    165 				s->avl_bits[cmp] = AVL_THREAD;
    166 			} else {
    167 				s->avl_link[cmp] = p->avl_link[ncmp];
    168 				p->avl_link[ncmp] = s;
    169 			}
    170 			if ( p->avl_bf == a ) {
    171 				s->avl_bf = -a;
    172 				r->avl_bf = 0;
    173 			} else if ( p->avl_bf == -a ) {
    174 				s->avl_bf = 0;
    175 				r->avl_bf = a;
    176 			} else {
    177 				s->avl_bf = 0;
    178 				r->avl_bf = 0;
    179 			}
    180 			p->avl_bf = 0;
    181 		}
    182 		/* Update parent */
    183 		if ( t == NULL )
    184 			*root = p;
    185 		else if ( s == t->avl_right )
    186 			t->avl_right = p;
    187 		else
    188 			t->avl_left = p;
    189     }
    190 
    191   return 0;
    192 }
    193 
    194 void*
    195 ldap_tavl_delete( TAvlnode **root, void* data, AVL_CMP fcmp )
    196 {
    197 	TAvlnode *p, *q, *r, *top;
    198 	int side, side_bf, shorter, nside = -1;
    199 
    200 	/* parent stack */
    201 	TAvlnode *pptr[MAX_TREE_DEPTH];
    202 	unsigned char pdir[MAX_TREE_DEPTH];
    203 	int depth = 0;
    204 
    205 	if ( *root == NULL )
    206 		return NULL;
    207 
    208 	p = *root;
    209 
    210 	while (1) {
    211 		side = fcmp( data, p->avl_data );
    212 		if ( !side )
    213 			break;
    214 		side = ( side > 0 );
    215 		pdir[depth] = side;
    216 		pptr[depth++] = p;
    217 
    218 		if ( p->avl_bits[side] == AVL_THREAD )
    219 			return NULL;
    220 		p = p->avl_link[side];
    221 	}
    222 	data = p->avl_data;
    223 
    224 	/* If this node has two children, swap so we are deleting a node with
    225 	 * at most one child.
    226 	 */
    227 	if ( p->avl_bits[0] == AVL_CHILD && p->avl_bits[1] == AVL_CHILD &&
    228 		p->avl_link[0] && p->avl_link[1] ) {
    229 
    230 		/* find the immediate predecessor <q> */
    231 		q = p->avl_link[0];
    232 		side = depth;
    233 		pdir[depth++] = 0;
    234 		while (q->avl_bits[1] == AVL_CHILD && q->avl_link[1]) {
    235 			pdir[depth] = 1;
    236 			pptr[depth++] = q;
    237 			q = q->avl_link[1];
    238 		}
    239 		/* swap links */
    240 		r = p->avl_link[0];
    241 		p->avl_link[0] = q->avl_link[0];
    242 		q->avl_link[0] = r;
    243 
    244 		q->avl_link[1] = p->avl_link[1];
    245 		p->avl_link[1] = q;
    246 
    247 		p->avl_bits[0] = q->avl_bits[0];
    248 		p->avl_bits[1] = q->avl_bits[1];
    249 		q->avl_bits[0] = q->avl_bits[1] = AVL_CHILD;
    250 
    251 		q->avl_bf = p->avl_bf;
    252 
    253 		/* fix stack positions: old parent of p points to q */
    254 		pptr[side] = q;
    255 		if ( side ) {
    256 			r = pptr[side-1];
    257 			r->avl_link[pdir[side-1]] = q;
    258 		} else {
    259 			*root = q;
    260 		}
    261 		/* new parent of p points to p */
    262 		if ( depth-side > 1 ) {
    263 			r = pptr[depth-1];
    264 			r->avl_link[1] = p;
    265 		} else {
    266 			q->avl_link[0] = p;
    267 		}
    268 
    269 		/* fix right subtree: successor of p points to q */
    270 		r = q->avl_link[1];
    271 		while ( r->avl_bits[0] == AVL_CHILD && r->avl_link[0] )
    272 			r = r->avl_link[0];
    273 		r->avl_link[0] = q;
    274 	}
    275 
    276 	/* now <p> has at most one child, get it */
    277 	if ( p->avl_link[0] && p->avl_bits[0] == AVL_CHILD ) {
    278 		q = p->avl_link[0];
    279 		/* Preserve thread continuity */
    280 		r = p->avl_link[1];
    281 		nside = 1;
    282 	} else if ( p->avl_link[1] && p->avl_bits[1] == AVL_CHILD ) {
    283 		q = p->avl_link[1];
    284 		r = p->avl_link[0];
    285 		nside = 0;
    286 	} else {
    287 		q = NULL;
    288 		if ( depth > 0 )
    289 			r = p->avl_link[pdir[depth-1]];
    290 		else
    291 			r = NULL;
    292 	}
    293 
    294 	ber_memfree( p );
    295 
    296 	/* Update child thread */
    297 	if ( q ) {
    298 		for ( ; q->avl_bits[nside] == AVL_CHILD && q->avl_link[nside];
    299 			q = q->avl_link[nside] ) ;
    300 		q->avl_link[nside] = r;
    301 	}
    302 
    303 	if ( !depth ) {
    304 		*root = q;
    305 		return data;
    306 	}
    307 
    308 	/* set the child into p's parent */
    309 	depth--;
    310 	p = pptr[depth];
    311 	side = pdir[depth];
    312 	p->avl_link[side] = q;
    313 
    314 	if ( !q ) {
    315 		p->avl_bits[side] = AVL_THREAD;
    316 		p->avl_link[side] = r;
    317 	}
    318 
    319 	top = NULL;
    320 	shorter = 1;
    321 
    322 	while ( shorter ) {
    323 		p = pptr[depth];
    324 		side = pdir[depth];
    325 		nside = !side;
    326 		side_bf = avl_bfs[side];
    327 
    328 		/* case 1: height unchanged */
    329 		if ( p->avl_bf == EH ) {
    330 			/* Tree is now heavier on opposite side */
    331 			p->avl_bf = avl_bfs[nside];
    332 			shorter = 0;
    333 
    334 		} else if ( p->avl_bf == side_bf ) {
    335 		/* case 2: taller subtree shortened, height reduced */
    336 			p->avl_bf = EH;
    337 		} else {
    338 		/* case 3: shorter subtree shortened */
    339 			if ( depth )
    340 				top = pptr[depth-1]; /* p->parent; */
    341 			else
    342 				top = NULL;
    343 			/* set <q> to the taller of the two subtrees of <p> */
    344 			q = p->avl_link[nside];
    345 			if ( q->avl_bf == EH ) {
    346 				/* case 3a: height unchanged, single rotate */
    347 				if ( q->avl_bits[side] == AVL_THREAD ) {
    348 					q->avl_bits[side] = AVL_CHILD;
    349 					p->avl_bits[nside] = AVL_THREAD;
    350 				} else {
    351 					p->avl_link[nside] = q->avl_link[side];
    352 					q->avl_link[side] = p;
    353 				}
    354 				shorter = 0;
    355 				q->avl_bf = side_bf;
    356 				p->avl_bf = (- side_bf);
    357 
    358 			} else if ( q->avl_bf == p->avl_bf ) {
    359 				/* case 3b: height reduced, single rotate */
    360 				if ( q->avl_bits[side] == AVL_THREAD ) {
    361 					q->avl_bits[side] = AVL_CHILD;
    362 					p->avl_bits[nside] = AVL_THREAD;
    363 				} else {
    364 					p->avl_link[nside] = q->avl_link[side];
    365 					q->avl_link[side] = p;
    366 				}
    367 				shorter = 1;
    368 				q->avl_bf = EH;
    369 				p->avl_bf = EH;
    370 
    371 			} else {
    372 				/* case 3c: height reduced, balance factors opposite */
    373 				r = q->avl_link[side];
    374 				if ( r->avl_bits[nside] == AVL_THREAD ) {
    375 					r->avl_bits[nside] = AVL_CHILD;
    376 					q->avl_bits[side] = AVL_THREAD;
    377 				} else {
    378 					q->avl_link[side] = r->avl_link[nside];
    379 					r->avl_link[nside] = q;
    380 				}
    381 
    382 				if ( r->avl_bits[side] == AVL_THREAD ) {
    383 					r->avl_bits[side] = AVL_CHILD;
    384 					p->avl_bits[nside] = AVL_THREAD;
    385 					p->avl_link[nside] = r;
    386 				} else {
    387 					p->avl_link[nside] = r->avl_link[side];
    388 					r->avl_link[side] = p;
    389 				}
    390 
    391 				if ( r->avl_bf == side_bf ) {
    392 					q->avl_bf = (- side_bf);
    393 					p->avl_bf = EH;
    394 				} else if ( r->avl_bf == (- side_bf)) {
    395 					q->avl_bf = EH;
    396 					p->avl_bf = side_bf;
    397 				} else {
    398 					q->avl_bf = EH;
    399 					p->avl_bf = EH;
    400 				}
    401 				r->avl_bf = EH;
    402 				q = r;
    403 			}
    404 			/* a rotation has caused <q> (or <r> in case 3c) to become
    405 			 * the root.  let <p>'s former parent know this.
    406 			 */
    407 			if ( top == NULL ) {
    408 				*root = q;
    409 			} else if (top->avl_link[0] == p) {
    410 				top->avl_link[0] = q;
    411 			} else {
    412 				top->avl_link[1] = q;
    413 			}
    414 			/* end case 3 */
    415 			p = q;
    416 		}
    417 		if ( !depth )
    418 			break;
    419 		depth--;
    420 	} /* end while(shorter) */
    421 
    422 	return data;
    423 }
    424 
    425 /*
    426  * ldap_tavl_free -- traverse avltree root, freeing the memory it is using.
    427  * the dfree() is called to free the data portion of each node.  The
    428  * number of items actually freed is returned.
    429  */
    430 
    431 int
    432 ldap_tavl_free( TAvlnode *root, AVL_FREE dfree )
    433 {
    434 	int	nleft, nright;
    435 
    436 	if ( root == 0 )
    437 		return( 0 );
    438 
    439 	nleft = ldap_tavl_free( ldap_avl_lchild( root ), dfree );
    440 
    441 	nright = ldap_tavl_free( ldap_avl_rchild( root ), dfree );
    442 
    443 	if ( dfree )
    444 		(*dfree)( root->avl_data );
    445 	ber_memfree( root );
    446 
    447 	return( nleft + nright + 1 );
    448 }
    449 
    450 /*
    451  * ldap_tavl_find -- search avltree root for a node with data data.  the function
    452  * cmp is used to compare things.  it is called with data as its first arg
    453  * and the current node data as its second.  it should return 0 if they match,
    454  * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
    455  */
    456 
    457 /*
    458  * ldap_tavl_find2 - returns TAvlnode instead of data pointer.
    459  * ldap_tavl_find3 - as above, but returns TAvlnode even if no match is found.
    460  *				also set *ret = last comparison result, or -1 if root == NULL.
    461  */
    462 TAvlnode *
    463 ldap_tavl_find3( TAvlnode *root, const void *data, AVL_CMP fcmp, int *ret )
    464 {
    465 	int	cmp = -1, dir;
    466 	TAvlnode *prev = root;
    467 
    468 	while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
    469 		prev = root;
    470 		dir = cmp > 0;
    471 		root = ldap_avl_child( root, dir );
    472 	}
    473 	*ret = cmp;
    474 	return root ? root : prev;
    475 }
    476 
    477 TAvlnode *
    478 ldap_tavl_find2( TAvlnode *root, const void *data, AVL_CMP fcmp )
    479 {
    480 	int	cmp;
    481 
    482 	while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
    483 		cmp = cmp > 0;
    484 		root = ldap_avl_child( root, cmp );
    485 	}
    486 	return root;
    487 }
    488 
    489 void*
    490 ldap_tavl_find( TAvlnode *root, const void* data, AVL_CMP fcmp )
    491 {
    492 	int	cmp;
    493 
    494 	while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
    495 		cmp = cmp > 0;
    496 		root = ldap_avl_child( root, cmp );
    497 	}
    498 
    499 	return( root ? root->avl_data : 0 );
    500 }
    501 
    502 /* Return the leftmost or rightmost node in the tree */
    503 TAvlnode *
    504 ldap_tavl_end( TAvlnode *root, int dir )
    505 {
    506 	if ( root ) {
    507 		while ( root->avl_bits[dir] == AVL_CHILD )
    508 			root = root->avl_link[dir];
    509 	}
    510 	return root;
    511 }
    512 
    513 /* Return the next node in the given direction */
    514 TAvlnode *
    515 ldap_tavl_next( TAvlnode *root, int dir )
    516 {
    517 	if ( root ) {
    518 		int c = root->avl_bits[dir];
    519 
    520 		root = root->avl_link[dir];
    521 		if ( c == AVL_CHILD ) {
    522 			dir ^= 1;
    523 			while ( root->avl_bits[dir] == AVL_CHILD )
    524 				root = root->avl_link[dir];
    525 		}
    526 	}
    527 	return root;
    528 }
    529