mcs/class/monodoc/Mono.Utilities/LRUCache.cs

   1 /*
   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
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  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.
  16  */
  17
  18 using System;
  19 using System.Collections.Generic;
  20
  21 namespace Mono.Utilities
  22 {
  23     public class LRUCache<TKey, TValue>
  24     {
  25             [ThreadStatic]
  26             static LRUCache<TKey, TValue> deflt;
  27
  28             public static LRUCache<TKey, TValue> Default {
  29                     get {
  30                             return deflt != null ? deflt : (deflt = new LRUCache<TKey, TValue> (5));
  31                     }
  32             }
  33
  34         int capacity;
  35         LinkedList<ListValueEntry<TKey, TValue>> list;
  36         Dictionary<TKey, LinkedListNode<ListValueEntry<TKey, TValue>>> lookup;
  37         LinkedListNode<ListValueEntry<TKey, TValue>> openNode;
  38
  39         public LRUCache (int capacity)
  40         {
  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)));
  45         }
  46
  47         public void Put (TKey key, TValue value)
  48         {
  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);
  54
  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;
  58
  59                     // remove from list & dictionary
  60                     this.list.RemoveLast();
  61                     this.lookup.Remove(this.openNode.Value.ItemKey);
  62                 } else {
  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)));
  65                 }
  66             }
  67         }
  68
  69         public TValue Get (TKey key)
  70         {
  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;
  77         }
  78
  79         class ListValueEntry<K, V> where K : TKey
  80                                    where V : TValue
  81         {
  82             internal V ItemValue;
  83             internal K ItemKey;
  84
  85             internal ListValueEntry(K key, V value)
  86             {
  87                 this.ItemKey = key;
  88                 this.ItemValue = value;
  89             }
  90         }
  91     }
  92 }