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; private set; }
  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                 if (this.CacheRemoved != null)
 102                     this.CacheRemoved(this, new CacheRemovedEventArgs(node.Value));
 103             }
 104
 105             return true;
 106         }
 107
 108         internal bool AutoTrim()
 109         {
 110             if (this.accessCount < this.AutoTrimCount) return false;
 111
 112             this.accessCount = 0; // カウンターをリセット
 113
 114             return this.Trim();
 115         }
 116
 117         public void Add(TKey key, TValue value)
 118         {
 119             this.Add(new KeyValuePair<TKey, TValue>(key, value));
 120         }
 121
 122         public void Add(KeyValuePair<TKey, TValue> item)
 123         {
 124             var node = new LinkedListNode<KeyValuePair<TKey, TValue>>(item);
 125             this.innerList.AddFirst(node);
 126             this.innerDict.Add(item.Key, node);
 127
 128             this.accessCount++;
 129             this.AutoTrim();
 130         }
 131
 132         public bool ContainsKey(TKey key)
 133         {
 134             return this.innerDict.ContainsKey(key);
 135         }
 136
 137         public bool Contains(KeyValuePair<TKey, TValue> item)
 138         {
 139             if (!this.innerDict.ContainsKey(item.Key)) return false;
 140
 141             return this.innerDict[item.Key].Value.Value.Equals(item.Value);
 142         }
 143
 144         public bool Remove(TKey key)
 145         {
 146             if (!this.innerDict.ContainsKey(key)) return false;
 147
 148             var node = this.innerDict[key];
 149             this.innerList.Remove(node);
 150
 151             return this.innerDict.Remove(key);
 152         }
 153
 154         public bool Remove(KeyValuePair<TKey, TValue> item)
 155         {
 156             if (!this.innerDict.ContainsKey(item.Key)) return false;
 157
 158             var node = this.innerDict[item.Key];
 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.ContainsKey(key))
 216                 {
 217                     node = this.innerDict[key];
 218                     this.innerList.Remove(node);
 219                     node.Value = pair;
 220                 }
 221                 else
 222                 {
 223                     node = new LinkedListNode<KeyValuePair<TKey, TValue>>(pair);
 224                     this.innerDict[key] = node;
 225                 }
 226
 227                 this.innerList.AddFirst(node);
 228
 229                 this.accessCount++;
 230                 this.AutoTrim();
 231             }
 232         }
 233
 234         public void Clear()
 235         {
 236             this.innerList.Clear();
 237             this.innerDict.Clear();
 238         }
 239
 240         public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
 241         {
 242             if (array == null)
 243                 throw new ArgumentNullException();
 244             if (arrayIndex < 0)
 245                 throw new ArgumentOutOfRangeException();
 246             if (arrayIndex >= array.Length)
 247                 throw new ArgumentException("arrayIndex is equal to or greater than array.Length.");
 248             if (array.Length - arrayIndex < this.Count)
 249                 throw new ArgumentException("The destination array is too small.");
 250
 251             foreach (var pair in this)
 252                 array[arrayIndex++] = pair;
 253         }
 254
 255         public int Count
 256         {
 257             get { return this.innerDict.Count; }
 258         }
 259
 260         public bool IsReadOnly
 261         {
 262             get { return false; }
 263         }
 264
 265         public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
 266         {
 267             return this.innerDict.Select(x => x.Value.Value).GetEnumerator();
 268         }
 269
 270         IEnumerator IEnumerable.GetEnumerator()
 271         {
 272             return this.GetEnumerator();
 273         }
 274     }
 275 }