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

bitfaster / BitFaster.Caching / 25139091561

29 Apr 2026 11:25PM UTC coverage: 99.11% (-0.07%) from 99.181%
25139091561

Pull #795

github

web-flow
Merge 444a35b0b into e3ad50ae3
Pull Request #795: Implement ConcurrentLfu events

1361 of 1394 branches covered (97.63%)

Branch coverage included in aggregate %.

135 of 136 new or added lines in 8 files covered. (99.26%)

3 existing lines in 1 file now uncovered.

5767 of 5798 relevant lines covered (99.47%)

88468684.16 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;
4,199✔
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(
4,199✔
74
            int concurrencyLevel,
4,199✔
75
            ICapacityPartition capacity,
4,199✔
76
            IEqualityComparer<K> comparer,
4,199✔
77
            P itemPolicy,
4,199✔
78
            T telemetryPolicy)
4,199✔
79
        {
4,199✔
80
            if (capacity == null)
4,199✔
81
                Throw.ArgNull(ExceptionArgument.capacity);
7✔
82

83
            if (comparer == null)
4,192✔
84
                Throw.ArgNull(ExceptionArgument.comparer);
7✔
85

86
            capacity.Validate();
4,185✔
87
            this.capacity = capacity;
4,178✔
88

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

93
            int dictionaryCapacity = ConcurrentDictionarySize.Estimate(this.Capacity);
4,178✔
94

95
            this.dictionary = new ConcurrentDictionary<K, I>(concurrencyLevel, dictionaryCapacity, comparer);
4,178✔
96
            this.itemPolicy = itemPolicy;
4,164✔
97
            this.telemetryPolicy = telemetryPolicy;
4,164✔
98
            this.telemetryPolicy.SetEventSource(this);
4,164✔
99
        }
4,164✔
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();
24,444,995✔
104

105
        ///<inheritdoc/>
106
        public int Capacity => this.capacity.Hot + this.capacity.Warm + this.capacity.Cold;
2,800,006,337✔
107

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

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

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

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

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

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

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

137
#if NET9_0_OR_GREATER
138
        /// <inheritdoc/>
139
        public IEqualityComparer<K> Comparer => this.dictionary.Comparer;
276✔
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
        {
441✔
152
            foreach (var kvp in this.dictionary)
2,268✔
153
            {
476✔
154
                if (!itemPolicy.ShouldDiscard(kvp.Value))
476✔
155
                {
455✔
156
                    yield return new KeyValuePair<K, V>(kvp.Key, kvp.Value.Value);
455✔
157
                }
448✔
158
            }
469✔
159
        }
434✔
160

161
        ///<inheritdoc/>
162
        public bool TryGet(K key, [MaybeNullWhen(false)] out V value)
163
        {
3,188,910,689✔
164
            if (dictionary.TryGetValue(key, out var item))
3,188,910,689✔
165
            {
2,831,246,510✔
166
                return GetOrDiscard(item, out value);
2,831,246,510✔
167
            }
168

169
            value = default;
357,664,179✔
170
            this.telemetryPolicy.IncrementMiss();
357,664,179✔
171
            return false;
357,664,179✔
172
        }
3,188,910,689✔
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,852,389,165✔
179
            if (this.itemPolicy.ShouldDiscard(item))
2,852,389,165✔
180
            {
6,050,521✔
181
                this.Move(item, ItemDestination.Remove, ItemRemovedReason.Evicted);
6,050,521✔
182
                this.telemetryPolicy.IncrementMiss();
6,050,521✔
183
                value = default;
6,050,521✔
184
                return false;
6,050,521✔
185
            }
186

187
            value = item.Value;
2,846,338,644✔
188

189
            this.itemPolicy.Touch(item);
2,846,338,644✔
190
            this.telemetryPolicy.IncrementHit();
2,846,338,644✔
191
            return true;
2,846,338,644✔
192
        }
2,852,389,165✔
193

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

198
            if (this.dictionary.TryAdd(key, newItem))
