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