Renamed Trie to Tree for consistency.
This is in the context of SDN-IP's patricia tree.
Change-Id: I59437fb49580aba01a287e9bc0bf035c093c7b95
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 {