< Summary

Information
Class: System.Buffers.AhoCorasickNode
Assembly: System.Private.CoreLib
File(s): https://raw.githubusercontent.com/dotnet/runtime/811a7eabb75c42db53440e8ba3f60c07511cfd1f/src/libraries/System.Private.CoreLib/src/System/SearchValues/Strings/Helpers/AhoCorasickNode.cs
Line coverage
0%
Covered lines: 0
Uncovered lines: 67
Coverable lines: 67
Total lines: 193
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()100%110%
TryGetChild(...)0%10100%
AddChild(...)0%440%
AddChildrenToQueue(...)0%660%
OptimizeChildren()0%10100%
TryCreateJumpTable(System.Collections.Generic.Dictionary`2<System.Char,System.Int32>,System.Int32[]&)0%660%
TableMemoryFootprintBytesEstimate(System.Int32)100%110%
DictionaryMemoryFootprintBytesEstimate(System.Int32)0%660%

File(s)

https://raw.githubusercontent.com/dotnet/runtime/811a7eabb75c42db53440e8ba3f60c07511cfd1f/src/libraries/System.Private.CoreLib/src/System/SearchValues/Strings/Helpers/AhoCorasickNode.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.Diagnostics.CodeAnalysis;
 7using System.Runtime.CompilerServices;
 8
 9namespace System.Buffers
 10{
 11    internal struct AhoCorasickNode
 12    {
 013        private static object EmptyChildrenSentinel => Array.Empty<int>();
 14
 15        public int SuffixLink;
 16        public int MatchLength;
 17
 18        // This is not a radix tree so we may have a lot of very sparse nodes (single child).
 19        // We save 1 child separately to avoid allocating a separate collection in such cases.
 20        private int _firstChildChar;
 21        private int _firstChildIndex;
 22        private object _children; // Either int[] or Dictionary<char, int>
 23
 24        public AhoCorasickNode()
 25        {
 026            _firstChildChar = -1;
 027            _children = EmptyChildrenSentinel;
 028        }
 29
 30        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 31        public readonly bool TryGetChild(char c, out int index)
 32        {
 033            if (_firstChildChar == c)
 34            {
 035                index = _firstChildIndex;
 036                return true;
 37            }
 38
 039            object children = _children;
 040            Debug.Assert(children is int[] || children is Dictionary<char, int>);
 41
 042            if (children.GetType() == typeof(int[]))
 43            {
 044                int[] table = (int[])children;
 045                if (c < (uint)table.Length)
 46                {
 047                    index = table[c];
 048                    if (index >= 0)
 49                    {
 050                        return true;
 51                    }
 52                }
 53            }
 54            else
 55            {
 056                return Unsafe.As<Dictionary<char, int>>(children).TryGetValue(c, out index);
 57            }
 58
 059            index = 0;
 060            return false;
 61        }
 62
 63        public void AddChild(char c, int index)
 64        {
 065            if (_firstChildChar < 0)
 66            {
 067                _firstChildChar = c;
 068                _firstChildIndex = index;
 69            }
 70            else
 71            {
 072                if (ReferenceEquals(_children, EmptyChildrenSentinel))
 73                {
 074                    _children = new Dictionary<char, int>();
 75                }
 76
 077                ((Dictionary<char, int>)_children).Add(c, index);
 78            }
 079        }
 80
 81        public readonly void AddChildrenToQueue(Queue<(char Char, int Index)> queue)
 82        {
 083            if (_firstChildChar >= 0)
 84            {
 085                queue.Enqueue(((char)_firstChildChar, _firstChildIndex));
 86
 087                if (_children is Dictionary<char, int> children)
 88                {
 089                    foreach ((char childChar, int childIndex) in children)
 90                    {
 091                        queue.Enqueue((childChar, childIndex));
 92                    }
 93                }
 94                else
 95                {
 096                    Debug.Assert(ReferenceEquals(_children, EmptyChildrenSentinel));
 97                }
 98            }
 099        }
 100
 101        public void OptimizeChildren()
 102        {
 0103            if (_children is Dictionary<char, int> children)
 104            {
 0105                children.Add((char)_firstChildChar, _firstChildIndex);
 106
 0107                float frequency = -2;
 108
 109                // We have the _firstChildChar field that will always be checked first.
 110                // Improve throughput by setting it to the child character with the highest frequency.
 0111                foreach ((char childChar, int childIndex) in children)
 112                {
 0113                    float newFrequency = char.IsAscii(childChar) ? CharacterFrequencyHelper.AsciiFrequency[childChar] : 
 114
 0115                    if (newFrequency > frequency)
 116                    {
 0117                        frequency = newFrequency;
 0118                        _firstChildChar = childChar;
 0119                        _firstChildIndex = childIndex;
 120                    }
 121                }
 122
 0123                children.Remove((char)_firstChildChar);
 124
 0125                if (TryCreateJumpTable(children, out int[]? table))
 126                {
 0127                    _children = table;
 128                }
 129            }
 130
 131            static bool TryCreateJumpTable(Dictionary<char, int> children, [NotNullWhen(true)] out int[]? table)
 132            {
 133                // We can use either a Dictionary<char, int> or int[] to map child characters to node indexes.
 134                // int[] is generally faster but consumes more memory for characters with high values.
 135                // We try to find the right balance between memory usage and lookup performance.
 136                // Currently we will sacrifice up to ~2x the memory consumption to use int[] for faster lookups.
 137                const int AcceptableSizeMultiplier = 2;
 138
 0139                Debug.Assert(children.Count > 0);
 140
 0141                int maxValue = -1;
 142
 0143                foreach ((char childChar, _) in children)
 144                {
 0145                    maxValue = Math.Max(maxValue, childChar);
 146                }
 147
 0148                int tableSize = TableMemoryFootprintBytesEstimate(maxValue);
 0149                int dictionarySize = DictionaryMemoryFootprintBytesEstimate(children.Count);
 150
 0151                if (tableSize > dictionarySize * AcceptableSizeMultiplier)
 152                {
 153                    // We would have a lot of empty entries. Avoid wasting too much memory.
 0154                    table = null;
 0155                    return false;
 156                }
 157
 0158                table = new int[maxValue + 1];
 0159                Array.Fill(table, -1);
 160
 0161                foreach ((char childChar, int childIndex) in children)
 162                {
 0163                    table[childChar] = childIndex;
 164                }
 165
 0166                return true;
 167
 168                static int TableMemoryFootprintBytesEstimate(int maxValue)
 169                {
 170                    // An approximate number of bytes consumed by an
 171                    // int[] table with a known number of entries.
 172                    // Only used as a heuristic, so numbers don't have to be exact.
 0173                    return 32 + (maxValue * sizeof(int));
 174                }
 175
 176                static int DictionaryMemoryFootprintBytesEstimate(int childCount)
 177                {
 178                    // An approximate number of bytes consumed by a
 179                    // Dictionary<char, int> with a known number of entries.
 180                    // Only used as a heuristic, so numbers don't have to be exact.
 0181                    return childCount switch
 0182                    {
 0183                        < 4 => 192,
 0184                        < 8 => 272,
 0185                        < 12 => 352,
 0186                        _ => childCount * 25
 0187                    };
 188                }
 189            }
 0190        }
 191    }
 192}
 193
Generated by: ReportGenerator 5.5.11.0
10/9/2026 - 5:46:17 PM
GitHub | reportgenerator.io

Methods/Properties

EmptyChildrenSentinel()
.ctor()
TryGetChild(System.Char,System.Int32&)
AddChild(System.Char,System.Int32)
AddChildrenToQueue(System.Collections.Generic.Queue`1<System.ValueTuple`2<System.Char,System.Int32>>)
OptimizeChildren()
TryCreateJumpTable(System.Collections.Generic.Dictionary`2<System.Char,System.Int32>,System.Int32[]&)
TableMemoryFootprintBytesEstimate(System.Int32)
DictionaryMemoryFootprintBytesEstimate(System.Int32)