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;