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
|
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
using System;
using System.Collections.Generic;
namespace Mono.Utilities
{
public class LRUCache<TKey, TValue>
{
[ThreadStatic]
static LRUCache<TKey, TValue> deflt;
public static LRUCache<TKey, TValue> Default {
get {
return deflt != null ? deflt : (deflt = new LRUCache<TKey, TValue> (5));
}
}
int capacity;
LinkedList<ListValueEntry<TKey, TValue>> list;
Dictionary<TKey, LinkedListNode<ListValueEntry<TKey, TValue>>> lookup;
LinkedListNode<ListValueEntry<TKey, TValue>> openNode;
public LRUCache (int capacity)
{
this.capacity = capacity;
this.list = new LinkedList<ListValueEntry<TKey, TValue>>();
this.lookup = new Dictionary<TKey, LinkedListNode<ListValueEntry<TKey, TValue>>> (capacity + 1);
this.openNode = new LinkedListNode<ListValueEntry<TKey, TValue>>(new ListValueEntry<TKey, TValue> (default(TKey), default(TValue)));
}
public void Put (TKey key, TValue value)
{
if (Get(key) == null) {
this.openNode.Value.Itemkey = key;
this.openNode.Value.Itemvalue = value;
this.list.AddFirst (this.openNode);
this.lookup.Add (key, this.openNode);
if (this.list.Count > this.capacity) {
// last node is to be removed and saved for the next addition to the cache
this.openNode = this.list.Last;
// remove from list & dictionary
this.list.RemoveLast();
this.lookup.Remove(this.openNode.Value.Itemkey);
} else {
// still filling the cache, create a new open node for the next time
this.openNode = new LinkedListNode<ListValueEntry<Tkey, Tvalue>>(new ListValueEntry<Tkey, Tvalue>(default(Tkey), default(Tvalue)));
}
}
}
public TValue Get (TKey key)
{
LinkedListNode<ListValueEntry<TKey, TValue>> node = null;
if (!this.lookup.TryGetValue (key, out node))
return default (TValue);
this.list.Remove (node);
this.list.AddFirst (node);
return node.Value.ItemValue;
}
class ListValueEntry<K, V> where K : TKey
where V : TValue
{
internal V ItemValue;
internal K ItemKey;
internal ListValueEntry(K key, V value)
{
this.ItemKey = key;
this.ItemValue = value;
}
}
}
}
|
