OLD | NEW |
1 // Copyright 2014 Google Inc. All Rights Reserved. | 1 // Copyright 2014 Google Inc. All Rights Reserved. |
2 // | 2 // |
3 // Licensed under the Apache License, Version 2.0 (the "License"); | 3 // Licensed under the Apache License, Version 2.0 (the "License"); |
4 // you may not use this file except in compliance with the License. | 4 // you may not use this file except in compliance with the License. |
5 // You may obtain a copy of the License at | 5 // You may obtain a copy of the License at |
6 // | 6 // |
7 // http://www.apache.org/licenses/LICENSE-2.0 | 7 // http://www.apache.org/licenses/LICENSE-2.0 |
8 // | 8 // |
9 // Unless required by applicable law or agreed to in writing, software | 9 // Unless required by applicable law or agreed to in writing, software |
10 // distributed under the License is distributed on an "AS IS" BASIS, | 10 // distributed under the License is distributed on an "AS IS" BASIS, |
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 // See the License for the specific language governing permissions and | 12 // See the License for the specific language governing permissions and |
13 // limitations under the License. | 13 // limitations under the License. |
14 | 14 |
15 part of quiver.collection; | 15 part of quiver.collection; |
16 | 16 |
17 /** | 17 /// An implementation of a [Map] which has a maximum size and uses a (Least |
18 * An implementation of a [Map] which has a maximum size and uses a (Least | 18 /// Recently Used)[http://en.wikipedia.org/wiki/Cache_algorithms#LRU] algorithm |
19 * Recently Used)[http://en.wikipedia.org/wiki/Cache_algorithms#LRU] algorithm | 19 /// to remove items from the [Map] when the [maximumSize] is reached and new |
20 * to remove items from the [Map] when the [maximumSize] is reached and new | 20 /// items are added. |
21 * items are added. | 21 /// |
22 * | 22 /// It is safe to access the [keys] and [values] collections without affecting |
23 * It is safe to access the [keys] and [values] collections without affecting | 23 /// the "used" ordering - as well as using [forEach]. Other types of access, |
24 * the "used" ordering - as well as using [forEach]. Other types of access, | 24 /// including bracket, and [putIfAbsent], promotes the key-value pair to the |
25 * including bracket, and [putIfAbsent], promotes the key-value pair to the MRU | 25 /// MRU position. |
26 * position. | |
27 */ | |
28 abstract class LruMap<K, V> implements Map<K, V> { | 26 abstract class LruMap<K, V> implements Map<K, V> { |
29 /** | 27 /// Creates a [LruMap] instance with the default implementation. |
30 * Creates a [LruMap] instance with the default implementation. | 28 factory LruMap({int maximumSize}) = LinkedLruHashMap<K, V>; |
31 */ | |
32 factory LruMap({int maximumSize}) = LinkedLruHashMap; | |
33 | 29 |
34 /** | 30 /// Maximum size of the [Map]. If [length] exceeds this value at any time, n |
35 * Maximum size of the [Map]. If [length] exceeds this value at any time, | 31 /// entries accessed the earliest are removed, where n is [length] - |
36 * n entries accessed the earliest are removed, where n is [length] - | 32 /// [maximumSize]. |
37 * [maximumSize]. | |
38 */ | |
39 int maximumSize; | 33 int maximumSize; |
40 } | 34 } |
41 | 35 |
42 /** | 36 /// Simple implementation of a linked-list entry that contains a [key] and |
43 * Simple implementation of a linked-list entry that contains a [key] and | 37 /// [value]. |
44 * [value]. | |
45 */ | |
46 class _LinkedEntry<K, V> { | 38 class _LinkedEntry<K, V> { |
47 K key; | 39 K key; |
48 V value; | 40 V value; |
49 | 41 |
50 _LinkedEntry<K, V> next; | 42 _LinkedEntry<K, V> next; |
51 _LinkedEntry<K, V> previous; | 43 _LinkedEntry<K, V> previous; |
52 | 44 |
53 _LinkedEntry([this.key, this.value]); | 45 _LinkedEntry([this.key, this.value]); |
54 } | 46 } |
55 | 47 |
56 /** | 48 /// A linked hash-table based implementation of [LruMap]. |
57 * A linked hash-table based implementation of [LruMap]. | |
58 */ | |
59 class LinkedLruHashMap<K, V> implements LruMap<K, V> { | 49 class LinkedLruHashMap<K, V> implements LruMap<K, V> { |
60 static const _DEFAULT_MAXIMUM_SIZE = 100; | 50 static const _DEFAULT_MAXIMUM_SIZE = 100; |
61 | 51 |
62 final Map<K, _LinkedEntry<K, V>> _entries; | 52 final Map<K, _LinkedEntry<K, V>> _entries; |
63 | 53 |
64 int _maximumSize; | 54 int _maximumSize; |
65 | 55 |
66 _LinkedEntry<K, V> _head; | 56 _LinkedEntry<K, V> _head; |
67 _LinkedEntry<K, V> _tail; | 57 _LinkedEntry<K, V> _tail; |
68 | 58 |
69 /** | 59 /// Create a new LinkedLruHashMap with a [maximumSize]. |
70 * Create a new LinkedLruHashMap with a [maximumSize]. | |
71 */ | |
72 factory LinkedLruHashMap({int maximumSize}) => | 60 factory LinkedLruHashMap({int maximumSize}) => |
73 new LinkedLruHashMap._fromMap(new HashMap<K, _LinkedEntry<K, V>>(), | 61 new LinkedLruHashMap._fromMap(new HashMap<K, _LinkedEntry<K, V>>(), |
74 maximumSize: maximumSize); | 62 maximumSize: maximumSize); |
75 | 63 |
76 LinkedLruHashMap._fromMap( | 64 LinkedLruHashMap._fromMap(this._entries, {int maximumSize}) |
77 this._entries, { | 65 // This pattern is used instead of a default value because we want to |
78 int maximumSize}) | 66 // be able to respect null values coming in from MapCache.lru. |
79 // This pattern is used instead of a default value because we want to | 67 : _maximumSize = firstNonNull(maximumSize, _DEFAULT_MAXIMUM_SIZE); |
80 // be able to respect null values coming in from MapCache.lru. | |
81 : _maximumSize = firstNonNull(maximumSize, _DEFAULT_MAXIMUM_SIZE); | |
82 | 68 |
83 /** | 69 /// Adds all key-value pairs of [other] to this map. |
84 * Adds all key-value pairs of [other] to this map. | 70 /// |
85 * | 71 /// The operation is equivalent to doing this[key] = value for each key and |
86 * The operation is equivalent to doing this[key] = value for each key and | 72 /// associated value in other. It iterates over other, which must therefore |
87 * associated value in other. It iterates over other, which must therefore not | 73 /// not change during the iteration. |
88 * change during the iteration. | 74 /// |
89 * | 75 /// If a key of [other] is already in this map, its value is overwritten. If |
90 * If a key of [other] is already in this map, its value is overwritten. If | 76 /// the number of unique keys is greater than [maximumSize] then the least |
91 * the number of unique keys is greater than [maximumSize] then the least | 77 /// recently use keys are evicted. For keys written to by [other], the least |
92 * recently use keys are evicted. For keys written to by [other], the least | 78 /// recently user order is determined by [other]'s iteration order. |
93 * recently user order is determined by [other]'s iteration order. | |
94 */ | |
95 @override | 79 @override |
96 void addAll(Map<K, V> other) => other.forEach((k, v) => this[k] = v); | 80 void addAll(Map<K, V> other) => other.forEach((k, v) => this[k] = v); |
97 | 81 |
98 @override | 82 @override |
99 void clear() { | 83 void clear() { |
100 _entries.clear(); | 84 _entries.clear(); |
101 _head = _tail = null; | 85 _head = _tail = null; |
102 } | 86 } |
103 | 87 |
104 @override | 88 @override |
105 bool containsKey(K key) => _entries.containsKey(key); | 89 bool containsKey(Object key) => _entries.containsKey(key); |
106 | 90 |
107 @override | 91 @override |
108 bool containsValue(V value) => values.contains(value); | 92 bool containsValue(Object value) => values.contains(value); |
109 | 93 |
110 /** | 94 /// Applies [action] to each key-value pair of the map in order of MRU to |
111 * Applies [action] to each key-value pair of the map in order of MRU to LRU. | 95 /// LRU. |
112 * | 96 /// |
113 * Calling `action` must not add or remove keys from the map. | 97 /// Calling `action` must not add or remove keys from the map. |
114 */ | |
115 @override | 98 @override |
116 void forEach(void action(K key, V value)) { | 99 void forEach(void action(K key, V value)) { |
117 var head = _head; | 100 var head = _head; |
118 while (head != null) { | 101 while (head != null) { |
119 action(head.key, head.value); | 102 action(head.key, head.value); |
120 head = head.next; | 103 head = head.next; |
121 } | 104 } |
122 } | 105 } |
123 | 106 |
124 @override | 107 @override |
125 int get length => _entries.length; | 108 int get length => _entries.length; |
126 | 109 |
127 @override | 110 @override |
128 bool get isEmpty => _entries.isEmpty; | 111 bool get isEmpty => _entries.isEmpty; |
129 | 112 |
130 @override | 113 @override |
131 bool get isNotEmpty => _entries.isNotEmpty; | 114 bool get isNotEmpty => _entries.isNotEmpty; |
132 | 115 |
133 /** | 116 /// Creates an [Iterable] around the entries of the map. |
134 * Creates an [Iterable] around the entries of the map. | |
135 */ | |
136 Iterable<_LinkedEntry<K, V>> _iterable() { | 117 Iterable<_LinkedEntry<K, V>> _iterable() { |
137 return new GeneratingIterable<_LinkedEntry<K, V>>( | 118 return new GeneratingIterable<_LinkedEntry<K, V>>( |
138 () => _head, (n) => n.next); | 119 () => _head, (n) => n.next); |
139 } | 120 } |
140 | 121 |
141 /** | 122 /// The keys of [this] - in order of MRU to LRU. |
142 * The keys of [this] - in order of MRU to LRU. | 123 /// |
143 * | 124 /// The returned iterable does *not* have efficient `length` or `contains`. |
144 * The returned iterable does *not* have efficient `length` or `contains`. | |
145 */ | |
146 @override | 125 @override |
147 Iterable<K> get keys => _iterable().map((e) => e.key); | 126 Iterable<K> get keys => _iterable().map((e) => e.key); |
148 | 127 |
149 /** | 128 /// The values of [this] - in order of MRU to LRU. |
150 * The values of [this] - in order of MRU to LRU. | 129 /// |
151 * | 130 /// The returned iterable does *not* have efficient `length` or `contains`. |
152 * The returned iterable does *not* have efficient `length` or `contains`. | |
153 */ | |
154 @override | 131 @override |
155 Iterable<V> get values => _iterable().map((e) => e.value); | 132 Iterable<V> get values => _iterable().map((e) => e.value); |
156 | 133 |
157 @override | 134 @override |
158 int get maximumSize => _maximumSize; | 135 int get maximumSize => _maximumSize; |
159 | 136 |
160 @override | 137 @override |
161 void set maximumSize(int maximumSize) { | 138 void set maximumSize(int maximumSize) { |
162 if (maximumSize == null) throw new ArgumentError.notNull('maximumSize'); | 139 if (maximumSize == null) throw new ArgumentError.notNull('maximumSize'); |
163 while (length > maximumSize) { | 140 while (length > maximumSize) { |
164 _removeLru(); | 141 _removeLru(); |
165 } | 142 } |
166 _maximumSize = maximumSize; | 143 _maximumSize = maximumSize; |
167 } | 144 } |
168 | 145 |
169 /** | 146 /// Look up the value associated with [key], or add a new value if it isn't |
170 * Look up the value associated with [key], or add a new value if it isn't | 147 /// there. The pair is promoted to the MRU position. |
171 * there. The pair is promoted to the MRU position. | 148 /// |
172 * | 149 /// Otherwise calls [ifAbsent] to get a new value, associates [key] to that |
173 * Otherwise calls [ifAbsent] to get a new value, associates [key] to that | 150 /// [value], and then returns the new [value], with the key-value pair in the |
174 * [value], and then returns the new [value], with the key-value pair in the | 151 /// MRU position. If this causes [length] to exceed [maximumSize], then the |
175 * MRU position. If this causes [length] to exceed [maximumSize], then the | 152 /// LRU position is removed. |
176 * LRU position is removed. | |
177 */ | |
178 @override | 153 @override |
179 V putIfAbsent(K key, V ifAbsent()) { | 154 V putIfAbsent(K key, V ifAbsent()) { |
180 final entry = _entries.putIfAbsent( | 155 final entry = |
181 key, () => _createEntry(key, ifAbsent())); | 156 _entries.putIfAbsent(key, () => _createEntry(key, ifAbsent())); |
182 if (length > maximumSize) { | 157 if (length > maximumSize) { |
183 _removeLru(); | 158 _removeLru(); |
184 } | 159 } |
185 _promoteEntry(entry); | 160 _promoteEntry(entry); |
186 return entry.value; | 161 return entry.value; |
187 } | 162 } |
188 | 163 |
189 /** | 164 /// Get the value for a [key] in the [Map]. The [key] will be promoted to the |
190 * Get the value for a [key] in the [Map]. The [key] will be promoted to the | 165 /// 'Most Recently Used' position. *NOTE*: Calling [] inside an iteration |
191 * 'Most Recently Used' position. *NOTE*: Calling [] inside an iteration over | 166 /// over keys/values is currently unsupported; use [keys] or [values] if you |
192 * keys/values is currently unsupported; use [keys] or [values] if you | 167 /// need information about entries without modifying their position. |
193 * need information about entries without modifying their position. | |
194 */ | |
195 @override | 168 @override |
196 V operator[](K key) { | 169 V operator [](Object key) { |
197 final entry = _entries[key]; | 170 final entry = _entries[key]; |
198 if (entry != null) { | 171 if (entry != null) { |
199 _promoteEntry(entry); | 172 _promoteEntry(entry); |
200 return entry.value; | 173 return entry.value; |
201 } else { | 174 } else { |
202 return null; | 175 return null; |
203 } | 176 } |
204 } | 177 } |
205 | 178 |
206 /** | 179 /// If [key] already exists, promotes it to the MRU position & assigns |
207 * If [key] already exists, promotes it to the MRU position & assigns [value]. | 180 /// [value]. |
208 * | 181 /// |
209 * Otherwise, adds [key] and [value] to the MRU position. | 182 /// Otherwise, adds [key] and [value] to the MRU position. If [length] |
210 * If [length] exceeds [maximumSize] while adding, removes the LRU position. | 183 /// exceeds [maximumSize] while adding, removes the LRU position. |
211 */ | |
212 @override | 184 @override |
213 void operator []=(K key, V value) { | 185 void operator []=(K key, V value) { |
214 // Add this item to the MRU position. | 186 // Add this item to the MRU position. |
215 _insertMru(_createEntry(key, value)); | 187 _insertMru(_createEntry(key, value)); |
216 | 188 |
217 // Remove the LRU item if the size would be exceeded by adding this item. | 189 // Remove the LRU item if the size would be exceeded by adding this item. |
218 if (length > maximumSize) { | 190 if (length > maximumSize) { |
219 assert(length == maximumSize + 1); | 191 assert(length == maximumSize + 1); |
220 _removeLru(); | 192 _removeLru(); |
221 } | 193 } |
222 } | 194 } |
223 | 195 |
224 @override | 196 @override |
225 V remove(K key) { | 197 V remove(Object key) { |
226 final entry = _entries.remove(key); | 198 final entry = _entries.remove(key); |
227 if (entry != null) { | 199 if (entry != null) { |
228 if (entry == _head) { | 200 if (entry == _head) { |
229 _head = _head.next; | 201 _head = _head.next; |
230 } else if (entry == _tail) { | 202 } else if (entry == _tail) { |
231 _tail.previous.next = null; | 203 _tail.previous.next = null; |
232 _tail = _tail.previous; | 204 _tail = _tail.previous; |
233 } else { | 205 } else { |
234 entry.previous.next = entry.next; | 206 entry.previous.next = entry.next; |
235 } | 207 } |
236 return entry.value; | 208 return entry.value; |
237 } | 209 } |
238 return null; | 210 return null; |
239 } | 211 } |
240 | 212 |
241 @override | 213 @override |
242 String toString() => Maps.mapToString(this); | 214 String toString() => Maps.mapToString(this); |
243 | 215 |
244 /** | 216 /// Moves [entry] to the MRU position, shifting the linked list if necessary. |
245 * Moves [entry] to the MRU position, shifting the linked list if necessary. | |
246 */ | |
247 void _promoteEntry(_LinkedEntry<K, V> entry) { | 217 void _promoteEntry(_LinkedEntry<K, V> entry) { |
248 if (entry.previous != null) { | 218 if (entry.previous != null) { |
249 // If already existed in the map, link previous to next. | 219 // If already existed in the map, link previous to next. |
250 entry.previous.next = entry.next; | 220 entry.previous.next = entry.next; |
251 | 221 |
252 // If this was the tail element, assign a new tail. | 222 // If this was the tail element, assign a new tail. |
253 if (_tail == entry) { | 223 if (_tail == entry) { |
254 _tail = entry.previous; | 224 _tail = entry.previous; |
255 } | 225 } |
256 } | 226 } |
257 | 227 |
258 // Replace head with this element. | 228 // Replace head with this element. |
259 if (_head != null) { | 229 if (_head != null) { |
260 _head.previous = entry; | 230 _head.previous = entry; |
261 } | 231 } |
262 entry.previous = null; | 232 entry.previous = null; |
263 entry.next = _head; | 233 entry.next = _head; |
264 _head = entry; | 234 _head = entry; |
265 | 235 |
266 // Add a tail if this is the first element. | 236 // Add a tail if this is the first element. |
267 if (_tail == null) { | 237 if (_tail == null) { |
268 assert(length == 1); | 238 assert(length == 1); |
269 _tail = _head; | 239 _tail = _head; |
270 } | 240 } |
271 } | 241 } |
272 | 242 |
273 /** | 243 /// Creates and returns an entry from [key] and [value]. |
274 * Creates and returns an entry from [key] and [value]. | |
275 */ | |
276 _LinkedEntry<K, V> _createEntry(K key, V value) { | 244 _LinkedEntry<K, V> _createEntry(K key, V value) { |
277 return new _LinkedEntry<K, V>(key, value); | 245 return new _LinkedEntry<K, V>(key, value); |
278 } | 246 } |
279 | 247 |
280 /** | 248 /// If [entry] does not exist, inserts it into the backing map. If it does, |
281 * If [entry] does not exist, inserts it into the backing map. | 249 /// replaces the existing [_LinkedEntry.value] with [entry.value]. Then, in |
282 * If it does, replaces the existing [_LinkedEntry.value] with [entry.value]. | 250 /// either case, promotes [entry] to the MRU position. |
283 * Then, in either case, promotes [entry] to the MRU position. | |
284 */ | |
285 void _insertMru(_LinkedEntry<K, V> entry) { | 251 void _insertMru(_LinkedEntry<K, V> entry) { |
286 // Insert a new entry if necessary (only 1 hash lookup in entire function). | 252 // Insert a new entry if necessary (only 1 hash lookup in entire function). |
287 // Otherwise, just updates the existing value. | 253 // Otherwise, just updates the existing value. |
288 final value = entry.value; | 254 final value = entry.value; |
289 _promoteEntry(_entries.putIfAbsent(entry.key, () => entry)..value = value); | 255 _promoteEntry(_entries.putIfAbsent(entry.key, () => entry)..value = value); |
290 } | 256 } |
291 | 257 |
292 /** | 258 /// Removes the LRU position, shifting the linked list if necessary. |
293 * Removes the LRU position, shifting the linked list if necessary. | |
294 */ | |
295 void _removeLru() { | 259 void _removeLru() { |
296 // Remove the tail from the internal map. | 260 // Remove the tail from the internal map. |
297 _entries.remove(_tail.key); | 261 _entries.remove(_tail.key); |
298 | 262 |
299 // Remove the tail element itself. | 263 // Remove the tail element itself. |
300 _tail = _tail.previous; | 264 _tail = _tail.previous; |
301 _tail.next = null; | 265 _tail.next = null; |
302 } | 266 } |
303 } | 267 } |
OLD | NEW |