  Tree data structures, such as red-black trees, quad trees, treaps, or tries,
are fundamental tools in computer science. A classical problem in concurrency
is to obtain expressive, efficient, and scalable versions of practical tree
data structures. We are interested in concurrent trees supporting range
queries, i.e., queries that involve multiple consecutive data items. Existing
implementations with this capability can list keys in a specific range, but do
not support aggregate range queries: for instance, if we want to calculate the
number of keys in a range, the only choice is to retrieve a whole list and
return its size. This is suboptimal: in the sequential setting, one can augment
a balanced search tree with counters and, consequently, perform these aggregate
requests in logarithmic rather than linear time.
  In this paper, we propose a generic approach to implement a broad class of
range queries on concurrent trees in a way that is wait-free, asymptotically
efficient, and practically scalable. The key idea is a new mechanism for
maintaining metadata concurrently at tree nodes, which can be seen as a
wait-free variant of hand-over-hand locking (which we call hand-over-hand
helping). We implement, test, and benchmark a balanced binary search tree with
wait-free insert, delete, contains, and count operations, returning the number
of keys in a given range which validates the expected speedups because of our
method in practice.
