1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
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 }