[12]RFR 8205399 : Set node color on pinned HashMap.TreeNode deletion

Martin Buchholz martinrb at google.com
Wed Aug 8 20:23:29 UTC 2018


Brent, thanks for writing a test.
I would probably not have bothered.  Or if I was ambitious, I might have
written a whitebox test against all the red-black tree implementations in
the core libs, verifying node color.

+        int hash;

final?

+    static class Key implements Comparable {

implements Comparable<Key> ?

+        @Override public int compareTo(Object k) {
+            return this.hash - ((Key)k).hash;
+        }

Buggy - use Integer.compare instead.
https://download.java.net/java/early_access/jdk12/docs/api/java.base/java/lang/Integer.html#compare(int,int)

Approved.


On Wed, Aug 8, 2018 at 11:57 AM, Brent Christian <brent.christian at oracle.com
> wrote:

> Hi,
>
> Please review the following fix.
>
> Bug: https://bugs.openjdk.java.net/browse/JDK-8205399
> Webrev: http://cr.openjdk.java.net/~bchristi/8205399/webrev01/
>
> The vmTestbase/vm/gc/containers/Combination05/TestDescription.java test,
> which does random adds and removes (via Iterator), has been failing
> intermittently with an AssertionError.
>
> I tracked down a couple sequences of operations that trigger the
> assertion.  Sufficient HashMap collisions convert a bin to a tree, and then
> values are deleted using Iterator.remove() (pinned node deletion).
>
> The condition that fails in HashMap.TreeNode.checkInvariants() is:
>
>   if (t.red && tl != null && tl.red && tr != null && tr.red)
>
> A red TreeNode should not have two red children.
>
> Many thanks to Doug Lea for providing the fix for the HashMap red/black
> tree code.  The root node color needs to be set in this case.
>
> Thanks,
> -Brent
>


More information about the core-libs-dev mailing list