6854393539

Committed 13 Nov 2023 06:49PM UTC coverage: 98.616% (-0.06%) from 98.678%

Build # 6854393539

Build Type

push

github

Committed by

web-flow

Commit Message

Fix line endings (#474)

Run Details

939 of 968 branches covered (0.0%)

Branch coverage included in aggregate %.

999 of 1012 new or added lines in 10 files covered. (98.72%)

2 existing lines in 1 file now uncovered.

3835 of 3873 relevant lines covered (99.02%)

20699462.19 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

92.83

/BitFaster.Caching/Lru/ClassicLru.cs

﻿using System;
using System.Collections;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace BitFaster.Caching.Lru
{
    /// <summary>
    /// LRU implementation where Lookup operations are backed by a ConcurrentDictionary and the LRU list is protected
    /// by a global lock. All list operations performed within the lock are fast O(1) operations. 
    /// </summary>
    /// <remarks>
    /// Due to the lock protecting list operations, this class may suffer lock contention under heavy load.
    /// </remarks>
    /// <typeparam name="K">The type of the key</typeparam>
    /// <typeparam name="V">The type of the value</typeparam>
    public sealed class ClassicLru<K, V> : ICache<K, V>, IAsyncCache<K, V>, IBoundedPolicy, IEnumerable<KeyValuePair<K, V>>
    {
        private readonly int capacity;
        private readonly ConcurrentDictionary<K, LinkedListNode<LruItem>> dictionary;
        private readonly LinkedList<LruItem> linkedList = new();

        private readonly CacheMetrics metrics = new();
        private readonly CachePolicy policy;

        /// <summary>
        /// Initializes a new instance of the ClassicLru class with the specified capacity.
        /// </summary>
        /// <param name="capacity"></param>
        public ClassicLru(int capacity)
            : this(Defaults.ConcurrencyLevel, capacity, EqualityComparer<K>.Default)
        {
        }

        /// <summary>
        /// Initializes a new instance of the ClassicLru class with the specified concurrencyLevel, capacity and equality comparer.
        /// </summary>
        /// <param name="concurrencyLevel">The concurrency level.</param>
        /// <param name="capacity">The capacity.</param>
        /// <param name="comparer">The key comparer</param>
        /// <exception cref="ArgumentOutOfRangeException"></exception>
        /// <exception cref="ArgumentNullException"></exception>
        public ClassicLru(int concurrencyLevel, int capacity, IEqualityComparer<K> comparer)
        {
            if (capacity < 3)
                Throw.ArgOutOfRange(nameof(capacity), "Capacity must be greater than or equal to 3.");

            if (comparer == null)
                Throw.ArgNull(ExceptionArgument.comparer);

            this.capacity = capacity;
            int dictionaryCapacity = ConcurrentDictionarySize.Estimate(capacity);
            this.dictionary = new ConcurrentDictionary<K, LinkedListNode<LruItem>>(concurrencyLevel, dictionaryCapacity, comparer);
            this.policy = new CachePolicy(new Optional<IBoundedPolicy>(this), Optional<ITimePolicy>.None());
        }

        ///<inheritdoc/>
        public int Count => this.linkedList.Count;

        ///<inheritdoc/>
        public int Capacity => this.capacity;

        ///<inheritdoc/>
        public Optional<ICacheMetrics> Metrics => new(this.metrics);

        ///<inheritdoc/>
        public Optional<ICacheEvents<K, V>> Events => Optional<ICacheEvents<K, V>>.None();

        ///<inheritdoc/>
        public CachePolicy Policy => this.policy;

        /// <summary>
        /// Gets a collection containing the keys in the cache.
        /// </summary>
        public ICollection<K> Keys => this.dictionary.Keys;

        /// <summary>Returns an enumerator that iterates through the cache.</summary>
        /// <returns>An enumerator for the cache.</returns>
        /// <remarks>
        /// The enumerator returned from the cache is safe to use concurrently with
        /// reads and writes, however it does not represent a moment-in-time snapshot.  
        /// The contents exposed through the enumerator may contain modifications
        /// made after <see cref="GetEnumerator"/> was called.
        /// </remarks>
        public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
        {
            foreach (var kvp in this.dictionary)
            {
                yield return new KeyValuePair<K, V>(kvp.Key, kvp.Value.Value.Value);
            }
        }

        ///<inheritdoc/>
        public bool TryGet(K key, out V value)
        {
            Interlocked.Increment(ref this.metrics.requestTotalCount);

            if (dictionary.TryGetValue(key, out var node))
            {
                LockAndMoveToEnd(node);
                Interlocked.Increment(ref this.metrics.requestHitCount);
                value = node.Value.Value;
                return true;
            }

            value = default;
            return false;
        }

        private bool TryAdd(K key, V value)
        {
            var node = new LinkedListNode<LruItem>(new LruItem(key, value));

            if (this.dictionary.TryAdd(key, node))
            {
                LinkedListNode<LruItem> first = null;

                lock (this.linkedList)
                {
                    if (linkedList.Count >= capacity)
                    {
                        first = linkedList.First;
                        linkedList.RemoveFirst();
                    }

                    linkedList.AddLast(node);
                }

                // Remove from the dictionary outside the lock. This means that the dictionary at this moment
                // contains an item that is not in the linked list. If another thread fetches this item, 
                // LockAndMoveToEnd will ignore it, since it is detached. This means we potentially 'lose' an 
                // item just as it was about to move to the back of the LRU list and be preserved. The next request
                // for the same key will be a miss. Dictionary and list are eventually consistent.
                // However, all operations inside the lock are extremely fast, so contention is minimized.
                if (first != null)
                {
                    dictionary.TryRemove(first.Value.Key, out var removed);

                    Interlocked.Increment(ref this.metrics.evictedCount);
                    Disposer<V>.Dispose(removed.Value.Value);
                }

                return true;
            }

            return false;
        }

        ///<inheritdoc/>
        public V GetOrAdd(K key, Func<K, V> valueFactory)
        {
            if (this.TryGet(key, out var value))
            {
                return value;
            }

            value = valueFactory(key);

            if (TryAdd(key, value))
            {
                return value;
            }

            return this.GetOrAdd(key, valueFactory);
        }

        /// <summary>
        /// Adds a key/value pair to the cache if the key does not already exist. Returns the new value, or the 
        /// existing value if the key already exists.
        /// </summary>
        /// <typeparam name="TArg">The type of an argument to pass into valueFactory.</typeparam>
        /// <param name="key">The key of the element to add.</param>
        /// <param name="valueFactory">The factory function used to generate a value for the key.</param>
        /// <param name="factoryArgument">An argument value to pass into valueFactory.</param>
        /// <returns>The value for the key. This will be either the existing value for the key if the key is already 
        /// in the cache, or the new value if the key was not in the cache.</returns>
        public V GetOrAdd<TArg>(K key, Func<K, TArg, V> valueFactory, TArg factoryArgument)
        {
            if (this.TryGet(key, out var value))
            {
                return value;
            }

            value = valueFactory(key, factoryArgument);

            if (TryAdd(key, value))
            {
                return value;
            }

            return this.GetOrAdd(key, valueFactory, factoryArgument);
        }

        ///<inheritdoc/>
        public async ValueTask<V> GetOrAddAsync(K key, Func<K, Task<V>> valueFactory)
        {
            if (this.TryGet(key, out var value))
            {
                return value;
            }

            value = await valueFactory(key).ConfigureAwait(false);

            if (TryAdd(key, value))
            {
                return value;
            }

            return await this.GetOrAddAsync(key, valueFactory).ConfigureAwait(false);
        }

        /// <summary>
        /// Adds a key/value pair to the cache if the key does not already exist. Returns the new value, or the 
        /// existing value if the key already exists.
        /// </summary>
        /// <typeparam name="TArg">The type of an argument to pass into valueFactory.</typeparam>
        /// <param name="key">The key of the element to add.</param>
        /// <param name="valueFactory">The factory function used to asynchronously generate a value for the key.</param>
        /// <param name="factoryArgument">An argument value to pass into valueFactory.</param>
        /// <returns>A task that represents the asynchronous GetOrAdd operation.</returns>
        public async ValueTask<V> GetOrAddAsync<TArg>(K key, Func<K, TArg, Task<V>> valueFactory, TArg factoryArgument)
        {
            if (this.TryGet(key, out var value))
            {
                return value;
            }

            value = await valueFactory(key, factoryArgument).ConfigureAwait(false);

            if (TryAdd(key, value))
            {
                return value;
            }

            return await this.GetOrAddAsync(key, valueFactory, factoryArgument).ConfigureAwait(false);
        }

        /// <summary>
        /// Attempts to remove the specified key value pair.
        /// </summary>
        /// <param name="item">The item to remove.</param>
        /// <returns>true if the item was removed successfully; otherwise, false.</returns>
        public bool TryRemove(KeyValuePair<K, V> item)
        {
            if (this.dictionary.TryGetValue(item.Key, out var node))
            {
                if (EqualityComparer<V>.Default.Equals(node.Value.Value, item.Value))
                {
                    var kvp = new KeyValuePair<K, LinkedListNode<LruItem>>(item.Key, node);

#if NET6_0_OR_GREATER
                    if (this.dictionary.TryRemove(kvp))
#else
                    // https://devblogs.microsoft.com/pfxteam/little-known-gems-atomic-conditional-removals-from-concurrentdictionary/
                    if (((ICollection<KeyValuePair<K, LinkedListNode<LruItem>>>)this.dictionary).Remove(kvp))
#endif
                    {
                        OnRemove(node);
                        return true;
                    }
                }
            }

            return false;
        }

        /// <summary>
        /// Attempts to remove and return the value that has the specified key.
        /// </summary>
        /// <param name="key">The key of the element to remove.</param>
        /// <param name="value">When this method returns, contains the object removed, or the default value of the value type if key does not exist.</param>
        /// <returns>true if the object was removed successfully; otherwise, false.</returns>
        public bool TryRemove(K key, out V value)
        {
            if (dictionary.TryRemove(key, out var node))
            {
                OnRemove(node);
                value = node.Value.Value;
                return true;
            }

            value = default;
            return false;

        }

        ///<inheritdoc/>
        public bool TryRemove(K key)
        {
            return TryRemove(key, out var _);
        }

        private void OnRemove(LinkedListNode<LruItem> node)
        {
            // If the node has already been removed from the list, ignore.
            // E.g. thread A reads x from the dictionary. Thread B adds a new item, removes x from 
            // the List & Dictionary. Now thread A will try to move x to the end of the list.
            if (node.List != null)
            {
                lock (this.linkedList)
                {
                    if (node.List != null)
                    {
                        linkedList.Remove(node);
                    }
                }
            }

            Disposer<V>.Dispose(node.Value.Value);
        }

        ///<inheritdoc/>
        ///<remarks>Note: Calling this method does not affect LRU order.</remarks>
        public bool TryUpdate(K key, V value)
        {
            if (this.dictionary.TryGetValue(key, out var node))
            {
                node.Value.Value = value;
                Interlocked.Increment(ref this.metrics.updatedCount);
                return true;
            }

            return false;
        }

        ///<inheritdoc/>
        ///<remarks>Note: Updates to existing items do not affect LRU order. Added items are at the top of the LRU.</remarks>
        public void AddOrUpdate(K key, V value)
        {
            // first, try to update
            if (this.dictionary.TryGetValue(key, out var existingNode))
            {
                existingNode.Value.Value = value;
                Interlocked.Increment(ref this.metrics.updatedCount);
                return;
            }

            // then try add
            var newNode = new LinkedListNode<LruItem>(new LruItem(key, value));

            if (this.dictionary.TryAdd(key, newNode))
            {
                LinkedListNode<LruItem> first = null;

                lock (this.linkedList)
                {
                    if (linkedList.Count >= capacity)
                    {
                        first = linkedList.First;
                        linkedList.RemoveFirst();
                    }

                    linkedList.AddLast(newNode);
                }

                // Remove from the dictionary outside the lock. This means that the dictionary at this moment
                // contains an item that is not in the linked list. If another thread fetches this item, 
                // LockAndMoveToEnd will ignore it, since it is detached. This means we potentially 'lose' an 
                // item just as it was about to move to the back of the LRU list and be preserved. The next request
                // for the same key will be a miss. Dictionary and list are eventually consistent.
                // However, all operations inside the lock are extremely fast, so contention is minimized.
                if (first != null)
                {
                    dictionary.TryRemove(first.Value.Key, out var removed);

                    Interlocked.Increment(ref this.metrics.evictedCount);
                    Disposer<V>.Dispose(removed.Value.Value);
                }

                return;
            }

            // if both update and add failed there was a race, try again
            AddOrUpdate(key, value);
        }

        ///<inheritdoc/>
        public void Clear()
        {
            // take a key snapshot
            var keys = this.dictionary.Keys.ToList();

            // remove all keys in the snapshot - this correctly handles disposable values
            foreach (var key in keys)
            {
                TryRemove(key);
            }
        }

        ///<inheritdoc/>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="itemCount"/> is less than 0./</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="itemCount"/> is greater than capacity./</exception>
        public void Trim(int itemCount)
        {
            if (itemCount < 1 || itemCount > this.capacity)
            {
                Throw.ArgOutOfRange(nameof(itemCount), "itemCount must be greater than or equal to one, and less than the capacity of the cache.");
            }

            for (int i = 0; i < itemCount; i++)
            {
                LinkedListNode<LruItem> first = null;

                lock (this.linkedList)
                {
                    if (linkedList.Count > 0)
                    {
                        first = linkedList.First;
                        linkedList.RemoveFirst();
                    }
                }

                if (first != null)
                {
                    dictionary.TryRemove(first.Value.Key, out var removed);
                    Disposer<V>.Dispose(removed.Value.Value);
                }
            }
        }

        // Thead A reads x from the dictionary. Thread B adds a new item. Thread A moves x to the end. Thread B now removes the new first Node (removal is atomic on both data structures).
        private void LockAndMoveToEnd(LinkedListNode<LruItem> node)
        {
            // If the node has already been removed from the list, ignore.
            // E.g. thread A reads x from the dictionary. Thread B adds a new item, removes x from 
            // the List & Dictionary. Now thread A will try to move x to the end of the list.
            if (node.List == null)
            {
                return;
            }

            lock (this.linkedList)
            {
                if (node.List == null)
                {
                    return;
                }

                linkedList.Remove(node);
                linkedList.AddLast(node);
            }
        }

        /// <summary>Returns an enumerator that iterates through the cache.</summary>
        /// <returns>An enumerator for the cache.</returns>
        /// <remarks>
        /// The enumerator returned from the cache is safe to use concurrently with
        /// reads and writes, however it does not represent a moment-in-time snapshot.  
        /// The contents exposed through the enumerator may contain modifications
        /// made after <see cref="GetEnumerator"/> was called.
        /// </remarks>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((ClassicLru<K, V>)this).GetEnumerator();
        }

        private class LruItem
        {
            public LruItem(K k, V v)
            {
                Key = k;
                Value = v;
            }

            public K Key { get; }

            public V Value { get; set; }
        }

        private class CacheMetrics : ICacheMetrics
        {
            public long requestHitCount;
            public long requestTotalCount;
            public long updatedCount;
            public long evictedCount;

            public double HitRatio => (double)requestHitCount / (double)requestTotalCount;

            public long Total => requestTotalCount;

            public long Hits => requestHitCount;

            public long Misses => requestTotalCount - requestHitCount;

            public long Evicted => evictedCount;

            public long Updated => updatedCount;
        }
    }
}

