Method putImpl

vm/JavaAPI/src/java/util/TreeMap.java:4413–4625

(K key, V value)

    }
    
    private V putImpl(K key, V value) {
        if (root == null) {
            root = createNode(key, value);
            size = 1;
            modCount++;
            return null;
        }    
        java.lang.Comparable<K> object = comparator == null ? toComparable((K) key)
                : null;
        K keyK = (K) key;
        Node<K, V> node = root;
        Node<K, V> prevNode = null;
        int result = 0;
        while (node != null) {
            prevNode = node;
            K[] keys = node.keys;
            int left_idx = node.left_idx;
            result = cmp(object, keyK, keys[left_idx]);
            if (result < 0) {
                node = node.left;
            } else if (result == 0) {
                V res = node.values[left_idx];
                node.values[left_idx] = value;
                return res;
            } else {
                int right_idx = node.right_idx;
                if (left_idx != right_idx) {
                    result = cmp(object, keyK, keys[right_idx]);
                }
                if (result > 0) {
                    node = node.right;
                } else if (result == 0) {
                    V res = node.values[right_idx];
                    node.values[right_idx] = value;
                    return res;
                } else { /* search in node */
                    int low = left_idx + 1, mid = 0, high = right_idx - 1;
                    while (low <= high) {
                        mid = (low + high) >>> 1;
                        result = cmp(object, keyK, keys[mid]);
                        if (result > 0) {
                            low = mid + 1;
                        } else if (result == 0) {
                            V res = node.values[mid];
                            node.values[mid] = value;
                            return res;
                        } else {
                            high = mid - 1;
                        }
                    }
                    result = low;
                    break;
                }
            }
        } /* while */
        /*
         * if(node == null) { if(prevNode==null) { - case of empty Tree } else {
         * result < 0 - prevNode.left==null - attach here result > 0 -