OpenTween/LRUCacheDictionary.cs

   1 // OpenTween - Client of Twitter
   2 // Copyright (c) 2013 kim_upsilon (@kim_upsilon) <https://upsilo.net/~upsilon/>
   3 // All rights reserved.
   4 //
   5 // This file is part of OpenTween.
   6 //
   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)
  10 // any later version.
  11 //
  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
  15 // for more details.
  16 //
  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.
  21
  22 #nullable enable
  23
  24 using System;
  25 using System.Collections;
  26 using System.Collections.Generic;
  27 using System.Diagnostics.CodeAnalysis;
  28 using System.Linq;
  29 using System.Text;
  30
  31 namespace OpenTween
  32 {
  33     /// <summary>
  34     /// LRU によるキャッシュを行うための辞書クラス
  35     /// </summary>
  36     public class LRUCacheDictionary<TKey, TValue> : IDictionary<TKey, TValue>
  37     {
  38         /// <summary>
  39         /// 保持するアイテムの個数
  40         /// </summary>
  41         /// <remarks>
  42         /// TrimLimit を上回る個数のアイテムが格納されている場合は Trim メソッド実行時に除去される。
  43         /// </remarks>
  44         public int TrimLimit { get; set; }
  45
  46         /// <summary>
  47         /// 自動で Trim メソッドを実行する、参照回数の閾値
  48         /// </summary>
  49         /// <remarks>
  50         /// AutoTrimCount で指定された回数だけアイテムが参照される度に Trim メソッドが実行される。
  51         /// </remarks>
  52         public int AutoTrimCount { get; set; }
  53
  54         public class CacheRemovedEventArgs : EventArgs
  55         {
  56             public KeyValuePair<TKey, TValue> Item { get; }
  57
  58             public CacheRemovedEventArgs(KeyValuePair<TKey, TValue> item)
  59                 => this.Item = item;
  60         }
  61
  62         public event EventHandler<CacheRemovedEventArgs>? CacheRemoved;
  63
  64         internal LinkedList<KeyValuePair<TKey, TValue>> InnerList;
  65         internal Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> InnerDict;
  66
  67         internal int AccessCount = 0;
  68
  69         public LRUCacheDictionary()
  70             : this(trimLimit: int.MaxValue, autoTrimCount: int.MaxValue)
  71         {
  72         }
  73
  74         public LRUCacheDictionary(int trimLimit, int autoTrimCount)
  75         {
  76             this.TrimLimit = trimLimit;
  77             this.AutoTrimCount = autoTrimCount;
  78
  79             this.InnerList = new LinkedList<KeyValuePair<TKey, TValue>>();
  80             this.InnerDict = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>();
  81         }
  82
  83         /// <summary>
  84         /// innerList の並び順を最近アクセスがあった順に維持するために、
  85         /// 辞書内のアイテムが参照する度に呼び出されるメソッド。
  86         /// </summary>
  87         protected void UpdateAccess(LinkedListNode<KeyValuePair<TKey, TValue>> node)
  88         {
  89             this.InnerList.Remove(node);
  90             this.InnerList.AddFirst(node);
  91         }
  92
  93         public bool Trim()
  94         {
  95             if (this.Count <= this.TrimLimit) return false;
  96
  97             for (var i = this.Count; i > this.TrimLimit; i--)
  98             {
  99                 var node = this.InnerList.Last;
 100                 this.InnerList.Remove(node);
 101                 this.InnerDict.Remove(node.Value.Key);
 102
 103                 this.CacheRemoved?.Invoke(this, new CacheRemovedEventArgs(node.Value));
 104             }
 105
 106             return true;
 107         }
 108
 109         internal bool AutoTrim()
 110         {
 111             if (this.AccessCount < this.AutoTrimCount) return false;
 112
 113             this.AccessCount = 0; // カウンターをリセット
 114
 115             return this.Trim();
 116         }
 117
 118         public void Add(TKey key, TValue value)
 119             => this.Add(new KeyValuePair<TKey, TValue>(key, value));
 120
 121         public void Add(KeyValuePair<TKey, TValue> item)
 122         {
 123             var node = new LinkedListNode<KeyValuePair<TKey, TValue>>(item);
 124             this.InnerList.AddFirst(node);
 125             this.InnerDict.Add(item.Key, node);
 126
 127             this.AccessCount++;
 128             this.AutoTrim();
 129         }
 130
 131         public bool ContainsKey(TKey key)
 132             => this.InnerDict.ContainsKey(key);
 133
 134         public bool Contains(KeyValuePair<TKey, TValue> item)
 135         {
 136             if (!this.InnerDict.TryGetValue(item.Key, out var node)) return false;
 137
 138             return EqualityComparer<TValue>.Default.Equals(node.Value.Value, item.Value);
 139         }
 140
 141         public bool Remove(TKey key)
 142         {
 143             if (!this.InnerDict.TryGetValue(key, out var node)) return false;
 144
 145             this.InnerList.Remove(node);
 146
 147             return this.InnerDict.Remove(key);
 148         }
 149
 150         public bool Remove(KeyValuePair<TKey, TValue> item)
 151         {
 152             if (!this.InnerDict.TryGetValue(item.Key, out var node)) return false;
 153
 154             if (!EqualityComparer<TValue>.Default.Equals(node.Value.Value, item.Value))
 155                 return false;
 156
 157             this.InnerList.Remove(node);
 158
 159             return this.InnerDict.Remove(item.Key);
 160         }
 161
 162 #pragma warning disable CS8767
 163         public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value)
 164 #pragma warning restore CS8767
 165         {
 166             var ret = this.InnerDict.TryGetValue(key, out var node);
 167
 168             if (!ret)
 169             {
 170                 value = default!;
 171                 return false;
 172             }
 173
 174             this.UpdateAccess(node);
 175             value = node.Value.Value;
 176
 177             this.AccessCount++;
 178             this.AutoTrim();
 179
 180             return true;
 181         }
 182
 183         public ICollection<TKey> Keys
 184             => this.InnerDict.Keys;
 185
 186         public ICollection<TValue> Values
 187             => this.InnerDict.Values.Select(x => x.Value.Value).ToList();
 188
 189         public TValue this[TKey key]
 190         {
 191             get
 192             {
 193                 var node = this.InnerDict[key];
 194                 this.UpdateAccess(node);
 195
 196                 this.AccessCount++;
 197                 this.AutoTrim();
 198
 199                 return node.Value.Value;
 200             }
 201
 202             set
 203             {
 204                 var pair = new KeyValuePair<TKey, TValue>(key, value);
 205
 206                 if (this.InnerDict.TryGetValue(key, out var node))
 207                 {
 208                     this.InnerList.Remove(node);
 209                     node.Value = pair;
 210                 }
 211                 else
 212                 {
 213                     node = new LinkedListNode<KeyValuePair<TKey, TValue>>(pair);
 214                     this.InnerDict[key] = node;
 215                 }
 216
 217                 this.InnerList.AddFirst(node);
 218
 219                 this.AccessCount++;
 220                 this.AutoTrim();
 221             }
 222         }
 223
 224         public void Clear()
 225         {
 226             this.InnerList.Clear();
 227             this.InnerDict.Clear();
 228         }
 229
 230         public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
 231         {
 232             if (array == null)
 233                 throw new ArgumentNullException(nameof(array));
 234             if (arrayIndex < 0)
 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));
 240
 241             foreach (var pair in this)
 242                 array[arrayIndex++] = pair;
 243         }
 244
 245         public int Count
 246             => this.InnerDict.Count;
 247
 248         public bool IsReadOnly
 249             => false;
 250
 251         public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
 252             => this.InnerDict.Select(x => x.Value.Value).GetEnumerator();
 253
 254         IEnumerator IEnumerable.GetEnumerator()
 255             => this.GetEnumerator();
 256     }
 257 }