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