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

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