[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: tower.[ch]
|
From: |
Ben Pfaff |
|
Subject: |
Re: tower.[ch] |
|
Date: |
Fri, 21 Nov 2008 21:58:58 -0800 |
|
User-agent: |
Gnus/5.11 (Gnus v5.11) Emacs/22.2 (gnu/linux) |
John Darrington <address@hidden> writes:
> Since the situation is similar to the "pile of books" analogy as
> described in the comment in src/libpspp/tower.h, I thought I could use
> that. However, there doesn't seem to be any way 1) to get a
> tower_node by index; or 2) given a tower_node (or index), find out how
> far from the "ground level" this node starts.
>
> If tower.[ch] can be made to do this in less than linear time, then I
> think we can use this to make operations on the datasheet much faster.
Here is a pair of patches, to be applied sequentially, that add
such support to the tower code. Is this what you are looking
for?
commit 56e6ea6d522df8e5ee87c4b0fa9825e482ffa767
Author: Ben Pfaff <address@hidden>
Date: Fri Nov 21 20:30:49 2008 -0800
tower: Don't refer to two different quantities as "height".
The tower code uses the word "height" for both the height of a
node off the table and the thickness of a node. That's confusing.
Use the word "size" for thickness, instead, to clarify.
diff --git a/src/data/datasheet.c b/src/data/datasheet.c
index a11a1e5..fd07ed3 100644
--- a/src/data/datasheet.c
+++ b/src/data/datasheet.c
@@ -693,7 +693,7 @@ axis_clone (const struct axis *old)
for (node = tower_first (&old->log_to_phy); node != NULL;
node = tower_next (&old->log_to_phy, node))
{
- unsigned long int size = tower_node_get_height (node);
+ unsigned long int size = tower_node_get_size (node);
struct axis_group *group = tower_data (node, struct axis_group, logical);
tower_insert (&new->log_to_phy, size, make_axis_group (group->phy_start),
NULL);
@@ -717,7 +717,7 @@ axis_hash (const struct axis *axis, struct md4_ctx *ctx)
{
struct axis_group *group = tower_data (tn, struct axis_group, logical);
unsigned long int phy_start = group->phy_start;
- unsigned long int size = tower_node_get_height (tn);
+ unsigned long int size = tower_node_get_size (tn);
md4_process_bytes (&phy_start, sizeof phy_start, ctx);
md4_process_bytes (&size, sizeof size, ctx);
@@ -921,7 +921,7 @@ split_axis (struct axis *axis, unsigned long int where)
if (where > group_start)
{
unsigned long int size_1 = where - group_start;
- unsigned long int size_2 = tower_node_get_height (group_node) - size_1;
+ unsigned long int size_2 = tower_node_get_size (group_node) - size_1;
struct tower_node *next = tower_next (&axis->log_to_phy, group_node);
struct tower_node *new = make_axis_group (group->phy_start + size_1);
tower_resize (&axis->log_to_phy, group_node, size_1);
@@ -961,11 +961,11 @@ merge_axis_nodes (struct axis *axis, struct tower_node
*node,
if (next != NULL)
{
struct axis_group *next_group = axis_group_from_tower_node (next);
- unsigned long this_height = tower_node_get_height (node);
+ unsigned long this_height = tower_node_get_size (node);
if (group->phy_start + this_height == next_group->phy_start)
{
- unsigned long next_height = tower_node_get_height (next);
+ unsigned long next_height = tower_node_get_size (next);
tower_resize (t, node, this_height + next_height);
if (other_node != NULL && *other_node == next)
*other_node = tower_next (t, *other_node);
@@ -979,11 +979,11 @@ merge_axis_nodes (struct axis *axis, struct tower_node
*node,
if (prev != NULL)
{
struct axis_group *prev_group = axis_group_from_tower_node (prev);
- unsigned long prev_height = tower_node_get_height (prev);
+ unsigned long prev_height = tower_node_get_size (prev);
if (prev_group->phy_start + prev_height == group->phy_start)
{
- unsigned long this_height = tower_node_get_height (node);
+ unsigned long this_height = tower_node_get_size (node);
group->phy_start = prev_group->phy_start;
tower_resize (t, node, this_height + prev_height);
if (other_node != NULL && *other_node == prev)
@@ -1007,7 +1007,7 @@ check_axis_merged (const struct axis *axis UNUSED)
if (prev != NULL)
{
struct axis_group *prev_group = axis_group_from_tower_node (prev);
- unsigned long prev_height = tower_node_get_height (prev);
+ unsigned long prev_height = tower_node_get_size (prev);
struct axis_group *node_group = axis_group_from_tower_node (node);
assert (prev_group->phy_start + prev_height != node_group->phy_start);
}
diff --git a/src/libpspp/tower.c b/src/libpspp/tower.c
index 02447d7..4d0f794 100644
--- a/src/libpspp/tower.c
+++ b/src/libpspp/tower.c
@@ -30,7 +30,7 @@ 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 void reaugment_tower_node (struct abt_node *,
const struct abt_node *,
const struct abt_node *,
@@ -55,17 +55,17 @@ tower_is_empty (const struct 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;
@@ -81,13 +81,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;
}
@@ -135,7 +135,7 @@ tower_lookup (const struct tower *t_,
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;
@@ -145,8 +145,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];
@@ -155,11 +155,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;
@@ -170,8 +170,8 @@ 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;
}
}
}
@@ -253,16 +253,16 @@ 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_height : 0;
+ return p != NULL ? abt_to_tower_node (p)->subtree_size : 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,
@@ -270,9 +270,9 @@ 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;
+ node->subtree_size = node->size;
if (left != NULL)
- node->subtree_height += abt_to_tower_node (left)->subtree_height;
+ node->subtree_size += abt_to_tower_node (left)->subtree_size;
if (right != NULL)
- node->subtree_height += abt_to_tower_node (right)->subtree_height;
+ node->subtree_size += abt_to_tower_node (right)->subtree_size;
}
diff --git a/src/libpspp/tower.h b/src/libpspp/tower.h
index 55184e5..102967c 100644
--- a/src/libpspp/tower.h
+++ b/src/libpspp/tower.h
@@ -33,7 +33,7 @@
This is the analogy behind this data structure. Each node in
the data structure has a "thickness", which is actually called
- the node's "height" because "thickness" is just too awkward a
+ the node's "size" because "thickness" is just too awkward a
name. The primary way to look up nodes is by a height from
the bottom of the tower; any height within a node retrieves
that node, not just the distance to the bottom of the node.
@@ -58,15 +58,15 @@
struct tower_node
{
struct abt_node abt_node; /* ABT node. */
- unsigned long int subtree_height; /* Node's plus descendants' heights. */
- unsigned long int height; /* Height. */
+ unsigned long int subtree_size; /* Node size plus descendants' sizes. */
+ unsigned long int size; /* Size. */
};
-/* Returns the height of a tower node. */
+/* Returns the size of a tower node. */
static inline unsigned long
-tower_node_get_height (const struct tower_node *node)
+tower_node_get_size (const struct tower_node *node)
{
- return node->height;
+ return node->size;
}
/* A tower. */
@@ -82,11 +82,11 @@ void tower_init (struct tower *);
bool tower_is_empty (const struct tower *);
unsigned long int tower_height (const struct tower *);
-void tower_insert (struct tower *, unsigned long int height,
+void tower_insert (struct tower *, unsigned long int size,
struct tower_node *new, struct tower_node *under);
struct tower_node *tower_delete (struct tower *, struct tower_node *);
void tower_resize (struct tower *, struct tower_node *,
- unsigned long int new_height);
+ unsigned long int new_size);
void tower_splice (struct tower *dst, struct tower_node *under,
struct tower *src,
struct tower_node *first, struct tower_node *last);
diff --git a/tests/libpspp/tower-test.c b/tests/libpspp/tower-test.c
index 504e19f..1041906 100644
--- a/tests/libpspp/tower-test.c
+++ b/tests/libpspp/tower-test.c
@@ -245,7 +245,7 @@ next_composition (int n, int *k, int parts[])
/* A block expected to be found in a tower. */
struct expected_block
{
- int height; /* Expected height of bottom of block. */
+ int size; /* Expected thickness of block. */
int x; /* Expected value for `x' member. */
};
@@ -266,7 +266,7 @@ check_tower (struct tower *t,
{
unsigned long int level;
for (level = total_height;
- level < total_height + blocks[i].height;
+ level < total_height + blocks[i].size;
level++)
{
struct tower_node *found;
@@ -276,7 +276,7 @@ check_tower (struct tower *t,
check (tower_node_to_block (found)->x == blocks[i].x);
check (block_start == total_height);
}
- total_height += blocks[i].height;
+ total_height += blocks[i].size;
}
check (tower_height (t) == total_height);
@@ -284,7 +284,7 @@ check_tower (struct tower *t,
node != NULL;
node = tower_next (t, node), i++)
{
- check (tower_node_get_height (node) == blocks[i].height);
+ check (tower_node_get_size (node) == blocks[i].size);
check (tower_node_to_block (node)->x == blocks[i].x);
}
check (i == block_cnt);
@@ -293,7 +293,7 @@ check_tower (struct tower *t,
node != NULL;
node = tower_prev (t, node), i--)
{
- check (tower_node_get_height (node) == blocks[i].height);
+ check (tower_node_get_size (node) == blocks[i].size);
check (tower_node_to_block (node)->x == blocks[i].x);
}
check (i == SIZE_MAX);
@@ -312,19 +312,19 @@ test_insert (void)
{
unsigned int composition_cnt;
struct expected_block *expected;
- int *heights;
+ int *sizes;
int block_cnt;
int *order;
struct block *blocks;
expected = xnmalloc (cnt, sizeof *expected);
- heights = xnmalloc (cnt, sizeof *heights);
+ sizes = xnmalloc (cnt, sizeof *sizes);
order = xnmalloc (cnt, sizeof *order);
blocks = xnmalloc (cnt, sizeof *blocks);
block_cnt = 0;
composition_cnt = 0;
- while (next_composition (cnt, &block_cnt, heights))
+ while (next_composition (cnt, &block_cnt, sizes))
{
int i, j;
unsigned int permutation_cnt;
@@ -338,7 +338,7 @@ test_insert (void)
struct tower t;
/* Inserts the block_cnt blocks with the given
- heights[] into T in the order given by order[]. */
+ sizes[] into T in the order given by order[]. */
tower_init (&t);
for (i = 0; i < block_cnt; i++)
{
@@ -354,14 +354,14 @@ test_insert (void)
&& (under == NULL || under->x > order[j]))
under = &blocks[order[j]];
- tower_insert (&t, heights[idx], &blocks[idx].node,
+ tower_insert (&t, sizes[idx], &blocks[idx].node,
under != NULL ? &under->node : NULL);
}
/* Check that the result is what we expect. */
for (i = 0; i < block_cnt; i++)
{
- expected[i].height = heights[i];
+ expected[i].size = sizes[i];
expected[i].x = i;
}
check_tower (&t, expected, block_cnt);
@@ -375,14 +375,14 @@ test_insert (void)
check (composition_cnt == 1 << (cnt - 1));
free (expected);
- free (heights);
+ free (sizes);
free (order);
free (blocks);
}
}
/* Tests deleting blocks from towers that initially contain all
- possible sets of block heights into a tower in all possible
+ possible sets of block sizes into a tower in all possible
orders, up to a specified maximum tower height. */
static void
test_delete (void)
@@ -394,19 +394,19 @@ test_delete (void)
{
unsigned int composition_cnt;
struct expected_block *expected;
- int *heights;
+ int *sizes;
int block_cnt;
int *order;
struct block *blocks;
expected = xnmalloc (cnt, sizeof *expected);
- heights = xnmalloc (cnt, sizeof *heights);
+ sizes = xnmalloc (cnt, sizeof *sizes);
order = xnmalloc (cnt, sizeof *order);
blocks = xnmalloc (cnt, sizeof *blocks);
block_cnt = 0;
composition_cnt = 0;
- while (next_composition (cnt, &block_cnt, heights))
+ while (next_composition (cnt, &block_cnt, sizes))
{
int i;
unsigned int permutation_cnt;
@@ -424,9 +424,9 @@ test_delete (void)
for (i = 0; i < block_cnt; i++)
{
blocks[i].x = i;
- tower_insert (&t, heights[i], &blocks[i].node, NULL);
+ tower_insert (&t, sizes[i], &blocks[i].node, NULL);
expected[i].x = i;
- expected[i].height = heights[i];
+ expected[i].size = sizes[i];
}
check_tower (&t, expected, block_cnt);
@@ -459,14 +459,14 @@ test_delete (void)
check (composition_cnt == 1 << (cnt - 1));
free (expected);
- free (heights);
+ free (sizes);
free (order);
free (blocks);
}
}
-/* Tests towers containing all possible block heights, resizing
- the blocks to all possible heights that conserve the total
+/* Tests towers containing all possible block sizes, resizing
+ the blocks to all possible sizes that conserve the total
tower height, up to a maximum total tower height. */
static void
test_resize (void)
@@ -478,27 +478,27 @@ test_resize (void)
{
unsigned int composition_cnt;
struct expected_block *expected;
- int *heights, *new_heights;
+ int *sizes, *new_sizes;
int block_cnt;
int *order;
struct block *blocks;
expected = xnmalloc (cnt, sizeof *expected);
- heights = xnmalloc (cnt, sizeof *heights);
- new_heights = xnmalloc (cnt, sizeof *new_heights);
+ sizes = xnmalloc (cnt, sizeof *sizes);
+ new_sizes = xnmalloc (cnt, sizeof *new_sizes);
order = xnmalloc (cnt, sizeof *order);
blocks = xnmalloc (cnt, sizeof *blocks);
block_cnt = 0;
composition_cnt = 0;
- while (next_composition (cnt, &block_cnt, heights))
+ while (next_composition (cnt, &block_cnt, sizes))
{
int i;
unsigned int resizes = 0;
- for (resizes = 0, first_k_composition (cnt, block_cnt, new_heights);
+ for (resizes = 0, first_k_composition (cnt, block_cnt, new_sizes);
(resizes == 0
- || next_k_composition (cnt, block_cnt, new_heights));
+ || next_k_composition (cnt, block_cnt, new_sizes));
resizes++)
{
struct tower t;
@@ -508,18 +508,18 @@ test_resize (void)
for (i = 0; i < block_cnt; i++)
{
blocks[i].x = i;
- tower_insert (&t, heights[i], &blocks[i].node, NULL);
+ tower_insert (&t, sizes[i], &blocks[i].node, NULL);
expected[i].x = i;
- expected[i].height = heights[i];
+ expected[i].size = sizes[i];
}
check_tower (&t, expected, block_cnt);
/* Resize all the blocks. */
for (i = 0; i < block_cnt; i++)
{
- if (expected[i].height != new_heights[i] || rand () % 2)
- tower_resize (&t, &blocks[i].node, new_heights[i]);
- expected[i].height = new_heights[i];
+ if (expected[i].size != new_sizes[i] || rand () % 2)
+ tower_resize (&t, &blocks[i].node, new_sizes[i]);
+ expected[i].size = new_sizes[i];
}
check_tower (&t, expected, block_cnt);
}
@@ -530,8 +530,8 @@ test_resize (void)
check (composition_cnt == 1 << (cnt - 1));
free (expected);
- free (new_heights);
- free (heights);
+ free (new_sizes);
+ free (sizes);
free (order);
free (blocks);
}
@@ -549,20 +549,20 @@ test_splice_out (void)
{
unsigned int composition_cnt;
struct expected_block *expected;
- int *heights, *new_heights;
+ int *sizes, *new_sizes;
int block_cnt;
int *order;
struct block *blocks;
expected = xnmalloc (cnt, sizeof *expected);
- heights = xnmalloc (cnt, sizeof *heights);
- new_heights = xnmalloc (cnt, sizeof *new_heights);
+ sizes = xnmalloc (cnt, sizeof *sizes);
+ new_sizes = xnmalloc (cnt, sizeof *new_sizes);
order = xnmalloc (cnt, sizeof *order);
blocks = xnmalloc (cnt, sizeof *blocks);
block_cnt = 0;
composition_cnt = 0;
- while (next_composition (cnt, &block_cnt, heights))
+ while (next_composition (cnt, &block_cnt, sizes))
{
int i, j;
@@ -579,9 +579,9 @@ test_splice_out (void)
for (k = 0; k < block_cnt; k++)
{
blocks[k].x = k;
- tower_insert (&src, heights[k], &blocks[k].node, NULL);
+ tower_insert (&src, sizes[k], &blocks[k].node, NULL);
expected[k].x = k;
- expected[k].height = heights[k];
+ expected[k].size = sizes[k];
}
check_tower (&src, expected, block_cnt);
@@ -598,8 +598,8 @@ test_splice_out (void)
check (composition_cnt == 1 << (cnt - 1));
free (expected);
- free (new_heights);
- free (heights);
+ free (new_sizes);
+ free (sizes);
free (order);
free (blocks);
}
@@ -617,20 +617,20 @@ test_splice_in (void)
{
unsigned int composition_cnt;
struct expected_block *expected;
- int *heights, *new_heights;
+ int *sizes, *new_sizes;
int block_cnt;
int *order;
struct block *blocks;
expected = xnmalloc (cnt, sizeof *expected);
- heights = xnmalloc (cnt, sizeof *heights);
- new_heights = xnmalloc (cnt, sizeof *new_heights);
+ sizes = xnmalloc (cnt, sizeof *sizes);
+ new_sizes = xnmalloc (cnt, sizeof *new_sizes);
order = xnmalloc (cnt, sizeof *order);
blocks = xnmalloc (cnt, sizeof *blocks);
block_cnt = 0;
composition_cnt = 0;
- while (next_composition (cnt, &block_cnt, heights))
+ while (next_composition (cnt, &block_cnt, sizes))
{
int i, j;
@@ -648,9 +648,9 @@ test_splice_in (void)
{
blocks[k].x = k;
tower_insert (k >= i && k < j ? &src : &dst,
- heights[k], &blocks[k].node, NULL);
+ sizes[k], &blocks[k].node, NULL);
expected[k].x = k;
- expected[k].height = heights[k];
+ expected[k].size = sizes[k];
}
/* Splice SRC into DST. */
@@ -663,8 +663,8 @@ test_splice_in (void)
check (composition_cnt == 1 << (cnt - 1));
free (expected);
- free (new_heights);
- free (heights);
+ free (new_sizes);
+ free (sizes);
free (order);
free (blocks);
}
----------------------------------------------------------------------
commit c7e6095d9ee3eee25940f0ae42f4990c1605b5ea
Author: Ben Pfaff <address@hidden>
Date: Fri Nov 21 21:57:14 2008 -0800
Add support for array-like indexes to tower code.
diff --git a/src/libpspp/tower.c b/src/libpspp/tower.c
index 4d0f794..e8d253d 100644
--- a/src/libpspp/tower.c
+++ b/src/libpspp/tower.c
@@ -31,11 +31,58 @@ static struct tower_node *next_node (const struct tower *,
static struct tower_node *prev_node (const struct tower *,
const struct tower_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)
@@ -51,6 +98,13 @@ 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)
@@ -177,6 +231,33 @@ tower_lookup (const struct tower *t_,
}
}
+/* 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 = (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 *
@@ -261,6 +342,14 @@ 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_count : 0;
+}
+
/* Recalculates the subtree_size of NODE based on its LEFT and
RIGHT children's subtree_sizes. */
static void
@@ -271,8 +360,17 @@ reaugment_tower_node (struct abt_node *node_,
{
struct tower_node *node = abt_to_tower_node (node_);
node->subtree_size = node->size;
- if (left != NULL)
- node->subtree_size += abt_to_tower_node (left)->subtree_size;
- if (right != NULL)
- node->subtree_size += abt_to_tower_node (right)->subtree_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;
+ }
}
diff --git a/src/libpspp/tower.h b/src/libpspp/tower.h
index 102967c..246984a 100644
--- a/src/libpspp/tower.h
+++ b/src/libpspp/tower.h
@@ -40,7 +40,11 @@
You can insert a new node between any two existing nodes, or
at either end, which shifts up the height of all the nodes
above it. You can also delete any node, which shifts down the
- height of all the nodes above it. */
+ height of all the nodes above it.
+
+ The tower data structure also implements efficient access to
+ nodes by index, i.e. by 0-based count of nodes from the bottom
+ of the tower. */
#ifndef LIBPSPP_TOWER_H
#define LIBPSPP_TOWER_H
@@ -60,6 +64,7 @@ struct tower_node
struct abt_node abt_node; /* ABT node. */
unsigned long int subtree_size; /* Node size plus descendants' sizes. */
unsigned long int size; /* Size. */
+ unsigned long int subtree_count; /* Number of descendants, plus 1. */
};
/* Returns the size of a tower node. */
@@ -69,6 +74,9 @@ tower_node_get_size (const struct tower_node *node)
return node->size;
}
+unsigned long int tower_node_get_level (const struct tower_node *);
+unsigned long int tower_node_get_index (const struct tower_node *);
+
/* A tower. */
struct tower
{
@@ -80,6 +88,7 @@ struct tower
void tower_init (struct tower *);
bool tower_is_empty (const struct tower *);
+unsigned long int tower_count (const struct tower *);
unsigned long int tower_height (const struct tower *);
void tower_insert (struct tower *, unsigned long int size,
@@ -94,6 +103,7 @@ void tower_splice (struct tower *dst, struct tower_node
*under,
struct tower_node *tower_lookup (const struct tower *,
unsigned long int level,
unsigned long int *node_start);
+struct tower_node *tower_get (const struct tower *, unsigned long int index);
struct tower_node *tower_first (const struct tower *);
struct tower_node *tower_last (const struct tower *);
struct tower_node *tower_next (const struct tower *,
diff --git a/tests/libpspp/tower-test.c b/tests/libpspp/tower-test.c
index 1041906..c603c3a 100644
--- a/tests/libpspp/tower-test.c
+++ b/tests/libpspp/tower-test.c
@@ -259,6 +259,7 @@ check_tower (struct tower *t,
struct tower_node *node;
size_t i;
+ check (tower_count (t) == block_cnt);
check (tower_is_empty (t) == (block_cnt == 0));
total_height = 0;
@@ -275,6 +276,9 @@ check_tower (struct tower *t,
check (found != NULL);
check (tower_node_to_block (found)->x == blocks[i].x);
check (block_start == total_height);
+ check (tower_node_get_level (found) == total_height);
+ check (tower_node_get_index (found) == i);
+ check (tower_get (t, i) == found);
}
total_height += blocks[i].size;
}
--
Ben Pfaff
http://benpfaff.org
- tower.[ch], John Darrington, 2008/11/21
- Re: tower.[ch],
Ben Pfaff <=