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