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             LinkedListNode<KeyValuePair<TKey, TValue>> node;
 139             if (!this.innerDict.TryGetValue(item.Key, out node)) return false;
 140
 141             return node.Value.Value.Equals(item.Value);
 142         }
 143
 144         public bool Remove(TKey key)
 145         {
 146             LinkedListNode<KeyValuePair<TKey, TValue>> node;
 147             if (!this.innerDict.TryGetValue(key, out node)) return false;
 148
 149             this.innerList.Remove(node);
 150
 151             return this.innerDict.Remove(key);
 152         }
 153
 154         public bool Remove(KeyValuePair<TKey, TValue> item)
 155         {
 156             LinkedListNode<KeyValuePair<TKey, TValue>> node;
 157             if (!this.innerDict.TryGetValue(item.Key, out node)) return false;
 158
 159             if (!node.Value.Value.Equals(item.Value)) return false;
 160
 161             this.innerList.Remove(node);
 162
 163             return this.innerDict.Remove(item.Key);
 164         }
 165
 166         public bool TryGetValue(TKey key, out TValue value)
 167         {
 168             LinkedListNode<KeyValuePair<TKey, TValue>> node;
 169
 170             var ret = this.innerDict.TryGetValue(key, out node);
 171
 172             if (!ret)
 173             {
 174                 value = default(TValue);
 175                 return false;
 176             }
 177
 178             this.UpdateAccess(node);
 179             value = node.Value.Value;
 180
 181             this.accessCount++;
 182             this.AutoTrim();
 183
 184             return true;
 185         }
 186
 187         public ICollection<TKey> Keys
 188         {
 189             get { return this.innerDict.Keys; }
 190         }
 191
 192         public ICollection<TValue> Values
 193         {
 194             get { return this.innerDict.Values.Select(x => x.Value.Value).ToList(); }
 195         }
 196
 197         public TValue this[TKey key]
 198         {
 199             get
 200             {
 201                 var node = this.innerDict[key];
 202                 this.UpdateAccess(node);
 203
 204                 this.accessCount++;
 205                 this.AutoTrim();
 206
 207                 return node.Value.Value;
 208             }
 209             set
 210             {
 211                 LinkedListNode<KeyValuePair<TKey, TValue>> node;
 212
 213                 var pair = new KeyValuePair<TKey, TValue>(key, value);
 214
 215                 if (this.innerDict.TryGetValue(key, out node))
 216                 {
 217                     this.innerList.Remove(node);
 218                     node.Value = pair;
 219                 }
 220                 else
 221                 {
 222                     node = new LinkedListNode<KeyValuePair<TKey, TValue>>(pair);
 223                     this.innerDict[key] = node;
 224                 }
 225
 226                 this.innerList.AddFirst(node);
 227
 228                 this.accessCount++;
 229                 this.AutoTrim();
 230             }
 231         }
 232
 233         public void Clear()
 234         {
 235             this.innerList.Clear();
 236             this.innerDict.Clear();
 237         }
 238
 239         public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
 240         {
 241             if (array == null)
 242                 throw new ArgumentNullException(nameof(array));
 243             if (arrayIndex < 0)
 244                 throw new ArgumentOutOfRangeException(nameof(arrayIndex));
 245             if (arrayIndex >= array.Length)
 246                 throw new ArgumentException("arrayIndex is equal to or greater than array.Length.", nameof(arrayIndex));
 247             if (array.Length - arrayIndex < this.Count)
 248                 throw new ArgumentException("The destination array is too small.", nameof(array));
 249
 250             foreach (var pair in this)
 251                 array[arrayIndex++] = pair;
 252         }
 253
 254         public int Count
 255         {
 256             get { return this.innerDict.Count; }
 257         }
 258
 259         public bool IsReadOnly
 260         {
 261             get { return false; }
 262         }
 263
 264         public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
 265         {
 266             return this.innerDict.Select(x => x.Value.Value).GetEnumerator();
 267         }
 268
 269         IEnumerator IEnumerable.GetEnumerator()
 270         {
 271             return this.GetEnumerator();
 272         }
 273     }
 274 }