/**
* An implementation of a non-blocking k-ary search tree with k=3.
* Copyright (C) 2011 Trevor Brown, Joanna Helga
* Contact Trevor Brown (tabrown@cs.toronto.edu) with any questions or comments.
*
* 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
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
import java.util.*;
import java.util.concurrent.atomic.*;
public class LockFree3ST, V> {
/**
*
* GLOBALS
*
*/
private static final AtomicReferenceFieldUpdater c0Updater =
AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "c0");
private static final AtomicReferenceFieldUpdater c1Updater =
AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "c1");
private static final AtomicReferenceFieldUpdater c2Updater =
AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "c2");
private static final AtomicReferenceFieldUpdater infoUpdater =
AtomicReferenceFieldUpdater.newUpdater(Node.class, Info.class, "info");
private final Node root;
/**
*
* CONSTRUCTORS
*
*/
public LockFree3ST() {
this.root = new Node(true);
}
private LockFree3ST(Node root) {
this.root = root;
}
/**
*
* PUBLIC FUNCTIONS
*
*/
/**
* Determines whether a key is present in the tree.
* @return true if the key is present in the tree, and false otherwise
* @throws NullPointerException in the event that key is null
*/
public final boolean containsKey(final E key) {
if (key == null) throw new NullPointerException();
Node l = root.c0;
while (l.c0 != null) l = child(key, l); /* while l is internal */
return l.hasKey(key);
}
/**
* Retrieves the value associated with key from the tree.
* @return the value mapped to the key, or null in the event that
* (1) the key is not present in the tree, or
* (2) the value null is stored with the key
* @throws NullPointerException in the event that key is null
*/
public final V get(final E key) {
if (key == null) throw new NullPointerException();
Node l = root.c0;
while (l.c0 != null) l = child(key, l); /* while l is internal */
return l.getValue(key);
}
/**
* Adds a key-value pair to the tree if the key does not already exist.
* @return the previous value mapped to the key, or null in the event that
* (1) the key was not previously in the tree and the new
* value was successfully assigned, or
* (2) the key existed in the tree,
* and the value stored with it was null.
* @throws NullPointerException in the event that key is null
*/
public final V putIfAbsent(final E key, final V value) {
if (key == null) throw new NullPointerException();
Node p, l, newchild;
Info pinfo;
while (true) {
// search
p = root;
pinfo = p.info;
l = p.c0;
while (l.c0 != null) {
p = l;
l = child(key, l);
}
pinfo = p.info; // read pinfo once instead of every iteration
if (l != child(key, p)) continue; // then confirm the child link to l is valid
// (just as if we'd read p's info field before the reference to l)
if (l.hasKey(key)) return l.getValue(key);
else if (pinfo != null && pinfo.getClass() != Clean.class) help(pinfo);
else {
// SPROUTING INSERTION
if (l.kcount == 2) { // l is full of keys
// create internal node with 3 children sorted by key
newchild = new Node(key, value, l);
// SIMPLE INSERTION
} else {
// create leaf node with sorted keys
// (at least one key of l is null and, by structural invariant,
// nulls appear at the end, so the last key is null)
newchild = new Node(key, value, l, false);
}
// flag and perform the insertion
final IInfo newPInfo = new IInfo(l, p, newchild);
if (infoUpdater.compareAndSet(p, pinfo, newPInfo)) { // [[ iflag CAS ]]
helpInsert(newPInfo);
return null;
} else {
// help current operation first
help(p.info);
}
}
}
}
/**
* Adds a key-value pair to the tree, overwriting any pre-existing mapping.
* @return the value that was previously mapped to the key, or null if the
* key was not in the tree (or if the value stored with it was null)
* @throws NullPointerException in the event that key is null
*/
public final V put(final E key, final V value) {
if (key == null) throw new NullPointerException();
Node p, l, newchild;
Info pinfo;
while (true) {
// search
p = root;
pinfo = p.info;
l = p.c0;
while (l.c0 != null) {
p = l;
l = child(key, l);
}
pinfo = p.info; // read pinfo once instead of every iteration
if (l != child(key, p)) continue; // then confirm the child link to l is valid
// (just as if we'd read p's info field before the reference to l)
if (pinfo != null && pinfo.getClass() != Clean.class) {
help(pinfo);
} else if (l.hasKey(key)) {
// REPLACE INSERTION
newchild = new Node(key, value, l, true); // true means key is already in node l
// flag and perform the insertion
final IInfo newPInfo = new IInfo(l, p, newchild);
if (infoUpdater.compareAndSet(p, pinfo, newPInfo)) { // [[ iflag CAS ]]
helpInsert(newPInfo);
return l.getValue(key);
} else {
// help current operation first
help(p.info);
}
} else {
// SPROUTING INSERTION
if (l.kcount == 2) { // l is full of keys
// create internal node with 3 children sorted by key
newchild = new Node(key, value, l);
// SIMPLE INSERTION
} else {
// create leaf node with sorted keys
// (at least one key of l is null and, by structural invariant,
// nulls appear at the end, so the last key is null)
newchild = new Node(key, value, l, false); // false means key is not in l
}
// flag and perform the insertion
final IInfo newPInfo = new IInfo(l, p, newchild);
if (infoUpdater.compareAndSet(p, pinfo, newPInfo)) { // [[ iflag CAS ]]
helpInsert(newPInfo);
return null;
} else {
// help current operation first
help(p.info);
}
}
}
}
/**
* Remove a key from the tree.
* @return the value that was removed from the tree, or null if the key was
* not in the tree (or if the value stored with it was null)
* @throws NullPointerException in the event that key is null
*/
public final V remove(final E key) {
if (key == null) throw new NullPointerException();
Node gp, p, l, newchild;
Info gpinfo, pinfo;
while (true) {
// search
gp = null;
gpinfo = null;
p = root;
pinfo = p.info;
l = p.c0;
while (l.c0 != null) {
gp = p;
p = l;
l = child(key, l);
}
gpinfo = gp.info; // - read gpinfo once instead of every iteration
if (p != child(key, gp)) continue; // then confirm the child link to p is valid
pinfo = p.info; // (just as if we'd read gp's info field before the reference to p)
if (l != child(key, p)) continue; // - do the same for pinfo and l
// if the key is not in the tree, return null
if (!l.hasKey(key))
return null;
else if (gpinfo != null && gpinfo.getClass() != Clean.class)
help(gpinfo);
else if (pinfo != null && pinfo.getClass() != Clean.class)
help(pinfo);
else {
// count number of non-empty children of p
final int ccount = (p.c0.kcount > 0 ? 1 : 0) +
(p.c1.kcount > 0 ? 1 : 0) +
(p.c2.kcount > 0 ? 1 : 0);
// two types of deletion: PRUNING and SIMPLE
// simple deletion --is removing a key within a leaf
// --is performed when child-count > 2 or key-count > 1
// --is like insertion in that it does not need a mark
// pruning deletion --is pruning a leaf and its parent out of the tree
// --is performed when key-count is 1 and child-count is 2
// --needs a mark
// simple deletion uses an "insert to replace" method of deletion.
// pruning deletion uses a "bypass to replace" method of deletion.
// SIMPLE DELETION
if (ccount > 2 || l.kcount > 1) { // equivalent to (ccount>2 or (ccount==2 and l.kcount==1))
// observe: l.keycount never changes (we create objects to change it)
// thus l.keycount is forever > 1
// create leaf with sorted keys
newchild = new Node(key, l, l.kcount - 1);
// flag and perform the key deletion (like insertion)
final IInfo newPInfo = new IInfo(l, p, newchild);
if (infoUpdater.compareAndSet(p, pinfo, newPInfo)) { // [[ kdflag CAS ]]
helpInsert(newPInfo);
return l.getValue(key);
} else {
help(p.info);
}
// PRUNING DELETION
} else {
// observe: if the number of nonempty children is different from
// ccount, then the child pointers of p will have changed, and p.info
// will have changed, so that the clean value is different from what
// was read in the search above and saved to use as the `expected'
// value for the upcoming CAS. (so the cas will fail if it changes)
// (further, from data structure invariants, nodes always satisfy:
// (0 nonempty children) or (2 <= number of nonempty children <= 4))
final DInfo newGPInfo = new DInfo(l, p, gp, pinfo);
if (infoUpdater.compareAndSet(gp, gpinfo, newGPInfo)) { // [[ dflag CAS ]]
if (helpDelete(newGPInfo)) return l.getValue(key);
} else {
help(gp.info);
}
}
}
}
}
/**
* Determines the size of the tree
* @return the size of the tree, or -1 if the tree was concurrently modified
*/
public final int size() {
Node newroot = getSnapshot();
if (newroot == null) return -1;
return sequentialSize(newroot);
}
/**
* Determines the size of the tree (retries until the tree can be read in
* its entirety without concurrent modification)
* @return the size of the tree
*/
public final int sizeBlocking() {
int sz = 0;
for (;;) if ((sz = size()) != -1) return sz;
}
/**
* This assumes that there are no concurrent accesses occurring.
* If concurrent accesses can occur, use size() or sizeBlocking().
*/
public int sequentialSize() {
return sequentialSize(root);
}
/**
* Clones the tree (retries until the tree can be read in its
* entirety without concurrent modification)
* @return a reference to a clone of the tree
*/
@Override
public final LockFree3ST clone() {
Node newroot = null;
for (;;) if ((newroot = getSnapshot()) != null) return new LockFree3ST(newroot);
}
@Override
public final String toString() {
StringBuffer sb = new StringBuffer();
treeString(root, sb);
return sb.toString();
}
/**
*
* PRIVATE FUNCTIONS
*
*/
// Precondition: `nonnull' is non-null
private static , V> boolean less(final E nonnull, final E other) {
if (other == null) return true;
return nonnull.compareTo(other) < 0;
}
// Precondition: `nonnull' is non-null
private static , V> boolean equal(final E nonnull, final E other) {
if (other == null) return false;
return nonnull.compareTo(other) == 0;
}
private Node child(final E key, final Node l) {
if (less(key, l.k0)) return l.c0;
if (less(key, l.k1)) return l.c1;
return l.c2;
}
private void help(final Info info) {
if (info.getClass() == IInfo.class) helpInsert((IInfo) info);
else if (info.getClass() == DInfo.class) helpDelete((DInfo) info);
else if (info.getClass() == Mark.class) helpMarked(((Mark) info).dinfo);
}
private void helpInsert(final IInfo info) {
// CAS the correct child pointer of p from oldchild to newchild
((info.p.c0 == info.oldchild) ? c0Updater :
(info.p.c1 == info.oldchild) ? c1Updater :
c2Updater).compareAndSet(info.p, info.oldchild, info.newchild); // [[ ichild CAS ]]
infoUpdater.compareAndSet(info.p, info, new Clean()); // [[ iunflag CAS ]]
}
private boolean helpDelete(final DInfo info) {
final boolean markSuccess = infoUpdater.compareAndSet(
info.p, info.pinfo, new Mark(info)); // [[ mark CAS ]]
final Info currentPInfo = info.p.info;
if (markSuccess || (currentPInfo.getClass() == Mark.class
&& ((Mark) currentPInfo).dinfo == info)) {
helpMarked(info);
return true;
} else {
help(currentPInfo);
infoUpdater.compareAndSet(info.gp, info, new Clean()); // [[ backtrack CAS ]]
return false;
}
}
private void helpMarked(final DInfo info) {
// observe that there are two non-empty children of info.p
// so the following test correctly finds the "other" (remaining) node
final Node other = (info.p.c0.kcount > 0 && info.p.c0 != info.l) ? info.p.c0 :
(info.p.c1.kcount > 0 && info.p.c1 != info.l) ? info.p.c1 :
info.p.c2;
// CAS the correct child pointer of info.gp from info.p to other
((info.gp.c0 == info.p) ? c0Updater :
(info.gp.c1 == info.p) ? c1Updater :
c2Updater).compareAndSet(info.gp, info.p, other); // [[ dchild CAS ]]
infoUpdater.compareAndSet(info.gp, info, new Clean()); // [[ dunflag CAS ]]
}
public static void treeString(Node root, StringBuffer sb) {
if (root == null) {
sb.append("*");
return;
}
sb.append("(");
sb.append(root.kcount);
sb.append(" keys,");
sb.append((root.k0 == null ? "-" : root.k0.toString()));sb.append(",");
sb.append((root.k1 == null ? "-" : root.k1.toString()));sb.append(",");
treeString(root.c0, sb); sb.append(",");
treeString(root.c1, sb); sb.append(",");
treeString(root.c2, sb); sb.append(")");
}
/**
* This assumes that there are no concurrent accesses occurring!
* This is more efficient than size(), but its correctness is only
* guaranteed if it is known that there will be no concurrent accesses
* to the tree. If this is not known for certain, then use size() instead.
* @return the size of the tree
*/
private int sequentialSize(final Node node) {
if (node == null) return 0;
if (node.c0 == null) {
return (node.k1 != null ? 2 :
node.k0 != null ? 1 :
0);
} else {
return sequentialSize(node.c0) +
sequentialSize(node.c1) +
sequentialSize(node.c2);
}
}
/**
* Makes a shallow copy of node node
, storing information
* regarding its child references in map refs
, before
* recursively operating on its children.
*/
private void readRefs(final Node node, final HashMap refs) {
if (node == null) return;
refs.put(node, new Children(node));
readRefs(node.c0, refs);
readRefs(node.c1, refs);
readRefs(node.c2, refs);
}
/**
* Checks that the structure of the subtree rooted at node
* matches the structure captured in the map refs
.
* @return true if the structures match, and false otherwise
*/
private boolean checkRefs(final Node node, final HashMap refs) {
if (node == null) return true;
Children children = refs.get(node);
if (!children.equals(new Children(node))) return false;
return checkRefs(children.c0, refs) &&
checkRefs(children.c1, refs) &&
checkRefs(children.c2, refs);
}
/**
* Record the structure of the tree (child references) in map refs
.
*/
private Node buildRefs(final Node node, final HashMap refs) {
if (node == null) return null;
Children children = refs.get(node);
return new Node(node, buildRefs(children.c0, refs),
buildRefs(children.c1, refs),
buildRefs(children.c2, refs));
}
/**
* Obtains a snapshot of the tree by reading and duplicating all tree
* structure, then re-checking all "live" tree structure to see that it
* matches the recorded structure (to ensure validity of the snapshot),
* then building the copy from the recorded information.
* @return a snapshot of the tree, or null if the tree was concurrently modified
*/
private Node getSnapshot() {
final HashMap refs = new HashMap();
readRefs(root, refs);
if (!checkRefs(root, refs)) return null;
return buildRefs(root, refs);
}
/**
*
* PRIVATE CLASSES
*
*/
public static final class Node, V> {
public final int kcount; // key count
public final E k0, k1; // keys
public final V v0, v1; // values
public volatile Node c0, c1, c2; // children
public volatile Info info = null;
/**
* DEBUG CODE
*/
public Node(final Node node, final Node c0,
final Node c1,
final Node c2) {
this.kcount = node.kcount;
this.k0 = node.k0;
this.k1 = node.k1;
this.v0 = node.v0;
this.v1 = node.v1;
this.c0 = c0;
this.c1 = c1;
this.c2 = c2;
}
/**
* Constructor for leaf with zero keys.
*/
Node() {
kcount = 0;
this.k0 = this.k1 = null;
this.v0 = this.v1 = null;
}
/**
* Constructor for newly created leaves with one key.
*/
public Node(final E key, final V value) {
this.k0 = key;
this.v0 = value;
this.kcount = 1;
// fill in the final variables
this.k1 = null;
this.v1 = null;
}
/**
* Constructor for the root of the tree.
*
* The initial tree consists of 2+3 nodes.
* The root node has 1 child, its 2 keys are null (infinity),
* and its key count is 2.
* The sole child of the root, c0, is an internal node with 3 children.
* Its keys are also null, and its key count is 2.
* Its children are leaves. c0 is an empty leaf (no keys).
* c1, c2, ... are leaves with 1 key, namely null (representing infinity).
* c1, c2, ... exist to prevent deletion of this node (root.c0).
*
* @param root if true, the root is created otherwise, if false,
* the root's child root.c0 is created.
*/
public Node(final boolean root) {
this.k0 = this.k1 = null; // fill in final variables
this.v0 = this.v1 = null;
this.kcount = 2;
if (root) {
c0 = new Node(false); // only c0 since other children unused
} else {
this.c0 = new Node(); // empty leaf
// leaves with 1 key -- prevent deletion of this
this.c1 = new Node(null, null);
this.c2 = new Node(null, null);
}
}
/**
* Constructor for case that (knew,vnew)
is being inserted,
* the leaf's key set is full (l.kcount == 2
), and knew is
* not in l. This constructor creates a new internal node with 2 keys and
* 3 children sorted by key.
*/
public Node(final E knew, final V vnew, final Node l) {
if (less(knew, l.k0)) {
this.c0 = new Node(knew, vnew);
this.c1 = new Node(l.k0, l.v0);
this.c2 = new Node(l.k1, l.v1);
} else if (less(knew, l.k1)) {
this.c0 = new Node(l.k0, l.v0);
this.c1 = new Node(knew, vnew);
this.c2 = new Node(l.k1, l.v1);
} else {
this.c0 = new Node(l.k0, l.v0);
this.c1 = new Node(l.k1, l.v1);
this.c2 = new Node(knew, vnew);
}
this.k0 = this.c1.k0;
this.k1 = this.c2.k0;
this.v0 = this.v1 = null;
this.kcount = 2;
}
/**
* Constructor for case that cnew
is being inserted, and
* the leaf's key set is not full.
* This constructor creates a new leaf with keycount(old leaf)+1 keys.
*
* @param knew the key being inserted
* @param l the leaf into which the key is being inserted
* @param haskey indicates whether l already has knew
as a key
*/
public Node(final E knew, final V vnew, final Node l, final boolean haskey) {
if (haskey) {
if (equal(knew, l.k0)) {
this.k0 = knew;
this.v0 = vnew;
this.k1 = l.k1;
this.v1 = l.v1;
} else {
this.k0 = l.k0;
this.v0 = l.v0;
this.k1 = knew;
this.v1 = vnew;
}
this.kcount = l.kcount;
} else {
if (less(knew, l.k0)) {
this.k0 = knew;
this.v0 = vnew;
this.k1 = l.k0;
this.v1 = l.v0;
} else {
this.k0 = l.k0;
this.v0 = l.v0;
this.k1 = knew;
this.v1 = vnew;
}
this.kcount = l.kcount + 1;
}
}
/**
* Constructor for the case that a key is being deleted from the
* key set of a leaf. This constructor creates a new leaf with
* keycount(old leaf)-1 sorted keys.
*/
public Node(final E key, final Node l, final int kcount) {
this.kcount = kcount;
this.k1 = null;
this.v1 = null;
if (equal(key, l.k0)) {
this.k0 = l.k1;
this.v0 = l.v1;
} else {
this.k0 = l.k0;
this.v0 = l.v0;
}
}
// Precondition: key is not null
final boolean hasKey(final E key) {
return equal(key, k0) || equal(key, k1);
}
// Precondition: key is not null
V getValue(E key) {
return equal(key, k0) ? v0 :
equal(key, k1) ? v1 : null;
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
treeString(this, sb);
return sb.toString();
}
@Override
public final boolean equals(final Object o) {
if (o == null) return false;
if (o.getClass() != getClass()) return false;
Node n = (Node) o;
if (n.c0 != null && !n.c0.equals(c0) ||
n.c1 != null && !n.c1.equals(c1) ||
n.c2 != null && !n.c2.equals(c2)) return false;
if (n.k0 != null && !n.k0.equals(k0) ||
n.k1 != null && !n.k1.equals(k1)) return false;
if (n.v0 != null && !n.v0.equals(v0) ||
n.v1 != null && !n.v1.equals(v1)) return false;
if ((n.info != null && !n.info.equals(info)) || n.kcount != kcount) return false;
return true;
}
}
static interface Info, V> {}
static final class IInfo, V> implements Info {
final Node p, oldchild, newchild;
IInfo(final Node oldchild, final Node p, final Node newchild) {
this.p = p;
this.oldchild = oldchild;
this.newchild = newchild;
}
@Override
public boolean equals(Object o) {
IInfo x = (IInfo) o;
if (x.p != p || x.oldchild != oldchild || x.newchild != newchild) return false;
return true;
}
}
static final class DInfo, V> implements Info {
final Node p, l, gp;
final Info pinfo;
DInfo(final Node l, final Node p, final Node gp, final Info pinfo) {
this.p = p;
this.l = l;
this.gp = gp;
this.pinfo = pinfo;
}
@Override
public boolean equals(Object o) {
DInfo x = (DInfo) o;
if (x.p != p || x.l != l || x.gp != gp || x.pinfo != pinfo) return false;
return true;
}
}
static final class Mark, V> implements Info {
final DInfo dinfo;
Mark(final DInfo dinfo) {
this.dinfo = dinfo;
}
@Override
public boolean equals(Object o) {
Mark x = (Mark) o;
if (x.dinfo != dinfo) return false;
return true;
}
}
static final class Clean, V> implements Info {
@Override
public boolean equals(Object o) {
return (this == o);
}
}
private class Children {
Node c0, c1, c2;
public Children(Node node) {
this.c0 = node.c0;
this.c1 = node.c1;
this.c2 = node.c2;
}
@Override
public boolean equals(Object o) {
if (o == null || !o.getClass().equals(getClass())) return false; // CAN DO AWAY WITH THIS AT THE COST OF TYPE SAFETY!!
Children children = (Children) o;
return this.c0 == children.c0 &&
this.c1 == children.c1 &&
this.c2 == children.c2;
}
}
}