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