Implemented PatriciaTrie.match and put an interface PTrie in BgpRoute. Minor bug fixes to Prefix and RibEntry
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
index 28093fc..89dfb30 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
@@ -101,8 +101,6 @@
/*exact match*/
@Override
public synchronized V lookup(Prefix prefix) {
- //TODO
-
if (prefix.getPrefixLength() > maxPrefixLength) {
return null;
}
@@ -135,7 +133,13 @@
@Override
public synchronized V match(Prefix prefix) {
//TODO
- return null;
+ if (prefix.getPrefixLength() > maxPrefixLength) {
+ return null;
+ }
+
+ Node closestNode = findClosestNode(prefix);
+
+ return closestNode == null ? null : closestNode.value;
}
@Override
@@ -226,6 +230,27 @@
return null;
}
+ private Node findClosestNode(Prefix prefix) {
+ 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.isAggregate()) {
+ match = node;
+ }
+
+ if (bit_check(prefix.getAddress(), node.prefix.getPrefixLength()) == true) {
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+
+ return match;
+ }
+
/*
* Receives a 1-based bit index
* Returns a 1-based byte index