< Summary

Information
Class: Trailblazer.Pathing.NavigationGridChangeIngress
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/NavigationGridChangeIngress.cs
Line coverage
100%
Covered lines: 274
Uncovered lines: 0
Coverable lines: 274
Total lines: 496
Line coverage: 100%
Branch coverage
100%
Covered branches: 132
Total branches: 132
Branch coverage: 100%
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_IndexCapacity()100%11100%
get_HasPendingWork()100%22100%
GetRetainedBytes()100%11100%
GetMaximumCapacity(...)100%44100%
GetRetainedBytes(...)100%11100%
Enqueue(...)100%1414100%
DetachInto(...)100%11100%
DetachInto(...)100%2020100%
RequeuePrefix(...)100%3030100%
MarkResnapshotRequired()100%11100%
Reset()100%11100%
Dispose()100%11100%
Append(...)100%22100%
Prepend(...)100%22100%
IsOrderedBeforeCurrent(...)100%66100%
Unlink(...)100%44100%
ResetSlots()100%66100%
IsTopologyLifecycle(...)100%44100%
GetIndexCapacity(...)100%22100%
AlignToEight(...)100%11100%
TrackScope(...)100%1010100%
UntrackScope(...)100%1212100%
CopyBlockedScopes(...)100%66100%
.ctor(...)100%11100%
.ctor(...)100%11100%
TryCreate(...)100%22100%
Equals(...)100%66100%
GetHashCode()100%11100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/NavigationGridChangeIngress.cs

