X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Ftower.c;h=863da820c3bf081ec1ed374d36a6411ceade7f9e;hb=50800683562f7eaa3d8872b71163bbdcfb1d9ea5;hp=95eb9c2c7dd47f3aa2c5dd5b28cf18b640780a3d;hpb=f5c108becd49d78f4898cab11352291f5689d24e;p=pspp
diff --git a/src/libpspp/tower.c b/src/libpspp/tower.c
index 95eb9c2c7d..863da820c3 100644
--- a/src/libpspp/tower.c
+++ b/src/libpspp/tower.c
@@ -1,29 +1,28 @@
-/* PSPP - computes sample statistics.
- Copyright (C) 2007 Free Software Foundation, Inc.
+/* PSPP - a program for statistical analysis.
+ Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.
- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of the
- License, or (at your option) any later version.
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
- This program is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
- 02110-1301, USA. */
+ along with this program. If not, see . */
#include
-#include
+#include "libpspp/tower.h"
#include
-#include
-#include
+#include "libpspp/assertion.h"
+#include "libpspp/cast.h"
+#include "libpspp/compiler.h"
static struct tower_node *abt_to_tower_node (const struct abt_node *);
static struct tower_node *first_node (const struct tower *);
@@ -32,12 +31,59 @@ static struct tower_node *next_node (const struct tower *,
const struct tower_node *);
static struct tower_node *prev_node (const struct tower *,
const struct tower_node *);
-static unsigned long int get_subtree_height (const struct abt_node *);
+static unsigned long int get_subtree_size (const struct abt_node *);
+static unsigned long int get_subtree_count (const struct abt_node *);
static void reaugment_tower_node (struct abt_node *,
const struct abt_node *,
const struct abt_node *,
const void *aux);
+/* Returns the height of the bottom of the given tower NODE.
+
+ The performance of this function is O(lg n) in the number of
+ nodes in the tower. It is often possible to avoid calling
+ this function, either by taking advantage of the NODE_START
+ parameter to tower_lookup or by incrementally keeping track of
+ height while iterating through a tower. In the former case
+ the asymptotic performance is no different, since tower_lookup
+ is also O(lg n), but in the latter case performance improves
+ from O(lg n) to O(1). */
+unsigned long int
+tower_node_get_level (const struct tower_node *node)
+{
+ const struct abt_node *p = &node->abt_node;
+ unsigned long level = get_subtree_size (p->down[0]);
+ while (p->up != NULL)
+ {
+ if (p == p->up->down[1])
+ level += (get_subtree_size (p->up->down[0])
+ + abt_to_tower_node (p->up)->size);
+ p = p->up;
+ }
+ return level;
+}
+
+/* Returns the index of the given tower NODE.
+
+ The performance of this function is O(lg n) in the number of
+ nodes in the tower. It is often possible to avoid calling
+ this function by keeping track of the index while iterating
+ through a tower. Doing so when possible will improve
+ performance from O(lg n) to O(1). */
+unsigned long int
+tower_node_get_index (const struct tower_node *node)
+{
+ const struct abt_node *p = &node->abt_node;
+ unsigned long index = get_subtree_count (p->down[0]);
+ while (p->up != NULL)
+ {
+ if (p == p->up->down[1])
+ index += get_subtree_count (p->up->down[0]) + 1;
+ p = p->up;
+ }
+ return index;
+}
+
/* Initializes T as an empty tower. */
void
tower_init (struct tower *t)
@@ -53,21 +99,28 @@ tower_is_empty (const struct tower *t)
return t->abt.root == NULL;
}
+/* Returns the number of nodes in tower T. */
+unsigned long int
+tower_count (const struct tower *t)
+{
+ return get_subtree_count (t->abt.root);
+}
+
/* Returns the total height of tower T. */
unsigned long
tower_height (const struct tower *t)
{
- return get_subtree_height (t->abt.root);
+ return get_subtree_size (t->abt.root);
}
-/* Inserts node NEW with the specified HEIGHT into T just below
+/* Inserts node NEW with the specified SIZE into T just below
node UNDER, or at the top of T if UNDER is a null pointer. */
void
-tower_insert (struct tower *t, unsigned long height, struct tower_node *new,
+tower_insert (struct tower *t, unsigned long size, struct tower_node *new,
struct tower_node *under)
{
- assert (height > 0);
- new->height = height;
+ assert (size > 0);
+ new->size = size;
abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
&new->abt_node);
t->cache_bottom = ULONG_MAX;
@@ -83,13 +136,13 @@ tower_delete (struct tower *t, struct tower_node *node)
return next;
}
-/* Changes the height of NODE in tower T to NEW_HEIGHT. */
+/* Changes the size of NODE in tower T to NEW_SIZE. */
void
tower_resize (struct tower *t, struct tower_node *node,
- unsigned long new_height)
+ unsigned long new_size)
{
- assert (new_height > 0);
- node->height = new_height;
+ assert (new_size > 0);
+ node->size = new_size;
abt_reaugmented (&t->abt, &node->abt_node);
t->cache_bottom = ULONG_MAX;
}
@@ -132,12 +185,12 @@ tower_lookup (const struct tower *t_,
unsigned long height,
unsigned long *node_start)
{
- struct tower *t = (struct tower *) t_;
+ struct tower *t = CONST_CAST (struct tower *, t_);
struct abt_node *p;
assert (height < tower_height (t));
- if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->height)
+ if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->size)
{
*node_start = t->cache_bottom;
return t->cache;
@@ -147,8 +200,8 @@ tower_lookup (const struct tower *t_,
p = t->abt.root;
for (;;)
{
- unsigned long left_height = get_subtree_height (p->down[0]);
- if (height < left_height)
+ unsigned long left_size = get_subtree_size (p->down[0]);
+ if (height < left_size)
{
/* Our goal height must lie within the left subtree. */
p = p->down[0];
@@ -157,11 +210,11 @@ tower_lookup (const struct tower *t_,
{
/* Our goal height cannot be in the left subtree. */
struct tower_node *node = abt_to_tower_node (p);
- unsigned long int node_height = node->height;
+ unsigned long int node_size = node->size;
- height -= left_height;
- *node_start += left_height;
- if (height < node_height)
+ height -= left_size;
+ *node_start += left_size;
+ if (height < node_size)
{
/* Our goal height is in P. */
t->cache = node;
@@ -172,13 +225,40 @@ tower_lookup (const struct tower *t_,
{
/* Our goal height is in the right subtree. */
p = p->down[1];
- height -= node_height;
- *node_start += node_height;
+ height -= node_size;
+ *node_start += node_size;
}
}
}
}
+/* Returns the node with the given 0-based INDEX, which must be
+ less than the number of nodes in T (as returned by
+ tower_count). */
+struct tower_node *
+tower_get (const struct tower *t_, unsigned long int index)
+{
+ struct tower *t = CONST_CAST (struct tower *, t_);
+ struct abt_node *p;
+
+ assert (index < tower_count (t));
+
+ p = t->abt.root;
+ for (;;)
+ {
+ unsigned long left_count = get_subtree_count (p->down[0]);
+ if (index < left_count)
+ p = p->down[0];
+ else if (index == left_count)
+ return abt_to_tower_node (p);
+ else
+ {
+ p = p->down[1];
+ index -= left_count + 1;
+ }
+ }
+}
+
/* Returns the node at height 0 in tower T, or a null pointer if
T is empty. */
struct tower_node *
@@ -255,16 +335,24 @@ prev_node (const struct tower *t, const struct tower_node *node)
return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
}
-/* Returns the total height of the nodes in the subtree rooted at
+/* Returns the total size of the nodes in the subtree rooted at
P, or 0 if P is null. */
static unsigned long int
-get_subtree_height (const struct abt_node *p)
+get_subtree_size (const struct abt_node *p)
+{
+ return p != NULL ? abt_to_tower_node (p)->subtree_size : 0;
+}
+
+/* Returns the total number of nodes in the subtree rooted at P,
+ or 0 if P is null. */
+static unsigned long int
+get_subtree_count (const struct abt_node *p)
{
- return p != NULL ? abt_to_tower_node (p)->subtree_height : 0;
+ return p != NULL ? abt_to_tower_node (p)->subtree_count : 0;
}
-/* Recalculates the subtree_height of NODE based on its LEFT and
- RIGHT children's subtree_heights. */
+/* Recalculates the subtree_size of NODE based on its LEFT and
+ RIGHT children's subtree_sizes. */
static void
reaugment_tower_node (struct abt_node *node_,
const struct abt_node *left,
@@ -272,9 +360,18 @@ reaugment_tower_node (struct abt_node *node_,
const void *aux UNUSED)
{
struct tower_node *node = abt_to_tower_node (node_);
- node->subtree_height = node->height;
- if (left != NULL)
- node->subtree_height += abt_to_tower_node (left)->subtree_height;
- if (right != NULL)
- node->subtree_height += abt_to_tower_node (right)->subtree_height;
+ node->subtree_size = node->size;
+ node->subtree_count = 1;
+ if (left != NULL)
+ {
+ struct tower_node *left_node = abt_to_tower_node (left);
+ node->subtree_size += left_node->subtree_size;
+ node->subtree_count += left_node->subtree_count;
+ }
+ if (right != NULL)
+ {
+ struct tower_node *right_node = abt_to_tower_node (right);
+ node->subtree_size += right_node->subtree_size;
+ node->subtree_count += right_node->subtree_count;
+ }
}