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             {
  57                 this.Item = item;
  58             }
  59         }
  60         public event EventHandler<CacheRemovedEventArgs> CacheRemoved;
  61
  62         internal LinkedList<KeyValuePair<TKey, TValue>> innerList;
  63         internal Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> innerDict;
  64
  65         internal int accessCount = 0;
  66
  67         public LRUCacheDictionary()
  68             : this(trimLimit: int.MaxValue, autoTrimCount: int.MaxValue)
  69         {
  70         }
  71
  72         public LRUCacheDictionary(int trimLimit, int autoTrimCount)
  73         {
  74             this.TrimLimit = trimLimit;
  75             this.AutoTrimCount = autoTrimCount;
  76
  77             this.innerList = new LinkedList<KeyValuePair<TKey, TValue>>();
  78             this.innerDict = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>();
  79         }
  80
  81         /// <summary>
  82         /// innerList の並び順を最近アクセスがあった順に維持するために、
  83         /// 辞書内のアイテムが参照する度に呼び出されるメソッド。
  84         /// </summary>
  85         protected void UpdateAccess(LinkedListNode<KeyValuePair<TKey, TValue>> node)
  86         {
  87             this.innerList.Remove(node);
  88             this.innerList.AddFirst(node);
  89         }
  90
  91         public bool Trim()
  92         {
  93             if (this.Count <= this.TrimLimit) return false;
  94
  95             for (int i = this.Count; i > this.TrimLimit; i--)
  96             {
  97                 var node = this.innerList.Last;
  98                 this.innerList.Remove(node);
  99                 this.innerDict.Remove(node.Value.Key);
 100
 101                 this.CacheRemoved?.Invoke(this, new CacheRemovedEventArgs(node.Value));
 102             }
 103
 104             return true;
 105         }
 106
 107         internal bool AutoTrim()
 108         {
 109             if (this.accessCount < this.AutoTrimCount) return false;
 110
 111             this.accessCount = 0; // カウンターをリセット
 112
 113             return this.Trim();
 114         }
 115
 116         public void Add(TKey key, TValue value)
 117         {
 118             this.Add(new KeyValuePair<TKey, TValue>(key, value));
 119         }
 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         {
 133             return this.innerDict.ContainsKey(key);
 134         }
 135
 136         public bool Contains(KeyValuePair<TKey, TValue> item)
 137         {
 138             if (!this.innerDict.TryGetValue(item.Key, out var node)) return false;
 139
 140             return node.Value.Value.Equals(item.Value);
 141         }
 142
 143         public bool Remove(TKey key)
 144         {
 145             if (!this.innerDict.TryGetValue(key, out var node)) return false;
 146
 147             this.innerList.Remove(node);
 148
 149             return this.innerDict.Remove(key);
 150         }
 151
 152         public bool Remove(KeyValuePair<TKey, TValue> item)
 153         {
 154             if (!this.innerDict.TryGetValue(item.Key, out var node)) return false;
 155
 156             if (!node.Value.Value.Equals(item.Value)) return false;
 157
 158             this.innerList.Remove(node);
 159
 160             return this.innerDict.Remove(item.Key);
 161         }
 162
 163         public bool TryGetValue(TKey key, out TValue value)
 164         {
 165             var ret = this.innerDict.TryGetValue(key, out var node);
 166
 167             if (!ret)
 168             {
 169                 value = default(TValue);
 170                 return false;
 171             }
 172
 173             this.UpdateAccess(node);
 174             value = node.Value.Value;
 175
 176             this.accessCount++;
 177             this.AutoTrim();
 178
 179             return true;
 180         }
 181
 182         public ICollection<TKey> Keys
 183         {
 184             get { return this.innerDict.Keys; }
 185         }
 186
 187         public ICollection<TValue> Values
 188         {
 189             get { return this.innerDict.Values.Select(x => x.Value.Value).ToList(); }
 190         }
 191
 192         public TValue this[TKey key]
 193         {
 194             get
 195             {
 196                 var node = this.innerDict[key];
 197                 this.UpdateAccess(node);
 198
 199                 this.accessCount++;
 200                 this.AutoTrim();
 201
 202                 return node.Value.Value;
 203             }
 204             set
 205             {
 206                 var pair = new KeyValuePair<TKey, TValue>(key, value);
 207
 208                 if (this.innerDict.TryGetValue(key, out var node))
 209                 {
 210                     this.innerList.Remove(node);
 211                     node.Value = pair;
 212                 }
 213                 else
 214                 {
 215                     node = new LinkedListNode<KeyValuePair<TKey, TValue>>(pair);
 216                     this.innerDict[key] = node;
 217                 }
 218
 219                 this.innerList.AddFirst(node);
 220
 221                 this.accessCount++;
 222                 this.AutoTrim();
 223             }
 224         }
 225
 226         public void Clear()
 227         {
 228             this.innerList.Clear();
 229             this.innerDict.Clear();
 230         }
 231
 232         public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
 233         {
 234             if (array == null)
 235                 throw new ArgumentNullException(nameof(array));
 236             if (arrayIndex < 0)
 237                 throw new ArgumentOutOfRangeException(nameof(arrayIndex));
 238             if (arrayIndex >= array.Length)
 239                 throw new ArgumentException("arrayIndex is equal to or greater than array.Length.", nameof(arrayIndex));
 240             if (array.Length - arrayIndex < this.Count)
 241                 throw new ArgumentException("The destination array is too small.", nameof(array));
 242
 243             foreach (var pair in this)
 244                 array[arrayIndex++] = pair;
 245         }
 246
 247         public int Count
 248         {
 249             get { return this.innerDict.Count; }
 250         }
 251
 252         public bool IsReadOnly
 253         {
 254             get { return false; }
 255         }
 256
 257         public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
 258         {
 259             return this.innerDict.Select(x => x.Value.Value).GetEnumerator();
 260         }
 261
 262         IEnumerator IEnumerable.GetEnumerator()
 263         {
 264             return this.GetEnumerator();
 265         }
 266     }
 267 }