< Summary

Information
Class: System.Buffers.ProbabilisticMapState
Assembly: System.Private.CoreLib
File(s): D:\runner\runtime\src\libraries\System.Private.CoreLib\src\System\SearchValues\ProbabilisticMapState.cs
Line coverage
71%
Covered lines: 76
Uncovered lines: 30
Coverable lines: 106
Total lines: 308
Line coverage: 71.6%
Branch coverage
71%
Covered branches: 30
Total branches: 42
Branch coverage: 71.4%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity NPath complexity Sequence coverage
.ctor(...)100%22100%
.ctor(...)100%110%
GetValues()100%110%
FastContains(...)100%11100%
FastContains(...)100%11100%
SlowProbabilisticContains(...)100%110%
SlowContains(...)100%110%
ConfirmProbabilisticMatch(...)50%2266.66%
FindModulus(...)80%101093.75%
TestModulus(System.ReadOnlySpan`1<System.Char>,System.Int32)100%44100%
TryRemoveDuplicates(System.ReadOnlySpan`1<System.Char>,System.Char[]&)75%4471.42%
GetFastModMultiplier(...)100%11100%
FastMod(...)100%11100%
IndexOfAnySimpleLoop(...)60%101070.58%
LastIndexOfAnySimpleLoop(...)60%101072.72%

File(s)

D:\runner\runtime\src\libraries\System.Private.CoreLib\src\System\SearchValues\ProbabilisticMapState.cs

