RFR 8023463 Update HashMap and LinkedHashMap to use bins/buckets or trees (red/black)

[Paul Sandoz]

I updated the webrev and replaced TreeBinSplitBackToEntries.java with:

  http://cr.openjdk.java.net/~psandoz/tl/JDK-8023463-Linked-HashMap-bin-and-tree/webrev/test/java/util/Map/MapBinToFromTreeTest.java.html

Paul.

On Aug 21, 2013, at 4:00 PM, Paul Sandoz <Paul.Sandoz at oracle.com> wrote:

> I updated the webrev to adjust some tests that a JPRT run reporting as failing:
> 
> FAILED: java/util/Map/CheckRandomHashSeed.java
> FAILED: java/util/Map/TreeBinSplitBackToEntries.java
> 
> The test TreeBinSplitBackToEntries needs to be revamped as the conditions under which bins are converted to trees and vice versa are no longer hold.
> 
> Conversion from a bin to a tree will not happen unless the table size is >= 64 (MIN_TREEIFY_CAPACITY) and the number of entries in a bin before adding is >= 7 (TREEIFY_THRESHOLD - 1). 
> 
> Conversion back from a tree to a bin occurs if the number of entries in a tree is <= 6 (UNTREEIFY_THRESHOLD), which AFAICT can occur when the table is resized, but can also occur under remove when the tree size is somewhere between 2 and 6. So we should try and create some tests to trigger this conversion too.
> 
> Plus tests for traversal when it is known the table contains trees (it is tempting, for convenience, to add instances to Spliterator traversing tests but that is probably overkill)
> 
> Paul.
> 
> On Aug 21, 2013, at 2:25 PM, Paul Sandoz <Paul.Sandoz at oracle.com> wrote:
> 
>> Hi,
>> 
>> Here are Doug's Linked/HashMap changes, discussed in a previous thread, as a webrev:
>> 
>> http://cr.openjdk.java.net/~psandoz/tl/JDK-8023463-Linked-HashMap-bin-and-tree/webrev/
>> 
>> I also added some tests related to characteristics associated with fixing another bug.
>> 
>> Looking at the diffs will be tricky given there are so many changes.
>> 
>> 
>> I fixed unchecked warnings in LinkedHashMap, but have not done so for HashMap, where there are many more casts from Node to TreeNode. One way to solve that is with a static method:
>> 
>>   @SuppressWarnings("unchecked")
>>   static <K, V> TreeNode<K, V> asTreeNode(Node<K, V> n) {
>>       return (TreeNode<K, V>) n;
>>   }
>> 
>> but i dunno what the performance implications are. Perhaps it's best to simply stuff @SuppressWarnings on methods of TreeNode rather than trying to modify code just for the sake of reducing the scope.
>> 
>> 
>> A JPRT job has been kicked off.
>> 
>> I recommend when this code goes in we look closely at code coverage results to see if we are missing areas testing tree functionality and update/add new tests accordingly.
>> 
>> Paul.
>> 
>