src/libpspp/tower.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 #include <config.h>
  18
  19 #include <libpspp/tower.h>
  20
  21 #include <limits.h>
  22
  23 #include <libpspp/assertion.h>
  24 #include <libpspp/compiler.h>
  25
  26 static struct tower_node *abt_to_tower_node (const struct abt_node *);
  27 static struct tower_node *first_node (const struct tower *);
  28 static struct tower_node *last_node (const struct tower *);
  29 static struct tower_node *next_node (const struct tower *,
  30                                      const struct tower_node *);
  31 static struct tower_node *prev_node (const struct tower *,
  32                                      const struct tower_node *);
  33 static unsigned long int get_subtree_height (const struct abt_node *);
  34 static void reaugment_tower_node (struct abt_node *,
  35                                   const struct abt_node *,
  36                                   const struct abt_node *,
  37                                   const void *aux);
  38
  39 /* Initializes T as an empty tower. */
  40 void
  41 tower_init (struct tower *t)
  42 {
  43   abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
  44   t->cache_bottom = ULONG_MAX;
  45 }
  46
  47 /* Returns true if T contains no nodes, false otherwise. */
  48 bool
  49 tower_is_empty (const struct tower *t)
  50 {
  51   return t->abt.root == NULL;
  52 }
  53
  54 /* Returns the total height of tower T. */
  55 unsigned long
  56 tower_height (const struct tower *t)
  57 {
  58   return get_subtree_height (t->abt.root);
  59 }
  60
  61 /* Inserts node NEW with the specified HEIGHT into T just below
  62    node UNDER, or at the top of T if UNDER is a null pointer. */
  63 void
  64 tower_insert (struct tower *t, unsigned long height, struct tower_node *new,
  65               struct tower_node *under)
  66 {
  67   assert (height > 0);
  68   new->height = height;
  69   abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
  70                      &new->abt_node);
  71   t->cache_bottom = ULONG_MAX;
  72 }
  73
  74 /* Deletes NODE from tower T. */
  75 struct tower_node *
  76 tower_delete (struct tower *t, struct tower_node *node)
  77 {
  78   struct tower_node *next = next_node (t, node);
  79   abt_delete (&t->abt, &node->abt_node);
  80   t->cache_bottom = ULONG_MAX;
  81   return next;
  82 }
  83
  84 /* Changes the height of NODE in tower T to NEW_HEIGHT. */
  85 void
  86 tower_resize (struct tower *t, struct tower_node *node,
  87               unsigned long new_height)
  88 {
  89   assert (new_height > 0);
  90   node->height = new_height;
  91   abt_reaugmented (&t->abt, &node->abt_node);
  92   t->cache_bottom = ULONG_MAX;
  93 }
  94
  95 /* Removes nodes FIRST through LAST (exclusive) from tower SRC
  96    and splices them into tower DST just below node UNDER, or at
  97    the top of DST if UNDER is a null pointer.
  98
  99    It might be better to implement an abt_splice function and
 100    turn this into a wrapper, but the asymptotic performance would
 101    be the same. */
 102 void
 103 tower_splice (struct tower *dst, struct tower_node *under,
 104               struct tower *src,
 105               struct tower_node *first, struct tower_node *last)
 106 {
 107   struct tower_node *next;
 108
 109   /* Conceptually, DST == SRC is valid.
 110      Practically, it's more difficult to get it right, and our
 111      client code doesn't need it. */
 112   assert (dst != src);
 113
 114   for (; first != last; first = next)
 115     {
 116       next = tower_delete (src, first);
 117       abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
 118                          &first->abt_node);
 119     }
 120   dst->cache_bottom = src->cache_bottom = ULONG_MAX;
 121 }
 122
 123 /* Returns the node at the given HEIGHT from the bottom of tower
 124    T.  HEIGHT must be less than T's height (as returned by
 125    tower_height).  Stores in *NODE_START the height of the bottom
 126    of the returned node, which may be less than HEIGHT if HEIGHT
 127    refers to the middle of a node instead of its bottom. */
 128 struct tower_node *
 129 tower_lookup (const struct tower *t_,
 130               unsigned long height,
 131               unsigned long *node_start)
 132 {
 133   struct tower *t = (struct tower *) t_;
 134   struct abt_node *p;
 135
 136   assert (height < tower_height (t));
 137
 138   if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->height)
 139     {
 140       *node_start = t->cache_bottom;
 141       return t->cache;
 142     }
 143
 144   *node_start = 0;
 145   p = t->abt.root;
 146   for (;;)
 147     {
 148       unsigned long left_height = get_subtree_height (p->down[0]);
 149       if (height < left_height)
 150         {
 151           /* Our goal height must lie within the left subtree. */
 152           p = p->down[0];
 153         }
 154       else
 155         {
 156           /* Our goal height cannot be in the left subtree. */
 157           struct tower_node *node = abt_to_tower_node (p);
 158           unsigned long int node_height = node->height;
 159
 160           height -= left_height;
 161           *node_start += left_height;
 162           if (height < node_height)
 163             {
 164               /* Our goal height is in P. */
 165               t->cache = node;
 166               t->cache_bottom = *node_start;
 167               return node;
 168             }
 169           else
 170             {
 171               /* Our goal height is in the right subtree. */
 172               p = p->down[1];
 173               height -= node_height;
 174               *node_start += node_height;
 175             }
 176         }
 177     }
 178 }
 179
 180 /* Returns the node at height 0 in tower T, or a null pointer if
 181    T is empty. */
 182 struct tower_node *
 183 tower_first (const struct tower *t)
 184 {
 185   return first_node (t);
 186 }
 187
 188 /* Returns the node at the top of tower T, or a null pointer if T
 189    is empty. */
 190 struct tower_node *
 191 tower_last (const struct tower *t)
 192 {
 193   return last_node (t);
 194 }
 195
 196 /* If NODE is nonnull, returns the node just above NODE in tower
 197    T, or a null pointer if NODE is the topmost node in T.
 198    If NODE is null, acts like tower_first. */
 199 struct tower_node *
 200 tower_next (const struct tower *t, const struct tower_node *node)
 201 {
 202   return node != NULL ? next_node (t, node) : first_node (t);
 203 }
 204
 205 /* If NODE is nonnull, returns the node just below NODE in tower
 206    T, or a null pointer if NODE is the bottommost node in T.
 207    If NODE is null, acts like tower_last. */
 208 struct tower_node *
 209 tower_prev (const struct tower *t, const struct tower_node *node)
 210 {
 211   return node != NULL ? prev_node (t, node) : last_node (t);
 212 }
 213 \f
 214 /* Returns the tower node corresponding to the given ABT_NODE. */
 215 static struct tower_node *
 216 abt_to_tower_node (const struct abt_node *abt_node)
 217 {
 218   return abt_data (abt_node, struct tower_node, abt_node);
 219 }
 220
 221 /* Returns the tower node corresponding to the given ABT_NODE. */
 222 static struct tower_node *
 223 abt_to_tower_node_null (const struct abt_node *abt_node)
 224 {
 225   return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
 226 }
 227
 228 /* Returns the first node in TOWER. */
 229 static struct tower_node *
 230 first_node (const struct tower *t)
 231 {
 232   return abt_to_tower_node_null (abt_first (&t->abt));
 233 }
 234
 235 /* Returns the first node in TOWER. */
 236 static struct tower_node *
 237 last_node (const struct tower *t)
 238 {
 239   return abt_to_tower_node_null (abt_last (&t->abt));
 240 }
 241
 242 /* Returns the next node in TOWER after NODE. */
 243 static struct tower_node *
 244 next_node (const struct tower *t, const struct tower_node *node)
 245 {
 246   return abt_to_tower_node_null (abt_next (&t->abt, &node->abt_node));
 247 }
 248
 249 /* Returns the previous node in TOWER before NODE. */
 250 static struct tower_node *
 251 prev_node (const struct tower *t, const struct tower_node *node)
 252 {
 253   return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
 254 }
 255
 256 /* Returns the total height of the nodes in the subtree rooted at
 257    P, or 0 if P is null. */
 258 static unsigned long int
 259 get_subtree_height (const struct abt_node *p)
 260 {
 261   return p != NULL ? abt_to_tower_node (p)->subtree_height : 0;
 262 }
 263
 264 /* Recalculates the subtree_height of NODE based on its LEFT and
 265    RIGHT children's subtree_heights. */
 266 static void
 267 reaugment_tower_node (struct abt_node *node_,
 268                       const struct abt_node *left,
 269                       const struct abt_node *right,
 270                       const void *aux UNUSED)
 271 {
 272   struct tower_node *node = abt_to_tower_node (node_);
 273   node->subtree_height = node->height;
 274   if (left != NULL)
 275     node->subtree_height += abt_to_tower_node (left)->subtree_height;
 276   if (right != NULL)
 277     node->subtree_height += abt_to_tower_node (right)->subtree_height;
 278 }