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