#LineLine coverage
 1//=======================================================================
 2// NavigationGridChangeIngress.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using GridForge.Grids;
 10using GridForge.Spatial;
 11using SwiftCollections;
 12using SwiftCollections.Utility;
 13
 14namespace Trailblazer.Pathing;
 15
 16/// <summary>Buffers the single GridForge committed final-state feed without running graph work in callbacks.</summary>
 17internal sealed unsafe class NavigationGridChangeIngress
 18{
 19    private const int BaseRetainedBytes = 384;
 120    private static readonly int EventSlotBytes = sizeof(GridEventInfo) + (2 * sizeof(int));
 121    private static readonly int DictionaryEntryBytes = AlignToEight(
 122        sizeof(EventKey) + (2 * sizeof(int)) + sizeof(bool));
 123    private static readonly int ScopeEntryBytes = AlignToEight(
 124        sizeof(NavigationGridChangeScope) + sizeof(int));
 121425    private readonly object _sync = new();
 26    private readonly GridEventInfo[] _events;
 27    private readonly int[] _next;
 28    private readonly int[] _previous;
 29    private readonly SwiftDictionary<EventKey, int> _coalescedIndexes;
 30    private readonly ScopeEntry[] _scopes;
 121431    private int _head = -1;
 121432    private int _tail = -1;
 33    private int _freeHead;
 34    private int _count;
 35    private int _scopeCount;
 36    private int _topologyLifecycleCount;
 37    private bool _scopeTrackingAll;
 38    private bool _overflowed;
 39    private bool _overflowedTopologyLifecycle;
 40    private bool _disposed;
 41
 121442    internal NavigationGridChangeIngress(int capacity, int maximumScopes = 16)
 43    {
 121444        _events = new GridEventInfo[capacity];
 121445        _next = new int[capacity];
 121446        _previous = new int[capacity];
 121447        int indexCapacity = checked(((capacity * 100) / 82) + 1);
 121448        _coalescedIndexes = new SwiftDictionary<EventKey, int>(indexCapacity);
 121449        _scopes = new ScopeEntry[maximumScopes];
 121450        ResetSlots();
 121451    }
 52
 353    internal int IndexCapacity => _coalescedIndexes.Capacity;
 54
 55    internal bool HasPendingWork
 56    {
 57        get
 58        {
 659            lock (_sync)
 660                return _overflowed || _count != 0;
 661        }
 62    }
 63
 164    internal long GetRetainedBytes() => GetRetainedBytes(_events.Length, _scopes.Length);
 65
 66    internal static int GetMaximumCapacity(
 67        int maximumEntries,
 68        long maximumBytes,
 69        int maximumScopes = 16)
 70    {
 119971        int low = 0;
 119972        int high = maximumEntries;
 1773973        while (low < high)
 74        {
 1654075            int middle = low + ((high - low + 1) >> 1);
 1654076            if (GetRetainedBytes(middle, maximumScopes) <= maximumBytes)
 941977                low = middle;
 78            else
 712179                high = middle - 1;
 80        }
 119981        return low;
 82    }
 83
 84    internal static long GetRetainedBytes(int capacity, int maximumScopes = 16)
 85    {
 1654286        int indexCapacity = GetIndexCapacity(capacity);
 1654287        return checked(
 1654288            BaseRetainedBytes
 1654289            + ((long)capacity * EventSlotBytes)
 1654290            + ((long)indexCapacity * DictionaryEntryBytes)
 1654291            + ((long)maximumScopes * ScopeEntryBytes));
 92    }
 93
 94    internal void Enqueue(GridEventInfo eventInfo)
 95    {
 129296        lock (_sync)
 97        {
 129298            if (_disposed)
 199                return;
 1291100            if (_overflowed)
 101            {
 3102                TrackScope(eventInfo);
 3103                _overflowedTopologyLifecycle |= IsTopologyLifecycle(eventInfo);
 3104                return;
 105            }
 1288106            if (EventKey.TryCreate(eventInfo, out EventKey key)
 1288107                && _coalescedIndexes.TryGetValue(key, out int existing))
 108            {
 3109                Unlink(existing);
 3110                _events[existing] = eventInfo;
 3111                Append(existing);
 3112                return;
 113            }
 1285114            if (_count == _events.Length)
 115            {
 11116                _overflowed = true;
 11117                TrackScope(eventInfo);
 11118                _overflowedTopologyLifecycle = IsTopologyLifecycle(eventInfo);
 11119                return;
 120            }
 1274121            int insertion = _freeHead;
 1274122            _freeHead = _next[insertion];
 1274123            _events[insertion] = eventInfo;
 1274124            Append(insertion);
 1274125            _count++;
 1274126            if (IsTopologyLifecycle(eventInfo))
 1108127                _topologyLifecycleCount++;
 1274128            if (key.IsValid)
 162129                _coalescedIndexes[key] = insertion;
 1274130            TrackScope(eventInfo);
 1274131        }
 1292132    }
 133
 134    internal int DetachInto(
 135        Span<GridEventInfo> destination,
 136        Span<NavigationGridChangeScope> blockedScopes,
 137        out int blockedScopeCount,
 15138        out bool blockAll) => DetachInto(
 15139            destination,
 15140            blockedScopes,
 15141            out blockedScopeCount,
 15142            out blockAll,
 15143            out _);
 144
 145    internal int DetachInto(
 146        Span<GridEventInfo> destination,
 147        Span<NavigationGridChangeScope> blockedScopes,
 148        out int blockedScopeCount,
 149        out bool blockAll,
 150        out bool topologyLifecycleCoverageLost)
 151    {
 20285152        lock (_sync)
 153        {
 20285154            if (_overflowed)
 155            {
 43156                topologyLifecycleCoverageLost = _topologyLifecycleCount != 0
 43157                    || _overflowedTopologyLifecycle;
 43158                blockedScopeCount = CopyBlockedScopes(blockedScopes, out blockAll);
 43159                _coalescedIndexes.Clear();
 43160                ResetSlots();
 43161                return 0;
 162            }
 163
 20242164            int count = _count < destination.Length ? _count : destination.Length;
 42642165            for (int i = 0; i < count; i++)
 166            {
 1079167                int slot = _head;
 1079168                GridEventInfo eventInfo = _events[slot];
 1079169                destination[i] = eventInfo;
 1079170                Unlink(slot);
 1079171                if (EventKey.TryCreate(eventInfo, out EventKey key)
 1079172                    && _coalescedIndexes.TryGetValue(key, out int indexedSlot)
 1079173                    && indexedSlot == slot)
 174                {
 148175                    _coalescedIndexes.Remove(key);
 176                }
 1079177                UntrackScope(eventInfo);
 1079178                if (IsTopologyLifecycle(eventInfo))
 928179                    _topologyLifecycleCount--;
 1079180                _next[slot] = _freeHead;
 1079181                _previous[slot] = -1;
 1079182                _freeHead = slot;
 183            }
 20242184            _count -= count;
 20242185            topologyLifecycleCoverageLost = false;
 20242186            blockAll = false;
 20242187            blockedScopeCount = _count > 0
 20242188                ? CopyBlockedScopes(blockedScopes, out blockAll)
 20242189                : 0;
 20242190            if (_count == 0)
 191            {
 20237192                blockAll = false;
 20237193                _scopeCount = 0;
 20237194                _scopeTrackingAll = false;
 195            }
 20242196            return count;
 197        }
 20285198    }
 199
 200    /// <summary>
 201    /// Restores an unpublished committed prefix ahead of changes that arrived after detachment.
 202    /// Newer same-address final states win without moving backward in committed sequence order.
 203    /// </summary>
 204    internal void RequeuePrefix(ReadOnlySpan<GridEventInfo> prefix)
 205    {
 10866206        if (prefix.IsEmpty)
 10778207            return;
 88208        lock (_sync)
 209        {
 88210            if (_disposed)
 1211                return;
 87212            if (_overflowed || !IsOrderedBeforeCurrent(prefix))
 213            {
 22214                for (int i = 0; i < prefix.Length; i++)
 215                {
 6216                    TrackScope(prefix[i]);
 6217                    _overflowedTopologyLifecycle |= IsTopologyLifecycle(prefix[i]);
 218                }
 5219                _overflowed = true;
 5220                return;
 221            }
 222
 82223            int insertionCount = 0;
 372224            for (int i = 0; i < prefix.Length; i++)
 225            {
 104226                if (!EventKey.TryCreate(prefix[i], out EventKey key)
 104227                    || !_coalescedIndexes.ContainsKey(key))
 228                {
 103229                    insertionCount++;
 230                    continue;
 231                }
 232            }
 82233            if (insertionCount > _events.Length - _count)
 234            {
 6235                for (int i = 0; i < prefix.Length; i++)
 236                {
 2237                    TrackScope(prefix[i]);
 2238                    _overflowedTopologyLifecycle |= IsTopologyLifecycle(prefix[i]);
 239                }
 1240                _overflowed = true;
 1241                return;
 242            }
 243
 366244            for (int i = prefix.Length - 1; i >= 0; i--)
 245            {
 102246                GridEventInfo eventInfo = prefix[i];
 102247                bool keyed = EventKey.TryCreate(eventInfo, out EventKey key);
 102248                if (keyed && _coalescedIndexes.ContainsKey(key))
 249                    continue;
 101250                int insertion = _freeHead;
 101251                _freeHead = _next[insertion];
 101252                _events[insertion] = eventInfo;
 101253                Prepend(insertion);
 101254                _count++;
 101255                if (IsTopologyLifecycle(eventInfo))
 27256                    _topologyLifecycleCount++;
 101257                if (keyed)
 73258                    _coalescedIndexes[key] = insertion;
 101259                TrackScope(eventInfo);
 260            }
 81261        }
 88262    }
 263
 264    internal void MarkResnapshotRequired()
 265    {
 31266        lock (_sync)
 267        {
 31268            _scopeTrackingAll = true;
 31269            _overflowed = true;
 31270        }
 31271    }
 272
 273    internal void Reset()
 274    {
 24275        lock (_sync)
 276        {
 24277            _coalescedIndexes.Clear();
 24278            ResetSlots();
 24279        }
 24280    }
 281
 282    internal void Dispose()
 283    {
 1198284        lock (_sync)
 285        {
 1198286            _disposed = true;
 1198287            _coalescedIndexes.Clear();
 1198288            ResetSlots();
 1198289        }
 1198290    }
 291
 292    private void Append(int slot)
 293    {
 1277294        _previous[slot] = _tail;
 1277295        _next[slot] = -1;
 1277296        if (_tail >= 0)
 310297            _next[_tail] = slot;
 298        else
 967299            _head = slot;
 1277300        _tail = slot;
 1277301    }
 302
 303    private void Prepend(int slot)
 304    {
 101305        _previous[slot] = -1;
 101306        _next[slot] = _head;
 101307        if (_head >= 0)
 22308            _previous[_head] = slot;
 309        else
 79310            _tail = slot;
 101311        _head = slot;
 101312    }
 313
 314    private bool IsOrderedBeforeCurrent(ReadOnlySpan<GridEventInfo> prefix)
 315    {
 210316        for (int i = 1; i < prefix.Length; i++)
 317        {
 23318            if (prefix[i].ChangeSequence <= prefix[i - 1].ChangeSequence)
 1319                return false;
 320        }
 82321        return _head < 0 || prefix[prefix.Length - 1].ChangeSequence < _events[_head].ChangeSequence;
 322    }
 323
 324    private void Unlink(int slot)
 325    {
 1082326        int previous = _previous[slot];
 1082327        int next = _next[slot];
 1082328        if (previous >= 0)
 1329            _next[previous] = next;
 330        else
 1081331            _head = next;
 1082332        if (next >= 0)
 262333            _previous[next] = previous;
 334        else
 820335            _tail = previous;
 820336    }
 337
 338    private void ResetSlots()
 339    {
 2479340        _head = -1;
 2479341        _tail = -1;
 2479342        _count = 0;
 2479343        _scopeCount = 0;
 2479344        _topologyLifecycleCount = 0;
 2479345        _scopeTrackingAll = false;
 2479346        _overflowed = false;
 2479347        _overflowedTopologyLifecycle = false;
 2479348        _freeHead = _events.Length == 0 ? -1 : 0;
 64006660349        for (int i = 0; i < _events.Length; i++)
 350        {
 32000851351            _previous[i] = -1;
 32000851352            _next[i] = i + 1 < _events.Length ? i + 1 : -1;
 353        }
 2479354    }
 355
 356    private static bool IsTopologyLifecycle(in GridEventInfo eventInfo) =>
 2476357        eventInfo.ChangeKind == GridEventKind.GridAdded
 2476358        || eventInfo.ChangeKind == GridEventKind.GridRemoved
 2476359        || eventInfo.ChangeKind == GridEventKind.WorldReset;
 360
 361    private static int GetIndexCapacity(int capacity)
 362    {
 16542363        int requested = checked(((capacity * 100) / 82) + 1);
 16542364        int result = SwiftDictionary<EventKey, int>.DefaultCapacity;
 204380365        while (result < requested)
 187838366            result = checked(result * 2);
 16542367        return result;
 368    }
 369
 2370    private static int AlignToEight(int value) => (value + 7) & ~7;
 371
 372    private void TrackScope(in GridEventInfo eventInfo)
 373    {
 1397374        if (_scopeTrackingAll)
 5375            return;
 1392376        if (eventInfo.ChangeKind == GridEventKind.WorldReset)
 377        {
 7378            _scopeTrackingAll = true;
 7379            return;
 380        }
 381
 1385382        var scope = new NavigationGridChangeScope(eventInfo);
 3604383        for (int i = 0; i < _scopeCount; i++)
 384        {
 518385            if (!_scopes[i].Scope.Equals(scope))
 386                continue;
 101387            _scopes[i].Scope = scope;
 101388            _scopes[i].Count++;
 101389            return;
 390        }
 1284391        if (_scopeCount == _scopes.Length)
 392        {
 1393            _scopeTrackingAll = true;
 1394            return;
 395        }
 1283396        _scopes[_scopeCount++] = new ScopeEntry(scope, 1);
 1283397    }
 398
 399    private void UntrackScope(in GridEventInfo eventInfo)
 400    {
 1079401        if (_scopeTrackingAll || eventInfo.ChangeKind == GridEventKind.WorldReset)
 2402            return;
 1077403        var scope = new NavigationGridChangeScope(eventInfo);
 1077404        int matchingScopeIndex = _scopes.Length;
 1077405        for (int i = 0;
 2285406            i < _scopeCount && matchingScopeIndex == _scopes.Length;
 1208407            i++)
 408        {
 1208409            if (_scopes[i].Scope.Equals(scope))
 1077410                matchingScopeIndex = i;
 411        }
 412        System.Diagnostics.Debug.Assert(
 413            matchingScopeIndex < _scopeCount,
 414            "Every retained non-global event owns one matching tracked scope.");
 1077415        if (--_scopes[matchingScopeIndex].Count > 0)
 23416            return;
 1054417        _scopes[matchingScopeIndex] = _scopes[--_scopeCount];
 1054418        _scopes[_scopeCount] = default;
 1054419    }
 420
 421    private int CopyBlockedScopes(
 422        Span<NavigationGridChangeScope> destination,
 423        out bool blockAll)
 424    {
 48425        blockAll = _scopeTrackingAll || _scopeCount > destination.Length;
 48426        if (blockAll)
 32427            return 0;
 74428        for (int i = 0; i < _scopeCount; i++)
 21429            destination[i] = _scopes[i].Scope;
 16430        return _scopeCount;
 431    }
 432
 433    private struct ScopeEntry
 434    {
 435        internal ScopeEntry(NavigationGridChangeScope scope, int count)
 436        {
 1283437            Scope = scope;
 1283438            Count = count;
 1283439        }
 440
 441        internal NavigationGridChangeScope Scope;
 442        internal int Count;
 443    }
 444
 445    private readonly struct EventKey : IEquatable<EventKey>
 446    {
 447        private EventKey(
 448            long worldSpawnToken,
 449            ushort gridIndex,
 450            long gridSpawnToken,
 451            VoxelIndex index)
 452        {
 468453            WorldSpawnToken = worldSpawnToken;
 468454            GridIndex = gridIndex;
 468455            GridSpawnToken = gridSpawnToken;
 468456            Index = index;
 468457            IsValid = true;
 468458        }
 459
 460        private long WorldSpawnToken { get; }
 461        private ushort GridIndex { get; }
 462        private long GridSpawnToken { get; }
 463        private VoxelIndex Index { get; }
 464        internal bool IsValid { get; }
 465
 466        internal static bool TryCreate(GridEventInfo eventInfo, out EventKey key)
 467        {
 2573468            if (!eventInfo.HasVoxelState)
 469            {
 2105470                key = default;
 2105471                return false;
 472            }
 468473            key = new EventKey(
 468474                eventInfo.WorldSpawnToken,
 468475                eventInfo.GridIndex,
 468476                eventInfo.GridSpawnToken,
 468477                eventInfo.VoxelIndex);
 468478            return true;
 479        }
 480
 481        public bool Equals(EventKey other) =>
 310482            WorldSpawnToken == other.WorldSpawnToken
 310483            && GridIndex == other.GridIndex
 310484            && GridSpawnToken == other.GridSpawnToken
 310485            && Index.Equals(other.Index);
 486
 487        public override int GetHashCode()
 488        {
 1086489            int hash = SwiftHashTools.CombineHashCodes(
 1086490                WorldSpawnToken.GetHashCode(),
 1086491                GridSpawnToken.GetHashCode());
 1086492            hash = SwiftHashTools.CombineHashCodes(hash, GridIndex.GetHashCode());
 1086493            return SwiftHashTools.CombineHashCodes(hash, Index.GetHashCode());
 494        }
 495    }
 496}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

