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}