RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Jeff Hain]

Hello.



Implementing some RB-tree I found out that

a lot of the null checks from CLR code
could be removed from balancing operations.



Looking at TreeBin
(http://cr.openjdk.java.net/~bchristi/8005698/webrev.01/)
I found some places where such checks could also be removed.


In putTreeNode(...) (see comments):
        if (x == xp.right) {
            rotateLeft(x = xp);
            // Rotation adds a parent,
            // and xpp was not null, so the new xpp
            // is not null either (even though we
            // did x = xp).
            //xpp = (xp = x.parent) == null ? null :
 xp.parent;
            xpp = (xp = x.parent).parent;
        }
        //if (xp != null) {
            xp.red = false;
            //if (xpp != null) {
                xpp.red = true;
                rotateRight(xpp);
            //}
        //}
(...)
        if (x == xp.left) {
            rotateRight(x = xp);
            // Rotation adds a parent,
            // and xp was not null, so the new xp
            // is not null either (even though we
            // did x = xp).
            //xpp = (xp = x.parent) == null ? null : xp.parent;
            xpp = (xp = x.parent).parent;
       
 }
        //if (xp != null) {
            xp.red = false;
            if (xpp != null) {
                xpp.red = true;
                rotateLeft(xpp);
            }
        //}
(...)

        // p is not null so root is not null.
        //if (r != null && r.red)
 {
        if (r.red) {
            r.red = false;
        }


Similar rotation-related simplifications
could be done in deleteTreeNode(...).



Doing a lot of random add/remove calls (for integers
in bounded ranges, for removes to actually work
not too rarely),
it seemed that null checks could actually be removed
for all remaining calls to leftOf/rightOf/setColor
(not for getColor), but since I didn't figure out why
I didn't  touch these.


-Jeff