Paramaterized the Patricia Trie
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRoute.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRoute.java
index c36d4a5..827c8d2 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRoute.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRoute.java
@@ -88,7 +88,7 @@
protected ProxyArpManager proxyArp;
//protected static Ptree ptree;
- protected IPatriciaTrie ptree;
+ protected IPatriciaTrie<RibEntry> ptree;
protected BlockingQueue<RibUpdate> ribUpdates;
protected String bgpdRestIp;
@@ -253,7 +253,7 @@
throws FloodlightModuleException {
//ptree = new Ptree(32);
- ptree = new PatriciaTrie(32);
+ ptree = new PatriciaTrie<RibEntry>(32);
ribUpdates = new LinkedBlockingQueue<RibUpdate>();
@@ -314,14 +314,14 @@
}
//public Ptree getPtree() {
- public IPatriciaTrie getPtree() {
+ public IPatriciaTrie<RibEntry> getPtree() {
return ptree;
}
public void clearPtree() {
//ptree = null;
//ptree = new Ptree(32);
- ptree = new PatriciaTrie(32);
+ ptree = new PatriciaTrie<RibEntry>(32);
}
public String getBGPdRestIp() {
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRouteResource.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRouteResource.java
index c9b3265..f058843 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRouteResource.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/BgpRouteResource.java
@@ -60,7 +60,7 @@
}
else {
//Ptree ptree = bgpRoute.getPtree();
- IPatriciaTrie ptree = bgpRoute.getPtree();
+ IPatriciaTrie<RibEntry> ptree = bgpRoute.getPtree();
output += "{\n \"rib\": [\n";
boolean printed = false;
@@ -78,16 +78,16 @@
}*/
synchronized(ptree) {
- Iterator<IPatriciaTrie.Entry> it = ptree.iterator();
+ Iterator<IPatriciaTrie.Entry<RibEntry>> it = ptree.iterator();
while (it.hasNext()) {
- IPatriciaTrie.Entry entry = it.next();
+ IPatriciaTrie.Entry<RibEntry> entry = it.next();
if (printed == true) {
output += ",\n";
}
output += " {\"prefix\": \"" + entry.getPrefix() +"\", ";
- output += "\"nexthop\": \"" + entry.getRib().getNextHop().getHostAddress() +"\"}";
+ output += "\"nexthop\": \"" + entry.getValue().getNextHop().getHostAddress() +"\"}";
//output += ",\n";
printed = true;
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/IBgpRouteService.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/IBgpRouteService.java
index ba912ce..954976c 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/IBgpRouteService.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/IBgpRouteService.java
@@ -7,7 +7,7 @@
//public RibEntry lookupRib(byte[] dest);
//public Ptree getPtree();
- public IPatriciaTrie getPtree();
+ public IPatriciaTrie<RibEntry> getPtree();
public String getBGPdRestIp();
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/IPatriciaTrie.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/IPatriciaTrie.java
index 7fd7382..1fb0716 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/IPatriciaTrie.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/IPatriciaTrie.java
@@ -2,19 +2,19 @@
import java.util.Iterator;
-public interface IPatriciaTrie {
- public RibEntry put(Prefix p, RibEntry r);
+public interface IPatriciaTrie<V> {
+ public V put(Prefix prefix, V value);
- public RibEntry lookup(Prefix p);
+ public V lookup(Prefix prefix);
- public RibEntry match(Prefix p);
+ public V match(Prefix prefix);
- public boolean remove(Prefix p, RibEntry r);
+ public boolean remove(Prefix prefix, V value);
- public Iterator<Entry> iterator();
+ public Iterator<Entry<V>> iterator();
- interface Entry {
+ interface Entry<V> {
public Prefix getPrefix();
- public RibEntry getRib();
+ public V getValue();
}
}
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 86bc8cf..28093fc 100644
--- a/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
@@ -3,7 +3,7 @@
import java.util.Iterator;
import java.util.NoSuchElementException;
-public class PatriciaTrie implements IPatriciaTrie{
+public class PatriciaTrie<V> implements IPatriciaTrie<V> {
private final byte maskBits[] = {(byte)0x00, (byte)0x80, (byte)0xc0, (byte)0xe0, (byte)0xf0,
(byte)0xf8, (byte)0xfc, (byte)0xfe, (byte)0xff};
@@ -15,14 +15,15 @@
this.maxPrefixLength = maxPrefixLength;
}
- public synchronized RibEntry put(Prefix p, RibEntry r) {
- if (p.getPrefixLength() > maxPrefixLength) {
+ @Override
+ public synchronized V put(Prefix prefix, V value) {
+ if (prefix.getPrefixLength() > maxPrefixLength) {
throw new IllegalArgumentException(String.format(
"Prefix length %d is greater than max prefix length %d",
- p.getPrefixLength(), maxPrefixLength));
+ prefix.getPrefixLength(), maxPrefixLength));
}
- if (p == null || r == null) {
+ if (prefix == null || value == null) {
throw new NullPointerException();
}
@@ -30,23 +31,23 @@
Node match = null;
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()) {
+ && 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.
*/
- RibEntry oldRib = node.rib;
- node.rib = r;
- return oldRib;
+ V oldValue = node.value;
+ node.value = value;
+ return oldValue;
}
match = node;
- if (bit_check(p.getAddress(), node.prefix.getPrefixLength()) == true) {
+ if (bit_check(prefix.getAddress(), node.prefix.getPrefixLength()) == true) {
node = node.right;
} else {
node = node.left;
@@ -56,7 +57,9 @@
Node add = null;
if (node == null) {
- add = new Node(p, r);
+ //add = new Node(p, r);
+ add = new Node(prefix);
+ add.value = value;
if (match != null) {
node_link(match, add);
@@ -64,7 +67,7 @@
top = add;
}
} else {
- add = node_common(node, p.getAddress(), p.getPrefixLength());
+ add = node_common(node, prefix.getAddress(), prefix.getPrefixLength());
if (add == null) {
//I think this is -ENOMEM?
//return null;
@@ -77,14 +80,16 @@
}
node_link(add, node);
- if (add.prefix.getPrefixLength() != p.getPrefixLength()) {
+ if (add.prefix.getPrefixLength() != prefix.getPrefixLength()) {
match = add;
- add = new Node(p, r);
+ //add = new Node(p, r);
+ add = new Node(prefix);
+ add.value = value;
node_link(match, add);
}
else {
- add.rib = r;
+ add.value = value;
}
}
@@ -94,10 +99,11 @@
}
/*exact match*/
- public synchronized RibEntry lookup(Prefix p) {
+ @Override
+ public synchronized V lookup(Prefix prefix) {
//TODO
- if (p.getPrefixLength() > maxPrefixLength) {
+ if (prefix.getPrefixLength() > maxPrefixLength) {
return null;
}
@@ -120,28 +126,30 @@
}
*/
- Node node = findNode(p);
+ Node node = findNode(prefix);
- return node == null ? null : node.rib;
+ return node == null ? null : node.value;
}
/*closest containing prefix*/
- public synchronized RibEntry match(Prefix p) {
+ @Override
+ public synchronized V match(Prefix prefix) {
//TODO
return null;
}
- public synchronized boolean remove(Prefix p, RibEntry r) {
+ @Override
+ public synchronized boolean remove(Prefix prefix, V value) {
Node child;
Node parent;
- if (p == null || r == null) {
+ if (prefix == null || value == null) {
return false;
}
- Node node = findNode(p);
+ Node node = findNode(prefix);
- if (node == null || node.rib == null || !node.rib.equals(r)) {
+ if (node == null || node.isAggregate() || !node.value.equals(value)) {
//Given <prefix, nexthop> mapping is not in the tree
return false;
}
@@ -151,7 +159,7 @@
//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.rib = null;
+ node.value = null;
return true;
}
@@ -192,22 +200,23 @@
return true;
}
- public Iterator<Entry> iterator() {
+ @Override
+ public Iterator<Entry<V>> iterator() {
return new PatriciaTrieIterator(top);
}
- private Node findNode(Prefix p) {
+ private Node findNode(Prefix prefix) {
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()) {
+ && node.prefix.getPrefixLength() <= prefix.getPrefixLength()
+ && key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), prefix.getAddress(), prefix.getPrefixLength()) == true) {
+ if (node.prefix.getPrefixLength() == prefix.getPrefixLength()) {
//return addReference(node);
return node;
}
- if (bit_check(p.getAddress(), node.prefix.getPrefixLength()) == true) {
+ if (bit_check(prefix.getAddress(), node.prefix.getPrefixLength()) == true) {
node = node.right;
} else {
node = node.left;
@@ -325,7 +334,8 @@
if (boundary != 0)
newPrefix[j] = (byte)(node.prefix.getAddress()[j] & maskBits[common_len % 8]);
- return new Node(new Prefix(newPrefix, common_len), null);
+ //return new Node(new Prefix(newPrefix, common_len), null);
+ return new Node(new Prefix(newPrefix, common_len));
//return add;
}
@@ -334,26 +344,33 @@
public Node left = null;
public Node right = null;
- public Prefix prefix;
- public RibEntry rib;
+ public final Prefix prefix;
+ public V value;
- public Node(Prefix p, RibEntry r) {
+ //public Node(Prefix p, RibEntry r) {
+ // this.prefix = p;
+ // this.rib = r;
+ //}
+ public Node(Prefix p) {
this.prefix = p;
- this.rib = r;
}
- public Entry getEntry() {
- return new PatriciaTrieEntry(prefix, rib);
+ public boolean isAggregate() {
+ return value == null;
+ }
+
+ public Entry<V> getEntry() {
+ return new PatriciaTrieEntry(prefix, value);
}
}
- private class PatriciaTrieEntry implements Entry {
+ private class PatriciaTrieEntry implements Entry<V> {
private Prefix prefix;
- private RibEntry rib;
+ private V value;
- public PatriciaTrieEntry(Prefix prefix, RibEntry rib) {
+ public PatriciaTrieEntry(Prefix prefix, V value) {
this.prefix = prefix;
- this.rib = rib;
+ this.value = value;
}
@Override
@@ -362,12 +379,12 @@
}
@Override
- public RibEntry getRib() {
- return rib;
+ public V getValue() {
+ return value;
}
}
- private class PatriciaTrieIterator implements Iterator<Entry> {
+ private class PatriciaTrieIterator implements Iterator<Entry<V>> {
private Node current;
private boolean started = false;
@@ -376,7 +393,7 @@
current = start;
//If the start is an aggregate node fast forward to find the next valid node
- if (current != null && current.rib == null) {
+ if (current != null && current.isAggregate()) {
current = findNext(current);
}
}
@@ -395,7 +412,7 @@
}
@Override
- public Entry next() {
+ public Entry<V> next() {
if (current == null) {
throw new NoSuchElementException();
}
@@ -452,9 +469,9 @@
return null;
}
- //If the node doesn't have a rib, it's not an actual node, it's an artifically
+ //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.rib == null) {
+ if (next.isAggregate()) {
return findNext(next);
}
diff --git a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java
index 1af0416..29bb201 100644
--- a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java
+++ b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java
@@ -17,13 +17,13 @@
public class PatriciaTrieTest {
- IPatriciaTrie ptrie;
+ IPatriciaTrie<RibEntry> ptrie;
Prefix[] prefixes;
Map<Prefix, RibEntry> mappings;
@Before
public void setUp() throws Exception {
- ptrie = new PatriciaTrie(32);
+ ptrie = new PatriciaTrie<RibEntry>(32);
mappings = new HashMap<Prefix, RibEntry>();
prefixes = new Prefix[] {
@@ -50,7 +50,7 @@
@Test
public void testPut() {
- IPatriciaTrie ptrie = new PatriciaTrie(32);
+ IPatriciaTrie<RibEntry> ptrie = new PatriciaTrie<RibEntry>(32);
Prefix p1 = new Prefix("192.168.240.0", 20);
RibEntry r1 = new RibEntry("192.168.10.101", "192.168.60.2");
@@ -169,19 +169,19 @@
public void testIterator() {
int[] order = new int[] {7, 5, 3, 8, 2, 1, 0, 4, 6};
- Iterator<IPatriciaTrie.Entry> it = ptrie.iterator();
+ Iterator<IPatriciaTrie.Entry<RibEntry>> it = ptrie.iterator();
int i = 0;
assertTrue(it.hasNext());
while (it.hasNext()) {
- IPatriciaTrie.Entry entry = it.next();
+ IPatriciaTrie.Entry<RibEntry> entry = it.next();
assertTrue(entry.getPrefix().equals(prefixes[order[i]]));
i++;
}
assertFalse(it.hasNext());
assertTrue(i == order.length);
- IPatriciaTrie pt = new PatriciaTrie(32);
- Iterator<IPatriciaTrie.Entry> it2 = pt.iterator();
+ IPatriciaTrie<RibEntry> pt = new PatriciaTrie<RibEntry>(32);
+ Iterator<IPatriciaTrie.Entry<RibEntry>> it2 = pt.iterator();
assertFalse(it2.hasNext());
it.next(); //throws NoSuchElementException
}