|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Numerics;
using System.Threading;
namespace System.Dynamic.Utils
{
/// <summary>
/// Provides a dictionary-like object used for caches which holds onto a maximum
/// number of elements specified at construction time.
/// </summary>
internal sealed class CacheDict<TKey, TValue> where TKey : notnull
{
// cache size is always ^2.
// items are placed at [hash ^ mask]
// new item will displace previous one at the same location.
private readonly int _mask;
private readonly Entry[] _entries;
// class, to ensure atomic updates.
private sealed class Entry
{
internal readonly int _hash;
internal readonly TKey _key;
internal readonly TValue _value;
internal Entry(int hash, TKey key, TValue value)
{
_hash = hash;
_key = key;
_value = value;
}
}
/// <summary>
/// Creates a dictionary-like object used for caches.
/// </summary>
/// <param name="size">The maximum number of elements to store will be this number aligned to next ^2.</param>
internal CacheDict(int size)
{
int alignedSize = (int)BitOperations.RoundUpToPowerOf2((uint)size);
_mask = alignedSize - 1;
_entries = new Entry[alignedSize];
}
/// <summary>
/// Tries to get the value associated with 'key', returning true if it's found and
/// false if it's not present.
/// </summary>
internal bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value)
{
int hash = key.GetHashCode();
int idx = hash & _mask;
Entry entry = Volatile.Read(ref _entries[idx]);
if (entry != null && entry._hash == hash && entry._key.Equals(key))
{
value = entry._value;
return true;
}
value = default;
return false;
}
/// <summary>
/// Adds a new element to the cache, possibly replacing some
/// element that is already present.
/// </summary>
internal void Add(TKey key, TValue value)
{
int hash = key.GetHashCode();
int idx = hash & _mask;
Entry entry = Volatile.Read(ref _entries[idx]);
if (entry == null || entry._hash != hash || !entry._key.Equals(key))
{
Volatile.Write(ref _entries[idx], new Entry(hash, key, value));
}
}
/// <summary>
/// Sets the value associated with the given key.
/// </summary>
internal TValue this[TKey key]
{
set
{
Add(key, value);
}
}
}
}
|