/**
* Implementation of the dictionary ADT with a thread-safe B-slack tree.
* Copyright (C) 2014 Trevor Brown
* Contact (tabrown [at] cs [dot] toronto [dot] edu) with questions or comments.
*
* Details of the B-slack tree algorithm appear in the paper:
* Brown, Trevor. B-slack trees: space efficient B-trees. SWAT 2014.
*
* This tree is thread-safe, so multiple threads can perform operations on it
* at the same time. Updates synchronize with a single coarse-grained lock,
* so only one updater can work at a time. However, one particularly nice
* property of this implementation is that searches can proceed without any
* synchronization. Therefore, searches are not blocked by updates, and are
* very fast.
*
* Unfortunately, in Java, you cannot embed arrays inside nodes, so nodes
* contain pointers to key/value arrays. This makes the tree somewhat less
* efficient in Java. This is a reference implementation intended to show how
* to produce a simple implementation of a B-slack tree. The intention is to
* provide others with a guide they can use to produce a simple B-slack tree
* implementation in a language that gives more control over memory layout,
* such as C or C++. Better implementations are possible. See the full version
* of the paper for discussion of the algorithm and implementation details.
*
* The paper leaves it up to the implementer to decide when and how to perform
* rebalancing steps (i.e., Root-Zero, Root-Replace, Absorb, Split, Compress
* and One-Child). In this implementation, since there is only one updater, it
* is fairly straightforward to keep track of violations and fix them using
* a recursive procedure. The recursive procedure is designed as follows.
* After performing a rebalancing step, recursive invocations are made for every
* rebalancing step that are needed as a consequence. If an invocation I is
* trying to fix a violation at a node that has already been replaced by another
* invocation I', then I can hand off responsibility for fixing the violation to
* I'. Designing the rebalancing procedure to allow responsibility to be handed
* off in this manner is not difficult; it simply requires going through each
* rebalancing step S and observing which nodes involved in S can have
* violations after S (and then making a recursive call for each violation).
*
* Updated Oct 22, 2014.
*
* -----------------------------------------------------------------------------
*
* 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 .
*/
package algorithms.published;
import java.util.Arrays;
import java.util.Comparator;
/**
*
* @author Trevor Brown
*/
public class SyncBSlackTreeMap,V> {
public final Comparator super K> comparator;
public final int b;
private int size;
private final Node root;
/**
* Creates a new B-slack tree wherein:
* each internal node has up to 16 child pointers, and
* each leaf has up to 16 key/value pairs.
*/
public SyncBSlackTreeMap() {
this(16);
}
/**
* Creates a new B-slack tree wherein:
* each internal node has up to nodeCapacity
child pointers, and
* each leaf has up to nodeCapacity
key/value pairs.
*/
public SyncBSlackTreeMap(final int nodeCapacity) {
this(nodeCapacity, null);
}
/**
* Creates a new B-slack tree wherein:
* each internal node has up to nodeCapacity
child pointers, and
* each leaf has up to nodeCapacity
key/value pairs, and
* keys are ordered according to the provided comparator.
*/
public SyncBSlackTreeMap(final int nodeCapacity, final Comparator comparator) {
this.b = nodeCapacity;
this.comparator = comparator;
this.root = new Node(
new Object[0], // maybe can be null
null,
(Node[]) new Node[]{
new Node(
new Object[0],
new Object[0],
null,
true)
},
true);
}
/**
* Returns true if the dictionary contains key and false otherwise.
*/
public boolean containsKey(final K key) {
return get(key) != null;
}
/**
* Returns the value associated with key, or null if key is not in the
* dictionary.
*/
public V get(final K key) {
final Comparable super K> k = comparable(key);
Node l = root.children[0];
while (true) {
if (l.isLeaf()) break;
l = l.children[l.getChildIndex(k)];
}
final int keyIndex = l.getKeyIndex(k);
return (l.containsKey(keyIndex)) ? (V) l.values[keyIndex] : null;
}
/**
* Inserts a key/value pair into the dictionary if key is not already
* present, and does not change the data structure otherwise.
* Precondition: key != null
*
* @param key key to insert into the dictionary
* @param value value to associate with key
* @return true if the key/value pair was inserted into the dictionary,
* and false if key was already in the dictionary.
*/
public synchronized boolean putIfAbsent(final K key, final V value) {
return doPut(key, value, false) == null;
}
/**
* Inserts a key/value pair into the dictionary, replacing any previous
* value associated with the key.
* Precondition: key != null
*
* @param key key to insert into the dictionary
* @param value value to associate with key
* @return the value associated with key just before this operation, and
* null if key was not previously in the dictionary.
*/
public synchronized V put(final K key, final V value) {
return doPut(key, value, true);
}
private V doPut(final K key, final V value, final boolean replace) {
/**
* search.
*/
final Comparable super K> k = comparable(key);
Node gp = null;
Node p = root;
Node l = p.children[0];
int ixToP = -1;
int ixToL = -1;
int ix = 0;
while (true) {
ixToP = ixToL;
ixToL = ix;
ix = l.getChildIndex(k);
if (l.isLeaf()) break;
gp = p;
p = l;
l = l.children[ix];
}
/**
* do the update.
*/
int keyIndex = l.getKeyIndex(k);
if (l.containsKey(keyIndex)) {
/**
* if l already contains key, replace the existing value.
*/
final V oldValue = (V) l.values[keyIndex];
if (replace) {
l.values[keyIndex] = value;
}
return oldValue;
} else {
/**
* if l does not contain key, we have to insert it.
*/
// we start by creating a sorted array containing key and all of l's existing keys
// (and likewise for the values)
keyIndex = -(keyIndex + 1); //
final Object[] keys = new Object[l.keys.length+1];
final Object[] values = new Object[l.keys.length+1];
System.arraycopy(l.keys, 0, keys, 0, keyIndex);
System.arraycopy(l.keys, keyIndex, keys, keyIndex+1, l.keys.length-keyIndex);
keys[keyIndex] = key;
System.arraycopy(l.values, 0, values, 0, keyIndex);
System.arraycopy(l.values, keyIndex, values, keyIndex+1, l.values.length-keyIndex);
values[keyIndex] = value;
if (l.keys.length < b) {
/**
* Insert.
*/
// the new arrays are small enough to fit in a single node,
// so we replace l by a new node containing these arrays.
p.children[ixToL] = new Node(keys, values, null, true);
} else {
/**
* Overflow.
*/
// the new arrays are too big to fit in a single node,
// so we replace l by a new subtree containing three new nodes:
// a parent, and two leaves.
// the new arrays are then split between the two new leaves.
final int size1 = keys.length/2;
final Object[] keys1 = new Object[size1];
final Object[] values1 = new Object[size1];
System.arraycopy(keys, 0, keys1, 0, size1);
System.arraycopy(values, 0, values1, 0, size1);
final int size2 = keys.length - size1;
final Object[] keys2 = new Object[size2];
final Object[] values2 = new Object[size2];
System.arraycopy(keys, size1, keys2, 0, size2);
System.arraycopy(values, size1, values2, 0, size2);
final Node newL = new Node(
new Object[]{keys2[0]},
null,
(Node[]) new Node[]{
new Node(keys1, values1, null, true),
new Node(keys2, values2, null, true)
},
gp == null);
// note: weight of new internal node newL will be zero,
// unless it is the root. this is because we test
// gp == null, above. in doing this, we are actually
// performing Root-Zero at the same time as this Overflow
// if newL will become the root.
p.children[ixToL] = newL;
// if the new internal node newL is not the root, then we need
// to perform some rebalancing (at least one Split or Absorb)
if (hasWeightViolation(newL)) fixWeightViolation(gp, p, newL, ixToP, ixToL);
}
++size;
return null;
}
}
/**
* Removes a key from the dictionary (eliminating any value associated with
* it), and returns the value that was associated with the key just before
* the key was removed.
* Precondition: key != null
*
* @param key the key to remove from the dictionary
* @return the value associated with the key just before key was removed
*/
public synchronized V remove(final K key) {
/**
* search.
*/
final Comparable super K> k = comparable(key);
Node gp = null;
Node p = root;
Node l = p.children[0];
int ixToP = -1;
int ixToL = -1;
int ix = 0;
while (true) {
ixToP = ixToL;
ixToL = ix;
ix = l.getChildIndex(k);
if (l.isLeaf()) break;
gp = p;
p = l;
l = l.children[ix];
}
/**
* do the update.
*/
final int keyIndex = l.getKeyIndex(k);
if (!l.containsKey(keyIndex)) {
/**
* if l does not contain key, we are done.
*/
return null;
} else {
/**
* if l contains key, replace l by a new copy that does not contain key.
*/
final V oldValue = (V) l.values[keyIndex];
final Object[] keys = new Object[l.keys.length-1];
final Object[] values = new Object[l.keys.length-1];
System.arraycopy(l.keys, 0, keys, 0, keyIndex);
System.arraycopy(l.keys, keyIndex+1, keys, keyIndex, keys.length-keyIndex);
System.arraycopy(l.values, 0, values, 0, keyIndex);
System.arraycopy(l.values, keyIndex+1, values, keyIndex, values.length-keyIndex);
p.children[ixToL] = new Node(keys, values, null, true);
/**
* Compress may be needed at p after removing key.
*/
if (hasDegreeOrSlackViolation(p)) fixDegreeOrSlackViolation(gp, p, ixToP);
--size;
return oldValue;
}
}
private Comparable super K> comparable(final Object key) {
if (key == null) {
throw new NullPointerException();
}
if (comparator == null) {
return (Comparable super K>)key;
}
return new Comparable() {
final Comparator super K> _cmp = comparator;
@SuppressWarnings("unchecked")
public int compareTo(final K rhs) { return _cmp.compare((K)key, rhs); }
};
}
// retrieves the current parent of a node in the tree.
// this procedure could be replaced by parent pointers stored in nodes.
// precondition: node just be in the tree.
private Node getParent(final Node node) {
if (node == root) return null;
final Comparable super K> k = comparable(node.keys[0]);
Node p = root;
Node l = p.children[0];
while (true) {
if (l == node) break;
if (l.isLeaf()) return null;
p = l;
l = l.children[l.getChildIndex(k)];
}
return p;
}
private int getNumberOfKeysInChildren(final Node p) {
int result = 0;
for (int i=0;i p) {
int result = 0;
for (int i=0;i gp, final Node p, final int ixToP) {
if (gp == null) return; // this line may be unnecessary
// assert: gp is non-null
// assert: p is internal
if (p.children.length < 2) { // degree violation
/**
* If p has fewer than 2 children,
* then we cannot do a Compress or One-Child here
* until we first do Compress or One-Child at gp.
*/
final Node ggp = getParent(gp);
// since this is not a concurrent implementation, ggp and gp are still in the tree.
fixDegreeOrSlackViolation(ggp, gp, ggp.getChildIndex(gp));
// if the recursive call replaced p, then we hand off responsibility
// for the violation we were trying to fix to the recursive call.
// otherwise, p is still in the tree, and we still need to fix
// the violation we found earlier. we make a recursive call
// to fix the violation. (another way to do this that avoids making
// a recursive call is to wrap this function in a "retry loop."
if (!p.replacedByCompressOrOneChild) {
if (gp.replacedByCompressOrOneChild) {
// if gp was replaced, we must search for the new parent of p
final Node newgp = getParent(p);
fixDegreeOrSlackViolation(newgp, p, newgp.getChildIndex(p));
} else {
// otherwise, gp is still in the tree and gp[ixToP] = p
fixDegreeOrSlackViolation(gp, p, ixToP);
}
}
} else { // slack violation
/**
* NOTE: the following code performs Compress if the children of p
* contain at most |children(p)| * b - b keys, and it will
* perform One-Child otherwise.
* To see why, let c = total degree of p's children,
* and k = # of p's children.
* The only difference between Compress and One-Child is that
* One-Child does not change the number of children p has.
* The line "numberOfNodes = ((numberOfKeys + (b-1)) / b)",
* which determines how many children p will have after the
* update below takes effect, evaluates to:
* ceiling(c/b) when Compress should occur
* [i.e., when c is less than or equal to kb-b], and
* k when One-Child should occur
* [i.e., when c is greater than kb-b].
* So, whenever One-Child is supposed to occur, the number of
* children of p will not change (which means the update performed
* is One-Child).
*/
// since leaves and internal nodes use different fields of the node,
// we have to have two separate code paths to do CompressOrOneChild
// for the cases when
// 1. all children of p are leaves, and
// 2. all children of p are internal.
int numberOfNodes;
Node[] childrenNewP;
K[] keysNewP;
if (p.children[0].isLeaf()) { // assert: all children of p are leaves
/**
* if p's children are leaves, we replace these leaves
* with new copies that evenly share the keys/values originally
* contained in the children of p.
*/
// this is wasted computation (done before the call to compress),
// but at least the data should all be cached...
int numberOfKeys = getNumberOfKeysInChildren(p);
// combine keys and values of all children into big arrays
final K[] keys = (K[]) new Comparable[numberOfKeys];
final V[] values = (V[]) new Object[numberOfKeys];
numberOfKeys = 0;
for (int i=0;i[]) new Node[numberOfNodes];
for (int i=0;i(keysNode, valuesNode, null, true);
}
// divide remaining keys&values into leaves of degree keysPerNodeFloor
for (int i=0;i(keysNode, valuesNode, null, true);
}
// build keys array for new parent
keysNewP = (K[]) new Comparable[numberOfNodes-1];
for (int i=1;i[] children = (Node[]) new Node[numberOfChildren];
numberOfChildren = 0;
for (int i=0;i[]) new Node[numberOfNodes];
for (int i=0;i[] childrenNode = (Node[]) new Node[childrenPerNodeCeil];
System.arraycopy(keys, childrenPerNodeCeil*i, keysNode, 0, childrenPerNodeCeil-1);
System.arraycopy(children, childrenPerNodeCeil*i, childrenNode, 0, childrenPerNodeCeil);
childrenNewP[i] = new Node(keysNode, null, childrenNode, true);
}
// divide remaining keys&pointers into internal nodes of degree childrenPerNodeFloor
for (int i=0;i[] childrenNode = (Node[]) new Node[childrenPerNodeFloor];
System.arraycopy(keys, childrenPerNodeCeil*nodesWithCeil+childrenPerNodeFloor*i, keysNode, 0, childrenPerNodeFloor-1);
System.arraycopy(children, childrenPerNodeCeil*nodesWithCeil+childrenPerNodeFloor*i, childrenNode, 0, childrenPerNodeFloor);
childrenNewP[i+nodesWithCeil] = new Node(keysNode, null, childrenNode, true);
}
// build keys array for new parent
keysNewP = (K[]) new Comparable[numberOfNodes-1];
for (int i=0;i newP = new Node(keysNewP, null, childrenNewP, true);
gp.children[ixToP] = newP;
/**
* Compress may be needed at the grandparent gp.
*/
if (hasDegreeOrSlackViolation(gp)) {
final Node ggp = getParent(gp);
// since this is not a concurrent implementation, ggp and gp are still in the tree.
fixDegreeOrSlackViolation(ggp, gp, ggp.getChildIndex(gp));
}
/**
* Compress may be needed at some children of the new internal node newP.
*/
if (!newP.children[0].isLeaf()) {
// assert: all children of newP are internal
for (int i=0;i currentP = getParent(childrenNewP[i]);
fixDegreeOrSlackViolation(currentP, childrenNewP[i], currentP.getChildIndex(childrenNewP[i]));
}
}
}
}
}
}
private boolean hasDegreeOrSlackViolation(final Node p) {
if (p.isLeaf()) return false;
// if a Compress/One-Child C (at parent(p)) replaced p,
// then C is responsible for any violation that was at p before C.
if (p.replacedByCompressOrOneChild) return false;
// check if any child has exactly one child pointer
for (int i=0;i gp, final Node p, final Node l, final int ixToP, final int ixToL) {
// merge keys of p and l into one big array (and similarly for children)
// (we essentially replace the pointer to l with the contents of l)
final int c = p.children.length + l.children.length;
final int size = c-1;
final K[] keys = (K[]) new Comparable[size-1];
final Node[] children = (Node[]) new Node[size];
System.arraycopy(p.children, 0, children, 0, ixToL);
System.arraycopy(l.children, 0, children, ixToL, l.children.length);
System.arraycopy(p.children, ixToL+1, children, ixToL+l.children.length, p.children.length-(ixToL+1));
System.arraycopy(p.keys, 0, keys, 0, ixToL);
System.arraycopy(l.keys, 0, keys, ixToL, l.keys.length);
System.arraycopy(p.keys, ixToL, keys, ixToL+l.keys.length, p.keys.length-ixToL);
if (size <= b) {
/**
* Absorb.
*/
// the new arrays are small enough to fit in a single node,
// so we replace p by a new internal node.
final Node newP = new Node(keys, null, children, true);
gp.children[ixToP] = newP;
/**
* Compress may be needed at the new internal node we created
* (since we move grandchildren from two parents together).
*/
if (hasDegreeOrSlackViolation(newP)) {
// since this is not a concurrent implementation, gp and newP are in the tree.
fixDegreeOrSlackViolation(gp, newP, gp.getChildIndex(newP));
}
} else {
/**
* Split.
*/
// the new arrays are too big to fit in a single node,
// so we replace p by a new internal node and two new children.
// we take the big merged array and split it into two arrays,
// which are used to create two new children u and v.
// we then create a new internal node (whose weight will be zero
// if it is not the root), with u and v as its children.
final int size1 = size / 2;
final int size2 = size - size1;
final K[] keys1 = (K[]) new Comparable[size1-1];
final K[] keys2 = (K[]) new Comparable[size2-1];
final Node[] children1 = (Node[]) new Node[size1];
final Node[] children2 = (Node[]) new Node[size2];
System.arraycopy(keys, 0, keys1, 0, size1-1);
System.arraycopy(keys, size1, keys2, 0, size2-1);
System.arraycopy(children, 0, children1, 0, size1);
System.arraycopy(children, size1, children2, 0, size2);
final Node left = new Node(keys1, null, children1, true);
final Node right = new Node(keys2, null, children2, true);
final Node newP = new Node(
new Comparable[]{keys[size1-1]},
null,
(Node[]) new Node[]{left, right},
gp == root);
gp.children[ixToP] = newP;
/**
* Split may be needed at the new parent we created.
*/
if (hasWeightViolation(newP)) {
final Node ggp = getParent(gp);
// since this is not a concurrent implementation,
// we know ggp, gp, newP are still in the tree.
fixWeightViolation(ggp, gp, newP, ggp.getChildIndex(gp), ixToP);
}
/**
* Compress may be needed at the new children we created.
*/
if (hasDegreeOrSlackViolation(left)) {
final Node leftP = getParent(left);
// left is not in the tree only if a compress replaced left
// (since the recursive split calls cannot replace left).
// however, isCompressNeeded returns false if a compress replaced left,
// and leftP is in the tree if left is, so left and leftP are in the tree.
fixDegreeOrSlackViolation(leftP, left, leftP.getChildIndex(left));
}
if (hasDegreeOrSlackViolation(right)) {
final Node rightP = getParent(right);
// same comment as above, but with "right" instead of "left."
fixDegreeOrSlackViolation(rightP, right, rightP.getChildIndex(right));
}
}
}
private boolean hasWeightViolation(final Node p) {
return !p.weight;
}
private static class Node {
public final Object[] keys;
public final Object[] values;
public final Node[] children;
public final boolean weight;
public boolean replacedByCompressOrOneChild;
public Node(final Object[] keys, final Object[] values, final Node[] children, final boolean weight) {
this.keys = keys;
this.values = values;
this.children = children;
this.weight = weight;
}
public boolean isLeaf() {
return children == null;
}
public boolean containsKey(final Comparable super K> key) {
return containsKey(getKeyIndex(key));
}
public boolean containsKey(final int keyIndex) {
return (keyIndex >= 0);
}
/**
* if this returns a negative value, add one and then negate it to
* learn where key should appear in the array.
*/
public int getKeyIndex(final Comparable super K> key) {
if (keys == null || keys.length == 0) return -1;
return Arrays.binarySearch(keys, key, null);
}
public int getChildIndex(final Node child) {
if (child == null) return 0;
if (child.keys == null) return 0;
return getChildIndex((Comparable) child.keys[0]);
}
public int getChildIndex(final Comparable super K> key) {
return getChildIndex(getKeyIndex(key), key);
}
public int getChildIndex(int keyIndex, final Comparable super K> key) {
if (keyIndex < 0) { // key not in node
return -(keyIndex + 1); // return position of first key greater than key (i.e., the position key would be at)
} else { // key in node
return keyIndex + 1; // return 1+position key is at
}
}
public String getKeysString() {
StringBuilder sb = new StringBuilder();
for (int i=0;i