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