< Summary

Information
Class: SwiftCollections.SwiftHashSet<T>
Assembly: SwiftCollections
File(s): File 1: /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftHashSet.cs
File 2: /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftHashSet.SwiftHashSetEnumerator.cs
Line coverage
100%
Covered lines: 382
Uncovered lines: 0
Coverable lines: 382
Total lines: 1062
Line coverage: 100%
Branch coverage
100%
Covered branches: 220
Total branches: 220
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
File 1: .cctor()100%44100%
File 1: .ctor()100%11100%
File 1: .ctor(...)100%11100%
File 1: .ctor(...)100%11100%
File 1: .ctor(...)100%44100%
File 1: .ctor(...)100%11100%
File 1: get_Count()100%11100%
File 1: get_Comparer()100%11100%
File 1: System.Collections.Generic.ICollection<T>.get_IsReadOnly()100%11100%
File 1: get_Item(...)100%22100%
File 1: get_State()100%22100%
File 1: set_State(...)100%66100%
File 1: Add(...)100%11100%
File 1: System.Collections.Generic.ICollection<T>.Add(...)100%11100%
File 1: AddRange(...)100%66100%
File 1: AddKnownCountRange(...)100%44100%
File 1: AddUnknownCountRange(...)100%44100%
File 1: InsertIfNotExists(...)100%2626100%
File 1: Remove(...)100%1414100%
File 1: Clear()100%44100%
File 1: Clear(...)100%66100%
File 1: CheckLoadThreshold()100%22100%
File 1: EnsureCapacityForAddRange(...)100%22100%
File 1: EnsureCapacity(...)100%22100%
File 1: Resize(...)100%88100%
File 1: TrimExcess()100%1212100%
File 1: CalculateAdaptiveResizeFactors(...)100%66100%
File 1: Initialize(...)100%22100%
File 1: Contains(...)100%11100%
File 1: Exists(...)100%66100%
File 1: Find(...)100%66100%
File 1: TryGetValue(...)100%22100%
File 1: CopyTo(...)100%44100%
File 1: SetComparer(...)100%22100%
File 1: SwitchToRandomizedComparer()100%11100%
File 1: RehashEntries()100%88100%
File 1: FindEntry(...)100%1616100%
File 1: GetEnumerator()100%11100%
File 1: System.Collections.Generic.IEnumerable<T>.GetEnumerator()100%11100%
File 1: System.Collections.IEnumerable.GetEnumerator()100%11100%
File 1: ExceptWith(...)100%44100%
File 1: IntersectWith(...)100%88100%
File 1: IsProperSubsetOf(...)100%88100%
File 1: IsProperSupersetOf(...)100%66100%
File 1: IsSubsetOf(...)100%88100%
File 1: IsSupersetOf(...)100%44100%
File 1: Overlaps(...)100%44100%
File 1: SetEquals(...)100%66100%
File 1: SymmetricExceptWith(...)100%66100%
File 1: UnionWith(...)100%22100%
File 2: .ctor(...)100%11100%
File 2: get_Current()100%11100%
File 2: System.Collections.IEnumerator.get_Current()100%11100%
File 2: MoveNext()100%44100%
File 2: Reset()100%11100%
File 2: Dispose()100%11100%

File(s)

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

