Это мертвый код в LinkedHashMap в JDK11？ - PullRequest
Новая
       74

Это мертвый код в LinkedHashMap в JDK11？

15 голосов
/ 06 мая 2020

Я читаю исходный код LinkedHashMap в JDK 11 и обнаружил кусок мертвого кода (я не уверен)

Как мы все знаем, LinkedHashMap использует двусвязный список, чтобы сохранить порядок всех У него есть член с именем accessOrder

final boolean accessOrder;

По умолчанию он равен false, но если он установлен в true, каждый раз, когда вы запускаете get, он перемещает элемент, который он получает, в конец связанного списка. Это то, что делает функция afterNodeAccess. 

//if accessOrder were set as true, after you visit node e, if e is not the end node of the linked list,
//it will move the node to the end of the linkedlist. 
    void afterNodeAccess(Node<K, V> e) {
        LinkedHashMap.Entry<K, V> last;

        if(accessOrder && (last = tail) != e) {

            //if enter `if` ，it indicates that e is not the end of the linked list, because (last=tail!=e)
            //then `a` as the after node of p(p is e after casting to LinkedHashMap.Entry) is never gonna be null. Only if p is last node of the linked list then a will be null.
            LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after;

            p.after = null;

            if(b == null) {
                head = a;
            } else {
                b.after = a;
            }

            // Is the if else clasue redundant? `a` must not be null.. the else clase will never be excuted.
            if(a != null) {
                a.before = b;
            } else {
                last = b;
            }

            if(last == null) {
                head = p;
            } else {
                p.before = last;
                last.after = p;
            }

            tail = p;

            ++modCount;
        }
    }

Итак, вот моя проблема:

(accessOrder && (last = tail) != e означает, что e не является последним узлом связанного список. Если e уже является последним узлом, нам не нужно ничего делать, правильно?

Тогда a в качестве узла после p (p является e после преобразования в LinkedHashMap.Entry), он не может быть нулевым. Только если p - последний узел, тогда a может быть нулевым.

Так в чем же смысл следующего фрагмента кода? 

 // Is the if else clasue redundant? `a` must not be null.. the else clase will never be excuted.
            if(a != null) {
                a.before = b;
            } else {
                last = b;
            }

a всегда != null, предложение else last = b никогда не будет выполнено .... это мертвый код?

Также я провожу эксперимент с accessorder, установленным как true, затем я get последний узел в режиме отладки, и кажется, что я не могу никогда не попасть в вышеуказанное caluse last = b

Есть предложения?

1 Ответ

3 голосов
/ 21 мая 2020

Код, представленный в OP, представляет собой алгоритм удаления узла для одинарного связанного списка, который устанавливает удаленный узел в качестве хвоста списка (перемещение в хвост): 

        LinkedHashMap.Entry<K, V> current = (LinkedHashMap.Entry<K, V>) e
        LinkedHashMap.Entry<K, V> pred = current.before, succ = current.after;

        current.after = null;

        // position the successor of the removed node correctly 
        // (either as the head of the list or as the successor of the node BEFORE the removed node)
        if(pred == null) {
            head = succ;
        } else {
            pred.after = succ ;
        }

        // position the predecessor of the removed node correctly
        // (either as the tail of the list or as the predecessor of the node AFTER the removed node)
        if(succ != null) {
            succ.before = pred;
        } else { // unreachable for non tail nodes
            last = pred;
        }

        // final step - if the predecessor of the removed node was null then the head
        // of the list is the removed node (the list contains a single node).
        // otherwise update the removed node as the tail of the list -
        // its predecessor will be the previous tail of the list
        if(last == null) { // unreachable for non tail nodes
            head = current;
        } else { 
            current.before = last;
            last.after = current;
        }

        tail = current;

Этот алгоритм обрабатывает все возможные случаи с учетом узла, который должен быть перемещен в качестве хвоста связанного случая.

В контексте метода afterNodeAccess в общем алгоритме случая будет некоторая избыточность, поскольку перемещенный узел никогда не будет в конце списка благодаря (last = tail) != e. Следовательно, более эффективный алгоритм будет: 

        current.after = null;
        // position the successor of the removed node correctly 
        // (either as the head of the list or as the successor of the node BEFORE the removed node)
        if(pred == null) {
            head = succ;
        } else {
            pred.after = succ ;
        }

        // position the predecessor of the removed node correctly
        // (as the predecessor of the node AFTER the removed node)
        // update the removed node as the tail of the list -
        // its predecessor will be the previous tail of the list
        succ.before = pred;
        current.before = last;
        last.after = current;
        tail = current;

Как holger , упомянутый в комментариях - это классическое c решение «копировать-вставить», которое, IMHO, показывает, что повторное использование кода в некоторых случаях может показаться неэффективным и непонятным.

Как предложил Йоханнес Кун , вы можете рассмотреть возможность отправки исправления недоступного кода сообществу OpenJDK. См. Ссылки на то, как это можно сделать.

Ссылки:

...