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; 025import java.util.Map; 026import java.util.concurrent.ConcurrentNavigableMap; 027import java.util.concurrent.ConcurrentSkipListMap; 028import java.util.concurrent.ThreadLocalRandom; 029import org.apache.hadoop.hbase.HBaseClassTestRule; 030import org.apache.hadoop.hbase.testclassification.MediumTests; 031import org.apache.hadoop.hbase.testclassification.MiscTests; 032import org.junit.Before; 033import org.junit.ClassRule; 034import org.junit.Test; 035import org.junit.experimental.categories.Category; 036 037@Category({ MiscTests.class, MediumTests.class }) 038public class TestCopyOnWriteMaps { 039 @ClassRule 040 public static final HBaseClassTestRule CLASS_RULE = 041 HBaseClassTestRule.forClass(TestCopyOnWriteMaps.class); 042 043 private static final int MAX_RAND = 10 * 1000 * 1000; 044 private ConcurrentNavigableMap<Long, Long> m; 045 private ConcurrentSkipListMap<Long, Long> csm; 046 047 @Before 048 public void setUp() { 049 m = new CopyOnWriteArrayMap<>(); 050 csm = new ConcurrentSkipListMap<>(); 051 052 for (long i = 0 ; i < 10000; i++) { 053 long o = ThreadLocalRandom.current().nextLong(MAX_RAND); 054 m.put(i, o); 055 csm.put(i,o); 056 } 057 long o = ThreadLocalRandom.current().nextLong(MAX_RAND); 058 m.put(0L, o); 059 csm.put(0L,o); 060 } 061 062 @Test 063 public void testSize() { 064 assertEquals("Size should always be equal", m.size(), csm.size()); 065 } 066 067 @Test 068 public void testIsEmpty() { 069 m.clear(); 070 assertTrue(m.isEmpty()); 071 m.put(100L, 100L); 072 assertFalse(m.isEmpty()); 073 m.remove(100L); 074 assertTrue(m.isEmpty()); 075 } 076 077 @Test 078 public void testFindOnEmpty() { 079 m.clear(); 080 assertTrue(m.isEmpty()); 081 assertNull(m.get(100L)); 082 assertFalse(m.containsKey(100L)); 083 assertEquals(0, m.tailMap(100L).entrySet().size()); 084 } 085 086 @Test 087 public void testLowerKey() { 088 assertEquals(csm.lowerKey(400L), m.lowerKey(400L)); 089 assertEquals(csm.lowerKey(-1L), m.lowerKey(-1L)); 090 091 for (int i = 0 ; i < 100; i++) { 092 Long key = ThreadLocalRandom.current().nextLong(); 093 assertEquals(csm.lowerKey(key), m.lowerKey(key)); 094 } 095 } 096 097 @Test 098 public void testFloorEntry() { 099 for (int i = 0 ; i < 100; i++) { 100 Long key = ThreadLocalRandom.current().nextLong(); 101 assertEquals(csm.floorEntry(key), m.floorEntry(key)); 102 } 103 } 104 105 @Test 106 public void testFloorKey() { 107 for (int i = 0 ; i < 100; i++) { 108 Long key = ThreadLocalRandom.current().nextLong(); 109 assertEquals(csm.floorKey(key), m.floorKey(key)); 110 } 111 } 112 113 @Test 114 public void testCeilingKey() { 115 assertEquals(csm.ceilingKey(4000L), m.ceilingKey(4000L)); 116 assertEquals(csm.ceilingKey(400L), m.ceilingKey(400L)); 117 assertEquals(csm.ceilingKey(-1L), m.ceilingKey(-1L)); 118 119 for (int i = 0 ; i < 100; i++) { 120 Long key = ThreadLocalRandom.current().nextLong(); 121 assertEquals(csm.ceilingKey(key), m.ceilingKey(key)); 122 } 123 } 124 125 @Test 126 public void testHigherKey() { 127 assertEquals(csm.higherKey(4000L), m.higherKey(4000L)); 128 assertEquals(csm.higherKey(400L), m.higherKey(400L)); 129 assertEquals(csm.higherKey(-1L), m.higherKey(-1L)); 130 131 for (int i = 0 ; i < 100; i++) { 132 Long key = ThreadLocalRandom.current().nextLong(); 133 assertEquals(csm.higherKey(key), m.higherKey(key)); 134 } 135 } 136 137 @Test 138 public void testRemove() { 139 for (Map.Entry<Long, Long> e : csm.entrySet()) { 140 assertEquals(csm.remove(e.getKey()), m.remove(e.getKey())); 141 assertNull(m.remove(e.getKey())); 142 } 143 } 144 145 @Test 146 public void testReplace() { 147 for (Map.Entry<Long, Long> e : csm.entrySet()) { 148 Long newValue = ThreadLocalRandom.current().nextLong(); 149 assertEquals(csm.replace(e.getKey(), newValue), m.replace(e.getKey(), newValue)); 150 } 151 assertNull(m.replace(MAX_RAND + 100L, ThreadLocalRandom.current().nextLong())); 152 } 153 154 @Test 155 public void testReplace1() { 156 for (Map.Entry<Long, Long> e : csm.entrySet()) { 157 Long newValue = ThreadLocalRandom.current().nextLong(); 158 assertEquals(csm.replace(e.getKey(), e.getValue() + 1, newValue), 159 m.replace(e.getKey(), e.getValue() + 1, newValue)); 160 assertEquals(csm.replace(e.getKey(), e.getValue(), newValue), 161 m.replace(e.getKey(), e.getValue(), newValue)); 162 assertEquals(newValue, m.get(e.getKey())); 163 assertEquals(csm.get(e.getKey()), m.get(e.getKey())); 164 } 165 assertNull(m.replace(MAX_RAND + 100L, ThreadLocalRandom.current().nextLong())); 166 } 167 168 @Test 169 public void testMultiAdd() throws InterruptedException { 170 Thread[] threads = new Thread[10]; 171 for (int i = 0 ; i < threads.length; i++) { 172 threads[i] = new Thread(() -> { 173 for (int j = 0; j < 5000; j++) { 174 m.put(ThreadLocalRandom.current().nextLong(), 175 ThreadLocalRandom.current().nextLong()); 176 } 177 }); 178 } 179 180 for (Thread thread1 : threads) { 181 thread1.start(); 182 } 183 184 for (Thread thread2 : threads) { 185 thread2.join(); 186 } 187 } 188 189 @Test 190 public void testFirstKey() { 191 assertEquals(csm.firstKey(), m.firstKey()); 192 } 193 194 @Test 195 public void testLastKey() { 196 assertEquals(csm.lastKey(), m.lastKey()); 197 } 198 199 @Test 200 public void testFirstEntry() { 201 assertEquals(csm.firstEntry().getKey(), m.firstEntry().getKey()); 202 assertEquals(csm.firstEntry().getValue(), m.firstEntry().getValue()); 203 assertEquals(csm.firstEntry(), m.firstEntry()); 204 } 205 206 @Test 207 public void testLastEntry() { 208 assertEquals(csm.lastEntry().getKey(), m.lastEntry().getKey()); 209 assertEquals(csm.lastEntry().getValue(), m.lastEntry().getValue()); 210 assertEquals(csm.lastEntry(), m.lastEntry()); 211 } 212 213 @Test 214 public void testKeys() { 215 for (Long key : csm.keySet()) { 216 assertNotNull(m.get(key)); 217 assertNotNull(m.remove(key)); 218 assertNull(m.get(key)); 219 } 220 } 221 222 @Test 223 public void testValues() { 224 for (Long value : m.values()) { 225 assertTrue(csm.containsValue(value)); 226 assertTrue(m.containsValue(value)); 227 } 228 } 229 230 @Test 231 public void testTailMap() { 232 Map<Long, Long> fromCsm = csm.tailMap(50L); 233 Map<Long, Long> fromM = m.tailMap(50L); 234 assertEquals(fromCsm, fromM); 235 for (Long value : m.keySet()) { 236 assertEquals(csm.tailMap(value), m.tailMap(value)); 237 } 238 239 for (long i = 0; i < 100; i++) { 240 long o = ThreadLocalRandom.current().nextLong(MAX_RAND); 241 assertEquals(csm.tailMap(o), m.tailMap(o)); 242 } 243 } 244 245 @Test 246 public void testTailMapExclusive() { 247 m.clear(); 248 m.put(100L, 100L); 249 m.put(101L, 101L); 250 m.put(101L, 101L); 251 m.put(103L, 103L); 252 m.put(99L, 99L); 253 m.put(102L, 102L); 254 255 long n = 100L; 256 CopyOnWriteArrayMap<Long,Long> tm99 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(99L, false); 257 for (Map.Entry<Long,Long> e : tm99.entrySet()) { 258 assertEquals(Long.valueOf(n), e.getKey()); 259 assertEquals(Long.valueOf(n), e.getValue()); 260 n++; 261 } 262 } 263 264 @Test 265 public void testTailMapInclusive() { 266 m.clear(); 267 m.put(100L, 100L); 268 m.put(101L, 101L); 269 m.put(101L, 101L); 270 m.put(103L, 103L); 271 m.put(99L, 99L); 272 m.put(102L, 102L); 273 274 long n = 102; 275 CopyOnWriteArrayMap<Long,Long> tm102 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(102L, true); 276 for (Map.Entry<Long,Long> e : tm102.entrySet()) { 277 assertEquals(Long.valueOf(n), e.getKey()); 278 assertEquals(Long.valueOf(n), e.getValue()); 279 n++; 280 } 281 n = 99; 282 CopyOnWriteArrayMap<Long,Long> tm98 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(98L, true); 283 for (Map.Entry<Long,Long> e : tm98.entrySet()) { 284 assertEquals(Long.valueOf(n), e.getKey()); 285 assertEquals(Long.valueOf(n), e.getValue()); 286 n++; 287 } 288 } 289 290 @Test 291 public void testPut() { 292 m.clear(); 293 m.put(100L, 100L); 294 m.put(101L, 101L); 295 m.put(101L, 101L); 296 m.put(103L, 103L); 297 m.put(99L, 99L); 298 m.put(102L, 102L); 299 long n = 99; 300 301 for (Map.Entry<Long, Long> e : m.entrySet()) { 302 assertEquals(Long.valueOf(n), e.getKey()); 303 assertEquals(Long.valueOf(n), e.getValue()); 304 n++; 305 } 306 assertEquals(5, m.size()); 307 assertFalse(m.isEmpty()); 308 } 309}