< Summary

Information
Class: SwiftCollections.SwiftGenerationalBucket<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftGenerationalBucket.cs
Line coverage
97%
Covered lines: 174
Uncovered lines: 4
Coverable lines: 178
Total lines: 610
Line coverage: 97.7%
Branch coverage
80%
Covered branches: 74
Total branches: 92
Branch coverage: 80.4%
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(...)50%22100%
.ctor(...)50%44100%
get_Count()100%11100%
get_Capacity()100%11100%
get_State()100%44100%
set_State(...)50%88100%
GetStateSourceLength(...)100%11100%
GetStateCapacity(...)100%22100%
InitializeStateStorage(...)100%11100%
RestoreEntries(...)100%66100%
GetStateGeneration(...)50%2266.66%
IsStateIndexAllocated(...)50%22100%
RestoreAllocatedEntry(...)100%22100%
RestoreFreeIndices(...)100%44100%
NormalizePeak(...)100%22100%
Add(...)100%44100%
TryGet(...)100%66100%
GetRef(...)50%22100%
Remove(...)66.66%6691.66%
IsValid(...)50%4475%
EnsureCapacity(...)100%22100%
Resize(...)50%22100%
CloneTo(...)100%66100%
Exists(...)75%8888.88%
Find(...)100%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()50%22100%
MoveNext()100%44100%
Reset()100%11100%
Dispose()100%11100%

File(s)

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