#LineLine coverage
 1//=======================================================================
 2// SwiftHashSet.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 System;
 9using System.Collections;
 10using System.Collections.Generic;
 11using System.Runtime.CompilerServices;
 12using System.Text.Json.Serialization;
 13using Chronicler;
 14using Chronicler.Diagnostics;
 15using Chronicler.Serialization;
 16using MemoryPack;
 17using SwiftCollections.Utility;
 18
 19namespace SwiftCollections;
 20
 21/// <summary>
 22/// Represents a high-performance set of unique values with efficient operations for addition, removal, and lookup
 23/// </summary>
 24/// <typeparam name="T">The type of elements in the set.</typeparam>
 25/// <remarks>
 26/// The comparer is not serialized. After deserialization the set reverts
 27/// to the same default comparer selection used by a new instance. String values
 28/// use SwiftCollections' deterministic default comparer. Object values use a
 29/// SwiftCollections comparer that hashes strings deterministically, while other
 30/// object-value determinism still depends on the underlying value type's
 31/// <see cref="object.GetHashCode()"/> implementation. Other types use
 32/// <see cref="EqualityComparer{T}.Default"/>.
 33///
 34/// If a custom comparer is required it can be reapplied using
 35/// <see cref="SetComparer(IEqualityComparer{T})"/>.
 36/// </remarks>
 37[Serializable]
 38[JsonConverter(typeof(StateJsonConverterFactory))]
 39[MemoryPackable]
 40public sealed partial class SwiftHashSet<T> : IStateBacked<SwiftArrayState<T>>, ISet<T>, ICollection<T>, IEnumerable<T>,
 41    where T : notnull
 42{
 43    #region Constants
 44
 45    /// <summary>
 46    /// The default initial capacity of the set.
 47    /// </summary>
 48    public const int DefaultCapacity = 8;
 49
 50    /// <summary>
 51    /// Determines the maximum allowable load factor before resizing the hash set to maintain performance.
 52    /// </summary>
 53    private const float _LoadFactorThreshold = 0.85f;
 54
 55    #endregion
 56
 57    #region Fields
 58
 59    /// <summary>
 60    /// The array containing the entries of the SwiftHashSet.
 61    /// </summary>
 62    /// <remarks>
 63    /// Capacity will always be a power of two for efficient pooling cache.
 64    /// </remarks>
 65    internal Entry[] _entries;
 66
 67    /// <summary>
 68    /// The total number of entries in the hash set
 69    /// </summary>
 70    private int _count;
 71
 72    private int _lastIndex;
 73
 74    // A cold lookup must not box a default value while initializing this flag.
 1075    private static readonly bool _ItemCanBeNull = !typeof(T).IsValueType
 1076        || (typeof(T).IsGenericType && typeof(T).GetGenericTypeDefinition() == typeof(Nullable<>));
 77
 78    /// <summary>
 79    /// A mask used for efficiently computing the entry index from a hash code.
 80    /// This is typically the size of the entry array minus one, assuming the size is a power of two.
 81    /// </summary>
 82    private int _entryMask;
 83
 84    /// <summary>
 85    /// The comparer used to determine equality of keys and to generate hash codes.
 86    /// </summary>
 87    private IEqualityComparer<T> _comparer;
 88
 89    /// <summary>
 90    /// Specifies the dynamic growth factor for resizing, adjusted based on recent usage patterns.
 91    /// </summary>
 92    private int _adaptiveResizeFactor;
 93
 94    /// <summary>
 95    /// Tracks the count threshold at which the hash set should resize based on the load factor.
 96    /// </summary>
 97    private uint _nextResizeCount;
 98
 99    /// <summary>
 100    /// Represents the moving average of the fill rate, used to dynamically adjust resizing behavior.
 101    /// </summary>
 102    private double _movingFillRate;
 103
 104    private int _maxStepCount;
 105
 106    /// <summary>
 107    /// A version counter used to track modifications to the set.
 108    /// Incremented on mutations to detect changes during enumeration and ensure enumerator validity.
 109    /// </summary>
 110    private uint _version;
 111
 112    #endregion
 113
 114    #region Constructors
 115
 116    /// <summary>
 117    /// Initialize a new instance of <see cref="SwiftHashSet{T}"/> with customizable capacity and comparer for optimal p
 118    /// </summary>
 158119    public SwiftHashSet() : this(DefaultCapacity, null) { }
 120
 121    /// <inheritdoc cref="SwiftHashSet()"/>
 12122    public SwiftHashSet(IEqualityComparer<T>? comparer) : this(DefaultCapacity, comparer) { }
 123
 124    /// <summary>
 125    /// Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class that is empty and has the default initial 
 126    /// </summary>
 109127    public SwiftHashSet(int capacity, IEqualityComparer<T>? comparer = null)
 128    {
 109129        Initialize(capacity, comparer);
 130
 109131        ChronicleGuard.ThrowIfNull(_entries, nameof(_entries));
 109132        ChronicleGuard.ThrowIfNull(_comparer, nameof(_comparer));
 109133    }
 134
 135    /// <summary>
 136    /// Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class that contains elements copied from the spe
 137    /// </summary>
 138    /// <param name="collection">The collection whose elements are copied to the new set.</param>
 139    /// <param name="comparer">The comparer to use when comparing elements.</param>
 59140    public SwiftHashSet(IEnumerable<T> collection, IEqualityComparer<T>? comparer = null)
 141    {
 59142        ChronicleGuard.ThrowIfNull(collection, nameof(collection));
 143
 59144        int count = (collection as ICollection<T>)?.Count ?? DefaultCapacity;
 59145        int size = (int)(count / _LoadFactorThreshold);  // Dynamic padding based on collision estimation
 59146        Initialize(size, comparer);
 147
 59148        ChronicleGuard.ThrowIfNull(_entries, nameof(_entries));
 59149        ChronicleGuard.ThrowIfNull(_comparer, nameof(_comparer));
 150
 492151        foreach (T item in collection)
 187152            InsertIfNotExists(item);
 59153    }
 154
 155    ///  <summary>
 156    ///  Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class with the specified <see cref="SwiftArrayS
 157    ///  </summary>
 158    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 159    [MemoryPackConstructor]
 7160    public SwiftHashSet(SwiftArrayState<T> state)
 161    {
 7162        State = state;
 163
 7164        ChronicleGuard.ThrowIfNull(_entries, nameof(_entries));
 7165        ChronicleGuard.ThrowIfNull(_comparer, nameof(_comparer));
 7166    }
 167
 168    #endregion
 169
 170    #region Properties
 171
 172    /// <summary>
 173    /// Gets the number of elements contained in the set.
 174    /// </summary>
 175    [JsonIgnore]
 176    [MemoryPackIgnore]
 83177    public int Count => _count;
 178
 179    /// <summary>
 180    /// Gets the <see cref="IEqualityComparer{T}"/> object that is used to determine equality for the values in the set.
 181    /// </summary>
 182    [JsonIgnore]
 183    [MemoryPackIgnore]
 14184    public IEqualityComparer<T> Comparer => _comparer;
 185
 186    [JsonIgnore]
 187    [MemoryPackIgnore]
 1188    bool ICollection<T>.IsReadOnly => false;
 189
 190    /// <summary>
 191    /// Gets the stored value that matches the specified key.
 192    /// </summary>
 193    /// <param name="key">The lookup value used to find an equal element in the set.</param>
 194    /// <exception cref="KeyNotFoundException">No matching value exists in the set.</exception>
 195    [JsonIgnore]
 196    [MemoryPackIgnore]
 197    public T this[T key]
 198    {
 199        get
 200        {
 388201            int index = FindEntry(key);
 202            // The object-based error helper would box a value key even on a successful lookup.
 388203            if (index < 0)
 2204                ChronicleGuard.ThrowIfKeyInvalid(index, key);
 386205            return _entries[index].Value;
 206        }
 207    }
 208
 209    /// <summary>
 210    /// Gets or sets the current state of the array, including its items and structure.
 211    /// </summary>
 212    /// <remarks>
 213    /// Setting this property replaces the contents of the array with the items from the specified state.
 214    /// If the provided state is empty, the array is cleared.
 215    /// The setter is intended for internal use and may reset internal versioning.
 216    /// </remarks>
 217    [JsonInclude]
 218    [MemoryPackInclude]
 219    public SwiftArrayState<T> State
 220    {
 221        get
 222        {
 6223            if (_count == 0)
 1224                return new SwiftArrayState<T>(Array.Empty<T>());
 225
 5226            T[] items = new T[_count];
 5227            CopyTo(items, 0);
 228
 5229            return new SwiftArrayState<T>(items);
 230        }
 231        internal set
 232        {
 7233            ChronicleGuard.ThrowIfNull(value.Items, nameof(value));
 234
 7235            T[] items = value.Items;
 7236            int count = items.Length;
 237
 7238            if (count == 0)
 239            {
 1240                Initialize(DefaultCapacity);
 1241                _count = 0;
 1242                _version = 0;
 1243                return;
 244            }
 245
 6246            int size = (int)(count / _LoadFactorThreshold);
 6247            Initialize(size);
 248
 60249            foreach (T item in items)
 24250                if (item != null)
 23251                    InsertIfNotExists(item);
 252
 6253            _version = 0;
 6254        }
 255    }
 256
 257    #endregion
 258
 259    #region Collection Manipulation
 260
 261    /// <inheritdoc/>
 262    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 263    public bool Add(T item)
 264    {
 216013265        CheckLoadThreshold();
 216013266        return InsertIfNotExists(item);
 267    }
 268
 1269    void ICollection<T>.Add(T item) => Add(item);
 270
 271    /// <summary>
 272    /// Adds the elements of the specified collection to the set, ignoring null values and duplicates.
 273    /// </summary>
 274    /// <remarks>
 275    /// If the source collection is the same instance as the set, the method returns without making any changes.
 276    /// The method preserves single-pass enumeration for sources that do not support multiple iterations.</remarks>
 277    /// <param name="items">The collection of elements to add to the set. Elements that are null or already present in t
 278    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 279    public void AddRange(IEnumerable<T> items)
 280    {
 5281        ChronicleGuard.ThrowIfNull(items, nameof(items));
 282
 5283        if (ReferenceEquals(this, items))
 1284            return;
 285
 4286        if (items is ICollection<T> collection)
 287        {
 2288            AddKnownCountRange(collection, collection.Count);
 2289            return;
 290        }
 291
 2292        if (items is IReadOnlyCollection<T> readOnlyCollection)
 293        {
 1294            AddKnownCountRange(readOnlyCollection, readOnlyCollection.Count);
 1295            return;
 296        }
 297
 1298        AddUnknownCountRange(items);
 1299    }
 300
 301    private void AddKnownCountRange(IEnumerable<T> items, int count)
 302    {
 3303        EnsureCapacityForAddRange(count);
 304
 20305        foreach (T item in items)
 7306            if (item != null)
 7307                InsertIfNotExists(item);
 3308    }
 309
 310    private void AddUnknownCountRange(IEnumerable<T> items)
 311    {
 8312        foreach (T item in items)
 3313            if (item != null)
 3314                Add(item);
 1315    }
 316
 317    /// <summary>
 318    /// Adds the specified element to the set if it's not already present.
 319    /// </summary>
 320    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 321    private bool InsertIfNotExists(T item)
 322    {
 216231323        ChronicleGuard.ThrowIfNullGeneric(item, nameof(item));
 324
 216230325        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 216230326        int entryIndex = hashCode & _entryMask;
 327
 216230328        int firstDeletedIndex = -1;
 216230329        int step = 1;
 330        // Cumulative square offsets repeat after 2 * capacity for power-of-two tables.
 331        // One capacity can revisit buckets before reaching every slot, including after trim.
 216230332        uint probeLimit = (uint)_entries.Length * 2;
 374281333        while ((uint)step <= probeLimit)
 334        {
 374280335            ref Entry entry = ref _entries[entryIndex];
 374280336            if (entry.IsUsed)
 337            {
 158040338                if (entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 17339                    return false; // Item already exists
 340            }
 216240341            else if (entry.HashCode == -1)
 342            {
 35343                if (firstDeletedIndex < 0) firstDeletedIndex = entryIndex;
 344            }
 345            else
 346            {
 347                break;
 348            }
 349
 158051350            entryIndex = (entryIndex + step * step) & _entryMask; // Quadratic probing
 158051351            step++;
 352        }
 353
 216213354        if (firstDeletedIndex >= 0)
 6355            entryIndex = firstDeletedIndex;
 216207356        else if ((uint)step > probeLimit)
 357        {
 1358            Resize(_entries.Length * _adaptiveResizeFactor);
 1359            return InsertIfNotExists(item);
 360        }
 361
 332061362        if ((uint)entryIndex > (uint)_lastIndex) _lastIndex = entryIndex;
 363
 216212364        _entries[entryIndex].HashCode = hashCode;
 216212365        _entries[entryIndex].Value = item;
 216212366        _entries[entryIndex].IsUsed = true;
 216212367        _count++;
 216212368        _version++;
 369
 216212370        if ((uint)step > (uint)_maxStepCount)
 371        {
 2629372            _maxStepCount = step;
 2629373            if (_comparer is not IRandomedEqualityComparer &&
 2629374                _maxStepCount > 100 &&
 2629375                SwiftHashTools.IsWellKnownEqualityComparer(_comparer))
 1376                SwitchToRandomizedComparer();  // Attempt to recompute hash code with potential randomization for better
 377        }
 378
 216212379        return true;
 380    }
 381
 382    /// <summary>
 383    /// Removes the specified element from the set.
 384    /// </summary>
 385    /// <param name="item">The element to remove from the set.</param>
 386    /// <returns>
 387    /// True if the element is successfully found and removed; otherwise, false.
 388    /// </returns>
 389    public bool Remove(T item)
 390    {
 100633391        ChronicleGuard.ThrowIfNullGeneric(item, nameof(item));
 392
 100632393        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 100632394        int entryIndex = hashCode & _entryMask;
 395
 100632396        int step = 0;
 397        // A bucket index is not a probe distance: wrapped chains can take more steps.
 398        // Use the same complete cumulative-square period as insertion.
 151950399        while ((uint)step < (uint)_entries.Length * 2)
 400        {
 151947401            ref Entry entry = ref _entries[entryIndex];
 402            // Stop probing if an unused entry is found (not deleted)
 151947403            if (!entry.IsUsed && entry.HashCode != -1)
 5404                return false;
 151942405            if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 406            {
 407                // Mark entry as deleted
 100624408                entry.IsUsed = false;
 100624409                entry.Value = default!;
 100624410                entry.HashCode = -1;
 100624411                _count--;
 100632412                if ((uint)_count == 0) _lastIndex = 0;
 100624413                _version++;
 100624414                return true;
 415            }
 416
 417            // Entry not found in expected entry, it either doesn't exist or was moved via quadratic probing
 51318418            step++;
 51318419            entryIndex = (entryIndex + step * step) & _entryMask;
 420        }
 3421        return false; // Item not found after full loop
 422    }
 423
 424    /// <summary>
 425    /// Removes all elements from the set.
 426    /// </summary>
 427    public void Clear()
 428    {
 2230429        if ((uint)_count == 0) return;
 430
 40034431        for (uint i = 0; i <= (uint)_lastIndex; i++)
 432        {
 433            // Clear is a full reset, not a delete; future probes must be able to stop
 434            // at these now-empty slots instead of treating them as tombstones.
 17797435            _entries[i].HashCode = 0;
 17797436            _entries[i].Value = default!;
 17797437            _entries[i].IsUsed = false;
 438        }
 439
 2220440        _count = 0;
 2220441        _lastIndex = 0;
 2220442        _maxStepCount = 0;
 2220443        _movingFillRate = 0;
 2220444        _adaptiveResizeFactor = 4;
 445
 2220446        _version++;
 2220447    }
 448
 449    /// <summary>
 450    /// Removes all elements, optionally releasing references throughout retained backing storage.
 451    /// </summary>
 452    /// <param name="clearRetainedReferences">If true, also releases references outside the live range; otherwise uses o
 453    /// <remarks>Capacity is preserved. Full reference cleanup can take time proportional to retained capacity.</remarks
 454    public void Clear(bool clearRetainedReferences)
 455    {
 136456        if (clearRetainedReferences && RuntimeHelpers.IsReferenceOrContainsReferences<Entry>())
 457        {
 130458            int start = _count == 0 ? 0 : _lastIndex + 1;
 130459            Array.Clear(_entries, start, _entries.Length - start);
 460        }
 136461        Clear();
 136462    }
 463
 464    #endregion
 465
 466    #region Capacity Management
 467
 468    /// <summary>
 469    /// Ensures that the hash set is resized when the current load factor exceeds the predefined threshold.
 470    /// </summary>
 471    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 472    private void CheckLoadThreshold()
 473    {
 216013474        if ((uint)_count >= _nextResizeCount)
 35475            Resize(_entries.Length * _adaptiveResizeFactor);
 216013476    }
 477
 478    /// <summary>
 479    /// Ensures there is enough room to add a batch of items without repeatedly checking the load threshold.
 480    /// </summary>
 481    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 482    private void EnsureCapacityForAddRange(int incomingCount)
 483    {
 3484        if (incomingCount <= 0)
 1485            return;
 486
 2487        long requiredCount = (long)_count + incomingCount;
 2488        ChronicleGuard.ThrowIfTrue(requiredCount > int.MaxValue, message: "The collection is too large.");
 489
 2490        double minimumCapacity = Math.Ceiling(requiredCount / (double)_LoadFactorThreshold);
 2491        EnsureCapacity((int)Math.Min(minimumCapacity, int.MaxValue));
 2492    }
 493
 494    /// <summary>
 495    /// Ensures that the set can hold up to the specified number of elements without resizing.
 496    /// </summary>
 497    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 498    public void EnsureCapacity(int capacity)
 499    {
 5500        capacity = SwiftHashTools.NextPowerOfTwo(capacity);  // Capacity must be a power of 2 for proper masking
 5501        if (capacity > _entries.Length)
 3502            Resize(capacity);
 5503    }
 504
 505    /// <summary>
 506    /// Resizes the hash set to the specified capacity, redistributing all entries to maintain efficiency.
 507    /// </summary>
 508    /// <param name="newSize"></param>
 509    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 510    private void Resize(int newSize)
 511    {
 39512        Entry[] newEntries = new Entry[newSize];
 39513        int newMask = newSize - 1;
 514
 39515        int lastIndex = 0;
 184578516        for (uint i = 0; i <= (uint)_lastIndex; i++)
 517        {
 92250518            if (_entries[i].IsUsed)
 519            {
 85693520                ref Entry oldEntry = ref _entries[i];
 85693521                int newIndex = oldEntry.HashCode & newMask;
 522                // If current entry not available, perform Quadratic probing to find the next available entry
 85693523                int step = 1;
 90768524                while (newEntries[newIndex].IsUsed)
 525                {
 5075526                    newIndex = (newIndex + step * step) & newMask;
 5075527                    step++;
 528                }
 85693529                newEntries[newIndex] = oldEntry;
 134343530                if (newIndex > lastIndex) lastIndex = newIndex;
 531            }
 532        }
 533
 39534        _lastIndex = lastIndex;
 535
 39536        CalculateAdaptiveResizeFactors(newSize);
 537
 39538        _entries = newEntries;
 39539        _entryMask = newMask;
 540
 39541        _version++;
 39542    }
 543
 544    /// <summary>
 545    /// Sets the capacity of a <see cref="SwiftHashSet{T}"/> to the actual
 546    /// number of elements it contains, rounded up to a nearby next power of 2 value.
 547    /// </summary>
 548    public void TrimExcess()
 549    {
 6550        int newSize = _count <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(_count);
 7551        if (newSize >= _entries.Length) return;
 552
 5553        Entry[] newEntries = new Entry[newSize];
 5554        int newMask = newSize - 1;
 555
 5556        int lastIndex = 0;
 478557        for (int i = 0; i <= (uint)_lastIndex; i++)
 558        {
 234559            if (_entries[i].IsUsed)
 560            {
 71561                ref Entry oldEntry = ref _entries[i];
 71562                int newIndex = oldEntry.HashCode & newMask;
 563                // If current entry not available, perform quadratic probing to find the next available entry
 71564                int step = 1;
 1015565                while (newEntries[newIndex].IsUsed)
 566                {
 944567                    newIndex = (newIndex + step * step) & newMask;
 944568                    step++;
 569                }
 71570                newEntries[newIndex] = oldEntry;
 97571                if (newIndex > lastIndex) lastIndex = newIndex;
 572            }
 573        }
 574
 5575        _lastIndex = lastIndex;
 576
 5577        CalculateAdaptiveResizeFactors(newSize);
 578
 5579        _entryMask = newMask;
 5580        _entries = newEntries;
 581
 5582        _version++;
 5583    }
 584
 585    /// <summary>
 586    ///  Updates adaptive resize parameters based on the current fill rate to balance memory usage and performance.
 587    /// </summary>
 588    /// <param name="newSize"></param>
 589    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 590    private void CalculateAdaptiveResizeFactors(int newSize)
 591    {
 592        // Calculate current fill rate and update moving average
 44593        double currentFillRate = (double)_count / newSize;
 44594        _movingFillRate = _movingFillRate == 0 ? currentFillRate : (_movingFillRate * 0.7 + currentFillRate * 0.3);
 595
 44596        if (_movingFillRate > 0.3f)
 6597            _adaptiveResizeFactor = 2; // Growth stabilizing
 38598        else if (_movingFillRate < 0.28f)
 37599            _adaptiveResizeFactor = 4; // Rapid growth
 600
 601        // Reset the resize threshold based on the new size
 44602        _nextResizeCount = (uint)(newSize * _LoadFactorThreshold);
 44603    }
 604
 605    #endregion
 606
 607    #region Utility Methods
 608
 609    /// <summary>
 610    /// Initializes the hash set with a given capacity, ensuring it starts with an optimal internal structure.
 611    /// </summary>
 612    /// <param name="capacity"></param>
 613    /// <param name="comparer"></param>
 614    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 615    private void Initialize(int capacity, IEqualityComparer<T>? comparer = null)
 616    {
 175617        _comparer = SwiftHashTools.GetDefaultEqualityComparer(comparer);
 618
 175619        int size = capacity < DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity);
 175620        _entries = new Entry[size];
 175621        _entryMask = size - 1;
 622
 175623        _nextResizeCount = (uint)(size * _LoadFactorThreshold);
 175624        _adaptiveResizeFactor = 4; // start agressive
 175625        _movingFillRate = 0.0;
 175626    }
 627
 628    /// <summary>
 629    /// Determines whether the set contains the specified element.
 630    /// </summary>
 631    /// <param name="item">The element to locate in the set.</param>
 632    /// <returns>
 633    /// True if the set contains the specified element; otherwise, false.
 634    /// </returns>
 635    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 2251636    public bool Contains(T item) => FindEntry(item) >= 0;
 637
 638    /// <summary>
 639    /// Determines whether the <see cref="SwiftHashSet{T}"/> contains an element that matches the conditions defined by 
 640    /// </summary>
 641    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 642    /// <returns><c>true</c> if the <see cref="SwiftHashSet{T}"/> contains one or more elements that match the specified
 643    public bool Exists(Predicate<T> match)
 644    {
 3645        ChronicleGuard.ThrowIfNull(match, nameof(match));
 646
 16647        for (int i = 0; i <= _lastIndex; i++)
 648        {
 7649            if (_entries[i].IsUsed && match(_entries[i].Value))
 1650                return true;
 651        }
 652
 1653        return false;
 654    }
 655
 656    /// <summary>
 657    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 658    /// </summary>
 659    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 660    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 661    public T Find(Predicate<T> match)
 662    {
 2663        ChronicleGuard.ThrowIfNull(match, nameof(match));
 664
 16665        for (int i = 0; i <= _lastIndex; i++)
 666        {
 7667            if (_entries[i].IsUsed && match(_entries[i].Value))
 1668                return _entries[i].Value;
 669        }
 670
 1671        return default!;
 672    }
 673
 674    /// <summary>
 675    /// Searches the set for a given value and returns the equal value it finds, if any.
 676    /// </summary>
 677    public bool TryGetValue(T expected, out T actual)
 678    {
 772679        int index = FindEntry(expected);
 772680        if (index >= 0)
 681        {
 386682            actual = _entries[index].Value;
 386683            return true;
 684        }
 386685        actual = default!;
 386686        return false;
 687    }
 688
 689    /// <summary>
 690    /// Copies the elements of the set to an array, starting at the specified array index.
 691    /// </summary>
 692    public void CopyTo(T[] array, int arrayIndex)
 693    {
 11694        ChronicleGuard.ThrowIfNull(array, nameof(array));
 10695        ChronicleGuard.ThrowIfArrayIndexInvalid(arrayIndex, array.Length);
 8696        ChronicleGuard.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The array is not large enough
 697
 112698        for (uint i = 0; i <= (uint)_lastIndex; i++)
 699        {
 49700            if (_entries[i].IsUsed)
 28701                array[arrayIndex++] = _entries[i].Value;
 702        }
 7703    }
 704
 705    /// <summary>
 706    /// Switches the hash set's comparer and rehashes all entries
 707    /// using the new comparer to redistribute them across <see cref="_entries"/>.
 708    /// </summary>
 709    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 710    public void SetComparer(IEqualityComparer<T>? comparer = null)
 711    {
 5712        ChronicleGuard.ThrowIfNull(comparer, nameof(comparer));
 4713        if (ReferenceEquals(comparer, _comparer))
 1714            return;
 715
 3716        _comparer = comparer;
 3717        RehashEntries();
 3718    }
 719
 720    /// <summary>
 721    /// Replaces the hash set's comparer with a randomized comparer to mitigate high collision rates.
 722    /// </summary>
 723    private void SwitchToRandomizedComparer()
 724    {
 1725        _comparer = (IEqualityComparer<T>)SwiftHashTools.GetSwiftEqualityComparer(_comparer);
 726
 1727        RehashEntries();
 1728        _maxStepCount = 0;
 729
 1730        _version++;
 1731    }
 732
 733    /// <summary>
 734    /// Reconstructs the internal entry structure to align with updated hash codes, ensuring efficient access and storag
 735    /// </summary>
 736    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 737    private void RehashEntries()
 738    {
 4739        Entry[] newEntries = new Entry[_entries.Length];
 4740        int newMask = newEntries.Length - 1;
 741
 4742        int lastIndex = 0;
 584743        for (uint i = 0; i <= (uint)_lastIndex; i++)
 744        {
 288745            if (_entries[i].IsUsed)
 746            {
 101747                ref Entry oldEntry = ref _entries[i];
 101748                oldEntry.HashCode = _comparer.GetHashCode(oldEntry.Value) & 0x7FFFFFFF;
 101749                int newIndex = oldEntry.HashCode & newMask;
 101750                int step = 1;
 113751                while (newEntries[newIndex].IsUsed)
 752                {
 12753                    newIndex = (newIndex + step * step) & newMask; // Quadratic probing
 12754                    step++;
 755                }
 101756                newEntries[newIndex] = _entries[i];
 119757                if (newIndex > lastIndex) lastIndex = newIndex;
 758            }
 759        }
 760
 4761        _lastIndex = lastIndex;
 762
 4763        _entryMask = newMask;
 4764        _entries = newEntries;
 765
 4766        _version++;
 4767    }
 768
 769    /// <summary>
 770    /// Searches for an entry in the hash set by following its probing sequence, returning its index if found.
 771    /// </summary>
 772    /// <param name="item"></param>
 773    /// <returns></returns>
 774    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 775    private int FindEntry(T item)
 776    {
 3415777        if (_ItemCanBeNull && item is null) return -1;
 778
 3407779        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 3407780        int entryIndex = hashCode & _entryMask;
 781
 3407782        int step = 0;
 783        // A bucket index is not a probe distance: wrapped chains can take more steps.
 784        // Use the same complete cumulative-square period as insertion.
 17713785        while ((uint)step < (uint)_entries.Length * 2)
 786        {
 17710787            ref Entry entry = ref _entries[entryIndex];
 788            // Stop probing if an unused entry is found (not deleted)
 17710789            if (!entry.IsUsed && entry.HashCode != -1)
 1300790                return -1;
 16410791            if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 2104792                return entryIndex; // Match found
 793
 794            // Perform quadratic probing to see if maybe the entry was shifted.
 14306795            step++;
 14306796            entryIndex = (entryIndex + step * step) & _entryMask;
 797
 798        }
 3799        return -1; // Item not found, full loop completed
 800    }
 801
 802    #endregion
 803
 804    #region Enumerators
 805
 806    /// <summary>
 807    /// Returns an enumerator that iterates through the set.
 808    /// </summary>
 84809    public SwiftHashSetEnumerator GetEnumerator() => new(this);
 45810    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 19811    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 812
 813
 814
 815    #endregion
 816
 817    #region ISet<T> Implementations
 818
 819    /// <inheritdoc/>
 820    public void ExceptWith(IEnumerable<T> other)
 821    {
 2822        ChronicleGuard.ThrowIfNull(other, nameof(other));
 823
 2824        if (ReferenceEquals(this, other))
 825        {
 1826            Clear();
 1827            return;
 828        }
 829
 1830        var otherSet = new SwiftHashSet<T>(other, _comparer);
 831
 8832        foreach (var item in otherSet)
 3833            Remove(item);
 1834    }
 835
 836    /// <inheritdoc/>
 837    public void IntersectWith(IEnumerable<T> other)
 838    {
 2839        ChronicleGuard.ThrowIfNull(other, nameof(other));
 840
 2841        if (ReferenceEquals(this, other))
 1842            return;
 843
 1844        var otherSet = new SwiftHashSet<T>(other, _comparer);
 845
 12846        for (int i = 0; i <= _lastIndex; i++)
 847        {
 5848            if (_entries[i].IsUsed)
 849            {
 4850                var value = _entries[i].Value;
 4851                if (!otherSet.Contains(value))
 2852                    Remove(value);
 853            }
 854        }
 1855    }
 856
 857    /// <inheritdoc/>
 858    public bool IsProperSubsetOf(IEnumerable<T> other)
 859    {
 3860        ChronicleGuard.ThrowIfNull(other, nameof(other));
 861
 3862        var otherSet = new SwiftHashSet<T>(other, _comparer);
 863
 3864        if (Count >= otherSet.Count)
 1865            return false;
 866
 14867        for (int i = 0; i <= _lastIndex; i++)
 6868            if (_entries[i].IsUsed && !otherSet.Contains(_entries[i].Value))
 1869                return false;
 870
 1871        return true;
 872    }
 873
 874    /// <inheritdoc/>
 875    public bool IsProperSupersetOf(IEnumerable<T> other)
 876    {
 3877        ChronicleGuard.ThrowIfNull(other, nameof(other));
 878
 3879        var otherSet = new SwiftHashSet<T>(other, _comparer);
 880
 3881        if (Count <= otherSet.Count)
 1882            return false;
 883
 9884        foreach (var item in otherSet)
 3885            if (!Contains(item))
 1886                return false;
 887
 1888        return true;
 1889    }
 890
 891    /// <inheritdoc/>
 892    public bool IsSubsetOf(IEnumerable<T> other)
 893    {
 3894        ChronicleGuard.ThrowIfNull(other, nameof(other));
 895
 3896        var otherSet = new SwiftHashSet<T>(other, _comparer);
 897
 3898        if (otherSet.Count < Count)
 1899            return false;
 900
 14901        for (int i = 0; i <= _lastIndex; i++)
 6902            if (_entries[i].IsUsed && !otherSet.Contains(_entries[i].Value))
 1903                return false;
 904
 1905        return true;
 906    }
 907
 908    /// <inheritdoc/>
 909    public bool IsSupersetOf(IEnumerable<T> other)
 910    {
 2911        ChronicleGuard.ThrowIfNull(other, nameof(other));
 912
 13913        foreach (var item in other)
 914        {
 5915            if (!Contains(item))
 1916                return false;
 917        }
 918
 1919        return true;
 1920    }
 921
 922    /// <inheritdoc/>
 923    public bool Overlaps(IEnumerable<T> other)
 924    {
 2925        ChronicleGuard.ThrowIfNull(other, nameof(other));
 926
 9927        foreach (var item in other)
 3928            if (Contains(item))
 1929                return true;
 930
 1931        return false;
 1932    }
 933
 934    /// <inheritdoc/>
 935    public bool SetEquals(IEnumerable<T> other)
 936    {
 9937        ChronicleGuard.ThrowIfNull(other, nameof(other));
 938
 9939        var otherSet = new SwiftHashSet<T>(other, _comparer);
 940
 9941        if (otherSet.Count != Count)
 1942            return false;
 943
 68944        foreach (var item in otherSet)
 27945            if (!Contains(item))
 2946                return false;
 947
 6948        return true;
 2949    }
 950
 951    /// <inheritdoc/>
 952    public void SymmetricExceptWith(IEnumerable<T> other)
 953    {
 2954        ChronicleGuard.ThrowIfNull(other, nameof(other));
 955
 2956        if (ReferenceEquals(this, other))
 957        {
 1958            Clear();
 1959            return;
 960        }
 961
 1962        var otherSet = new SwiftHashSet<T>(other, _comparer);
 963
 6964        foreach (var item in otherSet)
 965        {
 2966            if (!Remove(item))
 1967                Add(item);
 968        }
 1969    }
 970
 971    /// <inheritdoc/>
 972    public void UnionWith(IEnumerable<T> other)
 973    {
 1974        ChronicleGuard.ThrowIfNull(other, nameof(other));
 975
 6976        foreach (var item in other)
 2977            Add(item);
 1978    }
 979
 980    #endregion
 981}

