< Summary

Information
Class: Trailblazer.Pathing.PathHeapMetadata<T>
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/OpenSet/PathHeapMetadata.cs
Line coverage
100%
Covered lines: 121
Uncovered lines: 0
Coverable lines: 121
Total lines: 283
Line coverage: 100%
Branch coverage
97%
Covered branches: 37
Total branches: 38
Branch coverage: 97.3%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.cctor()100%11100%
.ctor(...)100%11100%
get_Count()100%11100%
get_Item(...)100%22100%
set_Item(...)100%11100%
TryGetValue(...)100%44100%
Set(...)100%66100%
EnumerateClosed(...)100%11100%
Clear()100%22100%
EnsureCapacity(...)100%22100%
TrimExcess()100%22100%
Initialize(...)100%11100%
Resize(...)75%44100%
InsertNew(...)100%22100%
FindSlot(...)100%66100%
GetStoredHash(...)100%11100%
NormalizeCapacity(...)100%22100%
.ctor(...)100%11100%
GetEnumerator()100%11100%
System.Collections.Generic.IEnumerable<TNode>.GetEnumerator()100%11100%
System.Collections.IEnumerable.GetEnumerator()100%11100%
.ctor(...)100%11100%
get_Current()100%11100%
System.Collections.IEnumerator.get_Current()100%11100%
MoveNext()100%66100%
Reset()100%11100%
Dispose()100%11100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/OpenSet/PathHeapMetadata.cs

