1 // OpenTween - Client of Twitter
2 // Copyright (c) 2013 kim_upsilon (@kim_upsilon) <https://upsilo.net/~upsilon/>
3 // All rights reserved.
5 // This file is part of OpenTween.
7 // This program is free software; you can redistribute it and/or modify it
8 // under the terms of the GNU General Public License as published by the Free
9 // Software Foundation; either version 3 of the License, or (at your option)
12 // This program is distributed in the hope that it will be useful, but
13 // WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 // or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 // You should have received a copy of the GNU General Public License along
18 // with this program. If not, see <http://www.gnu.org/licenses/>, or write to
19 // the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
20 // Boston, MA 02110-1301, USA.
25 using System.Collections;
26 using System.Collections.Generic;
27 using System.Diagnostics.CodeAnalysis;
34 /// LRU によるキャッシュを行うための辞書クラス
36 public class LRUCacheDictionary<TKey, TValue> : IDictionary<TKey, TValue>
42 /// TrimLimit を上回る個数のアイテムが格納されている場合は Trim メソッド実行時に除去される。
44 public int TrimLimit { get; set; }
47 /// 自動で Trim メソッドを実行する、参照回数の閾値
50 /// AutoTrimCount で指定された回数だけアイテムが参照される度に Trim メソッドが実行される。
52 public int AutoTrimCount { get; set; }
54 public class CacheRemovedEventArgs : EventArgs
56 public KeyValuePair<TKey, TValue> Item { get; }
58 public CacheRemovedEventArgs(KeyValuePair<TKey, TValue> item)
62 public event EventHandler<CacheRemovedEventArgs>? CacheRemoved;
64 internal LinkedList<KeyValuePair<TKey, TValue>> InnerList;
65 internal Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> InnerDict;
67 internal int AccessCount = 0;
69 public LRUCacheDictionary()
70 : this(trimLimit: int.MaxValue, autoTrimCount: int.MaxValue)
74 public LRUCacheDictionary(int trimLimit, int autoTrimCount)
76 this.TrimLimit = trimLimit;
77 this.AutoTrimCount = autoTrimCount;
79 this.InnerList = new LinkedList<KeyValuePair<TKey, TValue>>();
80 this.InnerDict = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>();
84 /// innerList の並び順を最近アクセスがあった順に維持するために、
85 /// 辞書内のアイテムが参照する度に呼び出されるメソッド。
87 protected void UpdateAccess(LinkedListNode<KeyValuePair<TKey, TValue>> node)
89 this.InnerList.Remove(node);
90 this.InnerList.AddFirst(node);
95 if (this.Count <= this.TrimLimit) return false;
97 for (var i = this.Count; i > this.TrimLimit; i--)
99 var node = this.InnerList.Last;
100 this.InnerList.Remove(node);
101 this.InnerDict.Remove(node.Value.Key);
103 this.CacheRemoved?.Invoke(this, new CacheRemovedEventArgs(node.Value));
109 internal bool AutoTrim()
111 if (this.AccessCount < this.AutoTrimCount) return false;
113 this.AccessCount = 0; // カウンターをリセット
118 public void Add(TKey key, TValue value)
119 => this.Add(new KeyValuePair<TKey, TValue>(key, value));
121 public void Add(KeyValuePair<TKey, TValue> item)
123 var node = new LinkedListNode<KeyValuePair<TKey, TValue>>(item);
124 this.InnerList.AddFirst(node);
125 this.InnerDict.Add(item.Key, node);
131 public bool ContainsKey(TKey key)
132 => this.InnerDict.ContainsKey(key);
134 public bool Contains(KeyValuePair<TKey, TValue> item)
136 if (!this.InnerDict.TryGetValue(item.Key, out var node)) return false;
138 return EqualityComparer<TValue>.Default.Equals(node.Value.Value, item.Value);
141 public bool Remove(TKey key)
143 if (!this.InnerDict.TryGetValue(key, out var node)) return false;
145 this.InnerList.Remove(node);
147 return this.InnerDict.Remove(key);
150 public bool Remove(KeyValuePair<TKey, TValue> item)
152 if (!this.InnerDict.TryGetValue(item.Key, out var node)) return false;
154 if (!EqualityComparer<TValue>.Default.Equals(node.Value.Value, item.Value))
157 this.InnerList.Remove(node);
159 return this.InnerDict.Remove(item.Key);
162 #pragma warning disable CS8767
163 public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value)
164 #pragma warning restore CS8767
166 var ret = this.InnerDict.TryGetValue(key, out var node);
174 this.UpdateAccess(node);
175 value = node.Value.Value;
183 public ICollection<TKey> Keys
184 => this.InnerDict.Keys;
186 public ICollection<TValue> Values
187 => this.InnerDict.Values.Select(x => x.Value.Value).ToList();
189 public TValue this[TKey key]
193 var node = this.InnerDict[key];
194 this.UpdateAccess(node);
199 return node.Value.Value;
204 var pair = new KeyValuePair<TKey, TValue>(key, value);
206 if (this.InnerDict.TryGetValue(key, out var node))
208 this.InnerList.Remove(node);
213 node = new LinkedListNode<KeyValuePair<TKey, TValue>>(pair);
214 this.InnerDict[key] = node;
217 this.InnerList.AddFirst(node);
226 this.InnerList.Clear();
227 this.InnerDict.Clear();
230 public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
233 throw new ArgumentNullException(nameof(array));
235 throw new ArgumentOutOfRangeException(nameof(arrayIndex));
236 if (arrayIndex >= array.Length)
237 throw new ArgumentException("arrayIndex is equal to or greater than array.Length.", nameof(arrayIndex));
238 if (array.Length - arrayIndex < this.Count)
239 throw new ArgumentException("The destination array is too small.", nameof(array));
241 foreach (var pair in this)
242 array[arrayIndex++] = pair;
246 => this.InnerDict.Count;
248 public bool IsReadOnly
251 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
252 => this.InnerDict.Select(x => x.Value.Value).GetEnumerator();
254 IEnumerator IEnumerable.GetEnumerator()
255 => this.GetEnumerator();