1 /** 2 * Licensed to the Apache Software Foundation (ASF) under one 3 * or more contributor license agreements. See the NOTICE file 4 * distributed with this work for additional information 5 * regarding copyright ownership. The ASF licenses this file 6 * to you under the Apache License, Version 2.0 (the 7 * "License"); you may not use this file except in compliance 8 * with the License. You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 19 package org.apache.hadoop.hbase.types; 20 21 import org.apache.hadoop.hbase.testclassification.SmallTests; 22 import org.junit.Before; 23 import org.junit.Test; 24 import org.junit.experimental.categories.Category; 25 26 import java.util.Map; 27 import java.util.concurrent.ConcurrentNavigableMap; 28 import java.util.concurrent.ConcurrentSkipListMap; 29 import java.util.concurrent.ThreadLocalRandom; 30 31 import static org.junit.Assert.*; 32 33 @Category(SmallTests.class) 34 public class TestCopyOnWriteMaps { 35 36 private static final int MAX_RAND = 10 * 1000 * 1000; 37 private ConcurrentNavigableMap<Long, Long> m; 38 private ConcurrentSkipListMap<Long, Long> csm; 39 40 @Before setUp()41 public void setUp() { 42 m = new CopyOnWriteArrayMap<>(); 43 csm = new ConcurrentSkipListMap<>(); 44 45 for ( long i = 0 ; i < 10000; i++ ) { 46 long o = ThreadLocalRandom.current().nextLong(MAX_RAND); 47 m.put(i, o); 48 csm.put(i,o); 49 } 50 long o = ThreadLocalRandom.current().nextLong(MAX_RAND); 51 m.put(0L, o); 52 csm.put(0L,o); 53 } 54 55 @Test testSize()56 public void testSize() throws Exception { 57 assertEquals("Size should always be equal", m.size(), csm.size()); 58 } 59 60 @Test testIsEmpty()61 public void testIsEmpty() throws Exception { 62 m.clear(); 63 assertTrue(m.isEmpty()); 64 m.put(100L, 100L); 65 assertFalse(m.isEmpty()); 66 m.remove(100L); 67 assertTrue(m.isEmpty()); 68 } 69 70 @Test testFindOnEmpty()71 public void testFindOnEmpty() throws Exception { 72 m.clear(); 73 assertTrue(m.isEmpty()); 74 assertNull(m.get(100L)); 75 assertFalse(m.containsKey(100L)); 76 assertEquals(0, m.tailMap(100L).entrySet().size()); 77 } 78 79 80 @Test testLowerKey()81 public void testLowerKey() throws Exception { 82 83 assertEquals(csm.lowerKey(400L), m.lowerKey(400L)); 84 assertEquals(csm.lowerKey(-1L), m.lowerKey(-1L)); 85 86 for ( int i =0 ; i < 100; i ++) { 87 Long key = ThreadLocalRandom.current().nextLong(); 88 assertEquals(csm.lowerKey(key), m.lowerKey(key)); 89 } 90 } 91 92 @Test testFloorEntry()93 public void testFloorEntry() throws Exception { 94 for ( int i =0 ; i < 100; i ++) { 95 Long key = ThreadLocalRandom.current().nextLong(); 96 assertEquals(csm.floorEntry(key), m.floorEntry(key)); 97 } 98 } 99 100 @Test testFloorKey()101 public void testFloorKey() throws Exception { 102 for ( int i =0 ; i < 100; i ++) { 103 Long key = ThreadLocalRandom.current().nextLong(); 104 assertEquals(csm.floorKey(key), m.floorKey(key)); 105 } 106 } 107 108 @Test testCeilingKey()109 public void testCeilingKey() throws Exception { 110 111 assertEquals(csm.ceilingKey(4000L), m.ceilingKey(4000L)); 112 assertEquals(csm.ceilingKey(400L), m.ceilingKey(400L)); 113 assertEquals(csm.ceilingKey(-1L), m.ceilingKey(-1L)); 114 115 for ( int i =0 ; i < 100; i ++) { 116 Long key = ThreadLocalRandom.current().nextLong(); 117 assertEquals(csm.ceilingKey(key), m.ceilingKey(key)); 118 } 119 } 120 121 @Test testHigherKey()122 public void testHigherKey() throws Exception { 123 124 assertEquals(csm.higherKey(4000L), m.higherKey(4000L)); 125 assertEquals(csm.higherKey(400L), m.higherKey(400L)); 126 assertEquals(csm.higherKey(-1L), m.higherKey(-1L)); 127 128 for ( int i =0 ; i < 100; i ++) { 129 Long key = ThreadLocalRandom.current().nextLong(); 130 assertEquals(csm.higherKey(key), m.higherKey(key)); 131 } 132 } 133 134 @Test testRemove()135 public void testRemove() throws Exception { 136 for (Map.Entry<Long, Long> e:csm.entrySet()) { 137 assertEquals(csm.remove(e.getKey()), m.remove(e.getKey())); 138 assertEquals(null, m.remove(e.getKey())); 139 } 140 } 141 142 @Test testReplace()143 public void testReplace() throws Exception { 144 for (Map.Entry<Long, Long> e:csm.entrySet()) { 145 Long newValue = ThreadLocalRandom.current().nextLong(); 146 assertEquals(csm.replace(e.getKey(), newValue), m.replace(e.getKey(), newValue)); 147 } 148 assertEquals(null, m.replace(MAX_RAND + 100L, ThreadLocalRandom.current().nextLong())); 149 } 150 151 @Test testReplace1()152 public void testReplace1() throws Exception { 153 for (Map.Entry<Long, Long> e: csm.entrySet()) { 154 Long newValue = ThreadLocalRandom.current().nextLong(); 155 assertEquals(csm.replace(e.getKey(), e.getValue() + 1, newValue), 156 m.replace(e.getKey(), e.getValue() + 1, newValue)); 157 assertEquals(csm.replace(e.getKey(), e.getValue(), newValue), 158 m.replace(e.getKey(), e.getValue(), newValue)); 159 assertEquals(newValue, m.get(e.getKey())); 160 assertEquals(csm.get(e.getKey()), m.get(e.getKey())); 161 } 162 assertEquals(null, m.replace(MAX_RAND + 100L, ThreadLocalRandom.current().nextLong())); 163 } 164 165 @Test testMultiAdd()166 public void testMultiAdd() throws InterruptedException { 167 168 Thread[] threads = new Thread[10]; 169 for ( int i =0 ; i<threads.length; i++) { 170 threads[i] = new Thread(new Runnable() { 171 @Override 172 public void run() { 173 for ( int j = 0; j < 5000; j++) { 174 m.put(ThreadLocalRandom.current().nextLong(), 175 ThreadLocalRandom.current().nextLong()); 176 } 177 } 178 }); 179 } 180 181 for (Thread thread1 : threads) { 182 thread1.start(); 183 } 184 185 for (Thread thread2 : threads) { 186 thread2.join(); 187 } 188 } 189 190 @Test testFirstKey()191 public void testFirstKey() throws Exception { 192 assertEquals(csm.firstKey(), m.firstKey()); 193 } 194 195 @Test testLastKey()196 public void testLastKey() throws Exception { 197 assertEquals(csm.lastKey(), m.lastKey()); 198 } 199 200 @Test testFirstEntry()201 public void testFirstEntry() throws Exception { 202 assertEquals(csm.firstEntry().getKey(), m.firstEntry().getKey()); 203 assertEquals(csm.firstEntry().getValue(), m.firstEntry().getValue()); 204 assertEquals(csm.firstEntry(), m.firstEntry()); 205 } 206 207 @Test testLastEntry()208 public void testLastEntry() throws Exception { 209 assertEquals(csm.lastEntry().getKey(), m.lastEntry().getKey()); 210 assertEquals(csm.lastEntry().getValue(), m.lastEntry().getValue()); 211 assertEquals(csm.lastEntry(), m.lastEntry()); 212 } 213 214 @Test testKeys()215 public void testKeys() throws Exception { 216 for (Long key:csm.keySet()) { 217 //assertTrue(m.containsKey(key)); 218 assertNotNull(m.get(key)); 219 assertNotNull(m.remove(key)); 220 assertNull(m.get(key)); 221 } 222 } 223 224 @Test testValues()225 public void testValues() throws Exception { 226 for (Long value:m.values()) { 227 assertTrue(csm.values().contains(value)); 228 assertTrue(m.containsValue(value)); 229 } 230 } 231 232 @Test testTailMap()233 public void testTailMap() throws Exception { 234 Map<Long, Long> fromCsm = csm.tailMap(50L); 235 Map<Long, Long> fromM = m.tailMap(50L); 236 assertEquals(fromCsm, fromM); 237 for (Long value:m.keySet()) { 238 assertEquals(csm.tailMap(value), m.tailMap(value)); 239 } 240 241 for ( long i = 0 ; i < 100; i++ ) { 242 long o = ThreadLocalRandom.current().nextLong(MAX_RAND); 243 assertEquals(csm.tailMap(o), m.tailMap(o)); 244 } 245 } 246 247 @Test testTailMapExclusive()248 public void testTailMapExclusive() throws Exception { 249 m.clear(); 250 m.put(100L, 100L); 251 m.put(101L, 101L); 252 m.put(101L, 101L); 253 m.put(103L, 103L); 254 m.put(99L, 99L); 255 m.put(102L, 102L); 256 257 long n = 100L; 258 CopyOnWriteArrayMap<Long,Long> tm99 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(99L, false); 259 for (Map.Entry<Long,Long> e:tm99.entrySet()) { 260 assertEquals(new Long(n), e.getKey()); 261 assertEquals(new Long(n), e.getValue()); 262 n++; 263 } 264 } 265 266 @Test testTailMapInclusive()267 public void testTailMapInclusive() throws Exception { 268 m.clear(); 269 m.put(100L, 100L); 270 m.put(101L, 101L); 271 m.put(101L, 101L); 272 m.put(103L, 103L); 273 m.put(99L, 99L); 274 m.put(102L, 102L); 275 276 long n = 102; 277 CopyOnWriteArrayMap<Long,Long> tm102 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(102L, true); 278 for (Map.Entry<Long,Long> e:tm102.entrySet()) { 279 assertEquals(new Long(n), e.getKey()); 280 assertEquals(new Long(n), e.getValue()); 281 n++; 282 } 283 n = 99; 284 CopyOnWriteArrayMap<Long,Long> tm98 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(98L, true); 285 for (Map.Entry<Long,Long> e:tm98.entrySet()) { 286 assertEquals(new Long(n), e.getKey()); 287 assertEquals(new Long(n), e.getValue()); 288 n++; 289 } 290 } 291 292 @Test testPut()293 public void testPut() throws Exception { 294 m.clear(); 295 m.put(100L, 100L); 296 m.put(101L, 101L); 297 m.put(101L, 101L); 298 m.put(103L, 103L); 299 m.put(99L, 99L); 300 m.put(102L, 102L); 301 long n = 99; 302 303 for (Map.Entry<Long, Long> e:m.entrySet()) { 304 assertEquals(new Long(n), e.getKey()); 305 assertEquals(new Long(n), e.getValue()); 306 n++; 307 } 308 assertEquals(5, m.size()); 309 assertEquals(false, m.isEmpty()); 310 } 311 }