1	using System;
2	using System.Collections;
3	using System.Collections.Concurrent;
4	using System.Collections.Generic;
5	using System.Linq;
6	using System.Threading;
7	using System.Threading.Tasks;
8
9	namespace BitFaster.Caching.Lru
10	{
11	/// <summary>
12	/// LRU implementation where Lookup operations are backed by a ConcurrentDictionary and the LRU list is protected
13	/// by a global lock. All list operations performed within the lock are fast O(1) operations.
14	/// </summary>
15	/// <remarks>
16	/// Due to the lock protecting list operations, this class may suffer lock contention under heavy load.
17	/// </remarks>
18	/// <typeparam name="K">The type of the key</typeparam>
19	/// <typeparam name="V">The type of the value</typeparam>
20	public sealed class ClassicLru<K, V> : ICache<K, V>, IAsyncCache<K, V>, IBoundedPolicy, IEnumerable<KeyValuePair<K, V>>
21	{
22	private readonly int capacity;
23	private readonly ConcurrentDictionary<K, LinkedListNode<LruItem>> dictionary;
24	private readonly LinkedList<LruItem> linkedList = new();	201✔
25
26	private readonly CacheMetrics metrics = new();	201✔
27	private readonly CachePolicy policy;
28
29	/// <summary>
30	/// Initializes a new instance of the ClassicLru class with the specified capacity.
31	/// </summary>
32	/// <param name="capacity"></param>
33	public ClassicLru(int capacity)
34	: this(Defaults.ConcurrencyLevel, capacity, EqualityComparer<K>.Default)	6✔
35	{	6✔
36	}	6✔
37
38	/// <summary>
39	/// Initializes a new instance of the ClassicLru class with the specified concurrencyLevel, capacity and equality comparer.
40	/// </summary>
41	/// <param name="concurrencyLevel">The concurrency level.</param>
42	/// <param name="capacity">The capacity.</param>
43	/// <param name="comparer">The key comparer</param>
44	/// <exception cref="ArgumentOutOfRangeException"></exception>
45	/// <exception cref="ArgumentNullException"></exception>
46	public ClassicLru(int concurrencyLevel, int capacity, IEqualityComparer<K> comparer)	201✔
47	{	201✔
48	if (capacity < 3)	201✔
49	Throw.ArgOutOfRange(nameof(capacity), "Capacity must be greater than or equal to 3.");	3✔
50
51	if (comparer == null)	198✔
52	Throw.ArgNull(ExceptionArgument.comparer);	3✔
53
54	this.capacity = capacity;	195✔
55	int dictionaryCapacity = ConcurrentDictionarySize.Estimate(capacity);	195✔
56	this.dictionary = new ConcurrentDictionary<K, LinkedListNode<LruItem>>(concurrencyLevel, dictionaryCapacity, comparer);	195✔
57	this.policy = new CachePolicy(new Optional<IBoundedPolicy>(this), Optional<ITimePolicy>.None());	192✔
58	}	192✔
59
60	///<inheritdoc/>
61	public int Count => this.linkedList.Count;	30✔
62
63	///<inheritdoc/>
64	public int Capacity => this.capacity;	3✔
65
66	///<inheritdoc/>
67	public Optional<ICacheMetrics> Metrics => new(this.metrics);	27✔
68
69	///<inheritdoc/>
70	public Optional<ICacheEvents<K, V>> Events => Optional<ICacheEvents<K, V>>.None();	3✔
71
72	///<inheritdoc/>
73	public CachePolicy Policy => this.policy;	3✔
74
75	/// <summary>
76	/// Gets a collection containing the keys in the cache.
77	/// </summary>
78	public ICollection<K> Keys => this.dictionary.Keys;	12✔
79
80	/// <summary>Returns an enumerator that iterates through the cache.</summary>
81	/// <returns>An enumerator for the cache.</returns>
82	/// <remarks>
83	/// The enumerator returned from the cache is safe to use concurrently with
84	/// reads and writes, however it does not represent a moment-in-time snapshot.
85	/// The contents exposed through the enumerator may contain modifications
86	/// made after <see cref="GetEnumerator"/> was called.
87	/// </remarks>
88	public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
89	{	6✔
90	foreach (var kvp in this.dictionary)	42✔
91	{	12✔
92	yield return new KeyValuePair<K, V>(kvp.Key, kvp.Value.Value.Value);	12✔
93	}	12✔
94	}	6✔
95
96	///<inheritdoc/>
97	public bool TryGet(K key, out V value)
98	{	267✔
99	Interlocked.Increment(ref this.metrics.requestTotalCount);	267✔
100
101	if (dictionary.TryGetValue(key, out var node))	267✔
102	{	57✔
103	LockAndMoveToEnd(node);	57✔
104	Interlocked.Increment(ref this.metrics.requestHitCount);	57✔
105	value = node.Value.Value;	57✔
106	return true;	57✔
107	}
108
109	value = default;	210✔
110	return false;	210✔
111	}	267✔
112
113	private bool TryAdd(K key, V value)
114	{	195✔
115	var node = new LinkedListNode<LruItem>(new LruItem(key, value));	195✔
116
117	if (this.dictionary.TryAdd(key, node))	195!
118	{	195✔
119	LinkedListNode<LruItem> first = null;	195✔
120
121	lock (this.linkedList)	195✔
122	{	195✔
123	if (linkedList.Count >= capacity)	195✔
124	{	21✔
125	first = linkedList.First;	21✔
126	linkedList.RemoveFirst();	21✔
127	}	21✔
128
129	linkedList.AddLast(node);	195✔
130	}	195✔
131
132	// Remove from the dictionary outside the lock. This means that the dictionary at this moment
133	// contains an item that is not in the linked list. If another thread fetches this item,
134	// LockAndMoveToEnd will ignore it, since it is detached. This means we potentially 'lose' an
135	// item just as it was about to move to the back of the LRU list and be preserved. The next request
136	// for the same key will be a miss. Dictionary and list are eventually consistent.
137	// However, all operations inside the lock are extremely fast, so contention is minimized.
138	if (first != null)	195✔
139	{	21✔
140	dictionary.TryRemove(first.Value.Key, out var removed);	21✔
141
142	Interlocked.Increment(ref this.metrics.evictedCount);	21✔
143	Disposer<V>.Dispose(removed.Value.Value);	21✔
144	}	21✔
145
146	return true;	195✔
147	}
148
NEW 149	return false;	×
150	}	195✔
151
152	///<inheritdoc/>
153	public V GetOrAdd(K key, Func<K, V> valueFactory)
154	{	165✔
155	if (this.TryGet(key, out var value))	165✔
156	{	18✔
157	return value;	18✔
158	}
159
160	value = valueFactory(key);	147✔
161
162	if (TryAdd(key, value))	147!
163	{	147✔
164	return value;	147✔
165	}
166
NEW 167	return this.GetOrAdd(key, valueFactory);	×
168	}	165✔
169
170	/// <summary>
171	/// Adds a key/value pair to the cache if the key does not already exist. Returns the new value, or the
172	/// existing value if the key already exists.
173	/// </summary>
174	/// <typeparam name="TArg">The type of an argument to pass into valueFactory.</typeparam>
175	/// <param name="key">The key of the element to add.</param>
176	/// <param name="valueFactory">The factory function used to generate a value for the key.</param>
177	/// <param name="factoryArgument">An argument value to pass into valueFactory.</param>
178	/// <returns>The value for the key. This will be either the existing value for the key if the key is already
179	/// in the cache, or the new value if the key was not in the cache.</returns>
180	public V GetOrAdd<TArg>(K key, Func<K, TArg, V> valueFactory, TArg factoryArgument)
181	{	6✔
182	if (this.TryGet(key, out var value))	6✔
183	{	3✔
184	return value;	3✔
185	}
186
187	value = valueFactory(key, factoryArgument);	3✔
188
189	if (TryAdd(key, value))	3!
190	{	3✔
191	return value;	3✔
192	}
193
NEW 194	return this.GetOrAdd(key, valueFactory, factoryArgument);	×
195	}	6✔
196
197	///<inheritdoc/>
198	public async ValueTask<V> GetOrAddAsync(K key, Func<K, Task<V>> valueFactory)
199	{	45✔
200	if (this.TryGet(key, out var value))	45✔
201	{	3✔
202	return value;	3✔
203	}
204
205	value = await valueFactory(key).ConfigureAwait(false);	42✔
206
207	if (TryAdd(key, value))	42!
208	{	42✔
209	return value;	42✔
210	}
211
NEW 212	return await this.GetOrAddAsync(key, valueFactory).ConfigureAwait(false);	×
213	}	45✔
214
215	/// <summary>
216	/// Adds a key/value pair to the cache if the key does not already exist. Returns the new value, or the
217	/// existing value if the key already exists.
218	/// </summary>
219	/// <typeparam name="TArg">The type of an argument to pass into valueFactory.</typeparam>
220	/// <param name="key">The key of the element to add.</param>
221	/// <param name="valueFactory">The factory function used to asynchronously generate a value for the key.</param>
222	/// <param name="factoryArgument">An argument value to pass into valueFactory.</param>
223	/// <returns>A task that represents the asynchronous GetOrAdd operation.</returns>
224	public async ValueTask<V> GetOrAddAsync<TArg>(K key, Func<K, TArg, Task<V>> valueFactory, TArg factoryArgument)
225	{	6✔
226	if (this.TryGet(key, out var value))	6✔
227	{	3✔
228	return value;	3✔
229	}
230
231	value = await valueFactory(key, factoryArgument).ConfigureAwait(false);	3✔
232
233	if (TryAdd(key, value))	3!
234	{	3✔
235	return value;	3✔
236	}
237
NEW 238	return await this.GetOrAddAsync(key, valueFactory, factoryArgument).ConfigureAwait(false);	×
239	}	6✔
240
241	/// <summary>
242	/// Attempts to remove the specified key value pair.
243	/// </summary>
244	/// <param name="item">The item to remove.</param>
245	/// <returns>true if the item was removed successfully; otherwise, false.</returns>
246	public bool TryRemove(KeyValuePair<K, V> item)
247	{	6✔
248	if (this.dictionary.TryGetValue(item.Key, out var node))	6✔
249	{	6✔
250	if (EqualityComparer<V>.Default.Equals(node.Value.Value, item.Value))	6✔
251	{	3✔
252	var kvp = new KeyValuePair<K, LinkedListNode<LruItem>>(item.Key, node);	3✔
253
254	#if NET6_0_OR_GREATER
255	if (this.dictionary.TryRemove(kvp))	2!
256	#else
257	// https://devblogs.microsoft.com/pfxteam/little-known-gems-atomic-conditional-removals-from-concurrentdictionary/
258	if (((ICollection<KeyValuePair<K, LinkedListNode<LruItem>>>)this.dictionary).Remove(kvp))	1!
259	#endif
260	{	3✔
261	OnRemove(node);	3✔
262	return true;	3✔
263	}
264	}	×
265	}	3✔
266
267	return false;	3✔
268	}	6✔
269
270	/// <summary>
271	/// Attempts to remove and return the value that has the specified key.
272	/// </summary>
273	/// <param name="key">The key of the element to remove.</param>
274	/// <param name="value">When this method returns, contains the object removed, or the default value of the value type if key does not exist.</param>
275	/// <returns>true if the object was removed successfully; otherwise, false.</returns>
276	public bool TryRemove(K key, out V value)
277	{	27✔
278	if (dictionary.TryRemove(key, out var node))	27✔
279	{	24✔
280	OnRemove(node);	24✔
281	value = node.Value.Value;	24✔
282	return true;	24✔
283	}
284
285	value = default;	3✔
286	return false;	3✔
287
288	}	27✔
289
290	///<inheritdoc/>
291	public bool TryRemove(K key)
292	{	24✔
293	return TryRemove(key, out var _);	24✔
294	}	24✔
295
296	private void OnRemove(LinkedListNode<LruItem> node)
297	{	27✔
298	// If the node has already been removed from the list, ignore.
299	// E.g. thread A reads x from the dictionary. Thread B adds a new item, removes x from
300	// the List & Dictionary. Now thread A will try to move x to the end of the list.
301	if (node.List != null)	27✔
302	{	27✔
303	lock (this.linkedList)	27✔
304	{	27✔
305	if (node.List != null)	27✔
306	{	27✔
307	linkedList.Remove(node);	27✔
308	}	27✔
309	}	27✔
310	}	27✔
311
312	Disposer<V>.Dispose(node.Value.Value);	27✔
313	}	27✔
314
315	///<inheritdoc/>
316	///<remarks>Note: Calling this method does not affect LRU order.</remarks>
317	public bool TryUpdate(K key, V value)
318	{	12✔
319	if (this.dictionary.TryGetValue(key, out var node))	12✔
320	{	6✔
321	node.Value.Value = value;	6✔
322	Interlocked.Increment(ref this.metrics.updatedCount);	6✔
323	return true;	6✔
324	}
325
326	return false;	6✔
327	}	12✔
328
329	///<inheritdoc/>
330	///<remarks>Note: Updates to existing items do not affect LRU order. Added items are at the top of the LRU.</remarks>
331	public void AddOrUpdate(K key, V value)
332	{	90✔
333	// first, try to update
334	if (this.dictionary.TryGetValue(key, out var existingNode))	90✔
335	{	3✔
336	existingNode.Value.Value = value;	3✔
337	Interlocked.Increment(ref this.metrics.updatedCount);	3✔
338	return;	3✔
339	}
340
341	// then try add
342	var newNode = new LinkedListNode<LruItem>(new LruItem(key, value));	87✔
343
344	if (this.dictionary.TryAdd(key, newNode))	87!
345	{	87✔
346	LinkedListNode<LruItem> first = null;	87✔
347
348	lock (this.linkedList)	87✔
349	{	87✔
350	if (linkedList.Count >= capacity)	87✔
351	{	9✔
352	first = linkedList.First;	9✔
353	linkedList.RemoveFirst();	9✔
354	}	9✔
355
356	linkedList.AddLast(newNode);	87✔
357	}	87✔
358
359	// Remove from the dictionary outside the lock. This means that the dictionary at this moment
360	// contains an item that is not in the linked list. If another thread fetches this item,
361	// LockAndMoveToEnd will ignore it, since it is detached. This means we potentially 'lose' an
362	// item just as it was about to move to the back of the LRU list and be preserved. The next request
363	// for the same key will be a miss. Dictionary and list are eventually consistent.
364	// However, all operations inside the lock are extremely fast, so contention is minimized.
365	if (first != null)	87✔
366	{	9✔
367	dictionary.TryRemove(first.Value.Key, out var removed);	9✔
368
369	Interlocked.Increment(ref this.metrics.evictedCount);	9✔
370	Disposer<V>.Dispose(removed.Value.Value);	9✔
371	}	9✔
372
373	return;	87✔
374	}
375
376	// if both update and add failed there was a race, try again
NEW 377	AddOrUpdate(key, value);	×
378	}	90✔
379
380	///<inheritdoc/>
381	public void Clear()
382	{	9✔
383	// take a key snapshot
384	var keys = this.dictionary.Keys.ToList();	9✔
385
386	// remove all keys in the snapshot - this correctly handles disposable values
387	foreach (var key in keys)	57✔
388	{	15✔
389	TryRemove(key);	15✔
390	}	15✔
391	}	9✔
392
393	///<inheritdoc/>
394	/// <exception cref="ArgumentOutOfRangeException"><paramref name="itemCount"/> is less than 0./</exception>
395	/// <exception cref="ArgumentOutOfRangeException"><paramref name="itemCount"/> is greater than capacity./</exception>
396	public void Trim(int itemCount)
397	{	21✔
398	if (itemCount < 1 \|\| itemCount > this.capacity)	21✔
399	{	6✔
400	Throw.ArgOutOfRange(nameof(itemCount), "itemCount must be greater than or equal to one, and less than the capacity of the cache.");	6✔
NEW 401	}	×
402
403	for (int i = 0; i < itemCount; i++)	90✔
404	{	30✔
405	LinkedListNode<LruItem> first = null;	30✔
406
407	lock (this.linkedList)	30✔
408	{	30✔
409	if (linkedList.Count > 0)	30✔
410	{	24✔
411	first = linkedList.First;	24✔
412	linkedList.RemoveFirst();	24✔
413	}	24✔
414	}	30✔
415
416	if (first != null)	30✔
417	{	24✔
418	dictionary.TryRemove(first.Value.Key, out var removed);	24✔
419	Disposer<V>.Dispose(removed.Value.Value);	24✔
420	}	24✔
421	}	30✔
422	}	15✔
423
424	// Thead A reads x from the dictionary. Thread B adds a new item. Thread A moves x to the end. Thread B now removes the new first Node (removal is atomic on both data structures).
425	private void LockAndMoveToEnd(LinkedListNode<LruItem> node)
426	{	57✔
427	// If the node has already been removed from the list, ignore.
428	// E.g. thread A reads x from the dictionary. Thread B adds a new item, removes x from
429	// the List & Dictionary. Now thread A will try to move x to the end of the list.
430	if (node.List == null)	57!
NEW 431	{	×
NEW 432	return;	×
433	}
434
435	lock (this.linkedList)	57✔
436	{	57✔
437	if (node.List == null)	57!
NEW 438	{	×
NEW 439	return;	×
440	}
441
442	linkedList.Remove(node);	57✔
443	linkedList.AddLast(node);	57✔
444	}	57✔
445	}	57✔
446
447	/// <summary>Returns an enumerator that iterates through the cache.</summary>
448	/// <returns>An enumerator for the cache.</returns>
449	/// <remarks>
450	/// The enumerator returned from the cache is safe to use concurrently with
451	/// reads and writes, however it does not represent a moment-in-time snapshot.
452	/// The contents exposed through the enumerator may contain modifications
453	/// made after <see cref="GetEnumerator"/> was called.
454	/// </remarks>
455	IEnumerator IEnumerable.GetEnumerator()
456	{	6✔
457	return ((ClassicLru<K, V>)this).GetEnumerator();	6✔
458	}	6✔
459
460	private class LruItem
461	{
462	public LruItem(K k, V v)	282✔
463	{	282✔
464	Key = k;	282✔
465	Value = v;	282✔
466	}	282✔
467
468	public K Key { get; }	54✔
469
470	public V Value { get; set; }	471✔
471	}
472
473	private class CacheMetrics : ICacheMetrics
474	{
475	public long requestHitCount;
476	public long requestTotalCount;
477	public long updatedCount;
478	public long evictedCount;
479
480	public double HitRatio => (double)requestHitCount / (double)requestTotalCount;	3✔
481
482	public long Total => requestTotalCount;	3✔
483
484	public long Hits => requestHitCount;	3✔
485
486	public long Misses => requestTotalCount - requestHitCount;	3✔
487
488	public long Evicted => evictedCount;	6✔
489
490	public long Updated => updatedCount;	6✔
491	}
492	}
493	}

bitfaster / BitFaster.Caching / 6854393539

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous