1/* $NetBSD: tavl.c,v 1.2 2021/08/14 16:14:56 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-2020 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.2 2021/08/14 16:14:56 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 47static 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 */ 67int 68ldap_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 194void* 195ldap_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 431int 432ldap_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 */ 462TAvlnode * 463ldap_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 477TAvlnode * 478ldap_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 489void* 490ldap_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 */ 503TAvlnode * 504ldap_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 */ 514TAvlnode * 515ldap_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