Jonathan Hart | 8f6dc09 | 2014-04-18 15:56:43 -0700 | [diff] [blame] | 1 | package net.onrc.onos.apps.sdnip; |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 2 | |
| 3 | import static org.junit.Assert.assertFalse; |
| 4 | import static org.junit.Assert.assertNotNull; |
| 5 | import static org.junit.Assert.assertNull; |
| 6 | import static org.junit.Assert.assertTrue; |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 7 | |
| 8 | import java.util.HashMap; |
| 9 | import java.util.Iterator; |
| 10 | import java.util.Map; |
| 11 | |
| 12 | import org.junit.After; |
| 13 | import org.junit.Before; |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 14 | import org.junit.Test; |
| 15 | |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 16 | public class PatriciaTreeTest { |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 17 | |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 18 | IPatriciaTree<RibEntry> ptree; |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 19 | Prefix[] prefixes; |
| 20 | Map<Prefix, RibEntry> mappings; |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 21 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 22 | @Before |
| 23 | public void setUp() throws Exception { |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 24 | ptree = new PatriciaTree<RibEntry>(32); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 25 | mappings = new HashMap<Prefix, RibEntry>(); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 26 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 27 | prefixes = new Prefix[]{ |
| 28 | new Prefix("192.168.10.0", 24), |
| 29 | new Prefix("192.168.8.0", 23), |
| 30 | new Prefix("192.168.8.0", 22), |
| 31 | new Prefix("192.0.0.0", 7), |
| 32 | new Prefix("192.168.11.0", 24), |
| 33 | new Prefix("10.0.23.128", 25), |
| 34 | new Prefix("206.17.144.0", 20), |
| 35 | new Prefix("9.17.0.0", 12), |
| 36 | new Prefix("192.168.0.0", 16) |
| 37 | }; |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 38 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 39 | for (int i = 0; i < prefixes.length; i++) { |
| 40 | mappings.put(prefixes[i], new RibEntry("192.168.10.101", "192.168.20." + i)); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 41 | ptree.put(prefixes[i], new RibEntry("192.168.10.101", "192.168.20." + i)); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 42 | } |
| 43 | } |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 44 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 45 | @After |
| 46 | public void tearDown() throws Exception { |
| 47 | } |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 48 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 49 | @Test |
| 50 | public void testPut() { |
Yuta HIGUCHI | 44a0b35 | 2014-05-14 21:32:48 -0700 | [diff] [blame] | 51 | ptree = new PatriciaTree<RibEntry>(32); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 52 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 53 | Prefix p1 = new Prefix("192.168.240.0", 20); |
| 54 | RibEntry r1 = new RibEntry("192.168.10.101", "192.168.60.2"); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 55 | RibEntry retval = ptree.put(p1, r1); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 56 | assertNull(retval); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 57 | retval = ptree.lookup(p1); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 58 | assertTrue(r1 == retval); //should be the same object |
| 59 | |
| 60 | Prefix p2 = new Prefix("192.160.0.0", 12); |
| 61 | RibEntry r2 = new RibEntry("192.168.10.101", "192.168.20.1"); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 62 | retval = ptree.put(p2, r2); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 63 | assertNull(retval); |
| 64 | |
| 65 | Prefix p3 = new Prefix("192.168.208.0", 20); |
| 66 | RibEntry r3 = new RibEntry("192.168.10.101", "192.168.30.1"); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 67 | retval = ptree.put(p3, r3); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 68 | assertNull(retval); |
| 69 | |
| 70 | //Insert a new RibEntry entry over a previous one |
| 71 | RibEntry r3new = new RibEntry("192.168.10.101", "192.168.60.2"); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 72 | retval = ptree.put(p3, r3new); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 73 | assertNotNull(retval); |
| 74 | assertTrue(retval.equals(r3)); |
| 75 | assertTrue(retval == r3); //should be the same object |
| 76 | |
| 77 | //Now we have an aggregate node with prefix 192.168.192.0/18. |
| 78 | //We will insert a RibEntry at this prefix |
| 79 | Prefix p4 = new Prefix("192.168.192.0", 18); |
| 80 | RibEntry r4 = new RibEntry("192.168.10.101", "192.168.40.1"); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 81 | retval = ptree.put(p4, r4); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 82 | assertNull(retval); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 83 | retval = ptree.lookup(p4); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 84 | assertTrue(retval == r4); //should be the same object |
| 85 | } |
| 86 | |
| 87 | @Test |
| 88 | public void testLookup() { |
| 89 | for (Map.Entry<Prefix, RibEntry> entry : mappings.entrySet()) { |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 90 | RibEntry r = ptree.lookup(entry.getKey()); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 91 | assertTrue(entry.getValue().equals(r)); |
| 92 | } |
| 93 | |
| 94 | //These are aggregate nodes in the tree. Shouldn't be returned by lookup |
| 95 | Prefix p1 = new Prefix("0.0.0.0", 0); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 96 | RibEntry retval = ptree.lookup(p1); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 97 | assertNull(retval); |
| 98 | |
| 99 | //We'll put a RibEntry at an aggregate node and check if lookup returns correctly |
| 100 | Prefix p2 = new Prefix("192.0.0.0", 4); |
| 101 | RibEntry r2 = new RibEntry("192.168.10.101", "192.168.60.1"); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 102 | retval = ptree.put(p2, r2); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 103 | assertNull(retval); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 104 | retval = ptree.lookup(p2); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 105 | assertTrue(retval.equals(r2)); |
| 106 | } |
| 107 | |
| 108 | //@Ignore |
| 109 | @Test |
| 110 | public void testMatch() { |
| 111 | Prefix p1 = new Prefix("192.168.10.30", 32); |
| 112 | Prefix p2 = new Prefix("192.168.10.30", 31); |
| 113 | Prefix p3 = new Prefix("192.168.8.241", 32); |
| 114 | Prefix p4 = new Prefix("1.0.0.0", 32); |
| 115 | Prefix p5 = new Prefix("192.168.8.0", 22); |
| 116 | Prefix p6 = new Prefix("192.168.8.0", 21); |
| 117 | |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 118 | assertTrue(ptree.match(p1).equals(mappings.get(prefixes[0]))); |
| 119 | assertTrue(ptree.match(p2).equals(mappings.get(prefixes[0]))); |
| 120 | assertTrue(ptree.match(p3).equals(mappings.get(prefixes[1]))); |
| 121 | assertNull(ptree.match(p4)); |
| 122 | assertTrue(ptree.match(p5).equals(mappings.get(prefixes[2]))); |
| 123 | //System.out.println(ptree.match(p6).getNextHop().getHostAddress()); |
| 124 | assertTrue(ptree.match(p6).equals(mappings.get(prefixes[8]))); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 125 | |
| 126 | |
| 127 | //TODO more extensive tests |
| 128 | //fail("Not yet implemented"); |
| 129 | } |
| 130 | |
| 131 | @Test |
| 132 | public void testRemove() { |
| 133 | Prefix p1 = new Prefix("192.168.8.0", 23); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 134 | RibEntry retval = ptree.lookup(p1); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 135 | assertNotNull(retval); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 136 | boolean success = ptree.remove(p1, retval); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 137 | assertTrue(success); |
| 138 | |
| 139 | Prefix p2 = new Prefix("192.168.8.0", 22); |
| 140 | Prefix p3 = new Prefix("192.168.10.0", 24); |
| 141 | |
| 142 | //Test it does the right thing with null arguments |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 143 | success = ptree.remove(null, null); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 144 | assertFalse(success); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 145 | success = ptree.remove(p2, null); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 146 | assertFalse(success); |
| 147 | |
| 148 | //Check other prefixes are still there |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 149 | retval = ptree.lookup(p2); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 150 | assertNotNull(retval); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 151 | retval = ptree.lookup(p3); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 152 | assertNotNull(retval); |
| 153 | |
| 154 | Prefix p4 = new Prefix("9.17.0.0", 12); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 155 | retval = ptree.lookup(p4); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 156 | assertNotNull(retval); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 157 | success = ptree.remove(p4, retval); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 158 | assertTrue(success); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 159 | success = ptree.remove(p4, retval); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 160 | assertFalse(success); |
| 161 | |
| 162 | //Check other prefixes are still there |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 163 | retval = ptree.lookup(p2); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 164 | assertNotNull(retval); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 165 | retval = ptree.lookup(p3); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 166 | assertNotNull(retval); |
| 167 | |
| 168 | Prefix p5 = new Prefix("192.0.0.0", 7); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 169 | retval = ptree.lookup(p5); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 170 | assertNotNull(retval); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 171 | success = ptree.remove(p5, retval); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 172 | assertTrue(success); |
| 173 | |
| 174 | //Check other prefixes are still there |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 175 | retval = ptree.lookup(p2); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 176 | assertNotNull(retval); |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 177 | retval = ptree.lookup(p3); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 178 | assertNotNull(retval); |
| 179 | |
| 180 | |
| 181 | } |
| 182 | |
| 183 | @Test(expected = java.util.NoSuchElementException.class) |
| 184 | public void testIterator() { |
| 185 | int[] order = new int[]{7, 5, 3, 8, 2, 1, 0, 4, 6}; |
| 186 | |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 187 | Iterator<IPatriciaTree.Entry<RibEntry>> it = ptree.iterator(); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 188 | int i = 0; |
| 189 | assertTrue(it.hasNext()); |
| 190 | while (it.hasNext()) { |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 191 | IPatriciaTree.Entry<RibEntry> entry = it.next(); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 192 | assertTrue(entry.getPrefix().equals(prefixes[order[i]])); |
| 193 | i++; |
| 194 | } |
| 195 | assertFalse(it.hasNext()); |
| 196 | assertTrue(i == order.length); |
| 197 | |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 198 | IPatriciaTree<RibEntry> pt = new PatriciaTree<RibEntry>(32); |
| 199 | Iterator<IPatriciaTree.Entry<RibEntry>> it2 = pt.iterator(); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 200 | assertFalse(it2.hasNext()); |
| 201 | it.next(); //throws NoSuchElementException |
| 202 | } |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 203 | |
| 204 | } |