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_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(), 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}