/
lru_cache.dart
107 lines (83 loc) · 2.32 KB
/
lru_cache.dart
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
// 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;
}
if (_entries.containsKey(key)) {
remove(key);
}
_entries[key] = entry;
_currentWeightTotal += entry.weight;
_promote(entry);
while (_currentWeightTotal > _totalWeightMax) {
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);
}