001/** 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, software 013 * distributed under the License is distributed on an "AS IS" BASIS, 014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 015 * See the License for the specific language governing permissions and 016 * limitations under the License. 017 */ 018package org.apache.hadoop.hbase.types; 019 020import static org.junit.Assert.assertEquals; 021import static org.junit.Assert.assertFalse; 022import static org.junit.Assert.assertNotNull; 023import static org.junit.Assert.assertNull; 024import static org.junit.Assert.assertTrue; 025 026import java.util.Map; 027import java.util.concurrent.ConcurrentNavigableMap; 028import java.util.concurrent.ConcurrentSkipListMap; 029import java.util.concurrent.ThreadLocalRandom; 030import org.apache.hadoop.hbase.HBaseClassTestRule; 031import org.apache.hadoop.hbase.testclassification.MiscTests; 032import org.apache.hadoop.hbase.testclassification.SmallTests; 033import org.junit.Before; 034import org.junit.ClassRule; 035import org.junit.Test; 036import org.junit.experimental.categories.Category; 037 038@Category({ MiscTests.class, SmallTests.class }) 039public class TestCopyOnWriteMaps { 040 @ClassRule 041 public static final HBaseClassTestRule CLASS_RULE = 042 HBaseClassTestRule.forClass(TestCopyOnWriteMaps.class); 043 044 private static final int MAX_RAND = 10 * 1000 * 1000; 045 private ConcurrentNavigableMap<Long, Long> m; 046 private ConcurrentSkipListMap<Long, Long> csm; 047 048 @Before 049 public void setUp() { 050 m = new CopyOnWriteArrayMap<>(); 051 csm = new ConcurrentSkipListMap<>(); 052 053 for (long i = 0 ; i < 10000; i++) { 054 long o = ThreadLocalRandom.current().nextLong(MAX_RAND); 055 m.put(i, o); 056 csm.put(i,o); 057 } 058 long o = ThreadLocalRandom.current().nextLong(MAX_RAND); 059 m.put(0L, o); 060 csm.put(0L,o); 061 } 062 063 @Test 064 public void testSize() { 065 assertEquals("Size should always be equal", m.size(), csm.size()); 066 } 067 068 @Test 069 public void testIsEmpty() { 070 m.clear(); 071 assertTrue(m.isEmpty()); 072 m.put(100L, 100L); 073 assertFalse(m.isEmpty()); 074 m.remove(100L); 075 assertTrue(m.isEmpty()); 076 } 077 078 @Test 079 public void testFindOnEmpty() { 080 m.clear(); 081 assertTrue(m.isEmpty()); 082 assertNull(m.get(100L)); 083 assertFalse(m.containsKey(100L)); 084 assertEquals(0, m.tailMap(100L).entrySet().size()); 085 } 086 087 @Test 088 public void testLowerKey() { 089 assertEquals(csm.lowerKey(400L), m.lowerKey(400L)); 090 assertEquals(csm.lowerKey(-1L), m.lowerKey(-1L)); 091 092 for (int i = 0 ; i < 100; i++) { 093 Long key = ThreadLocalRandom.current().nextLong(); 094 assertEquals(csm.lowerKey(key), m.lowerKey(key)); 095 } 096 } 097 098 @Test 099 public void testFloorEntry() { 100 for (int i = 0 ; i < 100; i++) { 101 Long key = ThreadLocalRandom.current().nextLong(); 102 assertEquals(csm.floorEntry(key), m.floorEntry(key)); 103 } 104 } 105 106 @Test 107 public void testFloorKey() { 108 for (int i = 0 ; i < 100; i++) { 109 Long key = ThreadLocalRandom.current().nextLong(); 110 assertEquals(csm.floorKey(key), m.floorKey(key)); 111 } 112 } 113 114 @Test 115 public void testCeilingKey() { 116 assertEquals(csm.ceilingKey(4000L), m.ceilingKey(4000L)); 117 assertEquals(csm.ceilingKey(400L), m.ceilingKey(400L)); 118 assertEquals(csm.ceilingKey(-1L), m.ceilingKey(-1L)); 119 120 for (int i = 0 ; i < 100; i++) { 121 Long key = ThreadLocalRandom.current().nextLong(); 122 assertEquals(csm.ceilingKey(key), m.ceilingKey(key)); 123 } 124 } 125 126 @Test 127 public void testHigherKey() { 128 assertEquals(csm.higherKey(4000L), m.higherKey(4000L)); 129 assertEquals(csm.higherKey(400L), m.higherKey(400L)); 130 assertEquals(csm.higherKey(-1L), m.higherKey(-1L)); 131 132 for (int i = 0 ; i < 100; i++) { 133 Long key = ThreadLocalRandom.current().nextLong(); 134 assertEquals(csm.higherKey(key), m.higherKey(key)); 135 } 136 } 137 138 @Test 139 public void testRemove() { 140 for (Map.Entry<Long, Long> e : csm.entrySet()) { 141 assertEquals(csm.remove(e.getKey()), m.remove(e.getKey())); 142 assertNull(m.remove(e.getKey())); 143 } 144 } 145 146 @Test 147 public void testReplace() { 148 for (Map.Entry<Long, Long> e : csm.entrySet()) { 149 Long newValue = ThreadLocalRandom.current().nextLong(); 150 assertEquals(csm.replace(e.getKey(), newValue), m.replace(e.getKey(), newValue)); 151 } 152 assertNull(m.replace(MAX_RAND + 100L, ThreadLocalRandom.current().nextLong())); 153 } 154 155 @Test 156 public void testReplace1() { 157 for (Map.Entry<Long, Long> e : csm.entrySet()) { 158 Long newValue = ThreadLocalRandom.current().nextLong(); 159 assertEquals(csm.replace(e.getKey(), e.getValue() + 1, newValue), 160 m.replace(e.getKey(), e.getValue() + 1, newValue)); 161 assertEquals(csm.replace(e.getKey(), e.getValue(), newValue), 162 m.replace(e.getKey(), e.getValue(), newValue)); 163 assertEquals(newValue, m.get(e.getKey())); 164 assertEquals(csm.get(e.getKey()), m.get(e.getKey())); 165 } 166 assertNull(m.replace(MAX_RAND + 100L, ThreadLocalRandom.current().nextLong())); 167 } 168 169 @Test 170 public void testMultiAdd() throws InterruptedException { 171 Thread[] threads = new Thread[10]; 172 for (int i = 0 ; i < threads.length; i++) { 173 threads[i] = new Thread(() -> { 174 for (int j = 0; j < 5000; j++) { 175 m.put(ThreadLocalRandom.current().nextLong(), 176 ThreadLocalRandom.current().nextLong()); 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 191 public void testFirstKey() { 192 assertEquals(csm.firstKey(), m.firstKey()); 193 } 194 195 @Test 196 public void testLastKey() { 197 assertEquals(csm.lastKey(), m.lastKey()); 198 } 199 200 @Test 201 public void testFirstEntry() { 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 208 public void testLastEntry() { 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 215 public void testKeys() { 216 for (Long key : csm.keySet()) { 217 assertNotNull(m.get(key)); 218 assertNotNull(m.remove(key)); 219 assertNull(m.get(key)); 220 } 221 } 222 223 @Test 224 public void testValues() { 225 for (Long value : m.values()) { 226 assertTrue(csm.containsValue(value)); 227 assertTrue(m.containsValue(value)); 228 } 229 } 230 231 @Test 232 public void testTailMap() { 233 Map<Long, Long> fromCsm = csm.tailMap(50L); 234 Map<Long, Long> fromM = m.tailMap(50L); 235 assertEquals(fromCsm, fromM); 236 for (Long value : m.keySet()) { 237 assertEquals(csm.tailMap(value), m.tailMap(value)); 238 } 239 240 for (long i = 0; i < 100; i++) { 241 long o = ThreadLocalRandom.current().nextLong(MAX_RAND); 242 assertEquals(csm.tailMap(o), m.tailMap(o)); 243 } 244 } 245 246 @Test 247 public void testTailMapExclusive() { 248 m.clear(); 249 m.put(100L, 100L); 250 m.put(101L, 101L); 251 m.put(101L, 101L); 252 m.put(103L, 103L); 253 m.put(99L, 99L); 254 m.put(102L, 102L); 255 256 long n = 100L; 257 CopyOnWriteArrayMap<Long,Long> tm99 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(99L, false); 258 for (Map.Entry<Long,Long> e : tm99.entrySet()) { 259 assertEquals(Long.valueOf(n), e.getKey()); 260 assertEquals(Long.valueOf(n), e.getValue()); 261 n++; 262 } 263 } 264 265 @Test 266 public void testTailMapInclusive() { 267 m.clear(); 268 m.put(100L, 100L); 269 m.put(101L, 101L); 270 m.put(101L, 101L); 271 m.put(103L, 103L); 272 m.put(99L, 99L); 273 m.put(102L, 102L); 274 275 long n = 102; 276 CopyOnWriteArrayMap<Long,Long> tm102 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(102L, true); 277 for (Map.Entry<Long,Long> e : tm102.entrySet()) { 278 assertEquals(Long.valueOf(n), e.getKey()); 279 assertEquals(Long.valueOf(n), e.getValue()); 280 n++; 281 } 282 n = 99; 283 CopyOnWriteArrayMap<Long,Long> tm98 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(98L, true); 284 for (Map.Entry<Long,Long> e : tm98.entrySet()) { 285 assertEquals(Long.valueOf(n), e.getKey()); 286 assertEquals(Long.valueOf(n), e.getValue()); 287 n++; 288 } 289 } 290 291 @Test 292 public void testPut() { 293 m.clear(); 294 m.put(100L, 100L); 295 m.put(101L, 101L); 296 m.put(101L, 101L); 297 m.put(103L, 103L); 298 m.put(99L, 99L); 299 m.put(102L, 102L); 300 long n = 99; 301 302 for (Map.Entry<Long, Long> e : m.entrySet()) { 303 assertEquals(Long.valueOf(n), e.getKey()); 304 assertEquals(Long.valueOf(n), e.getValue()); 305 n++; 306 } 307 assertEquals(5, m.size()); 308 assertFalse(m.isEmpty()); 309 } 310}