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