We introduce a template that can be used to implement a large class of non-blocking tree data structures efficiently. Using this template is significantly easier than designing the implementation from scratch. The template also drastically simplifies correctness proofs. Thus, the template allows us to obtain provably correct, non-blocking implementations of more complicated tree data structures than those that were previously possible. For example, we use the template to obtain the first non-blocking balanced binary search tree (BST) using finegrained synchronization.
展开▼
