Replaced our old Patricia tree with Google's concurrent radix tree
This required some changes to the Prefix class to store a binary string
representation of the prefix to use as a key in the radix tree.
Also unrelated, bounds checking of the Prefix class has been improved and some
Prefix unit tests have been added.
Change-Id: I56f5b69346801ec70535ed470ae064b1fdf8cfdf
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/web/IncomingRequestResource.java b/src/main/java/net/onrc/onos/apps/sdnip/web/IncomingRequestResource.java
index 690ec4d..5a35bb4 100644
--- a/src/main/java/net/onrc/onos/apps/sdnip/web/IncomingRequestResource.java
+++ b/src/main/java/net/onrc/onos/apps/sdnip/web/IncomingRequestResource.java
@@ -3,7 +3,6 @@
import java.util.Iterator;
import net.onrc.onos.apps.sdnip.ISdnIpService;
-import net.onrc.onos.apps.sdnip.IPatriciaTree;
import net.onrc.onos.apps.sdnip.Prefix;
import net.onrc.onos.apps.sdnip.RestClient;
import net.onrc.onos.apps.sdnip.RibEntry;
@@ -17,6 +16,9 @@
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
+import com.googlecode.concurrenttrees.common.KeyValuePair;
+import com.googlecode.concurrenttrees.radix.RadixTree;
+
/**
* REST resource that handles REST calls from BGPd. This is the interface BGPd
* uses to push RIB entries (routes) to SDN-IP.
@@ -38,27 +40,26 @@
get(ISdnIpService.class.getCanonicalName());
if (dest == null) {
- IPatriciaTree<RibEntry> ptree = sdnIp.getPtree();
+ RadixTree<RibEntry> radixTree = sdnIp.getPtree();
output.append("{\n \"rib\": [\n");
boolean printed = false;
- synchronized (ptree) {
- Iterator<IPatriciaTree.Entry<RibEntry>> it = ptree.iterator();
- while (it.hasNext()) {
- IPatriciaTree.Entry<RibEntry> entry = it.next();
+ Iterator<KeyValuePair<RibEntry>> it =
+ radixTree.getKeyValuePairsForKeysStartingWith("").iterator();
+ while (it.hasNext()) {
+ KeyValuePair<RibEntry> entry = it.next();
- if (printed) {
- output.append(",\n");
- }
-
- output.append(" {\"prefix\": \"");
- output.append(entry.getPrefix());
- output.append("\", \"nexthop\": \"");
- output.append(entry.getValue().getNextHop().getHostAddress());
- output.append("\"}");
-
- printed = true;
+ if (printed) {
+ output.append(",\n");
}
+
+ output.append(" {\"prefix\": \"");
+ output.append(entry.getKey());
+ output.append("\", \"nexthop\": \"");
+ output.append(entry.getValue().getNextHop().getHostAddress());
+ output.append("\"}");
+
+ printed = true;
}
output.append("\n ]\n}\n");