Renamed Trie to Tree for consistency.
This is in the context of SDN-IP's patricia tree.
Change-Id: I59437fb49580aba01a287e9bc0bf035c093c7b95
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTree.java b/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTree.java
new file mode 100644
index 0000000..3a6a46c
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTree.java
@@ -0,0 +1,519 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * Implements a patricia tree. See {@link IPatriciaTree} for a description of
+ * how the tree works and its usage.
+ *
+ * @param <V> the type of objects that will be stored in the tree
+ */
+public class PatriciaTree<V> implements IPatriciaTree<V> {
+ private final byte[] maskBits = {(byte) 0x00, (byte) 0x80, (byte) 0xc0, (byte) 0xe0, (byte) 0xf0,
+ (byte) 0xf8, (byte) 0xfc, (byte) 0xfe, (byte) 0xff};
+
+ private final int maxPrefixLength;
+
+ private Node top;
+
+ /**
+ * Class constructor which takes the maximum length of strings that can be
+ * stored in the tree. This is used as a sanity check to prevent
+ * excessively long strings from being added, as this could slow down
+ * lookups.
+ *
+ * @param maxPrefixLength the maximum length of prefixes
+ */
+ public PatriciaTree(int maxPrefixLength) {
+ this.maxPrefixLength = maxPrefixLength;
+ }
+
+ @Override
+ public V put(Prefix prefix, V value) {
+ synchronized (this) {
+ if (prefix == null || value == null) {
+ throw new IllegalArgumentException("Null argument");
+ }
+
+ if (prefix.getPrefixLength() > maxPrefixLength) {
+ throw new IllegalArgumentException(String.format(
+ "Prefix length %d is greater than max prefix length %d",
+ prefix.getPrefixLength(), maxPrefixLength));
+ }
+
+ Node node = top;
+ Node match = null;
+
+ while (node != null
+ && node.prefix.getPrefixLength() <= prefix.getPrefixLength()
+ && checkKeyMatch(node.prefix.getAddress(),
+ node.prefix.getPrefixLength(),
+ prefix.getAddress(),
+ prefix.getPrefixLength())) {
+ if (node.prefix.getPrefixLength() == prefix.getPrefixLength()) {
+ /*
+ * Prefix is already in tree. This may be an aggregate node, in which case
+ * we are inserting a new prefix, or it could be an actual node, in which
+ * case we are inserting a new nexthop for the prefix and should return
+ * the old nexthop.
+ */
+ V oldValue = node.value;
+ node.value = value;
+ return oldValue;
+ }
+
+ match = node;
+
+ if (checkBit(prefix.getAddress(), node.prefix.getPrefixLength())) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ Node add = null;
+
+ if (node == null) {
+ //add = new Node(p, r);
+ add = new Node(prefix);
+ add.value = value;
+
+ if (match == null) {
+ top = add;
+ } else {
+ linkNodes(match, add);
+ }
+ } else {
+ add = findCommonNode(node, prefix.getAddress(), prefix.getPrefixLength());
+
+ if (match == null) {
+ top = add;
+ } else {
+ linkNodes(match, add);
+ }
+ linkNodes(add, node);
+
+ if (add.prefix.getPrefixLength() == prefix.getPrefixLength()) {
+ add.value = value;
+ } else {
+ match = add;
+
+ //add = new Node(p, r);
+ add = new Node(prefix);
+ add.value = value;
+ linkNodes(match, add);
+ }
+ }
+
+ //If we added a new Node, there was no previous mapping
+ return null;
+ //return addReference(add);
+ }
+ }
+
+ /*exact match*/
+ @Override
+ public V lookup(Prefix prefix) {
+ synchronized (this) {
+ if (prefix.getPrefixLength() > maxPrefixLength) {
+ return null;
+ }
+
+ /*
+ Node node = top;
+
+ while (node != null
+ && node.prefix.getPrefixLength() <= p.getPrefixLength()
+ && key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), p.getAddress(), p.getPrefixLength()) == true) {
+ if (node.prefix.getPrefixLength() == p.getPrefixLength()) {
+ //return addReference(node);
+ return node.rib;
+ }
+
+ if (bit_check(p.getAddress(), node.prefix.getPrefixLength()) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+ */
+
+ Node node = findNode(prefix);
+
+ return node == null ? null : node.value;
+ }
+ }
+
+ // closest containing prefix
+ @Override
+ public V match(Prefix prefix) {
+ //TODO
+ synchronized (this) {
+ if (prefix.getPrefixLength() > maxPrefixLength) {
+ return null;
+ }
+
+ Node closestNode = findClosestNode(prefix);
+
+ return closestNode == null ? null : closestNode.value;
+ }
+ }
+
+ @Override
+ public boolean remove(Prefix prefix, V value) {
+ synchronized (this) {
+ if (prefix == null || value == null) {
+ return false;
+ }
+
+ Node node = findNode(prefix);
+
+ if (node == null || node.isAggregate() || !node.value.equals(value)) {
+ //Given <prefix, nexthop> mapping is not in the tree
+ return false;
+ }
+
+ if (node.left != null && node.right != null) {
+ //Remove the RibEntry entry and leave this node as an aggregate node
+ //In the future, maybe we should re-evaluate what the aggregate prefix should be?
+ //It shouldn't necessarily stay the same.
+ //More complicated if the above prefix is also aggregate.
+ node.value = null;
+ return true;
+ }
+
+ Node child;
+ if (node.left != null) {
+ child = node.left;
+ } else {
+ child = node.right;
+ }
+
+ Node parent = node.parent;
+
+ if (child != null) {
+ child.parent = parent;
+ }
+
+ if (parent != null) {
+ if (parent.left == node) {
+ parent.left = child;
+ } else {
+ parent.right = child;
+ }
+ } else {
+ top = child;
+ }
+
+ /*
+ * TODO not sure what to do here. I think this is lazily deleting aggregate nodes,
+ * notice that it used to do nothing if it detected both children were not null earlier.
+ * But here, what we really should do is reevaluate the aggregate prefix of the parent
+ * node (if it is indeed an aggregate). Because at the moment, no aggregate node will ever
+ * be removed. BUT, I don't actually think this presents a correctness problem, at
+ * least from an external point of view.
+ */
+ //if (parent != null && parent.refCount == 0) {
+ //node_remove(parent);
+ //}
+
+ return true;
+ }
+ }
+
+ @Override
+ public Iterator<Entry<V>> iterator() {
+ return new PatriciaTreeIterator(top);
+ }
+
+ private Node findNode(Prefix prefix) {
+ Node node = top;
+
+ while (node != null
+ && node.prefix.getPrefixLength() <= prefix.getPrefixLength()
+ && checkKeyMatch(node.prefix.getAddress(),
+ node.prefix.getPrefixLength(),
+ prefix.getAddress(), prefix.getPrefixLength())) {
+ if (node.prefix.getPrefixLength() == prefix.getPrefixLength()) {
+ //return addReference(node);
+ return node;
+ }
+
+ if (checkBit(prefix.getAddress(), node.prefix.getPrefixLength())) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ return null;
+ }
+
+ private Node findClosestNode(Prefix prefix) {
+ Node node = top;
+ Node match = null;
+
+ while (node != null
+ && node.prefix.getPrefixLength() <= prefix.getPrefixLength()
+ && checkKeyMatch(node.prefix.getAddress(),
+ node.prefix.getPrefixLength(),
+ prefix.getAddress(), prefix.getPrefixLength())) {
+ if (!node.isAggregate()) {
+ match = node;
+ }
+
+ if (checkBit(prefix.getAddress(), node.prefix.getPrefixLength())) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ return match;
+ }
+
+ /*
+ * Receives a 1-based bit index
+ * Returns a 1-based byte index
+ * eg. (0 => 1), 1 => 1, 8 => 1, 9 => 2, 17 => 3
+ */
+ private int getByteContainingBit(int bitNumber) {
+ return Math.max((bitNumber + 7) / 8, 1);
+ }
+
+ private boolean checkKeyMatch(byte[] key1, int key1Length, byte[] key2, int key2Length) {
+ //int offset;
+ //int shift;
+
+ if (key1Length > key2Length) {
+ return false;
+ }
+
+ int offset = (Math.min(key1Length, key2Length)) / 8;
+ int shift = (Math.min(key1Length, key2Length)) % 8;
+
+ if (shift != 0) {
+ if ((maskBits[shift] & (key1[offset] ^ key2[offset])) != 0) {
+ return false;
+ }
+ }
+
+ while (offset != 0) {
+ offset--;
+ if (key1[offset] != key2[offset]) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private boolean checkBit(byte[] key, int keyBits) {
+ int offset = keyBits / 8;
+ int shift = 7 - (keyBits % 8);
+ int bit = key[offset] & 0xff;
+
+ bit >>= shift;
+
+ return ((bit & 1) == 1);
+ }
+
+ private void linkNodes(Node node, Node add) {
+ boolean bit = checkBit(add.prefix.getAddress(), node.prefix.getPrefixLength());
+
+ if (bit) {
+ node.right = add;
+ } else {
+ node.left = add;
+ }
+ add.parent = node;
+ }
+
+ private Node findCommonNode(Node node, byte[] key, int keyBits) {
+ int i;
+ int limit = Math.min(node.prefix.getPrefixLength(), keyBits) / 8;
+
+ for (i = 0; i < limit; i++) {
+ if (node.prefix.getAddress()[i] != key[i]) {
+ break;
+ }
+ }
+
+ int commonLen = i * 8;
+ int boundary = 0;
+
+ if (commonLen != keyBits) {
+ byte diff = (byte) (node.prefix.getAddress()[i] ^ key[i]);
+ byte mask = (byte) 0x80;
+ int shiftMask = 0;
+
+ while (commonLen < keyBits && ((mask & diff) == 0)) {
+ boundary = 1;
+
+ shiftMask = (mask & 0xff);
+ shiftMask >>= 1;
+ mask = (byte) shiftMask;
+
+ commonLen++;
+ }
+ }
+
+ //Creating a new Prefix with a prefix length of common_len
+ //Bits are copied from node's up until the common_len'th bit
+ //RibEntry is null, because this is an aggregate prefix - it's not
+ //actually been added to the tree.
+
+ byte[] newPrefix = new byte[getByteContainingBit(maxPrefixLength)];
+
+ int j;
+ for (j = 0; j < i; j++) {
+ newPrefix[j] = node.prefix.getAddress()[j];
+ }
+
+ if (boundary != 0) {
+ newPrefix[j] =
+ (byte) (node.prefix.getAddress()[j] & maskBits[commonLen % 8]);
+ }
+
+ //return new Node(new Prefix(newPrefix, common_len), null);
+ return new Node(new Prefix(newPrefix, commonLen));
+ //return add;
+ }
+
+ private class Node {
+ public Node parent;
+ public Node left;
+ public Node right;
+
+ public final Prefix prefix;
+ public V value;
+
+ //public Node(Prefix p, RibEntry r) {
+ // this.prefix = p;
+ // this.rib = r;
+ //}
+ public Node(Prefix p) {
+ this.prefix = p;
+ }
+
+ public boolean isAggregate() {
+ return value == null;
+ }
+
+ public Entry<V> getEntry() {
+ return new PatriciaTreeEntry(prefix, value);
+ }
+ }
+
+ private class PatriciaTreeEntry implements Entry<V> {
+ private final Prefix prefix;
+ private final V value;
+
+ public PatriciaTreeEntry(Prefix prefix, V value) {
+ this.prefix = prefix;
+ this.value = value;
+ }
+
+ @Override
+ public Prefix getPrefix() {
+ return prefix;
+ }
+
+ @Override
+ public V getValue() {
+ return value;
+ }
+ }
+
+ private class PatriciaTreeIterator implements Iterator<Entry<V>> {
+ private Node current;
+ private boolean started; // initialized to false
+
+ public PatriciaTreeIterator(Node start) {
+ current = start;
+
+ //If the start is an aggregate node fast forward to find the next valid node
+ if (current != null && current.isAggregate()) {
+ current = findNext(current);
+ }
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (current == null) {
+ return false;
+ }
+
+ if (!started) {
+ return true;
+ }
+
+ return findNext(current) != null;
+ }
+
+ @Override
+ public Entry<V> next() {
+ if (current == null) {
+ throw new NoSuchElementException();
+ }
+
+ if (!started) {
+ started = true;
+ return current.getEntry();
+ }
+
+ current = findNext(current);
+ if (current == null) {
+ throw new NoSuchElementException();
+ }
+
+ return current.getEntry();
+ }
+
+ @Override
+ public void remove() {
+ // TODO This could be implemented, if it were needed
+ throw new NoSuchElementException();
+ }
+
+ private Node findNext(Node node) {
+ Node next = null;
+
+ if (node.left != null) {
+ next = node.left;
+ //addReference(next);
+ //delReference(node);
+ //return next;
+ } else if (node.right != null) {
+ next = node.right;
+ //addReference(next);
+ //delReference(node);
+ //return next;
+ } else {
+ //Node start = node;
+ while (node.parent != null) {
+ if (node.parent.left == node && node.parent.right != null) {
+ next = node.parent.right;
+ //addReference(next);
+ //delReference(start);
+ //return next;
+ break;
+ }
+ node = node.parent;
+ }
+ }
+
+ if (next == null) {
+ return null;
+ }
+
+ //If the node doesn't have a value, it's not an actual node, it's an artifically
+ //inserted aggregate node. We don't want to return these to the user.
+ if (next.isAggregate()) {
+ return findNext(next);
+ }
+
+ return next;
+ }
+ }
+}