5 // Miguel de Icaza (miguel@gnome.org)
6 // Andres G. Aragoneses (andres@7digital.com)
8 // Copyright 2010 Miguel de Icaza
9 // Copyright 2013 7digital Media Ltd.
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:
18 // The above copyright notice and this permission notice shall be included in
19 // all copies or substantial portions of the Software.
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
31 using System.Collections.Generic;
33 namespace System.Web.Configuration {
35 class LruCache<TKey, TValue> {
36 Dictionary<TKey, LinkedListNode <TValue>> dict;
37 Dictionary<LinkedListNode<TValue>, TKey> revdict;
38 LinkedList<TValue> list;
41 bool eviction_warning_shown;
44 internal string EvictionWarning { set; private get; }
46 public LruCache (int entryLimit)
48 entry_limit = entryLimit;
49 dict = new Dictionary<TKey, LinkedListNode<TValue>> ();
50 revdict = new Dictionary<LinkedListNode<TValue>, TKey> ();
51 list = new LinkedList<TValue> ();
54 //for debugging: public int Count { get { return dict.Count; } }
62 var key = revdict [last];
65 revdict.Remove (last);
67 DisposeValue (last.Value);
70 if (!String.IsNullOrEmpty (EvictionWarning) && !eviction_warning_shown && (evictions >= entry_limit)) {
71 Console.Error.WriteLine ("WARNING: " + EvictionWarning);
72 eviction_warning_shown = true;
78 foreach (var element in list) {
79 DisposeValue (element);
85 eviction_warning_shown = false;
89 void DisposeValue (TValue value)
91 if (value is IDisposable) {
92 ((IDisposable)value).Dispose ();
96 public bool TryGetValue (TKey key, out TValue value)
98 LinkedListNode<TValue> node;
100 if (dict.TryGetValue (key, out node)){
102 list.AddFirst (node);
107 value = default (TValue);
111 public void Add (TKey key, TValue value)
113 LinkedListNode<TValue> node;
115 if (dict.TryGetValue (key, out node)){
117 // If we already have a key, move it to the front
119 list.AddFirst (node);
121 // Remove the old value
122 DisposeValue (node.Value);
128 if (dict.Count >= entry_limit)
132 node = new LinkedListNode<TValue> (value);
133 list.AddFirst (node);
135 revdict [node] = key;
138 public override string ToString ()
140 return "LRUCache dict={0} revdict={1} list={2}";