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