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 static org.junit.Assert.assertEquals;
  19 import static org.junit.Assert.assertNotNull;
  20 import static org.junit.Assert.assertNull;
  21
  22 import org.junit.Test;
  23
  24 public class TestHashCollisions {
  25     @Test
  26     public void testHashCollisions () {
  27         final TrieMap<Object, Object> bt = new TrieMap<>();
  28
  29         insertStrings(bt);
  30         insertChars(bt);
  31         insertInts(bt);
  32         insertBytes(bt);
  33
  34         removeStrings(bt);
  35         removeChars(bt);
  36         removeInts(bt);
  37         removeBytes(bt);
  38
  39         insertStrings(bt);
  40         insertInts(bt);
  41         insertBytes(bt);
  42         insertChars(bt);
  43
  44         removeBytes(bt);
  45         removeStrings(bt);
  46         removeChars(bt);
  47         removeInts(bt);
  48
  49         insertStrings(bt);
  50         insertInts(bt);
  51         insertBytes(bt);
  52         insertChars(bt);
  53
  54         removeStrings(bt);
  55         removeChars(bt);
  56         removeInts(bt);
  57         removeBytes(bt);
  58
  59         insertStrings(bt);
  60         insertInts(bt);
  61         insertBytes(bt);
  62         insertChars(bt);
  63
  64         removeChars(bt);
  65         removeInts(bt);
  66         removeBytes(bt);
  67         removeStrings(bt);
  68
  69         insertStrings(bt);
  70         insertInts(bt);
  71         insertBytes(bt);
  72         insertChars(bt);
  73
  74         removeInts(bt);
  75         removeBytes(bt);
  76         removeStrings(bt);
  77         removeChars(bt);
  78     }
  79
  80     private static void insertChars (final TrieMap<Object, Object> bt) {
  81         assertNull(bt.put('a', 'a'));
  82         assertNull(bt.put('b', 'b'));
  83         assertNull(bt.put('c', 'c'));
  84         assertNull(bt.put('d', 'd'));
  85         assertNull(bt.put('e', 'e'));
  86
  87         assertEquals('a', bt.put('a', 'a'));
  88         assertEquals('b', bt.put('b', 'b'));
  89         assertEquals('c', bt.put('c', 'c'));
  90         assertEquals('d', bt.put('d', 'd'));
  91         assertEquals('e', bt.put('e', 'e'));
  92     }
  93
  94     private static void insertStrings (final TrieMap<Object, Object> bt) {
  95         assertNull(bt.put("a", "a"));
  96         assertNull(bt.put("b", "b"));
  97         assertNull(bt.put("c", "c"));
  98         assertNull(bt.put("d", "d"));
  99         assertNull(bt.put("e", "e"));
 100
 101         assertEquals("a", bt.put("a", "a"));
 102         assertEquals("b", bt.put("b", "b"));
 103         assertEquals("c", bt.put("c", "c"));
 104         assertEquals("d", bt.put("d", "d"));
 105         assertEquals("e", bt.put("e", "e"));
 106     }
 107
 108     private static void insertBytes (final TrieMap<Object, Object> bt) {
 109         for (byte i = 0; i < 128 && i >= 0; i++) {
 110             final Byte bigB = Byte.valueOf(i);
 111             assertNull(bt.put(bigB, bigB));
 112             assertEquals(bigB, bt.put(bigB, bigB));
 113         }
 114     }
 115
 116     private static void insertInts (final TrieMap<Object, Object> bt) {
 117         for (int i = 0; i < 128; i++) {
 118             final Integer bigI = Integer.valueOf(i);
 119             assertNull(bt.put(bigI, bigI));
 120             assertEquals(bigI, bt.put(bigI, bigI));
 121         }
 122     }
 123
 124     private static void removeChars (final TrieMap<Object, Object> bt) {
 125         assertNotNull(bt.get('a'));
 126         assertNotNull(bt.get('b'));
 127         assertNotNull(bt.get('c'));
 128         assertNotNull(bt.get('d'));
 129         assertNotNull(bt.get('e'));
 130
 131         assertNotNull(bt.remove('a'));
 132         assertNotNull(bt.remove('b'));
 133         assertNotNull(bt.remove('c'));
 134         assertNotNull(bt.remove('d'));
 135         assertNotNull(bt.remove('e'));
 136
 137         assertNull(bt.remove('a'));
 138         assertNull(bt.remove('b'));
 139         assertNull(bt.remove('c'));
 140         assertNull(bt.remove('d'));
 141         assertNull(bt.remove('e'));
 142
 143         assertNull(bt.get('a'));
 144         assertNull(bt.get('b'));
 145         assertNull(bt.get('c'));
 146         assertNull(bt.get('d'));
 147         assertNull(bt.get('e'));
 148     }
 149
 150     private static void removeStrings (final TrieMap<Object, Object> bt) {
 151         assertNotNull(bt.get("a"));
 152         assertNotNull(bt.get("b"));
 153         assertNotNull(bt.get("c"));
 154         assertNotNull(bt.get("d"));
 155         assertNotNull(bt.get("e"));
 156
 157         assertNotNull(bt.remove("a"));
 158         assertNotNull(bt.remove("b"));
 159         assertNotNull(bt.remove("c"));
 160         assertNotNull(bt.remove("d"));
 161         assertNotNull(bt.remove("e"));
 162
 163         assertNull(bt.remove("a"));
 164         assertNull(bt.remove("b"));
 165         assertNull(bt.remove("c"));
 166         assertNull(bt.remove("d"));
 167         assertNull(bt.remove("e"));
 168
 169         assertNull(bt.get("a"));
 170         assertNull(bt.get("b"));
 171         assertNull(bt.get("c"));
 172         assertNull(bt.get("d"));
 173         assertNull(bt.get("e"));
 174     }
 175
 176     private static void removeInts (final TrieMap<Object, Object> bt) {
 177         for (int i = 0; i < 128; i++) {
 178             final Integer bigI = Integer.valueOf(i);
 179             assertNotNull(bt.get(bigI));
 180             assertNotNull(bt.remove(bigI));
 181             assertNull(bt.remove(bigI));
 182             assertNull(bt.get(bigI));
 183         }
 184     }
 185
 186     private static void removeBytes (final TrieMap<Object, Object> bt) {
 187         for (byte i = 0; i < 128 && i >= 0; i++) {
 188             final Byte bigB = Byte.valueOf(i);
 189             assertNotNull(bt.get(bigB));
 190             assertNotNull(bt.remove(bigB));
 191             assertNull(bt.remove(bigB));
 192             assertNull(bt.get(bigB));
 193         }
 194     }
 195 }