| 1 |
/* |
| 2 |
* Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. |
| 3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 |
* |
| 5 |
* This code is free software; you can redistribute it and/or modify it |
| 6 |
* under the terms of the GNU General Public License version 2 only, as |
| 7 |
* published by the Free Software Foundation. |
| 8 |
* |
| 9 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
| 10 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 11 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| 12 |
* version 2 for more details (a copy is included in the LICENSE file that |
| 13 |
* accompanied this code). |
| 14 |
* |
| 15 |
* You should have received a copy of the GNU General Public License version |
| 16 |
* 2 along with this work; if not, write to the Free Software Foundation, |
| 17 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| 18 |
* |
| 19 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| 20 |
* or visit www.oracle.com if you need additional information or have any |
| 21 |
* questions. |
| 22 |
*/ |
| 23 |
|
| 24 |
import org.testng.annotations.Test; |
| 25 |
|
| 26 |
import java.util.concurrent.CompletableFuture; |
| 27 |
import java.util.concurrent.CompletionException; |
| 28 |
import java.util.concurrent.ConcurrentHashMap; |
| 29 |
import java.util.concurrent.CountDownLatch; |
| 30 |
import java.util.function.Supplier; |
| 31 |
import java.util.stream.IntStream; |
| 32 |
import java.util.stream.Stream; |
| 33 |
|
| 34 |
/** |
| 35 |
* @test |
| 36 |
* @bug 8028564 |
| 37 |
* @run testng ConcurrentContainsKeyTest |
| 38 |
* @summary Test that entries are always present in the map, |
| 39 |
* when entries are held within one bin that is a tree |
| 40 |
*/ |
| 41 |
@Test |
| 42 |
public class ConcurrentContainsKeyTest { |
| 43 |
|
| 44 |
// The number of entries for each thread to place in a map |
| 45 |
// Should be > ConcurrentHashMap.TREEIFY_THRESHOLD but small |
| 46 |
// enough to allow for enough iteration overlap by multiple threads |
| 47 |
private static final int N = Integer.getInteger("n", 16); |
| 48 |
// The number of rounds each thread performs per entry |
| 49 |
private static final int R = Integer.getInteger("r", 32); |
| 50 |
// The number of iterations of the test |
| 51 |
private static final int I = Integer.getInteger("i", 256); |
| 52 |
|
| 53 |
// Object to be placed in the concurrent map |
| 54 |
static class X implements Comparable<X> { |
| 55 |
|
| 56 |
private final int a; |
| 57 |
|
| 58 |
X(int a) { |
| 59 |
this.a = a; |
| 60 |
} |
| 61 |
|
| 62 |
public int compareTo(X o) { |
| 63 |
return this.a - o.a; |
| 64 |
} |
| 65 |
|
| 66 |
public int hashCode() { |
| 67 |
// Return the same hash code to guarantee collisions |
| 68 |
return 0; |
| 69 |
} |
| 70 |
} |
| 71 |
|
| 72 |
@Test |
| 73 |
public void testContainsKey() { |
| 74 |
X[] content = IntStream.range(0, N).mapToObj(i -> new X(i)).toArray(X[]::new); |
| 75 |
// Create map with an initial size >= ConcurrentHashMap.TREEIFY_THRESHOLD |
| 76 |
// ensuring tree'ification will occur for a small number of entries |
| 77 |
// with the same hash code |
| 78 |
ConcurrentHashMap<Object, Object> m = new ConcurrentHashMap<>(64); |
| 79 |
Stream.of(content).forEach(x -> m.put(x, x)); |
| 80 |
test(content, m); |
| 81 |
} |
| 82 |
|
| 83 |
private static void test(X[] content, ConcurrentHashMap<Object, Object> m) { |
| 84 |
for (int i = 0; i < I; i++) { |
| 85 |
testOnce(content, m); |
| 86 |
} |
| 87 |
} |
| 88 |
|
| 89 |
static class AssociationFailure extends RuntimeException { |
| 90 |
AssociationFailure(String message) { |
| 91 |
super(message); |
| 92 |
} |
| 93 |
} |
| 94 |
|
| 95 |
private static void testOnce(Object[] content, ConcurrentHashMap<Object, Object> m) { |
| 96 |
CountDownLatch s = new CountDownLatch(1); |
| 97 |
|
| 98 |
Supplier<Runnable> sr = () -> () -> { |
| 99 |
try { |
| 100 |
s.await(); |
| 101 |
} |
| 102 |
catch (InterruptedException e) { |
| 103 |
} |
| 104 |
|
| 105 |
for (int i = 0; i < R * N; i++) { |
| 106 |
Object o = content[i % content.length]; |
| 107 |
if (!m.containsKey(o)) { |
| 108 |
throw new AssociationFailure("CHM.containsKey failed: entry does not exist"); |
| 109 |
} |
| 110 |
} |
| 111 |
}; |
| 112 |
|
| 113 |
int ps = Runtime.getRuntime().availableProcessors(); |
| 114 |
Stream<CompletableFuture> runners = IntStream.range(0, ps) |
| 115 |
.mapToObj(i -> sr.get()) |
| 116 |
.map(CompletableFuture::runAsync); |
| 117 |
|
| 118 |
CompletableFuture all = CompletableFuture.allOf( |
| 119 |
runners.toArray(CompletableFuture[]::new)); |
| 120 |
|
| 121 |
// Trigger the runners to start checking key membership |
| 122 |
s.countDown(); |
| 123 |
try { |
| 124 |
all.join(); |
| 125 |
} |
| 126 |
catch (CompletionException e) { |
| 127 |
Throwable t = e.getCause(); |
| 128 |
if (t instanceof AssociationFailure) { |
| 129 |
throw (AssociationFailure) t; |
| 130 |
} |
| 131 |
else { |
| 132 |
throw e; |
| 133 |
} |
| 134 |
} |
| 135 |
} |
| 136 |
} |
