third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/TestHashCollisions.java

   1 /*
   2  * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package org.opendaylight.yangtools.triemap;
  17
  18 import org.junit.Test;
  19
  20 public class TestHashCollisions {
  21     @Test
  22     public void testHashCollisions () {
  23         final TrieMap<Object, Object> bt = new TrieMap<> ();
  24
  25         insertStrings (bt);
  26         insertChars (bt);
  27         insertInts (bt);
  28         insertBytes (bt);
  29
  30         removeStrings (bt);
  31         removeChars (bt);
  32         removeInts (bt);
  33         removeBytes (bt);
  34
  35         insertStrings (bt);
  36         insertInts (bt);
  37         insertBytes (bt);
  38         insertChars (bt);
  39
  40         removeBytes (bt);
  41         removeStrings (bt);
  42         removeChars (bt);
  43         removeInts (bt);
  44
  45         insertStrings (bt);
  46         insertInts (bt);
  47         insertBytes (bt);
  48         insertChars (bt);
  49
  50         removeStrings (bt);
  51         removeChars (bt);
  52         removeInts (bt);
  53         removeBytes (bt);
  54
  55         insertStrings (bt);
  56         insertInts (bt);
  57         insertBytes (bt);
  58         insertChars (bt);
  59
  60         removeChars (bt);
  61         removeInts (bt);
  62         removeBytes (bt);
  63         removeStrings (bt);
  64
  65         insertStrings (bt);
  66         insertInts (bt);
  67         insertBytes (bt);
  68         insertChars (bt);
  69
  70         removeInts (bt);
  71         removeBytes (bt);
  72         removeStrings (bt);
  73         removeChars (bt);
  74
  75         System.out.println (bt);
  76     }
  77
  78     private static void insertChars (final TrieMap<Object, Object> bt) {
  79         TestHelper.assertEquals (null, bt.put ('a', 'a'));
  80         TestHelper.assertEquals (null, bt.put ('b', 'b'));
  81         TestHelper.assertEquals (null, bt.put ('c', 'c'));
  82         TestHelper.assertEquals (null, bt.put ('d', 'd'));
  83         TestHelper.assertEquals (null, bt.put ('e', 'e'));
  84
  85         TestHelper.assertEquals ('a', bt.put ('a', 'a'));
  86         TestHelper.assertEquals ('b', bt.put ('b', 'b'));
  87         TestHelper.assertEquals ('c', bt.put ('c', 'c'));
  88         TestHelper.assertEquals ('d', bt.put ('d', 'd'));
  89         TestHelper.assertEquals ('e', bt.put ('e', 'e'));
  90     }
  91
  92     private static void insertStrings (final TrieMap<Object, Object> bt) {
  93         TestHelper.assertEquals (null, bt.put ("a", "a"));
  94         TestHelper.assertEquals (null, bt.put ("b", "b"));
  95         TestHelper.assertEquals (null, bt.put ("c", "c"));
  96         TestHelper.assertEquals (null, bt.put ("d", "d"));
  97         TestHelper.assertEquals (null, bt.put ("e", "e"));
  98
  99         TestHelper.assertEquals ("a", bt.put ("a", "a"));
 100         TestHelper.assertEquals ("b", bt.put ("b", "b"));
 101         TestHelper.assertEquals ("c", bt.put ("c", "c"));
 102         TestHelper.assertEquals ("d", bt.put ("d", "d"));
 103         TestHelper.assertEquals ("e", bt.put ("e", "e"));
 104     }
 105
 106     private static void insertBytes (final TrieMap<Object, Object> bt) {
 107         for (byte i = 0; i < 128 && i >= 0; i++) {
 108             final Byte bigB = Byte.valueOf (i);
 109             TestHelper.assertEquals (null, bt.put (bigB, bigB));
 110             TestHelper.assertEquals (bigB, bt.put (bigB, bigB));
 111         }
 112     }
 113
 114     private static void insertInts (final TrieMap<Object, Object> bt) {
 115         for (int i = 0; i < 128; i++) {
 116             final Integer bigI = Integer.valueOf (i);
 117             TestHelper.assertEquals (null, bt.put (bigI, bigI));
 118             TestHelper.assertEquals (bigI, bt.put (bigI, bigI));
 119         }
 120     }
 121
 122     private static void removeChars (final TrieMap<Object, Object> bt) {
 123         TestHelper.assertTrue (null != bt.lookup ('a'));
 124         TestHelper.assertTrue (null != bt.lookup ('b'));
 125         TestHelper.assertTrue (null != bt.lookup ('c'));
 126         TestHelper.assertTrue (null != bt.lookup ('d'));
 127         TestHelper.assertTrue (null != bt.lookup ('e'));
 128
 129         TestHelper.assertTrue (null != bt.remove ('a'));
 130         TestHelper.assertTrue (null != bt.remove ('b'));
 131         TestHelper.assertTrue (null != bt.remove ('c'));
 132         TestHelper.assertTrue (null != bt.remove ('d'));
 133         TestHelper.assertTrue (null != bt.remove ('e'));
 134
 135         TestHelper.assertFalse (null != bt.remove ('a'));
 136         TestHelper.assertFalse (null != bt.remove ('b'));
 137         TestHelper.assertFalse (null != bt.remove ('c'));
 138         TestHelper.assertFalse (null != bt.remove ('d'));
 139         TestHelper.assertFalse (null != bt.remove ('e'));
 140
 141         TestHelper.assertTrue (null == bt.lookup ('a'));
 142         TestHelper.assertTrue (null == bt.lookup ('b'));
 143         TestHelper.assertTrue (null == bt.lookup ('c'));
 144         TestHelper.assertTrue (null == bt.lookup ('d'));
 145         TestHelper.assertTrue (null == bt.lookup ('e'));
 146     }
 147
 148     private static void removeStrings (final TrieMap<Object, Object> bt) {
 149         TestHelper.assertTrue (null != bt.lookup ("a"));
 150         TestHelper.assertTrue (null != bt.lookup ("b"));
 151         TestHelper.assertTrue (null != bt.lookup ("c"));
 152         TestHelper.assertTrue (null != bt.lookup ("d"));
 153         TestHelper.assertTrue (null != bt.lookup ("e"));
 154
 155         TestHelper.assertTrue (null != bt.remove ("a"));
 156         TestHelper.assertTrue (null != bt.remove ("b"));
 157         TestHelper.assertTrue (null != bt.remove ("c"));
 158         TestHelper.assertTrue (null != bt.remove ("d"));
 159         TestHelper.assertTrue (null != bt.remove ("e"));
 160
 161         TestHelper.assertFalse (null != bt.remove ("a"));
 162         TestHelper.assertFalse (null != bt.remove ("b"));
 163         TestHelper.assertFalse (null != bt.remove ("c"));
 164         TestHelper.assertFalse (null != bt.remove ("d"));
 165         TestHelper.assertFalse (null != bt.remove ("e"));
 166
 167         TestHelper.assertTrue (null == bt.lookup ("a"));
 168         TestHelper.assertTrue (null == bt.lookup ("b"));
 169         TestHelper.assertTrue (null == bt.lookup ("c"));
 170         TestHelper.assertTrue (null == bt.lookup ("d"));
 171         TestHelper.assertTrue (null == bt.lookup ("e"));
 172     }
 173
 174     private static void removeInts (final TrieMap<Object, Object> bt) {
 175         for (int i = 0; i < 128; i++) {
 176             final Integer bigI = Integer.valueOf (i);
 177             TestHelper.assertTrue (null != bt.lookup (bigI));
 178             TestHelper.assertTrue (null != bt.remove (bigI));
 179             TestHelper.assertFalse (null != bt.remove (bigI));
 180             TestHelper.assertTrue (null == bt.lookup (bigI));
 181         }
 182     }
 183
 184     private static void removeBytes (final TrieMap<Object, Object> bt) {
 185         for (byte i = 0; i < 128 && i >= 0; i++) {
 186             final Byte bigB = Byte.valueOf (i);
 187             TestHelper.assertTrue (null != bt.lookup (bigB));
 188             TestHelper.assertTrue (null != bt.remove (bigB));
 189             TestHelper.assertFalse (null != bt.remove (bigB));
 190             TestHelper.assertTrue (null == bt.lookup (bigB));
 191         }
 192     }
 193 }