.cctor()
.ctor(System.Int32,System.Int32)
get_IndexCapacity()
get_HasPendingWork()
GetRetainedBytes()
GetMaximumCapacity(System.Int32,System.Int64,System.Int32)
GetRetainedBytes(System.Int32,System.Int32)
Enqueue(GridForge.Grids.GridEventInfo)
DetachInto(System.Span`1<GridForge.Grids.GridEventInfo>,System.Span`1<Trailblazer.Pathing.NavigationGridChangeScope>,System.Int32&,System.Boolean&)
DetachInto(System.Span`1<GridForge.Grids.GridEventInfo>,System.Span`1<Trailblazer.Pathing.NavigationGridChangeScope>,System.Int32&,System.Boolean&,System.Boolean&)
RequeuePrefix(System.ReadOnlySpan`1<GridForge.Grids.GridEventInfo>)
MarkResnapshotRequired()
Reset()
Dispose()
Append(System.Int32)
Prepend(System.Int32)
IsOrderedBeforeCurrent(System.ReadOnlySpan`1<GridForge.Grids.GridEventInfo>)
Unlink(System.Int32)
ResetSlots()
IsTopologyLifecycle(GridForge.Grids.GridEventInfo&)
GetIndexCapacity(System.Int32)
AlignToEight(System.Int32)
TrackScope(GridForge.Grids.GridEventInfo&)
UntrackScope(GridForge.Grids.GridEventInfo&)
CopyBlockedScopes(System.Span`1<Trailblazer.Pathing.NavigationGridChangeScope>,System.Boolean&)
.ctor(Trailblazer.Pathing.NavigationGridChangeScope,System.Int32)
.ctor(System.Int64,System.UInt16,System.Int64,GridForge.Spatial.VoxelIndex)
TryCreate(GridForge.Grids.GridEventInfo,Trailblazer.Pathing.NavigationGridChangeIngress/EventKey&)
Equals(Trailblazer.Pathing.NavigationGridChangeIngress/EventKey)
GetHashCode()