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

   1 /*
   2   Andersson tree library
   3
   4     > Created (Julienne Walker): September 10, 2005
   5     > Corrections (James Bucanek): April 10, 2006
   6       1) Typo in jsw_aerase:
   7            up != 0 should be top != 0
   8       2) Bug in jsw_aerase:
   9            skew ( path[top] ) should be skew ( up )
  10            split ( path[top] ) should be split ( up )
  11       3) Bug in skew and split macros:
  12            Condition should test for nil
  13       4) Bug in jsw_aerase:
  14            Search for successor should save the path
  15 */
  16 #include "jsw_atree.h"
  17
  18 #ifdef __cplusplus
  19 #include <cstdlib>
  20
  21 using std::malloc;
  22 using std::free;
  23 using std::size_t;
  24 #else
  25 #include <stdlib.h>
  26 #endif
  27
  28 #ifndef HEIGHT_LIMIT
  29 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */
  30 #endif
  31
  32 typedef struct jsw_anode {
  33   int               level;   /* Horizontal level for balance */
  34   void             *data;    /* User-defined content */
  35   struct jsw_anode *link[2]; /* Left (0) and right (1) links */
  36 } jsw_anode_t;
  37
  38 struct jsw_atree {
  39   jsw_anode_t *root; /* Top of the tree */
  40   jsw_anode_t *nil;  /* End of tree sentinel */
  41   cmp_f        cmp;  /* Compare two items */
  42   dup_f        dup;  /* Clone an item (user-defined) */
  43   rel_f        rel;  /* Destroy an item (user-defined) */
  44   size_t       size; /* Number of items (user-defined) */
  45 };
  46
  47 struct jsw_atrav {
  48   jsw_atree_t *tree;               /* Paired tree */
  49   jsw_anode_t *it;                 /* Current node */
  50   jsw_anode_t *path[HEIGHT_LIMIT]; /* Traversal path */
  51   size_t       top;                /* Top of stack */
  52 };
  53
  54 /* Remove left horizontal links */
  55 #define skew(t) do {                                      \
  56   if ( t->link[0]->level == t->level && t->level != 0 ) { \
  57     jsw_anode_t *save = t->link[0];                       \
  58     t->link[0] = save->link[1];                           \
  59     save->link[1] = t;                                    \
  60     t = save;                                             \
  61   }                                                       \
  62 } while(0)
  63
  64 /* Remove consecutive horizontal links */
  65 #define split(t) do {                                              \
  66   if ( t->link[1]->link[1]->level == t->level && t->level != 0 ) { \
  67     jsw_anode_t *save = t->link[1];                                \
  68     t->link[1] = save->link[0];                                    \
  69     save->link[0] = t;                                             \
  70     t = save;                                                      \
  71     ++t->level;                                                    \
  72   }                                                                \
  73 } while(0)
  74
  75 static jsw_anode_t *new_node ( jsw_atree_t *tree, void *data )
  76 {
  77   jsw_anode_t *rn = (jsw_anode_t *)malloc ( sizeof *rn );
  78
  79   if ( rn == NULL )
  80     return tree->nil;
  81
  82   rn->level = 1;
  83   rn->data = tree->dup ( data );
  84   rn->link[0] = rn->link[1] = tree->nil;
  85
  86   return rn;
  87 }
  88
  89 jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel )
  90 {
  91   jsw_atree_t *rt = (jsw_atree_t *)malloc ( sizeof *rt );
  92
  93   if ( rt == NULL )
  94     return NULL;
  95
  96   /* Initialize sentinel */
  97   rt->nil = (jsw_anode_t *)malloc ( sizeof *rt->nil );
  98   if ( rt->nil == NULL ) {
  99     free ( rt );
 100     return NULL;
 101   }
 102
 103   rt->nil->data = NULL; /* Simplifies some ops */
 104   rt->nil->level = 0;
 105   rt->nil->link[0] = rt->nil->link[1] = rt->nil;
 106
 107   /* Initialize tree */
 108   rt->root = rt->nil;
 109   rt->cmp = cmp;
 110   rt->dup = dup;
 111   rt->rel = rel;
 112   rt->size = 0;
 113
 114   return rt;
 115 }
 116
 117 void jsw_adelete ( jsw_atree_t *tree )
 118 {
 119   jsw_anode_t *it = tree->root;
 120   jsw_anode_t *save;
 121
 122   /* Destruction by rotation */
 123   while ( it != tree->nil ) {
 124     if ( it->link[0] == tree->nil ) {
 125       /* Remove node */
 126       save = it->link[1];
 127       tree->rel ( it->data );
 128       free ( it );
 129     }
 130     else {
 131       /* Rotate right */
 132       save = it->link[0];
 133       it->link[0] = save->link[1];
 134       save->link[1] = it;
 135     }
 136
 137     it = save;
 138   }
 139
 140   /* Finalize destruction */
 141   free ( tree->nil );
 142   free ( tree );
 143 }
 144
 145 void *jsw_afind ( jsw_atree_t *tree, void *data )
 146 {
 147   jsw_anode_t *it = tree->root;
 148
 149   while ( it != tree->nil ) {
 150     int cmp = tree->cmp ( it->data, data );
 151
 152     if ( cmp == 0 )
 153       break;
 154
 155     it = it->link[cmp < 0];
 156   }
 157
 158   /* nil->data == NULL */
 159   return it->data;
 160 }
 161
 162 int jsw_ainsert ( jsw_atree_t *tree, void *data )
 163 {
 164   if ( tree->root == tree->nil ) {
 165     /* Empty tree case */
 166     tree->root = new_node ( tree, data );
 167     if ( tree->root == tree->nil )
 168       return 0;
 169   }
 170   else {
 171     jsw_anode_t *it = tree->root;
 172     jsw_anode_t *path[HEIGHT_LIMIT];
 173     int top = 0, dir;
 174
 175     /* Find a spot and save the path */
 176     for ( ; ; ) {
 177       path[top++] = it;
 178       dir = tree->cmp ( it->data, data ) < 0;
 179
 180       if ( it->link[dir] == tree->nil )
 181         break;
 182
 183       it = it->link[dir];
 184     }
 185
 186     /* Create a new item */
 187     it->link[dir] = new_node ( tree, data );
 188     if ( it->link[dir] == tree->nil )
 189       return 0;
 190
 191     /* Walk back and rebalance */
 192     while ( --top >= 0 ) {
 193       /* Which child? */
 194       if ( top != 0 )
 195         dir = path[top - 1]->link[1] == path[top];
 196
 197       skew ( path[top] );
 198       split ( path[top] );
 199
 200       /* Fix the parent */
 201       if ( top != 0 )
 202         path[top - 1]->link[dir] = path[top];
 203       else
 204         tree->root = path[top];
 205     }
 206   }
 207
 208   ++tree->size;
 209
 210   return 1;
 211 }
 212
 213 int jsw_aerase ( jsw_atree_t *tree, void *data )
 214 {
 215   if ( tree->root == tree->nil )
 216     return 0;
 217   else {
 218     jsw_anode_t *it = tree->root;
 219     jsw_anode_t *path[HEIGHT_LIMIT];
 220     int top = 0, dir, cmp;
 221
 222     /* Find node to remove and save path */
 223     for ( ; ; ) {
 224       path[top++] = it;
 225
 226       if ( it == tree->nil )
 227         return 0;
 228
 229       cmp = tree->cmp ( it->data, data );
 230       if ( cmp == 0 )
 231         break;
 232
 233       dir = cmp < 0;
 234       it = it->link[dir];
 235     }
 236
 237     /* Remove the found node */
 238     if ( it->link[0] == tree->nil
 239       || it->link[1] == tree->nil )
 240     {
 241       /* Single child case */
 242       int dir2 = it->link[0] == tree->nil;
 243
 244       /* Unlink the item */
 245       if ( --top != 0 )
 246         path[top - 1]->link[dir] = it->link[dir2];
 247       else
 248         tree->root = it->link[1];
 249
 250       tree->rel ( it->data );
 251       free ( it );
 252     }
 253     else {
 254       /* Two child case */
 255       jsw_anode_t *heir = it->link[1];
 256       jsw_anode_t *prev = it;
 257
 258       while ( heir->link[0] != tree->nil ) {
 259         path[top++] = prev = heir;
 260         heir = heir->link[0];
 261       }
 262
 263       /*
 264         Order is important!
 265         (free item, replace item, free heir)
 266       */
 267       tree->rel ( it->data );
 268       it->data = heir->data;
 269       prev->link[prev == it] = heir->link[1];
 270       free ( heir );
 271     }
 272
 273     /* Walk back up and rebalance */
 274     while ( --top >= 0 ) {
 275       jsw_anode_t *up = path[top];
 276
 277       if ( top != 0 )
 278         dir = path[top - 1]->link[1] == up;
 279
 280       /* Rebalance (aka. black magic) */
 281       if ( up->link[0]->level < up->level - 1
 282         || up->link[1]->level < up->level - 1 )
 283       {
 284         if ( up->link[1]->level > --up->level )
 285           up->link[1]->level = up->level;
 286
 287         /* Order is important! */
 288         skew ( up );
 289         skew ( up->link[1] );
 290         skew ( up->link[1]->link[1] );
 291         split ( up );
 292         split ( up->link[1] );
 293       }
 294
 295       /* Fix the parent */
 296       if ( top != 0 )
 297         path[top - 1]->link[dir] = up;
 298       else
 299         tree->root = up;
 300     }
 301   }
 302
 303   --tree->size;
 304
 305   return 1;
 306 }
 307
 308 size_t jsw_asize ( jsw_atree_t *tree )
 309 {
 310   return tree->size;
 311 }
 312
 313 jsw_atrav_t *jsw_atnew ( void )
 314 {
 315   return malloc ( sizeof ( jsw_atrav_t ) );
 316 }
 317
 318 void jsw_atdelete ( jsw_atrav_t *trav )
 319 {
 320   free ( trav );
 321 }
 322
 323 /*
 324   First step in traversal,
 325   handles min and max
 326 */
 327 static void *start ( jsw_atrav_t *trav,
 328   jsw_atree_t *tree, int dir )
 329 {
 330   trav->tree = tree;
 331   trav->it = tree->root;
 332   trav->top = 0;
 333
 334   /* Build a path to work with */
 335   if ( trav->it != tree->nil ) {
 336     while ( trav->it->link[dir] != tree->nil ) {
 337       trav->path[trav->top++] = trav->it;
 338       trav->it = trav->it->link[dir];
 339     }
 340   }
 341
 342   /* Could be nil, but nil->data == NULL */
 343   return trav->it->data;
 344 }
 345
 346 /*
 347   Subsequent traversal steps,
 348   handles ascending and descending
 349 */
 350 static void *move ( jsw_atrav_t *trav, int dir )
 351 {
 352   jsw_anode_t *nil = trav->tree->nil;
 353
 354   if ( trav->it->link[dir] != nil ) {
 355     /* Continue down this branch */
 356     trav->path[trav->top++] = trav->it;
 357     trav->it = trav->it->link[dir];
 358
 359     while ( trav->it->link[!dir] != nil ) {
 360       trav->path[trav->top++] = trav->it;
 361       trav->it = trav->it->link[!dir];
 362     }
 363   }
 364   else {
 365     /* Move to the next branch */
 366     jsw_anode_t *last;
 367
 368     do {
 369       if ( trav->top == 0 ) {
 370         trav->it = nil;
 371         break;
 372       }
 373
 374       last = trav->it;
 375       trav->it = trav->path[--trav->top];
 376     } while ( last == trav->it->link[dir] );
 377   }
 378
 379   /* Could be nil, but nil->data == NULL */
 380   return trav->it->data;
 381 }
 382
 383 void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree )
 384 {
 385   return start ( trav, tree, 0 ); /* Min value */
 386 }
 387
 388 void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree )
 389 {
 390   return start ( trav, tree, 1 ); /* Max value */
 391 }
 392
 393 void *jsw_atnext ( jsw_atrav_t *trav )
 394 {
 395   return move ( trav, 1 ); /* Toward larger items */
 396 }
 397
 398 void *jsw_atprev ( jsw_atrav_t *trav )
 399 {
 400   return move ( trav, 0 ); /* Toward smaller items */
 401 }