pintos-os.org Git - pspp/blob - src/libpspp/tower.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009, 2011 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/cast.h"
  25 #include "libpspp/compiler.h"
  26
  27 static struct tower_node *abt_to_tower_node (const struct abt_node *);
  28 static struct tower_node *first_node (const struct tower *);
  29 static struct tower_node *last_node (const struct tower *);
  30 static struct tower_node *next_node (const struct tower *,
  31                                      const struct tower_node *);
  32 static struct tower_node *prev_node (const struct tower *,
  33                                      const struct tower_node *);
  34 static unsigned long int get_subtree_size (const struct abt_node *);
  35 static unsigned long int get_subtree_count (const struct abt_node *);
  36 static void reaugment_tower_node (struct abt_node *, const void *aux);
  37
  38 /* Returns the height of the bottom of the given tower NODE.
  39
  40    The performance of this function is O(lg n) in the number of
  41    nodes in the tower.  It is often possible to avoid calling
  42    this function, either by taking advantage of the NODE_START
  43    parameter to tower_lookup or by incrementally keeping track of
  44    height while iterating through a tower.  In the former case
  45    the asymptotic performance is no different, since tower_lookup
  46    is also O(lg n), but in the latter case performance improves
  47    from O(lg n) to O(1). */
  48 unsigned long int
  49 tower_node_get_level (const struct tower_node *node)
  50 {
  51   const struct abt_node *p = &node->abt_node;
  52   unsigned long level = get_subtree_size (p->down[0]);
  53   while (p->up != NULL)
  54     {
  55       if (p == p->up->down[1])
  56         level += (get_subtree_size (p->up->down[0])
  57                   + abt_to_tower_node (p->up)->size);
  58       p = p->up;
  59     }
  60   return level;
  61 }
  62
  63 /* Returns the index of the given tower NODE.
  64
  65    The performance of this function is O(lg n) in the number of
  66    nodes in the tower.  It is often possible to avoid calling
  67    this function by keeping track of the index while iterating
  68    through a tower.  Doing so when possible will improve
  69    performance from O(lg n) to O(1). */
  70 unsigned long int
  71 tower_node_get_index (const struct tower_node *node)
  72 {
  73   const struct abt_node *p = &node->abt_node;
  74   unsigned long index = get_subtree_count (p->down[0]);
  75   while (p->up != NULL)
  76     {
  77       if (p == p->up->down[1])
  78         index += get_subtree_count (p->up->down[0]) + 1;
  79       p = p->up;
  80     }
  81   return index;
  82 }
  83
  84 /* Initializes T as an empty tower. */
  85 void
  86 tower_init (struct tower *t)
  87 {
  88   abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
  89   t->cache_bottom = ULONG_MAX;
  90 }
  91
  92 /* Returns true if T contains no nodes, false otherwise. */
  93 bool
  94 tower_is_empty (const struct tower *t)
  95 {
  96   return t->abt.root == NULL;
  97 }
  98
  99 /* Returns the number of nodes in tower T. */
 100 unsigned long int
 101 tower_count (const struct tower *t)
 102 {
 103   return get_subtree_count (t->abt.root);
 104 }
 105
 106 /* Returns the total height of tower T. */
 107 unsigned long
 108 tower_height (const struct tower *t)
 109 {
 110   return get_subtree_size (t->abt.root);
 111 }
 112
 113 /* Inserts node NEW with the specified SIZE into T just below
 114    node UNDER, or at the top of T if UNDER is a null pointer. */
 115 void
 116 tower_insert (struct tower *t, unsigned long size, struct tower_node *new,
 117               struct tower_node *under)
 118 {
 119   assert (size > 0);
 120   new->size = size;
 121   abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
 122                      &new->abt_node);
 123   t->cache_bottom = ULONG_MAX;
 124 }
 125
 126 /* Deletes NODE from tower T. */
 127 struct tower_node *
 128 tower_delete (struct tower *t, struct tower_node *node)
 129 {
 130   struct tower_node *next = next_node (t, node);
 131   abt_delete (&t->abt, &node->abt_node);
 132   t->cache_bottom = ULONG_MAX;
 133   return next;
 134 }
 135
 136 /* Changes the size of NODE in tower T to NEW_SIZE. */
 137 void
 138 tower_resize (struct tower *t, struct tower_node *node,
 139               unsigned long new_size)
 140 {
 141   assert (new_size > 0);
 142   node->size = new_size;
 143   abt_reaugmented (&t->abt, &node->abt_node);
 144   t->cache_bottom = ULONG_MAX;
 145 }
 146
 147 /* Removes nodes FIRST through LAST (exclusive) from tower SRC
 148    and splices them into tower DST just below node UNDER, or at
 149    the top of DST if UNDER is a null pointer.
 150
 151    It might be better to implement an abt_splice function and
 152    turn this into a wrapper, but the asymptotic performance would
 153    be the same. */
 154 void
 155 tower_splice (struct tower *dst, struct tower_node *under,
 156               struct tower *src,
 157               struct tower_node *first, struct tower_node *last)
 158 {
 159   struct tower_node *next;
 160
 161   /* Conceptually, DST == SRC is valid.
 162      Practically, it's more difficult to get it right, and our
 163      client code doesn't need it. */
 164   assert (dst != src);
 165
 166   for (; first != last; first = next)
 167     {
 168       next = tower_delete (src, first);
 169       abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
 170                          &first->abt_node);
 171     }
 172   dst->cache_bottom = src->cache_bottom = ULONG_MAX;
 173 }
 174
 175 /* Returns the node at the given HEIGHT from the bottom of tower
 176    T.  HEIGHT must be less than T's height (as returned by
 177    tower_height).  Stores in *NODE_START the height of the bottom
 178    of the returned node, which may be less than HEIGHT if HEIGHT
 179    refers to the middle of a node instead of its bottom. */
 180 struct tower_node *
 181 tower_lookup (const struct tower *t_,
 182               unsigned long height,
 183               unsigned long *node_start)
 184 {
 185   struct tower *t = CONST_CAST (struct tower *, t_);
 186   struct abt_node *p;
 187
 188   assert (height < tower_height (t));
 189
 190   if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->size)
 191     {
 192       *node_start = t->cache_bottom;
 193       return t->cache;
 194     }
 195
 196   *node_start = 0;
 197   p = t->abt.root;
 198   for (;;)
 199     {
 200       unsigned long left_size = get_subtree_size (p->down[0]);
 201       if (height < left_size)
 202         {
 203           /* Our goal height must lie within the left subtree. */
 204           p = p->down[0];
 205         }
 206       else
 207         {
 208           /* Our goal height cannot be in the left subtree. */
 209           struct tower_node *node = abt_to_tower_node (p);
 210           unsigned long int node_size = node->size;
 211
 212           height -= left_size;
 213           *node_start += left_size;
 214           if (height < node_size)
 215             {
 216               /* Our goal height is in P. */
 217               t->cache = node;
 218               t->cache_bottom = *node_start;
 219               return node;
 220             }
 221           else
 222             {
 223               /* Our goal height is in the right subtree. */
 224               p = p->down[1];
 225               height -= node_size;
 226               *node_start += node_size;
 227             }
 228         }
 229     }
 230 }
 231
 232 /* Returns the node with the given 0-based INDEX, which must be
 233    less than the number of nodes in T (as returned by
 234    tower_count). */
 235 struct tower_node *
 236 tower_get (const struct tower *t_, unsigned long int index)
 237 {
 238   struct tower *t = CONST_CAST (struct tower *, t_);
 239   struct abt_node *p;
 240
 241   assert (index < tower_count (t));
 242
 243   p = t->abt.root;
 244   for (;;)
 245     {
 246       unsigned long left_count = get_subtree_count (p->down[0]);
 247       if (index < left_count)
 248         p = p->down[0];
 249       else if (index == left_count)
 250         return abt_to_tower_node (p);
 251       else
 252         {
 253           p = p->down[1];
 254           index -= left_count + 1;
 255         }
 256     }
 257 }
 258
 259 /* Returns the node at height 0 in tower T, or a null pointer if
 260    T is empty. */
 261 struct tower_node *
 262 tower_first (const struct tower *t)
 263 {
 264   return first_node (t);
 265 }
 266
 267 /* Returns the node at the top of tower T, or a null pointer if T
 268    is empty. */
 269 struct tower_node *
 270 tower_last (const struct tower *t)
 271 {
 272   return last_node (t);
 273 }
 274
 275 /* If NODE is nonnull, returns the node just above NODE in tower
 276    T, or a null pointer if NODE is the topmost node in T.
 277    If NODE is null, acts like tower_first. */
 278 struct tower_node *
 279 tower_next (const struct tower *t, const struct tower_node *node)
 280 {
 281   return node != NULL ? next_node (t, node) : first_node (t);
 282 }
 283
 284 /* If NODE is nonnull, returns the node just below NODE in tower
 285    T, or a null pointer if NODE is the bottommost node in T.
 286    If NODE is null, acts like tower_last. */
 287 struct tower_node *
 288 tower_prev (const struct tower *t, const struct tower_node *node)
 289 {
 290   return node != NULL ? prev_node (t, node) : last_node (t);
 291 }
 292 \f
 293 /* Returns the tower node corresponding to the given ABT_NODE. */
 294 static struct tower_node *
 295 abt_to_tower_node (const struct abt_node *abt_node)
 296 {
 297   return abt_data (abt_node, struct tower_node, abt_node);
 298 }
 299
 300 /* Returns the tower node corresponding to the given ABT_NODE. */
 301 static struct tower_node *
 302 abt_to_tower_node_null (const struct abt_node *abt_node)
 303 {
 304   return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
 305 }
 306
 307 /* Returns the first node in TOWER. */
 308 static struct tower_node *
 309 first_node (const struct tower *t)
 310 {
 311   return abt_to_tower_node_null (abt_first (&t->abt));
 312 }
 313
 314 /* Returns the first node in TOWER. */
 315 static struct tower_node *
 316 last_node (const struct tower *t)
 317 {
 318   return abt_to_tower_node_null (abt_last (&t->abt));
 319 }
 320
 321 /* Returns the next node in TOWER after NODE. */
 322 static struct tower_node *
 323 next_node (const struct tower *t, const struct tower_node *node)
 324 {
 325   return abt_to_tower_node_null (abt_next (&t->abt, &node->abt_node));
 326 }
 327
 328 /* Returns the previous node in TOWER before NODE. */
 329 static struct tower_node *
 330 prev_node (const struct tower *t, const struct tower_node *node)
 331 {
 332   return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
 333 }
 334
 335 /* Returns the total size of the nodes in the subtree rooted at
 336    P, or 0 if P is null. */
 337 static unsigned long int
 338 get_subtree_size (const struct abt_node *p)
 339 {
 340   return p != NULL ? abt_to_tower_node (p)->subtree_size : 0;
 341 }
 342
 343 /* Returns the total number of nodes in the subtree rooted at P,
 344    or 0 if P is null. */
 345 static unsigned long int
 346 get_subtree_count (const struct abt_node *p)
 347 {
 348   return p != NULL ? abt_to_tower_node (p)->subtree_count : 0;
 349 }
 350
 351 /* Recalculates the subtree_size of NODE based on the subtree_sizes of its
 352    children. */
 353 static void
 354 reaugment_tower_node (struct abt_node *node_, const void *aux UNUSED)
 355 {
 356   struct tower_node *node = abt_to_tower_node (node_);
 357   node->subtree_size = node->size;
 358   node->subtree_count = 1;
 359
 360   if (node->abt_node.down[0] != NULL)
 361     {
 362       struct tower_node *left = abt_to_tower_node (node->abt_node.down[0]);
 363       node->subtree_size += left->subtree_size;
 364       node->subtree_count += left->subtree_count;
 365     }
 366
 367   if (node->abt_node.down[1] != NULL)
 368     {
 369       struct tower_node *right = abt_to_tower_node (node->abt_node.down[1]);
 370       node->subtree_size += right->subtree_size;
 371       node->subtree_count += right->subtree_count;
 372     }
 373 }