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