LinkedLruHashMap: More bad internal state after calling remove

[hugovangalen]

I got the same crash as #385, "next called on null" from _removeLru. After verifying I was not accessing the list while it was getting updated, I found the culprit to again be caused by a bug in the remove method.

It appears to, somehow, do with the order in which the items have been added, and in which they are removed that reveals there are cases not caught correctly handled, that cause the doubly linked list to get corrupted with bad values and not releasing values that should be garbage collected, slowly eating up memory.

This is the fixed remove method:

@override
V remove(Object key) {
    final entry = _entries.remove(key);

    if (entry != null) {
      if (entry == _head && entry == _tail) {
        _head = _tail = null;
      } else if (entry == _head) {
        _head = _head.next;
        _head.previous = null; // don't dangle this one
      } else if (entry == _tail) {
        _tail.previous.next = null;
        _tail = _tail.previous;
      } else {
        // also point next to previous:
        entry.next.previous = entry.previous;
        entry.previous.next = entry.
      }
      return entry.value;
    }
    return null;
  }

Code to reproduce the problem:

List<String> testIds = <String>[
    "1",
    "2",
    "3",
    "4",
    "5",
    "6"
];

void main() {
    LinkedLruHashMap<String,Object> testData = new LinkedLruHashMap<String,Object>();
    for(String test in testIds) {
        testData.addAll( { test: { "debug": test } } );
    }
    
    testData.remove( "4" );
    testData.remove( "3" );
    testData.remove( "5" );
    testData.remove( "2" );
    testData.remove( "1" );
    
    print( "Remaining keys should be (6): ${testData.keys}" );    
    
    print( "Keys: " );
    for(String test in testData.keys) {
        print( "- $test, value is ${testData[test]}" );
    }
}

[adamlofts]

There should be an extra line here https://github.com/google/quiver-dart/blob/master/lib/src/collection/lru_map.dart#L242 like:

entry.next.previous = entry.previous.

I don't have the dev sdk installed so cannot create a PR right now.

[cbracken]

Fixed by #429. Thanks for taking a look @adamlofts -- also landed a couple other preventative fixes that should very very marginally help GC and future-proof a little.