package algorithms.published;
/**
* An implementation of a non-blocking k-ary search tree supporting range queries.
* Copyright (C) 2012-2014 Trevor Brown
* Contact (tabrown [at] cs [dot] toronto [dot 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 .
*
* Updated Oct 22, 2014.
*/
import java.util.concurrent.atomic.*;
public class LockFreeKSTRQ, V> {
/**
*
* GLOBALS
*
*/
private static final AtomicReferenceFieldUpdater infoUpdater =
AtomicReferenceFieldUpdater.newUpdater(Node.class, Info.class, "info");
private final Node root;
private final int K;
/**
*
* CONSTRUCTORS
*
*/
public LockFreeKSTRQ(final int K) {
this(K, new Node(K, true));
}
private LockFreeKSTRQ(final int K, final Node root) {
this.K = K;
this.root = root;
}
/**
*
* PUBLIC FUNCTIONS
*
*/
/**
* size() is NOT a constant time method, and the result is only guaranteed to
* be consistent if no concurrent updates occur.
* Note: linearizable size() and iterators can be implemented, so contact
* the author if they are needed for some application.
*/
public final int size() {
return sequentialSize(root);
}
private int sequentialSize(final Node node) {
if (node == null) return 0;
if (node.c == null) return node.kcount;
int sum = 0;
for (int i=0;i l = root.c.get(0);
while (l.c != 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.c.get(0);
while (l.c != 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;
int pindex; // index of the child of p that points to l
while (true) {
// search
p = root;
pinfo = p.info; // TODO: NOTE THIS LINE IS UNNECESSARY
l = p.c.get(0);
while (l.c != null) {
p = l;
l = child(key, l);
}
// - read pinfo once instead of every iteration of the previous loop
// then re-read and verify the child pointer from p to l
// (so it is as if p.info were read first)
// and also store the index of the child pointer of p that points to l
pinfo = p.info;
Node currentL = p.c.get(p.kcount);
pindex = p.kcount;
for (int i=0;i(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, pindex);
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;
int pindex; // index of the child of p that points to l
while (true) {
// search
p = root;
pinfo = p.info;
l = p.c.get(0);
while (l.c != null) {
p = l;
l = child(key, l);
}
// - read pinfo once instead of every iteration of the previous loop
// then re-read and verify the child pointer from p to l
// (so it is as if p.info were read first)
// and also store the index of the child pointer of p that points to l
pinfo = p.info;
Node currentL = p.c.get(p.kcount);
pindex = p.kcount;
for (int i=0;i(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, pindex);
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 == K-1) { // l is full of keys
// create internal node with K 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, pindex);
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;
int pindex; // index of the child of p that points to l
int gpindex; // index of the child of gp that points to p
while (true) {
// search
gp = null;
gpinfo = null;
p = root;
pinfo = p.info;
l = p.c.get(0);
while (l.c != null) {
gp = p;
p = l;
l = child(key, l);
}
// - read gpinfo once instead of every iteration of the previous loop
// then re-read and verify the child pointer from gp to p
// (so it is as if gp.info were read first)
// and also store the index of the child pointer of gp that points to p
gpinfo = gp.info;
Node currentP = gp.c.get(gp.kcount);
gpindex = gp.kcount;
for (int i=0;i currentL = p.c.get(p.kcount);
pindex = p.kcount;
for (int i=0;i 0) {
ccount++;
if (ccount > 2) break; // [todo] add this optimization for large k
}
}
}
// PRUNING DELETION
if (l.kcount == 1 && ccount == 2) {
final DInfo newGPInfo = new DInfo(l, p, gp, pinfo, gpindex);
if (infoUpdater.compareAndSet(gp, gpinfo, newGPInfo)) { // [[ dflag CAS ]]
if (helpDelete(newGPInfo)) return l.getValue(key);
} else {
help(gp.info);
}
// SIMPLE DELETION
} else {
// create leaf with sorted keys
newchild = new Node(key, l);
// flag and perform the key deletion (like insertion)
final IInfo newPInfo = new IInfo(l, p, newchild, pindex);
if (infoUpdater.compareAndSet(p, pinfo, newPInfo)) { // [[ kdflag CAS ]]
helpInsert(newPInfo);
return l.getValue(key);
} else {
help(p.info);
}
}
}
}
}
public static final class Stack {
private static final int INIT_SIZE = 64;
public Node[] s; // unsafe
public int size = 0; // unsafe
public Stack() {
s = new Node[INIT_SIZE];
}
public final void push(final Node x) {
if (size == s.length) {
final Node[] newS = new Node[s.length*2];
System.arraycopy(s, 0, newS, 0, size);
s = newS;
}
s[size] = x;
++size;
}
public final Node pop() {
return s[--size];
}
}
public final Object[] subSet(final E lo, final E hi) {
if (less(hi, lo)) {
throw new IllegalArgumentException("inconsistent range");
}
while (true) {
final Stack snap = new Stack();
final Stack s = new Stack();
s.push(root.c.get(0));
while (s.size > 0) {
final Node u = s.pop();
if (u == null) continue;
if (u.c == null) { // add u to partial snapshot if it is a leaf
snap.push(u);
} else {
// find right-most sub-tree that could contain a key in [lo, hi]
int r = u.kcount;
while (r > 0 && less(hi, (E)u.k[r-1])) { // subtree rooted at u.c.get(r) contains only keys > hi
--r;
}
// find left-most sub-tree that could contain a key in [lo, hi]
int l = 0;
while (l < u.kcount && greaterEqual(lo, (E)u.k[l])) {
++l;
}
// perform DFS from left to right (so push onto stack from right to left)
for (int i=r; i>=l; --i) {
s.push(u.c.get(i));
}
}
}
boolean retry = false;
for (int i=0;i=0;ei--) {
for (ej=snap.s[ei].kcount-1;ej>=0;ej--) {
if (greaterEqual(hi, (E) snap.s[ei].k[ej])) {
loop = false;
break;
}
}
if (!loop) break;
}
// CASE: NO NODES WITH KEYS IN RANGE
if (si > ei) {
return new Object[0];
}
// CASE: SINGLE NODE WITH KEYS IN RANGE
if (si == ei) {
final Object[] result = new Object[ej-sj+1];
System.arraycopy(snap.s[si].k, sj, result, 0, ej-sj+1);
return result;
}
// CASE: MULTIPLE NODES WITH KEYS IN RANGE
// get total number of keys in range [lo,hi]
int numKeys = ej+1-sj;
for (int i=si;i 0 && numKeys < n) {
final Node u = s.pop();
if (u == null) continue;
if (u.c == null) { // u is a leaf
if (u.kcount > 0) { // ignore empty leaves
result[k++] = u;
numKeys += u.kcount;
}
} else { // u is internal
for (int j=0;j 0 && i < n) {
final Node u = s.pop();
if (u == null) continue;
if (u.c == null) { // u is a leaf
result[i++] = u;
} else { // u is internal
for (int j=0;j, V> boolean equal(final E nonnull, final E other) {
if (other == null) return false;
return nonnull.compareTo(other) == 0;
}
// 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 lessEqual(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 greater(final E nonnull, final E other) {
if (other == null) return false;
return nonnull.compareTo(other) > 0;
}
// Precondition: `nonnull' is non-null
private static , V> boolean greaterEqual(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) {
// for (int i=0;i left) {
int mid = (left+right)/2;
if (key.compareTo((E)l.k[mid]) < 0) {
right = mid;
} else {
left = mid+1;
}
}
if (left == l.kcount-1 && key.compareTo((E)l.k[left]) >= 0) {
return l.c.get(l.kcount);
}
return l.c.get(left);
}
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) {
info.oldchild.dirty = info; // make it dirty
// CAS the correct child pointer of p from oldchild to newchild
info.p.c.compareAndSet(info.pindex, 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 exactly two non-empty children of info.p,
// so the following test correctly finds the "other" (remaining) node
Node other = info.p.c.get(info.p.kcount);
for (int i=0;i 0 && u != info.l) {
other = u;
break;
}
}
for (int i=0;i()); // [[ 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");
for (int i=0;i, V> {
public final int kcount; // key count
public final Object[] k; // keys
public final Object[] v; // values
public final AtomicReferenceArray c; // children
public volatile Info info = null;
public volatile Info dirty = null; // null === false, non-null === true, and indicates which operation set it dirty
/**
* Constructor for leaf with zero keys.
*/
Node() {
this.k = null;
this.v = null;
this.c = null;
kcount = 0;
}
/**
* Constructor for newly created leaves with one key.
*/
public Node(final Object key, final Object value) {
this.k = new Object[]{key};
this.v = new Object[]{value};
this.c = null;
this.kcount = 1;
}
/**
* Constructor for the root of the tree.
*
* The initial tree consists of 2+4 nodes.
* The root node has K children, its K-1 keys are null (infinity),
* and its key count is K-1.
* The first child of the root, c0, is an internal node with K children.
* Its keys are also null, and its key count is K-1.
* Its children are all empty leaves (no keys).
* c1, c2, ... exist to prevent deletion of this node (root.c0).
* The other children of the root are all empty leaves
* (to prevent null pointer exceptions).
*
* @param root if true, the root is created otherwise, if false,
* the root's child root.c0 is created.
*/
public Node(final int K, final boolean root) {
this.k = new Object[K-1];
this.v = null;
this.kcount = K-1;
if (root) {
this.c = new AtomicReferenceArray(K);
this.c.set(0, new Node(K, false));
for (int i=1;i());
}
} else {
this.c = new AtomicReferenceArray(K);
for (int i=0;i());
}
}
}
/**
* Constructor for case that (knew,vnew)
is being inserted,
* the leaf's key set is full (l.kcount == K-1
), and knew is
* not in l. This constructor creates a new internal node with K-1 keys and
* K children sorted by key.
*/
public Node(final E knew, final Object vnew, final Node l) {
this.kcount = l.kcount;
// determine which elements of l.k should precede knew (will be 0...i-1)
int i = 0;
for (;i(kcount+1);
// add children with keys preceding knew
for (int j=0;j(l.k[j], l.v[j]));
}
// add
this.c.set(i, new Node(knew, vnew));
// add children with keys following knew
for (int j=i;j(l.k[j], l.v[j]));
}
this.k = new Object[kcount];
for (int j=0;jcnew 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) {
this.c = null;
if (haskey) {
this.kcount = l.kcount;
this.k = l.k; // all keys are the same (and keys of a node never change)
this.v = new Object[kcount];
for (int i=0;i in the process
// determine which keys precede knew
int i = 0;
for (;i pairs preceding
// knew precedes l.k[i], but all of l.k[0...i-1] precede knew.
for (int j=0;j
this.k[i] = knew;
this.v[i] = vnew;
// write pairs following
for (int j=i;j l) {
this.c = null;
this.kcount = l.kcount - 1;
this.k = new Object[kcount];
this.v = new Object[kcount];
for (int i=0;i, V> {}
static final class IInfo, V> implements Info {
final Node p, oldchild, newchild;
final int pindex;
IInfo(final Node oldchild, final Node p, final Node newchild,
final int pindex) {
this.p = p;
this.oldchild = oldchild;
this.newchild = newchild;
this.pindex = pindex;
}
@Override
public boolean equals(Object o) {
IInfo x = (IInfo) o;
if (x.p != p
|| x.oldchild != oldchild
|| x.newchild != newchild
|| x.pindex != pindex) return false;
return true;
}
}
static final class DInfo, V> implements Info {
final Node p, l, gp;
final Info pinfo;
final int gpindex;
DInfo(final Node l, final Node p, final Node gp,
final Info pinfo, final int gpindex) {
this.p = p;
this.l = l;
this.gp = gp;
this.pinfo = pinfo;
this.gpindex = gpindex;
}
@Override
public boolean equals(Object o) {
DInfo x = (DInfo) o;
if (x.p != p
|| x.l != l
|| x.gp != gp
|| x.pinfo != pinfo
|| x.gpindex != gpindex) 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);
}
}
}