mappingservice/inmemorydb/src/test/java/org/opendaylight/lispflowmapping/inmemorydb/radixtrie/RadixTrieTest.java

   1 /*
   2  * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8
   9 package org.opendaylight.lispflowmapping.inmemorydb.radixtrie;
  10
  11 import static org.junit.Assert.assertTrue;
  12
  13 import java.net.InetAddress;
  14 import java.net.UnknownHostException;
  15 import java.util.ArrayList;
  16 import java.util.Arrays;
  17 import java.util.Iterator;
  18 import org.junit.Assert;
  19 import org.junit.Before;
  20 import org.junit.Test;
  21 import org.slf4j.Logger;
  22 import org.slf4j.LoggerFactory;
  23
  24 public class RadixTrieTest {
  25     protected static final Logger LOG = LoggerFactory.getLogger(RadixTrieTest.class);
  26
  27     private static RadixTrie<Integer> radixTrie4;
  28     private static RadixTrie<Integer> radixTrie6;
  29
  30     private static byte[] IP4_DEFAULT;
  31     private static byte[] IP4_BYTES1;
  32     private static byte[] IP4_BYTES2;
  33     private static byte[] IP4_BYTES3;
  34     private static byte[] IP4_BYTES4;
  35     private static byte[] IP4_BYTES5;
  36     private static byte[] IP4_BYTES6;
  37     private static byte[] IP4_BYTES7;
  38     private static byte[] IP4_BYTES8;
  39     private static byte[] IP4_BYTES9;
  40     private static byte[] IP4_BYTES10;
  41     private static byte[] IP4_BYTES11;
  42     private static byte[] IP4_BYTES12;
  43     private static byte[] IP4_BYTES13;
  44     private static byte[] IP4_BYTES14;
  45     private static byte[] IP4_BYTES15;
  46     private static byte[] IP4_BYTES16;
  47     private static byte[] IP4_BYTES17;
  48     private static byte[] IP4_BYTES18;
  49     private static byte[] IP4_BYTES19;
  50     private static byte[] IP4_BYTES20;
  51     private static byte[] IP4_BYTES21;
  52
  53     ArrayList<byte []> itPrefixList4;
  54     ArrayList<Integer> itPreflenList4;
  55
  56     private static byte[] IP6_BYTES1;
  57     private static byte[] IP6_BYTES2;
  58     private static byte[] IP6_BYTES3;
  59     private static byte[] IP6_BYTES4;
  60     private static byte[] IP6_BYTES5;
  61     private static byte[] IP6_BYTES6;
  62     private static byte[] IP6_BYTES7;
  63
  64     @Before
  65     public void init() {
  66         try {
  67             IP4_DEFAULT = InetAddress.getByName("0.0.0.0").getAddress();
  68             IP4_BYTES1 = InetAddress.getByName("192.168.0.0").getAddress();
  69             IP4_BYTES2 = InetAddress.getByName("192.167.0.0").getAddress();
  70             IP4_BYTES3 = InetAddress.getByName("192.169.0.0").getAddress();
  71             IP4_BYTES4 = InetAddress.getByName("192.168.1.0").getAddress();
  72             IP4_BYTES5 = InetAddress.getByName("192.168.2.0").getAddress();
  73             IP4_BYTES6 = InetAddress.getByName("192.168.1.0").getAddress();
  74             IP4_BYTES7 = InetAddress.getByName("192.168.1.1").getAddress();
  75             IP4_BYTES8 = InetAddress.getByName("193.168.1.1").getAddress();
  76             IP4_BYTES9 = InetAddress.getByName("192.168.3.0").getAddress();
  77             IP4_BYTES10 = InetAddress.getByName("129.214.0.0").getAddress();
  78             IP4_BYTES11 = InetAddress.getByName("192.168.2.0").getAddress();
  79             IP4_BYTES12 = InetAddress.getByName("128.0.0.0").getAddress();
  80             IP4_BYTES13 = InetAddress.getByName("1.1.128.0").getAddress();
  81             IP4_BYTES14 = InetAddress.getByName("1.1.32.0").getAddress();
  82             IP4_BYTES15 = InetAddress.getByName("1.1.127.10").getAddress();
  83             IP4_BYTES16 = InetAddress.getByName("1.1.64.0").getAddress();
  84             IP4_BYTES17 = InetAddress.getByName("40.218.27.124").getAddress();
  85             IP4_BYTES18 = InetAddress.getByName("40.192.0.0").getAddress();
  86             IP4_BYTES19 = InetAddress.getByName("64.142.3.176").getAddress();
  87             IP4_BYTES20 = InetAddress.getByName("64.228.0.0").getAddress();
  88             IP4_BYTES21 = InetAddress.getByName("64.0.0.0").getAddress();
  89
  90             IP6_BYTES1 = InetAddress.getByName("192:168::0:0").getAddress();
  91             IP6_BYTES2 = InetAddress.getByName("192:167::0:0").getAddress();
  92             IP6_BYTES3 = InetAddress.getByName("192:169::0:0").getAddress();
  93             IP6_BYTES4 = InetAddress.getByName("192:168::1:0").getAddress();
  94             IP6_BYTES5 = InetAddress.getByName("192:168::2:0").getAddress();
  95             IP6_BYTES6 = InetAddress.getByName("192:168::1:0").getAddress();
  96             IP6_BYTES7 = InetAddress.getByName("192:168::1:1").getAddress();
  97
  98             itPrefixList4 = new ArrayList<>();
  99             itPrefixList4.add(IP4_BYTES2);
 100             itPrefixList4.add(IP4_BYTES7);
 101             itPrefixList4.add(IP4_BYTES4);
 102             itPrefixList4.add(IP4_BYTES4);
 103             itPrefixList4.add(IP4_BYTES5);
 104             itPrefixList4.add(IP4_BYTES1);
 105             itPrefixList4.add(IP4_BYTES3);
 106
 107             itPreflenList4 = new ArrayList<>();
 108             itPreflenList4.add(16);
 109             itPreflenList4.add(32);
 110             itPreflenList4.add(25);
 111             itPreflenList4.add(24);
 112             itPreflenList4.add(24);
 113             itPreflenList4.add(16);
 114             itPreflenList4.add(16);
 115
 116         } catch (UnknownHostException e) {
 117             LOG.error("Caught exception: ", e);
 118         }
 119     }
 120
 121     /**
 122      * Tests v4 CRD operations.
 123      */
 124     @Test
 125     public void testIp4() {
 126         RadixTrie<Integer>.TrieNode res;
 127         radixTrie4 = new RadixTrie<>(32);
 128         addIp4Addresses(radixTrie4);
 129
 130         res = radixTrie4.lookupBest(IP4_BYTES7, 32);
 131         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES7));
 132         assertTrue(res.prefixLength() == 32);
 133         assertTrue(res.data() == 7);
 134
 135         res = radixTrie4.lookupBest(IP4_BYTES5, 24);
 136         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES5));
 137         assertTrue(res.prefixLength() == 24);
 138         assertTrue(res.data() == 5);
 139
 140         radixTrie4.remove(IP4_BYTES5, 24);
 141         res = radixTrie4.lookupBest(IP4_BYTES5, 24);
 142         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES1));
 143         assertTrue(res.prefixLength() == 16);
 144         assertTrue(res.data() == 1);
 145
 146         radixTrie4.remove(IP4_BYTES4, 24);
 147         radixTrie4.remove(IP4_BYTES7, 32);
 148         res = radixTrie4.lookupBest(IP4_BYTES7, 32);
 149         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES6));
 150         assertTrue(res.prefixLength() == 25);
 151         assertTrue(res.data() == 6);
 152
 153         radixTrie4.removeAll();
 154         assertTrue(radixTrie4.getRoot() == null);
 155     }
 156
 157     /**
 158      * Tests v4 inserts that overlap on byte edge.
 159      */
 160     @Test
 161     public void testIp4ByteBoundary() {
 162         radixTrie4 = new RadixTrie<>(32);
 163
 164         radixTrie4.insert(IP4_BYTES13, 17, 1);
 165         radixTrie4.insert(IP4_BYTES14, 19, 1);
 166
 167         RadixTrie<Integer>.TrieNode res = radixTrie4.lookupWidestNegative(IP4_BYTES15, 32);
 168         assertTrue(Arrays.equals(res.prefix, IP4_BYTES16));
 169         assertTrue(res.prefixLength() == 18);
 170
 171         radixTrie4.removeAll();
 172     }
 173
 174     /**
 175      * Tests iterator.
 176      */
 177     @Test
 178     public void testIterator() {
 179         RadixTrie<Integer>.TrieNode res;
 180
 181         addIp4Addresses(radixTrie4);
 182
 183         radixTrie4.remove(IP4_BYTES5, 24);
 184         radixTrie4.remove(IP4_BYTES4, 24);
 185         radixTrie4.insert(IP4_BYTES5, 24, 1);
 186         radixTrie4.insert(IP4_BYTES6, 24, 1);
 187
 188         Iterator<RadixTrie<Integer>.TrieNode> it = radixTrie4.getRoot().iterator();
 189
 190         int iterator = 0;
 191         while (it.hasNext()) {
 192             res = it.next();
 193             assertTrue(Arrays.equals(res.prefix(), itPrefixList4.get(iterator)));
 194             assertTrue(res.prefixLength() == itPreflenList4.get(iterator));
 195             iterator++;
 196         }
 197     }
 198
 199     /**
 200      * Tests v4 CRD operations with 0/0 as root.
 201      */
 202     @Test
 203     public void testIp4ZeroRoot() {
 204         radixTrie4 = new RadixTrie<>(32, true);
 205
 206         RadixTrie<Integer>.TrieNode res;
 207
 208         addIp4Addresses(radixTrie4);
 209
 210         res = radixTrie4.lookupBest(IP4_BYTES7, 32);
 211         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES7));
 212         assertTrue(res.prefixLength() == 32);
 213
 214         res = radixTrie4.lookupBest(IP4_BYTES5, 24);
 215         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES5));
 216         assertTrue(res.prefixLength() == 24);
 217
 218         radixTrie4.remove(IP4_BYTES5, 24);
 219         res = radixTrie4.lookupBest(IP4_BYTES5, 24);
 220         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES1));
 221         assertTrue(res.prefixLength() == 16);
 222
 223         radixTrie4.remove(IP4_BYTES4, 24);
 224         radixTrie4.remove(IP4_BYTES7, 32);
 225         res = radixTrie4.lookupBest(IP4_BYTES7, 32);
 226         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES6));
 227         assertTrue(res.prefixLength() == 25);
 228
 229         res = radixTrie4.lookupBest(IP4_BYTES8, 32);
 230         assertTrue(res == null);
 231
 232         radixTrie4.insert(IP4_DEFAULT, 0, 0);
 233         res = radixTrie4.lookupBest(IP4_BYTES8, 32);
 234         assertTrue(Arrays.equals(res.prefix(), IP4_DEFAULT));
 235
 236         radixTrie4.removeAll();
 237         assertTrue(!Arrays.equals(radixTrie4.getRoot().prefix(), IP4_DEFAULT));
 238         assertTrue(radixTrie4.getRoot().bit == 0);
 239     }
 240
 241     /**
 242      * Tests v4 widest negative prefix.
 243      */
 244     @Test
 245     public void testIp4WidestNegativePrefix() {
 246         radixTrie4 = new RadixTrie<>(32, true);
 247
 248         addIp4Addresses(radixTrie4);
 249
 250         radixTrie4.remove(IP4_BYTES5, 24);
 251         radixTrie4.remove(IP4_BYTES4, 24);
 252
 253         RadixTrie<Integer>.TrieNode res = radixTrie4.lookupWidestNegative(IP4_BYTES9, 24);
 254         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES11));
 255         assertTrue(res.prefixLength() == 23);
 256         res = radixTrie4.lookupWidestNegative(IP4_BYTES10, 16);
 257         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES12));
 258         assertTrue(res.prefixLength() == 2);
 259     }
 260
 261     /**
 262      * Tests v6 CRD operations.
 263      * It just makes sure v6 prefix lengths don't generate problems. Therefore it's not as thorough as v4.
 264      */
 265     @Test
 266     public void testIp6() {
 267         RadixTrie<Integer>.TrieNode res;
 268         radixTrie6 = new RadixTrie<>(128);
 269
 270         addIp6Addresses(radixTrie6);
 271
 272         res = radixTrie6.lookupBest(IP6_BYTES7, 128);
 273         assertTrue(Arrays.equals(res.prefix(), IP6_BYTES4));
 274         assertTrue(res.prefixLength() == 113);
 275
 276         res = radixTrie6.lookupBest(IP6_BYTES5, 112);
 277         assertTrue(Arrays.equals(res.prefix(), IP6_BYTES5));
 278         assertTrue(res.prefixLength() == 112);
 279
 280         radixTrie6.remove(IP6_BYTES5, 112);
 281         res = radixTrie6.lookupBest(IP6_BYTES5, 112);
 282         assertTrue(Arrays.equals(res.prefix(), IP6_BYTES1));
 283         assertTrue(res.prefixLength() == 32);
 284
 285         radixTrie6.remove(IP6_BYTES4, 112);
 286         res = radixTrie6.lookupBest(IP6_BYTES7, 128);
 287         assertTrue(Arrays.equals(res.prefix(), IP6_BYTES6));
 288         assertTrue(res.prefixLength() == 113);
 289
 290         radixTrie6.removeAll();
 291         assertTrue(radixTrie6.getRoot() == null);
 292     }
 293
 294     /**
 295      * Tests that parent insertions are done correctly.
 296      */
 297     @Test
 298     public void testParentInsertion() {
 299         radixTrie4 = new RadixTrie<>(32);
 300
 301         radixTrie4.insert(IP4_BYTES17, 30, 1);
 302         radixTrie4.insert(IP4_BYTES18, 11, 2);
 303
 304         RadixTrie<Integer>.TrieNode res = radixTrie4.lookupBest(IP4_BYTES17, 30);
 305         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES17));
 306
 307         radixTrie4.insert(IP4_BYTES19, 28, 3);
 308         radixTrie4.insert(IP4_BYTES20, 14, 3);
 309         radixTrie4.insert(IP4_BYTES21, 8, 3);
 310
 311         res = radixTrie4.lookupBest(IP4_BYTES19, 28);
 312         assertTrue(Arrays.equals(res.prefix(), IP4_BYTES19));
 313     }
 314
 315     /**
 316      * Test {@link RadixTrie#removeAll}.
 317      */
 318     @Test
 319     public void testRemoveAll() {
 320         radixTrie4 = new RadixTrie<>(32, true);
 321         addIp4Addresses(radixTrie4);
 322
 323         radixTrie4.removeAll();
 324         Assert.assertEquals(0, radixTrie4.getSize());
 325     }
 326
 327     private void addIp4Addresses(RadixTrie<Integer> trie) {
 328         trie.insert(IP4_BYTES7, 32, 7);
 329         trie.insert(IP4_BYTES6, 25, 6);
 330         trie.insert(IP4_BYTES5, 24, 5);
 331         trie.insert(IP4_BYTES4, 24, 4);
 332         trie.insert(IP4_BYTES3, 16, 3);
 333         trie.insert(IP4_BYTES2, 16, 2);
 334         trie.insert(IP4_BYTES1, 16, 1);
 335     }
 336
 337     private void addIp6Addresses(RadixTrie<Integer> trie) {
 338         trie.insert(IP6_BYTES1, 32, 1);
 339         trie.insert(IP6_BYTES2, 32, 1);
 340         trie.insert(IP6_BYTES3, 8, 1);
 341         trie.insert(IP6_BYTES4, 112, 1);
 342         trie.insert(IP6_BYTES5, 112, 1);
 343         trie.insert(IP6_BYTES6, 113, 1);
 344     }
 345 }