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