480,152,932✔
199
            {
467,873,341✔
200
                this.hotQueue.Enqueue(newItem);
467,873,341✔
201
                Cycle(Interlocked.Increment(ref counter.hot));
467,873,341✔
202
                return true;
467,873,341✔
203
            }
204

205
            Disposer<V>.Dispose(newItem.Value);
12,279,591✔
206
            return false;
12,279,591✔
207
        }
480,152,932✔
208

209
        ///<inheritdoc/>
210
        public V GetOrAdd(K key, Func<K, V> valueFactory)
211
        {
3,059,617,521✔
212
            while (true)
3,068,525,430✔
213
            {
3,068,525,430✔
214
                if (this.TryGet(key, out var value))
3,068,525,430✔
215
                {
2,813,526,699✔
216
                    return value;
2,813,526,699✔
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);
254,998,731✔
221

222
                if (TryAdd(key, value))
254,998,731✔
223
                {
246,090,822✔
224
                    return value;
246,090,822✔
225
                }
226
            }
8,907,909✔
227
        }
3,059,617,521✔
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
        {
54,972,488✔
244
            while (true)
55,402,709✔
245
            {
55,402,709✔
246
                if (this.TryGet(key, out var value))
55,402,709✔
247
                {
1,407,320✔
248
                    return value;
1,407,320✔
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);
53,995,389✔
253

254
                if (TryAdd(key, value))
53,995,389✔
255
                {
53,565,168✔
256
                    return value;
53,565,168✔
257
                }
258
            }
430,221✔
259
        }
54,972,488✔
260

261
        ///<inheritdoc/>
262
        public async ValueTask<V> GetOrAddAsync(K key, Func<K, Task<V>> valueFactory)
263
        {
28,000,544✔
264
            while (true)
28,384,761✔
265
            {
28,384,761✔
266
                if (this.TryGet(key, out var value))
28,384,761✔
267
                {
1,096,792✔
268
                    return value;
1,096,792✔
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);
27,287,969✔
274

275
                if (TryAdd(key, value))
27,287,948✔
276
                {
26,903,731✔
277
                    return value;
26,903,731✔
278
                }
279
            }
384,217✔
280
        }
28,000,523✔
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
        {
28,000,687✔
293
            while (true)
28,448,885✔
294
            {
28,448,885✔
295
                if (this.TryGet(key, out var value))
28,448,885✔
296
                {
1,394,220✔
297
                    return value;
1,394,220✔
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);
27,054,665✔
302

303
                if (TryAdd(key, value))
27,054,665✔
304
                {
26,606,467✔
305
                    return value;
26,606,467✔
306
                }
307
            }
448,198✔
308
        }
28,000,687✔
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
        {
33,486,301✔
317
            if (this.dictionary.TryGetValue(item.Key, out var existing))
33,486,301✔
318
            {
3,632,277✔
319
                lock (existing)
3,632,277✔
320
                {
3,632,277✔
321
                    if (EqualityComparer<V>.Default.Equals(existing.Value, item.Value))
3,632,277✔
322
                    {
272,580✔
323
                        var kvp = new KeyValuePair<K, I>(item.Key, existing);
272,580✔
324
#if NET6_0_OR_GREATER
325
                    if (this.dictionary.TryRemove(kvp))
185,414✔
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))
87,166✔
329
#endif
330
                        {
265,344✔
331
                            OnRemove(item.Key, kvp.Value, ItemRemovedReason.Removed);
265,344✔
332
                            return true;
265,344✔
333
                        }
334
                    }
7,236✔
335
                }
3,366,933✔
336

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

340
            return false;
33,220,957✔
341
        }
33,486,301✔
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
        {
28,000,418✔
351
            if (this.dictionary.TryRemove(key, out var item))
28,000,418✔
352
            {
46,889✔
353
                OnRemove(key, item, ItemRemovedReason.Removed);
46,889✔
354
                value = item.Value;
46,889✔
355
                return true;
46,889✔
356
            }
357

358
            value = default;
27,953,529✔
359
            return false;
27,953,529✔
360
        }
