mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Utils/CacheDict.cs

   1 /* ****************************************************************************
   2  *
   3  * Copyright (c) Microsoft Corporation.
   4  *
   5  * This source code is subject to terms and conditions of the Microsoft Public License. A
   6  * copy of the license can be found in the License.html file at the root of this distribution. If
   7  * you cannot locate the  Microsoft Public License, please send an email to
   8  * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
   9  * by the terms of the Microsoft Public License.
  10  *
  11  * You must not remove this notice, or any other, from this software.
  12  *
  13  *
  14  * ***************************************************************************/
  15
  16 #if CODEPLEX_40
  17 using System;
  18 #else
  19 using System; using Microsoft;
  20 #endif
  21 using System.Collections.Generic;
  22 using System.Text;
  23 using System.Diagnostics;
  24
  25 #if CODEPLEX_40
  26 namespace System.Dynamic.Utils {
  27 #else
  28 namespace Microsoft.Scripting.Utils {
  29 #endif
  30     /// <summary>
  31     /// Provides a dictionary-like object used for caches which holds onto a maximum
  32     /// number of elements specified at construction time.
  33     ///
  34     /// This class is not thread safe.
  35     /// </summary>
  36     internal class CacheDict<TKey, TValue> {
  37         private readonly Dictionary<TKey, KeyInfo> _dict = new Dictionary<TKey, KeyInfo>();
  38         private readonly LinkedList<TKey> _list = new LinkedList<TKey>();
  39         private readonly int _maxSize;
  40
  41         /// <summary>
  42         /// Creates a dictionary-like object used for caches.
  43         /// </summary>
  44         /// <param name="maxSize">The maximum number of elements to store.</param>
  45         internal CacheDict(int maxSize) {
  46             _maxSize = maxSize;
  47         }
  48
  49         /// <summary>
  50         /// Tries to get the value associated with 'key', returning true if it's found and
  51         /// false if it's not present.
  52         /// </summary>
  53         internal bool TryGetValue(TKey key, out TValue value) {
  54             KeyInfo storedValue;
  55             if (_dict.TryGetValue(key, out storedValue)) {
  56                 LinkedListNode<TKey> node = storedValue.List;
  57                 if (node.Previous != null) {
  58                     // move us to the head of the list...
  59                     _list.Remove(node);
  60                     _list.AddFirst(node);
  61                 }
  62
  63                 value = storedValue.Value;
  64                 return true;
  65             }
  66
  67             value = default(TValue);
  68             return false;
  69         }
  70
  71         /// <summary>
  72         /// Adds a new element to the cache, replacing and moving it to the front if the
  73         /// element is already present.
  74         /// </summary>
  75         internal void Add(TKey key, TValue value) {
  76             KeyInfo keyInfo;
  77             if (_dict.TryGetValue(key, out keyInfo)) {
  78                 // remove original entry from the linked list
  79                 _list.Remove(keyInfo.List);
  80             } else if (_list.Count == _maxSize) {
  81                 // we've reached capacity, remove the last used element...
  82                 LinkedListNode<TKey> node = _list.Last;
  83                 _list.RemoveLast();
  84                 bool res = _dict.Remove(node.Value);
  85                 Debug.Assert(res);
  86             }
  87
  88             // add the new entry to the head of the list and into the dictionary
  89             LinkedListNode<TKey> listNode = new LinkedListNode<TKey>(key);
  90             _list.AddFirst(listNode);
  91             _dict[key] = new CacheDict<TKey, TValue>.KeyInfo(value, listNode);
  92         }
  93
  94         /// <summary>
  95         /// Returns the value associated with the given key, or throws KeyNotFoundException
  96         /// if the key is not present.
  97         /// </summary>
  98         internal TValue this[TKey key] {
  99             get {
 100                 TValue res;
 101                 if (TryGetValue(key, out res)) {
 102                     return res;
 103                 }
 104                 throw new KeyNotFoundException();
 105             }
 106             set {
 107                 Add(key, value);
 108             }
 109         }
 110
 111         private struct KeyInfo {
 112             internal readonly TValue Value;
 113             internal readonly LinkedListNode<TKey> List;
 114
 115             internal KeyInfo(TValue value, LinkedListNode<TKey> list) {
 116                 Value = value;
 117                 List = list;
 118             }
 119         }
 120     }
 121 }