[12]RFR 8205399 : Set node color on pinned HashMap.TreeNode deletion (original) (raw)

Brent Christian brent.christian at oracle.com
Wed Aug 8 20:57:35 UTC 2018

Thank you for the review, Martin. Good suggestions, thanks.

-Brent

On 08/08/2018 01:23 PM, Martin Buchholz wrote:

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 ? + @Override public int compareTo(Object k) { + return this.hash - ((Key)k).hash; + } Buggy - use Integer.compare instead. https://download.java.net/java/earlyaccess/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 <mailto:brent.christian at oracle.com>> wrote: Hi, Please review the following fix. Bug: https://bugs.openjdk.java.net/browse/JDK-8205399 <https://bugs.openjdk.java.net/browse/JDK-8205399> Webrev: http://cr.openjdk.java.net/~bchristi/8205399/webrev01/ <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