28,000,418✔
361

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

368
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
369
        private void OnRemove(K key, I item, ItemRemovedReason reason)
370
        {
494,139,772✔
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;
494,139,772✔
375
            item.WasRemoved = true;
494,139,772✔
376

377
            this.telemetryPolicy.OnItemRemoved(key, item.Value, reason);
494,139,772✔
378

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

386
        ///<inheritdoc/>
387
        ///<remarks>Note: Calling this method does not affect LRU order.</remarks>
388
        public bool TryUpdate(K key, V value)
389
        {
88,324,480✔
390
            if (this.dictionary.TryGetValue(key, out var existing))
88,324,480✔
391
            {
7,383,087✔
392
                return this.TryUpdateValue(existing, value);
7,383,087✔
393
            }
394

395
            return false;
80,941,393✔
396
        }
88,324,480✔
397

398
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
399
        private bool TryUpdateValue(I existing, V value)
400
        {
7,383,129✔
401
            lock (existing)
7,383,129✔
402
            {
7,383,129✔
403
                if (!existing.WasRemoved)
7,383,129✔
404
                {
7,161,230✔
405
                    V oldValue = existing.Value;
7,161,230✔
406

407
                    existing.Value = value;
7,161,230✔
408

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

416
                    return true;
7,161,230✔
417
                }
418
            }
221,899✔
419

420
            return false;
221,899✔
421
        }
7,383,129✔
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
        {
32,141,361✔
427
            while (true)
32,324,305✔
428
            {
32,324,305✔
429
                // first, try to update
430
                if (this.TryUpdate(key, value))
32,324,305✔
431
                {
5,826,239✔
432
                    return;
5,826,239✔
433
                }
434

435
                // then try add
436
                var newItem = this.itemPolicy.CreateItem(key, value);
26,498,066✔
437

438
                if (this.dictionary.TryAdd(key, newItem))
26,498,066✔
439
                {
26,315,122✔
440
                    this.hotQueue.Enqueue(newItem);
26,315,122✔
441
                    Cycle(Interlocked.Increment(ref counter.hot));
26,315,122✔
442
                    return;
26,315,122✔
443
                }
444

445
                // if both update and add failed there was a race, try again
446
            }
182,944✔
447
        }
32,141,361✔
448

449
        ///<inheritdoc/>
450
        public void Clear()
451
        {
2,187,724✔
452
            // don't overlap Clear/Trim/TrimExpired
453
            lock (this.dictionary)
2,187,724✔
454
            {
2,187,724✔
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;
2,187,724✔
458
                this.TrimLiveItems(itemsRemoved: 0, queueCount, ItemRemovedReason.Cleared);
2,187,724✔
459
            }
2,187,724✔
460
        }
2,187,724✔
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
        {
427✔
475
            int capacity = this.Capacity;
427✔
476

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

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

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

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

493
        private void TrimExpired()
494
        {
64✔
495
            if (this.itemPolicy.CanDiscard())
64✔
496
            {
64✔
497
                lock (this.dictionary)
64✔
498
                {
64✔
499
                    this.TrimAllDiscardedItems();
64✔
500
                }
64✔
501
            }
64✔
502
        }
64✔
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
        {
477✔
511
            // don't overlap Clear/Trim/TrimExpired
512
            lock (this.dictionary)
477✔
513
            {
477✔
514
                int RemoveDiscardableItems(ConcurrentQueue<I> q, ref int queueCounter)
515
                {
1,431✔
516
                    int itemsRemoved = 0;
1,431✔
517
                    int localCount = queueCounter;
1,431✔
518

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

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

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

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

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

556
        private void TrimLiveItems(int itemsRemoved, int itemCount, ItemRemovedReason reason)
557
        {
2,188,137✔
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;
2,188,137✔
563
            int maxWarmHotAttempts = (this.capacity.Warm * 2) + this.capacity.Hot;
2,188,137✔
564

565
            while (itemsRemoved < itemCount && trimWarmAttempts < maxWarmHotAttempts)
22,263,194✔
566
            {
20,075,057✔
567
                if (Volatile.Read(ref this.counter.cold) > 0)
20,075,057✔
568
                {
15,539,318✔
569
                    if (TryRemoveCold(reason) == (ItemDestination.Remove, 0))
15,539,318✔
570
                    {
15,537,492✔
571
                        itemsRemoved++;
15,537,492✔
572
                        trimWarmAttempts = 0;
15,537,492✔
573
                    }
15,537,492✔
574
                    else
575
                    {
1,826✔
576
                        TrimWarmOrHot(reason);
1,826✔
577
                    }
1,826✔
578
                }
15,539,318✔
579
                else
580
                {
4,535,739✔
581
                    TrimWarmOrHot(reason);
4,535,739✔
582
                    trimWarmAttempts++;
4,535,739✔
583
                }
4,535,739✔
584
            }
20,075,057✔
585

586
            if (Volatile.Read(ref this.counter.warm) < this.capacity.Warm)
2,188,137✔
587
            {
1,217,191✔
588
                Volatile.Write(ref this.isWarm, false);
1,217,191✔
589
            }
1,217,191✔
590
        }
2,188,137✔
591

592
        private void TrimWarmOrHot(ItemRemovedReason reason)
593
        {
4,537,565✔
594
            if (Volatile.Read(ref this.counter.warm) > 0)
4,537,565✔
595
            {
1,536,173✔
596
                CycleWarmUnchecked(reason);
1,536,173✔
597
            }
1,536,173✔
598
            else if (Volatile.Read(ref this.counter.hot) > 0)
3,001,392✔
599
            {
3,000,048✔
600
                CycleHotUnchecked(reason);
3,000,048✔
601
            }
3,000,048✔
602
        }
4,537,565✔
603

604
        private void Cycle(int hotCount)
605
        {
494,188,463✔
606
            if (isWarm)
494,188,463✔
607
            {
488,990,698✔
608
                (var dest, var count) = CycleHot(hotCount);
488,990,698✔
609

610
                int cycles = 0;
488,990,698✔
611
                while (cycles++ < 3 && dest != ItemDestination.Remove)
1,056,758,785✔
612
                {
567,768,087✔
613
                    if (dest == ItemDestination.Warm)
567,768,087✔
614
                    {
74,868,056✔
615
                        (dest, count) = CycleWarm(count);
74,868,056✔
616
                    }
74,868,056✔
617
                    else if (dest == ItemDestination.Cold)
492,900,031✔
618
                    {
492,900,031✔
619
                        (dest, count) = CycleCold(count);
492,900,031✔
620
                    }
492,900,031✔
621
                }
567,768,087✔
622

623
                // If nothing was removed yet, constrain the size of warm and cold by discarding the coldest item.
624
                if (dest != ItemDestination.Remove)
488,990,698✔
625
                {
13,388,640✔
626
                    if (dest == ItemDestination.Warm && count > this.capacity.Warm)
13,388,640✔
627
                    {
8,092,321✔
628
                        count = LastWarmToCold();
8,092,321✔
629
                    }
8,092,321✔
630

631
                    ConstrainCold(count, ItemRemovedReason.Evicted);
13,388,640✔
632
                }
13,388,640✔
633
            }
488,990,698✔
634
            else
635
            {
5,197,765✔
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);
5,197,765✔
639
            }
5,197,765✔
640
        }
494,188,463✔
641

642
        [MethodImpl(MethodImplOptions.NoInlining)]
643
        private void CycleDuringWarmup(int hotCount)
644
        {
5,197,765✔
645
            // do nothing until hot is full
646
            if (hotCount > this.capacity.Hot)
5,197,765✔
647
            {
2,189,324✔
648
                Interlocked.Decrement(ref this.counter.hot);
2,189,324✔
649

650
                if (this.hotQueue.TryDequeue(out var item))
2,189,324✔
651
                {
2,189,312✔
652
                    // special case: removed during warmup
653
                    if (item.WasRemoved)
2,189,312✔
654
                    {
221,995✔
655
                        return;
221,995✔
656
                    }
657

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

660
                    // if warm is now full, overflow to cold and mark as warm
661
                    if (count > this.capacity.Warm)
1,967,317✔
662
                    {
447,509✔
663
                        Volatile.Write(ref this.isWarm, true);
447,509✔
664
                        count = LastWarmToCold();
447,509✔
665
                        ConstrainCold(count, ItemRemovedReason.Evicted);
447,509✔
666
                    }
447,509✔
667
                }
1,967,317✔
668
                else
669
                {
12✔
670
                    Interlocked.Increment(ref this.counter.hot);
12✔
671
                }
12✔
672
            }
1,967,329✔
673
        }
5,197,765✔
674

675
        private (ItemDestination, int) CycleHot(int hotCount)
676
        {
488,990,698✔
677
            if (hotCount > this.capacity.Hot)
488,990,698✔
678
            {
488,986,442✔
679
                return CycleHotUnchecked(ItemRemovedReason.Evicted);
488,986,442✔
680
            }
681

682
            return (ItemDestination.Remove, 0);
4,256✔
683
        }
488,990,698✔
684

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

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

702
        private (ItemDestination, int) CycleWarm(int count)
703
        {
74,868,056✔
704
            if (count > this.capacity.Warm)
74,868,056✔
705
            {
74,830,402✔
706
                return CycleWarmUnchecked(ItemRemovedReason.Evicted);
74,830,402✔
707
            }
708

709
            return (ItemDestination.Remove, 0);
37,654✔
710
        }
74,868,056✔
711

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

717
            if (this.warmQueue.TryDequeue(out var item))
76,366,575!
718
            {
76,366,575✔
719
                if (item.WasRemoved)
76,366,575✔
720
                {
1,086,521✔
721
                    return (ItemDestination.Remove, 0);
1,086,521✔
722
                }
723

724
                var where = this.itemPolicy.RouteWarm(item);
75,280,054✔
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)
75,280,054✔
730
                {
17,025,615✔
731
                    return (ItemDestination.Warm, this.Move(item, where, removedReason));
17,025,615✔
732
                }
733
                else
734
                {
58,254,439✔
735
                    return (ItemDestination.Cold, this.Move(item, ItemDestination.Cold, removedReason));
58,254,439✔
736
                }
737
            }
738
            else
UNCOV
739
            {
×
UNCOV
740
                Interlocked.Increment(ref this.counter.warm);
×
UNCOV
741
                return (ItemDestination.Remove, 0);
×
742
            }
743
        }
76,366,575✔
744

745
        private (ItemDestination, int) CycleCold(int count)
746
        {
492,900,031✔
747
            if (count > this.capacity.Cold)
492,900,031✔
748
            {
482,179,096✔
749
                return TryRemoveCold(ItemRemovedReason.Evicted);
482,179,096✔
750
            }
751

752
            return (ItemDestination.Remove, 0);
10,720,935✔
753
        }
492,900,031✔
754

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

760
            if (this.coldQueue.TryDequeue(out var item))
497,718,414✔
761
            {
497,717,049✔
762
                var where = this.itemPolicy.RouteCold(item);
497,717,049✔
763

764
                if (where == ItemDestination.Warm && Volatile.Read(ref this.counter.warm) <= this.capacity.Warm)
497,717,049✔
765
                {
19,478,918✔
766
                    return (ItemDestination.Warm, this.Move(item, where, removedReason));
19,478,918✔
767
                }
768
                else
769
                {
478,238,131✔
770
                    this.Move(item, ItemDestination.Remove, removedReason);
478,238,131✔
771
                    return (ItemDestination.Remove, 0);
478,238,131✔
772
                }
773
            }
774
            else
775
            {
1,365✔
776
                return (ItemDestination.Cold, Interlocked.Increment(ref this.counter.cold));
1,365✔
777
            }
778
        }
497,718,414✔
779

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

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

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

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

812
            switch (where)
1,094,908,678✔
813
            {
814
                case ItemDestination.Warm:
815
                    this.warmQueue.Enqueue(item);
84,933,593✔
816
                    return Interlocked.Increment(ref this.counter.warm);
84,933,593✔
817
                case ItemDestination.Cold:
818
                    this.coldQueue.Enqueue(item);
511,094,431✔
819
                    return Interlocked.Increment(ref this.counter.cold);
511,094,431✔
820
                case ItemDestination.Remove:
821

822
                    var kvp = new KeyValuePair<K, I>(item.Key, item);
498,880,654✔
823

824
#if NET6_0_OR_GREATER
825
                    if (this.dictionary.TryRemove(kvp))
444,165,763✔
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,714,891✔
829
#endif
830
                    {
493,812,700✔
831
                        OnRemove(item.Key, item, removedReason);
493,812,700✔
832
                    }
493,812,700✔
833
                    break;
498,880,654✔
834
            }
835

836
            return 0;
498,880,654✔
837
        }
