mcs/class/referencesource/System.ServiceModel.Internals/System/Runtime/MruCache.cs

   1 //------------------------------------------------------------
   2 // Copyright (c) Microsoft Corporation.  All rights reserved.
   3 //------------------------------------------------------------
   4 namespace System.Runtime
   5 {
   6     using System.Collections.Generic;
   7
   8     class MruCache<TKey, TValue>
   9         where TKey : class
  10         where TValue : class
  11     {
  12         LinkedList<TKey> mruList;
  13         Dictionary<TKey, CacheEntry> items;
  14         int lowWatermark;
  15         int highWatermark;
  16         CacheEntry mruEntry;
  17
  18         public MruCache(int watermark)
  19             : this(watermark * 4 / 5, watermark)
  20         {
  21         }
  22
  23         //
  24         // The cache will grow until the high watermark. At which point, the least recently used items
  25         // will be purge until the cache's size is reduced to low watermark
  26         //
  27         public MruCache(int lowWatermark, int highWatermark)
  28             : this(lowWatermark, highWatermark, null)
  29         {
  30         }
  31
  32         public MruCache(int lowWatermark, int highWatermark, IEqualityComparer<TKey> comparer)
  33         {
  34             Fx.Assert(lowWatermark < highWatermark, "");
  35             Fx.Assert(lowWatermark >= 0, "");
  36
  37             this.lowWatermark = lowWatermark;
  38             this.highWatermark = highWatermark;
  39             this.mruList = new LinkedList<TKey>();
  40             if (comparer == null)
  41             {
  42                 this.items = new Dictionary<TKey, CacheEntry>();
  43             }
  44             else
  45             {
  46                 this.items = new Dictionary<TKey, CacheEntry>(comparer);
  47             }
  48         }
  49
  50         public int Count
  51         {
  52             get
  53             {
  54                 return this.items.Count;
  55             }
  56         }
  57
  58         public void Add(TKey key, TValue value)
  59         {
  60             Fx.Assert(null != key, "");
  61
  62             // if anything goes wrong (duplicate entry, etc) we should
  63             // clear our caches so that we don't get out of sync
  64             bool success = false;
  65             try
  66             {
  67                 if (this.items.Count == this.highWatermark)
  68                 {
  69                     // If the cache is full, purge enough LRU items to shrink the
  70                     // cache down to the low watermark
  71                     int countToPurge = this.highWatermark - this.lowWatermark;
  72                     for (int i = 0; i < countToPurge; i++)
  73                     {
  74                         TKey keyRemove = this.mruList.Last.Value;
  75                         this.mruList.RemoveLast();
  76                         TValue item = this.items[keyRemove].value;
  77                         this.items.Remove(keyRemove);
  78                         OnSingleItemRemoved(item);
  79                         OnItemAgedOutOfCache(item);
  80                     }
  81                 }
  82                 // Add  the new entry to the cache and make it the MRU element
  83                 CacheEntry entry;
  84                 entry.node = this.mruList.AddFirst(key);
  85                 entry.value = value;
  86                 this.items.Add(key, entry);
  87                 this.mruEntry = entry;
  88                 success = true;
  89             }
  90             finally
  91             {
  92                 if (!success)
  93                 {
  94                     this.Clear();
  95                 }
  96             }
  97         }
  98
  99         public void Clear()
 100         {
 101             this.mruList.Clear();
 102             this.items.Clear();
 103             this.mruEntry.value = null;
 104             this.mruEntry.node = null;
 105         }
 106
 107         public bool Remove(TKey key)
 108         {
 109             Fx.Assert(null != key, "");
 110
 111             CacheEntry entry;
 112             if (this.items.TryGetValue(key, out entry))
 113             {
 114                 this.items.Remove(key);
 115                 OnSingleItemRemoved(entry.value);
 116                 this.mruList.Remove(entry.node);
 117                 if (object.ReferenceEquals(this.mruEntry.node, entry.node))
 118                 {
 119                     this.mruEntry.value = null;
 120                     this.mruEntry.node = null;
 121                 }
 122                 return true;
 123             }
 124
 125             return false;
 126         }
 127
 128         protected virtual void OnSingleItemRemoved(TValue item)
 129         {
 130         }
 131
 132         protected virtual void OnItemAgedOutOfCache(TValue item)
 133         {
 134         }
 135
 136         //
 137         // If found, make the entry most recently used
 138         //
 139         public bool TryGetValue(TKey key, out TValue value)
 140         {
 141             // first check our MRU item
 142             if (this.mruEntry.node != null && key != null && key.Equals(this.mruEntry.node.Value))
 143             {
 144                 value = this.mruEntry.value;
 145                 return true;
 146             }
 147
 148             CacheEntry entry;
 149
 150             bool found = this.items.TryGetValue(key, out entry);
 151             value = entry.value;
 152
 153             // Move the node to the head of the MRU list if it's not already there
 154             if (found && this.mruList.Count > 1
 155                 && !object.ReferenceEquals(this.mruList.First, entry.node))
 156             {
 157                 this.mruList.Remove(entry.node);
 158                 this.mruList.AddFirst(entry.node);
 159                 this.mruEntry = entry;
 160             }
 161
 162             return found;
 163         }
 164
 165         struct CacheEntry
 166         {
 167             internal TValue value;
 168             internal LinkedListNode<TKey> node;
 169         }
 170     }
 171 }