src/libpspp/abt.c

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