#LineLine coverage
 1using System;
 2using System.Collections;
 3using System.Collections.Generic;
 4using System.Runtime.CompilerServices;
 5
 6namespace Trailblazer.Pathing;
 7
 8/// <summary>
 9/// Low-allocation metadata table for <see cref="PathHeap{TNode}"/>.
 10/// </summary>
 11internal sealed class PathHeapMetadata<TNode> where TNode : class
 12{
 13    private const double LoadFactorThreshold = 0.72;
 14
 315    private static readonly EqualityComparer<TNode> _comparer = EqualityComparer<TNode>.Default;
 16
 17    private readonly int _minimumCapacity;
 18
 19    private TNode?[] _keys = null!;
 20
 21    private PathHeapMeta[] _values = null!;
 22
 23    private int[] _hashes = null!;
 24
 25    private int[] _occupiedSlots = null!;
 26
 27    private int _mask;
 28
 29    private int _resizeThreshold;
 30
 31    private int _count;
 32
 290933    public PathHeapMetadata(int capacity)
 34    {
 290935        _minimumCapacity = NormalizeCapacity(capacity);
 290936        Initialize(_minimumCapacity);
 290937    }
 38
 12339    public int Count => _count;
 40
 41    public PathHeapMeta this[TNode key]
 42    {
 43        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 44        get
 45        {
 4651046            if (TryGetValue(key, out PathHeapMeta value))
 4650947                return value;
 48
 149            throw new KeyNotFoundException("The requested path heap node is not tracked.");
 50        }
 51        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 2669452        set => Set(key, value);
 53    }
 54
 55    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 56    public bool TryGetValue(TNode key, out PathHeapMeta value)
 57    {
 13015458        if (key == null)
 59        {
 160            value = default;
 161            return false;
 62        }
 63
 13015364        int hash = GetStoredHash(key);
 13015365        int slot = FindSlot(key, hash);
 13015366        if (slot < 0)
 67        {
 2862668            value = default;
 2862669            return false;
 70        }
 71
 10152772        value = _values[slot];
 10152773        return true;
 74    }
 75
 76    public void Set(TNode key, PathHeapMeta value)
 77    {
 2669578        if (key == null)
 179            throw new ArgumentNullException(nameof(key));
 80
 2669481        int hash = GetStoredHash(key);
 2669482        int existingSlot = FindSlot(key, hash);
 2669483        if (existingSlot >= 0)
 84        {
 1419385            _values[existingSlot] = value;
 1419386            return;
 87        }
 88
 1250189        if (_count >= _resizeThreshold)
 1090            Resize(_keys.Length * 2);
 91
 1250192        InsertNew(key, hash, value);
 1250193    }
 94
 95    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 24996    public ClosedEnumerable EnumerateClosed(uint heapVersion) => new(this, heapVersion);
 97
 98    public void Clear()
 99    {
 19926100        for (int i = 0; i < _count; i++)
 101        {
 8250102            int slot = _occupiedSlots[i];
 8250103            _keys[slot] = null;
 8250104            _values[slot] = default;
 8250105            _hashes[slot] = 0;
 8250106            _occupiedSlots[i] = 0;
 107        }
 108
 1713109        _count = 0;
 1713110    }
 111
 112    public void EnsureCapacity(int capacity)
 113    {
 7114        int normalized = NormalizeCapacity(capacity);
 7115        if (normalized > _keys.Length)
 1116            Resize(normalized);
 7117    }
 118
 119    public void TrimExcess()
 120    {
 2121        int target = NormalizeCapacity(Math.Max(_minimumCapacity, _count));
 2122        if (target < _keys.Length)
 1123            Resize(target);
 2124    }
 125
 126    private void Initialize(int capacity)
 127    {
 2921128        _keys = new TNode?[capacity];
 2921129        _values = new PathHeapMeta[capacity];
 2921130        _hashes = new int[capacity];
 2921131        _occupiedSlots = new int[capacity];
 2921132        _mask = capacity - 1;
 2921133        _resizeThreshold = Math.Max(1, (int)(capacity * LoadFactorThreshold));
 2921134        _count = 0;
 2921135    }
 136
 137    private void Resize(int capacity)
 138    {
 12139        TNode?[] oldKeys = _keys;
 12140        PathHeapMeta[] oldValues = _values;
 12141        int[] oldHashes = _hashes;
 12142        int[] oldOccupiedSlots = _occupiedSlots;
 12143        int oldCount = _count;
 144
 12145        Initialize(NormalizeCapacity(capacity));
 146
 12378147        for (int i = 0; i < oldCount; i++)
 148        {
 6177149            int oldSlot = oldOccupiedSlots[i];
 6177150            TNode? key = oldKeys[oldSlot];
 6177151            if (key != null)
 6177152                InsertNew(key, oldHashes[oldSlot], oldValues[oldSlot]);
 153        }
 12154    }
 155
 156    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 157    private void InsertNew(TNode key, int hash, PathHeapMeta value)
 158    {
 18678159        int slot = hash & _mask;
 30549160        while (_keys[slot] != null)
 11871161            slot = (slot + 1) & _mask;
 162
 18678163        _keys[slot] = key;
 18678164        _hashes[slot] = hash;
 18678165        _values[slot] = value;
 18678166        _occupiedSlots[_count++] = slot;
 18678167    }
 168
 169    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 170    private int FindSlot(TNode key, int hash)
 171    {
 156847172        int slot = hash & _mask;
 173
 65768174        while (true)
 175        {
 222615176            TNode? candidate = _keys[slot];
 222615177            if (candidate == null)
 41127178                return -1;
 179
 181488180            if (_hashes[slot] == hash && _comparer.Equals(candidate, key))
 115720181                return slot;
 182
 65768183            slot = (slot + 1) & _mask;
 184        }
 185    }
 186
 187    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 188    private static int GetStoredHash(TNode key)
 189    {
 190        unchecked
 191        {
 156847192            uint hash = (uint)_comparer.GetHashCode(key);
 156847193            hash ^= hash >> 16;
 156847194            hash *= 0x7feb352d;
 156847195            hash ^= hash >> 15;
 156847196            hash *= 0x846ca68b;
 156847197            hash ^= hash >> 16;
 156847198            return (int)(hash & 0x7FFFFFFF);
 199        }
 200    }
 201
 202    private static int NormalizeCapacity(int capacity)
 203    {
 2930204        int normalized = 1;
 23454205        while (normalized < capacity)
 20524206            normalized <<= 1;
 207
 2930208        return Math.Max(2, normalized);
 209    }
 210
 211    internal readonly struct ClosedEnumerable : IEnumerable<TNode>
 212    {
 213        private readonly PathHeapMetadata<TNode> _metadata;
 214
 215        private readonly uint _heapVersion;
 216
 217        public ClosedEnumerable(PathHeapMetadata<TNode> metadata, uint heapVersion)
 218        {
 249219            _metadata = metadata;
 249220            _heapVersion = heapVersion;
 249221        }
 222
 223        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 249224        public Enumerator GetEnumerator() => new(_metadata, _heapVersion);
 225
 3226        IEnumerator<TNode> IEnumerable<TNode>.GetEnumerator() => GetEnumerator();
 227
 1228        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 229    }
 230
 231    internal struct Enumerator : IEnumerator<TNode>
 232    {
 233        private readonly PathHeapMetadata<TNode> _metadata;
 234
 235        private readonly uint _heapVersion;
 236
 237        private int _index;
 238
 239        private TNode? _current;
 240
 241        public Enumerator(PathHeapMetadata<TNode> metadata, uint heapVersion)
 242        {
 249243            _metadata = metadata;
 249244            _heapVersion = heapVersion;
 249245            _index = 0;
 249246            _current = null;
 249247        }
 248
 3639249        public readonly TNode Current => _current!;
 250
 2251        readonly object IEnumerator.Current => Current;
 252
 253        public bool MoveNext()
 254        {
 3895255            while (_index < _metadata._count)
 256            {
 3647257                int slot = _metadata._occupiedSlots[_index++];
 3647258                if (_metadata._values[slot].ClosedHeapVersion != _heapVersion)
 259                    continue;
 260
 3638261                TNode? key = _metadata._keys[slot];
 3638262                if (key == null)
 263                    continue;
 264
 3638265                _current = key;
 3638266                return true;
 267            }
 268
 248269            _current = null;
 248270            return false;
 271        }
 272
 273        public void Reset()
 274        {
 1275            _index = 0;
 1276            _current = null;
 1277        }
 278
 279        public readonly void Dispose()
 280        {
 248281        }
 282    }
 283}
Generated by: ReportGenerator 5.5.10.0
05/19/2026 - 21:06:43
GitHub | reportgenerator.io

Methods/Properties

.cctor()
.ctor(System.Int32)
get_Count()
get_Item(TNode)
set_Item(TNode,Trailblazer.Pathing.PathHeapMeta)
TryGetValue(TNode,Trailblazer.Pathing.PathHeapMeta&)
Set(TNode,Trailblazer.Pathing.PathHeapMeta)
EnumerateClosed(System.UInt32)
Clear()
EnsureCapacity(System.Int32)
TrimExcess()
Initialize(System.Int32)
Resize(System.Int32)
InsertNew(TNode,System.Int32,Trailblazer.Pathing.PathHeapMeta)
FindSlot(TNode,System.Int32)
GetStoredHash(TNode)
NormalizeCapacity(System.Int32)
.ctor(Trailblazer.Pathing.PathHeapMetadata`1<TNode>,System.UInt32)
GetEnumerator()
System.Collections.Generic.IEnumerable<TNode>.GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
.ctor(Trailblazer.Pathing.PathHeapMetadata`1<TNode>,System.UInt32)
get_Current()
System.Collections.IEnumerator.get_Current()
MoveNext()
Reset()
Dispose()