Renamed Trie to Tree for consistency.
This is in the context of SDN-IP's patricia tree.
Change-Id: I59437fb49580aba01a287e9bc0bf035c093c7b95
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/BgpRoute.java b/src/main/java/net/onrc/onos/apps/bgproute/BgpRoute.java
index 8f42605..ed70ae4 100644
--- a/src/main/java/net/onrc/onos/apps/bgproute/BgpRoute.java
+++ b/src/main/java/net/onrc/onos/apps/bgproute/BgpRoute.java
@@ -84,8 +84,8 @@
private IRestApiService restApi;
private IProxyArpService proxyArp;
- private IPatriciaTrie<RibEntry> ptree;
- private IPatriciaTrie<Interface> interfacePtrie;
+ private IPatriciaTree<RibEntry> ptree;
+ private IPatriciaTree<Interface> interfacePtree;
private BlockingQueue<RibUpdate> ribUpdates;
private String bgpdRestIp;
@@ -222,10 +222,10 @@
throw new ConfigurationRuntimeException("Error in JSON file", e);
}
- // Populate the interface Patricia Trie
+ // Populate the interface Patricia Tree
for (Interface intf : interfaces.values()) {
Prefix prefix = new Prefix(intf.getIpAddress().getAddress(), intf.getPrefixLength());
- interfacePtrie.put(prefix, intf);
+ interfacePtree.put(prefix, intf);
}
}
@@ -260,8 +260,8 @@
public void init(FloodlightModuleContext context)
throws FloodlightModuleException {
- ptree = new PatriciaTrie<RibEntry>(32);
- interfacePtrie = new PatriciaTrie<Interface>(32);
+ ptree = new PatriciaTree<RibEntry>(32);
+ interfacePtree = new PatriciaTree<Interface>(32);
ribUpdates = new LinkedBlockingQueue<RibUpdate>();
@@ -327,13 +327,13 @@
}
@Override
- public IPatriciaTrie<RibEntry> getPtree() {
+ public IPatriciaTree<RibEntry> getPtree() {
return ptree;
}
@Override
public void clearPtree() {
- ptree = new PatriciaTrie<RibEntry>(32);
+ ptree = new PatriciaTree<RibEntry>(32);
}
@Override
@@ -466,7 +466,7 @@
} else {
//Route to non-peer
log.debug("Route to non-peer {}", dstIpAddress);
- egressInterface = interfacePtrie.match(
+ egressInterface = interfacePtree.match(
new Prefix(dstIpAddress.getAddress(), 32));
if (egressInterface == null) {
log.warn("No outgoing interface found for {}", dstIpAddress.getHostAddress());
@@ -596,7 +596,7 @@
if (ptree.remove(prefix, update.getRibEntry())) {
/*
- * Only delete flows if an entry was actually removed from the trie.
+ * Only delete flows if an entry was actually removed from the tree.
* If no entry was removed, the <prefix, nexthop> wasn't there so
* it's probably already been removed and we don't need to do anything
*/
@@ -1363,13 +1363,13 @@
@Override
public boolean isInterfaceAddress(InetAddress address) {
- Interface intf = interfacePtrie.match(new Prefix(address.getAddress(), 32));
+ Interface intf = interfacePtree.match(new Prefix(address.getAddress(), 32));
return (intf != null && intf.getIpAddress().equals(address));
}
@Override
public boolean inConnectedNetwork(InetAddress address) {
- Interface intf = interfacePtrie.match(new Prefix(address.getAddress(), 32));
+ Interface intf = interfacePtree.match(new Prefix(address.getAddress(), 32));
return (intf != null && !intf.getIpAddress().equals(address));
}
@@ -1385,7 +1385,7 @@
@Override
public Interface getOutgoingInterface(InetAddress dstIpAddress) {
- return interfacePtrie.match(new Prefix(dstIpAddress.getAddress(), 32));
+ return interfacePtree.match(new Prefix(dstIpAddress.getAddress(), 32));
}
@Override
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteResource.java b/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteResource.java
index 9dd4b9b..1b20449 100644
--- a/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteResource.java
+++ b/src/main/java/net/onrc/onos/apps/bgproute/BgpRouteResource.java
@@ -32,14 +32,14 @@
get(IBgpRouteService.class.getCanonicalName());
if (dest == null) {
- IPatriciaTrie<RibEntry> ptree = bgpRoute.getPtree();
+ IPatriciaTree<RibEntry> ptree = bgpRoute.getPtree();
output.append("{\n \"rib\": [\n");
boolean printed = false;
synchronized (ptree) {
- Iterator<IPatriciaTrie.Entry<RibEntry>> it = ptree.iterator();
+ Iterator<IPatriciaTree.Entry<RibEntry>> it = ptree.iterator();
while (it.hasNext()) {
- IPatriciaTrie.Entry<RibEntry> entry = it.next();
+ IPatriciaTree.Entry<RibEntry> entry = it.next();
if (printed) {
output.append(",\n");
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/IBgpRouteService.java b/src/main/java/net/onrc/onos/apps/bgproute/IBgpRouteService.java
index fa2d3fc..effc81b 100644
--- a/src/main/java/net/onrc/onos/apps/bgproute/IBgpRouteService.java
+++ b/src/main/java/net/onrc/onos/apps/bgproute/IBgpRouteService.java
@@ -15,7 +15,7 @@
*
* @return the PATRICIA tree.
*/
- public IPatriciaTrie<RibEntry> getPtree();
+ public IPatriciaTree<RibEntry> getPtree();
/**
* Gets the IP address of REST server on the BGPd side. This is used to
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTrie.java b/src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTree.java
similarity index 95%
rename from src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTrie.java
rename to src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTree.java
index 32a7d2e..1ef9eae 100644
--- a/src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTrie.java
+++ b/src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTree.java
@@ -13,15 +13,15 @@
* {@code <prefix, next_hop>},
* e.g. {@code <192.168.1.0/24, 10.0.0.1>}
* <p/>
- * These updates are stored in the patricia trie, which acts as a map from
+ * 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_trie">Patricia tree</a>
+ * @see <a href="http://en.wikipedia.org/wiki/Patricia_tree">Patricia tree</a>
*/
-public interface IPatriciaTrie<V> {
+public interface IPatriciaTree<V> {
/**
* Puts a new mapping into the patricia tree.
*
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTrie.java b/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTree.java
similarity index 96%
rename from src/main/java/net/onrc/onos/apps/bgproute/PatriciaTrie.java
rename to src/main/java/net/onrc/onos/apps/bgproute/PatriciaTree.java
index 0c64502..3a6a46c 100644
--- a/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTrie.java
+++ b/src/main/java/net/onrc/onos/apps/bgproute/PatriciaTree.java
@@ -4,12 +4,12 @@
import java.util.NoSuchElementException;
/**
- * Implements a patricia tree. See {@link IPatriciaTrie} for a description of
+ * 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 PatriciaTrie<V> implements IPatriciaTrie<V> {
+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};
@@ -25,7 +25,7 @@
*
* @param maxPrefixLength the maximum length of prefixes
*/
- public PatriciaTrie(int maxPrefixLength) {
+ public PatriciaTree(int maxPrefixLength) {
this.maxPrefixLength = maxPrefixLength;
}
@@ -224,7 +224,7 @@
@Override
public Iterator<Entry<V>> iterator() {
- return new PatriciaTrieIterator(top);
+ return new PatriciaTreeIterator(top);
}
private Node findNode(Prefix prefix) {
@@ -361,7 +361,7 @@
//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 trie.
+ //actually been added to the tree.
byte[] newPrefix = new byte[getByteContainingBit(maxPrefixLength)];
@@ -401,15 +401,15 @@
}
public Entry<V> getEntry() {
- return new PatriciaTrieEntry(prefix, value);
+ return new PatriciaTreeEntry(prefix, value);
}
}
- private class PatriciaTrieEntry implements Entry<V> {
+ private class PatriciaTreeEntry implements Entry<V> {
private final Prefix prefix;
private final V value;
- public PatriciaTrieEntry(Prefix prefix, V value) {
+ public PatriciaTreeEntry(Prefix prefix, V value) {
this.prefix = prefix;
this.value = value;
}
@@ -425,11 +425,11 @@
}
}
- private class PatriciaTrieIterator implements Iterator<Entry<V>> {
+ private class PatriciaTreeIterator implements Iterator<Entry<V>> {
private Node current;
private boolean started; // initialized to false
- public PatriciaTrieIterator(Node start) {
+ public PatriciaTreeIterator(Node start) {
current = start;
//If the start is an aggregate node fast forward to find the next valid node
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/RibEntry.java b/src/main/java/net/onrc/onos/apps/bgproute/RibEntry.java
index 7ad1d3d..2392e01 100644
--- a/src/main/java/net/onrc/onos/apps/bgproute/RibEntry.java
+++ b/src/main/java/net/onrc/onos/apps/bgproute/RibEntry.java
@@ -19,8 +19,8 @@
/*
* Store the sequence number information provided on the update here for
* now. I think this *should* really be in the RibUpdate, and we should
- * store RibUpdates in the Ptrie. But, that's a bigger change to change
- * what the Ptrie stores.
+ * store RibUpdates in the Ptree. But, that's a bigger change to change
+ * what the Ptree stores.
*/
private final long sysUpTime;
private final long sequenceNum;
diff --git a/src/test/java/net/onrc/onos/apps/bgproute/PatriciaTrieTest.java b/src/test/java/net/onrc/onos/apps/bgproute/PatriciaTreeTest.java
similarity index 72%
rename from src/test/java/net/onrc/onos/apps/bgproute/PatriciaTrieTest.java
rename to src/test/java/net/onrc/onos/apps/bgproute/PatriciaTreeTest.java
index af59af5..ea4e600 100644
--- a/src/test/java/net/onrc/onos/apps/bgproute/PatriciaTrieTest.java
+++ b/src/test/java/net/onrc/onos/apps/bgproute/PatriciaTreeTest.java
@@ -13,15 +13,15 @@
import org.junit.Before;
import org.junit.Test;
-public class PatriciaTrieTest {
+public class PatriciaTreeTest {
- IPatriciaTrie<RibEntry> ptrie;
+ IPatriciaTree<RibEntry> ptree;
Prefix[] prefixes;
Map<Prefix, RibEntry> mappings;
@Before
public void setUp() throws Exception {
- ptrie = new PatriciaTrie<RibEntry>(32);
+ ptree = new PatriciaTree<RibEntry>(32);
mappings = new HashMap<Prefix, RibEntry>();
prefixes = new Prefix[]{
@@ -38,7 +38,7 @@
for (int i = 0; i < prefixes.length; i++) {
mappings.put(prefixes[i], new RibEntry("192.168.10.101", "192.168.20." + i));
- ptrie.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));
}
}
@@ -48,28 +48,28 @@
@Test
public void testPut() {
- IPatriciaTrie<RibEntry> ptrie = new PatriciaTrie<RibEntry>(32);
+ IPatriciaTree<RibEntry> 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 = ptrie.put(p1, r1);
+ RibEntry retval = ptree.put(p1, r1);
assertNull(retval);
- retval = ptrie.lookup(p1);
+ 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 = ptrie.put(p2, r2);
+ 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 = ptrie.put(p3, r3);
+ 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 = ptrie.put(p3, r3new);
+ retval = ptree.put(p3, r3new);
assertNotNull(retval);
assertTrue(retval.equals(r3));
assertTrue(retval == r3); //should be the same object
@@ -78,30 +78,30 @@
//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 = ptrie.put(p4, r4);
+ retval = ptree.put(p4, r4);
assertNull(retval);
- retval = ptrie.lookup(p4);
+ 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 = ptrie.lookup(entry.getKey());
+ 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 = ptrie.lookup(p1);
+ 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 = ptrie.put(p2, r2);
+ retval = ptree.put(p2, r2);
assertNull(retval);
- retval = ptrie.lookup(p2);
+ retval = ptree.lookup(p2);
assertTrue(retval.equals(r2));
}
@@ -115,13 +115,13 @@
Prefix p5 = new Prefix("192.168.8.0", 22);
Prefix p6 = new Prefix("192.168.8.0", 21);
- assertTrue(ptrie.match(p1).equals(mappings.get(prefixes[0])));
- assertTrue(ptrie.match(p2).equals(mappings.get(prefixes[0])));
- assertTrue(ptrie.match(p3).equals(mappings.get(prefixes[1])));
- assertNull(ptrie.match(p4));
- assertTrue(ptrie.match(p5).equals(mappings.get(prefixes[2])));
- //System.out.println(ptrie.match(p6).getNextHop().getHostAddress());
- assertTrue(ptrie.match(p6).equals(mappings.get(prefixes[8])));
+ 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
@@ -131,50 +131,50 @@
@Test
public void testRemove() {
Prefix p1 = new Prefix("192.168.8.0", 23);
- RibEntry retval = ptrie.lookup(p1);
+ RibEntry retval = ptree.lookup(p1);
assertNotNull(retval);
- boolean success = ptrie.remove(p1, 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 = ptrie.remove(null, null);
+ success = ptree.remove(null, null);
assertFalse(success);
- success = ptrie.remove(p2, null);
+ success = ptree.remove(p2, null);
assertFalse(success);
//Check other prefixes are still there
- retval = ptrie.lookup(p2);
+ retval = ptree.lookup(p2);
assertNotNull(retval);
- retval = ptrie.lookup(p3);
+ retval = ptree.lookup(p3);
assertNotNull(retval);
Prefix p4 = new Prefix("9.17.0.0", 12);
- retval = ptrie.lookup(p4);
+ retval = ptree.lookup(p4);
assertNotNull(retval);
- success = ptrie.remove(p4, retval);
+ success = ptree.remove(p4, retval);
assertTrue(success);
- success = ptrie.remove(p4, retval);
+ success = ptree.remove(p4, retval);
assertFalse(success);
//Check other prefixes are still there
- retval = ptrie.lookup(p2);
+ retval = ptree.lookup(p2);
assertNotNull(retval);
- retval = ptrie.lookup(p3);
+ retval = ptree.lookup(p3);
assertNotNull(retval);
Prefix p5 = new Prefix("192.0.0.0", 7);
- retval = ptrie.lookup(p5);
+ retval = ptree.lookup(p5);
assertNotNull(retval);
- success = ptrie.remove(p5, retval);
+ success = ptree.remove(p5, retval);
assertTrue(success);
//Check other prefixes are still there
- retval = ptrie.lookup(p2);
+ retval = ptree.lookup(p2);
assertNotNull(retval);
- retval = ptrie.lookup(p3);
+ retval = ptree.lookup(p3);
assertNotNull(retval);
@@ -184,19 +184,19 @@
public void testIterator() {
int[] order = new int[]{7, 5, 3, 8, 2, 1, 0, 4, 6};
- Iterator<IPatriciaTrie.Entry<RibEntry>> it = ptrie.iterator();
+ Iterator<IPatriciaTree.Entry<RibEntry>> it = ptree.iterator();
int i = 0;
assertTrue(it.hasNext());
while (it.hasNext()) {
- IPatriciaTrie.Entry<RibEntry> entry = it.next();
+ IPatriciaTree.Entry<RibEntry> entry = it.next();
assertTrue(entry.getPrefix().equals(prefixes[order[i]]));
i++;
}
assertFalse(it.hasNext());
assertTrue(i == order.length);
- IPatriciaTrie<RibEntry> pt = new PatriciaTrie<RibEntry>(32);
- Iterator<IPatriciaTrie.Entry<RibEntry>> it2 = pt.iterator();
+ 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/bgproute/PtreeTest.java b/src/test/java/net/onrc/onos/apps/bgproute/PtreeTest.java
index 1b4b8b1..ab461f6 100644
--- a/src/test/java/net/onrc/onos/apps/bgproute/PtreeTest.java
+++ b/src/test/java/net/onrc/onos/apps/bgproute/PtreeTest.java
@@ -25,14 +25,14 @@
private Logger log = LoggerFactory.getLogger(PtreeTest.class);
private Ptree ptree;
- private PatriciaTrie<RibEntry> ooptrie;
+ private PatriciaTree<RibEntry> ooPtree;
private Map<String, byte[]> byteAddresses;
@Before
public void setUp() throws Exception {
ptree = new Ptree(32);
- ooptrie = new PatriciaTrie<RibEntry>(32);
+ ooPtree = new PatriciaTree<RibEntry>(32);
String[] strPrefixes = {
"192.168.10.0/24",
@@ -54,7 +54,7 @@
PtreeNode node = ptree.acquire(byteAddresses.get(prefix), prefixLength);
// node.rib = new RibEntry("192.168.10.101", "192.168.60.1");
- ooptrie.put(new Prefix(byteAddresses.get(prefix), prefixLength),
+ ooPtree.put(new Prefix(byteAddresses.get(prefix), prefixLength),
new RibEntry("192.168.10.101", "192.168.60.1"));
}
}
@@ -200,11 +200,11 @@
@Test
public void testIteration() {
- Iterator<IPatriciaTrie.Entry<RibEntry>> it = ooptrie.iterator();
+ Iterator<IPatriciaTree.Entry<RibEntry>> it = ooPtree.iterator();
while (it.hasNext()) {
- IPatriciaTrie.Entry<RibEntry> entry = it.next();
- log.debug("PatriciaTrie prefix {} \t {}", entry.getPrefix(), entry.getPrefix().printAsBits());
+ IPatriciaTree.Entry<RibEntry> entry = it.next();
+ log.debug("PatriciaTree prefix {} \t {}", entry.getPrefix(), entry.getPrefix().printAsBits());
}
try {