mcs/class/System.Web/System.Web.Configuration_2.0/LruCache.cs

   1 //
   2 // A simple LRU cache
   3 //
   4 // Authors:
   5 //   Miguel de Icaza (miguel@gnome.org)
   6 //   Andres G. Aragoneses (andres@7digital.com)
   7 //
   8 // Copyright 2010 Miguel de Icaza
   9 // Copyright 2013 7digital Media Ltd.
  10 //
  11 // Permission is hereby granted, free of charge, to any person obtaining a copy
  12 // of this software and associated documentation files (the "Software"), to deal
  13 // in the Software without restriction, including without limitation the rights
  14 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  15 // copies of the Software, and to permit persons to whom the Software is
  16 // furnished to do so, subject to the following conditions:
  17 //
  18 // The above copyright notice and this permission notice shall be included in
  19 // all copies or substantial portions of the Software.
  20 //
  21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  22 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  23 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  24 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  25 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  26 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  27 // THE SOFTWARE.
  28 //
  29
  30 using System;
  31 using System.Collections.Generic;
  32
  33 namespace System.Web.Configuration {
  34
  35         class LruCache<TKey, TValue> {
  36                 Dictionary<TKey, LinkedListNode <TValue>> dict;
  37                 Dictionary<LinkedListNode<TValue>, TKey> revdict;
  38                 LinkedList<TValue> list;
  39                 int entry_limit;
  40
  41                 bool eviction_warning_shown;
  42                 int evictions;
  43                 bool size_overriden;
  44
  45                 internal string EvictionWarning { set; private get; }
  46
  47                 public LruCache (int entryLimit)
  48                 {
  49                         entry_limit = entryLimit;
  50                         dict = new Dictionary<TKey, LinkedListNode<TValue>> ();
  51                         revdict = new Dictionary<LinkedListNode<TValue>, TKey> ();
  52                         list = new LinkedList<TValue> ();
  53                 }
  54
  55                 //for debugging: public int Count { get { return dict.Count; } }
  56
  57                 void Evict ()
  58                 {
  59                         var last = list.Last;
  60                         if (last == null)
  61                                 return;
  62
  63                         var key = revdict [last];
  64
  65                         dict.Remove (key);
  66                         revdict.Remove (last);
  67                         list.RemoveLast ();
  68                         DisposeValue (last.Value);
  69                         evictions++;
  70
  71                         if (!String.IsNullOrEmpty (EvictionWarning) && !eviction_warning_shown && (evictions >= entry_limit)) {
  72                                 Console.Error.WriteLine ("WARNING: " + EvictionWarning);
  73                                 eviction_warning_shown = true;
  74                         }
  75                 }
  76
  77                 public void Clear ()
  78                 {
  79                         foreach (var element in list) {
  80                                 DisposeValue (element);
  81                         }
  82
  83                         dict.Clear ();
  84                         revdict.Clear ();
  85                         list.Clear ();
  86                         eviction_warning_shown = false;
  87                         evictions = 0;
  88                 }
  89
  90                 void DisposeValue (TValue value)
  91                 {
  92                         if (value is IDisposable) {
  93                                 ((IDisposable)value).Dispose ();
  94                         }
  95                 }
  96
  97                 public bool TryGetValue (TKey key, out TValue value)
  98                 {
  99                         LinkedListNode<TValue> node;
 100
 101                         if (dict.TryGetValue (key, out node)){
 102                                 list.Remove (node);
 103                                 list.AddFirst (node);
 104
 105                                 value = node.Value;
 106                                 return true;
 107                         }
 108                         value = default (TValue);
 109                         return false;
 110                 }
 111
 112                 public void Add (TKey key, TValue value)
 113                 {
 114                         LinkedListNode<TValue> node;
 115
 116                         if (dict.TryGetValue (key, out node)){
 117
 118                                 // If we already have a key, move it to the front
 119                                 list.Remove (node);
 120                                 list.AddFirst (node);
 121
 122                                 // Remove the old value
 123                                 DisposeValue (node.Value);
 124
 125                                 node.Value = value;
 126                                 return;
 127                         }
 128
 129                         if (dict.Count >= entry_limit)
 130                                 Evict ();
 131
 132                         // Adding new node
 133                         node = new LinkedListNode<TValue> (value);
 134                         list.AddFirst (node);
 135                         dict [key] = node;
 136                         revdict [node] = key;
 137                 }
 138
 139                 public override string ToString ()
 140                 {
 141                         return "LRUCache dict={0} revdict={1} list={2}";
 142                 }
 143         }
 144 }