改造LRU Cache for Windows Phone 7

13719654321

　　LRU是Least Recently Used最近最少使用算法,即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。
　　关于操作系统的内存管理，如何节省利用容量不大的内存为最多的进程提供资源，一直是研究的重要方向。
　　而内存的虚拟存储管理，是现在最通用，最成功的方式——在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。
　　
　　不重复造轮子了 下面是C#方式写的开源代码，我们改造一下让他适用于 WP7
　　http://lrucache.codeplex.com/
　　
　　主要改造如下： 用lock 替代过期的线程锁定代码，我不需要时间参数来LRU 所以也删掉了时间检测尽量提升性能！
　　不多说代码如下：



  1 namespace Utilities
  2 {
  3     using System;
  4     using System.Collections.Generic;
  5     using System.Diagnostics;
  6     using System.Threading;
  7
  8     ////This class implements an LRU based cache. Uses a linked list to keep track of node usage
  9 ////Clients should use the following methods:
10 ////AddObject(TKey key, TValue cacheObject)
11 ////TValue GetObject(TKey key)
12     public class LruCache where TValue : class
13     {
14         private readonly Dictionary cachedNodesDictionary = new Dictionary();
15         private readonly LinkedList lruLinkedList = new LinkedList();
16
17         private readonly int maxSize;
18       //  private readonly TimeSpan timeOut;
19
20 // private static readonly ReaderWriterLockSlim rwl = new ReaderWriterLockSlim();
21
22 // private Timer cleanupTimer;
23
24         public LruCache(int maxCacheSize, int memoryRefreshInterval)
25         {
26           //  this.timeOut = itemExpiryTimeout;
27             this.maxSize = maxCacheSize;
28             AutoResetEvent autoEvent = new AutoResetEvent(false);
29            // TimerCallback tcb = this.RemoveExpiredElements;
30            // this.cleanupTimer = new Timer(tcb, autoEvent, 0, memoryRefreshInterval);
31         }
32
33         public void AddObject(TKey key, TValue cacheObject)
34         {
35             if (key == null)
36             {
37                 throw new ArgumentNullException("key");
38             }
39
40             //    Trace.WriteLine(string.Format("Adding a cache object with key: {0}", key.ToString()));
41 //  rwl.EnterWriteLock();
42             try
43             {
44                 lock (cacheObject)
45                 {
46                     NodeInfo node;
47                     if (this.cachedNodesDictionary.TryGetValue(key, out node))
48                     {
49                         this.Delete(node);
50                     }
51                     this.ShrinkToSize(this.maxSize - 1);
52                     this.CreateNodeandAddtoList(key, cacheObject);
53                 }
54             }
55             finally
56             {
57                 //rwl.ExitWriteLock();
58             }
59         }
60
61         public TValue GetObject(TKey key)
62         {
63             if (key == null)
64             {
65                 throw new ArgumentNullException("key");
66             }
67
68             TValue data = null;
69             NodeInfo node;
70             //  rwl.EnterReadLock();
71
72             try
73             {
74                 lock (key)
75                 {
76                     if (this.cachedNodesDictionary.TryGetValue(key, out node))
77                     {
78                         if (node != null)// && !node.IsExpired())
79                         {
80                             //Trace.WriteLine(string.Format("Cache hit for key: {0}", key.ToString()));
81                             node.AccessCount++;
82                             data = node.Value;
83
84                             if (node.AccessCount > 20)
85                             {
86                                 ThreadPool.QueueUserWorkItem(this.AddBeforeFirstNode, key);
87                             }
88                         }
89                     }
90                     else
91                     {
92                         //      Trace.WriteLine(string.Format("Cache miss for key: {0}", key.ToString()));
93                     }
94
95                     return data;
96                 }
97             }
98             finally
99             {
100                 // rwl.ExitReadLock();
101             }
102         }
103
104         private void RemoveExpiredElements(object stateInfo)
105         {
106          //   rwl.EnterWriteLock();
107             try
108             {
109                 lock (stateInfo)
110                 {
111                     while (this.lruLinkedList.Last != null)
112                     {
113                         NodeInfo node = this.lruLinkedList.Last.Value;
114                         if (node != null)// && node.IsExpired())
115                         {
116                             this.Delete(node);
117                         }
118                         else
119                         {
120                             break;
121                         }
122                     }
123                 }
124             }
125             finally
126             {
127                // rwl.ExitWriteLock();
128             }
129         }
130
131         private void CreateNodeandAddtoList(TKey userKey, TValue cacheObject)
132         {
133             NodeInfo node = new NodeInfo(userKey, cacheObject);//, (this.timeOut > DateTime.MaxValue.Subtract(DateTime.UtcNow) ? DateTime.MaxValue : DateTime.UtcNow.Add(this.timeOut)));
134
135             node.LLNode = this.lruLinkedList.AddFirst(node);
136             this.cachedNodesDictionary[userKey] = node;
137         }
138
139         private void AddBeforeFirstNode(object stateinfo)
140         {
141             //rwl.EnterWriteLock();
142             try
143             {
144                 lock (stateinfo)
145                 {
146                     TKey key = (TKey)stateinfo;
147                     NodeInfo nodeInfo;
148                     if (this.cachedNodesDictionary.TryGetValue(key, out nodeInfo))
149                     {
150                         if (nodeInfo != null && nodeInfo.AccessCount > 20)// && !nodeInfo.IsExpired()
151                         {
152                             if (nodeInfo.LLNode != this.lruLinkedList.First)
153                             {
154                                 this.lruLinkedList.Remove(nodeInfo.LLNode);
155                                 nodeInfo.LLNode = this.lruLinkedList.AddBefore(this.lruLinkedList.First, nodeInfo);
156                                 nodeInfo.AccessCount = 0;
157                             }
158                         }
159                     }
160                 }
161             }
162             finally
163             {
164                // rwl.ExitWriteLock();
165             }
166         }
167
168         private void ShrinkToSize(int desiredSize)
169         {
170             while (this.cachedNodesDictionary.Count > desiredSize)
171             {
172                 this.RemoveLeastValuableNode();
173             }
174         }
175
176         private void RemoveLeastValuableNode()
177         {
178             if (this.lruLinkedList.Last != null)
179             {
180                 NodeInfo node = this.lruLinkedList.Last.Value;
181                 this.Delete(node);
182             }
183         }
184
185         private void Delete(NodeInfo node)
186         {
187             // Trace.WriteLine(string.Format("Evicting object from cache for key: {0}", node.Key.ToString()));
188             this.lruLinkedList.Remove(node.LLNode);
189             this.cachedNodesDictionary.Remove(node.Key);
190         }
191
192         ////This class represents data stored in the LinkedList Node and Dictionary
193         private class NodeInfo
194         {
195             //private readonly DateTime timeOutTime;
196
197             internal NodeInfo(TKey key, TValue value)//, DateTime timeouttime)
198             {
199                 this.Key = key;
200                 this.Value = value;
201                // this.timeOutTime = timeouttime;
202             }
203
204             internal TKey Key { get; private set; }
205
206             internal TValue Value { get; private set; }
207
208             internal int AccessCount { get; set; }
209
210             internal LinkedListNode LLNode { get; set; }
211
212             //internal bool IsExpired()
213 //{
214 //    return DateTime.UtcNow >= this.timeOutTime;
215 //}
216         }
217     }
218 }
　　
测试代码：



1             LruCache cache = new LruCache(3, 1000);
2             cache.AddObject(1, "One");
3             cache.AddObject(2, "Two");
4             cache.AddObject(3, "Three");
5
6             ////insert one more, which will kick 1 out
7             cache.AddObject(4, "Four");
8             Debug.WriteLine("cache.GetObject(1)" + cache.GetObject(1));
9             Debug.WriteLine("cache.GetObject(4)===" + cache.GetObject(4));
　　
　　取图服务中应用流程：