/home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftHashSet.SwiftHashSetEnumerator.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftHashSet.SwiftHashSetEnumerator.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 System;
 9using System.Collections;
 10using System.Collections.Generic;
 11using Chronicler.Diagnostics;
 12
 13namespace SwiftCollections;
 14
 15public sealed partial class SwiftHashSet<T>
 16    where T : notnull
 17{
 18    /// <summary>
 19    /// Provides an enumerator for iterating through the elements of the hash set, ensuring consistency during enumerati
 20    /// </summary>
 21    public struct SwiftHashSetEnumerator : IEnumerator<T>, IEnumerator, IDisposable
 22    {
 23        private readonly SwiftHashSet<T> _set;
 24        private readonly Entry[] _entries;
 25        private readonly uint _version;
 26        private int _index;
 27        private T _current;
 28
 29        internal SwiftHashSetEnumerator(SwiftHashSet<T> set)
 30        {
 8431            _set = set;
 8432            _version = set._version;
 8433            _entries = set._entries; // Cache the entry array
 8434            _index = -1;
 8435            _current = default!;
 8436        }
 37
 38        /// <inheritdoc/>
 9639        public readonly T Current => _current;
 40
 41        readonly object IEnumerator.Current
 42        {
 43            get
 44            {
 3145                ChronicleGuard.ThrowIfTrue((uint)_index > (uint)_set._lastIndex, message: "Enumeration has either not st
 1346                return _current;
 47            }
 48        }
 49
 50        /// <inheritdoc/>
 51        public bool MoveNext()
 52        {
 19553            ChronicleGuard.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration."
 54
 19155            uint last = (uint)_set._lastIndex;
 41856            while (++_index <= last)
 57            {
 34258                if (_entries[_index].IsUsed)
 59                {
 11560                    _current = _entries[_index].Value;
 11561                    return true;
 62                }
 63            }
 64
 7665            _current = default!;
 7666            return false;
 67        }
 68
 69        /// <inheritdoc/>
 70        public void Reset()
 71        {
 1072            ChronicleGuard.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration."
 73
 774            _index = -1;
 775            _current = default!;
 776        }
 77
 78        /// <inheritdoc/>
 6679        public void Dispose() => _index = -1;
 80    }
 81}
Generated by: ReportGenerator 5.5.12.0
11/05/2026 - 04:17:34
GitHub | reportgenerator.io

Methods/Properties

.cctor()
.ctor()
.ctor(System.Collections.Generic.IEqualityComparer`1<T>)
.ctor(System.Int32,System.Collections.Generic.IEqualityComparer`1<T>)
.ctor(System.Collections.Generic.IEnumerable`1<T>,System.Collections.Generic.IEqualityComparer`1<T>)
.ctor(SwiftCollections.SwiftArrayState`1<T>)
get_Count()
get_Comparer()
System.Collections.Generic.ICollection<T>.get_IsReadOnly()
get_Item(T)
get_State()
set_State(SwiftCollections.SwiftArrayState`1<T>)
Add(T)
System.Collections.Generic.ICollection<T>.Add(T)
AddRange(System.Collections.Generic.IEnumerable`1<T>)
AddKnownCountRange(System.Collections.Generic.IEnumerable`1<T>,System.Int32)
AddUnknownCountRange(System.Collections.Generic.IEnumerable`1<T>)
InsertIfNotExists(T)
Remove(T)
Clear()
Clear(System.Boolean)
CheckLoadThreshold()
EnsureCapacityForAddRange(System.Int32)
EnsureCapacity(System.Int32)
Resize(System.Int32)
TrimExcess()
CalculateAdaptiveResizeFactors(System.Int32)
Initialize(System.Int32,System.Collections.Generic.IEqualityComparer`1<T>)
Contains(T)
Exists(System.Predicate`1<T>)
Find(System.Predicate`1<T>)
TryGetValue(T,T&)
CopyTo(T[],System.Int32)
SetComparer(System.Collections.Generic.IEqualityComparer`1<T>)
SwitchToRandomizedComparer()
RehashEntries()
FindEntry(T)
GetEnumerator()
System.Collections.Generic.IEnumerable<T>.GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
ExceptWith(System.Collections.Generic.IEnumerable`1<T>)
IntersectWith(System.Collections.Generic.IEnumerable`1<T>)
IsProperSubsetOf(System.Collections.Generic.IEnumerable`1<T>)
IsProperSupersetOf(System.Collections.Generic.IEnumerable`1<T>)
IsSubsetOf(System.Collections.Generic.IEnumerable`1<T>)
IsSupersetOf(System.Collections.Generic.IEnumerable`1<T>)
Overlaps(System.Collections.Generic.IEnumerable`1<T>)
SetEquals(System.Collections.Generic.IEnumerable`1<T>)
SymmetricExceptWith(System.Collections.Generic.IEnumerable`1<T>)
UnionWith(System.Collections.Generic.IEnumerable`1<T>)
.ctor(SwiftCollections.SwiftHashSet`1<T>)
get_Current()
System.Collections.IEnumerator.get_Current()
MoveNext()
Reset()
Dispose()