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

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