1,094,908,678✔
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
        {
21✔
849
            return ((ConcurrentLruCore<K, V, I, P, T>)this).GetEnumerator();
21✔
850
        }
21✔
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
        {
105✔
859
            var sb = new System.Text.StringBuilder();
105✔
860

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

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

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

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

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

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

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

898
            return new(new Proxy(lru));
196✔
899
        }
231✔
900

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

908
            return new(new Proxy(lru));
2,533✔
909
        }
2,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
        {
267✔
917
            if (!this.dictionary.IsCompatibleKey<TAlternateKey, K, I>())
267✔
918
            {
18✔
919
                Throw.IncompatibleComparer();
18✔
920
            }
921

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

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

935
            lookup = default;
18✔
936
            return false;
18✔
937
        }
36✔
938

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

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

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

962
            lookup = default;
6✔
963
            return false;
6✔
964
        }
12✔
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
            {
318✔
971
                Debug.Assert(lru is not null);
318✔
972
                Debug.Assert(lru.dictionary.IsCompatibleKey<TAlternateKey, K, I>());
318✔
973
                this.Lru = lru;
318✔
974
                this.Alternate = lru.dictionary.GetAlternateLookup<TAlternateKey>();
318✔
975
                this.Comparer = lru.dictionary.GetAlternateComparer<TAlternateKey, K, I>();
318✔
976
            }
