src/libpspp/abt.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 /* Augmented binary tree (ABT) data structure. */
  18
  19 /* These library routines have no external dependencies other
  20    than the standard C library.
  21
  22    If you add routines in this file, please add a corresponding
  23    test to abt-test.c.  This test program should achieve 100%
  24    coverage of lines and branches in this code, as reported by
  25    "gcov -b". */
  26
  27 #ifdef HAVE_CONFIG_H
  28 #include <config.h>
  29 #endif
  30
  31 #include <libpspp/abt.h>
  32 #include <libpspp/cast.h>
  33
  34 #include <stdbool.h>
  35
  36 #include <libpspp/assertion.h>
  37
  38 static struct abt_node **down_link (struct abt *, struct abt_node *);
  39 static struct abt_node *skew (struct abt *, struct abt_node *);
  40 static struct abt_node *split (struct abt *, struct abt_node *);
  41
  42 /* Initializes ABT as an empty ABT that uses COMPARE and
  43    REAUGMENT functions, passing in AUX as auxiliary data.
  44
  45    The comparison function is optional.  If it is null, this
  46    indicates that the tree is being used for its augmentations
  47    only.  ABT functions that compare nodes may not be used with
  48    trees that lack comparison functions; contrariwise, other
  49    functions that could disrupt the ordering of a tree may not be
  50    used if a comparison function is specified.  Refer to
  51    individual function descriptions for details. */
  52 void
  53 abt_init (struct abt *abt,
  54           abt_compare_func *compare,
  55           abt_reaugment_func *reaugment,
  56           const void *aux)
  57 {
  58   assert (reaugment != NULL);
  59   abt->root = NULL;
  60   abt->compare = compare;
  61   abt->reaugment = reaugment;
  62   abt->aux = aux;
  63 }
  64
  65 /* Inserts the given NODE into ABT.
  66    Returns a null pointer if successful.
  67    Returns the existing node already in ABT equal to NODE, on
  68    failure.
  69    This function may be used only if ABT has a comparison
  70    function. */
  71 struct abt_node *
  72 abt_insert (struct abt *abt, struct abt_node *node)
  73 {
  74   node->down[0] = NULL;
  75   node->down[1] = NULL;
  76   node->level = 1;
  77
  78   if (abt->root == NULL)
  79     {
  80       abt->root = node;
  81       node->up = NULL;
  82       abt_reaugmented (abt, node);
  83     }
  84   else
  85     {
  86       struct abt_node *p = abt->root;
  87       for (;;)
  88         {
  89           int cmp, dir;
  90
  91           cmp = abt->compare (node, p, abt->aux);
  92           if (cmp == 0)
  93             return p;
  94
  95           dir = cmp > 0;
  96           if (p->down[dir] == NULL)
  97             {
  98               p->down[dir] = node;
  99               node->up = p;
 100               abt_reaugmented (abt, node);
 101               break;
 102             }
 103           p = p->down[dir];
 104         }
 105     }
 106
 107   while ((node = node->up) != NULL)
 108     {
 109       node = skew (abt, node);
 110       node = split (abt, node);
 111     }
 112
 113   return NULL;
 114 }
 115
 116 /* Inserts NODE before or after node P in ABT, depending on the
 117    value of AFTER.
 118    If P is null, then the node is inserted as the first node in
 119    the tree, if AFTER is true, or the last node, if AFTER is
 120    false. */
 121 static inline void
 122 insert_relative (struct abt *abt, const struct abt_node *p, bool after,
 123                  struct abt_node *node)
 124 {
 125   node->down[0] = NULL;
 126   node->down[1] = NULL;
 127   node->level = 1;
 128
 129   if (abt->root == NULL)
 130     {
 131       assert (p == NULL);
 132       abt->root = node;
 133       node->up = NULL;
 134       abt_reaugmented (abt, node);
 135     }
 136   else
 137     {
 138       int dir = after;
 139       if (p == NULL)
 140         {
 141           p = abt->root;
 142           dir = !after;
 143         }
 144       while (p->down[dir] != NULL)
 145         {
 146           p = p->down[dir];
 147           dir = !after;
 148         }
 149       CONST_CAST (struct abt_node *, p)->down[dir] = node;
 150       node->up = CONST_CAST (struct abt_node *, p);
 151       abt_reaugmented (abt, node);
 152     }
 153
 154   while ((node = node->up) != NULL)
 155     {
 156       node = skew (abt, node);
 157       node = split (abt, node);
 158     }
 159 }
 160
 161 /* Inserts NODE after node P in ABT.
 162    If P is null, then the node is inserted as the first node in
 163    the tree.
 164    This function may be used only if ABT lacks a comparison
 165    function. */
 166 void
 167 abt_insert_after (struct abt *abt,
 168                   const struct abt_node *p, struct abt_node *node)
 169 {
 170   assert (abt->compare == NULL);
 171   insert_relative (abt, p, true, node);
 172 }
 173
 174 /* Inserts NODE before node P in ABT.
 175    If P is null, then the node is inserted as the last node in
 176    the tree.
 177    This function may be used only if ABT lacks a comparison
 178    function. */
 179 void
 180 abt_insert_before (struct abt *abt,
 181                    const struct abt_node *p, struct abt_node *node)
 182 {
 183   assert (abt->compare == NULL);
 184   insert_relative (abt, p, false, node);
 185 }
 186
 187 /* Deletes P from ABT. */
 188 void
 189 abt_delete (struct abt *abt, struct abt_node *p)
 190 {
 191   struct abt_node **q = down_link (abt, p);
 192   struct abt_node *r = p->down[1];
 193   if (r == NULL)
 194     {
 195       *q = NULL;
 196       p = p->up;
 197     }
 198   else if (r->down[0] == NULL)
 199     {
 200       r->down[0] = p->down[0];
 201       *q = r;
 202       r->up = p->up;
 203       if (r->down[0] != NULL)
 204         r->down[0]->up = r;
 205       r->level = p->level;
 206       p = r;
 207     }
 208   else
 209     {
 210       struct abt_node *s = r->down[0];
 211       while (s->down[0] != NULL)
 212         s = s->down[0];
 213       r = s->up;
 214       r->down[0] = s->down[1];
 215       s->down[0] = p->down[0];
 216       s->down[1] = p->down[1];
 217       *q = s;
 218       s->down[0]->up = s;
 219       s->down[1]->up = s;
 220       s->up = p->up;
 221       s->level = p->level;
 222       if (r->down[0] != NULL)
 223         r->down[0]->up = r;
 224       p = r;
 225     }
 226   abt_reaugmented (abt, p);
 227
 228   for (; p != NULL; p = p->up)
 229     if ((p->down[0] != NULL ? p->down[0]->level : 0) < p->level - 1
 230         || (p->down[1] != NULL ? p->down[1]->level : 0) < p->level - 1)
 231       {
 232         p->level--;
 233         if (p->down[1] != NULL && p->down[1]->level > p->level)
 234           p->down[1]->level = p->level;
 235
 236         p = skew (abt, p);
 237         skew (abt, p->down[1]);
 238         if (p->down[1]->down[1] != NULL)
 239           skew (abt, p->down[1]->down[1]);
 240
 241         p = split (abt, p);
 242         split (abt, p->down[1]);
 243       }
 244 }
 245
 246 /* Returns the node with minimum value in ABT, or a null pointer
 247    if ABT is empty. */
 248 struct abt_node *
 249 abt_first (const struct abt *abt)
 250 {
 251   struct abt_node *p = abt->root;
 252   if (p != NULL)
 253     while (p->down[0] != NULL)
 254       p = p->down[0];
 255   return p;
 256 }
 257
 258 /* Returns the node with maximum value in ABT, or a null pointer
 259    if ABT is empty. */
 260 struct abt_node *
 261 abt_last (const struct abt *abt)
 262 {
 263   struct abt_node *p = abt->root;
 264   if (p != NULL)
 265     while (p->down[1] != NULL)
 266       p = p->down[1];
 267   return p;
 268 }
 269
 270 /* Searches ABT for a node equal to TARGET.
 271    Returns the node if found, or a null pointer otherwise.
 272    This function may be used only if ABT has a comparison
 273    function. */
 274 struct abt_node *
 275 abt_find (const struct abt *abt, const struct abt_node *target)
 276 {
 277   const struct abt_node *p;
 278   int cmp;
 279
 280   for (p = abt->root; p != NULL; p = p->down[cmp > 0])
 281     {
 282       cmp = abt->compare (target, p, abt->aux);
 283       if (cmp == 0)
 284         return CONST_CAST (struct abt_node *, p);
 285     }
 286
 287   return NULL;
 288 }
 289
 290 /* Returns the node in ABT following P in in-order.
 291    If P is null, returns the minimum node in ABT.
 292    Returns a null pointer if P is the maximum node in ABT or if P
 293    is null and ABT is empty. */
 294 struct abt_node *
 295 abt_next (const struct abt *abt, const struct abt_node *p)
 296 {
 297   if (p == NULL)
 298     return abt_first (abt);
 299   else if (p->down[1] == NULL)
 300     {
 301       struct abt_node *q;
 302       for (q = p->up; ; p = q, q = q->up)
 303         if (q == NULL || p == q->down[0])
 304           return q;
 305     }
 306   else
 307     {
 308       p = p->down[1];
 309       while (p->down[0] != NULL)
 310         p = p->down[0];
 311       return CONST_CAST (struct abt_node *, p);
 312     }
 313 }
 314
 315 /* Returns the node in ABT preceding P in in-order.
 316    If P is null, returns the maximum node in ABT.
 317    Returns a null pointer if P is the minimum node in ABT or if P
 318    is null and ABT is empty. */
 319 struct abt_node *
 320 abt_prev (const struct abt *abt, const struct abt_node *p)
 321 {
 322   if (p == NULL)
 323     return abt_last (abt);
 324   else if (p->down[0] == NULL)
 325     {
 326       struct abt_node *q;
 327       for (q = p->up; ; p = q, q = q->up)
 328         if (q == NULL || p == q->down[1])
 329           return q;
 330     }
 331   else
 332     {
 333       p = p->down[0];
 334       while (p->down[1] != NULL)
 335         p = p->down[1];
 336       return CONST_CAST (struct abt_node *, p);
 337     }
 338 }
 339
 340 /* Calls ABT's reaugmentation function to compensate for
 341    augmentation data in P having been modified.  Use abt_changed,
 342    instead, if the key data in P has changed.
 343
 344    It is not safe to update more than one node's augmentation
 345    data, then to call this function for each node.  Instead,
 346    update a single node's data, call this function, update
 347    another node's data, and so on.  Alternatively, remove all
 348    affected nodes from the tree, update their values, then
 349    re-insert all of them. */
 350 void
 351 abt_reaugmented (const struct abt *abt, struct abt_node *p)
 352 {
 353   for (; p != NULL; p = p->up)
 354     abt->reaugment (p, p->down[0], p->down[1], abt->aux);
 355 }
 356
 357 /* Moves P around in ABT to compensate for its key having
 358    changed.  Returns a null pointer if successful.  If P's new
 359    value is equal to that of some other node in ABT, returns the
 360    other node after removing P from ABT.
 361
 362    This function is an optimization only if it is likely that P
 363    can actually retain its relative position in ABT, e.g. its key
 364    has only been adjusted slightly.  Otherwise, it is more
 365    efficient to simply remove P from ABT, change its key, and
 366    re-insert P.
 367
 368    It is not safe to update more than one node's key, then to
 369    call this function for each node.  Instead, update a single
 370    node's key, call this function, update another node's key, and
 371    so on.  Alternatively, remove all affected nodes from the
 372    tree, update their keys, then re-insert all of them.
 373
 374    This function may be used only if ABT has a comparison
 375    function.  If it doesn't, then you probably just want
 376    abt_reaugmented. */
 377 struct abt_node *
 378 abt_changed (struct abt *abt, struct abt_node *p)
 379 {
 380   struct abt_node *prev = abt_prev (abt, p);
 381   struct abt_node *next = abt_next (abt, p);
 382
 383   if ((prev != NULL && abt->compare (prev, p, abt->aux) >= 0)
 384       || (next != NULL && abt->compare (p, next, abt->aux) >= 0))
 385     {
 386       abt_delete (abt, p);
 387       return abt_insert (abt, p);
 388     }
 389   else
 390     {
 391       abt_reaugmented (abt, p);
 392       return NULL;
 393     }
 394 }
 395
 396 /* ABT nodes may be moved around in memory as necessary, e.g. as
 397    the result of an realloc operation on a block that contains a
 398    node.  Once this is done, call this function passing node P
 399    that was moved and its ABT before attempting any other
 400    operation on ABT.
 401
 402    It is not safe to move more than one node, then to call this
 403    function for each node.  Instead, move a single node, call
 404    this function, move another node, and so on.  Alternatively,
 405    remove all affected nodes from the tree, move them, then
 406    re-insert all of them.
 407
 408    This function may be used only if ABT has a comparison
 409    function. */
 410 void
 411 abt_moved (struct abt *abt, struct abt_node *p)
 412 {
 413   if (p->up != NULL)
 414     {
 415       int d = p->up->down[0] == NULL || abt->compare (p, p->up, abt->aux) > 0;
 416       p->up->down[d] = p;
 417     }
 418   else
 419     abt->root = p;
 420   if (p->down[0] != NULL)
 421     p->down[0]->up = p;
 422   if (p->down[1] != NULL)
 423     p->down[1]->up = p;
 424 }
 425 \f
 426 /* Returns the address of the pointer that points down to P
 427    within ABT. */
 428 static struct abt_node **
 429 down_link (struct abt *abt, struct abt_node *p)
 430 {
 431   return (p->up != NULL
 432           ? &p->up->down[p->up->down[0] != p]
 433           : &abt->root);
 434 }
 435
 436 /* Remove a left "horizontal link" at A, if present.
 437    Returns the node that occupies the position previously
 438    occupied by A. */
 439 static struct abt_node *
 440 skew (struct abt *abt, struct abt_node *a)
 441 {
 442   struct abt_node *b = a->down[0];
 443   if (b != NULL && b->level == a->level)
 444     {
 445       /* Rotate right. */
 446       a->down[0] = b->down[1];
 447       b->down[1] = a;
 448       *down_link (abt, a) = b;
 449
 450       if (a->down[0] != NULL)
 451         a->down[0]->up = a;
 452       b->up = a->up;
 453       a->up = b;
 454
 455       abt->reaugment (a, a->down[0], a->down[1], abt->aux);
 456       abt->reaugment (b, b->down[0], b->down[1], abt->aux);
 457
 458       return b;
 459     }
 460   else
 461     return a;
 462 }
 463
 464 /* Removes a pair of consecutive right "horizontal links" at A,
 465    if present.
 466    Returns the node that occupies the position previously
 467    occupied by A. */
 468 static struct abt_node *
 469 split (struct abt *abt, struct abt_node *a)
 470 {
 471   struct abt_node *b = a->down[1];
 472   if (b != NULL && b->down[1] != NULL && b->down[1]->level == a->level)
 473     {
 474       /* Rotate left. */
 475       a->down[1] = b->down[0];
 476       b->down[0] = a;
 477       *down_link (abt, a) = b;
 478
 479       if (a->down[1] != NULL)
 480         a->down[1]->up = a;
 481       b->up = a->up;
 482       a->up = b;
 483
 484       b->level++;
 485
 486       abt->reaugment (a, a->down[0], a->down[1], abt->aux);
 487       abt->reaugment (b, b->down[0], b->down[1], abt->aux);
 488
 489       return b;
 490     }
 491   else
 492     return a;
 493 }