< Summary

Information
Class: SwiftCollections.SwiftGenerationalBucket<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftGenerationalBucket.cs
Line coverage
94%
Covered lines: 224
Uncovered lines: 14
Coverable lines: 238
Total lines: 488
Line coverage: 94.1%
Branch coverage
73%
Covered branches: 72
Total branches: 98
Branch coverage: 73.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%
Equals(...)50%22100%
Equals(...)50%22100%
GetHashCode()100%11100%
ToString()100%11100%
op_Equality(...)100%11100%
op_Inequality(...)100%11100%
.ctor()100%11100%
.ctor(...)50%22100%
.ctor(...)100%11100%
get_Count()100%11100%
get_Capacity()100%11100%
get_State()100%44100%
set_State(...)59.37%413279.54%
Add(...)100%44100%
TryGet(...)100%66100%
GetRef(...)50%4483.33%
Remove(...)66.66%6692.85%
IsValid(...)50%4483.33%
EnsureCapacity(...)100%22100%
Resize(...)50%22100%
CloneTo(...)100%66100%
Exists(...)75%8893.33%
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()100%11100%
MoveNext()83.33%6692.3%
Reset()100%11100%
Dispose()100%11100%

File(s)

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

#LineLine coverage
 1using MemoryPack;
 2using System;
 3using System.Collections;
 4using System.Collections.Generic;
 5using System.Text.Json.Serialization;
 6
 7namespace SwiftCollections;
 8
 9/// <summary>
 10/// Represents a high-performance generational bucket that assigns stable handles to stored items.
 11/// </summary>
 12/// <remarks>
 13/// <para>
 14/// <see cref="SwiftGenerationalBucket{T}"/> is similar to <see cref="SwiftBucket{T}"/> but adds
 15/// <b>generation tracking</b> to prevent stale references from accessing reused slots.
 16/// </para>
 17///
 18/// <para>
 19/// When an item is added, a <see cref="Handle"/> containing both an index and generation
 20/// is returned. If the item is removed and the slot reused later, the generation value
 21/// changes, causing older handles to automatically become invalid.
 22/// </para>
 23///
 24/// <para>
 25/// This pattern is widely used to safely reference objects without risking accidental access
 26/// to recycled memory slots.
 27/// </para>
 28///
 29/// <para>
 30/// Key characteristics:
 31/// <list type="bullet">
 32/// <item><description>O(1) insertion and removal.</description></item>
 33/// <item><description>Stable handles for the lifetime of stored items.</description></item>
 34/// <item><description>Automatic invalidation of stale handles via generation counters.</description></item>
 35/// <item><description>Cache-friendly contiguous storage.</description></item>
 36/// </list>
 37/// </para>
 38///
 39/// <para>
 40/// Use <see cref="SwiftBucket{T}"/> when raw indices are acceptable.
 41/// Use <see cref="SwiftGenerationalBucket{T}"/> when handle safety is required.
 42/// </para>
 43/// </remarks>
 44/// <typeparam name="T">Specifies the type of elements stored in the bucket.</typeparam>
 45[Serializable]
 46[JsonConverter(typeof(SwiftStateJsonConverterFactory))]
 47[MemoryPackable]
 48public sealed partial class SwiftGenerationalBucket<T> : ISwiftCloneable<T>, IEnumerable<T>
 49{
 50    #region Nested Types
 51
 52    public readonly struct Handle : IEquatable<Handle>
 53    {
 54        public readonly int Index;
 55        public readonly uint Generation;
 56
 57        public Handle(int index, uint generation)
 34858        {
 34859            Index = index;
 34860            Generation = generation;
 34861        }
 62
 63        public bool Equals(Handle other)
 464            => Index == other.Index && Generation == other.Generation;
 65
 66        public override bool Equals(object obj)
 167            => obj is Handle h && Equals(h);
 68
 69        public override int GetHashCode()
 270            => HashCode.Combine(Index, Generation);
 71
 72        public override string ToString()
 173            => $"Handle({Index}:{Generation})";
 74
 75        public static bool operator ==(Handle left, Handle right)
 276        {
 277            return left.Equals(right);
 278        }
 79
 80        public static bool operator !=(Handle left, Handle right)
 181        {
 182            return !(left == right);
 183        }
 84    }
 85
 86    private struct Entry
 87    {
 88        public uint Generation;
 89        public bool IsUsed;
 90        public T Value;
 91    }
 92
 93    #endregion
 94
 95    #region Constants
 96
 97    public const int DefaultCapacity = 8;
 98
 99    #endregion
 100
 101    #region Fields
 102
 103    private Entry[] _entries;
 104    private SwiftIntStack _freeIndices;
 105
 106    private int _count;
 107    private int _peak;
 108
 109    private uint _version;
 110
 111    #endregion
 112
 113    #region Constructors
 114
 45115    public SwiftGenerationalBucket() : this(DefaultCapacity) { }
 116
 17117    public SwiftGenerationalBucket(int capacity)
 17118    {
 17119        capacity = capacity <= DefaultCapacity
 17120            ? DefaultCapacity
 17121            : SwiftHashTools.NextPowerOfTwo(capacity);
 122
 17123        _entries = new Entry[capacity];
 17124        _freeIndices = new SwiftIntStack(capacity);
 17125    }
 126
 127    ///  <summary>
 128    ///  Initializes a new instance of the <see cref="SwiftGenerationalBucket{T}"/> class with the specified <see cref="
 129    ///  </summary>
 130    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 131    [MemoryPackConstructor]
 3132    public SwiftGenerationalBucket(SwiftGenerationalBucketState<T> state)
 3133    {
 3134        State = state;
 3135    }
 136
 137    #endregion
 138
 139    #region Properties
 140
 141    [JsonIgnore]
 142    [MemoryPackIgnore]
 9143    public int Count => _count;
 144
 145    [JsonIgnore]
 146    [MemoryPackIgnore]
 1147    public int Capacity => _entries.Length;
 148
 149    [JsonInclude]
 150    [MemoryPackInclude]
 151    public SwiftGenerationalBucketState<T> State
 152    {
 153        get
 2154        {
 2155            int length = _entries.Length;
 156
 2157            var items = new T[length];
 2158            var allocated = new bool[length];
 2159            var generations = new uint[length];
 160
 148161            for (int i = 0; i < length; i++)
 72162            {
 72163                generations[i] = _entries[i].Generation;
 164
 72165                if (_entries[i].IsUsed)
 53166                {
 53167                    items[i] = _entries[i].Value;
 53168                    allocated[i] = true;
 53169                }
 72170            }
 171
 2172            int[] free = new int[_freeIndices.Count];
 2173            Array.Copy(_freeIndices.Array, free, _freeIndices.Count);
 174
 2175            return new SwiftGenerationalBucketState<T>(
 2176                items,
 2177                allocated,
 2178                generations,
 2179                free,
 2180                _peak
 2181            );
 2182        }
 183        internal set
 3184        {
 3185            var items = value.Items ?? Array.Empty<T>();
 3186            var allocated = value.Allocated ?? Array.Empty<bool>();
 3187            var generations = value.Generations ?? Array.Empty<uint>();
 3188            var freeIndices = value.FreeIndices ?? Array.Empty<int>();
 189
 3190            int sourceLength = Math.Max(items.Length, Math.Max(allocated.Length, generations.Length));
 3191            int capacity = sourceLength < DefaultCapacity
 3192                ? DefaultCapacity
 3193                : SwiftHashTools.NextPowerOfTwo(sourceLength);
 194
 3195            _entries = new Entry[capacity];
 3196            _freeIndices = new SwiftIntStack(Math.Max(SwiftIntStack.DefaultCapacity, freeIndices.Length));
 197
 3198            _count = 0;
 3199            int maxReferencedIndex = -1;
 200
 156201            for (int i = 0; i < sourceLength; i++)
 75202            {
 75203                ref Entry entry = ref _entries[i];
 204
 75205                entry.Generation = generations.Length > i ? generations[i] : 0;
 75206                if (entry.Generation != 0)
 3207                    maxReferencedIndex = i;
 208
 75209                if (allocated.Length > i && allocated[i])
 55210                {
 55211                    if (items.Length > i)
 55212                        entry.Value = items[i];
 213
 55214                    entry.IsUsed = true;
 55215                    _count++;
 55216                    maxReferencedIndex = i;
 55217                }
 75218            }
 219
 9220            foreach (var index in freeIndices)
 0221            {
 0222                if ((uint)index >= (uint)capacity)
 0223                    throw new ArgumentException("Free index is out of range.");
 224
 0225                _freeIndices.Push(index);
 0226                if (index > maxReferencedIndex)
 0227                    maxReferencedIndex = index;
 0228            }
 229
 3230            int peak = value.Peak;
 3231            if (peak < 0)
 0232                peak = 0;
 233
 3234            _peak = Math.Max(peak, maxReferencedIndex + 1);
 3235            if (_peak > capacity)
 0236                _peak = capacity;
 237
 3238            _version = 0;
 3239        }
 240    }
 241
 242    #endregion
 243
 244    #region Core Operations
 245
 246    public Handle Add(T value)
 341247    {
 248        int index;
 249
 341250        if (_freeIndices.Count == 0)
 340251        {
 340252            index = _peak++;
 253
 340254            if ((uint)index >= (uint)_entries.Length)
 16255                Resize(_entries.Length * 2);
 340256        }
 257        else
 1258        {
 1259            index = _freeIndices.Pop();
 1260        }
 261
 341262        ref Entry entry = ref _entries[index];
 263
 341264        entry.Value = value;
 341265        entry.IsUsed = true;
 266
 341267        _count++;
 341268        _version++;
 269
 341270        return new Handle(index, entry.Generation);
 341271    }
 272
 273    public bool TryGet(Handle handle, out T value)
 208274    {
 208275        if ((uint)handle.Index >= (uint)_entries.Length)
 1276        {
 1277            value = default;
 1278            return false;
 279        }
 280
 207281        ref Entry entry = ref _entries[handle.Index];
 282
 207283        if (!entry.IsUsed || entry.Generation != handle.Generation)
 2284        {
 2285            value = default;
 2286            return false;
 287        }
 288
 205289        value = entry.Value;
 205290        return true;
 208291    }
 292
 293    public ref T GetRef(Handle handle)
 1294    {
 1295        ref Entry entry = ref _entries[handle.Index];
 296
 1297        if (!entry.IsUsed || entry.Generation != handle.Generation)
 0298            throw new InvalidOperationException("Invalid handle");
 299
 1300        return ref entry.Value;
 1301    }
 302
 303    public bool Remove(Handle handle)
 3304    {
 3305        if ((uint)handle.Index >= (uint)_entries.Length)
 1306            return false;
 307
 2308        ref Entry entry = ref _entries[handle.Index];
 309
 2310        if (!entry.IsUsed || entry.Generation != handle.Generation)
 0311            return false;
 312
 2313        entry.Value = default;
 2314        entry.IsUsed = false;
 315
 2316        entry.Generation++;
 317
 2318        _freeIndices.Push(handle.Index);
 319
 2320        _count--;
 2321        _version++;
 322
 2323        return true;
 3324    }
 325
 326    public bool IsValid(Handle handle)
 1327    {
 1328        if ((uint)handle.Index >= (uint)_entries.Length)
 0329            return false;
 330
 1331        ref Entry entry = ref _entries[handle.Index];
 332
 1333        return entry.IsUsed && entry.Generation == handle.Generation;
 1334    }
 335
 336    #endregion
 337
 338    #region Capacity
 339
 340    public void EnsureCapacity(int capacity)
 1341    {
 1342        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 1343        if (capacity > _entries.Length)
 1344            Resize(capacity);
 1345    }
 346
 347    private void Resize(int newSize)
 17348    {
 17349        int newCapacity = newSize <= DefaultCapacity ? DefaultCapacity : newSize;
 350
 17351        Entry[] newArray = new Entry[newCapacity];
 17352        Array.Copy(_entries, newArray, _entries.Length);
 17353        _entries = newArray;
 17354    }
 355
 356    #endregion
 357
 358    #region Utility
 359
 360    public void CloneTo(ICollection<T> output)
 1361    {
 1362        SwiftThrowHelper.ThrowIfNull(output, nameof(output));
 363
 1364        output.Clear();
 365
 1366        uint count = 0;
 1367        uint peak = (uint)_peak;
 368
 42369        for (uint i = 0; i < peak && count < (uint)_count; i++)
 20370        {
 20371            if (_entries[i].IsUsed)
 20372            {
 20373                output.Add(_entries[i].Value);
 20374                count++;
 20375            }
 20376        }
 1377    }
 378
 379    /// <summary>
 380    /// Determines whether the <see cref="SwiftGenerationalBucket{T}"/> contains an element that matches the conditions 
 381    /// </summary>
 382    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 383    /// <returns><c>true</c> if the <see cref="SwiftGenerationalBucket{T}"/> contains one or more elements that match th
 384    public bool Exists(Predicate<T> match)
 1385    {
 1386        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 387
 1388        uint count = 0;
 1389        uint peak = (uint)_peak;
 390
 4391        for (uint i = 0; i < peak && count < (uint)_count; i++)
 2392        {
 2393            if (_entries[i].IsUsed)
 2394            {
 2395                if (match(_entries[i].Value))
 1396                    return true;
 397
 1398                count++;
 1399            }
 1400        }
 401
 0402        return false;
 1403    }
 404
 405    /// <summary>
 406    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 407    /// </summary>
 408    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 409    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 410    public T Find(Predicate<T> match)
 2411    {
 2412        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 413
 2414        uint count = 0;
 2415        uint peak = (uint)_peak;
 416
 10417        for (uint i = 0; i < peak && count < (uint)_count; i++)
 4418        {
 4419            if (_entries[i].IsUsed)
 4420            {
 4421                T item = _entries[i].Value;
 4422                if (match(item))
 1423                    return item;
 424
 3425                count++;
 3426            }
 3427        }
 428
 1429        return default;
 2430    }
 431
 432    #endregion
 433
 434    #region Enumeration
 435
 6436    public Enumerator GetEnumerator() => new(this);
 437
 1438    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 1439    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 440
 441    public struct Enumerator : IEnumerator<T>
 442    {
 443        private readonly SwiftGenerationalBucket<T> _bucket;
 444        private readonly uint _version;
 445        private int _index;
 446        private T _current;
 447
 448        internal Enumerator(SwiftGenerationalBucket<T> bucket)
 6449        {
 6450            _bucket = bucket;
 6451            _version = bucket._version;
 6452            _index = -1;
 6453            _current = default;
 6454        }
 455
 103456        public readonly T Current => _current;
 457
 1458        readonly object IEnumerator.Current => _current;
 459
 460        public bool MoveNext()
 110461        {
 110462            if (_version != _bucket._version)
 1463                throw new InvalidOperationException("Collection modified");
 464
 109465            uint peak = (uint)_bucket._peak;
 109466            while (++_index < peak)
 106467            {
 106468                if (_bucket._entries[_index].IsUsed)
 106469                {
 106470                    _current = _bucket._entries[_index].Value;
 106471                    return true;
 472                }
 0473            }
 474
 3475            return false;
 109476        }
 477
 478        public void Reset()
 1479        {
 1480            _index = -1;
 1481            _current = default;
 1482        }
 483
 6484        public readonly void Dispose() { }
 485    }
 486
 487    #endregion
 488}
