Search code examples
javaclr

/*From CLR*/ in Java TreeMap implementation


I was looking Java's (JDK 1.6_45) TreeMap code to understand a problem I was having and on few methods I saw a comment saying /** From CLR */.

I was under the impression that CLR is Microsoft terminology for its common runtime. Is CLR terminology used for Java as well? If not, then is there a common agreement to use each others implementation (after converting of-course) or is it just some auto generated comment?

Example

/** From CLR */
    private void fixAfterInsertion(Entry<K,V> x) {

Solution

  • It looks like Java's TreeMap "borrowed" part of its implementation from JabberNet's Tree, which is written in C# — here the full C# source code.

    Most probably one of the authors of the Java's TreeMap included the comment to reflect this fact (so "CLR" in the comment indeed means "Common Language Runtime").

    Here a snippet from Java's TreeMap:

    /** From CLR */
    private void fixAfterDeletion(Entry<K,V> x) {
        while (x != root && colorOf(x) == BLACK) {
            if (x == leftOf(parentOf(x))) {
                Entry<K,V> sib = rightOf(parentOf(x));
    
                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }
    
                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                ...
    

    And here the corresponding snippet from the JabberNet C# code:

    private void fixAfterDeletion(Node x)
    {
        while ((x != root) && (colorOf(x) == NodeColor.BLACK))
        {
            if (x == leftOf(parentOf(x)))
            {
                Node sib = rightOf(parentOf(x));
    
                if (colorOf(sib) == NodeColor.RED)
                {
                    setColor(sib, NodeColor.BLACK);
                    setColor(parentOf(x), NodeColor.RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }
    
                if ((colorOf(leftOf(sib))  == NodeColor.BLACK) &&
                    (colorOf(rightOf(sib)) == NodeColor.BLACK))
                ... 
    

    As you can see, the code is almost identical — except for indentation, node class name and syntax differences.

    This is also true for other methods marked as /** From CLR */.

    However, the Java code does not seem to be fully auto-generated from the C# code, cf. this comment in the Java code:

    /**
     * Balancing operations.
     *
     * Implementations of rebalancings during insertion and deletion are
     * slightly different than the CLR version.  Rather than using dummy
     * nilnodes, we use a set of accessors that deal properly with null.  They
     * are used to avoid messiness surrounding nullness checks in the main
     * algorithms.
     */