Source code

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