< Summary

Information
Class: SwiftCollections.SwiftGenerationalBucket<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftGenerationalBucket.cs
Line coverage
100%
Covered lines: 178
Uncovered lines: 0
Coverable lines: 178
Total lines: 620
Line coverage: 100%
Branch coverage
94%
Covered branches: 81
Total branches: 86
Branch coverage: 94.1%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor()100%11100%
.ctor(...)100%22100%
.ctor(...)100%11100%
get_Count()100%11100%
get_Capacity()100%11100%
get_State()100%44100%
set_State(...)100%88100%
GetStateSourceLength(...)100%11100%
GetStateCapacity(...)100%22100%
InitializeStateStorage(...)100%11100%
RestoreEntries(...)100%66100%
GetStateGeneration(...)100%22100%
IsStateIndexAllocated(...)100%22100%
RestoreAllocatedEntry(...)50%22100%
RestoreFreeIndices(...)75%44100%
NormalizePeak(...)100%22100%
Add(...)100%44100%
TryGet(...)100%66100%
GetRef(...)100%22100%
Remove(...)100%66100%
IsValid(...)100%44100%
EnsureCapacity(...)50%22100%
Resize(...)100%11100%
CloneTo(...)83.33%66100%
Exists(...)100%88100%
Find(...)87.5%88100%
GetEnumerator()100%11100%
System.Collections.Generic.IEnumerable<T>.GetEnumerator()100%11100%
System.Collections.IEnumerable.GetEnumerator()100%11100%
.ctor(...)100%11100%
get_Current()100%11100%
System.Collections.IEnumerator.get_Current()100%22100%
MoveNext()100%44100%
Reset()100%11100%
Dispose()100%11100%

File(s)

