< Summary

Information
Class: System.Buffers.SingleStringSearchValuesThreeChars<T1, T2>
Assembly: System.Private.CoreLib
File(s): https://raw.githubusercontent.com/dotnet/runtime/811a7eabb75c42db53440e8ba3f60c07511cfd1f/src/libraries/System.Private.CoreLib/src/System/SearchValues/Strings/SingleStringSearchValuesThreeChars.cs
Line coverage
0%
Covered lines: 0
Uncovered lines: 143
Coverable lines: 143
Total lines: 390
Line coverage: 0%
Branch coverage
0%
Covered branches: 0
Total branches: 80
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%880%
IndexOfAnyMultiString(...)100%110%
IndexOf(...)0%44440%
GetComparisonResult(...)0%220%
GetComparisonResult(...)0%220%
GetComparisonResult(...)0%220%
TryMatch(...)0%660%
TryMatch(...)0%660%
ContainsCore(...)0%440%
GetValues()0%220%

File(s)

https://raw.githubusercontent.com/dotnet/runtime/811a7eabb75c42db53440e8ba3f60c07511cfd1f/src/libraries/System.Private.CoreLib/src/System/SearchValues/Strings/SingleStringSearchValuesThreeChars.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.Generic;
 5using System.Diagnostics;
 6using System.Numerics;
 7using System.Runtime.CompilerServices;
 8using System.Runtime.InteropServices;
 9using System.Runtime.Intrinsics;
 10using static System.Buffers.StringSearchValuesHelper;
 11
 12namespace System.Buffers
 13{
 14    // Based on SpanHelpers.IndexOf(ref char, int, ref char, int)
 15    // This implementation uses 3 precomputed anchor points when searching.
 16    // This implementation may also be used for length=2 values, in which case two anchors point at the same position.
 17    // Has an O(i * m) worst-case, with the expected time closer to O(i) for most inputs.
 18    internal sealed class SingleStringSearchValuesThreeChars<TValueLength, TCaseSensitivity> : StringSearchValuesBase
 19        where TValueLength : struct, IValueLength
 20        where TCaseSensitivity : struct, ICaseSensitivity
 21    {
 22        private const ushort CaseConversionMask = unchecked((ushort)~0x20);
 23
 24        private readonly SingleValueState _valueState;
 25        private readonly nint _minusValueTailLength;
 26        private readonly nuint _ch2ByteOffset;
 27        private readonly nuint _ch3ByteOffset;
 28        private readonly ushort _ch1;
 29        private readonly ushort _ch2;
 30        private readonly ushort _ch3;
 31
 032        private static bool IgnoreCase => typeof(TCaseSensitivity) != typeof(CaseSensitive);
 33
 34        // If the value is short (ValueLengthLessThan4 => 2 or 3 characters), the anchors already represent the whole va
 35        // With case-sensitive comparisons, we've therefore already confirmed the match.
 36        // With case-insensitive comparisons, we've applied the CaseConversionMask to the input, so while the anchors li
 37        // An exception to that is if we know the value is composed of only ASCII letters, in which case masking the inp
 38        private static bool CanSkipAnchorMatchVerification
 39        {
 40            [MethodImpl(MethodImplOptions.AggressiveInlining)]
 41            get =>
 042                typeof(TValueLength) == typeof(ValueLengthLessThan4) &&
 043                (typeof(TCaseSensitivity) == typeof(CaseSensitive) || typeof(TCaseSensitivity) == typeof(CaseInsensitive
 44        }
 45
 046        public SingleStringSearchValuesThreeChars(HashSet<string>? uniqueValues, string value, int ch2Offset, int ch3Off
 47        {
 48            // We could have more than one entry in 'uniqueValues' if this value is an exact prefix of all the others.
 049            Debug.Assert(value.Length > 1);
 050            Debug.Assert(ch3Offset == 0 || ch3Offset > ch2Offset);
 51
 052            _valueState = new SingleValueState(value, IgnoreCase);
 053            _minusValueTailLength = -(value.Length - 1);
 54
 055            _ch1 = value[0];
 056            _ch2 = value[ch2Offset];
 057            _ch3 = value[ch3Offset];
 58
 059            if (IgnoreCase)
 60            {
 061                Debug.Assert(char.IsAscii((char)_ch1) && char.IsAscii((char)_ch2) && char.IsAscii((char)_ch3));
 62
 063                _ch1 &= CaseConversionMask;
 064                _ch2 &= CaseConversionMask;
 065                _ch3 &= CaseConversionMask;
 66            }
 67
 068            _ch2ByteOffset = (nuint)ch2Offset * 2;
 069            _ch3ByteOffset = (nuint)ch3Offset * 2;
 070        }
 71
 72        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 73        internal override int IndexOfAnyMultiString(ReadOnlySpan<char> span) =>
 074            IndexOf(ref MemoryMarshal.GetReference(span), span.Length);
 75
 76        private int IndexOf(ref char searchSpace, int searchSpaceLength)
 77        {
 078            ref char searchSpaceStart = ref searchSpace;
 79
 080            nint searchSpaceMinusValueTailLength = searchSpaceLength + _minusValueTailLength;
 81
 082            if (!Vector128.IsHardwareAccelerated || searchSpaceMinusValueTailLength < Vector128<ushort>.Count)
 83            {
 84                goto ShortInput;
 85            }
 86
 087            nuint ch2ByteOffset = _ch2ByteOffset;
 088            nuint ch3ByteOffset = _ch3ByteOffset;
 89
 090            if (Vector512.IsHardwareAccelerated && searchSpaceMinusValueTailLength - Vector512<ushort>.Count >= 0)
 91            {
 092                Vector512<ushort> ch1 = Vector512.Create(_ch1);
 093                Vector512<ushort> ch2 = Vector512.Create(_ch2);
 094                Vector512<ushort> ch3 = Vector512.Create(_ch3);
 95
 096                ref char lastSearchSpace = ref Unsafe.Add(ref searchSpace, searchSpaceMinusValueTailLength - Vector512<u
 97
 98                while (true)
 99                {
 0100                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector512<ushort>.Cou
 0101                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector512<ushort>.Cou
 0102                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector512<ushort>.Cou
 103
 104                    // Find which starting positions likely contain a match (likely match all 3 anchor characters).
 0105                    Vector512<byte> result = GetComparisonResult(ref searchSpace, ch2ByteOffset, ch3ByteOffset, ch1, ch2
 106
 0107                    if (result != Vector512<byte>.Zero)
 108                    {
 109                        goto CandidateFound;
 110                    }
 111
 112                LoopFooter:
 113                    // We haven't found a match. Update the input position and check if we've reached the end.
 0114                    searchSpace = ref Unsafe.Add(ref searchSpace, Vector512<ushort>.Count);
 115
 0116                    if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpace))
 117                    {
 0118                        if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpace, Vector512<ushort>.Count)
 119                        {
 0120                            return -1;
 121                        }
 122
 123                        // We have fewer than 32 characters remaining. Adjust the input position such that we will do on
 0124                        searchSpace = ref lastSearchSpace;
 125                    }
 126
 0127                    continue;
 128
 129                CandidateFound:
 130                    // We found potential matches, but they may be false-positives, so we must verify each one.
 0131                    if (TryMatch(ref searchSpaceStart, searchSpaceLength, ref searchSpace, result.ExtractMostSignificant
 132                    {
 0133                        return offset;
 134                    }
 135                    goto LoopFooter;
 136                }
 137            }
 0138            else if (Vector256.IsHardwareAccelerated && searchSpaceMinusValueTailLength - Vector256<ushort>.Count >= 0)
 139            {
 0140                Vector256<ushort> ch1 = Vector256.Create(_ch1);
 0141                Vector256<ushort> ch2 = Vector256.Create(_ch2);
 0142                Vector256<ushort> ch3 = Vector256.Create(_ch3);
 143
 0144                ref char lastSearchSpace = ref Unsafe.Add(ref searchSpace, searchSpaceMinusValueTailLength - Vector256<u
 145
 146                while (true)
 147                {
 0148                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector256<ushort>.Cou
 0149                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector256<ushort>.Cou
 0150                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector256<ushort>.Cou
 151
 152                    // Find which starting positions likely contain a match (likely match all 3 anchor characters).
 0153                    Vector256<byte> result = GetComparisonResult(ref searchSpace, ch2ByteOffset, ch3ByteOffset, ch1, ch2
 154
 0155                    if (result != Vector256<byte>.Zero)
 156                    {
 157                        goto CandidateFound;
 158                    }
 159
 160                LoopFooter:
 0161                    searchSpace = ref Unsafe.Add(ref searchSpace, Vector256<ushort>.Count);
 162
 0163                    if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpace))
 164                    {
 0165                        if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpace, Vector256<ushort>.Count)
 166                        {
 0167                            return -1;
 168                        }
 169
 170                        // We have fewer than 16 characters remaining. Adjust the input position such that we will do on
 0171                        searchSpace = ref lastSearchSpace;
 172                    }
 173
 0174                    continue;
 175
 176                CandidateFound:
 177                    // We found potential matches, but they may be false-positives, so we must verify each one.
 0178                    if (TryMatch(ref searchSpaceStart, searchSpaceLength, ref searchSpace, result.ExtractMostSignificant
 179                    {
 0180                        return offset;
 181                    }
 182                    goto LoopFooter;
 183                }
 184            }
 185            else
 186            {
 0187                Vector128<ushort> ch1 = Vector128.Create(_ch1);
 0188                Vector128<ushort> ch2 = Vector128.Create(_ch2);
 0189                Vector128<ushort> ch3 = Vector128.Create(_ch3);
 190
 0191                ref char lastSearchSpace = ref Unsafe.Add(ref searchSpace, searchSpaceMinusValueTailLength - Vector128<u
 192
 193                while (true)
 194                {
 0195                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector128<ushort>.Cou
 0196                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector128<ushort>.Cou
 0197                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector128<ushort>.Cou
 198
 199                    // Find which starting positions likely contain a match (likely match all 3 anchor characters).
 0200                    Vector128<byte> result = GetComparisonResult(ref searchSpace, ch2ByteOffset, ch3ByteOffset, ch1, ch2
 201
 0202                    if (result != Vector128<byte>.Zero)
 203                    {
 204                        goto CandidateFound;
 205                    }
 206
 207                LoopFooter:
 0208                    searchSpace = ref Unsafe.Add(ref searchSpace, Vector128<ushort>.Count);
 209
 0210                    if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpace))
 211                    {
 0212                        if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpace, Vector128<ushort>.Count)
 213                        {
 0214                            return -1;
 215                        }
 216
 217                        // We have fewer than 8 characters remaining. Adjust the input position such that we will do one
 0218                        searchSpace = ref lastSearchSpace;
 219                    }
 220
 0221                    continue;
 222
 223                CandidateFound:
 224                    // We found potential matches, but they may be false-positives, so we must verify each one.
 0225                    if (TryMatch(ref searchSpaceStart, searchSpaceLength, ref searchSpace, result.ExtractMostSignificant
 226                    {
 0227                        return offset;
 228                    }
 229                    goto LoopFooter;
 230                }
 231            }
 232
 233        ShortInput:
 0234            char valueHead = _valueState.Value.GetRawStringData();
 235
 0236            for (nint i = 0; i < searchSpaceMinusValueTailLength; i++)
 237            {
 0238                ref char cur = ref Unsafe.Add(ref searchSpace, i);
 239
 240                // CaseInsensitiveUnicode doesn't support single-character transformations, so we skip checking the firs
 0241                if ((typeof(TCaseSensitivity) == typeof(CaseInsensitiveUnicode) || TCaseSensitivity.TransformInput(cur) 
 0242                    TCaseSensitivity.Equals<TValueLength>(ref cur, in _valueState))
 243                {
 0244                    return (int)i;
 245                }
 246            }
 247
 0248            return -1;
 249        }
 250
 251        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 252        private static Vector128<byte> GetComparisonResult(ref char searchSpace, nuint ch2ByteOffset, nuint ch3ByteOffse
 253        {
 254            // Load 3 vectors from the input.
 255            // One from the current search space, the other two at an offset based on the distance of those characters f
 0256            if (typeof(TCaseSensitivity) == typeof(CaseSensitive))
 257            {
 0258                Vector128<ushort> cmpCh1 = Vector128.Equals(ch1, Vector128.LoadUnsafe(ref searchSpace));
 0259                Vector128<ushort> cmpCh2 = Vector128.Equals(ch2, Vector128.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 0260                Vector128<ushort> cmpCh3 = Vector128.Equals(ch3, Vector128.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 261                // AND all 3 together to get a mask of possible match positions that match in at least 3 places.
 0262                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 263            }
 264            else
 265            {
 266                // For each, AND the value with ~0x20 so that letters are uppercased.
 267                // For characters that aren't ASCII letters, this may produce wrong results, but only false-positives.
 268                // We will take care of those in the verification step if the other characters also indicate a possible 
 0269                Vector128<ushort> caseConversion = Vector128.Create(CaseConversionMask);
 270
 0271                Vector128<ushort> cmpCh1 = Vector128.Equals(ch1, Vector128.LoadUnsafe(ref searchSpace) & caseConversion)
 0272                Vector128<ushort> cmpCh2 = Vector128.Equals(ch2, Vector128.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 0273                Vector128<ushort> cmpCh3 = Vector128.Equals(ch3, Vector128.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 274                // AND all 3 together to get a mask of possible match positions that likely match in at least 3 places.
 0275                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 276            }
 277        }
 278
 279        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 280        private static Vector256<byte> GetComparisonResult(ref char searchSpace, nuint ch2ByteOffset, nuint ch3ByteOffse
 281        {
 282            // See comments in 'GetComparisonResult' for Vector128<byte> above.
 283            // This method is the same, but operates on 16 input characters at a time.
 0284            if (typeof(TCaseSensitivity) == typeof(CaseSensitive))
 285            {
 0286                Vector256<ushort> cmpCh1 = Vector256.Equals(ch1, Vector256.LoadUnsafe(ref searchSpace));
 0287                Vector256<ushort> cmpCh2 = Vector256.Equals(ch2, Vector256.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 0288                Vector256<ushort> cmpCh3 = Vector256.Equals(ch3, Vector256.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 0289                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 290            }
 291            else
 292            {
 0293                Vector256<ushort> caseConversion = Vector256.Create(CaseConversionMask);
 294
 0295                Vector256<ushort> cmpCh1 = Vector256.Equals(ch1, Vector256.LoadUnsafe(ref searchSpace) & caseConversion)
 0296                Vector256<ushort> cmpCh2 = Vector256.Equals(ch2, Vector256.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 0297                Vector256<ushort> cmpCh3 = Vector256.Equals(ch3, Vector256.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 0298                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 299            }
 300        }
 301
 302        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 303        private static Vector512<byte> GetComparisonResult(ref char searchSpace, nuint ch2ByteOffset, nuint ch3ByteOffse
 304        {
 305            // See comments in 'GetComparisonResult' for Vector128<byte> above.
 306            // This method is the same, but operates on 32 input characters at a time.
 0307            if (typeof(TCaseSensitivity) == typeof(CaseSensitive))
 308            {
 0309                Vector512<ushort> cmpCh1 = Vector512.Equals(ch1, Vector512.LoadUnsafe(ref searchSpace));
 0310                Vector512<ushort> cmpCh2 = Vector512.Equals(ch2, Vector512.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 0311                Vector512<ushort> cmpCh3 = Vector512.Equals(ch3, Vector512.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 0312                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 313            }
 314            else
 315            {
 0316                Vector512<ushort> caseConversion = Vector512.Create(CaseConversionMask);
 317
 0318                Vector512<ushort> cmpCh1 = Vector512.Equals(ch1, Vector512.LoadUnsafe(ref searchSpace) & caseConversion)
 0319                Vector512<ushort> cmpCh2 = Vector512.Equals(ch2, Vector512.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 0320                Vector512<ushort> cmpCh3 = Vector512.Equals(ch3, Vector512.LoadUnsafe(ref Unsafe.As<char, byte>(ref sear
 0321                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 322            }
 323        }
 324
 325        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 326        private bool TryMatch(ref char searchSpaceStart, int searchSpaceLength, ref char searchSpace, uint mask, out int
 327        {
 328            // 'mask' encodes the input positions where at least 3 characters likely matched.
 329            // Verify each one to see if we've found a match, otherwise return back to the vectorized loop.
 330            do
 331            {
 0332                int bitPos = BitOperations.TrailingZeroCount(mask);
 0333                Debug.Assert(bitPos % 2 == 0);
 334
 0335                ref char matchRef = ref Unsafe.AddByteOffset(ref searchSpace, bitPos);
 336
 0337                ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref matchRef, _valueState.Value.Length);
 338
 0339                if (CanSkipAnchorMatchVerification || TCaseSensitivity.Equals<TValueLength>(ref matchRef, in _valueState
 340                {
 0341                    offsetFromStart = (int)((nuint)Unsafe.ByteOffset(ref searchSpaceStart, ref matchRef) / sizeof(char))
 0342                    return true;
 343                }
 344
 0345                mask = BitOperations.ResetLowestSetBit(BitOperations.ResetLowestSetBit(mask));
 346            }
 0347            while (mask != 0);
 348
 0349            offsetFromStart = 0;
 0350            return false;
 351        }
 352
 353        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 354        private bool TryMatch(ref char searchSpaceStart, int searchSpaceLength, ref char searchSpace, ulong mask, out in
 355        {
 356            // 'mask' encodes the input positions where at least 3 characters likely matched.
 357            // Verify each one to see if we've found a match, otherwise return back to the vectorized loop.
 358            do
 359            {
 0360                int bitPos = BitOperations.TrailingZeroCount(mask);
 0361                Debug.Assert(bitPos % 2 == 0);
 362
 0363                ref char matchRef = ref Unsafe.AddByteOffset(ref searchSpace, bitPos);
 364
 0365                ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref matchRef, _valueState.Value.Length);
 366
 0367                if (CanSkipAnchorMatchVerification || TCaseSensitivity.Equals<TValueLength>(ref matchRef, in _valueState
 368                {
 0369                    offsetFromStart = (int)((nuint)Unsafe.ByteOffset(ref searchSpaceStart, ref matchRef) / 2);
 0370                    return true;
 371                }
 372
 0373                mask = BitOperations.ResetLowestSetBit(BitOperations.ResetLowestSetBit(mask));
 374            }
 0375            while (mask != 0);
 376
 0377            offsetFromStart = 0;
 0378            return false;
 379        }
 380
 0381        internal override bool ContainsCore(string value) => HasUniqueValues
 0382            ? base.ContainsCore(value)
 0383            : _valueState.Value.Equals(value, IgnoreCase ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal
 384
 0385        internal override string[] GetValues() => HasUniqueValues
 0386            ? base.GetValues()
 0387            : [_valueState.Value];
 388    }
 389}
 390
Generated by: ReportGenerator 5.5.11.0
10/9/2026 - 5:35:27 PM
GitHub | reportgenerator.io

Methods/Properties

IgnoreCase()
CanSkipAnchorMatchVerification()
.ctor(System.Collections.Generic.HashSet`1<System.String>,System.String,System.Int32,System.Int32)
IndexOfAnyMultiString(System.ReadOnlySpan`1<System.Char>)
IndexOf(System.Char&,System.Int32)
GetComparisonResult(System.Char&,System.UIntPtr,System.UIntPtr,System.Runtime.Intrinsics.Vector128`1<System.UInt16>,System.Runtime.Intrinsics.Vector128`1<System.UInt16>,System.Runtime.Intrinsics.Vector128`1<System.UInt16>)
GetComparisonResult(System.Char&,System.UIntPtr,System.UIntPtr,System.Runtime.Intrinsics.Vector256`1<System.UInt16>,System.Runtime.Intrinsics.Vector256`1<System.UInt16>,System.Runtime.Intrinsics.Vector256`1<System.UInt16>)
GetComparisonResult(System.Char&,System.UIntPtr,System.UIntPtr,System.Runtime.Intrinsics.Vector512`1<System.UInt16>,System.Runtime.Intrinsics.Vector512`1<System.UInt16>,System.Runtime.Intrinsics.Vector512`1<System.UInt16>)
TryMatch(System.Char&,System.Int32,System.Char&,System.UInt32,System.Int32&)
TryMatch(System.Char&,System.Int32,System.Char&,System.UInt64,System.Int32&)
ContainsCore(System.String)
GetValues()