318✔
977

978
            internal ConcurrentLruCore<K, V, I, P, T> Lru { get; }
255,237,214✔
979

980
            internal ConcurrentDictionary<K, I>.AlternateLookup<TAlternateKey> Alternate { get; }
149,958,955✔
981

982
            internal IAlternateEqualityComparer<TAlternateKey, K> Comparer { get; }
116,816,168✔
983

984
            public bool TryGet(TAlternateKey key, [MaybeNullWhen(false)] out V value)
985
            {
137,958,814✔
986
                if (this.Alternate.TryGetValue(key, out var item))
137,958,814✔
987
                {
21,142,655✔
988
                    return this.Lru.GetOrDiscard(item, out value);
21,142,655✔
989
                }
990

991
                value = default;
116,816,159✔
992
                this.Lru.telemetryPolicy.IncrementMiss();
116,816,159✔
993
                return false;
116,816,159✔
994
            }
137,958,814✔
995

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

1005
                actualKey = default;
11,985,212✔
1006
                value = default;
11,985,212✔
1007
                return false;
11,985,212✔
1008
            }
12,000,051✔
1009

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

1017
                return false;
48✔
1018
            }
90✔
1019

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

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

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

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

1045
            public V GetOrAdd(TAlternateKey key, Func<K, V> valueFactory)
