• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

bitfaster / BitFaster.Caching / 25127507152

29 Apr 2026 06:47PM UTC coverage: 99.124% (-0.06%) from 99.181%
25127507152

Pull #794

github

web-flow
Merge df412d5ec into 5a56c90d7
Pull Request #794: Limit key count for soak test logging

1350 of 1382 branches covered (97.68%)

Branch coverage included in aggregate %.

3 of 3 new or added lines in 1 file covered. (100.0%)

3 existing lines in 1 file now uncovered.

5666 of 5696 relevant lines covered (99.47%)

59270783.39 hits per line

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

99.4
/BitFaster.Caching/Lru/ConcurrentLruCore.cs
1
using System;
2
using System.Collections;
3
using System.Collections.Concurrent;
4
using System.Collections.Generic;
5
using System.Diagnostics;
6
using System.Diagnostics.CodeAnalysis;
7
using System.Linq;
8
using System.Runtime.CompilerServices;
9
using System.Threading;
10
using System.Threading.Tasks;
11

12
namespace BitFaster.Caching.Lru
13
{
14
    /// <summary>
15
    /// A pseudo LRU based on the TU-Q eviction policy. The LRU list is composed of 3 segments: hot, warm and cold. 
16
    /// Cost of maintaining segments is amortized across requests. Items are only cycled when capacity is exceeded. 
17
    /// Pure read does not cycle items if all segments are within capacity constraints. There are no global locks. 
18
    /// On cache miss, a new item is added. Tail items in each segment are dequeued, examined, and are either enqueued 
19
    /// or discarded.
20
    /// The TU-Q scheme of hot, warm and cold is similar to that used in MemCached (https://memcached.org/blog/modern-lru/)
21
    /// and OpenBSD (https://flak.tedunangst.com/post/2Q-buffer-cache-algorithm), but does not use a background thread
22
    /// to maintain the internal queues.
23
    /// </summary>
24
    /// <remarks>
25
    /// Each segment has a capacity. When segment capacity is exceeded, items are moved as follows:
26
    /// <list type="number">
27
    ///   <item><description>New items are added to hot, WasAccessed = false.</description></item>
28
    ///   <item><description>When items are accessed, update WasAccessed = true.</description></item>
29
    ///   <item><description>When items are moved WasAccessed is set to false.</description></item>
30
    ///   <item><description>When hot is full, hot tail is moved to either Warm or Cold depending on WasAccessed.</description></item>
31
    ///   <item><description>When warm is full, warm tail is moved to warm head or cold depending on WasAccessed.</description></item>
32
    ///   <item><description>When cold is full, cold tail is moved to warm head or removed from dictionary on depending on WasAccessed.</description></item>
33
    ///</list>
34
    /// </remarks>
35
    public class ConcurrentLruCore<K, V, I, P, T> : ICacheExt<K, V>, IAsyncCacheExt<K, V>, IEnumerable<KeyValuePair<K, V>>
36
        where K : notnull
37
        where I : LruItem<K, V>
38
        where P : struct, IItemPolicy<K, V, I>
39
        where T : struct, ITelemetryPolicy<K, V>
40
    {
41
        private readonly ConcurrentDictionary<K, I> dictionary;
42

43
        private readonly ConcurrentQueue<I> hotQueue;
44
        private readonly ConcurrentQueue<I> warmQueue;
45
        private readonly ConcurrentQueue<I> coldQueue;
46

47
        // maintain count outside ConcurrentQueue, since ConcurrentQueue.Count holds a global lock
48
        private PaddedQueueCount counter;
49

50
        private readonly ICapacityPartition capacity;
51

52
        private readonly P itemPolicy;
53
        private bool isWarm = false;
2,783✔
54

55
        /// <summary>
56
        /// The telemetry policy.
57
        /// </summary>
58
        /// <remarks>
59
        /// Since T is a struct, making it readonly will force the runtime to make defensive copies
60
        /// if mutate methods are called. Therefore, field must be mutable to maintain count.
61
        /// </remarks>
62
        protected T telemetryPolicy;
63

64
        /// <summary>
65
        /// Initializes a new instance of the ConcurrentLruCore class with the specified concurrencyLevel, capacity, equality comparer, item policy and telemetry policy.
66
        /// </summary>
67
        /// <param name="concurrencyLevel">The concurrency level.</param>
68
        /// <param name="capacity">The capacity.</param>
69
        /// <param name="comparer">The equality comparer.</param>
70
        /// <param name="itemPolicy">The item policy.</param>
71
        /// <param name="telemetryPolicy">The telemetry policy.</param>
72
        /// <exception cref="ArgumentNullException"></exception>
73
        public ConcurrentLruCore(
2,783✔
74
            int concurrencyLevel,
2,783✔
75
            ICapacityPartition capacity,
2,783✔
76
            IEqualityComparer<K> comparer,
2,783✔
77
            P itemPolicy,
2,783✔
78
            T telemetryPolicy)
2,783✔
79
        {
2,783✔
80
            if (capacity == null)
2,783✔
81
                Throw.ArgNull(ExceptionArgument.capacity);
5✔
82

83
            if (comparer == null)
2,778✔
84
                Throw.ArgNull(ExceptionArgument.comparer);
5✔
85

86
            capacity.Validate();
2,773✔
87
            this.capacity = capacity;
2,768✔
88

89
            this.hotQueue = new ConcurrentQueue<I>();
2,768✔
90
            this.warmQueue = new ConcurrentQueue<I>();
2,768✔
91
            this.coldQueue = new ConcurrentQueue<I>();
2,768✔
92

93
            int dictionaryCapacity = ConcurrentDictionarySize.Estimate(this.Capacity);
2,768✔
94

95
            this.dictionary = new ConcurrentDictionary<K, I>(concurrencyLevel, dictionaryCapacity, comparer);
2,768✔
96
            this.itemPolicy = itemPolicy;
2,758✔
97
            this.telemetryPolicy = telemetryPolicy;
2,758✔
98
            this.telemetryPolicy.SetEventSource(this);
2,758✔
99
        }
2,758✔
100

101
        // No lock count: https://arbel.net/2013/02/03/best-practices-for-using-concurrentdictionary/
102
        ///<inheritdoc/>
103
        public int Count => this.dictionary.Where(i => !itemPolicy.ShouldDiscard(i.Value)).Count();
17,459,820✔
104

105
        ///<inheritdoc/>
106
        public int Capacity => this.capacity.Hot + this.capacity.Warm + this.capacity.Cold;
2,000,004,253✔
107

108
        ///<inheritdoc/>
109
        public Optional<ICacheMetrics> Metrics => CreateMetrics(this);
165✔
110

111
        ///<inheritdoc/>
112
        public Optional<ICacheEvents<K, V>> Events => CreateEvents(this);
1,624✔
113

114
        ///<inheritdoc/>
115
        public CachePolicy Policy => CreatePolicy(this);
345✔
116

117
        /// <summary>
118
        /// Gets the number of hot items.
119
        /// </summary>
120
        public int HotCount => Volatile.Read(ref this.counter.hot);
1,586,215✔
121

122
        /// <summary>
123
        /// Gets the number of warm items.
124
        /// </summary>
125
        public int WarmCount => Volatile.Read(ref this.counter.warm);
1,586,215✔
126

127
        /// <summary>
128
        /// Gets the number of cold items.
129
        /// </summary>
130
        public int ColdCount => Volatile.Read(ref this.counter.cold);
1,586,220✔
131

132
        /// <summary>
133
        /// Gets a collection containing the keys in the cache.
134
        /// </summary>
135
        public ICollection<K> Keys => this.dictionary.Keys;
1,050✔
136

137
#if NET9_0_OR_GREATER
138
        /// <inheritdoc/>
139
        public IEqualityComparer<K> Comparer => this.dictionary.Comparer;
92✔
140
#endif
141

142
        /// <summary>Returns an enumerator that iterates through the cache.</summary>
143
        /// <returns>An enumerator for the cache.</returns>
144
        /// <remarks>
145
        /// The enumerator returned from the cache is safe to use concurrently with
146
        /// reads and writes, however it does not represent a moment-in-time snapshot.  
147
        /// The contents exposed through the enumerator may contain modifications
148
        /// made after <see cref="GetEnumerator"/> was called.
149
        /// </remarks>
150
        public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
151
        {
315✔
152
            foreach (var kvp in this.dictionary)
1,620✔
153
            {
340✔
154
                if (!itemPolicy.ShouldDiscard(kvp.Value))
340✔
155
                {
325✔
156
                    yield return new KeyValuePair<K, V>(kvp.Key, kvp.Value.Value);
325✔
157
                }
320✔
158
            }
335✔
159
        }
310✔
160

161
        ///<inheritdoc/>
162
        public bool TryGet(K key, [MaybeNullWhen(false)] out V value)
163
        {
2,271,543,483✔
164
            if (dictionary.TryGetValue(key, out var item))
2,271,543,483✔
165
            {
2,017,305,061✔
166
                return GetOrDiscard(item, out value);
2,017,305,061✔
167
            }
168

169
            value = default;
254,238,422✔
170
            this.telemetryPolicy.IncrementMiss();
254,238,422✔
171
            return false;
254,238,422✔
172
        }
2,271,543,483✔
173

174
        // AggressiveInlining forces the JIT to inline policy.ShouldDiscard(). For LRU policy 
175
        // the first branch is completely eliminated due to JIT time constant propogation.
176
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
177
        private bool GetOrDiscard(I item, [MaybeNullWhen(false)] out V value)
178
        {
2,023,540,468✔
179
            if (this.itemPolicy.ShouldDiscard(item))
2,023,540,468✔
180
            {
4,400,511✔
181
                this.Move(item, ItemDestination.Remove, ItemRemovedReason.Evicted);
4,400,511✔
182
                this.telemetryPolicy.IncrementMiss();
4,400,511✔
183
                value = default;
4,400,511✔
184
                return false;
4,400,511✔
185
            }
186

187
            value = item.Value;
2,019,139,957✔
188

189
            this.itemPolicy.Touch(item);
2,019,139,957✔
190
            this.telemetryPolicy.IncrementHit();
2,019,139,957✔
191
            return true;
2,019,139,957✔
192
        }
2,023,540,468✔
193

194
        private bool TryAdd(K key, V value)
195
        {
298,165,077✔
196
            var newItem = this.itemPolicy.CreateItem(key, value);
298,165,077✔
197

198
            if (this.dictionary.TryAdd(key, newItem))
298,165,077✔
199
            {
291,451,538✔
200
                this.hotQueue.Enqueue(newItem);
291,451,538✔
201
                Cycle(Interlocked.Increment(ref counter.hot));
291,451,538✔
202
                return true;
291,451,538✔
203
            }
204

205
            Disposer<V>.Dispose(newItem.Value);
6,713,539✔
206
            return false;
6,713,539✔
207
        }
298,165,077✔
208

209
        ///<inheritdoc/>
210
        public V GetOrAdd(K key, Func<K, V> valueFactory)
211
        {
2,181,609,199✔
212
            while (true)
2,187,074,268✔
213
            {
2,187,074,268✔
214
                if (this.TryGet(key, out var value))
2,187,074,268✔
215
                {
2,005,285,739✔
216
                    return value;
2,005,285,739✔
217
                }
218

219
                // The value factory may be called concurrently for the same key, but the first write to the dictionary wins.
220
                value = valueFactory(key);
181,788,529✔
221

222
                if (TryAdd(key, value))
181,788,529✔
223
                {
176,323,460✔
224
                    return value;
176,323,460✔
225
                }
226
            }
5,465,069✔
227
        }
2,181,609,199✔
228

229
        /// <summary>
230
        /// Adds a key/value pair to the cache if the key does not already exist. Returns the new value, or the 
231
        /// existing value if the key already exists.
232
        /// </summary>
233
        /// <typeparam name="TArg">The type of an argument to pass into valueFactory.</typeparam>
234
        /// <param name="key">The key of the element to add.</param>
235
        /// <param name="valueFactory">The factory function used to generate a value for the key.</param>
236
        /// <param name="factoryArgument">An argument value to pass into valueFactory.</param>
237
        /// <returns>The value for the key. This will be either the existing value for the key if the key is already 
238
        /// in the cache, or the new value if the key was not in the cache.</returns>
239
        public V GetOrAdd<TArg>(K key, Func<K, TArg, V> valueFactory, TArg factoryArgument)
240
#if NET9_0_OR_GREATER
241
            where TArg : allows ref struct
242
#endif
243
        {
38,036,189✔
244
            while (true)
38,370,721✔
245
            {
38,370,721✔
246
                if (this.TryGet(key, out var value))
38,370,721✔
247
                {
1,102,001✔
248
                    return value;
1,102,001✔
249
                }
250

251
                // The value factory may be called concurrently for the same key, but the first write to the dictionary wins.
252
                value = valueFactory(key, factoryArgument);
37,268,720✔
253

254
                if (TryAdd(key, value))
37,268,720✔
255
                {
36,934,188✔
256
                    return value;
36,934,188✔
257
                }
258
            }
334,532✔
259
        }
38,036,189✔
260

261
        ///<inheritdoc/>
262
        public async ValueTask<V> GetOrAddAsync(K key, Func<K, Task<V>> valueFactory)
263
        {
20,000,384✔
264
            while (true)
20,199,532✔
265
            {
20,199,532✔
266
                if (this.TryGet(key, out var value))
20,199,532✔
267
                {
636,467✔
268
                    return value;
636,467✔
269
                }
270

271
                // The value factory may be called concurrently for the same key, but the first write to the dictionary wins.
272
                // This is identical logic in ConcurrentDictionary.GetOrAdd method.
273
                value = await valueFactory(key).ConfigureAwait(false);
19,563,065✔
274

275
                if (TryAdd(key, value))
19,563,050✔
276
                {
19,363,902✔
277
                    return value;
19,363,902✔
278
                }
279
            }
199,148✔
280
        }
20,000,369✔
281

282
        /// <summary>
283
        /// Adds a key/value pair to the cache if the key does not already exist. Returns the new value, or the 
284
        /// existing value if the key already exists.
285
        /// </summary>
286
        /// <typeparam name="TArg">The type of an argument to pass into valueFactory.</typeparam>
287
        /// <param name="key">The key of the element to add.</param>
288
        /// <param name="valueFactory">The factory function used to asynchronously generate a value for the key.</param>
289
        /// <param name="factoryArgument">An argument value to pass into valueFactory.</param>
290
        /// <returns>A task that represents the asynchronous GetOrAdd operation.</returns>
291
        public async ValueTask<V> GetOrAddAsync<TArg>(K key, Func<K, TArg, Task<V>> valueFactory, TArg factoryArgument)
292
        {
20,000,413✔
293
            while (true)
20,276,297✔
294
            {
20,276,297✔
295
                if (this.TryGet(key, out var value))
20,276,297✔
296
                {
831,613✔
297
                    return value;
831,613✔
298
                }
299

300
                // The value factory may be called concurrently for the same key, but the first write to the dictionary wins.
301
                value = await valueFactory(key, factoryArgument).ConfigureAwait(false);
19,444,684✔
302

303
                if (TryAdd(key, value))
19,444,684✔
304
                {
19,168,800✔
305
                    return value;
19,168,800✔
306
                }
307
            }
275,884✔
308
        }
20,000,413✔
309

310
        /// <summary>
311
        /// Attempts to remove the specified key value pair.
312
        /// </summary>
313
        /// <param name="item">The item to remove.</param>
314
        /// <returns>true if the item was removed successfully; otherwise, false.</returns>
315
        public bool TryRemove(KeyValuePair<K, V> item)
316
        {
27,374,783✔
317
            if (this.dictionary.TryGetValue(item.Key, out var existing))
27,374,783✔
318
            {
5,454,307✔
319
                lock (existing)
5,454,307✔
320
                {
5,454,307✔
321
                    if (EqualityComparer<V>.Default.Equals(existing.Value, item.Value))
5,454,307✔
322
                    {
292,321✔
323
                        var kvp = new KeyValuePair<K, I>(item.Key, existing);
292,321✔
324
#if NET6_0_OR_GREATER
325
                    if (this.dictionary.TryRemove(kvp))
198,281✔
326
#else
327
                        // https://devblogs.microsoft.com/pfxteam/little-known-gems-atomic-conditional-removals-from-concurrentdictionary/
328
                        if (((ICollection<KeyValuePair<K, I>>)this.dictionary).Remove(kvp))
94,040✔
329
#endif
330
                        {
284,791✔
331
                            OnRemove(item.Key, kvp.Value, ItemRemovedReason.Removed);
284,791✔
332
                            return true;
284,791✔
333
                        }
334
                    }
7,530✔
335
                }
5,169,516✔
336

337
                // it existed, but we couldn't remove - this means value was replaced afer the TryGetValue (a race)
338
            }
5,169,516✔
339

340
            return false;
27,089,992✔
341
        }
27,374,783✔
342

343
        /// <summary>
344
        /// Attempts to remove and return the value that has the specified key.
345
        /// </summary>
346
        /// <param name="key">The key of the element to remove.</param>
347
        /// <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>
348
        /// <returns>true if the object was removed successfully; otherwise, false.</returns>
349
        public bool TryRemove(K key, [MaybeNullWhen(false)] out V value)
350
        {
20,000,298✔
351
            if (this.dictionary.TryRemove(key, out var item))
20,000,298✔
352
            {
23,445✔
353
                OnRemove(key, item, ItemRemovedReason.Removed);
23,445✔
354
                value = item.Value;
23,445✔
355
                return true;
23,445✔
356
            }
357

358
            value = default;
19,976,853✔
359
            return false;
19,976,853✔
360
        }
20,000,298✔
361

362
        ///<inheritdoc/>
363
        public bool TryRemove(K key)
364
        {
20,000,220✔
365
            return TryRemove(key, out _);
20,000,220✔
366
        }
20,000,220✔
367

368
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
369
        private void OnRemove(K key, I item, ItemRemovedReason reason)
370
        {
310,752,592✔
371
            // Mark as not accessed, it will later be cycled out of the queues because it can never be fetched 
372
            // from the dictionary. Note: Hot/Warm/Cold count will reflect the removed item until it is cycled 
373
            // from the queue.
374
            item.WasAccessed = false;
310,752,592✔
375
            item.WasRemoved = true;
310,752,592✔
376

377
            this.telemetryPolicy.OnItemRemoved(key, item.Value, reason);
310,752,592✔
378

379
            // serialize dispose (common case dispose not thread safe)
380
            lock (item)
310,752,592✔
381
            {
310,752,592✔
382
                Disposer<V>.Dispose(item.Value);
310,752,592✔
383
            }
310,752,592✔
384
        }
310,752,592✔
385

386
        ///<inheritdoc/>
387
        ///<remarks>Note: Calling this method does not affect LRU order.</remarks>
388
        public bool TryUpdate(K key, V value)
389
        {
63,398,513✔
390
            if (this.dictionary.TryGetValue(key, out var existing))
63,398,513✔
391
            {
5,068,768✔
392
                return this.TryUpdateValue(existing, value);
5,068,768✔
393
            }
394

395
            return false;
58,329,745✔
396
        }
63,398,513✔
397

398
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
399
        private bool TryUpdateValue(I existing, V value)
400
        {
5,068,782✔
401
            lock (existing)
5,068,782✔
402
            {
5,068,782✔
403
                if (!existing.WasRemoved)
5,068,782✔
404
                {
4,810,941✔
405
                    V oldValue = existing.Value;
4,810,941✔
406

407
                    existing.Value = value;
4,810,941✔
408

409
                    this.itemPolicy.Update(existing);
4,810,941✔
410
                    // backcompat: remove conditional compile
411
#if NETCOREAPP3_0_OR_GREATER
412
                    this.telemetryPolicy.OnItemUpdated(existing.Key, oldValue, existing.Value);
4,810,941✔
413
#endif
414
                    Disposer<V>.Dispose(oldValue);
4,810,941✔
415

416
                    return true;
4,810,941✔
417
                }
418
            }
257,841✔
419

420
            return false;
257,841✔
421
        }
5,068,782✔
422

423
        ///<inheritdoc/>
424
        ///<remarks>Note: Updates to existing items do not affect LRU order. Added items are at the top of the LRU.</remarks>
425
        public void AddOrUpdate(K key, V value)
426
        {
23,309,747✔
427
            while (true)
23,398,387✔
428
            {
23,398,387✔
429
                // first, try to update
430
                if (this.TryUpdate(key, value))
23,398,387✔
431
                {
3,974,095✔
432
                    return;
3,974,095✔
433
                }
434

435
                // then try add
436
                var newItem = this.itemPolicy.CreateItem(key, value);
19,424,292✔
437

438
                if (this.dictionary.TryAdd(key, newItem))
19,424,292✔
439
                {
19,335,652✔
440
                    this.hotQueue.Enqueue(newItem);
19,335,652✔
441
                    Cycle(Interlocked.Increment(ref counter.hot));
19,335,652✔
442
                    return;
19,335,652✔
443
                }
444

445
                // if both update and add failed there was a race, try again
446
            }
88,640✔
447
        }
23,309,747✔
448

449
        ///<inheritdoc/>
450
        public void Clear()
451
        {
1,562,660✔
452
            // don't overlap Clear/Trim/TrimExpired
453
            lock (this.dictionary)
1,562,660✔
454
            {
1,562,660✔
455
                // evaluate queue count, remove everything including items removed from the dictionary but
456
                // not the queues. This also avoids the expensive o(n) no lock count, or locking the dictionary.
457
                int queueCount = this.HotCount + this.WarmCount + this.ColdCount;
1,562,660✔
458
                this.TrimLiveItems(itemsRemoved: 0, queueCount, ItemRemovedReason.Cleared);
1,562,660✔
459
            }
1,562,660✔
460
        }
1,562,660✔
461

462
        /// <summary>
463
        /// Trim the specified number of items from the cache. Removes all discardable items per IItemPolicy.ShouldDiscard(), then 
464
        /// itemCount-discarded items in LRU order, if any.
465
        /// </summary>
466
        /// <param name="itemCount">The number of items to remove.</param>
467
        /// <returns>The number of items removed from the cache.</returns>
468
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="itemCount"/> is less than 0./</exception>
469
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="itemCount"/> is greater than capacity./</exception>
470
        /// <remarks>
471
        /// Note: Trim affects LRU order. Calling Trim resets the internal accessed status of items.
472
        /// </remarks>
473
        public void Trim(int itemCount)
474
        {
305✔
475
            int capacity = this.Capacity;
305✔
476

477
            if (itemCount < 1 || itemCount > capacity)
305✔
478
                Throw.ArgOutOfRange(nameof(itemCount), "itemCount must be greater than or equal to one, and less than the capacity of the cache.");
10✔
479

480
            // clamp itemCount to number of items actually in the cache
481
            itemCount = Math.Min(itemCount, this.HotCount + this.WarmCount + this.ColdCount);
295✔
482

483
            // don't overlap Clear/Trim/TrimExpired
484
            lock (this.dictionary)
295✔
485
            {
295✔
486
                // first scan each queue for discardable items and remove them immediately. Note this can remove > itemCount items.
487
                int itemsRemoved = TrimAllDiscardedItems();
295✔
488

489
                TrimLiveItems(itemsRemoved, itemCount, ItemRemovedReason.Trimmed);
295✔
490
            }
295✔
491
        }
295✔
492

493
        private void TrimExpired()
494
        {
45✔
495
            if (this.itemPolicy.CanDiscard())
45✔
496
            {
45✔
497
                lock (this.dictionary)
45✔
498
                {
45✔
499
                    this.TrimAllDiscardedItems();
45✔
500
                }
45✔
501
            }
45✔
502
        }
45✔
503

504
        /// <summary>
505
        /// Trim discarded items from all queues.
506
        /// </summary>
507
        /// <returns>The number of items removed.</returns>
508
        // backcompat: make internal
509
        protected int TrimAllDiscardedItems()
510
        {
340✔
511
            // don't overlap Clear/Trim/TrimExpired
512
            lock (this.dictionary)
340✔
513
            {
340✔
514
                int RemoveDiscardableItems(ConcurrentQueue<I> q, ref int queueCounter)
515
                {
1,020✔
516
                    int itemsRemoved = 0;
1,020✔
517
                    int localCount = queueCounter;
1,020✔
518

519
                    for (int i = 0; i < localCount; i++)
6,216✔
520
                    {
2,088✔
521
                        if (q.TryDequeue(out var item))
2,088✔
522
                        {
2,088✔
523
                            if (this.itemPolicy.ShouldDiscard(item))
2,088✔
524
                            {
283✔
525
                                Interlocked.Decrement(ref queueCounter);
283✔
526
                                this.Move(item, ItemDestination.Remove, ItemRemovedReason.Trimmed);
283✔
527
                                itemsRemoved++;
283✔
528
                            }
283✔
529
                            else if (item.WasRemoved)
1,805✔
530
                            {
30✔
531
                                Interlocked.Decrement(ref queueCounter);
30✔
532
                            }
30✔
533
                            else
534
                            {
1,775✔
535
                                q.Enqueue(item);
1,775✔
536
                            }
1,775✔
537
                        }
2,088✔
538
                    }
2,088✔
539

540
                    return itemsRemoved;
1,020✔
541
                }
1,020✔
542

543
                int coldRem = RemoveDiscardableItems(coldQueue, ref this.counter.cold);
340✔
544
                int warmRem = RemoveDiscardableItems(warmQueue, ref this.counter.warm);
340✔
545
                int hotRem = RemoveDiscardableItems(hotQueue, ref this.counter.hot);
340✔
546

547
                if (warmRem > 0)
340✔
548
                {
40✔
549
                    Volatile.Write(ref this.isWarm, false);
40✔
550
                }
40✔
551

552
                return coldRem + warmRem + hotRem;
340✔
553
            }
554
        }
340✔
555

556
        private void TrimLiveItems(int itemsRemoved, int itemCount, ItemRemovedReason reason)
557
        {
1,562,955✔
558
            // When items are touched, they are moved to warm by cycling. Therefore, to guarantee 
559
            // that we can remove itemCount items, we must cycle (2 * capacity.Warm) + capacity.Hot times.
560
            // If clear is called during trimming, it would be possible to get stuck in an infinite
561
            // loop here. The warm + hot limit also guards against this case.
562
            int trimWarmAttempts = 0;
1,562,955✔
563
            int maxWarmHotAttempts = (this.capacity.Warm * 2) + this.capacity.Hot;
1,562,955✔
564

565
            while (itemsRemoved < itemCount && trimWarmAttempts < maxWarmHotAttempts)
15,909,324✔
566
            {
14,346,369✔
567
                if (Volatile.Read(ref this.counter.cold) > 0)
14,346,369✔
568
                {
11,012,905✔
569
                    if (TryRemoveCold(reason) == (ItemDestination.Remove, 0))
11,012,905✔
570
                    {
11,012,257✔
571
                        itemsRemoved++;
11,012,257✔
572
                        trimWarmAttempts = 0;
11,012,257✔
573
                    }
11,012,257✔
574
                    else
575
                    {
648✔
576
                        TrimWarmOrHot(reason);
648✔
577
                    }
648✔
578
                }
11,012,905✔
579
                else
580
                {
3,333,464✔
581
                    TrimWarmOrHot(reason);
3,333,464✔
582
                    trimWarmAttempts++;
3,333,464✔
583
                }
3,333,464✔
584
            }
14,346,369✔
585

586
            if (Volatile.Read(ref this.counter.warm) < this.capacity.Warm)
1,562,955✔
587
            {
871,773✔
588
                Volatile.Write(ref this.isWarm, false);
871,773✔
589
            }
871,773✔
590
        }
1,562,955✔
591

592
        private void TrimWarmOrHot(ItemRemovedReason reason)
593
        {
3,334,112✔
594
            if (Volatile.Read(ref this.counter.warm) > 0)
3,334,112✔
595
            {
1,118,162✔
596
                CycleWarmUnchecked(reason);
1,118,162✔
597
            }
1,118,162✔
598
            else if (Volatile.Read(ref this.counter.hot) > 0)
2,215,950✔
599
            {
2,213,793✔
600
                CycleHotUnchecked(reason);
2,213,793✔
601
            }
2,213,793✔
602
        }
3,334,112✔
603

604
        private void Cycle(int hotCount)
605
        {
310,787,190✔
606
            if (isWarm)
310,787,190✔
607
            {
306,917,378✔
608
                (var dest, var count) = CycleHot(hotCount);
306,917,378✔
609

610
                int cycles = 0;
306,917,378✔
611
                while (cycles++ < 3 && dest != ItemDestination.Remove)
657,127,670✔
612
                {
350,210,292✔
613
                    if (dest == ItemDestination.Warm)
350,210,292✔
614
                    {
43,880,753✔
615
                        (dest, count) = CycleWarm(count);
43,880,753✔
616
                    }
43,880,753✔
617
                    else if (dest == ItemDestination.Cold)
306,329,539✔
618
                    {
306,329,539✔
619
                        (dest, count) = CycleCold(count);
306,329,539✔
620
                    }
306,329,539✔
621
                }
350,210,292✔
622

623
                // If nothing was removed yet, constrain the size of warm and cold by discarding the coldest item.
624
                if (dest != ItemDestination.Remove)
306,917,378✔
625
                {
7,129,757✔
626
                    if (dest == ItemDestination.Warm && count > this.capacity.Warm)
7,129,757✔
627
                    {
4,550,948✔
628
                        count = LastWarmToCold();
4,550,948✔
629
                    }
4,550,948✔
630

631
                    ConstrainCold(count, ItemRemovedReason.Evicted);
7,129,757✔
632
                }
7,129,757✔
633
            }
306,917,378✔
634
            else
635
            {
3,869,812✔
636
                // fill up the warm queue with new items until warm is full.
637
                // else during warmup the cache will only use the hot + cold queues until any item is requested twice.
638
                CycleDuringWarmup(hotCount);
3,869,812✔
639
            }
3,869,812✔
640
        }
310,787,190✔
641

642
        [MethodImpl(MethodImplOptions.NoInlining)]
643
        private void CycleDuringWarmup(int hotCount)
644
        {
3,869,812✔
645
            // do nothing until hot is full
646
            if (hotCount > this.capacity.Hot)
3,869,812✔
647
            {
1,659,011✔
648
                Interlocked.Decrement(ref this.counter.hot);
1,659,011✔
649

650
                if (this.hotQueue.TryDequeue(out var item))
1,659,011✔
651
                {
1,658,990✔
652
                    // special case: removed during warmup
653
                    if (item.WasRemoved)
1,658,990✔
654
                    {
257,929✔
655
                        return;
257,929✔
656
                    }
657

658
                    int count = this.Move(item, ItemDestination.Warm, ItemRemovedReason.Evicted);
1,401,061✔
659

660
                    // if warm is now full, overflow to cold and mark as warm
661
                    if (count > this.capacity.Warm)
1,401,061✔
662
                    {
276,476✔
663
                        Volatile.Write(ref this.isWarm, true);
276,476✔
664
                        count = LastWarmToCold();
276,476✔
665
                        ConstrainCold(count, ItemRemovedReason.Evicted);
276,476✔
666
                    }
276,476✔
667
                }
1,401,061✔
668
                else
669
                {
21✔
670
                    Interlocked.Increment(ref this.counter.hot);
21✔
671
                }
21✔
672
            }
1,401,082✔
673
        }
3,869,812✔
674

675
        private (ItemDestination, int) CycleHot(int hotCount)
676
        {
306,917,378✔
677
            if (hotCount > this.capacity.Hot)
306,917,378✔
678
            {
306,905,492✔
679
                return CycleHotUnchecked(ItemRemovedReason.Evicted);
306,905,492✔
680
            }
681

682
            return (ItemDestination.Remove, 0);
11,886✔
683
        }
306,917,378✔
684

685
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
686
        private (ItemDestination, int) CycleHotUnchecked(ItemRemovedReason removedReason)
687
        {
309,119,285✔
688
            Interlocked.Decrement(ref this.counter.hot);
309,119,285✔
689

690
            if (this.hotQueue.TryDequeue(out var item))
309,119,285✔
691
            {
309,119,247✔
692
                var where = this.itemPolicy.RouteHot(item);
309,119,247✔
693
                return (where, this.Move(item, where, removedReason));
309,119,247✔
694
            }
695
            else
696
            {
38✔
697
                Interlocked.Increment(ref this.counter.hot);
38✔
698
                return (ItemDestination.Remove, 0);
38✔
699
            }
700
        }
309,119,285✔
701

702
        private (ItemDestination, int) CycleWarm(int count)
703
        {
43,880,753✔
704
            if (count > this.capacity.Warm)
43,880,753✔
705
            {
43,871,986✔
706
                return CycleWarmUnchecked(ItemRemovedReason.Evicted);
43,871,986✔
707
            }
708

709
            return (ItemDestination.Remove, 0);
8,767✔
710
        }
43,880,753✔
711

712
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
713
        private (ItemDestination, int) CycleWarmUnchecked(ItemRemovedReason removedReason)
714
        {
44,990,148✔
715
            int wc = Interlocked.Decrement(ref this.counter.warm);
44,990,148✔
716

717
            if (this.warmQueue.TryDequeue(out var item))
44,990,148!
718
            {
44,990,148✔
719
                if (item.WasRemoved)
44,990,148✔
720
                {
946,472✔
721
                    return (ItemDestination.Remove, 0);
946,472✔
722
                }
723

724
                var where = this.itemPolicy.RouteWarm(item);
44,043,676✔
725

726
                // When the warm queue is full, we allow an overflow of 1 item before redirecting warm items to cold.
727
                // This only happens when hit rate is high, in which case we can consider all items relatively equal in
728
                // terms of which was least recently used.
729
                if (where == ItemDestination.Warm && wc <= this.capacity.Warm)
44,043,676✔
730
                {
11,458,929✔
731
                    return (ItemDestination.Warm, this.Move(item, where, removedReason));
11,458,929✔
732
                }
733
                else
734
                {
32,584,747✔
735
                    return (ItemDestination.Cold, this.Move(item, ItemDestination.Cold, removedReason));
32,584,747✔
736
                }
737
            }
738
            else
UNCOV
739
            {
×
UNCOV
740
                Interlocked.Increment(ref this.counter.warm);
×
UNCOV
741
                return (ItemDestination.Remove, 0);
×
742
            }
743
        }
44,990,148✔
744

745
        private (ItemDestination, int) CycleCold(int count)
746
        {
306,329,539✔
747
            if (count > this.capacity.Cold)
306,329,539✔
748
            {
298,862,554✔
749
                return TryRemoveCold(ItemRemovedReason.Evicted);
298,862,554✔
750
            }
751

752
            return (ItemDestination.Remove, 0);
7,466,985✔
753
        }
306,329,539✔
754

755
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
756
        private (ItemDestination, int) TryRemoveCold(ItemRemovedReason removedReason)
757
        {
309,875,459✔
758
            Interlocked.Decrement(ref this.counter.cold);
309,875,459✔
759

760
            if (this.coldQueue.TryDequeue(out var item))
309,875,459✔
761
            {
309,874,939✔
762
                var where = this.itemPolicy.RouteCold(item);
309,874,939✔
763

764
                if (where == ItemDestination.Warm && Volatile.Read(ref this.counter.warm) <= this.capacity.Warm)
309,874,939✔
765
                {
8,572,799✔
766
                    return (ItemDestination.Warm, this.Move(item, where, removedReason));
8,572,799✔
767
                }
768
                else
769
                {
301,302,140✔
770
                    this.Move(item, ItemDestination.Remove, removedReason);
301,302,140✔
771
                    return (ItemDestination.Remove, 0);
301,302,140✔
772
                }
773
            }
774
            else
775
            {
520✔
776
                return (ItemDestination.Cold, Interlocked.Increment(ref this.counter.cold));
520✔
777
            }
778
        }
309,875,459✔
779

780
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
781
        private int LastWarmToCold()
782
        {
4,827,424✔
783
            Interlocked.Decrement(ref this.counter.warm);
4,827,424✔
784

785
            if (this.warmQueue.TryDequeue(out var item))
4,827,424✔
786
            {
4,827,400✔
787
                var destination = item.WasRemoved ? ItemDestination.Remove : ItemDestination.Cold;
4,827,400✔
788
                return this.Move(item, destination, ItemRemovedReason.Evicted);
4,827,400✔
789
            }
790
            else
791
            {
24✔
792
                Interlocked.Increment(ref this.counter.warm);
24✔
793
                return 0;
24✔
794
            }
795
        }
4,827,424✔
796

797
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
798
        private void ConstrainCold(int coldCount, ItemRemovedReason removedReason)
799
        {
7,406,233✔
800
            if (coldCount > this.capacity.Cold && this.coldQueue.TryDequeue(out var item))
7,406,233✔
801
            {
7,077,898✔
802
                Interlocked.Decrement(ref this.counter.cold);
7,077,898✔
803
                this.Move(item, ItemDestination.Remove, removedReason);
7,077,898✔
804
            }
7,077,898✔
805
        }
7,406,233✔
806

807
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
808
        private int Move(I item, ItemDestination where, ItemRemovedReason removedReason)
809
        {
680,745,015✔
810
            item.WasAccessed = false;
680,745,015✔
811

812
            switch (where)
680,745,015✔
813
            {
814
                case ItemDestination.Warm:
815
                    this.warmQueue.Enqueue(item);
49,836,825✔
816
                    return Interlocked.Increment(ref this.counter.warm);
49,836,825✔
817
                case ItemDestination.Cold:
818
                    this.coldQueue.Enqueue(item);
316,960,171✔
819
                    return Interlocked.Increment(ref this.counter.cold);
316,960,171✔
820
                case ItemDestination.Remove:
821

822
                    var kvp = new KeyValuePair<K, I>(item.Key, item);
313,948,019✔
823

824
#if NET6_0_OR_GREATER
825
                    if (this.dictionary.TryRemove(kvp))
259,186,756✔
826
#else
827
                    // https://devblogs.microsoft.com/pfxteam/little-known-gems-atomic-conditional-removals-from-concurrentdictionary/
828
                    if (((ICollection<KeyValuePair<K, I>>)this.dictionary).Remove(kvp))
54,761,263✔
829
#endif
830
                    {
310,432,376✔
831
                        OnRemove(item.Key, item, removedReason);
310,432,376✔
832
                    }
310,432,376✔
833
                    break;
313,948,019✔
834
            }
835

836
            return 0;
313,948,019✔
837
        }
680,745,015✔
838

839
        /// <summary>Returns an enumerator that iterates through the cache.</summary>
840
        /// <returns>An enumerator for the cache.</returns>
841
        /// <remarks>
842
        /// The enumerator returned from the cache is safe to use concurrently with
843
        /// reads and writes, however it does not represent a moment-in-time snapshot.  
844
        /// The contents exposed through the enumerator may contain modifications
845
        /// made after <see cref="GetEnumerator"/> was called.
846
        /// </remarks>
847
        IEnumerator IEnumerable.GetEnumerator()
848
        {
15✔
849
            return ((ConcurrentLruCore<K, V, I, P, T>)this).GetEnumerator();
15✔
850
        }
15✔
851

852
#if DEBUG
853
        /// <summary>
854
        /// Format the LRU as a string by converting all the keys to strings.
855
        /// </summary>
856
        /// <returns>The LRU formatted as a string.</returns>
857
        internal string FormatLruString()
858
        {
75✔
859
            var sb = new System.Text.StringBuilder();
75✔
860

861
            sb.Append("Hot [");
75✔
862
            sb.Append(string.Join(",", this.hotQueue.Select(n => n.Key.ToString())));
280✔
863
            sb.Append("] Warm [");
75✔
864
            sb.Append(string.Join(",", this.warmQueue.Select(n => n.Key.ToString())));
250✔
865
            sb.Append("] Cold [");
75✔
866
            sb.Append(string.Join(",", this.coldQueue.Select(n => n.Key.ToString())));
225✔
867
            sb.Append(']');
75✔
868

869
            return sb.ToString();
75✔
870
        }
75✔
871
#endif
872

873
        private static CachePolicy CreatePolicy(ConcurrentLruCore<K, V, I, P, T> lru)
874
        {
345✔
875
            var p = new Proxy(lru);
345✔
876

877
            if (typeof(P) == typeof(AfterAccessPolicy<K, V>))
345✔
878
            {
55✔
879
                return new CachePolicy(new Optional<IBoundedPolicy>(p), Optional<ITimePolicy>.None(), new Optional<ITimePolicy>(p), Optional<IDiscreteTimePolicy>.None());
55✔
880
            }
881

882
            // IsAssignableFrom is a jit intrinsic https://github.com/dotnet/runtime/issues/4920
883
            if (typeof(IDiscreteItemPolicy<K, V>).IsAssignableFrom(typeof(P)))
290✔
884
            {
75✔
885
                return new CachePolicy(new Optional<IBoundedPolicy>(p), Optional<ITimePolicy>.None(), Optional<ITimePolicy>.None(), new Optional<IDiscreteTimePolicy>(new DiscreteExpiryProxy(lru)));
75✔
886
            }
887

888
            return new CachePolicy(new Optional<IBoundedPolicy>(p), lru.itemPolicy.CanDiscard() ? new Optional<ITimePolicy>(p) : Optional<ITimePolicy>.None());
215✔
889
        }
345✔
890

891
        private static Optional<ICacheMetrics> CreateMetrics(ConcurrentLruCore<K, V, I, P, T> lru)
892
        {
165✔
893
            if (typeof(T) == typeof(NoTelemetryPolicy<K, V>))
165✔
894
            {
25✔
895
                return Optional<ICacheMetrics>.None();
25✔
896
            }
897

898
            return new(new Proxy(lru));
140✔
899
        }
165✔
900

901
        private static Optional<ICacheEvents<K, V>> CreateEvents(ConcurrentLruCore<K, V, I, P, T> lru)
902
        {
1,624✔
903
            if (typeof(T) == typeof(NoTelemetryPolicy<K, V>))
1,624✔
904
            {
65✔
905
                return Optional<ICacheEvents<K, V>>.None();
65✔
906
            }
907

908
            return new(new Proxy(lru));
1,559✔
909
        }
1,624✔
910

911
#if NET9_0_OR_GREATER
912
        ///<inheritdoc/>
913
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
914
        public IAlternateLookup<TAlternateKey, K, V> GetAlternateLookup<TAlternateKey>()
915
            where TAlternateKey : notnull, allows ref struct
916
        {
89✔
917
            if (!this.dictionary.IsCompatibleKey<TAlternateKey, K, I>())
89✔
918
            {
6✔
919
                Throw.IncompatibleComparer();
6✔
920
            }
921

922
            return new AlternateLookup<TAlternateKey>(this);
83✔
923
        }
83✔
924

925
        ///<inheritdoc/>
926
        public bool TryGetAlternateLookup<TAlternateKey>([MaybeNullWhen(false)] out IAlternateLookup<TAlternateKey, K, V> lookup)
927
            where TAlternateKey : notnull, allows ref struct
928
        {
12✔
929
            if (this.dictionary.IsCompatibleKey<TAlternateKey, K, I>())
12✔
930
            {
6✔
931
                lookup = new AlternateLookup<TAlternateKey>(this);
6✔
932
                return true;
6✔
933
            }
934

935
            lookup = default;
6✔
936
            return false;
6✔
937
        }
12✔
938

939
        ///<inheritdoc/>
940
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
941
        public IAsyncAlternateLookup<TAlternateKey, K, V> GetAsyncAlternateLookup<TAlternateKey>()
942
            where TAlternateKey : notnull, allows ref struct
943
        {
17✔
944
            if (!this.dictionary.IsCompatibleKey<TAlternateKey, K, I>())
17✔
945
            {
2✔
946
                Throw.IncompatibleComparer();
2✔
947
            }
948

949
            return new AlternateLookup<TAlternateKey>(this);
15✔
950
        }
15✔
951

952
        ///<inheritdoc/>
953
        public bool TryGetAsyncAlternateLookup<TAlternateKey>([MaybeNullWhen(false)] out IAsyncAlternateLookup<TAlternateKey, K, V> lookup)
954
            where TAlternateKey : notnull, allows ref struct
955
        {
4✔
956
            if (this.dictionary.IsCompatibleKey<TAlternateKey, K, I>())
4✔
957
            {
2✔
958
                lookup = new AlternateLookup<TAlternateKey>(this);
2✔
959
                return true;
2✔
960
            }
961

962
            lookup = default;
2✔
963
            return false;
2✔
964
        }
4✔
965

966
        internal readonly struct AlternateLookup<TAlternateKey> : IAlternateLookup<TAlternateKey, K, V>, IAsyncAlternateLookup<TAlternateKey, K, V>
967
            where TAlternateKey : notnull, allows ref struct
968
        {
969
            internal AlternateLookup(ConcurrentLruCore<K, V, I, P, T> lru)
970
            {
106✔
971
                Debug.Assert(lru is not null);
106✔
972
                Debug.Assert(lru.dictionary.IsCompatibleKey<TAlternateKey, K, I>());
106✔
973
                this.Lru = lru;
106✔
974
                this.Alternate = lru.dictionary.GetAlternateLookup<TAlternateKey>();
106✔
975
                this.Comparer = lru.dictionary.GetAlternateComparer<TAlternateKey, K, I>();
106✔
976
            }
106✔
977

978
            internal ConcurrentLruCore<K, V, I, P, T> Lru { get; }
86,569,128✔
979

980
            internal ConcurrentDictionary<K, I>.AlternateLookup<TAlternateKey> Alternate { get; }
50,335,532✔
981

982
            internal IAlternateEqualityComparer<TAlternateKey, K> Comparer { get; }
40,100,081✔
983

984
            public bool TryGet(TAlternateKey key, [MaybeNullWhen(false)] out V value)
985
            {
46,335,485✔
986
                if (this.Alternate.TryGetValue(key, out var item))
46,335,485✔
987
                {
6,235,407✔
988
                    return this.Lru.GetOrDiscard(item, out value);
6,235,407✔
989
                }
990

991
                value = default;
40,100,078✔
992
                this.Lru.telemetryPolicy.IncrementMiss();
40,100,078✔
993
                return false;
40,100,078✔
994
            }
46,335,485✔
995

996
            public bool TryRemove(TAlternateKey key, [MaybeNullWhen(false)] out K actualKey, [MaybeNullWhen(false)] out V value)
997
            {
4,000,017✔
998
                if (this.Alternate.TryRemove(key, out actualKey, out var item))
4,000,017✔
999
                {
11,980✔
1000
                    this.Lru.OnRemove(actualKey, item, ItemRemovedReason.Removed);
11,980✔
1001
                    value = item.Value;
11,980✔
1002
                    return true;
11,980✔
1003
                }
1004

1005
                actualKey = default;
3,988,037✔
1006
                value = default;
3,988,037✔
1007
                return false;
3,988,037✔
1008
            }
4,000,017✔
1009

1010
            public bool TryUpdate(TAlternateKey key, V value)
1011
            {
30✔
1012
                if (this.Alternate.TryGetValue(key, out var existing))
30✔
1013
                {
14✔
1014
                    return this.Lru.TryUpdateValue(existing, value);
14✔
1015
                }
1016

1017
                return false;
16✔
1018
            }
30✔
1019

1020
            public void AddOrUpdate(TAlternateKey key, V value)
1021
            {
16✔
1022
                K actualKey = default!;
16✔
1023
                bool hasActualKey = false;
16✔
1024

1025
                while (true)
16✔
1026
                {
16✔
1027
                    if (this.TryUpdate(key, value))
16✔
1028
                    {
7✔
1029
                        return;
7✔
1030
                    }
1031

1032
                    if (!hasActualKey)
9✔
1033
                    {
9✔
1034
                        actualKey = this.Comparer.Create(key);
9✔
1035
                        hasActualKey = true;
9✔
1036
                    }
9✔
1037

1038
                    if (this.Lru.TryAdd(actualKey, value))
9!
1039
                    {
9✔
1040
                        return;
9✔
1041
                    }
1042
                }
1043
            }
16✔
1044

1045
            public V GetOrAdd(TAlternateKey key, Func<K, V> valueFactory)
1046
            {
29,196,899✔
1047
                while (true)
29,439,246✔
1048
                {
29,439,246✔
1049
                    if (this.TryGet(key, out var value))
29,439,246✔
1050
                    {
5,849,879✔
1051
                        return value;
5,849,879✔
1052
                    }
1053

1054
                    K actualKey = this.Comparer.Create(key);
23,589,367✔
1055

1056
                    value = valueFactory(actualKey);
23,589,367✔
1057
                    if (this.Lru.TryAdd(actualKey, value))
23,589,367✔
1058
                    {
23,347,020✔
1059
                        return value;
23,347,020✔
1060
                    }
1061
                }
242,347✔
1062
            }
29,196,899✔
1063

1064
            public V GetOrAdd<TArg>(TAlternateKey key, Func<K, TArg, V> valueFactory, TArg factoryArgument)
1065
                where TArg : allows ref struct
1066
            {
8,821,197✔
1067
                while (true)
8,896,201✔
1068
                {
8,896,201✔
1069
                    if (this.TryGet(key, out var value))
8,896,201✔
1070
                    {
225,539✔
1071
                        return value;
225,539✔
1072
                    }
1073

1074
                    K actualKey = this.Comparer.Create(key);
8,670,662✔
1075

1076
                    value = valueFactory(actualKey, factoryArgument);
8,670,662✔
1077
                    if (this.Lru.TryAdd(actualKey, value))
8,670,662✔
1078
                    {
8,595,658✔
1079
                        return value;
8,595,658✔
1080
                    }
1081
                }
75,004✔
1082
            }
8,821,197✔
1083

1084
            public ValueTask<V> GetOrAddAsync(TAlternateKey key, Func<K, Task<V>> valueFactory)
1085
            {
4,000,002✔
1086
                if (this.TryGet(key, out var value))
4,000,002✔
1087
                {
100,916✔
1088
                    return new ValueTask<V>(value);
100,916✔
1089
                }
1090

1091
                K actualKey = this.Comparer.Create(key);
3,899,086✔
1092
                Task<V> task = valueFactory(actualKey);
3,899,086✔
1093

1094
                return GetOrAddAsyncSlow(actualKey, task);
3,899,086✔
1095
            }
4,000,002✔
1096

1097
            public ValueTask<V> GetOrAddAsync<TArg>(TAlternateKey key, Func<K, TArg, Task<V>> valueFactory, TArg factoryArgument)
1098
            {
4,000,002✔
1099
                if (this.TryGet(key, out var value))
4,000,002✔
1100
                {
59,045✔
1101
                    return new ValueTask<V>(value);
59,045✔
1102
                }
1103

1104
                K actualKey = this.Comparer.Create(key);
3,940,957✔
1105
                Task<V> task = valueFactory(actualKey, factoryArgument);
3,940,957✔
1106

1107
                return GetOrAddAsyncSlow(actualKey, task);
3,940,957✔
1108
            }
4,000,002✔
1109

1110
            // Since TAlternateKey can be a ref struct, we can't use async/await in the public GetOrAddAsync methods,
1111
            // so we delegate to this private async method after the value factory is invoked.
1112
            private async ValueTask<V> GetOrAddAsyncSlow(K actualKey, Task<V> task)
1113
            {
7,840,043✔
1114
                V value = await task.ConfigureAwait(false);
7,840,043✔
1115

1116
                while (true)
7,840,056✔
1117
                {
7,840,056✔
1118
                    if (this.Lru.TryAdd(actualKey, value))
7,840,056✔
1119
                    {
7,718,501✔
1120
                        return value;
7,718,501✔
1121
                    }
1122

1123
                    // Another thread added a value for this key first, retrieve it.
1124
                    if (this.Lru.TryGet(actualKey, out V? existing))
121,555✔
1125
                    {
121,542✔
1126
                        return existing;
121,542✔
1127
                    }
1128
                }
13✔
1129
            }
7,840,043✔
1130
        }
1131
#endif
1132

1133
        // To get JIT optimizations, policies must be structs.
1134
        // If the structs are returned directly via properties, they will be copied. Since  
1135
        // telemetryPolicy is a mutable struct, copy is bad. One workaround is to store the 
1136
        // state within the struct in an object. Since the struct points to the same object
1137
        // it becomes immutable. However, this object is then somewhere else on the 
1138
        // heap, which slows down the policies with hit counter logic in benchmarks. Likely
1139
        // this approach keeps the structs data members in the same CPU cache line as the LRU.
1140
        // backcompat: remove conditional compile
1141
#if NETCOREAPP3_0_OR_GREATER
1142
        [DebuggerDisplay("Hit = {Hits}, Miss = {Misses}, Upd = {Updated}, Evict = {Evicted}")]
1143
#else
1144
        [DebuggerDisplay("Hit = {Hits}, Miss = {Misses}, Evict = {Evicted}")]
1145
#endif
1146
        private class Proxy : ICacheMetrics, ICacheEvents<K, V>, IBoundedPolicy, ITimePolicy
1147
        {
1148
            private readonly ConcurrentLruCore<K, V, I, P, T> lru;
1149

1150
            public Proxy(ConcurrentLruCore<K, V, I, P, T> lru)
2,044✔
1151
            {
2,044✔
1152
                this.lru = lru;
2,044✔
1153
            }
2,044✔
1154

1155
            public double HitRatio => lru.telemetryPolicy.HitRatio;
10✔
1156

1157
            public long Total => lru.telemetryPolicy.Total;
5✔
1158

1159
            public long Hits => lru.telemetryPolicy.Hits;
30✔
1160

1161
            public long Misses => lru.telemetryPolicy.Misses;
30✔
1162

1163
            public long Evicted => lru.telemetryPolicy.Evicted;
40✔
1164

1165
            // backcompat: remove conditional compile
1166
#if NETCOREAPP3_0_OR_GREATER
1167
            public long Updated => lru.telemetryPolicy.Updated;
10✔
1168
#endif
1169
            public int Capacity => lru.Capacity;
135✔
1170

1171
            public TimeSpan TimeToLive => lru.itemPolicy.TimeToLive;
20✔
1172

1173
            public event EventHandler<ItemRemovedEventArgs<K, V>> ItemRemoved
1174
            {
1175
                add { this.lru.telemetryPolicy.ItemRemoved += value; }
225✔
1176
                remove { this.lru.telemetryPolicy.ItemRemoved -= value; }
30✔
1177
            }
1178

1179
            // backcompat: remove conditional compile
1180
#if NETCOREAPP3_0_OR_GREATER
1181
            public event EventHandler<ItemUpdatedEventArgs<K, V>> ItemUpdated
1182
            {
1183
                add { this.lru.telemetryPolicy.ItemUpdated += value; }
132✔
1184
                remove { this.lru.telemetryPolicy.ItemUpdated -= value; }
15✔
1185
            }
1186
#endif
1187
            public void Trim(int itemCount)
1188
            {
50✔
1189
                lru.Trim(itemCount);
50✔
1190
            }
50✔
1191

1192
            public void TrimExpired()
1193
            {
35✔
1194
                lru.TrimExpired();
35✔
1195
            }
35✔
1196
        }
1197

1198
        private class DiscreteExpiryProxy : IDiscreteTimePolicy
1199
        {
1200
            private readonly ConcurrentLruCore<K, V, I, P, T> lru;
1201

1202
            public DiscreteExpiryProxy(ConcurrentLruCore<K, V, I, P, T> lru)
75✔
1203
            {
75✔
1204
                this.lru = lru;
75✔
1205
            }
75✔
1206

1207
            public void TrimExpired()
1208
            {
10✔
1209
                lru.TrimExpired();
10✔
1210
            }
10✔
1211

1212
            public bool TryGetTimeToExpire<TKey>(TKey key, out TimeSpan timeToLive)
1213
            {
15✔
1214
                if (key is K k && lru.dictionary.TryGetValue(k, out var item))
15✔
1215
                {
5✔
1216
                    LongTickCountLruItem<K, V>? tickItem = item as LongTickCountLruItem<K, V>;
5✔
1217
                    timeToLive = (new Duration(tickItem!.TickCount) - Duration.SinceEpoch()).ToTimeSpan();
5✔
1218
                    return true;
5✔
1219
                }
1220

1221
                timeToLive = default;
10✔
1222
                return false;
10✔
1223
            }
15✔
1224
        }
1225
    }
1226
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc