| | | 1 | | using System.Collections.Generic; |
| | | 2 | | |
| | | 3 | | namespace Itinero.Profiles.EdgeTypesMap; |
| | | 4 | | |
| | | 5 | | internal class LruCache<K, V> |
| | | 6 | | { |
| | | 7 | | private readonly Dictionary<K, LinkedListNode<LruCacheItem<K, V>>> _cacheMap = new(); |
| | | 8 | | private readonly int _capacity; |
| | | 9 | | private readonly LinkedList<LruCacheItem<K, V>> _lruList = new(); |
| | | 10 | | |
| | | 11 | | public LruCache(int capacity) |
| | | 12 | | { |
| | | 13 | | _capacity = capacity; |
| | | 14 | | } |
| | | 15 | | |
| | | 16 | | public bool TryGet(K key, out V? value) |
| | | 17 | | { |
| | | 18 | | LinkedListNode<LruCacheItem<K, V>> node; |
| | | 19 | | if (!_cacheMap.TryGetValue(key, out node)) |
| | | 20 | | { |
| | | 21 | | value = default; |
| | | 22 | | return false; |
| | | 23 | | } |
| | | 24 | | |
| | | 25 | | value = node.Value.value; |
| | | 26 | | _lruList.Remove(node); |
| | | 27 | | _lruList.AddLast(node); |
| | | 28 | | return true; |
| | | 29 | | } |
| | | 30 | | |
| | | 31 | | public void Add(K key, V val) |
| | | 32 | | { |
| | | 33 | | if (_cacheMap.Count >= _capacity) |
| | | 34 | | { |
| | | 35 | | this.RemoveFirst(); |
| | | 36 | | } |
| | | 37 | | |
| | | 38 | | LruCacheItem<K, V> cacheItem = new(key, val); |
| | | 39 | | LinkedListNode<LruCacheItem<K, V>> node = new(cacheItem); |
| | | 40 | | _lruList.AddLast(node); |
| | | 41 | | _cacheMap.Add(key, node); |
| | | 42 | | } |
| | | 43 | | |
| | | 44 | | private void RemoveFirst() |
| | | 45 | | { |
| | | 46 | | // Remove from LRUPriority |
| | | 47 | | LinkedListNode<LruCacheItem<K, V>> node = _lruList.First; |
| | | 48 | | _lruList.RemoveFirst(); |
| | | 49 | | |
| | | 50 | | // Remove from cache |
| | | 51 | | _cacheMap.Remove(node.Value.key); |
| | | 52 | | } |
| | | 53 | | |
| | | 54 | | public int Count => _cacheMap.Count; |
| | | 55 | | } |
| | | 56 | | |
| | | 57 | | internal class LruCacheItem<K, V> |
| | | 58 | | { |
| | | 59 | | public K key; |
| | | 60 | | public V value; |
| | | 61 | | |
| | 0 | 62 | | public LruCacheItem(K k, V v) |
| | 0 | 63 | | { |
| | 0 | 64 | | key = k; |
| | 0 | 65 | | value = v; |
| | 0 | 66 | | } |
| | | 67 | | } |