Findbugs and PMD work
Change-Id: I0084f219084152fb705d76bf9d347effd9f78664
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTrie.java b/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTrie.java
index 245b574..54f8129 100644
--- a/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTrie.java
+++ b/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTrie.java
@@ -7,7 +7,7 @@
private final byte[] maskBits = {(byte) 0x00, (byte) 0x80, (byte) 0xc0, (byte) 0xe0, (byte) 0xf0,
(byte) 0xf8, (byte) 0xfc, (byte) 0xfe, (byte) 0xff};
- private int maxPrefixLength;
+ private final int maxPrefixLength;
private Node top;
@@ -16,187 +16,196 @@
}
@Override
- public synchronized V put(Prefix prefix, V value) {
- if (prefix == null || value == null) {
- throw new NullPointerException();
- }
-
- 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()
- && key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), prefix.getAddress(), prefix.getPrefixLength()) == true) {
- 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;
+ public V put(Prefix prefix, V value) {
+ synchronized (this) {
+ if (prefix == null || value == null) {
+ throw new IllegalArgumentException("Null argument");
}
- match = node;
-
- if (bit_check(prefix.getAddress(), node.prefix.getPrefixLength()) == true) {
- node = node.right;
- } else {
- node = node.left;
+ if (prefix.getPrefixLength() > maxPrefixLength) {
+ throw new IllegalArgumentException(String.format(
+ "Prefix length %d is greater than max prefix length %d",
+ prefix.getPrefixLength(), maxPrefixLength));
}
- }
- Node add = null;
+ Node node = top;
+ Node match = null;
- if (node == null) {
- //add = new Node(p, r);
- add = new Node(prefix);
- add.value = value;
+ 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;
+ }
- if (match != null) {
- node_link(match, add);
- } else {
- top = add;
+ match = node;
+
+ if (checkBit(prefix.getAddress(), node.prefix.getPrefixLength())) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
}
- } else {
- add = node_common(node, prefix.getAddress(), prefix.getPrefixLength());
- if (match != null) {
- node_link(match, add);
- } else {
- top = add;
- }
- node_link(add, node);
+ Node add = null;
- if (add.prefix.getPrefixLength() != prefix.getPrefixLength()) {
- match = add;
-
+ if (node == null) {
//add = new Node(p, r);
add = new Node(prefix);
add.value = value;
- node_link(match, add);
- } else {
- add.value = value;
- }
- }
- //If we added a new Node, there was no previous mapping
- return null;
- //return addReference(add);
+ 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 synchronized V lookup(Prefix prefix) {
- 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;
+ public V lookup(Prefix prefix) {
+ synchronized (this) {
+ if (prefix.getPrefixLength() > maxPrefixLength) {
+ return null;
}
- if (bit_check(p.getAddress(), node.prefix.getPrefixLength()) == true) {
- node = node.right;
- } else {
- node = node.left;
+ /*
+ 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;
}
- */
-
- Node node = findNode(prefix);
-
- return node == null ? null : node.value;
}
- /*closest containing prefix*/
+ // closest containing prefix
@Override
- public synchronized V match(Prefix prefix) {
+ public V match(Prefix prefix) {
//TODO
- if (prefix.getPrefixLength() > maxPrefixLength) {
- return null;
+ synchronized (this) {
+ if (prefix.getPrefixLength() > maxPrefixLength) {
+ return null;
+ }
+
+ Node closestNode = findClosestNode(prefix);
+
+ return closestNode == null ? null : closestNode.value;
}
-
- Node closestNode = findClosestNode(prefix);
-
- return closestNode == null ? null : closestNode.value;
}
@Override
- public synchronized boolean remove(Prefix prefix, V value) {
- Node child;
- Node parent;
+ public boolean remove(Prefix prefix, V value) {
+ synchronized (this) {
+ if (prefix == null || value == null) {
+ return false;
+ }
- if (prefix == null || value == null) {
- return false;
- }
+ Node node = findNode(prefix);
- 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 == 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;
+ }
- 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;
+ 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;
}
-
- 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;
- }
-
- /*
- * 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
@@ -209,13 +218,15 @@
while (node != null
&& node.prefix.getPrefixLength() <= prefix.getPrefixLength()
- && key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), prefix.getAddress(), prefix.getPrefixLength()) == true) {
+ && checkKeyMatch(node.prefix.getAddress(),
+ node.prefix.getPrefixLength(),
+ prefix.getAddress(), prefix.getPrefixLength())) {
if (node.prefix.getPrefixLength() == prefix.getPrefixLength()) {
//return addReference(node);
return node;
}
- if (bit_check(prefix.getAddress(), node.prefix.getPrefixLength()) == true) {
+ if (checkBit(prefix.getAddress(), node.prefix.getPrefixLength())) {
node = node.right;
} else {
node = node.left;
@@ -231,12 +242,14 @@
while (node != null
&& node.prefix.getPrefixLength() <= prefix.getPrefixLength()
- && key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), prefix.getAddress(), prefix.getPrefixLength()) == true) {
+ && checkKeyMatch(node.prefix.getAddress(),
+ node.prefix.getPrefixLength(),
+ prefix.getAddress(), prefix.getPrefixLength())) {
if (!node.isAggregate()) {
match = node;
}
- if (bit_check(prefix.getAddress(), node.prefix.getPrefixLength()) == true) {
+ if (checkBit(prefix.getAddress(), node.prefix.getPrefixLength())) {
node = node.right;
} else {
node = node.left;
@@ -255,16 +268,16 @@
return Math.max((bitNumber + 7) / 8, 1);
}
- private boolean key_match(byte[] key1, int key1_len, byte[] key2, int key2_len) {
+ private boolean checkKeyMatch(byte[] key1, int key1Length, byte[] key2, int key2Length) {
//int offset;
//int shift;
- if (key1_len > key2_len) {
+ if (key1Length > key2Length) {
return false;
}
- int offset = (Math.min(key1_len, key2_len)) / 8;
- int shift = (Math.min(key1_len, key2_len)) % 8;
+ 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) {
@@ -281,24 +294,20 @@
return true;
}
- private boolean bit_check(byte[] key, int key_bits) {
- int offset = key_bits / 8;
- int shift = 7 - (key_bits % 8);
+ private boolean checkBit(byte[] key, int keyBits) {
+ int offset = keyBits / 8;
+ int shift = 7 - (keyBits % 8);
int bit = key[offset] & 0xff;
bit >>= shift;
- if ((bit & 1) == 1) {
- return true;
- } else {
- return false;
- }
+ return ((bit & 1) == 1);
}
- private void node_link(Node node, Node add) {
- boolean bit = bit_check(add.prefix.getAddress(), node.prefix.getPrefixLength());
+ private void linkNodes(Node node, Node add) {
+ boolean bit = checkBit(add.prefix.getAddress(), node.prefix.getPrefixLength());
- if (bit == true) {
+ if (bit) {
node.right = add;
} else {
node.left = add;
@@ -306,9 +315,9 @@
add.parent = node;
}
- private Node node_common(Node node, byte[] key, int key_bits) {
+ private Node findCommonNode(Node node, byte[] key, int keyBits) {
int i;
- int limit = Math.min(node.prefix.getPrefixLength(), key_bits) / 8;
+ int limit = Math.min(node.prefix.getPrefixLength(), keyBits) / 8;
for (i = 0; i < limit; i++) {
if (node.prefix.getAddress()[i] != key[i]) {
@@ -319,12 +328,12 @@
int commonLen = i * 8;
int boundary = 0;
- if (commonLen != key_bits) {
+ if (commonLen != keyBits) {
byte diff = (byte) (node.prefix.getAddress()[i] ^ key[i]);
byte mask = (byte) 0x80;
int shiftMask = 0;
- while (commonLen < key_bits && ((mask & diff) == 0)) {
+ while (commonLen < keyBits && ((mask & diff) == 0)) {
boundary = 1;
shiftMask = (mask & 0xff);
@@ -335,11 +344,6 @@
}
}
- //Node add = new Node(null, common_len, maxKeyOctets);
- //if (add == null)
- //Another -ENOMEM;
- //return null;
-
//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
@@ -348,11 +352,14 @@
byte[] newPrefix = new byte[getByteContainingBit(maxPrefixLength)];
int j;
- for (j = 0; j < i; 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]);
+ 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));
@@ -360,9 +367,9 @@
}
private class Node {
- public Node parent = null;
- public Node left = null;
- public Node right = null;
+ public Node parent;
+ public Node left;
+ public Node right;
public final Prefix prefix;
public V value;
@@ -385,8 +392,8 @@
}
private class PatriciaTrieEntry implements Entry<V> {
- private Prefix prefix;
- private V value;
+ private final Prefix prefix;
+ private final V value;
public PatriciaTrieEntry(Prefix prefix, V value) {
this.prefix = prefix;
@@ -405,9 +412,8 @@
}
private class PatriciaTrieIterator implements Iterator<Entry<V>> {
-
private Node current;
- private boolean started = false;
+ private boolean started; // initialized to false
public PatriciaTrieIterator(Node start) {
current = start;