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