#LineLine coverage
 1using Chronicler;
 2using MemoryPack;
 3using System;
 4using System.Collections;
 5using System.Collections.Generic;
 6using System.Text.Json.Serialization;
 7
 8namespace SwiftCollections;
 9
 10/// <summary>
 11/// Represents a high-performance generational bucket that assigns stable handles to stored items.
 12/// </summary>
 13/// <remarks>
 14/// <para>
 15/// <see cref="SwiftGenerationalBucket{T}"/> is similar to <see cref="SwiftBucket{T}"/> but adds
 16/// <b>generation tracking</b> to prevent stale references from accessing reused slots.
 17/// </para>
 18///
 19/// <para>
 20/// When an item is added, a <see cref="SwiftHandle"/> containing both an index and generation
 21/// is returned. If the item is removed and the slot reused later, the generation value
 22/// changes, causing older handles to automatically become invalid.
 23/// </para>
 24///
 25/// <para>
 26/// This pattern is widely used to safely reference objects without risking accidental access
 27/// to recycled memory slots.
 28/// </para>
 29///
 30/// <para>
 31/// Key characteristics:
 32/// <list type="bullet">
 33/// <item><description>O(1) insertion and removal.</description></item>
 34/// <item><description>Stable handles for the lifetime of stored items.</description></item>
 35/// <item><description>Automatic invalidation of stale handles via generation counters.</description></item>
 36/// <item><description>Cache-friendly contiguous storage.</description></item>
 37/// </list>
 38/// </para>
 39///
 40/// <para>
 41/// Use <see cref="SwiftBucket{T}"/> when raw indices are acceptable.
 42/// Use <see cref="SwiftGenerationalBucket{T}"/> when handle safety is required.
 43/// </para>
 44/// </remarks>
 45/// <typeparam name="T">Specifies the type of elements stored in the bucket.</typeparam>
 46[Serializable]
 47[JsonConverter(typeof(StateJsonConverterFactory))]
 48[MemoryPackable]
 49public sealed partial class SwiftGenerationalBucket<T> : IStateBacked<SwiftGenerationalBucketState<T>>, ISwiftCloneable<
 50{
 51    #region Nested Types
 52
 53    private struct Entry
 54    {
 55        public uint Generation;
 56        public bool IsUsed;
 57        public T Value;
 58    }
 59
 60    #endregion
 61
 62    #region Constants
 63
 64    /// <summary>
 65    /// Represents the default initial capacity for the collection.
 66    /// </summary>
 67    /// <remarks>
 68    /// Use this constant when initializing the collection to its default size.
 69    /// The value is typically used to optimize memory allocation for small collections.
 70    /// </remarks>
 71    public const int DefaultCapacity = 8;
 72
 73    #endregion
 74
 75    #region Fields
 76
 77    private Entry[] _entries;
 78    private SwiftIntStack _freeIndices;
 79
 80    private int _count;
 81    private int _peak;
 82
 83    private uint _version;
 84
 85    #endregion
 86
 87    #region Constructors
 88
 89    /// <summary>
 90    /// Initializes a new instance of the SwiftGenerationalBucket class with the default capacity.
 91    /// </summary>
 3092    public SwiftGenerationalBucket() : this(DefaultCapacity) { }
 93
 94    /// <summary>
 95    /// Initializes a new instance of the SwiftGenerationalBucket class with the specified initial capacity.
 96    /// </summary>
 97    /// <remarks>
 98    /// The actual capacity will be set to the next power of two greater than or equal to the specified capacity,
 99    /// or to the default capacity if the specified value is too small.
 100    /// This ensures efficient internal storage and lookup performance.
 101    /// </remarks>
 102    /// <param name="capacity">
 103    /// The initial number of elements that the bucket can contain.
 104    /// If less than or equal to the default capacity, the default capacity is used.
 105    /// Must be a non-negative integer.
 106    /// </param>
 17107    public SwiftGenerationalBucket(int capacity)
 108    {
 17109        capacity = capacity <= DefaultCapacity
 17110            ? DefaultCapacity
 17111            : SwiftHashTools.NextPowerOfTwo(capacity);
 112
 17113        _entries = new Entry[capacity];
 17114        _freeIndices = new SwiftIntStack(capacity);
 17115    }
 116
 117    ///  <summary>
 118    ///  Initializes a new instance of the <see cref="SwiftGenerationalBucket{T}"/> class with the specified <see cref="
 119    ///  </summary>
 120    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 121    [MemoryPackConstructor]
 6122    public SwiftGenerationalBucket(SwiftGenerationalBucketState<T> state)
 123    {
 6124        State = state;
 125        // Ensure that the internal structures are initialized even if the state is null or incomplete.
 5126        _entries ??= new Entry[DefaultCapacity];
 5127        _freeIndices ??= new SwiftIntStack(DefaultCapacity);
 5128    }
 129
 130    #endregion
 131
 132    #region Properties
 133
 134    /// <summary>
 135    /// Gets the number of elements contained in the collection.
 136    /// </summary>
 137    [JsonIgnore]
 138    [MemoryPackIgnore]
 9139    public int Count => _count;
 140
 141    /// <summary>
 142    /// Gets the total number of elements that the internal data structure can hold without resizing.
 143    /// </summary>
 144    /// <remarks>
 145    /// This value represents the allocated size of the underlying storage, which may be greater than the actual number 
 146    /// Capacity is always greater than or equal to the current count of elements.
 147    /// </remarks>
 148    [JsonIgnore]
 149    [MemoryPackIgnore]
 2150    public int Capacity => _entries.Length;
 151
 152    /// <summary>
 153    /// Gets or sets the current state of the generational bucket.
 154    /// </summary>
 155    /// <remarks>
 156    /// This property provides a snapshot of the bucket's internal state, which can be used for serialization, diagnosti
 157    /// or restoring the bucket to a previous state.
 158    /// Setting this property replaces the entire state of the bucket, including its contents and allocation metadata.
 159    /// </remarks>
 160    [JsonInclude]
 161    [MemoryPackInclude]
 162    public SwiftGenerationalBucketState<T> State
 163    {
 164        get
 165        {
 3166            int length = _entries.Length;
 167
 3168            var items = new T[length];
 3169            var allocated = new bool[length];
 3170            var generations = new uint[length];
 171
 166172            for (int i = 0; i < length; i++)
 173            {
 80174                generations[i] = _entries[i].Generation;
 175
 80176                if (_entries[i].IsUsed)
 177                {
 54178                    items[i] = _entries[i].Value;
 54179                    allocated[i] = true;
 180                }
 181            }
 182
 3183            int[] free = new int[_freeIndices.Count];
 3184            Array.Copy(_freeIndices.Array, free, _freeIndices.Count);
 185
 3186            return new SwiftGenerationalBucketState<T>(
 3187                items,
 3188                allocated,
 3189                generations,
 3190                free,
 3191                _peak
 3192            );
 193        }
 194        internal set
 195        {
 6196            var items = value.Items ?? Array.Empty<T>();
 6197            var allocated = value.Allocated ?? Array.Empty<bool>();
 6198            var generations = value.Generations ?? Array.Empty<uint>();
 6199            var freeIndices = value.FreeIndices ?? Array.Empty<int>();
 200
 6201            int sourceLength = GetStateSourceLength(items, allocated, generations);
 6202            int capacity = GetStateCapacity(sourceLength);
 6203            InitializeStateStorage(capacity, freeIndices.Length);
 204
 6205            int maxReferencedIndex = RestoreEntries(items, allocated, generations, sourceLength);
 6206            maxReferencedIndex = RestoreFreeIndices(freeIndices, capacity, maxReferencedIndex);
 207
 5208            _peak = NormalizePeak(value.Peak, maxReferencedIndex, capacity);
 5209            _version = 0;
 5210        }
 211    }
 212
 213    private static int GetStateSourceLength(T[] items, bool[] allocated, uint[] generations)
 214    {
 6215        return Math.Max(items.Length, Math.Max(allocated.Length, generations.Length));
 216    }
 217
 218    private static int GetStateCapacity(int sourceLength)
 219    {
 6220        if (sourceLength < DefaultCapacity)
 4221            return DefaultCapacity;
 222
 2223        return SwiftHashTools.NextPowerOfTwo(sourceLength);
 224    }
 225
 226    private void InitializeStateStorage(int capacity, int freeIndexCount)
 227    {
 6228        _entries = new Entry[capacity];
 6229        _freeIndices = new SwiftIntStack(Math.Max(SwiftIntStack.DefaultCapacity, freeIndexCount));
 6230        _count = 0;
 6231    }
 232
 233    private int RestoreEntries(T[] items, bool[] allocated, uint[] generations, int sourceLength)
 234    {
 6235        int maxReferencedIndex = -1;
 168236        for (int i = 0; i < sourceLength; i++)
 237        {
 78238            ref Entry entry = ref _entries[i];
 78239            bool isAllocated = IsStateIndexAllocated(allocated, i);
 240
 78241            entry.Generation = GetStateGeneration(generations, i);
 78242            if (entry.Generation != 0 || isAllocated)
 59243                maxReferencedIndex = i;
 244
 78245            if (isAllocated)
 58246                RestoreAllocatedEntry(ref entry, items, i);
 247        }
 248
 6249        return maxReferencedIndex;
 250    }
 251
 252    private static uint GetStateGeneration(uint[] generations, int index)
 253    {
 78254        if (generations.Length <= index)
 0255            return 0;
 256
 78257        return generations[index];
 258    }
 259
 260    private static bool IsStateIndexAllocated(bool[] allocated, int index)
 261    {
 78262        return allocated.Length > index && allocated[index];
 263    }
 264
 265    private void RestoreAllocatedEntry(ref Entry entry, T[] items, int index)
 266    {
 58267        if (items.Length > index)
 58268            entry.Value = items[index];
 269
 58270        entry.IsUsed = true;
 58271        _count++;
 58272    }
 273
 274    private int RestoreFreeIndices(int[] freeIndices, int capacity, int maxReferencedIndex)
 275    {
 15276        foreach (var index in freeIndices)
 277        {
 2278            SwiftThrowHelper.ThrowIfArgument((uint)index >= (uint)capacity, message: "Free index is out of range.");
 279
 1280            _freeIndices.Push(index);
 1281            if (index > maxReferencedIndex)
 1282                maxReferencedIndex = index;
 283        }
 284
 5285        return maxReferencedIndex;
 286    }
 287
 288    private static int NormalizePeak(int peak, int maxReferencedIndex, int capacity)
 289    {
 5290        if (peak < 0)
 1291            peak = 0;
 292
 5293        return Math.Min(Math.Max(peak, maxReferencedIndex + 1), capacity);
 294    }
 295
 296    #endregion
 297
 298    #region Core Operations
 299
 300    /// <summary>
 301    /// Adds the specified value to the collection and returns a handle that can be used to reference it.
 302    /// </summary>
 303    /// <remarks>
 304    /// The returned handle can be used to access or remove the value later.
 305    /// Handles are only valid as long as the value remains in the collection.
 306    /// </remarks>
 307    /// <param name="value">The value to add to the collection.</param>
 308    /// <returns>A <see cref="SwiftHandle"/> that uniquely identifies the added value within the collection.</returns>
 309    public SwiftHandle Add(T value)
 310    {
 311        int index;
 312
 342313        if (_freeIndices.Count == 0)
 314        {
 340315            index = _peak++;
 316
 340317            if ((uint)index >= (uint)_entries.Length)
 16318                Resize(_entries.Length * 2);
 319        }
 320        else
 321        {
 2322            index = _freeIndices.Pop();
 323        }
 324
 342325        ref Entry entry = ref _entries[index];
 326
 342327        entry.Value = value;
 342328        entry.IsUsed = true;
 329
 342330        _count++;
 342331        _version++;
 332
 342333        return new SwiftHandle(index, entry.Generation);
 334    }
 335
 336    /// <summary>
 337    /// Attempts to retrieve the value associated with the specified handle.
 338    /// </summary>
 339    /// <remarks>
 340    /// Use this method to safely attempt retrieval without throwing an exception if the handle is invalid or the entry 
 341    /// </remarks>
 342    /// <param name="handle">The handle used to identify the entry to retrieve.</param>
 343    /// <param name="value">
 344    /// When this method returns, contains the value associated with the specified handle if the handle is valid
 345    /// and the entry is in use; otherwise, the default value for the type of the value parameter.
 346    /// This parameter is passed uninitialized.
 347    /// </param>
 348    /// <returns>true if the value was found and retrieved successfully; otherwise, false.</returns>
 349    public bool TryGet(SwiftHandle handle, out T value)
 350    {
 210351        if ((uint)handle.Index >= (uint)_entries.Length)
 352        {
 1353            value = default!;
 1354            return false;
 355        }
 356
 209357        ref Entry entry = ref _entries[handle.Index];
 358
 209359        if (!entry.IsUsed || entry.Generation != handle.Generation)
 360        {
 2361            value = default!;
 2362            return false;
 363        }
 364
 207365        value = entry.Value;
 207366        return true;
 367    }
 368
 369    /// <summary>
 370    /// Returns a reference to the value associated with the specified handle.
 371    /// </summary>
 372    /// <param name="handle">
 373    /// A handle that identifies the entry whose value is to be accessed.
 374    /// The handle must be valid and refer to an existing entry.
 375    /// </param>
 376    /// <returns>A reference to the value of type T associated with the specified handle.</returns>
 377    /// <exception cref="InvalidOperationException">Thrown if the handle does not refer to a valid or currently used ent
 378    public ref T GetRef(SwiftHandle handle)
 379    {
 1380        ref Entry entry = ref _entries[handle.Index];
 381
 1382        SwiftThrowHelper.ThrowIfTrue(!entry.IsUsed || entry.Generation != handle.Generation, message: "Invalid handle");
 383
 1384        return ref entry.Value;
 385    }
 386
 387    /// <summary>
 388    /// Removes the entry associated with the specified handle from the collection.
 389    /// </summary>
 390    /// <remarks>
 391    /// If the handle does not refer to a valid or currently used entry, the method returns false and no action is taken
 392    /// Removing an entry invalidates the handle for future operations.
 393    /// </remarks>
 394    /// <param name="handle">The handle identifying the entry to remove. The handle must refer to a valid, currently use
 395    /// <returns>true if the entry was successfully removed; otherwise, false.</returns>
 396    public bool Remove(SwiftHandle handle)
 397    {
 3398        if ((uint)handle.Index >= (uint)_entries.Length)
 1399            return false;
 400
 2401        ref Entry entry = ref _entries[handle.Index];
 402
 2403        if (!entry.IsUsed || entry.Generation != handle.Generation)
 0404            return false;
 405
 2406        entry.Value = default!;
 2407        entry.IsUsed = false;
 408
 2409        entry.Generation++;
 410
 2411        _freeIndices.Push(handle.Index);
 412
 2413        _count--;
 2414        _version++;
 415
 2416        return true;
 417    }
 418
 419    /// <summary>
 420    /// Determines whether the specified handle refers to a valid and currently used entry.
 421    /// </summary>
 422    /// <remarks>
 423    /// A handle may become invalid if the referenced entry has been removed or replaced.
 424    /// Use this method to check handle validity before accessing the associated entry.
 425    /// </remarks>
 426    /// <param name="handle">The handle to validate. The handle must have been obtained from this collection; otherwise,
 427    /// <returns>true if the handle is valid and refers to an active entry; otherwise, false.</returns>
 428    public bool IsValid(SwiftHandle handle)
 429    {
 1430        if ((uint)handle.Index >= (uint)_entries.Length)
 0431            return false;
 432
 1433        ref Entry entry = ref _entries[handle.Index];
 434
 1435        return entry.IsUsed && entry.Generation == handle.Generation;
 436    }
 437
 438    #endregion
 439
 440    #region Capacity
 441
 442    /// <summary>
 443    /// Ensures that the underlying storage has at least the specified capacity, expanding it if necessary.
 444    /// </summary>
 445    /// <remarks>
 446    /// If the current capacity is less than the specified value, the storage is resized to accommodate at least that ma
 447    /// The actual capacity may be rounded up to the next power of two for performance reasons.
 448    /// </remarks>
 449    /// <param name="capacity">The minimum number of elements that the storage should be able to hold. Must be a non-neg
 450    public void EnsureCapacity(int capacity)
 451    {
 1452        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 1453        if (capacity > _entries.Length)
 1454            Resize(capacity);
 1455    }
 456
 457    private void Resize(int newSize)
 458    {
 17459        int newCapacity = newSize <= DefaultCapacity ? DefaultCapacity : newSize;
 460
 17461        Entry[] newArray = new Entry[newCapacity];
 17462        Array.Copy(_entries, newArray, _entries.Length);
 17463        _entries = newArray;
 17464    }
 465
 466    #endregion
 467
 468    #region Utility
 469
 470    /// <inheritdoc/>
 471    public void CloneTo(ICollection<T> output)
 472    {
 1473        SwiftThrowHelper.ThrowIfNull(output, nameof(output));
 474
 1475        output.Clear();
 476
 1477        uint count = 0;
 1478        uint peak = (uint)_peak;
 479
 42480        for (uint i = 0; i < peak && count < (uint)_count; i++)
 481        {
 20482            if (_entries[i].IsUsed)
 483            {
 20484                output.Add(_entries[i].Value);
 20485                count++;
 486            }
 487        }
 1488    }
 489
 490    /// <summary>
 491    /// Determines whether the <see cref="SwiftGenerationalBucket{T}"/> contains an element that matches the conditions 
 492    /// </summary>
 493    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 494    /// <returns><c>true</c> if the <see cref="SwiftGenerationalBucket{T}"/> contains one or more elements that match th
 495    public bool Exists(Predicate<T> match)
 496    {
 1497        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 498
 1499        uint count = 0;
 1500        uint peak = (uint)_peak;
 501
 4502        for (uint i = 0; i < peak && count < (uint)_count; i++)
 503        {
 2504            if (_entries[i].IsUsed)
 505            {
 2506                if (match(_entries[i].Value))
 1507                    return true;
 508
 1509                count++;
 510            }
 511        }
 512
 0513        return false;
 514    }
 515
 516    /// <summary>
 517    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 518    /// </summary>
 519    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 520    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 521    public T Find(Predicate<T> match)
 522    {
 2523        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 524
 2525        uint count = 0;
 2526        uint peak = (uint)_peak;
 527
 10528        for (uint i = 0; i < peak && count < (uint)_count; i++)
 529        {
 4530            if (_entries[i].IsUsed)
 531            {
 4532                T item = _entries[i].Value;
 4533                if (match(item))
 1534                    return item;
 535
 3536                count++;
 537            }
 538        }
 539
 1540        return default!;
 541    }
 542
 543    #endregion
 544
 545    #region Enumeration
 546
 547    /// <inheritdoc cref="IEnumerable.GetEnumerator()"/>
 6548    public SwiftGenerationalBucketEnumerator GetEnumerator() => new(this);
 1549    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 1550    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 551
 552    /// <summary>
 553    /// Enumerates the elements of a <see cref="SwiftGenerationalBucket{T}"/> collection in a forward-only, read-only ma
 554    /// </summary>
 555    /// <remarks>
 556    /// The enumerator is invalidated if the underlying collection is modified during enumeration.
 557    /// In such cases, subsequent calls to MoveNext will throw an InvalidOperationException.
 558    /// This enumerator is typically obtained by calling GetEnumerator on a <see cref="SwiftGenerationalBucket{T}"/> ins
 559    /// </remarks>
 560    public struct SwiftGenerationalBucketEnumerator : IEnumerator<T>
 561    {
 562        private readonly SwiftGenerationalBucket<T> _bucket;
 563        private readonly uint _version;
 564        private int _index;
 565        private T _current;
 566
 567        internal SwiftGenerationalBucketEnumerator(SwiftGenerationalBucket<T> bucket)
 568        {
 6569            _bucket = bucket;
 6570            _version = bucket._version;
 6571            _index = -1;
 6572            _current = default!;
 6573        }
 574
 575        /// <inheritdoc/>
 103576        public readonly T Current => _current;
 577
 1578        readonly object IEnumerator.Current => _current ?? throw new InvalidOperationException();
 579
 580        /// <inheritdoc/>
 581        public bool MoveNext()
 582        {
 110583            SwiftThrowHelper.ThrowIfTrue(_version != _bucket._version, message: "Collection modified");
 584
 109585            uint peak = (uint)_bucket._peak;
 109586            while (++_index < peak)
 587            {
 106588                if (_bucket._entries[_index].IsUsed)
 589                {
 106590                    _current = _bucket._entries[_index].Value;
 106591                    return true;
 592                }
 593            }
 594
 3595            return false;
 596        }
 597
 598        /// <inheritdoc/>
 599        public void Reset()
 600        {
 1601            _index = -1;
 1602            _current = default!;
 1603        }
 604
 605        /// <inheritdoc/>
 3606        public void Dispose() => _index = -1;
 607    }
 608
 609    #endregion
 610}