< Summary

Information
Class: System.Buffers.ProbabilisticMapState
Assembly: System.Private.CoreLib
File(s): https://raw.githubusercontent.com/dotnet/runtime/811a7eabb75c42db53440e8ba3f60c07511cfd1f/src/libraries/System.Private.CoreLib/src/System/SearchValues/ProbabilisticMapState.cs
Line coverage
71%
Covered lines: 76
Uncovered lines: 30
Coverable lines: 106
Total lines: 309
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)

https://raw.githubusercontent.com/dotnet/runtime/811a7eabb75c42db53440e8ba3f60c07511cfd1f/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        {
 183135            Debug.Assert(!values.IsEmpty);
 36
 183137            Map = new ProbabilisticMap(values);
 38
 183139            uint modulus = FindModulus(values, maxInclusive);
 183140            _multiplier = GetFastModMultiplier(modulus);
 183141            _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.
 183146            _hashEntries.AsSpan().Fill(values[0]);
 47
 18743248            foreach (char c in values)
 49            {
 9188550                _hashEntries[FastMod(c, modulus, _multiplier)] = c;
 51            }
 183152        }
 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        {
 37926076            Debug.Assert(_hashEntries is not null);
 37926077            Debug.Assert((IntPtr)_slowContainsValuesPtr == IntPtr.Zero);
 78
 37926079            return FastContains(_hashEntries, _multiplier, value);
 80        }
 81
 82        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 83        private static bool FastContains(char[] hashEntries, uint multiplier, char value)
 84        {
 51442485            ulong offset = FastMod(value, (uint)hashEntries.Length, multiplier);
 51442486            Debug.Assert(offset < (ulong)hashEntries.Length);
 87
 51442488            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        {
 104550116            if (TUseFastContains.Value)
 117            {
 104550118                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        {
 1831131            Debug.Assert(maxInclusive <= char.MaxValue);
 132
 1831133            int modulus = HashHelpers.GetPrime(values.Length);
 1831134            bool removedDuplicates = false;
 135
 1831136            if (modulus >= maxInclusive)
 137            {
 38138                return (uint)(maxInclusive + 1);
 139            }
 140
 64983141            while (true)
 142            {
 68355143                if (modulus >= maxInclusive)
 144                {
 145                    // Try to remove duplicates and try again.
 1579146                    if (!removedDuplicates && TryRemoveDuplicates(values, out char[]? deduplicated))
 147                    {
 1579148                        removedDuplicates = true;
 1579149                        values = deduplicated;
 1579150                        modulus = HashHelpers.GetPrime(values.Length);
 1579151                        continue;
 152                    }
 153
 0154                    return (uint)(maxInclusive + 1);
 155                }
 156
 66776157                if (TestModulus(values, modulus))
 158                {
 1793159                    return (uint)modulus;
 160                }
 161
 64983162                modulus = HashHelpers.GetPrime(modulus + 1);
 163            }
 164
 165            static bool TestModulus(ReadOnlySpan<char> values, int modulus)
 166            {
 66776167                Debug.Assert(modulus < MaxModulus);
 168
 66776169                bool[] seen = ArrayPool<bool>.Shared.Rent(modulus);
 66776170                seen.AsSpan(0, modulus).Clear();
 171
 66776172                uint multiplier = GetFastModMultiplier((uint)modulus);
 173
 737215174                foreach (char c in values)
 175                {
 334323176                    ulong index = FastMod(c, (uint)modulus, multiplier);
 177
 334323178                    if (seen[index])
 179                    {
 64983180                        ArrayPool<bool>.Shared.Return(seen);
 64983181                        return false;
 182                    }
 183
 269340184                    seen[index] = true;
 185                }
 186
 187                // Saw no duplicates.
 1793188                ArrayPool<bool>.Shared.Return(seen);
 1793189                return true;
 190            }
 191
 192            static bool TryRemoveDuplicates(ReadOnlySpan<char> values, [NotNullWhen(true)] out char[]? deduplicated)
 193            {
 1579194                HashSet<char> unique = [.. values];
 195
 1579196                if (unique.Count == values.Length)
 197                {
 0198                    deduplicated = null;
 0199                    return false;
 200                }
 201
 1579202                deduplicated = new char[unique.Count];
 1579203                unique.CopyTo(deduplicated);
 1579204                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        {
 1009239211            Debug.Assert(divisor > 0);
 1009239212            Debug.Assert(divisor <= MaxModulus);
 213
 1009239214            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        {
 940632221            Debug.Assert(multiplier == GetFastModMultiplier(divisor));
 222
 940632223            ulong result = ((ulong)(multiplier * value) * divisor) >> 32;
 224
 940632225            Debug.Assert(result == (value % divisor));
 940632226            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        {
 10595234            ref char searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength);
 10595235            ref char cur = ref searchSpace;
 236
 10595237            if (TUseFastContains.Value)
 238            {
 10595239                Debug.Assert(state._hashEntries is not null);
 240
 10595241                char[] hashEntries = state._hashEntries;
 10595242                uint multiplier = state._multiplier;
 243
 124476244                while (!Unsafe.AreSame(ref cur, ref searchSpaceEnd))
 245                {
 118610246                    char c = cur;
 118610247                    if (TNegator.NegateIfNeeded(FastContains(hashEntries, multiplier, c)))
 248                    {
 4729249                        return (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref cur) / sizeof(char));
 250                    }
 251
 113881252                    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
 5866269            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        {
 5216277            if (TUseFastContains.Value)
 278            {
 5216279                Debug.Assert(state._hashEntries is not null);
 280
 5216281                char[] hashEntries = state._hashEntries;
 5216282                uint multiplier = state._multiplier;
 283
 19252284                while (--searchSpaceLength >= 0)
 285                {
 16554286                    char c = Unsafe.Add(ref searchSpace, searchSpaceLength);
 16554287                    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
 5216305            return searchSpaceLength;
 306        }
 307    }
 308}
 309
Generated by: ReportGenerator 5.5.11.0
10/9/2026 - 5:35:25 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&)