2 // A simple LRU cache used for tracking the cache items
5 // Miguel de Icaza (miguel@gnome.org)
7 // Copyright 2010 Miguel de Icaza
9 // Permission is hereby granted, free of charge, to any person obtaining a copy
10 // of this software and associated documentation files (the "Software"), to deal
11 // in the Software without restriction, including without limitation the rights
12 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 // copies of the Software, and to permit persons to whom the Software is
14 // furnished to do so, subject to the following conditions:
16 // The above copyright notice and this permission notice shall be included in
17 // all copies or substantial portions of the Software.
19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
28 using System.Collections.Generic;
30 namespace System.Web.Caching
32 sealed class CacheItemLRU
34 public delegate bool SelectItemsQualifier (CacheItem item);
36 Dictionary<string, LinkedListNode <CacheItem>> dict;
37 Dictionary<LinkedListNode<CacheItem>, string> revdict;
38 LinkedList<CacheItem> list;
41 // High/Low water mark is here to avoid situations when we hit a limit, evict an
42 // entry, add another one and have to evict again because the limit was hit. When we
43 // hit the high water limit, we evict until we reach the low water mark to avoid the
45 int highWaterMark, lowWaterMark;
49 get { return dict.Count; }
52 public CacheItemLRU (Cache owner, int highWaterMark, int lowWaterMark)
54 list = new LinkedList<CacheItem> ();
55 dict = new Dictionary<string, LinkedListNode<CacheItem>> (StringComparer.Ordinal);
56 revdict = new Dictionary<LinkedListNode<CacheItem>, string> ();
58 this.highWaterMark = highWaterMark;
59 this.lowWaterMark = lowWaterMark;
63 public bool TryGetValue (string key, out CacheItem value)
65 LinkedListNode <CacheItem> item;
67 if (dict.TryGetValue (key, out item)) {
75 // Must ALWAYS be called with the owner's write lock held
76 public void EvictIfNecessary ()
81 for (int i = dict.Count; i > lowWaterMark; i--) {
82 var key = revdict [list.Last];
84 owner.Remove (key, CacheItemRemovedReason.Underused, false, true);
88 // Must ALWAYS be called with the owner's read lock held
89 public void InvokePrivateCallbacks ()
91 foreach (var de in dict) {
92 CacheItem item = de.Value.Value;
93 if (item == null || item.Disabled)
96 if (item.OnRemoveCallback != null) {
98 item.OnRemoveCallback (de.Key, item.Value, CacheItemRemovedReason.Removed);
100 //TODO: anything to be done here?
106 // Must ALWAYS be called with the owner's write lock held
107 public List <CacheItem> SelectItems (SelectItemsQualifier qualifier)
109 var ret = new List <CacheItem> ();
111 foreach (LinkedListNode <CacheItem> node in dict.Values) {
112 CacheItem item = node.Value;
114 if (qualifier (item))
121 // Must ALWAYS be called with the owner's read lock held
122 public List <CacheItem> ToList ()
124 var ret = new List <CacheItem> ();
129 foreach (LinkedListNode <CacheItem> node in dict.Values)
130 ret.Add (node.Value);
135 public void Remove (string key)
140 LinkedListNode <CacheItem> node;
141 if (!dict.TryGetValue (key, out node))
144 CacheItem item = node.Value;
147 if (item == null || item.Priority != CacheItemPriority.NotRemovable) {
148 revdict.Remove (node);
153 public CacheItem this [string key] {
158 LinkedListNode<CacheItem> node;
161 if (dict.TryGetValue (key, out node)){
163 if (item == null || item.Priority != CacheItemPriority.NotRemovable) {
165 list.AddFirst (node);
175 LinkedListNode<CacheItem> node;
177 if (dict.TryGetValue (key, out node)){
178 // If we already have a key, move it to the front
180 if (value == null || value.Priority != CacheItemPriority.NotRemovable)
181 list.AddFirst (node);
183 revdict.Remove (node);
188 needsEviction = dict.Count >= highWaterMark;
191 node = new LinkedListNode<CacheItem> (value);
192 if (value == null || value.Priority != CacheItemPriority.NotRemovable) {
193 list.AddFirst (node);
194 revdict [node] = key;