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
setUp()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
testSize()56   public void testSize() throws Exception {
57     assertEquals("Size should always be equal", m.size(), csm.size());
58   }
59 
60   @Test
testIsEmpty()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
testFindOnEmpty()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
testLowerKey()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
testFloorEntry()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
testFloorKey()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
testCeilingKey()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
testHigherKey()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
testRemove()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
testReplace()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
testReplace1()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
testMultiAdd()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
testFirstKey()191   public void testFirstKey() throws Exception {
192     assertEquals(csm.firstKey(), m.firstKey());
193   }
194 
195   @Test
testLastKey()196   public void testLastKey() throws Exception {
197     assertEquals(csm.lastKey(), m.lastKey());
198   }
199 
200   @Test
testFirstEntry()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
testLastEntry()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
testKeys()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
testValues()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
testTailMap()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
testTailMapExclusive()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
testTailMapInclusive()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
testPut()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 }