Issue
I am reading LinkedHashMap source code in JDK 11 and I found a piece of dead code(I'm not sure)
As we all know, LinkedHashMap use a doubly linked list to preserve the order of all the elements.It has a member called accessOrder
final boolean accessOrder;
By default it is false, but if it is set to true, everytime you run get, it will move the element it gets to the end of the linked list.That is what the function afterNodeAccess do.
//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;
}
}
So here comes my problem:
(accessOrder && (last = tail) != e means e is not the last node of the linked list. If e is already the last node, we dont have to do anything right?
Then a as the after node of p, (p is e after casting to LinkedHashMap.Entry), it cant be null. Only if p is the last node then a can be null.
So what's the point of the following piece of code?
// 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 always != null , the else clause last = b will never be executed....So is it dead code?
Also I do an experiment with accessorder set as true, then I get the last node in debug mode and it seems that I can't never get into the above else caluse last = b
Any suggestions?
Solution
The code provided in the OP is a node removal algorithm for a single linked list, which sets the removed node as the tail of the list (reposition to the tail):
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;
This algorithm handles all possible cases given a node that should be repositioned as the tail of the linked case.
In the context of the afterNodeAccess method, there will be some redundancy in the general case algorithm since the repositioned node is never at the tail of the list thanks to (last = tail) != e. Therefore, a more efficient algorithm would be:
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;
As holger mentioned in the comments - this is a classic 'copy-paste' solution which IMHO shows that reusing code in some cases can seem to be inefficient and unclear.
As suggested by Johannes Kuhn, you can consider submitting a fix for the unreachable code to the OpenJDK community. See the references on how this can be done.
References:
Answered By - Rann Lifshitz
Answer Checked By - Senaida (JavaFixing Volunteer)