Generated by: ReportGenerator 5.5.4.0
04/03/2026 - 18:03:54
GitHub | reportgenerator.io

Methods/Properties

.ctor(System.Int32,System.UInt32)
Equals(SwiftCollections.SwiftGenerationalBucket`1/Handle<T>)
Equals(System.Object)
GetHashCode()
ToString()
op_Equality(SwiftCollections.SwiftGenerationalBucket`1/Handle<T>,SwiftCollections.SwiftGenerationalBucket`1/Handle<T>)
op_Inequality(SwiftCollections.SwiftGenerationalBucket`1/Handle<T>,SwiftCollections.SwiftGenerationalBucket`1/Handle<T>)
.ctor()
.ctor(System.Int32)
.ctor(SwiftCollections.SwiftGenerationalBucketState`1<T>)
get_Count()
get_Capacity()
get_State()
set_State(SwiftCollections.SwiftGenerationalBucketState`1<T>)
Add(T)
TryGet(SwiftCollections.SwiftGenerationalBucket`1/Handle<T>,T&)
GetRef(SwiftCollections.SwiftGenerationalBucket`1/Handle<T>)
Remove(SwiftCollections.SwiftGenerationalBucket`1/Handle<T>)
IsValid(SwiftCollections.SwiftGenerationalBucket`1/Handle<T>)
EnsureCapacity(System.Int32)
Resize(System.Int32)
CloneTo(System.Collections.Generic.ICollection`1<T>)
Exists(System.Predicate`1<T>)
Find(System.Predicate`1<T>)
GetEnumerator()
System.Collections.Generic.IEnumerable<T>.GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
.ctor(SwiftCollections.SwiftGenerationalBucket`1<T>)
get_Current()
System.Collections.IEnumerator.get_Current()
MoveNext()
Reset()
Dispose()