1046
            {
86,487,005✔
1047
                while (true)
87,908,664✔
1048
                {
87,908,664✔
1049
                    if (this.TryGet(key, out var value))
87,908,664✔
1050
                    {
19,930,433✔
1051
                        return value;
19,930,433✔
1052
                    }
1053

1054
                    K actualKey = this.Comparer.Create(key);
67,978,231✔
1055

1056
                    value = valueFactory(actualKey);
67,978,231✔
1057
                    if (this.Lru.TryAdd(actualKey, value))
67,978,231✔
1058
                    {
66,556,572✔
1059
                        return value;
66,556,572✔
1060
                    }
1061
                }
1,421,659✔
1062
            }
86,487,005✔
1063

1064
            public V GetOrAdd<TArg>(TAlternateKey key, Func<K, TArg, V> valueFactory, TArg factoryArgument)
1065
                where TArg : allows ref struct
1066
            {
25,809,969✔
1067
                while (true)
26,050,036✔
1068
                {
26,050,036✔
1069
                    if (this.TryGet(key, out var value))
26,050,036✔
1070
                    {
669,912✔
1071
                        return value;
669,912✔
1072
                    }
1073

1074
                    K actualKey = this.Comparer.Create(key);
25,380,124✔
1075

1076
                    value = valueFactory(actualKey, factoryArgument);
25,380,124✔
1077
                    if (this.Lru.TryAdd(actualKey, value))
25,380,124✔
1078
                    {
25,140,057✔
1079
                        return value;
25,140,057✔
1080
                    }
1081
                }
240,067✔
1082
            }
