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/pom.xml b/pom.xml
index a39db9d..bced4a7 100644
--- a/pom.xml
+++ b/pom.xml
@@ -604,6 +604,11 @@
</exclusions>
</dependency>
<dependency>
+ <groupId>com.googlecode.concurrent-trees</groupId>
+ <artifactId>concurrent-trees</artifactId>
+ <version>2.4.0</version>
+ </dependency>
+ <dependency>
<groupId>org.apache.curator</groupId>
<artifactId>curator-framework</artifactId>
<version>2.4.1</version>
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/ISdnIpService.java b/src/main/java/net/onrc/onos/apps/sdnip/ISdnIpService.java
index 21ee3d3..6189aa7 100644
--- a/src/main/java/net/onrc/onos/apps/sdnip/ISdnIpService.java
+++ b/src/main/java/net/onrc/onos/apps/sdnip/ISdnIpService.java
@@ -2,6 +2,8 @@
import net.floodlightcontroller.core.module.IFloodlightService;
+import com.googlecode.concurrenttrees.radix.RadixTree;
+
/**
* The API exported by the main SDN-IP class. This is the interface between the
* REST handlers and the SDN-IP module.
@@ -9,13 +11,14 @@
public interface ISdnIpService extends IFloodlightService {
/**
- * Gets a reference to SDN-IP's PATRICIA tree which stores the route table.
+ * Gets a reference to SDN-IP's radix tree which stores the route table
+ * learnt through BGP.
*
* XXX This is a poor API because it exposes internal state of SDN-IP.
*
- * @return the PATRICIA tree.
+ * @return the radix tree
*/
- public IPatriciaTree<RibEntry> getPtree();
+ public RadixTree<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/sdnip/Prefix.java b/src/main/java/net/onrc/onos/apps/sdnip/Prefix.java
index 91510b1..d4e730d 100644
--- a/src/main/java/net/onrc/onos/apps/sdnip/Prefix.java
+++ b/src/main/java/net/onrc/onos/apps/sdnip/Prefix.java
@@ -19,10 +19,18 @@
/**
* The length of addresses this class can represent prefixes of, in bytes.
*/
- public static final int ADDRESS_LENGTH = 4;
+ public static final int ADDRESS_LENGTH_BYTES = 4;
+
+ /**
+ * The length of addresses this class can represent prefixes of, in bits.
+ */
+ public static final int MAX_PREFIX_LENGTH = Byte.SIZE * ADDRESS_LENGTH_BYTES;
+
+ public static final int MIN_PREFIX_LENGTH = 0;
private final int prefixLength;
private final byte[] address;
+ private final String binaryString;
// For verifying the arguments and pretty printing
private final InetAddress inetAddress;
@@ -32,26 +40,28 @@
* a prefix length.
* <p/>
* The valid values for addr and prefixLength are bounded by
- * {@link #ADDRESS_LENGTH}.
+ * {@link #ADDRESS_LENGTH_BYTES}.
* <p/>
* A valid addr array satisfies
- * {@code addr.length == }{@value #ADDRESS_LENGTH}.
+ * {@code addr.length == }{@value #ADDRESS_LENGTH_BYTES}.
* <p/>
* A valid prefixLength satisfies
- * {@code (prefixLength > 0 && prefixLength <=} {@link Byte#SIZE}
- * {@code * }{@value #ADDRESS_LENGTH}{@code )}.
+ * {@code (prefixLength >= 0 && prefixLength <=} {@link Byte#SIZE}
+ * {@code * }{@value #ADDRESS_LENGTH_BYTES}{@code )}.
*
* @param addr a byte array representing the address
* @param prefixLength length of the prefix of the specified address
*/
public Prefix(byte[] addr, int prefixLength) {
- if (addr == null || addr.length != ADDRESS_LENGTH ||
- prefixLength < 0 || prefixLength > ADDRESS_LENGTH * Byte.SIZE) {
+ if (addr == null || addr.length != ADDRESS_LENGTH_BYTES ||
+ prefixLength < MIN_PREFIX_LENGTH ||
+ prefixLength > MAX_PREFIX_LENGTH) {
throw new IllegalArgumentException();
}
address = canonicalizeAddress(addr, prefixLength);
this.prefixLength = prefixLength;
+ binaryString = createBinaryString();
try {
inetAddress = InetAddress.getByAddress(address);
@@ -71,13 +81,15 @@
byte[] addr = null;
addr = InetAddresses.forString(strAddress).getAddress();
- if (addr == null || addr.length != ADDRESS_LENGTH ||
- prefixLength < 0 || prefixLength > ADDRESS_LENGTH * Byte.SIZE) {
+ if (addr == null || addr.length != ADDRESS_LENGTH_BYTES ||
+ prefixLength < MIN_PREFIX_LENGTH ||
+ prefixLength > MAX_PREFIX_LENGTH) {
throw new IllegalArgumentException();
}
address = canonicalizeAddress(addr, prefixLength);
this.prefixLength = prefixLength;
+ binaryString = createBinaryString();
try {
inetAddress = InetAddress.getByAddress(address);
@@ -86,12 +98,28 @@
}
}
+ /**
+ * This method takes a byte array passed in by the user and ensures it
+ * conforms to the format we want. The byte array can contain anything,
+ * but only some of the bits are significant. The bits after
+ * prefixLengthValue are not significant, and this method will zero them
+ * out in order to ensure there is a canonical representation for each
+ * prefix. This simplifies the equals and hashcode methods, because once we
+ * have a canonical byte array representation we can simply compare byte
+ * arrays to test equality.
+ *
+ * @param addressValue the byte array to canonicalize
+ * @param prefixLengthValue The length of the prefix. Bits up to and including
+ * prefixLength are significant, bits following prefixLength are not
+ * significant and will be zeroed out.
+ * @return the canonicalized representation of the prefix
+ */
private byte[] canonicalizeAddress(byte[] addressValue,
int prefixLengthValue) {
byte[] result = new byte[addressValue.length];
if (prefixLengthValue == 0) {
- for (int i = 0; i < ADDRESS_LENGTH; i++) {
+ for (int i = 0; i < ADDRESS_LENGTH_BYTES; i++) {
result[i] = 0;
}
@@ -102,7 +130,7 @@
//Set all bytes after the end of the prefix to 0
int lastByteIndex = (prefixLengthValue - 1) / Byte.SIZE;
- for (int i = lastByteIndex; i < ADDRESS_LENGTH; i++) {
+ for (int i = lastByteIndex; i < ADDRESS_LENGTH_BYTES; i++) {
result[i] = 0;
}
@@ -122,6 +150,31 @@
}
/**
+ * Creates the binary string representation of the prefix.
+ * The strings length is equal to prefixLength.
+ *
+ * @return the binary string representation
+ */
+ private String createBinaryString() {
+ if (prefixLength == 0) {
+ return "";
+ }
+
+ StringBuilder result = new StringBuilder(prefixLength);
+ for (int i = 0; i < address.length; i++) {
+ byte b = address[i];
+ for (int j = 0; j < Byte.SIZE; j++) {
+ byte mask = (byte) (0x80 >>> j);
+ result.append(((b & mask) == 0) ? "0" : "1");
+ if (i * Byte.SIZE + j == prefixLength - 1) {
+ return result.toString();
+ }
+ }
+ }
+ return result.toString();
+ }
+
+ /**
* Gets the length of the prefix of the address.
*
* @return the prefix length
@@ -165,6 +218,15 @@
}
/**
+ * Gets a binary string representation of the prefix.
+ *
+ * @return a binary string representation
+ */
+ public String toBinaryString() {
+ return binaryString;
+ }
+
+ /**
* Print the prefix to a String showing the bits of the address.
*
* @return the bit-string of the prefix
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/SdnIp.java b/src/main/java/net/onrc/onos/apps/sdnip/SdnIp.java
index 3b56468..745e27b 100644
--- a/src/main/java/net/onrc/onos/apps/sdnip/SdnIp.java
+++ b/src/main/java/net/onrc/onos/apps/sdnip/SdnIp.java
@@ -6,6 +6,7 @@
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
+import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
@@ -29,6 +30,7 @@
import net.onrc.onos.apps.proxyarp.IArpRequester;
import net.onrc.onos.apps.proxyarp.IProxyArpService;
import net.onrc.onos.apps.sdnip.RibUpdate.Operation;
+import net.onrc.onos.apps.sdnip.web.SdnIpWebRoutable;
import net.onrc.onos.apps.sdnip.web.SdnIpWebRoutableNew;
import net.onrc.onos.core.intent.IntentOperation;
import net.onrc.onos.core.intent.IntentOperationList;
@@ -55,6 +57,7 @@
import net.onrc.onos.core.util.PortNumber;
import net.onrc.onos.core.util.SwitchPort;
import net.sf.json.JSONArray;
+import net.sf.json.JSONException;
import net.sf.json.JSONObject;
import net.sf.json.JSONSerializer;
@@ -78,6 +81,10 @@
import com.google.common.collect.SetMultimap;
import com.google.common.net.InetAddresses;
import com.google.common.util.concurrent.ThreadFactoryBuilder;
+import com.googlecode.concurrenttrees.radix.RadixTree;
+import com.googlecode.concurrenttrees.radix.node.concrete.DefaultByteArrayNodeFactory;
+import com.googlecode.concurrenttrees.radixinverted.ConcurrentInvertedRadixTree;
+import com.googlecode.concurrenttrees.radixinverted.InvertedRadixTree;
public class SdnIp implements IFloodlightModule, ISdnIpService,
IArpRequester,
@@ -90,8 +97,9 @@
private IRestApiService restApi;
private IProxyArpService proxyArp;
- private IPatriciaTree<RibEntry> ptree;
- private IPatriciaTree<Interface> interfacePtree;
+ private InvertedRadixTree<RibEntry> bgpRoutes;
+ private InvertedRadixTree<Interface> interfaceRoutes;
+
private BlockingQueue<RibUpdate> ribUpdates;
private String bgpdRestIp;
@@ -236,8 +244,9 @@
// Populate the interface Patricia Tree
for (Interface intf : interfaces.values()) {
- Prefix prefix = new Prefix(intf.getIpAddress().getAddress(), intf.getPrefixLength());
- interfacePtree.put(prefix, intf);
+ Prefix prefix = new Prefix(intf.getIpAddress().getAddress(),
+ intf.getPrefixLength());
+ interfaceRoutes.put(prefix.toBinaryString(), intf);
}
}
@@ -274,8 +283,10 @@
public void init(FloodlightModuleContext context)
throws FloodlightModuleException {
- ptree = new PatriciaTree<RibEntry>(32);
- interfacePtree = new PatriciaTree<Interface>(32);
+ bgpRoutes = new ConcurrentInvertedRadixTree<>(
+ new DefaultByteArrayNodeFactory());
+ interfaceRoutes = new ConcurrentInvertedRadixTree<>(
+ new DefaultByteArrayNodeFactory());
ribUpdates = new LinkedBlockingQueue<RibUpdate>();
@@ -335,7 +346,7 @@
@Override
public void startUp(FloodlightModuleContext context) {
- //restApi.addRestletRoutable(new SdnIpWebRoutable());
+ restApi.addRestletRoutable(new SdnIpWebRoutable());
restApi.addRestletRoutable(new SdnIpWebRoutableNew());
floodlightProvider.addOFSwitchListener(this);
@@ -344,13 +355,13 @@
}
@Override
- public IPatriciaTree<RibEntry> getPtree() {
- return ptree;
+ public RadixTree<RibEntry> getPtree() {
+ return bgpRoutes;
}
@Override
public void clearPtree() {
- ptree = new PatriciaTree<RibEntry>(32);
+ log.warn("Clear table operation not supported");
}
@Override
@@ -371,43 +382,48 @@
return;
}
- response = response.replaceAll("\"", "'");
- JSONObject jsonObj = (JSONObject) JSONSerializer.toJSON(response);
- JSONArray ribArray = jsonObj.getJSONArray("rib");
- String inboundRouterId = jsonObj.getString("router-id");
+ try {
+ response = response.replaceAll("\"", "'");
+ JSONObject jsonObj = (JSONObject) JSONSerializer.toJSON(response);
+ JSONArray ribArray = jsonObj.getJSONArray("rib");
+ String inboundRouterId = jsonObj.getString("router-id");
- int size = ribArray.size();
+ int size = ribArray.size();
- log.info("Retrived RIB of {} entries from BGPd", size);
+ log.info("Retrived RIB of {} entries from BGPd", size);
- for (int j = 0; j < size; j++) {
- JSONObject ribEntry = ribArray.getJSONObject(j);
- String prefix = ribEntry.getString("prefix");
- String nexthop = ribEntry.getString("nexthop");
+ for (int j = 0; j < size; j++) {
+ JSONObject ribEntry = ribArray.getJSONObject(j);
+ String prefix = ribEntry.getString("prefix");
+ String nexthop = ribEntry.getString("nexthop");
- // Insert each rib entry into the local rib
- String[] substring = prefix.split("/");
- String prefix1 = substring[0];
- String mask1 = substring[1];
+ // Insert each rib entry into the local rib
+ String[] substring = prefix.split("/");
+ String prefix1 = substring[0];
+ String mask1 = substring[1];
- Prefix p;
- try {
- p = new Prefix(prefix1, Integer.parseInt(mask1));
- } catch (NumberFormatException e) {
- log.warn("Wrong mask format in RIB JSON: {}", mask1);
- continue;
- } catch (IllegalArgumentException e1) {
- log.warn("Wrong prefix format in RIB JSON: {}", prefix1);
- continue;
+ Prefix p;
+ try {
+ p = new Prefix(prefix1, Integer.parseInt(mask1));
+ } catch (NumberFormatException e) {
+ log.warn("Wrong mask format in RIB JSON: {}", mask1);
+ continue;
+ } catch (IllegalArgumentException e1) {
+ log.warn("Wrong prefix format in RIB JSON: {}", prefix1);
+ continue;
+ }
+
+ RibEntry rib = new RibEntry(inboundRouterId, nexthop);
+
+ try {
+ ribUpdates.put(new RibUpdate(Operation.UPDATE, p, rib));
+ } catch (InterruptedException e) {
+ log.debug("Interrupted while pushing onto update queue");
+ }
}
-
- RibEntry rib = new RibEntry(inboundRouterId, nexthop);
-
- try {
- ribUpdates.put(new RibUpdate(Operation.UPDATE, p, rib));
- } catch (InterruptedException e) {
- log.debug("Interrupted while pushing onto update queue");
- }
+ } catch (JSONException e) {
+ // TODO don't parse JSON manually
+ log.error("Error parsing inital route table JSON:", e);
}
}
@@ -427,7 +443,7 @@
log.debug("Processing prefix add {}", prefix);
- RibEntry rib = ptree.put(prefix, update.getRibEntry());
+ RibEntry rib = bgpRoutes.put(prefix.toBinaryString(), update.getRibEntry());
if (rib != null && !rib.equals(update.getRibEntry())) {
// There was an existing nexthop for this prefix. This update supersedes that,
@@ -611,7 +627,10 @@
synchronized (this) {
Prefix prefix = update.getPrefix();
- if (ptree.remove(prefix, update.getRibEntry())) {
+ //if (ptree.remove(prefix, update.getRibEntry())) {
+ // TODO check the change of logic here - remove doesn't check that the
+ // rib entry was what we expected (and we can't do this concurrently)
+ if (bgpRoutes.remove(prefix.toBinaryString())) {
/*
* Only delete flows if an entry was actually removed from the tree.
* If no entry was removed, the <prefix, nexthop> wasn't there so
@@ -868,8 +887,8 @@
srcPort.dpid().value(), srcPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, srcIP,
dstPort.dpid().value(), dstPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, dstIP);
ShortestPathIntent bwdIntent = new ShortestPathIntent(bwdIntentId,
- srcPort.dpid().value(), srcPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, dstIP,
- dstPort.dpid().value(), dstPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, srcIP);
+ dstPort.dpid().value(), dstPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, dstIP,
+ srcPort.dpid().value(), srcPort.port().value(), ShortestPathIntent.EMPTYMACADDRESS, srcIP);
IntentOperation.Operator operator = IntentOperation.Operator.ADD;
operations.add(operator, fwdIntent);
operations.add(operator, bwdIntent);
@@ -1118,7 +1137,8 @@
for (RibUpdate update : prefixesToPush) {
// These will always be adds
- RibEntry rib = ptree.lookup(update.getPrefix());
+ RibEntry rib = bgpRoutes.getValueForExactKey(
+ update.getPrefix().toBinaryString());
if (rib != null && rib.equals(update.getRibEntry())) {
log.debug("Pushing prefix {} next hop {}", update.getPrefix(),
rib.getNextHop().getHostAddress());
@@ -1352,7 +1372,8 @@
private boolean validateUpdate(RibUpdate update) {
RibEntry newEntry = update.getRibEntry();
- RibEntry oldEntry = ptree.lookup(update.getPrefix());
+ RibEntry oldEntry = bgpRoutes.getValueForExactKey(
+ update.getPrefix().toBinaryString());
//If there is no existing entry we must assume this is the most recent
//update. However this might not always be the case as we might have a
@@ -1376,6 +1397,21 @@
newEntry.getSequenceNum() > oldEntry.getSequenceNum();
}
+ private Interface longestInterfacePrefixMatch(InetAddress address) {
+ Prefix prefixToSearchFor = new Prefix(address.getAddress(),
+ Prefix.MAX_PREFIX_LENGTH);
+ Iterator<Interface> it =
+ interfaceRoutes.getValuesForKeysPrefixing(
+ prefixToSearchFor.toBinaryString()).iterator();
+ Interface intf = null;
+ // Find the last prefix, which will be the longest prefix
+ while (it.hasNext()) {
+ intf = it.next();
+ }
+
+ return intf;
+ }
+
// The code below should be reimplemented after removal of Floodlight's
// ITopologyService API. It should be implemented on top of network graph
// notifications. (It was pretty hacky anyway...)
@@ -1430,7 +1466,7 @@
@Override
public String getName() {
- return "SdnIp";
+ return "sdnip";
}
/*
@@ -1439,13 +1475,13 @@
@Override
public boolean isInterfaceAddress(InetAddress address) {
- Interface intf = interfacePtree.match(new Prefix(address.getAddress(), 32));
+ Interface intf = longestInterfacePrefixMatch(address);
return (intf != null && intf.getIpAddress().equals(address));
}
@Override
public boolean inConnectedNetwork(InetAddress address) {
- Interface intf = interfacePtree.match(new Prefix(address.getAddress(), 32));
+ Interface intf = longestInterfacePrefixMatch(address);
return (intf != null && !intf.getIpAddress().equals(address));
}
@@ -1461,7 +1497,7 @@
@Override
public Interface getOutgoingInterface(InetAddress dstIpAddress) {
- return interfacePtree.match(new Prefix(dstIpAddress.getAddress(), 32));
+ return longestInterfacePrefixMatch(dstIpAddress);
}
@Override
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");
diff --git a/src/main/java/net/onrc/onos/apps/sdnip/web/SdnIpWebRoutableNew.java b/src/main/java/net/onrc/onos/apps/sdnip/web/SdnIpWebRoutableNew.java
index 250b4da..5b6928a 100644
--- a/src/main/java/net/onrc/onos/apps/sdnip/web/SdnIpWebRoutableNew.java
+++ b/src/main/java/net/onrc/onos/apps/sdnip/web/SdnIpWebRoutableNew.java
@@ -21,6 +21,6 @@
@Override
public String basePath() {
- return "/wm/bgpNew";
+ return "/wm/sdnip";
}
}
diff --git a/src/test/java/net/onrc/onos/apps/sdnip/PrefixTest.java b/src/test/java/net/onrc/onos/apps/sdnip/PrefixTest.java
index cee6898..ae3b442 100644
--- a/src/test/java/net/onrc/onos/apps/sdnip/PrefixTest.java
+++ b/src/test/java/net/onrc/onos/apps/sdnip/PrefixTest.java
@@ -2,9 +2,12 @@
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;
import java.util.Arrays;
+import java.util.LinkedList;
+import java.util.List;
import org.junit.After;
import org.junit.Before;
@@ -12,8 +15,42 @@
public class PrefixTest {
+ private List<PrefixTestData> testPrefixes;
+
+ private class PrefixTestData {
+ public final String dotNotation;
+ public final String binaryNotation;
+ public final int prefixLength;
+
+ public PrefixTestData(String dotNotation, int prefixLength,
+ String binaryNotation) {
+ this.dotNotation = dotNotation;
+ this.prefixLength = prefixLength;
+ this.binaryNotation = binaryNotation;
+ }
+ }
+
@Before
public void setUp() throws Exception {
+
+ testPrefixes = new LinkedList<>();
+
+ testPrefixes.add(new PrefixTestData("0.0.0.0", 0, ""));
+
+ testPrefixes.add(new PrefixTestData("192.168.166.0", 22,
+ "1100000010101000101001"));
+
+ testPrefixes.add(new PrefixTestData("192.168.166.0", 23,
+ "11000000101010001010011"));
+
+ testPrefixes.add(new PrefixTestData("192.168.166.0", 24,
+ "110000001010100010100110"));
+
+ testPrefixes.add(new PrefixTestData("130.162.10.1", 25,
+ "1000001010100010000010100"));
+
+ testPrefixes.add(new PrefixTestData("255.255.255.255", 32,
+ "11111111111111111111111111111111"));
}
@After
@@ -21,7 +58,7 @@
}
@Test
- public void testPrefixByteArray() {
+ public void testNewPrefixFromByteArray() {
byte[] b1 = new byte[]{(byte) 0x8f, (byte) 0xa0, (byte) 0x00, (byte) 0x00};
byte[] b2 = new byte[]{(byte) 0x8f, (byte) 0xa0, (byte) 0xff, (byte) 0xff};
byte[] b3 = new byte[]{(byte) 0x8f, (byte) 0xac, (byte) 0x00, (byte) 0x00};
@@ -32,11 +69,11 @@
Prefix p3 = new Prefix(b3, 12);
Prefix p4 = new Prefix(b4, 11);
- //Have different byte arrays, but should be equal after construction
+ //Have different input byte arrays, but should be equal after construction
assertTrue(p1.equals(p2));
assertTrue(p2.equals(p3));
- //Same byte array, but should be false
+ //Same input byte array, but should be false
assertFalse(p1.equals(p4));
assertTrue(Arrays.equals(p1.getAddress(), p3.getAddress()));
@@ -65,14 +102,12 @@
assertEquals(p1.hashCode(), p3.hashCode());
}
- private static final int MAX_PREFIX_LENGTH = 32;
-
@Test
public void testPrefixReturnsSame() {
- //Create a prefix of all 1s for each prefix length.
+ //Create a prefix of all ones for each prefix length.
//Check that Prefix doesn't mangle it
- for (int prefixLength = 1; prefixLength <= MAX_PREFIX_LENGTH; prefixLength++) {
- byte[] address = new byte[MAX_PREFIX_LENGTH / Byte.SIZE];
+ for (int prefixLength = 1; prefixLength <= Prefix.MAX_PREFIX_LENGTH; prefixLength++) {
+ byte[] address = new byte[Prefix.ADDRESS_LENGTH_BYTES];
int lastByte = (prefixLength - 1) / Byte.SIZE;
int lastBit = (prefixLength - 1) % Byte.SIZE;
@@ -95,8 +130,65 @@
}
Prefix p = new Prefix(address, prefixLength);
- System.out.println(p.printAsBits());
+
assertTrue(Arrays.equals(address, p.getAddress()));
}
}
+
+ @Test
+ public void testToBinaryString() {
+ for (PrefixTestData testPrefix : testPrefixes) {
+ Prefix p = new Prefix(testPrefix.dotNotation, testPrefix.prefixLength);
+ assertEquals(testPrefix.binaryNotation, p.toBinaryString());
+ assertEquals(p.getPrefixLength(), p.toBinaryString().length());
+ }
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testStringConstructorPrefixLengthTooSmall() {
+ String s = "255.255.255.255";
+
+ // Check the first valid prefix length works
+ Prefix p = new Prefix(s, Prefix.MIN_PREFIX_LENGTH);
+ assertNotNull(p);
+
+ // Should throw IllegalArgumentException
+ new Prefix(s, Prefix.MIN_PREFIX_LENGTH - 1);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testStringConstructorPrefixLengthTooLarge() {
+ String s = "255.255.255.255";
+
+ // Check the last valid prefix length works
+ Prefix p = new Prefix(s, Prefix.MAX_PREFIX_LENGTH);
+ assertNotNull(p);
+
+ // Should throw IllegalArgumentException
+ new Prefix(s, Prefix.MAX_PREFIX_LENGTH + 1);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testByteConstructorPrefixLengthTooSmall() {
+ byte[] b = new byte[]{(byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff};
+
+ // Check the first valid prefix length works
+ Prefix p = new Prefix(b, Prefix.MIN_PREFIX_LENGTH);
+ assertNotNull(p);
+
+ // Should throw IllegalArgumentException
+ new Prefix(b, Prefix.MIN_PREFIX_LENGTH - 1);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testByteConstructorPrefixLengthTooLarge() {
+ byte[] b = new byte[]{(byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff};
+
+ // Check the last valid prefix length works
+ Prefix p = new Prefix(b, Prefix.MAX_PREFIX_LENGTH);
+ assertNotNull(p);
+
+ // Should throw IllegalArgumentException
+ new Prefix(b, Prefix.MAX_PREFIX_LENGTH + 1);
+ }
}