Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 1 | package net.onrc.onos.ofcontroller.bgproute; |
| 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 | |
| 16 | public class PatriciaTrieTest { |
| 17 | |
Jonathan Hart | 29b972d | 2013-08-12 23:43:51 +1200 | [diff] [blame] | 18 | IPatriciaTrie<RibEntry> ptrie; |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 19 | Prefix[] prefixes; |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 20 | Map<Prefix, RibEntry> mappings; |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 21 | |
| 22 | @Before |
| 23 | public void setUp() throws Exception { |
Jonathan Hart | 29b972d | 2013-08-12 23:43:51 +1200 | [diff] [blame] | 24 | ptrie = new PatriciaTrie<RibEntry>(32); |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 25 | mappings = new HashMap<Prefix, RibEntry>(); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 26 | |
| 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 | }; |
| 38 | |
| 39 | for (int i = 0; i < prefixes.length; i++) { |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 40 | mappings.put(prefixes[i], new RibEntry("192.168.10.101", "192.168.20." + i)); |
| 41 | ptrie.put(prefixes[i], new RibEntry("192.168.10.101", "192.168.20." + i)); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 42 | } |
| 43 | } |
| 44 | |
| 45 | @After |
| 46 | public void tearDown() throws Exception { |
| 47 | } |
| 48 | |
| 49 | @Test |
| 50 | public void testPut() { |
Jonathan Hart | 29b972d | 2013-08-12 23:43:51 +1200 | [diff] [blame] | 51 | IPatriciaTrie<RibEntry> ptrie = new PatriciaTrie<RibEntry>(32); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 52 | |
| 53 | Prefix p1 = new Prefix("192.168.240.0", 20); |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 54 | RibEntry r1 = new RibEntry("192.168.10.101", "192.168.60.2"); |
| 55 | RibEntry retval = ptrie.put(p1, r1); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 56 | assertNull(retval); |
| 57 | retval = ptrie.lookup(p1); |
| 58 | assertTrue(r1 == retval); //should be the same object |
| 59 | |
| 60 | Prefix p2 = new Prefix("192.160.0.0", 12); |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 61 | RibEntry r2 = new RibEntry("192.168.10.101", "192.168.20.1"); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 62 | retval = ptrie.put(p2, r2); |
| 63 | assertNull(retval); |
| 64 | |
| 65 | Prefix p3 = new Prefix("192.168.208.0", 20); |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 66 | RibEntry r3 = new RibEntry("192.168.10.101", "192.168.30.1"); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 67 | retval = ptrie.put(p3, r3); |
| 68 | assertNull(retval); |
| 69 | |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 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 | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 72 | retval = ptrie.put(p3, r3new); |
| 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. |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 78 | //We will insert a RibEntry at this prefix |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 79 | Prefix p4 = new Prefix("192.168.192.0", 18); |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 80 | RibEntry r4 = new RibEntry("192.168.10.101", "192.168.40.1"); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 81 | retval = ptrie.put(p4, r4); |
| 82 | assertNull(retval); |
| 83 | retval = ptrie.lookup(p4); |
| 84 | assertTrue(retval == r4); //should be the same object |
| 85 | } |
| 86 | |
| 87 | @Test |
| 88 | public void testLookup() { |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 89 | for (Map.Entry<Prefix, RibEntry> entry : mappings.entrySet()) { |
| 90 | RibEntry r = ptrie.lookup(entry.getKey()); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [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 | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 96 | RibEntry retval = ptrie.lookup(p1); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 97 | assertNull(retval); |
| 98 | |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 99 | //We'll put a RibEntry at an aggregate node and check if lookup returns correctly |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 100 | Prefix p2 = new Prefix("192.0.0.0", 4); |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 101 | RibEntry r2 = new RibEntry("192.168.10.101", "192.168.60.1"); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 102 | retval = ptrie.put(p2, r2); |
| 103 | assertNull(retval); |
| 104 | retval = ptrie.lookup(p2); |
| 105 | assertTrue(retval.equals(r2)); |
| 106 | } |
| 107 | |
Jonathan Hart | abf1022 | 2013-08-13 10:19:34 +1200 | [diff] [blame] | 108 | //@Ignore |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 109 | @Test |
| 110 | public void testMatch() { |
Jonathan Hart | abf1022 | 2013-08-13 10:19:34 +1200 | [diff] [blame] | 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 | |
| 118 | assertTrue(ptrie.match(p1).equals(mappings.get(prefixes[0]))); |
| 119 | assertTrue(ptrie.match(p2).equals(mappings.get(prefixes[0]))); |
| 120 | assertTrue(ptrie.match(p3).equals(mappings.get(prefixes[1]))); |
| 121 | assertNull(ptrie.match(p4)); |
| 122 | assertTrue(ptrie.match(p5).equals(mappings.get(prefixes[2]))); |
| 123 | //System.out.println(ptrie.match(p6).getNextHop().getHostAddress()); |
| 124 | assertTrue(ptrie.match(p6).equals(mappings.get(prefixes[8]))); |
| 125 | |
| 126 | |
| 127 | //TODO more extensive tests |
| 128 | //fail("Not yet implemented"); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 129 | } |
| 130 | |
| 131 | @Test |
| 132 | public void testRemove() { |
| 133 | Prefix p1 = new Prefix("192.168.8.0", 23); |
Jonathan Hart | b39a67d | 2013-08-10 23:59:50 +1200 | [diff] [blame] | 134 | RibEntry retval = ptrie.lookup(p1); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 135 | assertNotNull(retval); |
| 136 | boolean success = ptrie.remove(p1, retval); |
| 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 |
| 143 | success = ptrie.remove(null, null); |
| 144 | assertFalse(success); |
| 145 | success = ptrie.remove(p2, null); |
| 146 | assertFalse(success); |
| 147 | |
| 148 | //Check other prefixes are still there |
| 149 | retval = ptrie.lookup(p2); |
| 150 | assertNotNull(retval); |
| 151 | retval = ptrie.lookup(p3); |
| 152 | assertNotNull(retval); |
| 153 | |
| 154 | Prefix p4 = new Prefix("9.17.0.0", 12); |
| 155 | retval = ptrie.lookup(p4); |
| 156 | assertNotNull(retval); |
| 157 | success = ptrie.remove(p4, retval); |
| 158 | assertTrue(success); |
| 159 | success = ptrie.remove(p4, retval); |
| 160 | assertFalse(success); |
| 161 | |
| 162 | //Check other prefixes are still there |
| 163 | retval = ptrie.lookup(p2); |
| 164 | assertNotNull(retval); |
| 165 | retval = ptrie.lookup(p3); |
| 166 | assertNotNull(retval); |
| 167 | |
| 168 | Prefix p5 = new Prefix("192.0.0.0", 7); |
| 169 | retval = ptrie.lookup(p5); |
| 170 | assertNotNull(retval); |
| 171 | success = ptrie.remove(p5, retval); |
| 172 | assertTrue(success); |
| 173 | |
| 174 | //Check other prefixes are still there |
| 175 | retval = ptrie.lookup(p2); |
| 176 | assertNotNull(retval); |
| 177 | retval = ptrie.lookup(p3); |
| 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 | 29b972d | 2013-08-12 23:43:51 +1200 | [diff] [blame] | 187 | Iterator<IPatriciaTrie.Entry<RibEntry>> it = ptrie.iterator(); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 188 | int i = 0; |
| 189 | assertTrue(it.hasNext()); |
| 190 | while (it.hasNext()) { |
Jonathan Hart | 29b972d | 2013-08-12 23:43:51 +1200 | [diff] [blame] | 191 | IPatriciaTrie.Entry<RibEntry> entry = it.next(); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [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 | 29b972d | 2013-08-12 23:43:51 +1200 | [diff] [blame] | 198 | IPatriciaTrie<RibEntry> pt = new PatriciaTrie<RibEntry>(32); |
| 199 | Iterator<IPatriciaTrie.Entry<RibEntry>> it2 = pt.iterator(); |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 200 | assertFalse(it2.hasNext()); |
| 201 | it.next(); //throws NoSuchElementException |
| 202 | } |
| 203 | |
| 204 | } |