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
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
This is the analogy behind this data structure. Each node in
the data structure has a "thickness", which is actually called
This is the analogy behind this data structure. Each node in
the data structure has a "thickness", which is actually called
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
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. */
/* Returns the data structure corresponding to the given NODE,
assuming that NODE is embedded as the given MEMBER name in
data type STRUCT. */
/* Returns the data structure corresponding to the given NODE,
assuming that NODE is embedded as the given MEMBER name in
data type STRUCT. */
-#define tower_data(NODE, STRUCT, MEMBER) \
- ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
+#define tower_data(NODE, STRUCT, MEMBER) \
+ (CHECK_POINTER_HAS_TYPE (NODE, struct tower_node *), \
+ UP_CAST (NODE, STRUCT, MEMBER))
- 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. */
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 *,
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 *,
void tower_splice (struct tower *dst, struct tower_node *under,
struct tower *src,
struct tower_node *first, struct tower_node *last);
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_lookup (const struct tower *,
unsigned long int level,
unsigned long int *node_start);
struct tower_node *tower_first (const struct tower *);
struct tower_node *tower_last (const struct tower *);
struct tower_node *tower_next (const struct tower *,
struct tower_node *tower_first (const struct tower *);
struct tower_node *tower_last (const struct tower *);
struct tower_node *tower_next (const struct tower *,