1 /* **************************************************************************** 2 * 3 * Copyright (c) Microsoft Corporation. 4 * 5 * This source code is subject to terms and conditions of the Apache License, Version 2.0. 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 Apache License, Version 2.0, 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 Apache License, Version 2.0. 10 * 11 * You must not remove this notice, or any other, from this software. 12 * 13 * 14 * ***************************************************************************/ 15 16 using System; 17 using System.Collections.Generic; 18 using System.Text; 19 using System.Threading; 20 using System.Diagnostics; 21 22 namespace System.Dynamic.Utils { 23 /// <summary> 24 /// Provides a dictionary-like object used for caches which holds onto a maximum 25 /// number of elements specified at construction time. 26 /// </summary> 27 internal class CacheDict<TKey, TValue> { 28 29 // cache size is always ^2. 30 // items are placed at [hash ^ mask] 31 // new item will displace previous one at the same location. 32 protected readonly int mask; 33 protected readonly Entry[] entries; 34 35 // class, to ensure atomic updates. 36 internal class Entry 37 { 38 internal readonly int hash; 39 internal readonly TKey key; 40 internal readonly TValue value; 41 Entry(int hash, TKey key, TValue value)42 internal Entry(int hash, TKey key, TValue value) 43 { 44 this.hash = hash; 45 this.key = key; 46 this.value = value; 47 } 48 } 49 50 /// <summary> 51 /// Creates a dictionary-like object used for caches. 52 /// </summary> 53 /// <param name="maxSize">The maximum number of elements to store will be this number aligned to next ^2.</param> CacheDict(int size)54 internal CacheDict(int size) { 55 var alignedSize = AlignSize(size); 56 this.mask = alignedSize - 1; 57 this.entries = new Entry[alignedSize]; 58 } 59 AlignSize(int size)60 private static int AlignSize(int size) 61 { 62 Debug.Assert(size > 0); 63 64 size--; 65 size |= size >> 1; 66 size |= size >> 2; 67 size |= size >> 4; 68 size |= size >> 8; 69 size |= size >> 16; 70 return size + 1; 71 } 72 73 /// <summary> 74 /// Tries to get the value associated with 'key', returning true if it's found and 75 /// false if it's not present. 76 /// </summary> TryGetValue(TKey key, out TValue value)77 internal bool TryGetValue(TKey key, out TValue value) { 78 int hash = key.GetHashCode(); 79 int idx = hash & mask; 80 81 var entry = Volatile.Read(ref this.entries[idx]); 82 if (entry != null && entry.hash == hash && entry.key.Equals(key)) 83 { 84 value = entry.value; 85 return true; 86 } 87 88 value = default(TValue); 89 return false; 90 } 91 92 /// <summary> 93 /// Adds a new element to the cache, possibly replacing some 94 /// element that is already present. 95 /// </summary> Add(TKey key, TValue value)96 internal void Add(TKey key, TValue value) { 97 var hash = key.GetHashCode(); 98 var idx = hash & mask; 99 100 var entry = Volatile.Read(ref this.entries[idx]); 101 if (entry == null || entry.hash != hash || !entry.key.Equals(key)) 102 { 103 Volatile.Write(ref entries[idx], new Entry(hash, key, value)); 104 } 105 } 106 107 /// <summary> 108 /// Returns the value associated with the given key, or throws KeyNotFoundException 109 /// if the key is not present. 110 /// </summary> 111 internal TValue this[TKey key] { 112 get { 113 TValue res; 114 if (TryGetValue(key, out res)) { 115 return res; 116 } 117 throw new KeyNotFoundException(); 118 } 119 set { 120 Add(key, value); 121 } 122 } 123 } 124 } 125