pd.if.org Git - jsw/blob - jsw_avltree.c

   1 /*
   2   AVL balanced tree library
   3
   4     > Created (Julienne Walker): June 17, 2003
   5     > Modified (Julienne Walker): September 24, 2005
   6 */
   7 #include "jsw_avltree.h"
   8
   9 #ifdef __cplusplus
  10 #include <cstdlib>
  11
  12 using std::malloc;
  13 using std::free;
  14 using std::size_t;
  15 #else
  16 #include <stdlib.h>
  17 #endif
  18
  19 #ifndef HEIGHT_LIMIT
  20 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */
  21 #endif
  22
  23 typedef struct jsw_avlnode {
  24   int                 balance; /* Balance factor */
  25   void               *data;    /* User-defined content */
  26   struct jsw_avlnode *link[2]; /* Left (0) and right (1) links */
  27 } jsw_avlnode_t;
  28
  29 struct jsw_avltree {
  30   jsw_avlnode_t *root; /* Top of the tree */
  31   cmp_f          cmp;    /* Compare two items */
  32   dup_f          dup;    /* Clone an item (user-defined) */
  33   rel_f          rel;    /* Destroy an item (user-defined) */
  34   size_t         size;   /* Number of items (user-defined) */
  35 };
  36
  37 struct jsw_avltrav {
  38   jsw_avltree_t *tree;               /* Paired tree */
  39   jsw_avlnode_t *it;                 /* Current node */
  40   jsw_avlnode_t *path[HEIGHT_LIMIT]; /* Traversal path */
  41   size_t         top;                /* Top of stack */
  42 };
  43
  44 /* Two way single rotation */
  45 #define jsw_single(root,dir) do {         \
  46   jsw_avlnode_t *save = root->link[!dir]; \
  47   root->link[!dir] = save->link[dir];     \
  48   save->link[dir] = root;                 \
  49   root = save;                            \
  50 } while (0)
  51
  52 /* Two way double rotation */
  53 #define jsw_double(root,dir) do {                    \
  54   jsw_avlnode_t *save = root->link[!dir]->link[dir]; \
  55   root->link[!dir]->link[dir] = save->link[!dir];    \
  56   save->link[!dir] = root->link[!dir];               \
  57   root->link[!dir] = save;                           \
  58   save = root->link[!dir];                           \
  59   root->link[!dir] = save->link[dir];                \
  60   save->link[dir] = root;                            \
  61   root = save;                                       \
  62 } while (0)
  63
  64 /* Adjust balance before double rotation */
  65 #define jsw_adjust_balance(root,dir,bal) do { \
  66   jsw_avlnode_t *n = root->link[dir];         \
  67   jsw_avlnode_t *nn = n->link[!dir];          \
  68   if ( nn->balance == 0 )                     \
  69     root->balance = n->balance = 0;           \
  70   else if ( nn->balance == bal ) {            \
  71     root->balance = -bal;                     \
  72     n->balance = 0;                           \
  73   }                                           \
  74   else { /* nn->balance == -bal */            \
  75     root->balance = 0;                        \
  76     n->balance = bal;                         \
  77   }                                           \
  78   nn->balance = 0;                            \
  79 } while (0)
  80
  81 /* Rebalance after insertion */
  82 #define jsw_insert_balance(root,dir) do {  \
  83   jsw_avlnode_t *n = root->link[dir];      \
  84   int bal = dir == 0 ? -1 : +1;            \
  85   if ( n->balance == bal ) {               \
  86     root->balance = n->balance = 0;        \
  87     jsw_single ( root, !dir );             \
  88   }                                        \
  89   else { /* n->balance == -bal */          \
  90     jsw_adjust_balance ( root, dir, bal ); \
  91     jsw_double ( root, !dir );             \
  92   }                                        \
  93 } while (0)
  94
  95 /* Rebalance after deletion */
  96 #define jsw_remove_balance(root,dir,done) do { \
  97   jsw_avlnode_t *n = root->link[!dir];         \
  98   int bal = dir == 0 ? -1 : +1;                \
  99   if ( n->balance == -bal ) {                  \
 100     root->balance = n->balance = 0;            \
 101     jsw_single ( root, dir );                  \
 102   }                                            \
 103   else if ( n->balance == bal ) {              \
 104     jsw_adjust_balance ( root, !dir, -bal );   \
 105     jsw_double ( root, dir );                  \
 106   }                                            \
 107   else { /* n->balance == 0 */                 \
 108     root->balance = -bal;                      \
 109     n->balance = bal;                          \
 110     jsw_single ( root, dir );                  \
 111     done = 1;                                  \
 112   }                                            \
 113 } while (0)
 114
 115 static jsw_avlnode_t *new_node ( jsw_avltree_t *tree, void *data )
 116 {
 117   jsw_avlnode_t *rn = (jsw_avlnode_t *)malloc ( sizeof *rn );
 118
 119   if ( rn == NULL )
 120     return NULL;
 121
 122   rn->balance = 0;
 123   rn->data = tree->dup ( data );
 124   rn->link[0] = rn->link[1] = NULL;
 125
 126   return rn;
 127 }
 128
 129 jsw_avltree_t *jsw_avlnew ( cmp_f cmp, dup_f dup, rel_f rel )
 130 {
 131   jsw_avltree_t *rt = (jsw_avltree_t *)malloc ( sizeof *rt );
 132
 133   if ( rt == NULL )
 134     return NULL;
 135
 136   rt->root = NULL;
 137   rt->cmp = cmp;
 138   rt->dup = dup;
 139   rt->rel = rel;
 140   rt->size = 0;
 141
 142   return rt;
 143 }
 144
 145 void jsw_avldelete ( jsw_avltree_t *tree )
 146 {
 147   jsw_avlnode_t *it = tree->root;
 148   jsw_avlnode_t *save;
 149
 150   /* Destruction by rotation */
 151   while ( it != NULL ) {
 152     if ( it->link[0] == NULL ) {
 153       /* Remove node */
 154       save = it->link[1];
 155       tree->rel ( it->data );
 156       free ( it );
 157     }
 158     else {
 159       /* Rotate right */
 160       save = it->link[0];
 161       it->link[0] = save->link[1];
 162       save->link[1] = it;
 163     }
 164
 165     it = save;
 166   }
 167
 168   free ( tree );
 169 }
 170
 171 void *jsw_avlfind ( jsw_avltree_t *tree, void *data )
 172 {
 173   jsw_avlnode_t *it = tree->root;
 174
 175   while ( it != NULL ) {
 176     int cmp = tree->cmp ( it->data, data );
 177
 178     if ( cmp == 0 )
 179       break;
 180
 181     it = it->link[cmp < 0];
 182   }
 183
 184   return it == NULL ? NULL : it->data;
 185 }
 186
 187 int jsw_avlinsert ( jsw_avltree_t *tree, void *data )
 188 {
 189   /* Empty tree case */
 190   if ( tree->root == NULL ) {
 191     tree->root = new_node ( tree, data );
 192     if ( tree->root == NULL )
 193       return 0;
 194   }
 195   else {
 196     jsw_avlnode_t head = {0}; /* Temporary tree root */
 197     jsw_avlnode_t *s, *t;     /* Place to rebalance and parent */
 198     jsw_avlnode_t *p, *q;     /* Iterator and save pointer */
 199     int dir;
 200
 201     /* Set up false root to ease maintenance */
 202     t = &head;
 203     t->link[1] = tree->root;
 204
 205     /* Search down the tree, saving rebalance points */
 206     for ( s = p = t->link[1]; ; p = q ) {
 207       dir = tree->cmp ( p->data, data ) < 0;
 208       q = p->link[dir];
 209
 210       if ( q == NULL )
 211         break;
 212
 213       if ( q->balance != 0 ) {
 214         t = p;
 215         s = q;
 216       }
 217     }
 218
 219     p->link[dir] = q = new_node ( tree, data );
 220     if ( q == NULL )
 221       return 0;
 222
 223     /* Update balance factors */
 224     for ( p = s; p != q; p = p->link[dir] ) {
 225       dir = tree->cmp ( p->data, data ) < 0;
 226       p->balance += dir == 0 ? -1 : +1;
 227     }
 228
 229     q = s; /* Save rebalance point for parent fix */
 230
 231     /* Rebalance if necessary */
 232     if ( abs ( s->balance ) > 1 ) {
 233       dir = tree->cmp ( s->data, data ) < 0;
 234       jsw_insert_balance ( s, dir );
 235     }
 236
 237     /* Fix parent */
 238     if ( q == head.link[1] )
 239       tree->root = s;
 240     else
 241       t->link[q == t->link[1]] = s;
 242   }
 243
 244   ++tree->size;
 245
 246   return 1;
 247 }
 248
 249 int jsw_avlerase ( jsw_avltree_t *tree, void *data )
 250 {
 251   if ( tree->root != NULL ) {
 252     jsw_avlnode_t *it, *up[HEIGHT_LIMIT];
 253     int upd[HEIGHT_LIMIT], top = 0;
 254     int done = 0;
 255
 256     it = tree->root;
 257
 258     /* Search down tree and save path */
 259     for ( ; ; ) {
 260       if ( it == NULL )
 261         return 0;
 262       else if ( tree->cmp ( it->data, data ) == 0 )
 263         break;
 264
 265       /* Push direction and node onto stack */
 266       upd[top] = tree->cmp ( it->data, data ) < 0;
 267       up[top++] = it;
 268
 269       it = it->link[upd[top - 1]];
 270     }
 271
 272     /* Remove the node */
 273     if ( it->link[0] == NULL || it->link[1] == NULL ) {
 274       /* Which child is not null? */
 275       int dir = it->link[0] == NULL;
 276
 277       /* Fix parent */
 278       if ( top != 0 )
 279         up[top - 1]->link[upd[top - 1]] = it->link[dir];
 280       else
 281         tree->root = it->link[dir];
 282
 283       tree->rel ( it->data );
 284       free ( it );
 285     }
 286     else {
 287       /* Find the inorder successor */
 288       jsw_avlnode_t *heir = it->link[1];
 289       void *save;
 290
 291       /* Save this path too */
 292       upd[top] = 1;
 293       up[top++] = it;
 294
 295       while ( heir->link[0] != NULL ) {
 296         upd[top] = 0;
 297         up[top++] = heir;
 298         heir = heir->link[0];
 299       }
 300
 301       /* Swap data */
 302       save = it->data;
 303       it->data = heir->data;
 304       heir->data = save;
 305
 306       /* Unlink successor and fix parent */
 307       up[top - 1]->link[up[top - 1] == it] = heir->link[1];
 308
 309       tree->rel ( heir->data );
 310       free ( heir );
 311     }
 312
 313     /* Walk back up the search path */
 314     while ( --top >= 0 && !done ) {
 315       /* Update balance factors */
 316       up[top]->balance += upd[top] != 0 ? -1 : +1;
 317
 318       /* Terminate or rebalance as necessary */
 319       if ( abs ( up[top]->balance ) == 1 )
 320         break;
 321       else if ( abs ( up[top]->balance ) > 1 ) {
 322         jsw_remove_balance ( up[top], upd[top], done );
 323
 324         /* Fix parent */
 325         if ( top != 0 )
 326           up[top - 1]->link[upd[top - 1]] = up[top];
 327         else
 328           tree->root = up[0];
 329       }
 330     }
 331
 332     --tree->size;
 333   }
 334
 335   return 1;
 336 }
 337
 338 size_t jsw_avlsize ( jsw_avltree_t *tree )
 339 {
 340   return tree->size;
 341 }
 342
 343 jsw_avltrav_t *jsw_avltnew ( void )
 344 {
 345   return malloc ( sizeof ( jsw_avltrav_t ) );
 346 }
 347
 348 void jsw_avltdelete ( jsw_avltrav_t *trav )
 349 {
 350   free ( trav );
 351 }
 352
 353 /*
 354   First step in traversal,
 355   handles min and max
 356 */
 357 static void *start ( jsw_avltrav_t *trav, jsw_avltree_t *tree, int dir )
 358 {
 359   trav->tree = tree;
 360   trav->it = tree->root;
 361   trav->top = 0;
 362
 363   /* Build a path to work with */
 364   if ( trav->it != NULL ) {
 365     while ( trav->it->link[dir] != NULL ) {
 366       trav->path[trav->top++] = trav->it;
 367       trav->it = trav->it->link[dir];
 368     }
 369   }
 370
 371   return trav->it == NULL ? NULL : trav->it->data;
 372 }
 373
 374 /*
 375   Subsequent traversal steps,
 376   handles ascending and descending
 377 */
 378 static void *move ( jsw_avltrav_t *trav, int dir )
 379 {
 380   if ( trav->it->link[dir] != NULL ) {
 381     /* Continue down this branch */
 382     trav->path[trav->top++] = trav->it;
 383     trav->it = trav->it->link[dir];
 384
 385     while ( trav->it->link[!dir] != NULL ) {
 386       trav->path[trav->top++] = trav->it;
 387       trav->it = trav->it->link[!dir];
 388     }
 389   }
 390   else {
 391     /* Move to the next branch */
 392     jsw_avlnode_t *last;
 393
 394     do {
 395       if ( trav->top == 0 ) {
 396         trav->it = NULL;
 397         break;
 398       }
 399
 400       last = trav->it;
 401       trav->it = trav->path[--trav->top];
 402     } while ( last == trav->it->link[dir] );
 403   }
 404
 405   return trav->it == NULL ? NULL : trav->it->data;
 406 }
 407
 408 void *jsw_avltfirst ( jsw_avltrav_t *trav, jsw_avltree_t *tree )
 409 {
 410   return start ( trav, tree, 0 ); /* Min value */
 411 }
 412
 413 void *jsw_avltlast ( jsw_avltrav_t *trav, jsw_avltree_t *tree )
 414 {
 415   return start ( trav, tree, 1 ); /* Max value */
 416 }
 417
 418 void *jsw_avltnext ( jsw_avltrav_t *trav )
 419 {
 420   return move ( trav, 1 ); /* Toward larger items */
 421 }
 422
 423 void *jsw_avltprev ( jsw_avltrav_t *trav )
 424 {
 425   return move ( trav, 0 ); /* Toward smaller items */
 426 }