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

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