1/* avl.c - routines to implement an avl tree */
2/* $OpenLDAP$ */
3/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 *
5 * Copyright 1998-2011 The OpenLDAP Foundation.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
10 * Public License.
11 *
12 * A copy of this license is available in the file LICENSE in the
13 * top-level directory of the distribution or, alternatively, at
14 * <http://www.OpenLDAP.org/license.html>.
15 */
16/* Portions Copyright (c) 1993 Regents of the University of Michigan.
17 * All rights reserved.
18 *
19 * Redistribution and use in source and binary forms are permitted
20 * provided that this notice is preserved and that due credit is given
21 * to the University of Michigan at Ann Arbor. The name of the University
22 * may not be used to endorse or promote products derived from this
23 * software without specific prior written permission. This software
24 * is provided ``as is'' without express or implied warranty.
25 */
26/* ACKNOWLEDGEMENTS:
27 * This work was originally developed by the University of Michigan
28 * (as part of U-MICH LDAP).  Additional significant contributors
29 * include:
30 *   Howard Y. Chu
31 *   Hallvard B. Furuseth
32 *   Kurt D. Zeilenga
33 */
34
35#include "portable.h"
36
37#include <limits.h>
38#include <stdio.h>
39#include <ac/stdlib.h>
40
41#ifdef CSRIMALLOC
42#define ber_memalloc malloc
43#define ber_memrealloc realloc
44#define ber_memfree free
45#else
46#include "lber.h"
47#endif
48
49#define AVL_INTERNAL
50#include "avl.h"
51
52/* Maximum tree depth this host's address space could support */
53#define MAX_TREE_DEPTH	(sizeof(void *) * CHAR_BIT)
54
55static const int avl_bfs[] = {LH, RH};
56
57/*
58 * avl_insert -- insert a node containing data data into the avl tree
59 * with root root.  fcmp is a function to call to compare the data portion
60 * of two nodes.  it should take two arguments and return <, >, or == 0,
61 * depending on whether its first argument is <, >, or == its second
62 * argument (like strcmp, e.g.).  fdup is a function to call when a duplicate
63 * node is inserted.  it should return 0, or -1 and its return value
64 * will be the return value from avl_insert in the case of a duplicate node.
65 * the function will be called with the original node's data as its first
66 * argument and with the incoming duplicate node's data as its second
67 * argument.  this could be used, for example, to keep a count with each
68 * node.
69 *
70 * NOTE: this routine may malloc memory
71 */
72int
73avl_insert( Avlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
74{
75    Avlnode *t, *p, *s, *q, *r;
76    int a, cmp, ncmp;
77
78	if ( *root == NULL ) {
79		if (( r = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) {
80			return( -1 );
81		}
82		r->avl_link[0] = r->avl_link[1] = NULL;
83		r->avl_data = data;
84		r->avl_bf = EH;
85		*root = r;
86
87		return( 0 );
88	}
89
90    t = NULL;
91    s = p = *root;
92
93	/* find insertion point */
94    while (1) {
95		cmp = fcmp( data, p->avl_data );
96		if ( cmp == 0 )
97			return (*fdup)( p->avl_data, data );
98
99		cmp = (cmp > 0);
100		q = p->avl_link[cmp];
101		if (q == NULL) {
102			/* insert */
103			if (( q = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) {
104				return( -1 );
105			}
106			q->avl_link[0] = q->avl_link[1] = NULL;
107			q->avl_data = data;
108			q->avl_bf = EH;
109
110			p->avl_link[cmp] = q;
111			break;
112		} else if ( q->avl_bf ) {
113			t = p;
114			s = q;
115		}
116		p = q;
117    }
118
119    /* adjust balance factors */
120    cmp = fcmp( data, s->avl_data ) > 0;
121	r = p = s->avl_link[cmp];
122	a = avl_bfs[cmp];
123
124	while ( p != q ) {
125		cmp = fcmp( data, p->avl_data ) > 0;
126		p->avl_bf = avl_bfs[cmp];
127		p = p->avl_link[cmp];
128	}
129
130	/* checks and balances */
131
132	if ( s->avl_bf == EH ) {
133		s->avl_bf = a;
134		return 0;
135	} else if ( s->avl_bf == -a ) {
136		s->avl_bf = EH;
137		return 0;
138    } else if ( s->avl_bf == a ) {
139		cmp = (a > 0);
140		ncmp = !cmp;
141		if ( r->avl_bf == a ) {
142			/* single rotation */
143			p = r;
144			s->avl_link[cmp] = r->avl_link[ncmp];
145			r->avl_link[ncmp] = s;
146			s->avl_bf = 0;
147			r->avl_bf = 0;
148		} else if ( r->avl_bf == -a ) {
149			/* double rotation */
150			p = r->avl_link[ncmp];
151			r->avl_link[ncmp] = p->avl_link[cmp];
152			p->avl_link[cmp] = r;
153			s->avl_link[cmp] = p->avl_link[ncmp];
154			p->avl_link[ncmp] = s;
155
156			if ( p->avl_bf == a ) {
157				s->avl_bf = -a;
158				r->avl_bf = 0;
159			} else if ( p->avl_bf == -a ) {
160				s->avl_bf = 0;
161				r->avl_bf = a;
162			} else {
163				s->avl_bf = 0;
164				r->avl_bf = 0;
165			}
166			p->avl_bf = 0;
167		}
168		/* Update parent */
169		if ( t == NULL )
170			*root = p;
171		else if ( s == t->avl_right )
172			t->avl_right = p;
173		else
174			t->avl_left = p;
175    }
176
177  return 0;
178}
179
180void*
181avl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
182{
183	Avlnode *p, *q, *r, *top;
184	int side, side_bf, shorter, nside;
185
186	/* parent stack */
187	Avlnode *pptr[MAX_TREE_DEPTH];
188	unsigned char pdir[MAX_TREE_DEPTH];
189	int depth = 0;
190
191	if ( *root == NULL )
192		return NULL;
193
194	p = *root;
195
196	while (1) {
197		side = fcmp( data, p->avl_data );
198		if ( !side )
199			break;
200		side = ( side > 0 );
201		pdir[depth] = side;
202		pptr[depth++] = p;
203
204		p = p->avl_link[side];
205		if ( p == NULL )
206			return p;
207	}
208  	data = p->avl_data;
209
210	/* If this node has two children, swap so we are deleting a node with
211	 * at most one child.
212	 */
213	if ( p->avl_link[0] && p->avl_link[1] ) {
214
215		/* find the immediate predecessor <q> */
216		q = p->avl_link[0];
217		side = depth;
218		pdir[depth++] = 0;
219		while (q->avl_link[1]) {
220			pdir[depth] = 1;
221			pptr[depth++] = q;
222			q = q->avl_link[1];
223		}
224		/* swap links */
225		r = p->avl_link[0];
226		p->avl_link[0] = q->avl_link[0];
227		q->avl_link[0] = r;
228
229		q->avl_link[1] = p->avl_link[1];
230		p->avl_link[1] = NULL;
231
232		q->avl_bf = p->avl_bf;
233
234		/* fix stack positions: old parent of p points to q */
235		pptr[side] = q;
236		if ( side ) {
237			r = pptr[side-1];
238			r->avl_link[pdir[side-1]] = q;
239		} else {
240			*root = q;
241		}
242		/* new parent of p points to p */
243		if ( depth-side > 1 ) {
244			r = pptr[depth-1];
245			r->avl_link[1] = p;
246		} else {
247			q->avl_link[0] = p;
248		}
249	}
250
251	/* now <p> has at most one child, get it */
252	q = p->avl_link[0] ? p->avl_link[0] : p->avl_link[1];
253
254	ber_memfree( p );
255
256	if ( !depth ) {
257		*root = q;
258		return data;
259	}
260
261	/* set the child into p's parent */
262	depth--;
263	p = pptr[depth];
264	side = pdir[depth];
265	p->avl_link[side] = q;
266
267	top = NULL;
268	shorter = 1;
269
270	while ( shorter ) {
271		p = pptr[depth];
272		side = pdir[depth];
273		nside = !side;
274		side_bf = avl_bfs[side];
275
276		/* case 1: height unchanged */
277		if ( p->avl_bf == EH ) {
278			/* Tree is now heavier on opposite side */
279			p->avl_bf = avl_bfs[nside];
280			shorter = 0;
281
282		} else if ( p->avl_bf == side_bf ) {
283		/* case 2: taller subtree shortened, height reduced */
284			p->avl_bf = EH;
285		} else {
286		/* case 3: shorter subtree shortened */
287			if ( depth )
288				top = pptr[depth-1]; /* p->parent; */
289			else
290				top = NULL;
291			/* set <q> to the taller of the two subtrees of <p> */
292			q = p->avl_link[nside];
293			if ( q->avl_bf == EH ) {
294				/* case 3a: height unchanged, single rotate */
295				p->avl_link[nside] = q->avl_link[side];
296				q->avl_link[side] = p;
297				shorter = 0;
298				q->avl_bf = side_bf;
299				p->avl_bf = (- side_bf);
300
301			} else if ( q->avl_bf == p->avl_bf ) {
302				/* case 3b: height reduced, single rotate */
303				p->avl_link[nside] = q->avl_link[side];
304				q->avl_link[side] = p;
305				shorter = 1;
306				q->avl_bf = EH;
307				p->avl_bf = EH;
308
309			} else {
310				/* case 3c: height reduced, balance factors opposite */
311				r = q->avl_link[side];
312				q->avl_link[side] = r->avl_link[nside];
313				r->avl_link[nside] = q;
314
315				p->avl_link[nside] = r->avl_link[side];
316				r->avl_link[side] = p;
317
318				if ( r->avl_bf == side_bf ) {
319					q->avl_bf = (- side_bf);
320					p->avl_bf = EH;
321				} else if ( r->avl_bf == (- side_bf)) {
322					q->avl_bf = EH;
323					p->avl_bf = side_bf;
324				} else {
325					q->avl_bf = EH;
326					p->avl_bf = EH;
327				}
328				r->avl_bf = EH;
329				q = r;
330			}
331			/* a rotation has caused <q> (or <r> in case 3c) to become
332			 * the root.  let <p>'s former parent know this.
333			 */
334			if ( top == NULL ) {
335				*root = q;
336			} else if (top->avl_link[0] == p) {
337				top->avl_link[0] = q;
338			} else {
339				top->avl_link[1] = q;
340			}
341			/* end case 3 */
342			p = q;
343		}
344		if ( !depth )
345			break;
346		depth--;
347	} /* end while(shorter) */
348
349	return data;
350}
351
352static int
353avl_inapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
354{
355	if ( root == 0 )
356		return( AVL_NOMORE );
357
358	if ( root->avl_left != 0 )
359		if ( avl_inapply( root->avl_left, fn, arg, stopflag )
360		    == stopflag )
361			return( stopflag );
362
363	if ( (*fn)( root->avl_data, arg ) == stopflag )
364		return( stopflag );
365
366	if ( root->avl_right == 0 )
367		return( AVL_NOMORE );
368	else
369		return( avl_inapply( root->avl_right, fn, arg, stopflag ) );
370}
371
372static int
373avl_postapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
374{
375	if ( root == 0 )
376		return( AVL_NOMORE );
377
378	if ( root->avl_left != 0 )
379		if ( avl_postapply( root->avl_left, fn, arg, stopflag )
380		    == stopflag )
381			return( stopflag );
382
383	if ( root->avl_right != 0 )
384		if ( avl_postapply( root->avl_right, fn, arg, stopflag )
385		    == stopflag )
386			return( stopflag );
387
388	return( (*fn)( root->avl_data, arg ) );
389}
390
391static int
392avl_preapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
393{
394	if ( root == 0 )
395		return( AVL_NOMORE );
396
397	if ( (*fn)( root->avl_data, arg ) == stopflag )
398		return( stopflag );
399
400	if ( root->avl_left != 0 )
401		if ( avl_preapply( root->avl_left, fn, arg, stopflag )
402		    == stopflag )
403			return( stopflag );
404
405	if ( root->avl_right == 0 )
406		return( AVL_NOMORE );
407	else
408		return( avl_preapply( root->avl_right, fn, arg, stopflag ) );
409}
410
411/*
412 * avl_apply -- avl tree root is traversed, function fn is called with
413 * arguments arg and the data portion of each node.  if fn returns stopflag,
414 * the traversal is cut short, otherwise it continues.  Do not use -6 as
415 * a stopflag, as this is what is used to indicate the traversal ran out
416 * of nodes.
417 */
418
419int
420avl_apply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag, int type )
421{
422	switch ( type ) {
423	case AVL_INORDER:
424		return( avl_inapply( root, fn, arg, stopflag ) );
425	case AVL_PREORDER:
426		return( avl_preapply( root, fn, arg, stopflag ) );
427	case AVL_POSTORDER:
428		return( avl_postapply( root, fn, arg, stopflag ) );
429	default:
430		fprintf( stderr, "Invalid traversal type %d\n", type );
431		return( -1 );
432	}
433
434	/* NOTREACHED */
435}
436
437/*
438 * avl_prefixapply - traverse avl tree root, applying function fprefix
439 * to any nodes that match.  fcmp is called with data as its first arg
440 * and the current node's data as its second arg.  it should return
441 * 0 if they match, < 0 if data is less, and > 0 if data is greater.
442 * the idea is to efficiently find all nodes that are prefixes of
443 * some key...  Like avl_apply, this routine also takes a stopflag
444 * and will return prematurely if fmatch returns this value.  Otherwise,
445 * AVL_NOMORE is returned.
446 */
447
448int
449avl_prefixapply(
450    Avlnode	*root,
451    void*	data,
452    AVL_CMP		fmatch,
453    void*	marg,
454    AVL_CMP		fcmp,
455    void*	carg,
456    int		stopflag
457)
458{
459	int	cmp;
460
461	if ( root == 0 )
462		return( AVL_NOMORE );
463
464	cmp = (*fcmp)( data, root->avl_data /* , carg */);
465	if ( cmp == 0 ) {
466		if ( (*fmatch)( root->avl_data, marg ) == stopflag )
467			return( stopflag );
468
469		if ( root->avl_left != 0 )
470			if ( avl_prefixapply( root->avl_left, data, fmatch,
471			    marg, fcmp, carg, stopflag ) == stopflag )
472				return( stopflag );
473
474		if ( root->avl_right != 0 )
475			return( avl_prefixapply( root->avl_right, data, fmatch,
476			    marg, fcmp, carg, stopflag ) );
477		else
478			return( AVL_NOMORE );
479
480	} else if ( cmp < 0 ) {
481		if ( root->avl_left != 0 )
482			return( avl_prefixapply( root->avl_left, data, fmatch,
483			    marg, fcmp, carg, stopflag ) );
484	} else {
485		if ( root->avl_right != 0 )
486			return( avl_prefixapply( root->avl_right, data, fmatch,
487			    marg, fcmp, carg, stopflag ) );
488	}
489
490	return( AVL_NOMORE );
491}
492
493/*
494 * avl_free -- traverse avltree root, freeing the memory it is using.
495 * the dfree() is called to free the data portion of each node.  The
496 * number of items actually freed is returned.
497 */
498
499int
500avl_free( Avlnode *root, AVL_FREE dfree )
501{
502	int	nleft, nright;
503
504	if ( root == 0 )
505		return( 0 );
506
507	nleft = nright = 0;
508	if ( root->avl_left != 0 )
509		nleft = avl_free( root->avl_left, dfree );
510
511	if ( root->avl_right != 0 )
512		nright = avl_free( root->avl_right, dfree );
513
514	if ( dfree )
515		(*dfree)( root->avl_data );
516	ber_memfree( root );
517
518	return( nleft + nright + 1 );
519}
520
521/*
522 * avl_find -- search avltree root for a node with data data.  the function
523 * cmp is used to compare things.  it is called with data as its first arg
524 * and the current node data as its second.  it should return 0 if they match,
525 * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
526 */
527
528Avlnode *
529avl_find2( Avlnode *root, const void *data, AVL_CMP fcmp )
530{
531	int	cmp;
532
533	while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
534		cmp = cmp > 0;
535		root = root->avl_link[cmp];
536	}
537	return root;
538}
539
540void*
541avl_find( Avlnode *root, const void* data, AVL_CMP fcmp )
542{
543	int	cmp;
544
545	while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
546		cmp = cmp > 0;
547		root = root->avl_link[cmp];
548	}
549
550	return( root ? root->avl_data : 0 );
551}
552
553/*
554 * avl_find_lin -- search avltree root linearly for a node with data data.
555 * the function cmp is used to compare things.  it is called with data as its
556 * first arg and the current node data as its second.  it should return 0 if
557 * they match, non-zero otherwise.
558 */
559
560void*
561avl_find_lin( Avlnode *root, const void* data, AVL_CMP fcmp )
562{
563	void*	res;
564
565	if ( root == 0 )
566		return( NULL );
567
568	if ( (*fcmp)( data, root->avl_data ) == 0 )
569		return( root->avl_data );
570
571	if ( root->avl_left != 0 )
572		if ( (res = avl_find_lin( root->avl_left, data, fcmp ))
573		    != NULL )
574			return( res );
575
576	if ( root->avl_right == 0 )
577		return( NULL );
578	else
579		return( avl_find_lin( root->avl_right, data, fcmp ) );
580}
581
582/* NON-REENTRANT INTERFACE */
583
584static void*	*avl_list;
585static int	avl_maxlist;
586static int	avl_nextlist;
587
588#define AVL_GRABSIZE	100
589
590/* ARGSUSED */
591static int
592avl_buildlist( void* data, void* arg )
593{
594	static int	slots;
595
596	if ( avl_list == (void* *) 0 ) {
597		avl_list = (void* *) ber_memalloc(AVL_GRABSIZE * sizeof(void*));
598		slots = AVL_GRABSIZE;
599		avl_maxlist = 0;
600	} else if ( avl_maxlist == slots ) {
601		slots += AVL_GRABSIZE;
602		avl_list = (void* *) ber_memrealloc( (char *) avl_list,
603		    (unsigned) slots * sizeof(void*));
604	}
605
606	avl_list[ avl_maxlist++ ] = data;
607
608	return( 0 );
609}
610
611/*
612 * avl_getfirst() and avl_getnext() are provided as alternate tree
613 * traversal methods, to be used when a single function cannot be
614 * provided to be called with every node in the tree.  avl_getfirst()
615 * traverses the tree and builds a linear list of all the nodes,
616 * returning the first node.  avl_getnext() returns the next thing
617 * on the list built by avl_getfirst().  This means that avl_getfirst()
618 * can take a while, and that the tree should not be messed with while
619 * being traversed in this way, and that multiple traversals (even of
620 * different trees) cannot be active at once.
621 */
622
623void*
624avl_getfirst( Avlnode *root )
625{
626	if ( avl_list ) {
627		ber_memfree( (char *) avl_list);
628		avl_list = (void* *) 0;
629	}
630	avl_maxlist = 0;
631	avl_nextlist = 0;
632
633	if ( root == 0 )
634		return( 0 );
635
636	(void) avl_apply( root, avl_buildlist, (void*) 0, -1, AVL_INORDER );
637
638	return( avl_list[ avl_nextlist++ ] );
639}
640
641void*
642avl_getnext( void )
643{
644	if ( avl_list == 0 )
645		return( 0 );
646
647	if ( avl_nextlist == avl_maxlist ) {
648		ber_memfree( (void*) avl_list);
649		avl_list = (void* *) 0;
650		return( 0 );
651	}
652
653	return( avl_list[ avl_nextlist++ ] );
654}
655
656/* end non-reentrant code */
657
658
659int
660avl_dup_error( void* left, void* right )
661{
662	return( -1 );
663}
664
665int
666avl_dup_ok( void* left, void* right )
667{
668	return( 0 );
669}
670