View Javadoc

1   /**
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.hadoop.hbase.types;
20  
21  import org.apache.hadoop.hbase.testclassification.SmallTests;
22  import org.junit.Before;
23  import org.junit.Test;
24  import org.junit.experimental.categories.Category;
25  
26  import java.util.Map;
27  import java.util.concurrent.ConcurrentNavigableMap;
28  import java.util.concurrent.ConcurrentSkipListMap;
29  import java.util.concurrent.ThreadLocalRandom;
30  
31  import static org.junit.Assert.*;
32  
33  @Category(SmallTests.class)
34  public class TestCopyOnWriteMaps {
35  
36    private static final int MAX_RAND = 10 * 1000 * 1000;
37    private ConcurrentNavigableMap<Long, Long> m;
38    private ConcurrentSkipListMap<Long, Long> csm;
39  
40    @Before
41    public void setUp() {
42      m = new CopyOnWriteArrayMap<>();
43      csm = new ConcurrentSkipListMap<>();
44  
45      for (  long i = 0 ; i < 10000; i++ ) {
46        long o = ThreadLocalRandom.current().nextLong(MAX_RAND);
47        m.put(i, o);
48        csm.put(i,o);
49      }
50      long o = ThreadLocalRandom.current().nextLong(MAX_RAND);
51      m.put(0L, o);
52      csm.put(0L,o);
53    }
54  
55    @Test
56    public void testSize() throws Exception {
57      assertEquals("Size should always be equal", m.size(), csm.size());
58    }
59  
60    @Test
61    public void testIsEmpty() throws Exception {
62      m.clear();
63      assertTrue(m.isEmpty());
64      m.put(100L, 100L);
65      assertFalse(m.isEmpty());
66      m.remove(100L);
67      assertTrue(m.isEmpty());
68    }
69  
70    @Test
71    public void testFindOnEmpty() throws Exception {
72      m.clear();
73      assertTrue(m.isEmpty());
74      assertNull(m.get(100L));
75      assertFalse(m.containsKey(100L));
76      assertEquals(0, m.tailMap(100L).entrySet().size());
77    }
78  
79  
80    @Test
81    public void testLowerKey() throws Exception {
82  
83      assertEquals(csm.lowerKey(400L), m.lowerKey(400L));
84      assertEquals(csm.lowerKey(-1L), m.lowerKey(-1L));
85  
86      for ( int i =0 ; i < 100; i ++) {
87        Long key = ThreadLocalRandom.current().nextLong();
88        assertEquals(csm.lowerKey(key), m.lowerKey(key));
89      }
90    }
91  
92    @Test
93    public void testFloorEntry() throws Exception {
94      for ( int i =0 ; i < 100; i ++) {
95        Long key = ThreadLocalRandom.current().nextLong();
96        assertEquals(csm.floorEntry(key), m.floorEntry(key));
97      }
98    }
99  
100   @Test
101   public void testFloorKey() throws Exception {
102     for ( int i =0 ; i < 100; i ++) {
103       Long key = ThreadLocalRandom.current().nextLong();
104       assertEquals(csm.floorKey(key), m.floorKey(key));
105     }
106   }
107 
108   @Test
109   public void testCeilingKey() throws Exception {
110 
111     assertEquals(csm.ceilingKey(4000L), m.ceilingKey(4000L));
112     assertEquals(csm.ceilingKey(400L), m.ceilingKey(400L));
113     assertEquals(csm.ceilingKey(-1L), m.ceilingKey(-1L));
114 
115     for ( int i =0 ; i < 100; i ++) {
116       Long key = ThreadLocalRandom.current().nextLong();
117       assertEquals(csm.ceilingKey(key), m.ceilingKey(key));
118     }
119   }
120 
121   @Test
122   public void testHigherKey() throws Exception {
123 
124     assertEquals(csm.higherKey(4000L), m.higherKey(4000L));
125     assertEquals(csm.higherKey(400L), m.higherKey(400L));
126     assertEquals(csm.higherKey(-1L), m.higherKey(-1L));
127 
128     for ( int i =0 ; i < 100; i ++) {
129       Long key = ThreadLocalRandom.current().nextLong();
130       assertEquals(csm.higherKey(key), m.higherKey(key));
131     }
132   }
133 
134   @Test
135   public void testRemove() throws Exception {
136     for (Map.Entry<Long, Long> e:csm.entrySet()) {
137       assertEquals(csm.remove(e.getKey()), m.remove(e.getKey()));
138       assertEquals(null, m.remove(e.getKey()));
139     }
140   }
141 
142   @Test
143   public void testReplace() throws Exception {
144     for (Map.Entry<Long, Long> e:csm.entrySet()) {
145       Long newValue = ThreadLocalRandom.current().nextLong();
146       assertEquals(csm.replace(e.getKey(), newValue), m.replace(e.getKey(), newValue));
147     }
148     assertEquals(null, m.replace(MAX_RAND + 100L, ThreadLocalRandom.current().nextLong()));
149   }
150 
151   @Test
152   public void testReplace1() throws Exception {
153     for (Map.Entry<Long, Long> e: csm.entrySet()) {
154       Long newValue = ThreadLocalRandom.current().nextLong();
155       assertEquals(csm.replace(e.getKey(), e.getValue() + 1, newValue),
156           m.replace(e.getKey(), e.getValue() + 1, newValue));
157       assertEquals(csm.replace(e.getKey(), e.getValue(), newValue),
158           m.replace(e.getKey(), e.getValue(), newValue));
159       assertEquals(newValue, m.get(e.getKey()));
160       assertEquals(csm.get(e.getKey()), m.get(e.getKey()));
161     }
162     assertEquals(null, m.replace(MAX_RAND + 100L, ThreadLocalRandom.current().nextLong()));
163   }
164 
165   @Test
166   public void testMultiAdd() throws InterruptedException {
167 
168     Thread[] threads = new Thread[10];
169     for ( int i =0 ; i<threads.length; i++) {
170       threads[i] = new Thread(new Runnable() {
171         @Override
172         public void run() {
173           for ( int j = 0; j < 5000; j++) {
174             m.put(ThreadLocalRandom.current().nextLong(),
175                 ThreadLocalRandom.current().nextLong());
176           }
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() throws Exception {
192     assertEquals(csm.firstKey(), m.firstKey());
193   }
194 
195   @Test
196   public void testLastKey() throws Exception {
197     assertEquals(csm.lastKey(), m.lastKey());
198   }
199 
200   @Test
201   public void testFirstEntry() throws Exception {
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() throws Exception {
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() throws Exception {
216     for (Long key:csm.keySet()) {
217       //assertTrue(m.containsKey(key));
218       assertNotNull(m.get(key));
219       assertNotNull(m.remove(key));
220       assertNull(m.get(key));
221     }
222   }
223 
224   @Test
225   public void testValues() throws Exception {
226     for (Long value:m.values()) {
227       assertTrue(csm.values().contains(value));
228       assertTrue(m.containsValue(value));
229     }
230   }
231 
232   @Test
233   public void testTailMap() throws Exception {
234     Map<Long, Long> fromCsm = csm.tailMap(50L);
235     Map<Long, Long> fromM = m.tailMap(50L);
236     assertEquals(fromCsm, fromM);
237     for (Long value:m.keySet()) {
238       assertEquals(csm.tailMap(value), m.tailMap(value));
239     }
240 
241     for (  long i = 0 ; i < 100; i++ ) {
242       long o = ThreadLocalRandom.current().nextLong(MAX_RAND);
243       assertEquals(csm.tailMap(o), m.tailMap(o));
244     }
245   }
246 
247   @Test
248   public void testTailMapExclusive() throws Exception {
249     m.clear();
250     m.put(100L, 100L);
251     m.put(101L, 101L);
252     m.put(101L, 101L);
253     m.put(103L, 103L);
254     m.put(99L, 99L);
255     m.put(102L, 102L);
256 
257     long n = 100L;
258     CopyOnWriteArrayMap<Long,Long> tm99 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(99L, false);
259     for (Map.Entry<Long,Long> e:tm99.entrySet()) {
260       assertEquals(new Long(n), e.getKey());
261       assertEquals(new Long(n), e.getValue());
262       n++;
263     }
264   }
265 
266   @Test
267   public void testTailMapInclusive() throws Exception {
268     m.clear();
269     m.put(100L, 100L);
270     m.put(101L, 101L);
271     m.put(101L, 101L);
272     m.put(103L, 103L);
273     m.put(99L, 99L);
274     m.put(102L, 102L);
275 
276     long n = 102;
277     CopyOnWriteArrayMap<Long,Long> tm102 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(102L, true);
278     for (Map.Entry<Long,Long> e:tm102.entrySet()) {
279       assertEquals(new Long(n), e.getKey());
280       assertEquals(new Long(n), e.getValue());
281       n++;
282     }
283     n = 99;
284     CopyOnWriteArrayMap<Long,Long> tm98 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(98L, true);
285     for (Map.Entry<Long,Long> e:tm98.entrySet()) {
286       assertEquals(new Long(n), e.getKey());
287       assertEquals(new Long(n), e.getValue());
288       n++;
289     }
290   }
291 
292   @Test
293   public void testPut() throws Exception {
294     m.clear();
295     m.put(100L, 100L);
296     m.put(101L, 101L);
297     m.put(101L, 101L);
298     m.put(103L, 103L);
299     m.put(99L, 99L);
300     m.put(102L, 102L);
301     long n = 99;
302 
303     for (Map.Entry<Long, Long> e:m.entrySet()) {
304       assertEquals(new Long(n), e.getKey());
305       assertEquals(new Long(n), e.getValue());
306       n++;
307     }
308     assertEquals(5, m.size());
309     assertEquals(false, m.isEmpty());
310   }
311 }