1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.map;
18
19 import static org.junit.jupiter.api.Assertions.assertAll;
20 import static org.junit.jupiter.api.Assertions.assertEquals;
21 import static org.junit.jupiter.api.Assertions.assertFalse;
22 import static org.junit.jupiter.api.Assertions.assertNotNull;
23 import static org.junit.jupiter.api.Assertions.assertNull;
24 import static org.junit.jupiter.api.Assertions.assertSame;
25 import static org.junit.jupiter.api.Assertions.assertThrows;
26 import static org.junit.jupiter.api.Assertions.assertTrue;
27 import static org.junit.jupiter.api.Assertions.fail;
28
29 import java.util.ArrayList;
30 import java.util.HashMap;
31 import java.util.Iterator;
32 import java.util.List;
33 import java.util.Map;
34
35 import org.apache.commons.collections4.MapIterator;
36 import org.apache.commons.collections4.OrderedMap;
37 import org.apache.commons.collections4.ResettableIterator;
38 import org.junit.jupiter.api.Test;
39
40
41
42
43 public class LRUMapTest<K, V> extends AbstractOrderedMapTest<K, V> {
44
45 static class MockLRUMapSubclass<K, V> extends LRUMap<K, V> {
46
47
48
49
50 private static final long serialVersionUID = -2126883654452042477L;
51 LinkEntry<K, V> entry;
52 K key;
53 V value;
54
55 MockLRUMapSubclass(final int size) {
56 super(size);
57 }
58
59 @Override
60 protected boolean removeLRU(final LinkEntry<K, V> entry) {
61 this.entry = entry;
62 this.key = entry.getKey();
63 this.value = entry.getValue();
64 return true;
65 }
66
67 }
68 static class MockLRUMapSubclassBlocksRemove<K, V> extends LRUMap<K, V> {
69
70
71
72
73 private static final long serialVersionUID = 6278917461128992945L;
74
75 MockLRUMapSubclassBlocksRemove(final int size, final boolean scanUntilRemove) {
76 super(size, scanUntilRemove);
77 }
78
79 @Override
80 protected boolean removeLRU(final LinkEntry<K, V> entry) {
81 return false;
82 }
83
84 }
85
86 static class MockLRUMapSubclassFirstBlocksRemove<K, V> extends LRUMap<K, V> {
87
88
89
90
91 private static final long serialVersionUID = -6939790801702973428L;
92
93 MockLRUMapSubclassFirstBlocksRemove(final int size) {
94 super(size, true);
95 }
96
97 @Override
98 protected boolean removeLRU(final LinkEntry<K, V> entry) {
99 if ("a".equals(entry.getValue())) {
100 return false;
101 }
102 return true;
103 }
104
105 }
106
107 static class SingleHashCode {
108
109 private final String code;
110
111 SingleHashCode(final String code) {
112 this.code = code;
113 }
114
115 @Override
116 public int hashCode() {
117
118
119 return 12;
120 }
121
122 @Override
123 public String toString() {
124 return "SingleHashCode:" + code;
125 }
126
127 }
128
129 public LRUMapTest() {
130 super(LRUMapTest.class.getSimpleName());
131 }
132
133 @Override
134 public String getCompatibilityVersion() {
135 return "4";
136 }
137
138
139
140
141 @Override
142 public LRUMap<K, V> getMap() {
143 return (LRUMap<K, V>) super.getMap();
144 }
145
146 @Override
147 public boolean isGetStructuralModify() {
148 return true;
149 }
150
151
152
153
154 @Override
155 public LRUMap<K, V> makeFullMap() {
156 return (LRUMap<K, V>) super.makeFullMap();
157 }
158
159 @Override
160 public LRUMap<K, V> makeObject() {
161 return new LRUMap<>();
162 }
163
164 @Test
165 public void testAccessOrder() {
166 if (!isPutAddSupported() || !isPutChangeSupported()) {
167 return;
168 }
169 final K[] keys = getSampleKeys();
170 final V[] values = getSampleValues();
171 Iterator<K> kit;
172 Iterator<V> vit;
173
174 resetEmpty();
175 map.put(keys[0], values[0]);
176 map.put(keys[1], values[1]);
177 kit = map.keySet().iterator();
178 assertSame(keys[0], kit.next());
179 assertSame(keys[1], kit.next());
180 vit = map.values().iterator();
181 assertSame(values[0], vit.next());
182 assertSame(values[1], vit.next());
183
184
185 map.put(keys[1], values[1]);
186 kit = map.keySet().iterator();
187 assertSame(keys[0], kit.next());
188 assertSame(keys[1], kit.next());
189 vit = map.values().iterator();
190 assertSame(values[0], vit.next());
191 assertSame(values[1], vit.next());
192
193
194 map.put(keys[1], values[2]);
195 kit = map.keySet().iterator();
196 assertSame(keys[0], kit.next());
197 assertSame(keys[1], kit.next());
198 vit = map.values().iterator();
199 assertSame(values[0], vit.next());
200 assertSame(values[2], vit.next());
201
202
203 map.put(keys[0], values[3]);
204 kit = map.keySet().iterator();
205 assertSame(keys[1], kit.next());
206 assertSame(keys[0], kit.next());
207 vit = map.values().iterator();
208 assertSame(values[2], vit.next());
209 assertSame(values[3], vit.next());
210
211
212 map.get(keys[1]);
213 kit = map.keySet().iterator();
214 assertSame(keys[0], kit.next());
215 assertSame(keys[1], kit.next());
216 vit = map.values().iterator();
217 assertSame(values[3], vit.next());
218 assertSame(values[2], vit.next());
219
220
221 map.get(keys[0]);
222 kit = map.keySet().iterator();
223 assertSame(keys[1], kit.next());
224 assertSame(keys[0], kit.next());
225 vit = map.values().iterator();
226 assertSame(values[2], vit.next());
227 assertSame(values[3], vit.next());
228
229
230 map.get(keys[0]);
231 kit = map.keySet().iterator();
232 assertSame(keys[1], kit.next());
233 assertSame(keys[0], kit.next());
234 vit = map.values().iterator();
235 assertSame(values[2], vit.next());
236 assertSame(values[3], vit.next());
237 }
238
239 @Test
240 public void testAccessOrder2() {
241 if (!isPutAddSupported() || !isPutChangeSupported()) {
242 return;
243 }
244 final K[] keys = getSampleKeys();
245 final V[] values = getSampleValues();
246 Iterator<K> kit;
247 Iterator<V> vit;
248
249 resetEmpty();
250 final LRUMap<K, V> lruMap = (LRUMap<K, V>) map;
251
252 lruMap.put(keys[0], values[0]);
253 lruMap.put(keys[1], values[1]);
254 kit = lruMap.keySet().iterator();
255 assertSame(keys[0], kit.next());
256 assertSame(keys[1], kit.next());
257 vit = lruMap.values().iterator();
258 assertSame(values[0], vit.next());
259 assertSame(values[1], vit.next());
260
261
262 lruMap.put(keys[1], values[1]);
263 kit = lruMap.keySet().iterator();
264 assertSame(keys[0], kit.next());
265 assertSame(keys[1], kit.next());
266 vit = lruMap.values().iterator();
267 assertSame(values[0], vit.next());
268 assertSame(values[1], vit.next());
269
270
271 lruMap.get(keys[1], false);
272 kit = lruMap.keySet().iterator();
273 assertSame(keys[0], kit.next());
274 assertSame(keys[1], kit.next());
275 vit = lruMap.values().iterator();
276 assertSame(values[0], vit.next());
277 assertSame(values[1], vit.next());
278
279
280 lruMap.get(keys[0], true);
281 kit = lruMap.keySet().iterator();
282 assertSame(keys[1], kit.next());
283 assertSame(keys[0], kit.next());
284 vit = lruMap.values().iterator();
285 assertSame(values[1], vit.next());
286 assertSame(values[0], vit.next());
287 }
288
289 @Test
290 @SuppressWarnings("unchecked")
291 public void testClone() {
292 final LRUMap<K, V> map = new LRUMap<>(10);
293 map.put((K) "1", (V) "1");
294 final Map<K, V> cloned = map.clone();
295 assertEquals(map.size(), cloned.size());
296 assertSame(map.get("1"), cloned.get("1"));
297 }
298
299 @Test
300 public void testCtors() {
301 assertAll(
302 () -> assertThrows(IllegalArgumentException.class, () -> new LRUMap<K, V>(0),
303 "maxSize must be positive"),
304 () -> assertThrows(IllegalArgumentException.class, () -> new LRUMap<K, V>(-1, 12, 0.75f, false),
305 "maxSize must be positive"),
306 () -> assertThrows(IllegalArgumentException.class, () -> new LRUMap<K, V>(10, -1),
307 "initialSize must not be negative"),
308 () -> assertThrows(IllegalArgumentException.class, () -> new LRUMap<K, V>(10, 12),
309 "initialSize must not be larger than maxSize"),
310 () -> assertThrows(IllegalArgumentException.class, () -> new LRUMap<K, V>(10, -1, 0.75f, false),
311 "initialSize must not be negative"),
312 () -> assertThrows(IllegalArgumentException.class, () -> new LRUMap<K, V>(10, 12, 0.75f, false),
313 "initialSize must not be larger than maxSize")
314 );
315 }
316
317 @Test
318 @SuppressWarnings("unchecked")
319 public void testInternalState_Buckets() {
320 if (!isPutAddSupported() || !isPutChangeSupported()) {
321 return;
322 }
323 final SingleHashCode one = new SingleHashCode("1");
324 final SingleHashCode two = new SingleHashCode("2");
325 final SingleHashCode three = new SingleHashCode("3");
326 final SingleHashCode four = new SingleHashCode("4");
327 final SingleHashCode five = new SingleHashCode("5");
328 final SingleHashCode six = new SingleHashCode("6");
329
330 final LRUMap<K, V> map = new LRUMap<>(3, 1.0f);
331 final int hashIndex = map.hashIndex(map.hash(one), 4);
332 map.put((K) one, (V) "A");
333 map.put((K) two, (V) "B");
334 map.put((K) three, (V) "C");
335
336 assertEquals(4, map.data.length);
337 assertEquals(3, map.size);
338 assertNull(map.header.next);
339 assertEquals(one, map.header.after.key);
340 assertEquals(two, map.header.after.after.key);
341 assertEquals(three, map.header.after.after.after.key);
342 assertEquals(three, map.data[hashIndex].key);
343 assertEquals(two, map.data[hashIndex].next.key);
344 assertEquals(one, map.data[hashIndex].next.next.key);
345
346 map.put((K) four, (V) "D");
347
348 assertEquals(4, map.data.length);
349 assertEquals(3, map.size);
350 assertNull(map.header.next);
351 assertEquals(two, map.header.after.key);
352 assertEquals(three, map.header.after.after.key);
353 assertEquals(four, map.header.after.after.after.key);
354 assertEquals(four, map.data[hashIndex].key);
355 assertEquals(three, map.data[hashIndex].next.key);
356 assertEquals(two, map.data[hashIndex].next.next.key);
357
358 map.get(three);
359
360 assertEquals(4, map.data.length);
361 assertEquals(3, map.size);
362 assertNull(map.header.next);
363 assertEquals(two, map.header.after.key);
364 assertEquals(four, map.header.after.after.key);
365 assertEquals(three, map.header.after.after.after.key);
366 assertEquals(four, map.data[hashIndex].key);
367 assertEquals(three, map.data[hashIndex].next.key);
368 assertEquals(two, map.data[hashIndex].next.next.key);
369
370 map.put((K) five, (V) "E");
371
372 assertEquals(4, map.data.length);
373 assertEquals(3, map.size);
374 assertNull(map.header.next);
375 assertEquals(four, map.header.after.key);
376 assertEquals(three, map.header.after.after.key);
377 assertEquals(five, map.header.after.after.after.key);
378 assertEquals(five, map.data[hashIndex].key);
379 assertEquals(four, map.data[hashIndex].next.key);
380 assertEquals(three, map.data[hashIndex].next.next.key);
381
382 map.get(three);
383 map.get(five);
384
385 assertEquals(4, map.data.length);
386 assertEquals(3, map.size);
387 assertNull(map.header.next);
388 assertEquals(four, map.header.after.key);
389 assertEquals(three, map.header.after.after.key);
390 assertEquals(five, map.header.after.after.after.key);
391 assertEquals(five, map.data[hashIndex].key);
392 assertEquals(four, map.data[hashIndex].next.key);
393 assertEquals(three, map.data[hashIndex].next.next.key);
394
395 map.put((K) six, (V) "F");
396
397 assertEquals(4, map.data.length);
398 assertEquals(3, map.size);
399 assertNull(map.header.next);
400 assertEquals(three, map.header.after.key);
401 assertEquals(five, map.header.after.after.key);
402 assertEquals(six, map.header.after.after.after.key);
403 assertEquals(six, map.data[hashIndex].key);
404 assertEquals(five, map.data[hashIndex].next.key);
405 assertEquals(three, map.data[hashIndex].next.next.key);
406 }
407
408 @Test
409 @SuppressWarnings("unchecked")
410 public void testInternalState_getEntry_int() {
411 if (!isPutAddSupported() || !isPutChangeSupported()) {
412 return;
413 }
414 final SingleHashCode one = new SingleHashCode("1");
415 final SingleHashCode two = new SingleHashCode("2");
416 final SingleHashCode three = new SingleHashCode("3");
417
418 final LRUMap<K, V> map = new LRUMap<>(3, 1.0f);
419 map.put((K) one, (V) "A");
420 map.put((K) two, (V) "B");
421 map.put((K) three, (V) "C");
422
423 assertEquals(one, map.getEntry(0).key);
424 assertEquals(two, map.getEntry(1).key);
425 assertEquals(three, map.getEntry(2).key);
426 assertAll(
427 () -> assertThrows(IndexOutOfBoundsException.class, () -> map.getEntry(-1)),
428 () -> assertThrows(IndexOutOfBoundsException.class, () -> map.getEntry(3))
429 );
430 }
431
432 @Test
433 public void testLRU() {
434 if (!isPutAddSupported() || !isPutChangeSupported()) {
435 return;
436 }
437 final K[] keys = getSampleKeys();
438 final V[] values = getSampleValues();
439 Iterator<K> kit;
440 Iterator<V> vit;
441
442 final LRUMap<K, V> map = new LRUMap<>(2);
443 assertEquals(0, map.size());
444 assertFalse(map.isFull());
445 assertEquals(2, map.maxSize());
446
447 map.put(keys[0], values[0]);
448 assertEquals(1, map.size());
449 assertFalse(map.isFull());
450 assertEquals(2, map.maxSize());
451
452 map.put(keys[1], values[1]);
453 assertEquals(2, map.size());
454 assertTrue(map.isFull());
455 assertEquals(2, map.maxSize());
456 kit = map.keySet().iterator();
457 assertSame(keys[0], kit.next());
458 assertSame(keys[1], kit.next());
459 vit = map.values().iterator();
460 assertSame(values[0], vit.next());
461 assertSame(values[1], vit.next());
462
463 map.put(keys[2], values[2]);
464 assertEquals(2, map.size());
465 assertTrue(map.isFull());
466 assertEquals(2, map.maxSize());
467 kit = map.keySet().iterator();
468 assertSame(keys[1], kit.next());
469 assertSame(keys[2], kit.next());
470 vit = map.values().iterator();
471 assertSame(values[1], vit.next());
472 assertSame(values[2], vit.next());
473
474 map.put(keys[2], values[0]);
475 assertEquals(2, map.size());
476 assertTrue(map.isFull());
477 assertEquals(2, map.maxSize());
478 kit = map.keySet().iterator();
479 assertSame(keys[1], kit.next());
480 assertSame(keys[2], kit.next());
481 vit = map.values().iterator();
482 assertSame(values[1], vit.next());
483 assertSame(values[0], vit.next());
484
485 map.put(keys[1], values[3]);
486 assertEquals(2, map.size());
487 assertTrue(map.isFull());
488 assertEquals(2, map.maxSize());
489 kit = map.keySet().iterator();
490 assertSame(keys[2], kit.next());
491 assertSame(keys[1], kit.next());
492 vit = map.values().iterator();
493 assertSame(values[0], vit.next());
494 assertSame(values[3], vit.next());
495 }
496
497 @Test
498 @SuppressWarnings("unchecked")
499 public void testRemoveLRU() {
500 final MockLRUMapSubclass<K, String> map = new MockLRUMapSubclass<>(2);
501 assertNull(map.entry);
502 map.put((K) "A", "a");
503 assertNull(map.entry);
504 map.put((K) "B", "b");
505 assertNull(map.entry);
506 map.put((K) "C", "c");
507 assertNotNull(map.entry);
508 assertEquals("A", map.key);
509 assertEquals("a", map.value);
510 assertEquals("C", map.entry.getKey());
511 assertEquals("c", map.entry.getValue());
512 assertFalse(map.containsKey("A"));
513 assertTrue(map.containsKey("B"));
514 assertTrue(map.containsKey("C"));
515 }
516
517 @Test
518 @SuppressWarnings("unchecked")
519 public void testRemoveLRUBlocksRemove() {
520 final MockLRUMapSubclassBlocksRemove<K, V> map = new MockLRUMapSubclassBlocksRemove<>(2, false);
521 assertEquals(0, map.size());
522 map.put((K) "A", (V) "a");
523 assertEquals(1, map.size());
524 map.put((K) "B", (V) "b");
525 assertEquals(2, map.size());
526 map.put((K) "C", (V) "c");
527 assertEquals(3, map.size());
528 assertEquals(2, map.maxSize());
529 assertTrue(map.containsKey("A"));
530 assertTrue(map.containsKey("B"));
531 assertTrue(map.containsKey("C"));
532 }
533
534 @Test
535 @SuppressWarnings("unchecked")
536 public void testRemoveLRUBlocksRemoveScan() {
537 final MockLRUMapSubclassBlocksRemove<K, V> map = new MockLRUMapSubclassBlocksRemove<>(2, true);
538 assertEquals(0, map.size());
539 map.put((K) "A", (V) "a");
540 assertEquals(1, map.size());
541 map.put((K) "B", (V) "b");
542 assertEquals(2, map.size());
543 map.put((K) "C", (V) "c");
544 assertEquals(3, map.size());
545 assertEquals(2, map.maxSize());
546 assertTrue(map.containsKey("A"));
547 assertTrue(map.containsKey("B"));
548 assertTrue(map.containsKey("C"));
549 }
550
551 @Test
552 @SuppressWarnings("unchecked")
553 public void testRemoveLRUFirstBlocksRemove() {
554 final MockLRUMapSubclassFirstBlocksRemove<K, V> map = new MockLRUMapSubclassFirstBlocksRemove<>(2);
555 assertEquals(0, map.size());
556 map.put((K) "A", (V) "a");
557 assertEquals(1, map.size());
558 map.put((K) "B", (V) "b");
559 assertEquals(2, map.size());
560 map.put((K) "C", (V) "c");
561 assertEquals(2, map.size());
562 assertEquals(2, map.maxSize());
563 assertTrue(map.containsKey("A"));
564 assertFalse(map.containsKey("B"));
565 assertTrue(map.containsKey("C"));
566 }
567
568 @Test
569 @SuppressWarnings("unchecked")
570 public void testReset() {
571 resetEmpty();
572 OrderedMap<K, V> ordered = getMap();
573 ((ResettableIterator<K>) ordered.mapIterator()).reset();
574
575 resetFull();
576 ordered = getMap();
577 final List<K> list = new ArrayList<>(ordered.keySet());
578 final ResettableIterator<K> it = (ResettableIterator<K>) ordered.mapIterator();
579 assertSame(list.get(0), it.next());
580 assertSame(list.get(1), it.next());
581 it.reset();
582 assertSame(list.get(0), it.next());
583 }
584
585 @Test
586 public void testSynchronizedRemoveFromEntrySet() throws InterruptedException {
587
588 final Map<Object, Thread> map = new LRUMap<>(10000);
589
590 final Map<Throwable, String> exceptions = new HashMap<>();
591 final ThreadGroup tg = new ThreadGroup(getName()) {
592 @Override
593 public void uncaughtException(final Thread t, final Throwable e) {
594 exceptions.put(e, t.getName());
595 super.uncaughtException(t, e);
596 }
597 };
598
599 final int[] counter = new int[1];
600 counter[0] = 0;
601 final Thread[] threads = new Thread[50];
602 for (int i = 0; i < threads.length; ++i) {
603 threads[i] = new Thread(tg, "JUnit Thread " + i) {
604
605 @Override
606 public void run() {
607 int i = 0;
608 try {
609 synchronized (this) {
610 notifyAll();
611 wait();
612 }
613 final Thread thread = Thread.currentThread();
614 while (i < 1000 && !interrupted()) {
615 synchronized (map) {
616 map.put(thread.getName() + "[" + ++i + "]", thread);
617 }
618 }
619 synchronized (map) {
620 map.entrySet().removeIf(entry -> entry.getValue() == this);
621 }
622 } catch (final InterruptedException e) {
623 fail("Unexpected InterruptedException");
624 }
625 if (i > 0) {
626 synchronized (counter) {
627 counter[0]++;
628 }
629 }
630 }
631
632 };
633 }
634
635 for (final Thread thread : threads) {
636 synchronized (thread) {
637 thread.start();
638 thread.wait();
639 }
640 }
641
642 for (final Thread thread : threads) {
643 synchronized (thread) {
644 thread.notifyAll();
645 }
646 }
647
648 Thread.sleep(1000);
649
650 for (final Thread thread : threads) {
651 thread.interrupt();
652 }
653 for (final Thread thread : threads) {
654 synchronized (thread) {
655 thread.join();
656 }
657 }
658
659 assertEquals(0, exceptions.size(), "Exceptions have been thrown: " + exceptions);
660 assertTrue(counter[0] >= threads.length,
661 "Each thread should have put at least 1 element into the map, but only " + counter[0] + " did succeed");
662 }
663
664 @Test
665 public void testSynchronizedRemoveFromKeySet() throws InterruptedException {
666
667 final Map<Object, Thread> map = new LRUMap<>(10000);
668
669 final Map<Throwable, String> exceptions = new HashMap<>();
670 final ThreadGroup tg = new ThreadGroup(getName()) {
671 @Override
672 public void uncaughtException(final Thread t, final Throwable e) {
673 exceptions.put(e, t.getName());
674 super.uncaughtException(t, e);
675 }
676 };
677
678 final int[] counter = new int[1];
679 counter[0] = 0;
680 final Thread[] threads = new Thread[50];
681 for (int i = 0; i < threads.length; ++i) {
682 threads[i] = new Thread(tg, "JUnit Thread " + i) {
683
684 @Override
685 public void run() {
686 int i = 0;
687 try {
688 synchronized (this) {
689 notifyAll();
690 wait();
691 }
692 final Thread thread = Thread.currentThread();
693 while (i < 1000 && !interrupted()) {
694 synchronized (map) {
695 map.put(thread.getName() + "[" + ++i + "]", thread);
696 }
697 }
698 synchronized (map) {
699 for (final Iterator<Object> iter = map.keySet().iterator(); iter.hasNext();) {
700 final String name = (String) iter.next();
701 if (name.substring(0, name.indexOf('[')).equals(getName())) {
702 iter.remove();
703 }
704 }
705 }
706 } catch (final InterruptedException e) {
707 fail("Unexpected InterruptedException");
708 }
709 if (i > 0) {
710 synchronized (counter) {
711 counter[0]++;
712 }
713 }
714 }
715
716 };
717 }
718
719 for (final Thread thread : threads) {
720 synchronized (thread) {
721 thread.start();
722 thread.wait();
723 }
724 }
725
726 for (final Thread thread : threads) {
727 synchronized (thread) {
728 thread.notifyAll();
729 }
730 }
731
732 Thread.sleep(1000);
733
734 for (final Thread thread : threads) {
735 thread.interrupt();
736 }
737 for (final Thread thread : threads) {
738 synchronized (thread) {
739 thread.join();
740 }
741 }
742
743 assertEquals(0, exceptions.size(), "Exceptions have been thrown: " + exceptions);
744 assertTrue(counter[0] >= threads.length,
745 "Each thread should have put at least 1 element into the map, but only " + counter[0] + " did succeed");
746 }
747
748 @Test
749 public void testSynchronizedRemoveFromMapIterator() throws InterruptedException {
750
751 final LRUMap<Object, Thread> map = new LRUMap<>(10000);
752
753 final Map<Throwable, String> exceptions = new HashMap<>();
754 final ThreadGroup tg = new ThreadGroup(getName()) {
755 @Override
756 public void uncaughtException(final Thread t, final Throwable e) {
757 exceptions.put(e, t.getName());
758 super.uncaughtException(t, e);
759 }
760 };
761
762 final int[] counter = new int[1];
763 counter[0] = 0;
764 final Thread[] threads = new Thread[50];
765 for (int i = 0; i < threads.length; ++i) {
766 threads[i] = new Thread(tg, "JUnit Thread " + i) {
767
768 @Override
769 public void run() {
770 int i = 0;
771 try {
772 synchronized (this) {
773 notifyAll();
774 wait();
775 }
776 final Thread thread = Thread.currentThread();
777 while (i < 1000 && !interrupted()) {
778 synchronized (map) {
779 map.put(thread.getName() + "[" + ++i + "]", thread);
780 }
781 }
782 synchronized (map) {
783 for (final MapIterator<Object, Thread> iter = map.mapIterator(); iter.hasNext();) {
784 iter.next();
785 if (iter.getValue() == this) {
786 iter.remove();
787 }
788 }
789 }
790 } catch (final InterruptedException e) {
791 fail("Unexpected InterruptedException");
792 }
793 if (i > 0) {
794 synchronized (counter) {
795 counter[0]++;
796 }
797 }
798 }
799
800 };
801 }
802
803 for (final Thread thread : threads) {
804 synchronized (thread) {
805 thread.start();
806 thread.wait();
807 }
808 }
809
810 for (final Thread thread : threads) {
811 synchronized (thread) {
812 thread.notifyAll();
813 }
814 }
815
816 Thread.sleep(1000);
817
818 for (final Thread thread : threads) {
819 thread.interrupt();
820 }
821 for (final Thread thread : threads) {
822 synchronized (thread) {
823 thread.join();
824 }
825 }
826
827 assertEquals(0, exceptions.size(), "Exceptions have been thrown: " + exceptions);
828 assertTrue(counter[0] >= threads.length,
829 "Each thread should have put at least 1 element into the map, but only " + counter[0] + " did succeed");
830 }
831
832 @Test
833 public void testSynchronizedRemoveFromValues() throws InterruptedException {
834
835 final Map<Object, Thread> map = new LRUMap<>(10000);
836
837 final Map<Throwable, String> exceptions = new HashMap<>();
838 final ThreadGroup tg = new ThreadGroup(getName()) {
839 @Override
840 public void uncaughtException(final Thread t, final Throwable e) {
841 exceptions.put(e, t.getName());
842 super.uncaughtException(t, e);
843 }
844 };
845
846 final int[] counter = new int[1];
847 counter[0] = 0;
848 final Thread[] threads = new Thread[50];
849 for (int i = 0; i < threads.length; ++i) {
850 threads[i] = new Thread(tg, "JUnit Thread " + i) {
851
852 @Override
853 public void run() {
854 int i = 0;
855 try {
856 synchronized (this) {
857 notifyAll();
858 wait();
859 }
860 final Thread thread = Thread.currentThread();
861 while (i < 1000 && !interrupted()) {
862 synchronized (map) {
863 map.put(thread.getName() + "[" + ++i + "]", thread);
864 }
865 }
866 synchronized (map) {
867 map.values().removeIf(thread1 -> thread1 == this);
868 }
869 } catch (final InterruptedException e) {
870 fail("Unexpected InterruptedException");
871 }
872 if (i > 0) {
873 synchronized (counter) {
874 counter[0]++;
875 }
876 }
877 }
878
879 };
880 }
881
882 for (final Thread thread : threads) {
883 synchronized (thread) {
884 thread.start();
885 thread.wait();
886 }
887 }
888
889 for (final Thread thread : threads) {
890 synchronized (thread) {
891 thread.notifyAll();
892 }
893 }
894
895 Thread.sleep(1000);
896
897 for (final Thread thread : threads) {
898 thread.interrupt();
899 }
900 for (final Thread thread : threads) {
901 synchronized (thread) {
902 thread.join();
903 }
904 }
905
906 assertEquals(0, exceptions.size(), "Exceptions have been thrown: " + exceptions);
907 assertTrue(counter[0] >= threads.length,
908 "Each thread should have put at least 1 element into the map, but only " + counter[0] + " did succeed");
909 }
910
911
912
913
914
915
916
917
918 }