Removed unused Patricia Tree classes
Change-Id: I52f55bb74d0bef1b182ece5fc552b5d047531620
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/IPatriciaTree.java b/src/main/java/net/onrc/onos/apps/sdnip/IPatriciaTree.java
deleted file mode 100644
index 21cb823..0000000
--- a/src/main/java/net/onrc/onos/apps/sdnip/IPatriciaTree.java
+++ /dev/null
@@ -1,100 +0,0 @@
-package net.onrc.onos.apps.sdnip;
-
-import java.util.Iterator;
-
-/**
- * A PATRICIA tree is data structure for storing data where entries aggregate
- * based on shared prefixes. They provide lookups in O(k) where k is the
- * maximum length of the strings in the tree. They work well for storing IP
- * addresses.
- * <p/>
- * SDN-IP uses a patricia tree to store routes learnt from BGPd. BGPd sends
- * route updates in the form:
- * {@code <prefix, next_hop>},
- * e.g. {@code <192.168.1.0/24, 10.0.0.1>}
- * <p/>
- * These updates are stored in the patricia tree, which acts as a map from
- * {@code prefix} to {@code next_hop}. {@code next_hop} values can be looked up
- * by prefix.
- *
- * @param <V> The class of the data to stored in the patricia tree
- *
- * @see <a href="http://en.wikipedia.org/wiki/Patricia_tree">Patricia tree</a>
- */
-public interface IPatriciaTree<V> {
- /**
- * Puts a new mapping into the patricia tree.
- *
- * @param prefix the Prefix which is the key for this entry
- * @param value the value that maps to the Prefix
- * @return the old value that was mapped to the Prefix, or null if there
- * was no such mapping
- */
- public V put(Prefix prefix, V value);
-
- /**
- * Searches the tree for a prefix that exactly matches the argument. If an
- * exact match for the prefix is found in the tree, the value it maps to is
- * returned. Otherwise, null is returned.
- *
- * @param prefix the prefix to look up in the tree
- * @return the value if the prefix was found, otherwise null
- */
- public V lookup(Prefix prefix);
-
- /**
- * Searches the tree for the closest containing prefix of the supplied
- * argument. If an exact match is found, that will be returned. Otherwise,
- * the value of the most specific prefix that contains the argument prefix
- * will be returned. If no such prefix is found, null is returned.
- *
- * @param prefix the prefix to find the closest containing match for in the
- * tree
- * @return the value of the match if one was found, otherwise null
- */
- public V match(Prefix prefix);
-
- /**
- * Removes a prefix to value mapping from the tree. The prefix argument is
- * first looked up in the same way as the {@link #lookup(Prefix)} method.
- * If an exact match to the prefix is found in the tree, its value is
- * is checked to see if it matches the supplied argument value. The prefix
- * and value will be removed only if both the prefix and value arguments
- * match a mapping in the tree.
- *
- * @param prefix the prefix to remove from the tree
- * @param value the value that must be mapped to the prefix for it to be
- * removed
- * @return true if a mapping was removed, otherwise false
- */
- public boolean remove(Prefix prefix, V value);
-
- /**
- * Gets an iterator over all mappings in the tree.
- *
- * @return an iterator that will iterate over all entries in the tree
- */
- public Iterator<Entry<V>> iterator();
-
- /**
- * Represents an entry in the patricia tree. The {@code Entry} is a mapping
- * from {@link Prefix} to a value object of type {@code V}.
- *
- * @param <V> the class of objects stored in the tree
- */
- interface Entry<V> {
- /**
- * Gets the {@link Prefix} object for this entry.
- *
- * @return the prefix for this entry
- */
- public Prefix getPrefix();
-
- /**
- * Gets the value of this entry.
- *
- * @return the value object of this entry
- */
- public V getValue();
- }
-}
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/PatriciaTree.java b/src/main/java/net/onrc/onos/apps/sdnip/PatriciaTree.java
deleted file mode 100644
index cce2630..0000000
--- a/src/main/java/net/onrc/onos/apps/sdnip/PatriciaTree.java
+++ /dev/null
@@ -1,520 +0,0 @@
-package net.onrc.onos.apps.sdnip;
-
-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;
- }
- }
-}
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/Ptree.java b/src/main/java/net/onrc/onos/apps/sdnip/Ptree.java
deleted file mode 100644
index c47ef1d..0000000
--- a/src/main/java/net/onrc/onos/apps/sdnip/Ptree.java
+++ /dev/null
@@ -1,320 +0,0 @@
-package net.onrc.onos.apps.sdnip;
-
-/*
- * TODO This Ptree needs to be refactored if we're going to use it permenantly.
- *
- * The biggest problem is it leaks PTreeNode references - these need to stay within
- * the Ptree as they contain data fundamental to the structure of the tree.
- * You should put RIB entries in and get RIB entries out.
- * Also we need to get rid of the referencing scheme to determine when to delete nodes.
- * Deletes should be explicit, and there's no need to keep track of references if
- * we don't leak them out the the Ptree.
- */
-public class Ptree {
- private int maxKeyBits;
- private int maxKeyOctets;
- //private int refCount;
- private PtreeNode top;
- private byte[] maskBits =
- {(byte) 0x00, (byte) 0x80, (byte) 0xc0, (byte) 0xe0, (byte) 0xf0,
- (byte) 0xf8, (byte) 0xfc, (byte) 0xfe, (byte) 0xff};
-
- public Ptree(int maxKeyBits) {
- this.maxKeyBits = maxKeyBits;
- maxKeyOctets = bitToOctet(maxKeyBits);
- //refCount = 0;
- }
-
- public synchronized PtreeNode acquire(byte[] key) {
- return acquire(key, maxKeyBits);
- }
-
- public synchronized PtreeNode acquire(byte[] key, int keyBits) {
- if (keyBits > maxKeyBits) {
- return null;
- }
-
- PtreeNode node = top;
- PtreeNode match = null;
-
- while (node != null
- && node.keyBits <= keyBits
- && keyMatch(node.key, node.keyBits, key, keyBits)) {
- if (node.keyBits == keyBits) {
- return addReference(node);
- }
-
- match = node;
-
- if (bitCheck(key, node.keyBits)) {
- node = node.right;
- } else {
- node = node.left;
- }
- }
-
- PtreeNode add = null;
-
- if (node == null) {
- add = new PtreeNode(key, keyBits, maxKeyOctets);
-
- if (match != null) {
- nodeLink(match, add);
- } else {
- top = add;
- }
- } else {
- add = nodeCommon(node, key, keyBits);
-
- if (match != null) {
- nodeLink(match, add);
- } else {
- top = add;
- }
- nodeLink(add, node);
-
- if (add.keyBits != keyBits) {
- match = add;
-
- add = new PtreeNode(key, keyBits, maxKeyOctets);
- nodeLink(match, add);
- }
- }
-
- return addReference(add);
- }
-
- public synchronized PtreeNode lookup(byte[] key, int keyBits) {
- if (keyBits > maxKeyBits) {
- return null;
- }
-
- PtreeNode node = top;
-
- while (node != null
- && node.keyBits <= keyBits
- && keyMatch(node.key, node.keyBits, key, keyBits)) {
- if (node.keyBits == keyBits) {
- return addReference(node);
- }
-
- if (bitCheck(key, node.keyBits)) {
- node = node.right;
- } else {
- node = node.left;
- }
- }
- return null;
- }
-
- public synchronized PtreeNode match(byte[] key, int keyBits) {
- if (keyBits > maxKeyBits) {
- return null;
- }
- PtreeNode node = top;
- PtreeNode matched = null;
-
- if (node != null) {
-
- while (node != null
- && node.keyBits <= keyBits
- && keyMatch(node.key, node.keyBits, key, keyBits)) {
- matched = node;
-
- if (bitCheck(key, node.keyBits)) {
- node = node.right;
- } else {
- node = node.left;
- }
- }
- }
-
- if (matched != null) {
- return addReference(matched);
- }
-
- return null;
- }
-
- public synchronized PtreeNode begin() {
- if (top == null) {
- return null;
- }
- return addReference(top);
- }
-
- public synchronized PtreeNode next(PtreeNode node) {
- PtreeNode next;
-
- if (node.left != null) {
- next = node.left;
- addReference(next);
- delReference(node);
- return next;
- }
- if (node.right != null) {
- next = node.right;
- addReference(next);
- delReference(node);
- return next;
- }
-
- PtreeNode 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;
- }
- node = node.parent;
- }
-
- delReference(start);
-
- return null;
- }
-
- public static int bitToOctet(int keyBits) {
- return Math.max((keyBits + 7) / 8, 1);
- }
-
- private PtreeNode addReference(PtreeNode node) {
- node.refCount++;
- return node;
- }
-
- public synchronized void delReference(PtreeNode node) {
- if (node.refCount > 0) {
- node.refCount--;
- }
- if (node.refCount == 0) {
- nodeRemove(node);
- }
- }
-
- private boolean keyMatch(byte[] key1, int key1Len, byte[] key2, int key2Len) {
- int offset;
- int shift;
-
- if (key1Len > key2Len) {
- return false;
- }
-
- offset = (Math.min(key1Len, key2Len)) / 8;
- shift = (Math.min(key1Len, key2Len)) % 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 bitCheck(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 nodeLink(PtreeNode node, PtreeNode add) {
- boolean bit = bitCheck(add.key, node.keyBits);
-
- if (bit) {
- node.right = add;
- } else {
- node.left = add;
- }
- add.parent = node;
- }
-
- private PtreeNode nodeCommon(PtreeNode node, byte[] key, int keyBits) {
- int i;
- int limit = Math.min(node.keyBits, keyBits) / 8;
-
- for (i = 0; i < limit; i++) {
- if (node.key[i] != key[i]) {
- break;
- }
- }
-
- int commonLen = i * 8;
- int boundary = 0;
-
- if (commonLen != keyBits) {
- byte diff = (byte) (node.key[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++;
- }
- }
-
- PtreeNode add = new PtreeNode(null, commonLen, maxKeyOctets);
-
- int j;
- for (j = 0; j < i; j++) {
- add.key[j] = node.key[j];
- }
-
- if (boundary != 0) {
- add.key[j] = (byte) (node.key[j] & maskBits[add.keyBits % 8]);
- }
-
- return add;
- }
-
- private void nodeRemove(PtreeNode node) {
- PtreeNode child;
- PtreeNode parent;
-
- if (node.left != null && node.right != null) {
- return;
- }
-
- if (node.left != null) {
- child = node.left;
- } else {
- child = node.right;
- }
-
- 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;
- }
-
- if (parent != null && parent.refCount == 0) {
- nodeRemove(parent);
- }
- }
-}
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/PtreeNode.java b/src/main/java/net/onrc/onos/apps/sdnip/PtreeNode.java
deleted file mode 100644
index 912db1c..0000000
--- a/src/main/java/net/onrc/onos/apps/sdnip/PtreeNode.java
+++ /dev/null
@@ -1,44 +0,0 @@
-package net.onrc.onos.apps.sdnip;
-
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-public class PtreeNode {
- public PtreeNode parent;
- public PtreeNode left;
- public PtreeNode right;
-
- public byte[] key;
- public int keyBits;
-
- public int refCount;
-
- // public RibEntry rib;
- private static final Logger log = LoggerFactory.getLogger(PtreeNode.class);
-
- PtreeNode(byte[] key, int keyBits, int maxKeyOctet) {
- parent = null;
- left = null;
- right = null;
- refCount = 0;
- // rib = null;
- this.key = new byte[maxKeyOctet];
- this.keyBits = keyBits;
- log.debug("inside Ptreenode constructor key {} bits {}", key, keyBits);
-
- int octet = Ptree.bitToOctet(keyBits);
- for (int i = 0; i < maxKeyOctet; i++) {
- if (i < octet) {
- if (key != null) {
- log.debug(octet + ": filling key[{}] {}", i, key[i]);
- this.key[i] = key[i];
- } else {
- log.debug("no filling, null key");
- }
- } else {
- log.debug("filling key {} as 0", i);
- this.key[i] = 0;
- }
- }
- }
-}
diff --git a/src/test/java/net/onrc/onos/apps/sdnip/PatriciaTreeTest.java b/src/test/java/net/onrc/onos/apps/sdnip/PatriciaTreeTest.java
deleted file mode 100644
index c5138c1..0000000
--- a/src/test/java/net/onrc/onos/apps/sdnip/PatriciaTreeTest.java
+++ /dev/null
@@ -1,204 +0,0 @@
-package net.onrc.onos.apps.sdnip;
-
-import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertNotNull;
-import static org.junit.Assert.assertNull;
-import static org.junit.Assert.assertTrue;
-
-import java.util.HashMap;
-import java.util.Iterator;
-import java.util.Map;
-
-import org.junit.After;
-import org.junit.Before;
-import org.junit.Test;
-
-public class PatriciaTreeTest {
-
- IPatriciaTree<RibEntry> ptree;
- Prefix[] prefixes;
- Map<Prefix, RibEntry> mappings;
-
- @Before
- public void setUp() throws Exception {
- ptree = new PatriciaTree<RibEntry>(32);
- mappings = new HashMap<Prefix, RibEntry>();
-
- prefixes = new Prefix[]{
- new Prefix("192.168.10.0", 24),
- new Prefix("192.168.8.0", 23),
- new Prefix("192.168.8.0", 22),
- new Prefix("192.0.0.0", 7),
- new Prefix("192.168.11.0", 24),
- new Prefix("10.0.23.128", 25),
- new Prefix("206.17.144.0", 20),
- new Prefix("9.17.0.0", 12),
- new Prefix("192.168.0.0", 16)
- };
-
- for (int i = 0; i < prefixes.length; i++) {
- mappings.put(prefixes[i], new RibEntry("192.168.10.101", "192.168.20." + i));
- ptree.put(prefixes[i], new RibEntry("192.168.10.101", "192.168.20." + i));
- }
- }
-
- @After
- public void tearDown() throws Exception {
- }
-
- @Test
- public void testPut() {
- ptree = new PatriciaTree<RibEntry>(32);
-
- Prefix p1 = new Prefix("192.168.240.0", 20);
- RibEntry r1 = new RibEntry("192.168.10.101", "192.168.60.2");
- RibEntry retval = ptree.put(p1, r1);
- assertNull(retval);
- retval = ptree.lookup(p1);
- assertTrue(r1 == retval); //should be the same object
-
- Prefix p2 = new Prefix("192.160.0.0", 12);
- RibEntry r2 = new RibEntry("192.168.10.101", "192.168.20.1");
- retval = ptree.put(p2, r2);
- assertNull(retval);
-
- Prefix p3 = new Prefix("192.168.208.0", 20);
- RibEntry r3 = new RibEntry("192.168.10.101", "192.168.30.1");
- retval = ptree.put(p3, r3);
- assertNull(retval);
-
- //Insert a new RibEntry entry over a previous one
- RibEntry r3new = new RibEntry("192.168.10.101", "192.168.60.2");
- retval = ptree.put(p3, r3new);
- assertNotNull(retval);
- assertTrue(retval.equals(r3));
- assertTrue(retval == r3); //should be the same object
-
- //Now we have an aggregate node with prefix 192.168.192.0/18.
- //We will insert a RibEntry at this prefix
- Prefix p4 = new Prefix("192.168.192.0", 18);
- RibEntry r4 = new RibEntry("192.168.10.101", "192.168.40.1");
- retval = ptree.put(p4, r4);
- assertNull(retval);
- retval = ptree.lookup(p4);
- assertTrue(retval == r4); //should be the same object
- }
-
- @Test
- public void testLookup() {
- for (Map.Entry<Prefix, RibEntry> entry : mappings.entrySet()) {
- RibEntry r = ptree.lookup(entry.getKey());
- assertTrue(entry.getValue().equals(r));
- }
-
- //These are aggregate nodes in the tree. Shouldn't be returned by lookup
- Prefix p1 = new Prefix("0.0.0.0", 0);
- RibEntry retval = ptree.lookup(p1);
- assertNull(retval);
-
- //We'll put a RibEntry at an aggregate node and check if lookup returns correctly
- Prefix p2 = new Prefix("192.0.0.0", 4);
- RibEntry r2 = new RibEntry("192.168.10.101", "192.168.60.1");
- retval = ptree.put(p2, r2);
- assertNull(retval);
- retval = ptree.lookup(p2);
- assertTrue(retval.equals(r2));
- }
-
- //@Ignore
- @Test
- public void testMatch() {
- Prefix p1 = new Prefix("192.168.10.30", 32);
- Prefix p2 = new Prefix("192.168.10.30", 31);
- Prefix p3 = new Prefix("192.168.8.241", 32);
- Prefix p4 = new Prefix("1.0.0.0", 32);
- Prefix p5 = new Prefix("192.168.8.0", 22);
- Prefix p6 = new Prefix("192.168.8.0", 21);
-
- assertTrue(ptree.match(p1).equals(mappings.get(prefixes[0])));
- assertTrue(ptree.match(p2).equals(mappings.get(prefixes[0])));
- assertTrue(ptree.match(p3).equals(mappings.get(prefixes[1])));
- assertNull(ptree.match(p4));
- assertTrue(ptree.match(p5).equals(mappings.get(prefixes[2])));
- //System.out.println(ptree.match(p6).getNextHop().getHostAddress());
- assertTrue(ptree.match(p6).equals(mappings.get(prefixes[8])));
-
-
- //TODO more extensive tests
- //fail("Not yet implemented");
- }
-
- @Test
- public void testRemove() {
- Prefix p1 = new Prefix("192.168.8.0", 23);
- RibEntry retval = ptree.lookup(p1);
- assertNotNull(retval);
- boolean success = ptree.remove(p1, retval);
- assertTrue(success);
-
- Prefix p2 = new Prefix("192.168.8.0", 22);
- Prefix p3 = new Prefix("192.168.10.0", 24);
-
- //Test it does the right thing with null arguments
- success = ptree.remove(null, null);
- assertFalse(success);
- success = ptree.remove(p2, null);
- assertFalse(success);
-
- //Check other prefixes are still there
- retval = ptree.lookup(p2);
- assertNotNull(retval);
- retval = ptree.lookup(p3);
- assertNotNull(retval);
-
- Prefix p4 = new Prefix("9.17.0.0", 12);
- retval = ptree.lookup(p4);
- assertNotNull(retval);
- success = ptree.remove(p4, retval);
- assertTrue(success);
- success = ptree.remove(p4, retval);
- assertFalse(success);
-
- //Check other prefixes are still there
- retval = ptree.lookup(p2);
- assertNotNull(retval);
- retval = ptree.lookup(p3);
- assertNotNull(retval);
-
- Prefix p5 = new Prefix("192.0.0.0", 7);
- retval = ptree.lookup(p5);
- assertNotNull(retval);
- success = ptree.remove(p5, retval);
- assertTrue(success);
-
- //Check other prefixes are still there
- retval = ptree.lookup(p2);
- assertNotNull(retval);
- retval = ptree.lookup(p3);
- assertNotNull(retval);
-
-
- }
-
- @Test(expected = java.util.NoSuchElementException.class)
- public void testIterator() {
- int[] order = new int[]{7, 5, 3, 8, 2, 1, 0, 4, 6};
-
- Iterator<IPatriciaTree.Entry<RibEntry>> it = ptree.iterator();
- int i = 0;
- assertTrue(it.hasNext());
- while (it.hasNext()) {
- IPatriciaTree.Entry<RibEntry> entry = it.next();
- assertTrue(entry.getPrefix().equals(prefixes[order[i]]));
- i++;
- }
- assertFalse(it.hasNext());
- assertTrue(i == order.length);
-
- IPatriciaTree<RibEntry> pt = new PatriciaTree<RibEntry>(32);
- Iterator<IPatriciaTree.Entry<RibEntry>> it2 = pt.iterator();
- assertFalse(it2.hasNext());
- it.next(); //throws NoSuchElementException
- }
-
-}
diff --git a/src/test/java/net/onrc/onos/apps/sdnip/PtreeTest.java b/src/test/java/net/onrc/onos/apps/sdnip/PtreeTest.java
deleted file mode 100644
index ad36811..0000000
--- a/src/test/java/net/onrc/onos/apps/sdnip/PtreeTest.java
+++ /dev/null
@@ -1,226 +0,0 @@
-package net.onrc.onos.apps.sdnip;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
-import static org.junit.Assert.fail;
-
-import java.net.InetAddress;
-import java.net.UnknownHostException;
-import java.util.Arrays;
-import java.util.HashMap;
-import java.util.Iterator;
-import java.util.Map;
-
-import org.junit.After;
-import org.junit.Before;
-import org.junit.Ignore;
-import org.junit.Test;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import com.google.common.net.InetAddresses;
-
-public class PtreeTest {
-
- private Logger log = LoggerFactory.getLogger(PtreeTest.class);
-
- private Ptree ptree;
- private PatriciaTree<RibEntry> ooPtree;
-
- private Map<String, byte[]> byteAddresses;
-
- @Before
- public void setUp() throws Exception {
- ptree = new Ptree(32);
- ooPtree = new PatriciaTree<RibEntry>(32);
-
- String[] strPrefixes = {
- "192.168.10.0/24",
- "192.168.10.0/23",
- "192.168.10.0/22",
- "192.0.0.0/7",
- "192.168.11.0/24",
- "10.0.23.128/25",
- "206.17.144.0/20",
- "9.17.0.0/12",
- "192.168.0.0/16"
- };
-
- byteAddresses = new HashMap<String, byte[]>(strPrefixes.length + 10);
- for (String prefix : strPrefixes) {
- String address = prefix.split("/")[0];
- int prefixLength = Integer.parseInt(prefix.split("/")[1]);
- byteAddresses.put(prefix, InetAddresses.forString(address).getAddress());
-
- PtreeNode node = ptree.acquire(byteAddresses.get(prefix), prefixLength);
- // node.rib = new RibEntry("192.168.10.101", "192.168.60.1");
- ooPtree.put(new Prefix(byteAddresses.get(prefix), prefixLength),
- new RibEntry("192.168.10.101", "192.168.60.1"));
- }
- }
-
- @After
- public void tearDown() throws Exception {
- }
-
- @Ignore
- @Test
- public void testAcquireByteArray() {
- fail("Not yet implemented");
- }
-
- @Ignore
- @Test
- public void testAcquireByteArrayInt() {
- //First let's test an empty Ptree
- Ptree localPtree = new Ptree(32);
- PtreeNode node = localPtree.acquire(new byte[]{0x00, 0x00, 0x00, 0x00});
- // assertTrue(node != null && node.rib == null);
- assertTrue(node != null);
-
- //Now let's look at the prepopulated tree
- String testPrefix = "206.17.144.0/20";
- PtreeNode existingNode = ptree.acquire(byteAddresses.get(testPrefix), 20);
- printByteArray(existingNode.key);
- printByteArray(byteAddresses.get(testPrefix));
- // assertTrue(existingNode != null && existingNode.rib == null);
- assertTrue(existingNode != null);
-
- assertTrue(Arrays.equals(existingNode.key, byteAddresses.get(testPrefix)));
- }
-
- @Test
- public void testLookup() {
- String prefix1 = "192.168.10.12";
- int length1 = 29;
- PtreeNode node1 = ptree.lookup(InetAddresses.forString(prefix1).getAddress(), length1);
-
- //There should be no direct match
- assertTrue(node1 == null);
-
- log.debug("{} null: {}", "node1", node1 == null ? "true" : "false");
-
- String prefix2 = "206.17.144.0";
- int length2 = 20;
- PtreeNode node2 = ptree.lookup(InetAddresses.forString(prefix2).getAddress(), length2);
-
- assertTrue(node2 != null);
- assertTrue(Arrays.equals(node2.key, byteAddresses.get(prefix2 + "/" + length2)));
-
- log.debug("{} null: {}", "node2", node2 == null ? "true" : "false");
- if (node2 != null) {
- log.debug("{} key: {}, keybits: {}", new Object[]{"node2", node2.key, node2.keyBits});
- }
-
- String prefix3 = "192.0.0.0";
- int length3 = 7;
- PtreeNode node3 = ptree.lookup(InetAddresses.forString(prefix3).getAddress(), length3);
- assertTrue(node3 != null);
- }
-
- @Test
- public void testMatch() {
- String prefix1 = "192.168.10.12";
- int length1 = 29;
- PtreeNode node1 = ptree.match(InetAddresses.forString(prefix1).getAddress(), length1);
-
- //There should be no direct match, but we should get the covering prefix
- assertTrue(node1 != null);
- assertTrue(Arrays.equals(node1.key, byteAddresses.get("192.168.10.0/24")));
-
- log.debug("{} null: {}", "node1", node1 == null ? "true" : "false");
- if (node1 != null) {
- log.debug("{} key: {}, keybits: {}", new Object[]{"node1", node1.key, node1.keyBits});
- }
- }
-
- @Ignore
- @Test
- public void testTraverse() {
-
- String expected = "[0, 0, 0, 0]/0\n";
- expected += "[8, 0, 0, 0]/6\n";
- expected += "[9, 17, 0, 0]/12\n";
- expected += "[10, 0, 23, -128]/25\n";
- expected += "[-64, 0, 0, 0]/4\n";
- expected += "[-64, -88, 0, 0]/16\n";
- expected += "[-64, -88, 8, 0]/22\n";
- expected += "[-64, -88, 10, 0]/23\n";
- expected += "[-64, -88, 10, 0]/24\n";
- expected += "[-64, -88, 11, 0]/24\n";
- expected += "[-50, 17, -112, 0]/20\n";
-
- PtreeNode node;
- String result = "";
-
- for (node = ptree.begin(); node != null; node = ptree.next(node)) {
- result += printByteArray(node.key) + "/" + node.keyBits + "\n";
- }
-
- assertEquals(expected, result);
- }
-
- @Ignore
- @Test
- public void testBegin() {
- fail("Not yet implemented");
- }
-
- @Ignore
- @Test
- public void testNext() {
- fail("Not yet implemented");
- }
-
- @Ignore
- @Test
- public void testDelReference() {
- fail("Not yet implemented");
- }
-
- @Ignore
- @Test
- public void testMisc() {
- int bitIndex = -1;
- int index = bitIndex / Byte.SIZE;
- int bit = bitIndex % Byte.SIZE;
-
- log.debug("index {} bit {}", index, bit);
- log.debug("percent {}", 1 % 8);
-
- //PtreeNode node1 = new PtreeNode(new byte[] {0x0, 0x0, 0x0, 0x0}, 0, 4);
- PtreeNode node1 = new PtreeNode(null, 0, 4);
- log.debug("node1: key {}, keybits {}", printByteArray(node1.key), node1.keyBits);
-
- //PtreeNode node2 = new PtreeNode(new byte[] {(byte)0xff, (byte)0xff, (byte)0xff, (byte)0xff},
- PtreeNode node2 = new PtreeNode(null,
- 32, 4);
- log.debug("node2: key {}, keybits {}", printByteArray(node2.key), node2.keyBits);
- }
-
- @Test
- public void testIteration() throws UnknownHostException {
- Iterator<IPatriciaTree.Entry<RibEntry>> it = ooPtree.iterator();
-
- while (it.hasNext()) {
- IPatriciaTree.Entry<RibEntry> entry = it.next();
- log.debug("PatriciaTree prefix {} \t {}", entry.getPrefix(), entry.getPrefix().printAsBits());
- }
-
- PtreeNode node;
- for (node = ptree.begin(); node != null; node = ptree.next(node)) {
- log.debug("Ptree prefix {}/{}", InetAddress.getByAddress(node.key).getHostAddress(), node.keyBits);
- }
- }
-
- private String printByteArray(byte[] array) {
- String result = "[";
- for (byte b : array) {
- result += b + ", ";
- }
- result = result.substring(0, result.length() - 2);
- result += "]";
- return result;
- }
-
-}