#LineLine coverage
 1// Licensed to the .NET Foundation under one or more agreements.
 2// The .NET Foundation licenses this file to you under the MIT license.
 3
 4using System.Collections;
 5using System.Collections.Generic;
 6using System.Diagnostics;
 7using System.Diagnostics.CodeAnalysis;
 8using System.Runtime.CompilerServices;
 9using System.Runtime.InteropServices;
 10
 11namespace System.Buffers
 12{
 13    /// <summary>
 14    /// Stores the state necessary to call vectorized members on <see cref="ProbabilisticMap"/>,
 15    /// as well as (optionally) a precomputed perfect hash table for faster single-character lookups/match confirmations
 16    /// When the hash table isn't available, the structure stores a pointer to the span of values in the set instead.
 17    /// </summary>
 18    internal unsafe struct ProbabilisticMapState
 19    {
 20        private const int MaxModulus = char.MaxValue + 1;
 21
 22        public ProbabilisticMap Map;
 23
 24        // Hash entries store each value from the set at the index determined by the remainder modulo the table size.
 25        // As every value has a unique remainder, we can check if a value is contained in the set by checking
 26        // _hashEntries[value % _hashEntries.Length] == value (see FastContains below).
 27        // The multiplier is used for faster modulo operations when determining the hash table index.
 28        // Exactly one of _hashEntries and _slowContainsValuesPtr may be initialized at the same time.
 29        private readonly uint _multiplier;
 30        private readonly char[]? _hashEntries;
 31        private readonly ReadOnlySpan<char>* _slowContainsValuesPtr;
 32
 33        public ProbabilisticMapState(ReadOnlySpan<char> values, int maxInclusive)
 34        {
 195135            Debug.Assert(!values.IsEmpty);
 36
 195137            Map = new ProbabilisticMap(values);
 38
 195139            uint modulus = FindModulus(values, maxInclusive);
 195140            _multiplier = GetFastModMultiplier(modulus);
 195141            _hashEntries = new char[modulus];
 42
 43            // Some hash entries will remain unused.
 44            // We can't leave them uninitialized as we would otherwise erroneously match (char)0.
 45            // The exact value doesn't matter, as long as it's in the set of our values.
 195146            _hashEntries.AsSpan().Fill(values[0]);
 47
 23626248            foreach (char c in values)
 49            {
 11618050                _hashEntries[FastMod(c, modulus, _multiplier)] = c;
 51            }
 195152        }
 53
 54        // valuesPtr must remain valid for as long as this ProbabilisticMapState is used.
 55        public ProbabilisticMapState(ReadOnlySpan<char>* valuesPtr)
 56        {
 057            Debug.Assert((IntPtr)valuesPtr != IntPtr.Zero);
 58
 059            Map = new ProbabilisticMap(*valuesPtr);
 060            _slowContainsValuesPtr = valuesPtr;
 061        }
 62
 63        public char[] GetValues()
 64        {
 065            Debug.Assert(_hashEntries is not null);
 66
 067            var unique = new HashSet<char>(_hashEntries);
 068            char[] values = new char[unique.Count];
 069            unique.CopyTo(values);
 070            return values;
 71        }
 72
 73        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 74        public bool FastContains(char value)
 75        {
 56467676            Debug.Assert(_hashEntries is not null);
 56467677            Debug.Assert((IntPtr)_slowContainsValuesPtr == IntPtr.Zero);
 78
 56467679            return FastContains(_hashEntries, _multiplier, value);
 80        }
 81
 82        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 83        private static bool FastContains(char[] hashEntries, uint multiplier, char value)
 84        {
 69678385            ulong offset = FastMod(value, (uint)hashEntries.Length, multiplier);
 69678386            Debug.Assert(offset < (ulong)hashEntries.Length);
 87
 69678388            return Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(hashEntries), (nuint)offset) == value;
 89        }
 90
 91        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 92        private bool SlowProbabilisticContains(char value)
 93        {
 094            Debug.Assert(_hashEntries is null);
 095            Debug.Assert((IntPtr)_slowContainsValuesPtr != IntPtr.Zero);
 96
 097            return ProbabilisticMap.Contains(
 098                ref Unsafe.As<ProbabilisticMap, uint>(ref Map),
 099                *_slowContainsValuesPtr,
 0100                value);
 101        }
 102
 103        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 104        private bool SlowContains(char value)
 105        {
 0106            Debug.Assert(_hashEntries is null);
 0107            Debug.Assert((IntPtr)_slowContainsValuesPtr != IntPtr.Zero);
 108
 0109            return ProbabilisticMap.Contains(*_slowContainsValuesPtr, value);
 110        }
 111
 112        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 113        public bool ConfirmProbabilisticMatch<TUseFastContains>(char value)
 114            where TUseFastContains : struct, SearchValues.IRuntimeConst
 115        {
 259427116            if (TUseFastContains.Value)
 117            {
 259427118                return FastContains(value);
 119            }
 120            else
 121            {
 122                // We use SlowContains instead of SlowProbabilisticContains here as we've already checked
 123                // the value against the probabilistic filter and are now confirming the potential match.
 0124                return SlowContains(value);
 125            }
 126        }
 127
 128        /// <summary>Finds a modulus where remainders for all values in the set are unique.</summary>
 129        private static uint FindModulus(ReadOnlySpan<char> values, int maxInclusive)
 130        {
 1951131            Debug.Assert(maxInclusive <= char.MaxValue);
 132
 1951133            int modulus = HashHelpers.GetPrime(values.Length);
 1951134            bool removedDuplicates = false;
 135
 1951136            if (modulus >= maxInclusive)
 137            {
 31138                return (uint)(maxInclusive + 1);
 139            }
 140
 67517141            while (true)
 142            {
 71090143                if (modulus >= maxInclusive)
 144                {
 145                    // Try to remove duplicates and try again.
 1653146                    if (!removedDuplicates && TryRemoveDuplicates(values, out char[]? deduplicated))
 147                    {
 1653148                        removedDuplicates = true;
 1653149                        values = deduplicated;
 1653150                        modulus = HashHelpers.GetPrime(values.Length);
 1653151                        continue;
 152                    }
 153
 0154                    return (uint)(maxInclusive + 1);
 155                }
 156
 69437157                if (TestModulus(values, modulus))
 158                {
 1920159                    return (uint)modulus;
 160                }
 161
 67517162                modulus = HashHelpers.GetPrime(modulus + 1);
 163            }
 164
 165            static bool TestModulus(ReadOnlySpan<char> values, int modulus)
 166            {
 69437167                Debug.Assert(modulus < MaxModulus);
 168
 69437169                bool[] seen = ArrayPool<bool>.Shared.Rent(modulus);
 69437170                seen.AsSpan(0, modulus).Clear();
 171
 69437172                uint multiplier = GetFastModMultiplier((uint)modulus);
 173
 856701174                foreach (char c in values)
 175                {
 392672176                    ulong index = FastMod(c, (uint)modulus, multiplier);
 177
 392672178                    if (seen[index])
 179                    {
 67517180                        ArrayPool<bool>.Shared.Return(seen);
 67517181                        return false;
 182                    }
 183
 325155184                    seen[index] = true;
 185                }
 186
 187                // Saw no duplicates.
 1920188                ArrayPool<bool>.Shared.Return(seen);
 1920189                return true;
 190            }
 191
 192            static bool TryRemoveDuplicates(ReadOnlySpan<char> values, [NotNullWhen(true)] out char[]? deduplicated)
 193            {
 1653194                HashSet<char> unique = [.. values];
 195
 1653196                if (unique.Count == values.Length)
 197                {
 0198                    deduplicated = null;
 0199                    return false;
 200                }
 201
 1653202                deduplicated = new char[unique.Count];
 1653203                unique.CopyTo(deduplicated);
 1653204                return true;
 205            }
 206        }
 207
 208        // This is a variant of HashHelpers.GetFastModMultiplier, specialized for smaller divisors (<= 65536).
 209        private static uint GetFastModMultiplier(uint divisor)
 210        {
 1277023211            Debug.Assert(divisor > 0);
 1277023212            Debug.Assert(divisor <= MaxModulus);
 213
 1277023214            return uint.MaxValue / divisor + 1;
 215        }
 216
 217        // This is a faster variant of HashHelpers.FastMod, specialized for smaller divisors (<= 65536).
 218        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 219        private static ulong FastMod(char value, uint divisor, uint multiplier)
 220        {
 1205635221            Debug.Assert(multiplier == GetFastModMultiplier(divisor));
 222
 1205635223            ulong result = ((ulong)(multiplier * value) * divisor) >> 32;
 224
 1205635225            Debug.Assert(result == (value % divisor));
 1205635226            return result;
 227        }
 228
 229        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 230        public static int IndexOfAnySimpleLoop<TUseFastContains, TNegator>(ref char searchSpace, int searchSpaceLength, 
 231            where TUseFastContains : struct, SearchValues.IRuntimeConst
 232            where TNegator : struct, IndexOfAnyAsciiSearcher.INegator
 233        {
 11374234            ref char searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength);
 11374235            ref char cur = ref searchSpace;
 236
 11374237            if (TUseFastContains.Value)
 238            {
 11374239                Debug.Assert(state._hashEntries is not null);
 240
 11374241                char[] hashEntries = state._hashEntries;
 11374242                uint multiplier = state._multiplier;
 243
 130038244                while (!Unsafe.AreSame(ref cur, ref searchSpaceEnd))
 245                {
 123209246                    char c = cur;
 123209247                    if (TNegator.NegateIfNeeded(FastContains(hashEntries, multiplier, c)))
 248                    {
 4545249                        return (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref cur) / sizeof(char));
 250                    }
 251
 118664252                    cur = ref Unsafe.Add(ref cur, 1);
 253                }
 254            }
 255            else
 256            {
 0257                while (!Unsafe.AreSame(ref cur, ref searchSpaceEnd))
 258                {
 0259                    char c = cur;
 0260                    if (TNegator.NegateIfNeeded(state.SlowProbabilisticContains(c)))
 261                    {
 0262                        return (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref cur) / sizeof(char));
 263                    }
 264
 0265                    cur = ref Unsafe.Add(ref cur, 1);
 266                }
 267            }
 268
 6829269            return -1;
 270        }
 271
 272        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 273        public static int LastIndexOfAnySimpleLoop<TUseFastContains, TNegator>(ref char searchSpace, int searchSpaceLeng
 274            where TUseFastContains : struct, SearchValues.IRuntimeConst
 275            where TNegator : struct, IndexOfAnyAsciiSearcher.INegator
 276        {
 5702277            if (TUseFastContains.Value)
 278            {
 5702279                Debug.Assert(state._hashEntries is not null);
 280
 5702281                char[] hashEntries = state._hashEntries;
 5702282                uint multiplier = state._multiplier;
 283
 12156284                while (--searchSpaceLength >= 0)
 285                {
 8898286                    char c = Unsafe.Add(ref searchSpace, searchSpaceLength);
 8898287                    if (TNegator.NegateIfNeeded(FastContains(hashEntries, multiplier, c)))
 288                    {
 289                        break;
 290                    }
 291                }
 292            }
 293            else
 294            {
 0295                while (--searchSpaceLength >= 0)
 296                {
 0297                    char c = Unsafe.Add(ref searchSpace, searchSpaceLength);
 0298                    if (TNegator.NegateIfNeeded(state.SlowProbabilisticContains(c)))
 299                    {
 300                        break;
 301                    }
 302                }
 303            }
 304
 5702305            return searchSpaceLength;
 306        }
 307    }
 308}
Generated by: ReportGenerator 5.5.12.0
10/31/2026 - 12:26:28 PM
GitHub | reportgenerator.io

Methods/Properties

.ctor(System.ReadOnlySpan`1<System.Char>,System.Int32)
.ctor(System.ReadOnlySpan`1<System.Char>*)
GetValues()
FastContains(System.Char)
FastContains(System.Char[],System.UInt32,System.Char)
SlowProbabilisticContains(System.Char)
SlowContains(System.Char)
ConfirmProbabilisticMatch(System.Char)
FindModulus(System.ReadOnlySpan`1<System.Char>,System.Int32)
TestModulus(System.ReadOnlySpan`1<System.Char>,System.Int32)
TryRemoveDuplicates(System.ReadOnlySpan`1<System.Char>,System.Char[]&)
GetFastModMultiplier(System.UInt32)
FastMod(System.Char,System.UInt32,System.UInt32)
IndexOfAnySimpleLoop(System.Char&,System.Int32,System.Buffers.ProbabilisticMapState&)
LastIndexOfAnySimpleLoop(System.Char&,System.Int32,System.Buffers.ProbabilisticMapState&)