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.MiscTests;
032import org.apache.hadoop.hbase.testclassification.SmallTests;
033import org.junit.Before;
034import org.junit.ClassRule;
035import org.junit.Test;
036import org.junit.experimental.categories.Category;
037
038@Category({ MiscTests.class, SmallTests.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(),
176              ThreadLocalRandom.current().nextLong());
177        }
178      });
179    }
180
181    for (Thread thread1 : threads) {
182      thread1.start();
183    }
184
185    for (Thread thread2 : threads) {
186      thread2.join();
187    }
188  }
189
190  @Test
191  public void testFirstKey() {
192    assertEquals(csm.firstKey(), m.firstKey());
193  }
194
195  @Test
196  public void testLastKey() {
197    assertEquals(csm.lastKey(), m.lastKey());
198  }
199
200  @Test
201  public void testFirstEntry() {
202    assertEquals(csm.firstEntry().getKey(), m.firstEntry().getKey());
203    assertEquals(csm.firstEntry().getValue(), m.firstEntry().getValue());
204    assertEquals(csm.firstEntry(), m.firstEntry());
205  }
206
207  @Test
208  public void testLastEntry() {
209    assertEquals(csm.lastEntry().getKey(), m.lastEntry().getKey());
210    assertEquals(csm.lastEntry().getValue(), m.lastEntry().getValue());
211    assertEquals(csm.lastEntry(), m.lastEntry());
212  }
213
214  @Test
215  public void testKeys() {
216    for (Long key : csm.keySet()) {
217      assertNotNull(m.get(key));
218      assertNotNull(m.remove(key));
219      assertNull(m.get(key));
220    }
221  }
222
223  @Test
224  public void testValues() {
225    for (Long value : m.values()) {
226      assertTrue(csm.containsValue(value));
227      assertTrue(m.containsValue(value));
228    }
229  }
230
231  @Test
232  public void testTailMap() {
233    Map<Long, Long> fromCsm = csm.tailMap(50L);
234    Map<Long, Long> fromM = m.tailMap(50L);
235    assertEquals(fromCsm, fromM);
236    for (Long value : m.keySet()) {
237      assertEquals(csm.tailMap(value), m.tailMap(value));
238    }
239
240    for (long i = 0; i < 100; i++) {
241      long o = ThreadLocalRandom.current().nextLong(MAX_RAND);
242      assertEquals(csm.tailMap(o), m.tailMap(o));
243    }
244  }
245
246  @Test
247  public void testTailMapExclusive() {
248    m.clear();
249    m.put(100L, 100L);
250    m.put(101L, 101L);
251    m.put(101L, 101L);
252    m.put(103L, 103L);
253    m.put(99L, 99L);
254    m.put(102L, 102L);
255
256    long n = 100L;
257    CopyOnWriteArrayMap<Long,Long> tm99 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(99L, false);
258    for (Map.Entry<Long,Long> e : tm99.entrySet()) {
259      assertEquals(Long.valueOf(n), e.getKey());
260      assertEquals(Long.valueOf(n), e.getValue());
261      n++;
262    }
263  }
264
265  @Test
266  public void testTailMapInclusive() {
267    m.clear();
268    m.put(100L, 100L);
269    m.put(101L, 101L);
270    m.put(101L, 101L);
271    m.put(103L, 103L);
272    m.put(99L, 99L);
273    m.put(102L, 102L);
274
275    long n = 102;
276    CopyOnWriteArrayMap<Long,Long> tm102 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(102L, true);
277    for (Map.Entry<Long,Long> e : tm102.entrySet()) {
278      assertEquals(Long.valueOf(n), e.getKey());
279      assertEquals(Long.valueOf(n), e.getValue());
280      n++;
281    }
282    n = 99;
283    CopyOnWriteArrayMap<Long,Long> tm98 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(98L, true);
284    for (Map.Entry<Long,Long> e : tm98.entrySet()) {
285      assertEquals(Long.valueOf(n), e.getKey());
286      assertEquals(Long.valueOf(n), e.getValue());
287      n++;
288    }
289  }
290
291  @Test
292  public void testPut() {
293    m.clear();
294    m.put(100L, 100L);
295    m.put(101L, 101L);
296    m.put(101L, 101L);
297    m.put(103L, 103L);
298    m.put(99L, 99L);
299    m.put(102L, 102L);
300    long n = 99;
301
302    for (Map.Entry<Long, Long> e : m.entrySet()) {
303      assertEquals(Long.valueOf(n), e.getKey());
304      assertEquals(Long.valueOf(n), e.getValue());
305      n++;
306    }
307    assertEquals(5, m.size());
308    assertFalse(m.isEmpty());
309  }
310}