/home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftGenerationalBucket.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftGenerationalBucket.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using Chronicler;
 9using MemoryPack;
 10using SwiftCollections.Diagnostics;
 11using SwiftCollections.Utility;
 12using System;
 13using System.Collections;
 14using System.Collections.Generic;
 15using System.Text.Json.Serialization;
 16
 17namespace SwiftCollections;
 18
 19/// <summary>
 20/// Represents a high-performance generational bucket that assigns stable handles to stored items.
 21/// </summary>
 22/// <remarks>
 23/// <para>
 24/// <see cref="SwiftGenerationalBucket{T}"/> is similar to <see cref="SwiftBucket{T}"/> but adds
 25/// <b>generation tracking</b> to prevent stale references from accessing reused slots.
 26/// </para>
 27///
 28/// <para>
 29/// When an item is added, a <see cref="SwiftHandle"/> containing both an index and generation
 30/// is returned. If the item is removed and the slot reused later, the generation value
 31/// changes, causing older handles to automatically become invalid.
 32/// </para>
 33///
 34/// <para>
 35/// This pattern is widely used to safely reference objects without risking accidental access
 36/// to recycled memory slots.
 37/// </para>
 38///
 39/// <para>
 40/// Key characteristics:
 41/// <list type="bullet">
 42/// <item><description>O(1) insertion and removal.</description></item>
 43/// <item><description>Stable handles for the lifetime of stored items.</description></item>
 44/// <item><description>Automatic invalidation of stale handles via generation counters.</description></item>
 45/// <item><description>Cache-friendly contiguous storage.</description></item>
 46/// </list>
 47/// </para>
 48///
 49/// <para>
 50/// Use <see cref="SwiftBucket{T}"/> when raw indices are acceptable.
 51/// Use <see cref="SwiftGenerationalBucket{T}"/> when handle safety is required.
 52/// </para>
 53/// </remarks>
 54/// <typeparam name="T">Specifies the type of elements stored in the bucket.</typeparam>
 55[Serializable]
 56[JsonConverter(typeof(StateJsonConverterFactory))]
 57[MemoryPackable]
 58public sealed partial class SwiftGenerationalBucket<T> : IStateBacked<SwiftGenerationalBucketState<T>>, ISwiftCloneable<
 59{
 60    #region Nested Types
 61
 62    private struct Entry
 63    {
 64        public uint Generation;
 65        public bool IsUsed;
 66        public T Value;
 67    }
 68
 69    #endregion
 70
 71    #region Constants
 72
 73    /// <summary>
 74    /// Represents the default initial capacity for the collection.
 75    /// </summary>
 76    /// <remarks>
 77    /// Use this constant when initializing the collection to its default size.
 78    /// The value is typically used to optimize memory allocation for small collections.
 79    /// </remarks>
 80    public const int DefaultCapacity = 8;
 81
 82    #endregion
 83
 84    #region Fields
 85
 86    private Entry[] _entries;
 87    private SwiftIntStack _freeIndices;
 88
 89    private int _count;
 90    private int _peak;
 91
 92    private uint _version;
 93
 94    #endregion
 95
 96    #region Constructors
 97
 98    /// <summary>
 99    /// Initializes a new instance of the SwiftGenerationalBucket class with the default capacity.
 100    /// </summary>
 38101    public SwiftGenerationalBucket() : this(DefaultCapacity) { }
 102
 103    /// <summary>
 104    /// Initializes a new instance of the SwiftGenerationalBucket class with the specified initial capacity.
 105    /// </summary>
 106    /// <remarks>
 107    /// The actual capacity will be set to the next power of two greater than or equal to the specified capacity,
 108    /// or to the default capacity if the specified value is too small.
 109    /// This ensures efficient internal storage and lookup performance.
 110    /// </remarks>
 111    /// <param name="capacity">
 112    /// The initial number of elements that the bucket can contain.
 113    /// If less than or equal to the default capacity, the default capacity is used.
 114    /// Must be a non-negative integer.
 115    /// </param>
 23116    public SwiftGenerationalBucket(int capacity)
 117    {
 23118        capacity = capacity <= DefaultCapacity
 23119            ? DefaultCapacity
 23120            : SwiftHashTools.NextPowerOfTwo(capacity);
 121
 23122        _entries = new Entry[capacity];
 23123        _freeIndices = new SwiftIntStack(capacity);
 23124    }
 125
 126    ///  <summary>
 127    ///  Initializes a new instance of the <see cref="SwiftGenerationalBucket{T}"/> class with the specified <see cref="
 128    ///  </summary>
 129    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 130    [MemoryPackConstructor]
 8131    public SwiftGenerationalBucket(SwiftGenerationalBucketState<T> state)
 132    {
 8133        _entries = Array.Empty<Entry>();
 8134        _freeIndices = new SwiftIntStack(0);
 135
 8136        State = state;
 7137    }
 138
 139    #endregion
 140
 141    #region Properties
 142
 143    /// <summary>
 144    /// Gets the number of elements contained in the collection.
 145    /// </summary>
 146    [JsonIgnore]
 147    [MemoryPackIgnore]
 11148    public int Count => _count;
 149
 150    /// <summary>
 151    /// Gets the total number of elements that the internal data structure can hold without resizing.
 152    /// </summary>
 153    /// <remarks>
 154    /// This value represents the allocated size of the underlying storage, which may be greater than the actual number 
 155    /// Capacity is always greater than or equal to the current count of elements.
 156    /// </remarks>
 157    [JsonIgnore]
 158    [MemoryPackIgnore]
 6159    public int Capacity => _entries.Length;
 160
 161    /// <summary>
 162    /// Gets or sets the current state of the generational bucket.
 163    /// </summary>
 164    /// <remarks>
 165    /// This property provides a snapshot of the bucket's internal state, which can be used for serialization, diagnosti
 166    /// or restoring the bucket to a previous state.
 167    /// Setting this property replaces the entire state of the bucket, including its contents and allocation metadata.
 168    /// </remarks>
 169    [JsonInclude]
 170    [MemoryPackInclude]
 171    public SwiftGenerationalBucketState<T> State
 172    {
 173        get
 174        {
 3175            int length = _entries.Length;
 176
 3177            var items = new T[length];
 3178            var allocated = new bool[length];
 3179            var generations = new uint[length];
 180
 166181            for (int i = 0; i < length; i++)
 182            {
 80183                generations[i] = _entries[i].Generation;
 184
 80185                if (_entries[i].IsUsed)
 186                {
 54187                    items[i] = _entries[i].Value;
 54188                    allocated[i] = true;
 189                }
 190            }
 191
 3192            int[] free = new int[_freeIndices.Count];
 3193            Array.Copy(_freeIndices.Array, free, _freeIndices.Count);
 194
 3195            return new SwiftGenerationalBucketState<T>(
 3196                items,
 3197                allocated,
 3198                generations,
 3199                free,
 3200                _peak
 3201            );
 202        }
 203        internal set
 204        {
 8205            var items = value.Items ?? Array.Empty<T>();
 8206            var allocated = value.Allocated ?? Array.Empty<bool>();
 8207            var generations = value.Generations ?? Array.Empty<uint>();
 8208            var freeIndices = value.FreeIndices ?? Array.Empty<int>();
 209
 8210            int sourceLength = GetStateSourceLength(items, allocated, generations);
 8211            int capacity = GetStateCapacity(sourceLength);
 8212            InitializeStateStorage(capacity, freeIndices.Length);
 213
 8214            int maxReferencedIndex = RestoreEntries(items, allocated, generations, sourceLength);
 8215            maxReferencedIndex = RestoreFreeIndices(freeIndices, capacity, maxReferencedIndex);
 216
 7217            _peak = NormalizePeak(value.Peak, maxReferencedIndex, capacity);
 7218            _version = 0;
 7219        }
 220    }
 221
 222    private static int GetStateSourceLength(T[] items, bool[] allocated, uint[] generations)
 223    {
 8224        return Math.Max(items.Length, Math.Max(allocated.Length, generations.Length));
 225    }
 226
 227    private static int GetStateCapacity(int sourceLength)
 228    {
 8229        if (sourceLength < DefaultCapacity)
 6230            return DefaultCapacity;
 231
 2232        return SwiftHashTools.NextPowerOfTwo(sourceLength);
 233    }
 234
 235    private void InitializeStateStorage(int capacity, int freeIndexCount)
 236    {
 8237        _entries = new Entry[capacity];
 8238        _freeIndices = new SwiftIntStack(Math.Max(SwiftIntStack.DefaultCapacity, freeIndexCount));
 8239        _count = 0;
 8240    }
 241
 242    private int RestoreEntries(T[] items, bool[] allocated, uint[] generations, int sourceLength)
 243    {
 8244        int maxReferencedIndex = -1;
 178245        for (int i = 0; i < sourceLength; i++)
 246        {
 81247            ref Entry entry = ref _entries[i];
 81248            bool isAllocated = IsStateIndexAllocated(allocated, i);
 249
 81250            entry.Generation = GetStateGeneration(generations, i);
 81251            if (entry.Generation != 0 || isAllocated)
 60252                maxReferencedIndex = i;
 253
 81254            if (isAllocated)
 59255                RestoreAllocatedEntry(ref entry, items, i);
 256        }
 257
 8258        return maxReferencedIndex;
 259    }
 260
 261    private static uint GetStateGeneration(uint[] generations, int index)
 262    {
 81263        if (generations.Length <= index)
 2264            return 0;
 265
 79266        return generations[index];
 267    }
 268
 269    private static bool IsStateIndexAllocated(bool[] allocated, int index)
 270    {
 81271        return allocated.Length > index && allocated[index];
 272    }
 273
 274    private void RestoreAllocatedEntry(ref Entry entry, T[] items, int index)
 275    {
 59276        if (items.Length > index)
 59277            entry.Value = items[index];
 278
 59279        entry.IsUsed = true;
 59280        _count++;
 59281    }
 282
 283    private int RestoreFreeIndices(int[] freeIndices, int capacity, int maxReferencedIndex)
 284    {
 19285        foreach (var index in freeIndices)
 286        {
 2287            SwiftThrowHelper.ThrowIfArgument((uint)index >= (uint)capacity, message: "Free index is out of range.");
 288
 1289            _freeIndices.Push(index);
 1290            if (index > maxReferencedIndex)
 1291                maxReferencedIndex = index;
 292        }
 293
 7294        return maxReferencedIndex;
 295    }
 296
 297    private static int NormalizePeak(int peak, int maxReferencedIndex, int capacity)
 298    {
 7299        if (peak < 0)
 1300            peak = 0;
 301
 7302        return Math.Min(Math.Max(peak, maxReferencedIndex + 1), capacity);
 303    }
 304
 305    #endregion
 306
 307    #region Core Operations
 308
 309    /// <summary>
 310    /// Adds the specified value to the collection and returns a handle that can be used to reference it.
 311    /// </summary>
 312    /// <remarks>
 313    /// The returned handle can be used to access or remove the value later.
 314    /// Handles are only valid as long as the value remains in the collection.
 315    /// </remarks>
 316    /// <param name="value">The value to add to the collection.</param>
 317    /// <returns>A <see cref="SwiftHandle"/> that uniquely identifies the added value within the collection.</returns>
 318    public SwiftHandle Add(T value)
 319    {
 320        int index;
 321
 348322        if (_freeIndices.Count == 0)
 323        {
 346324            index = _peak++;
 325
 346326            if ((uint)index >= (uint)_entries.Length)
 16327                Resize(_entries.Length * 2);
 328        }
 329        else
 330        {
 2331            index = _freeIndices.Pop();
 332        }
 333
 348334        ref Entry entry = ref _entries[index];
 335
 348336        entry.Value = value;
 348337        entry.IsUsed = true;
 338
 348339        _count++;
 348340        _version++;
 341
 348342        return new SwiftHandle(index, entry.Generation);
 343    }
 344
 345    /// <summary>
 346    /// Attempts to retrieve the value associated with the specified handle.
 347    /// </summary>
 348    /// <remarks>
 349    /// Use this method to safely attempt retrieval without throwing an exception if the handle is invalid or the entry 
 350    /// </remarks>
 351    /// <param name="handle">The handle used to identify the entry to retrieve.</param>
 352    /// <param name="value">
 353    /// When this method returns, contains the value associated with the specified handle if the handle is valid
 354    /// and the entry is in use; otherwise, the default value for the type of the value parameter.
 355    /// This parameter is passed uninitialized.
 356    /// </param>
 357    /// <returns>true if the value was found and retrieved successfully; otherwise, false.</returns>
 358    public bool TryGet(SwiftHandle handle, out T value)
 359    {
 212360        if ((uint)handle.Index >= (uint)_entries.Length)
 361        {
 1362            value = default!;
 1363            return false;
 364        }
 365
 211366        ref Entry entry = ref _entries[handle.Index];
 367
 211368        if (!entry.IsUsed || entry.Generation != handle.Generation)
 369        {
 3370            value = default!;
 3371            return false;
 372        }
 373
 208374        value = entry.Value;
 208375        return true;
 376    }
 377
 378    /// <summary>
 379    /// Returns a reference to the value associated with the specified handle.
 380    /// </summary>
 381    /// <param name="handle">
 382    /// A handle that identifies the entry whose value is to be accessed.
 383    /// The handle must be valid and refer to an existing entry.
 384    /// </param>
 385    /// <returns>A reference to the value of type T associated with the specified handle.</returns>
 386    /// <exception cref="InvalidOperationException">Thrown if the handle does not refer to a valid or currently used ent
 387    public ref T GetRef(SwiftHandle handle)
 388    {
 3389        ref Entry entry = ref _entries[handle.Index];
 390
 3391        SwiftThrowHelper.ThrowIfTrue(!entry.IsUsed || entry.Generation != handle.Generation, message: "Invalid handle");
 392
 1393        return ref entry.Value;
 394    }
 395
 396    /// <summary>
 397    /// Removes the entry associated with the specified handle from the collection.
 398    /// </summary>
 399    /// <remarks>
 400    /// If the handle does not refer to a valid or currently used entry, the method returns false and no action is taken
 401    /// Removing an entry invalidates the handle for future operations.
 402    /// </remarks>
 403    /// <param name="handle">The handle identifying the entry to remove. The handle must refer to a valid, currently use
 404    /// <returns>true if the entry was successfully removed; otherwise, false.</returns>
 405    public bool Remove(SwiftHandle handle)
 406    {
 8407        if ((uint)handle.Index >= (uint)_entries.Length)
 1408            return false;
 409
 7410        ref Entry entry = ref _entries[handle.Index];
 411
 7412        if (!entry.IsUsed || entry.Generation != handle.Generation)
 2413            return false;
 414
 5415        entry.Value = default!;
 5416        entry.IsUsed = false;
 417
 5418        entry.Generation++;
 419
 5420        _freeIndices.Push(handle.Index);
 421
 5422        _count--;
 5423        _version++;
 424
 5425        return true;
 426    }
 427
 428    /// <summary>
 429    /// Determines whether the specified handle refers to a valid and currently used entry.
 430    /// </summary>
 431    /// <remarks>
 432    /// A handle may become invalid if the referenced entry has been removed or replaced.
 433    /// Use this method to check handle validity before accessing the associated entry.
 434    /// </remarks>
 435    /// <param name="handle">The handle to validate. The handle must have been obtained from this collection; otherwise,
 436    /// <returns>true if the handle is valid and refers to an active entry; otherwise, false.</returns>
 437    public bool IsValid(SwiftHandle handle)
 438    {
 5439        if ((uint)handle.Index >= (uint)_entries.Length)
 1440            return false;
 441
 4442        ref Entry entry = ref _entries[handle.Index];
 443
 4444        return entry.IsUsed && entry.Generation == handle.Generation;
 445    }
 446
 447    #endregion
 448
 449    #region Capacity
 450
 451    /// <summary>
 452    /// Ensures that the underlying storage has at least the specified capacity, expanding it if necessary.
 453    /// </summary>
 454    /// <remarks>
 455    /// If the current capacity is less than the specified value, the storage is resized to accommodate at least that ma
 456    /// The actual capacity may be rounded up to the next power of two for performance reasons.
 457    /// </remarks>
 458    /// <param name="capacity">The minimum number of elements that the storage should be able to hold. Must be a non-neg
 459    public void EnsureCapacity(int capacity)
 460    {
 1461        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 1462        if (capacity > _entries.Length)
 1463            Resize(capacity);
 1464    }
 465
 466    private void Resize(int newSize)
 467    {
 17468        Entry[] newArray = new Entry[newSize];
 17469        Array.Copy(_entries, newArray, _entries.Length);
 17470        _entries = newArray;
 17471    }
 472
 473    #endregion
 474
 475    #region Utility
 476
 477    /// <inheritdoc/>
 478    public void CloneTo(ICollection<T> output)
 479    {
 1480        SwiftThrowHelper.ThrowIfNull(output, nameof(output));
 481
 1482        output.Clear();
 483
 1484        uint count = 0;
 1485        uint peak = (uint)_peak;
 486
 42487        for (uint i = 0; i < peak && count < (uint)_count; i++)
 488        {
 20489            if (_entries[i].IsUsed)
 490            {
 20491                output.Add(_entries[i].Value);
 20492                count++;
 493            }
 494        }
 1495    }
 496
 497    /// <summary>
 498    /// Determines whether the <see cref="SwiftGenerationalBucket{T}"/> contains an element that matches the conditions 
 499    /// </summary>
 500    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 501    /// <returns><c>true</c> if the <see cref="SwiftGenerationalBucket{T}"/> contains one or more elements that match th
 502    public bool Exists(Predicate<T> match)
 503    {
 3504        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 505
 3506        uint count = 0;
 3507        uint peak = (uint)_peak;
 508
 10509        for (uint i = 0; i < peak; i++)
 510        {
 5511            if (count >= (uint)_count)
 512                break;
 513
 4514            if (_entries[i].IsUsed)
 515            {
 3516                if (match(_entries[i].Value))
 2517                    return true;
 518
 1519                count++;
 520            }
 521        }
 522
 1523        return false;
 524    }
 525
 526    /// <summary>
 527    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 528    /// </summary>
 529    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 530    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 531    public T Find(Predicate<T> match)
 532    {
 2533        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 534
 2535        uint count = 0;
 2536        uint peak = (uint)_peak;
 537
 10538        for (uint i = 0; i < peak && count < (uint)_count; i++)
 539        {
 4540            if (_entries[i].IsUsed)
 541            {
 4542                T item = _entries[i].Value;
 4543                if (match(item))
 1544                    return item;
 545
 3546                count++;
 547            }
 548        }
 549
 1550        return default!;
 551    }
 552
 553    #endregion
 554
 555    #region Enumeration
 556
 557    /// <inheritdoc cref="IEnumerable.GetEnumerator()"/>
 8558    public SwiftGenerationalBucketEnumerator GetEnumerator() => new(this);
 1559    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 2560    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 561
 562    /// <summary>
 563    /// Enumerates the elements of a <see cref="SwiftGenerationalBucket{T}"/> collection in a forward-only, read-only ma
 564    /// </summary>
 565    /// <remarks>
 566    /// The enumerator is invalidated if the underlying collection is modified during enumeration.
 567    /// In such cases, subsequent calls to MoveNext will throw an InvalidOperationException.
 568    /// This enumerator is typically obtained by calling GetEnumerator on a <see cref="SwiftGenerationalBucket{T}"/> ins
 569    /// </remarks>
 570    public struct SwiftGenerationalBucketEnumerator : IEnumerator<T>
 571    {
 572        private readonly SwiftGenerationalBucket<T> _bucket;
 573        private readonly uint _version;
 574        private int _index;
 575        private T _current;
 576
 577        internal SwiftGenerationalBucketEnumerator(SwiftGenerationalBucket<T> bucket)
 578        {
 8579            _bucket = bucket;
 8580            _version = bucket._version;
 8581            _index = -1;
 8582            _current = default!;
 8583        }
 584
 585        /// <inheritdoc/>
 104586        public readonly T Current => _current;
 587
 2588        readonly object IEnumerator.Current => _current ?? throw new InvalidOperationException();
 589
 590        /// <inheritdoc/>
 591        public bool MoveNext()
 592        {
 112593            SwiftThrowHelper.ThrowIfTrue(_version != _bucket._version, message: "Collection modified");
 594
 111595            uint peak = (uint)_bucket._peak;
 112596            while (++_index < peak)
 597            {
 108598                if (_bucket._entries[_index].IsUsed)
 599                {
 107600                    _current = _bucket._entries[_index].Value;
 107601                    return true;
 602                }
 603            }
 604
 4605            return false;
 606        }
 607
 608        /// <inheritdoc/>
 609        public void Reset()
 610        {
 1611            _index = -1;
 1612            _current = default!;
 1613        }
 614
 615        /// <inheritdoc/>
 4616        public void Dispose() => _index = -1;
 617    }
 618
 619    #endregion
 620}