  We describe a general technique for obtaining provably correct, non-blocking
implementations of a large class of tree data structures where pointers are
directed from parents to children. Updates are permitted to modify any
contiguous portion of the tree atomically. Our non-blocking algorithms make use
of the LLX, SCX and VLX primitives, which are multi-word generalizations of the
standard LL, SC and VL primitives and have been implemented from single-word
CAS.
  To illustrate our technique, we describe how it can be used in a fairly
straightforward way to obtain a non-blocking implementation of a chromatic
tree, which is a relaxed variant of a red-black tree. The height of the tree at
any time is $O(c+ \log n)$, where $n$ is the number of keys and $c$ is the
number of updates in progress. We provide an experimental performance analysis
which demonstrates that our Java implementation of a chromatic tree rivals, and
often significantly outperforms, other leading concurrent dictionaries.
