| | | 1 | | // Licensed to the .NET Foundation under one or more agreements. |
| | | 2 | | // The .NET Foundation licenses this file to you under the MIT license. |
| | | 3 | | |
| | | 4 | | using System.Collections.Generic; |
| | | 5 | | using CoreWCF.Runtime; |
| | | 6 | | |
| | | 7 | | namespace CoreWCF.Collections.Generic |
| | | 8 | | { |
| | | 9 | | internal class MruCache<TKey, TValue> |
| | | 10 | | where TKey : class |
| | | 11 | | where TValue : class |
| | | 12 | | { |
| | | 13 | | private readonly LinkedList<TKey> _mruList; |
| | | 14 | | private readonly Dictionary<TKey, CacheEntry> _items; |
| | | 15 | | private readonly int _lowWatermark; |
| | | 16 | | private readonly int _highWatermark; |
| | | 17 | | private CacheEntry _mruEntry; |
| | | 18 | | |
| | | 19 | | public MruCache(int watermark) |
| | 0 | 20 | | : this(watermark * 4 / 5, watermark) |
| | | 21 | | { |
| | 0 | 22 | | } |
| | | 23 | | |
| | | 24 | | // |
| | | 25 | | // The cache will grow until the high watermark. At which point, the least recently used items |
| | | 26 | | // will be purge until the cache's size is reduced to low watermark |
| | | 27 | | // |
| | | 28 | | public MruCache(int lowWatermark, int highWatermark) |
| | 0 | 29 | | : this(lowWatermark, highWatermark, null) |
| | | 30 | | { |
| | 0 | 31 | | } |
| | | 32 | | |
| | 0 | 33 | | public MruCache(int lowWatermark, int highWatermark, IEqualityComparer<TKey> comparer) |
| | | 34 | | { |
| | | 35 | | Fx.Assert(lowWatermark < highWatermark, ""); |
| | | 36 | | Fx.Assert(lowWatermark >= 0, ""); |
| | | 37 | | |
| | 0 | 38 | | _lowWatermark = lowWatermark; |
| | 0 | 39 | | _highWatermark = highWatermark; |
| | 0 | 40 | | _mruList = new LinkedList<TKey>(); |
| | 0 | 41 | | if (comparer == null) |
| | | 42 | | { |
| | 0 | 43 | | _items = new Dictionary<TKey, CacheEntry>(); |
| | | 44 | | } |
| | | 45 | | else |
| | | 46 | | { |
| | 0 | 47 | | _items = new Dictionary<TKey, CacheEntry>(comparer); |
| | | 48 | | } |
| | 0 | 49 | | } |
| | | 50 | | |
| | | 51 | | public int Count |
| | | 52 | | { |
| | | 53 | | get |
| | | 54 | | { |
| | 0 | 55 | | return _items.Count; |
| | | 56 | | } |
| | | 57 | | } |
| | | 58 | | |
| | | 59 | | public void Add(TKey key, TValue value) |
| | | 60 | | { |
| | | 61 | | Fx.Assert(null != key, ""); |
| | | 62 | | |
| | | 63 | | // if anything goes wrong (duplicate entry, etc) we should |
| | | 64 | | // clear our caches so that we don't get out of sync |
| | 0 | 65 | | bool success = false; |
| | | 66 | | try |
| | | 67 | | { |
| | 0 | 68 | | if (_items.Count == _highWatermark) |
| | | 69 | | { |
| | | 70 | | // If the cache is full, purge enough LRU items to shrink the |
| | | 71 | | // cache down to the low watermark |
| | 0 | 72 | | int countToPurge = _highWatermark - _lowWatermark; |
| | 0 | 73 | | for (int i = 0; i < countToPurge; i++) |
| | | 74 | | { |
| | 0 | 75 | | TKey keyRemove = _mruList.Last.Value; |
| | 0 | 76 | | _mruList.RemoveLast(); |
| | 0 | 77 | | TValue item = _items[keyRemove].value; |
| | 0 | 78 | | _items.Remove(keyRemove); |
| | 0 | 79 | | OnSingleItemRemoved(item); |
| | 0 | 80 | | OnItemAgedOutOfCache(item); |
| | | 81 | | } |
| | | 82 | | } |
| | | 83 | | // Add the new entry to the cache and make it the MRU element |
| | | 84 | | CacheEntry entry; |
| | 0 | 85 | | entry.node = _mruList.AddFirst(key); |
| | 0 | 86 | | entry.value = value; |
| | 0 | 87 | | _items.Add(key, entry); |
| | 0 | 88 | | _mruEntry = entry; |
| | 0 | 89 | | success = true; |
| | 0 | 90 | | } |
| | | 91 | | finally |
| | | 92 | | { |
| | 0 | 93 | | if (!success) |
| | | 94 | | { |
| | 0 | 95 | | Clear(); |
| | | 96 | | } |
| | 0 | 97 | | } |
| | 0 | 98 | | } |
| | | 99 | | |
| | | 100 | | public void Clear() |
| | | 101 | | { |
| | 0 | 102 | | _mruList.Clear(); |
| | 0 | 103 | | _items.Clear(); |
| | 0 | 104 | | _mruEntry.value = null; |
| | 0 | 105 | | _mruEntry.node = null; |
| | 0 | 106 | | } |
| | | 107 | | |
| | | 108 | | public bool Remove(TKey key) |
| | | 109 | | { |
| | | 110 | | Fx.Assert(null != key, ""); |
| | | 111 | | |
| | 0 | 112 | | if (_items.TryGetValue(key, out CacheEntry entry)) |
| | | 113 | | { |
| | 0 | 114 | | _items.Remove(key); |
| | 0 | 115 | | OnSingleItemRemoved(entry.value); |
| | 0 | 116 | | _mruList.Remove(entry.node); |
| | 0 | 117 | | if (ReferenceEquals(_mruEntry.node, entry.node)) |
| | | 118 | | { |
| | 0 | 119 | | _mruEntry.value = null; |
| | 0 | 120 | | _mruEntry.node = null; |
| | | 121 | | } |
| | 0 | 122 | | return true; |
| | | 123 | | } |
| | | 124 | | |
| | 0 | 125 | | return false; |
| | | 126 | | } |
| | | 127 | | |
| | | 128 | | protected virtual void OnSingleItemRemoved(TValue item) |
| | | 129 | | { |
| | 0 | 130 | | } |
| | | 131 | | |
| | | 132 | | protected virtual void OnItemAgedOutOfCache(TValue item) |
| | | 133 | | { |
| | 0 | 134 | | } |
| | | 135 | | |
| | | 136 | | // |
| | | 137 | | // If found, make the entry most recently used |
| | | 138 | | // |
| | | 139 | | public bool TryGetValue(TKey key, out TValue value) |
| | | 140 | | { |
| | | 141 | | // first check our MRU item |
| | 0 | 142 | | if (_mruEntry.node != null && key != null && key.Equals(_mruEntry.node.Value)) |
| | | 143 | | { |
| | 0 | 144 | | value = _mruEntry.value; |
| | 0 | 145 | | return true; |
| | | 146 | | } |
| | | 147 | | |
| | | 148 | | |
| | 0 | 149 | | bool found = _items.TryGetValue(key, out CacheEntry entry); |
| | 0 | 150 | | value = entry.value; |
| | | 151 | | |
| | | 152 | | // Move the node to the head of the MRU list if it's not already there |
| | 0 | 153 | | if (found && _mruList.Count > 1 |
| | 0 | 154 | | && !ReferenceEquals(_mruList.First, entry.node)) |
| | | 155 | | { |
| | 0 | 156 | | _mruList.Remove(entry.node); |
| | 0 | 157 | | _mruList.AddFirst(entry.node); |
| | 0 | 158 | | _mruEntry = entry; |
| | | 159 | | } |
| | | 160 | | |
| | 0 | 161 | | return found; |
| | | 162 | | } |
| | | 163 | | |
| | | 164 | | private struct CacheEntry |
| | | 165 | | { |
| | | 166 | | internal TValue value; |
| | | 167 | | internal LinkedListNode<TKey> node; |
| | | 168 | | } |
| | | 169 | | } |
| | | 170 | | } |