Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Concurrent TreeMap w/ efficient support for clone() and consistent iteration
Java
Branch: master

bug fix: extra routing nodes from race near a leaf

Summary: SnapTree repair relies on a notion of responsibility handoff,
where any violations of the tree constraints ("damage") are repaired
either by the current thread or by another thread that prevents the
current thread from completing the repair.  There are three types of
damage: incorrect height, out of balance, and unnecessary routing node.
The rotation code assumed that it repaired all damage to a node, but
only actually repaired the first 2 types.  This means that if a routing
node was simultaneously rotated down and had one of its leaves removed,
it could be left in the tree despite having only one child.  The end
effect is that after emptying the tree (and observing size() == 0),
isEmpty() still returned true.

This fixes issue #5
latest commit 178f6be838
@nbronson authored

README

This repository contains SnapTree, a concurrent AVL tree with fast
cloning, snapshots, and consistent iteration.  It is described in
the paper "A Practical Concurrent Binary Search Tree", by N. Bronson,
J. Casper, H. Chafi, and K. Olukotun, published in PPoPP'10.

SnapTreeMap is a drop-in replacement for ConcurrentSkipListMap,
with the additional guarantee that clone() is atomic and
iteration has snapshot isolation.  For more details see
http://ppl.stanford.edu/papers/ppopp207-bronson.pdf

The current release is 0.2, which has been published to the maven central
repository under the groupId edu.stanford.ppl and the artifactId snaptree.

VERSION 0.2:
 * Incorporates an important bugfix to isEmpty()

VERSION 0.1:
 * Initial release
Something went wrong with that request. Please try again.