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