git.sur5r.net Git - openldap/blob - libraries/liblutil/tavl.c

   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-2013 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
  42 static 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  */
  62 int
  63 tavl_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
 189 void*
 190 tavl_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
 426 int
 427 tavl_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  */
 457 Avlnode *
 458 tavl_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
 472 Avlnode *
 473 tavl_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
 484 void*
 485 tavl_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 */
 498 Avlnode *
 499 tavl_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 */
 509 Avlnode *
 510 tavl_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 }