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
|
/* ****************************************************************************
*
* Copyright (c) Microsoft Corporation.
*
* This source code is subject to terms and conditions of the Microsoft Public License. A
* copy of the license can be found in the License.html file at the root of this distribution. If
* you cannot locate the Microsoft Public License, please send an email to
* dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
* by the terms of the Microsoft Public License.
*
* You must not remove this notice, or any other, from this software.
*
*
* ***************************************************************************/
using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
namespace Microsoft.Scripting.Utils {
/// <summary>
/// Provides a dictionary-like object used for caches which holds onto a maximum
/// number of elements specified at construction time.
///
/// This class is not thread safe.
/// </summary>
public class CacheDict<TKey, TValue> {
private readonly Dictionary<TKey, KeyInfo> _dict = new Dictionary<TKey, KeyInfo>();
private readonly LinkedList<TKey> _list = new LinkedList<TKey>();
private readonly int _maxSize;
/// <summary>
/// Creates a dictionary-like object used for caches.
/// </summary>
/// <param name="maxSize">The maximum number of elements to store.</param>
public CacheDict(int maxSize) {
_maxSize = maxSize;
}
/// <summary>
/// Tries to get the value associated with 'key', returning true if it's found and
/// false if it's not present.
/// </summary>
public bool TryGetValue(TKey key, out TValue value) {
KeyInfo storedValue;
if (_dict.TryGetValue(key, out storedValue)) {
LinkedListNode<TKey> node = storedValue.List;
if (node.Previous != null) {
// move us to the head of the list...
_list.Remove(node);
_list.AddFirst(node);
}
value = storedValue.Value;
return true;
}
value = default(TValue);
return false;
}
/// <summary>
/// Adds a new element to the cache, replacing and moving it to the front if the
/// element is already present.
/// </summary>
public void Add(TKey key, TValue value) {
KeyInfo keyInfo;
if (_dict.TryGetValue(key, out keyInfo)) {
// remove original entry from the linked list
_list.Remove(keyInfo.List);
} else if (_list.Count == _maxSize) {
// we've reached capacity, remove the last used element...
LinkedListNode<TKey> node = _list.Last;
_list.RemoveLast();
bool res = _dict.Remove(node.Value);
Debug.Assert(res);
}
// add the new entry to the head of the list and into the dictionary
LinkedListNode<TKey> listNode = new LinkedListNode<TKey>(key);
_list.AddFirst(listNode);
_dict[key] = new CacheDict<TKey, TValue>.KeyInfo(value, listNode);
}
/// <summary>
/// Returns the value associated with the given key, or throws KeyNotFoundException
/// if the key is not present.
/// </summary>
public TValue this[TKey key] {
get {
TValue res;
if (TryGetValue(key, out res)) {
return res;
}
throw new KeyNotFoundException();
}
set {
Add(key, value);
}
}
private struct KeyInfo {
internal readonly TValue Value;
internal readonly LinkedListNode<TKey> List;
internal KeyInfo(TValue value, LinkedListNode<TKey> list) {
Value = value;
List = list;
}
}
}
}
|
