| // Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| /// A basic LRU Cache. |
| class LruCache<K, V> { |
| _Link<K, V> _head; |
| _Link<K, V> _tail; |
| |
| final int Function(V) _computeWeight; |
| |
| int _currentWeightTotal = 0; |
| final int _individualWeightMax; |
| final int _totalWeightMax; |
| |
| final _entries = <K, _Link<K, V>>{}; |
| |
| LruCache( |
| this._individualWeightMax, this._totalWeightMax, this._computeWeight); |
| |
| V operator [](K key) { |
| var entry = _entries[key]; |
| if (entry == null) return null; |
| |
| _promote(entry); |
| return entry.value; |
| } |
| |
| void operator []=(K key, V value) { |
| var entry = _Link(key, value, _computeWeight(value)); |
| // Don't cache at all if above the individual weight max. |
| if (entry.weight > _individualWeightMax) { |
| return; |
| } |
| |
| _entries[key] = entry; |
| _currentWeightTotal += entry.weight; |
| _promote(entry); |
| |
| while (_currentWeightTotal > _totalWeightMax) { |
| assert(_tail != null); |
| remove(_tail.key); |
| } |
| } |
| |
| /// Removes the value at [key] from the cache, and returns the value if it |
| /// existed. |
| V remove(K key) { |
| var entry = _entries[key]; |
| if (entry == null) return null; |
| |
| _currentWeightTotal -= entry.weight; |
| _entries.remove(key); |
| |
| if (entry == _tail) { |
| _tail = entry.next; |
| _tail?.previous = null; |
| } |
| if (entry == _head) { |
| _head = entry.previous; |
| _head?.next = null; |
| } |
| |
| return entry.value; |
| } |
| |
| /// Moves [link] to the [_head] of the list. |
| void _promote(_Link<K, V> link) { |
| if (link == _head) return; |
| |
| if (link == _tail) { |
| _tail = link.next; |
| } |
| |
| if (link.previous != null) { |
| link.previous.next = link.next; |
| } |
| if (link.next != null) { |
| link.next.previous = link.previous; |
| } |
| |
| _head?.next = link; |
| link.previous = _head; |
| _head = link; |
| _tail ??= link; |
| link.next = null; |
| } |
| } |
| |
| /// A [MapEntry] which is also a part of a doubly linked list. |
| class _Link<K, V> implements MapEntry<K, V> { |
| _Link<K, V> next; |
| _Link<K, V> previous; |
| |
| final int weight; |
| |
| @override |
| final K key; |
| |
| @override |
| final V value; |
| |
| _Link(this.key, this.value, this.weight); |
| } |