+/* 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;
+}
+