< 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
0%
Covered lines: 0
Uncovered lines: 106
Coverable lines: 106
Total lines: 309
Line coverage: 0%
Branch coverage
0%
Covered branches: 0
Total branches: 42
Branch coverage: 0%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity NPath complexity Sequence coverage
.ctor(...)0%220%
.ctor(...)100%110%
GetValues()100%110%
FastContains(...)100%110%
FastContains(...)100%110%
SlowProbabilisticContains(...)100%110%
SlowContains(...)100%110%
ConfirmProbabilisticMatch(...)0%220%
FindModulus(...)0%10100%
TestModulus(System.ReadOnlySpan`1<System.Char>,System.Int32)0%440%
TryRemoveDuplicates(System.ReadOnlySpan`1<System.Char>,System.Char[]&)0%440%
GetFastModMultiplier(...)100%110%
FastMod(...)100%110%
IndexOfAnySimpleLoop(...)0%10100%
LastIndexOfAnySimpleLoop(...)0%10100%

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        {
 035            Debug.Assert(!values.IsEmpty);
 36
 037            Map = new ProbabilisticMap(values);
 38
 039            uint modulus = FindModulus(values, maxInclusive);
 040            _multiplier = GetFastModMultiplier(modulus);
 041            _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.
 046            _hashEntries.AsSpan().Fill(values[0]);
 47
 048            foreach (char c in values)
 49            {
 050                _hashEntries[FastMod(c, modulus, _multiplier)] = c;
 51            }
 052        }
 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        {
 076            Debug.Assert(_hashEntries is not null);
 077            Debug.Assert((IntPtr)_slowContainsValuesPtr == IntPtr.Zero);
 78
 079            return FastContains(_hashEntries, _multiplier, value);
 80        }
 81
 82        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 83        private static bool FastContains(char[] hashEntries, uint multiplier, char value)
 84        {
 085            ulong offset = FastMod(value, (uint)hashEntries.Length, multiplier);
 086            Debug.Assert(offset < (ulong)hashEntries.Length);
 87
 088            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        {
 0116            if (TUseFastContains.Value)
 117            {
 0118                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        {
 0131            Debug.Assert(maxInclusive <= char.MaxValue);
 132
 0133            int modulus = HashHelpers.GetPrime(values.Length);
 0134            bool removedDuplicates = false;
 135
 0136            if (modulus >= maxInclusive)
 137            {
 0138                return (uint)(maxInclusive + 1);
 139            }
 140
 0141            while (true)
 142            {
 0143                if (modulus >= maxInclusive)
 144                {
 145                    // Try to remove duplicates and try again.
 0146                    if (!removedDuplicates && TryRemoveDuplicates(values, out char[]? deduplicated))
 147                    {
 0148                        removedDuplicates = true;
 0149                        values = deduplicated;
 0150                        modulus = HashHelpers.GetPrime(values.Length);
 0151                        continue;
 152                    }
 153
 0154                    return (uint)(maxInclusive + 1);
 155                }
 156
 0157                if (TestModulus(values, modulus))
 158                {
 0159                    return (uint)modulus;
 160                }
 161
 0162                modulus = HashHelpers.GetPrime(modulus + 1);
 163            }
 164
 165            static bool TestModulus(ReadOnlySpan<char> values, int modulus)
 166            {
 0167                Debug.Assert(modulus < MaxModulus);
 168
 0169                bool[] seen = ArrayPool<bool>.Shared.Rent(modulus);
 0170                seen.AsSpan(0, modulus).Clear();
 171
 0172                uint multiplier = GetFastModMultiplier((uint)modulus);
 173
 0174                foreach (char c in values)
 175                {
 0176                    ulong index = FastMod(c, (uint)modulus, multiplier);
 177
 0178                    if (seen[index])
 179                    {
 0180                        ArrayPool<bool>.Shared.Return(seen);
 0181                        return false;
 182                    }
 183
 0184                    seen[index] = true;
 185                }
 186
 187                // Saw no duplicates.
 0188                ArrayPool<bool>.Shared.Return(seen);
 0189                return true;
 190            }
 191
 192            static bool TryRemoveDuplicates(ReadOnlySpan<char> values, [NotNullWhen(true)] out char[]? deduplicated)
 193            {
 0194                HashSet<char> unique = [.. values];
 195
 0196                if (unique.Count == values.Length)
 197                {
 0198                    deduplicated = null;
 0199                    return false;
 200                }
 201
 0202                deduplicated = new char[unique.Count];
 0203                unique.CopyTo(deduplicated);
 0204                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        {
 0211            Debug.Assert(divisor > 0);
 0212            Debug.Assert(divisor <= MaxModulus);
 213
 0214            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        {
 0221            Debug.Assert(multiplier == GetFastModMultiplier(divisor));
 222
 0223            ulong result = ((ulong)(multiplier * value) * divisor) >> 32;
 224
 0225            Debug.Assert(result == (value % divisor));
 0226            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        {
 0234            ref char searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength);
 0235            ref char cur = ref searchSpace;
 236
 0237            if (TUseFastContains.Value)
 238            {
 0239                Debug.Assert(state._hashEntries is not null);
 240
 0241                char[] hashEntries = state._hashEntries;
 0242                uint multiplier = state._multiplier;
 243
 0244                while (!Unsafe.AreSame(ref cur, ref searchSpaceEnd))
 245                {
 0246                    char c = cur;
 0247                    if (TNegator.NegateIfNeeded(FastContains(hashEntries, multiplier, c)))
 248                    {
 0249                        return (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref cur) / sizeof(char));
 250                    }
 251
 0252                    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
 0269            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        {
 0277            if (TUseFastContains.Value)
 278            {
 0279                Debug.Assert(state._hashEntries is not null);
 280
 0281                char[] hashEntries = state._hashEntries;
 0282                uint multiplier = state._multiplier;
 283
 0284                while (--searchSpaceLength >= 0)
 285                {
 0286                    char c = Unsafe.Add(ref searchSpace, searchSpaceLength);
 0287                    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
 0305            return searchSpaceLength;
 306        }
 307    }
 308}
 309
Generated by: ReportGenerator 5.5.11.0
10/9/2026 - 5:46:17 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&)