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