25,809,969✔
1083

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

1091
                K actualKey = this.Comparer.Create(key);
11,701,981✔
1092
                Task<V> task = valueFactory(actualKey);
11,701,981✔
1093

1094
                return GetOrAddAsyncSlow(actualKey, task);
11,701,981✔
1095
            }
12,000,006✔
1096

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

1104
                K actualKey = this.Comparer.Create(key);
11,755,805✔
1105
                Task<V> task = valueFactory(actualKey, factoryArgument);
11,755,805✔
1106

1107
                return GetOrAddAsyncSlow(actualKey, task);
11,755,805✔
1108
            }
12,000,006✔
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
            {
23,457,786✔
1114
                V value = await task.ConfigureAwait(false);
23,457,786✔
1115

1116
                while (true)
23,457,817✔
1117
                {
23,457,817✔
1118
                    if (this.Lru.TryAdd(actualKey, value))
23,457,817✔
1119
                    {
23,010,497✔
1120
                        return value;
23,010,497✔
1121
                    }
1122

1123
                    // Another thread added a value for this key first, retrieve it.
1124
                    if (this.Lru.TryGet(actualKey, out V? existing))
447,320✔
1125
                    {
447,289✔
1126
                        return existing;
447,289✔
1127
                    }
1128
                }
31✔
1129
            }
23,457,786✔
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)
3,213✔
1151
            {
3,213✔
1152
                this.lru = lru;
3,213✔
1153
            }
3,213✔
1154

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

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

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

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

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

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

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

1173
            public event EventHandler<ItemRemovedEventArgs<K, V>> ItemRemoved
1174
            {
1175
                add { this.lru.telemetryPolicy.ItemRemoved += value; }
315✔
1176
                remove { this.lru.telemetryPolicy.ItemRemoved -= value; }
42✔
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; }
186✔
1184
                remove { this.lru.telemetryPolicy.ItemUpdated -= value; }
21✔
1185
            }
1186
#endif
1187
            public void Trim(int itemCount)
1188
            {
70✔
1189
                lru.Trim(itemCount);
70✔
1190
            }
70✔
1191

1192
            public void TrimExpired()
1193
            {
50✔
1194
                lru.TrimExpired();
50✔
1195
            }
50✔
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)
105✔
1203
            {
105✔
1204
                this.lru = lru;
105✔
1205
            }
105✔
1206

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

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

1221
                timeToLive = default;
14✔
1222
                return false;
14✔
1223
            }
21✔
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