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