src/libpspp/abt.c

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