2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
9 * http://www.apache.org/licenses/LICENSE-2.0
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
19 using System.Collections.Generic;
21 namespace Mono.Utilities
23 public class LRUCache<TKey, TValue>
26 static LRUCache<TKey, TValue> deflt;
28 public static LRUCache<TKey, TValue> Default {
30 return deflt != null ? deflt : (deflt = new LRUCache<TKey, TValue> (5));
35 LinkedList<ListValueEntry<TKey, TValue>> list;
36 Dictionary<TKey, LinkedListNode<ListValueEntry<TKey, TValue>>> lookup;
37 LinkedListNode<ListValueEntry<TKey, TValue>> openNode;
39 public LRUCache (int capacity)
41 this.capacity = capacity;
42 this.list = new LinkedList<ListValueEntry<TKey, TValue>>();
43 this.lookup = new Dictionary<TKey, LinkedListNode<ListValueEntry<TKey, TValue>>> (capacity + 1);
44 this.openNode = new LinkedListNode<ListValueEntry<TKey, TValue>>(new ListValueEntry<TKey, TValue> (default(TKey), default(TValue)));
47 public void Put (TKey key, TValue value)
49 if (Get(key) == null) {
50 this.openNode.Value.Itemkey = key;
51 this.openNode.Value.Itemvalue = value;
52 this.list.AddFirst (this.openNode);
53 this.lookup.Add (key, this.openNode);
55 if (this.list.Count > this.capacity) {
56 // last node is to be removed and saved for the next addition to the cache
57 this.openNode = this.list.Last;
59 // remove from list & dictionary
60 this.list.RemoveLast();
61 this.lookup.Remove(this.openNode.Value.Itemkey);
63 // still filling the cache, create a new open node for the next time
64 this.openNode = new LinkedListNode<ListValueEntry<Tkey, Tvalue>>(new ListValueEntry<Tkey, Tvalue>(default(Tkey), default(Tvalue)));
69 public TValue Get (TKey key)
71 LinkedListNode<ListValueEntry<TKey, TValue>> node = null;
72 if (!this.lookup.TryGetValue (key, out node))
73 return default (TValue);
74 this.list.Remove (node);
75 this.list.AddFirst (node);
76 return node.Value.ItemValue;
79 class ListValueEntry<K, V> where K : TKey
85 internal ListValueEntry(K key, V value)
88 this.ItemValue = value;