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);
{
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);
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);
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);
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)
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);
}
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)
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;
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;
}
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;
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];
{
/* 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;
{
/* 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 = (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 *
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,
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;
+ }
}
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.
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
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. */
+ unsigned long int subtree_count; /* Number of descendants, plus 1. */
};
-/* 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;
}
+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
{
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 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);
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 *,
/* 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. */
};
struct tower_node *node;
size_t i;
+ check (tower_count (t) == block_cnt);
check (tower_is_empty (t) == (block_cnt == 0));
total_height = 0;
{
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;
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].height;
+ total_height += blocks[i].size;
}
check (tower_height (t) == total_height);
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);
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);
{
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;
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++)
{
&& (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);
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)
{
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;
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);
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)
{
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;
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);
}
check (composition_cnt == 1 << (cnt - 1));
free (expected);
- free (new_heights);
- free (heights);
+ free (new_sizes);
+ free (sizes);
free (order);
free (blocks);
}
{
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;
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);
check (composition_cnt == 1 << (cnt - 1));
free (expected);
- free (new_heights);
- free (heights);
+ free (new_sizes);
+ free (sizes);
free (order);
free (blocks);
}
{
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;
{
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. */
check (composition_cnt == 1 << (cnt - 1));
free (expected);
- free (new_heights);
- free (heights);
+ free (new_sizes);
+ free (sizes);
free (order);
free (blocks);
}
projects / pspp-builds.git / commitdiff