< Summary

Information
Class: Trailblazer.Pathing.NavigationAStarAdmissionGate
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/AStar/NavigationAStarAdmissionGate.cs
Line coverage
100%
Covered lines: 238
Uncovered lines: 0
Coverable lines: 238
Total lines: 480
Line coverage: 100%
Branch coverage
100%
Covered branches: 68
Total branches: 68
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor(...)100%22100%
get_PayloadCache()100%11100%
Begin(...)100%44100%
Begin(...)100%66100%
Dispose()100%44100%
CancelActive()100%22100%
CanBegin()100%22100%
FitsBatchEnvelope(...)100%44100%
FitsSingleEnvelope(...)100%11100%
BeginCore(...)100%1010100%
GetDescriptor(...)100%44100%
GetAdmittedCount(...)100%11100%
IsAdmissionComplete(...)100%11100%
GetStatus(...)100%22100%
IsReadyToPublish(...)100%22100%
AdvanceAdmission(...)100%44100%
AdvanceSearch(...)100%22100%
PublishReadyPrefix(...)100%66100%
TakeResult(...)100%11100%
Release(...)100%66100%
EnsureActive(...)100%22100%
IsActive(...)100%44100%
.ctor(...)100%11100%
CompareTo(...)100%22100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/AStar/NavigationAStarAdmissionGate.cs

#LineLine coverage
 1//=======================================================================
 2// NavigationAStarAdmissionGate.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 System.Threading;
 10using GridForge.Grids;
 11
 12namespace Trailblazer.Pathing;
 13
 14/// <summary>Serializes context-owned A* resource admission.</summary>
 15internal sealed class NavigationAStarAdmissionGate : IDisposable
 16{
 100617    private readonly object _sync = new();
 18    private readonly NavigationWorldGraphStore _store;
 19    private readonly NavigationQueryLimits _limits;
 20    private readonly NavigationQueryAdmissionCoordinator _coordinator;
 21    private readonly NavigationAStarPayloadCache _cache;
 22    private readonly NavigationAStarQueryWork[] _queries;
 23    private readonly NavigationWorldGraphLease?[] _leases;
 24    private readonly NavigationAStarPayloadReservation[] _reservations;
 25    private readonly BatchDescriptor[] _descriptors;
 26    private ulong _generation;
 27    private ulong _activeGeneration;
 28    private NavigationQueryCapacityReservation _capacityReservation;
 29    private int _activeCount;
 30    private int _activeAdmittedCount;
 31    private int _nextAdmission;
 32    private int _nextPublication;
 33    private bool _active;
 34    private bool _disposed;
 35
 100636    internal NavigationAStarAdmissionGate(
 100637        GridWorld world,
 100638        NavigationWorldGraphStore store,
 100639        NavigationQueryLimits limits,
 100640        NavigationQueryAdmissionCoordinator coordinator)
 41    {
 100642        SwiftThrowHelper.ThrowIfNull(world, nameof(world));
 100643        SwiftThrowHelper.ThrowIfNull(store, nameof(store));
 100644        SwiftThrowHelper.ThrowIfNull(coordinator, nameof(coordinator));
 100645        SwiftThrowHelper.ThrowIfArgument(
 100646            limits.MaxConcurrentNavigationQueries <= 0,
 100647            nameof(limits),
 100648            "Query limits must be explicitly initialized.");
 100649        _store = store;
 100650        _limits = limits;
 100651        _coordinator = coordinator;
 100652        _cache = new NavigationAStarPayloadCache(
 100653            world,
 100654            limits.MaxAStarCacheEntries,
 100655            limits.MaxAStarReusablePayloadBytes,
 100656            limits.MaxAStarSinglePayloadBytes,
 100657            limits.MaxAStarActivePayloadBytes,
 100658            limits.MaxAStarActivePayloadLeases);
 100659        _queries = new NavigationAStarQueryWork[limits.MaxConcurrentNavigationQueries];
 100660        _leases = new NavigationWorldGraphLease[limits.MaxConcurrentNavigationQueries];
 100661        _reservations = new NavigationAStarPayloadReservation[limits.MaxConcurrentNavigationQueries];
 1762062        for (int i = 0; i < _queries.Length; i++)
 63        {
 780464            var workspace = new NavigationAStarWorkspace(
 780465                mapCapacity: limits.AStarWorkspaceMapCapacity,
 780466                endpointPageCapacity: limits.AStarWorkspaceEndpointPageCapacity,
 780467                componentCapacity: limits.AStarWorkspaceComponentCapacity,
 780468                nodeCapacity: limits.AStarWorkspaceNodeCapacity,
 780469                rayCoveredAddressCapacity: limits.RayWorkspaceCoveredAddressCapacity,
 780470                rayTraceIntervalCapacity: limits.RayWorkspaceTraceIntervalCapacity,
 780471                guidePointCapacity: limits.AStarWorkspaceGuidePointCapacity);
 780472            _queries[i] = new NavigationAStarQueryWork(world, store, workspace, _cache);
 73        }
 100674        _descriptors = new BatchDescriptor[limits.MaxBatchItems];
 100675    }
 76
 40377    internal NavigationAStarPayloadCache PayloadCache => _cache;
 78
 79    internal NavigationAStarQueryStatus Begin(
 80        PathQuery query,
 81        out NavigationAStarBatchWork work)
 82    {
 40483        lock (_sync)
 84        {
 40485            if (!CanBegin() || !FitsSingleEnvelope(query))
 86            {
 387                work = default;
 388                return NavigationAStarQueryStatus.CapacityExceeded;
 89            }
 40190            _descriptors[0] = new BatchDescriptor(0, 0, query);
 40191            return BeginCore(1, out work);
 92        }
 40493    }
 94
 95    internal NavigationAStarQueryStatus Begin(
 96        PathQueryBatch batch,
 97        out NavigationAStarBatchWork work)
 98    {
 1199        lock (_sync)
 100        {
 11101            if (!CanBegin() || !FitsBatchEnvelope(batch))
 102            {
 4103                work = default;
 4104                return NavigationAStarQueryStatus.CapacityExceeded;
 105            }
 40106            for (int i = 0; i < batch.Count; i++)
 107            {
 13108                PathQueryBatchItem item = batch.Items[i];
 13109                _descriptors[i] = new BatchDescriptor(item.StableOrdinal, i, item.Query);
 110            }
 7111            Array.Sort(_descriptors, 0, batch.Count);
 7112            return BeginCore(batch.Count, out work);
 113        }
 11114    }
 115
 116    public void Dispose()
 117    {
 1006118        NavigationAStarBatchWork active = default;
 1006119        lock (_sync)
 120        {
 1006121            if (_disposed)
 1122                return;
 1005123            _disposed = true;
 1005124            if (_active)
 1125                active = new NavigationAStarBatchWork(this, _activeGeneration);
 1005126        }
 1005127        active.Dispose();
 1006128    }
 129
 130    internal void CancelActive()
 131    {
 24132        NavigationAStarBatchWork active = default;
 24133        lock (_sync)
 134        {
 24135            if (_active)
 2136                active = new NavigationAStarBatchWork(this, _activeGeneration);
 24137        }
 24138        active.Dispose();
 24139    }
 140
 141    private bool CanBegin() =>
 415142        !_disposed
 415143        && !_active;
 144
 145    private bool FitsBatchEnvelope(PathQueryBatch batch) =>
 10146        batch.Count > 0
 10147        && batch.Count <= _limits.MaxBatchItems
 10148        && batch.GetLogicalRetainedBytes() <= _limits.MaxBatchDescriptorBytes;
 149
 150    private bool FitsSingleEnvelope(PathQuery query)
 151    {
 402152        return PathQueryBatchItem.GetLogicalRetainedBytes(query)
 402153            <= _limits.MaxBatchDescriptorBytes;
 154    }
 155
 156    private NavigationAStarQueryStatus BeginCore(
 157        int count,
 158        out NavigationAStarBatchWork work)
 159    {
 408160        int candidateCount = _coordinator.TryReservePrefix(
 408161            PathAlgorithm.AStar,
 408162            Math.Min(count, _queries.Length),
 408163            out _capacityReservation);
 408164        int leased = _store.TryAcquirePrefix(_leases.AsSpan(0, candidateCount));
 408165        _capacityReservation = _coordinator.Trim(_capacityReservation, leased);
 166
 408167        int admitted = 0;
 1226168        for (; admitted < leased; admitted++)
 169        {
 410170            PathQuery query = _descriptors[admitted].Query;
 410171            long maximumBytes = Math.Min(
 410172                NavigationAStarPayload.GetMaximumRetainedBytes(
 410173                    _limits.AStarWorkspaceGuidePointCapacity,
 410174                    query.AllowTransitions
 410175                        ? _limits.AStarWorkspaceNodeCapacity - 1
 410176                        : 0,
 410177                    _limits.AStarWorkspaceComponentCapacity,
 410178                    _limits.AStarWorkspaceEndpointPageCapacity),
 410179                _limits.MaxAStarSinglePayloadBytes);
 410180            if (!_cache.TryReservePayload(maximumBytes, out _reservations[admitted]))
 181                break;
 182        }
 820183        for (int i = admitted; i < leased; i++)
 184        {
 2185            _leases[i]!.Dispose();
 2186            _leases[i] = null;
 187        }
 408188        _capacityReservation = _coordinator.Trim(_capacityReservation, admitted);
 1634189        for (int i = 0; i < admitted; i++)
 190        {
 409191            _descriptors[i].SlotIndex = i;
 409192            _queries[i].BeginReserved(
 409193                _descriptors[i].Query,
 409194                _leases[i]!,
 409195                ref _reservations[i]);
 409196            _leases[i] = null;
 197        }
 408198        _generation = unchecked(_generation + 1UL);
 408199        _activeGeneration = _generation;
 408200        _activeCount = count;
 408201        _activeAdmittedCount = admitted;
 408202        _nextAdmission = 0;
 408203        _nextPublication = 0;
 408204        _active = true;
 408205        work = new NavigationAStarBatchWork(this, _activeGeneration);
 408206        return NavigationAStarQueryStatus.Pending;
 207    }
 208
 209    private BatchDescriptor GetDescriptor(int inputIndex)
 210    {
 1701211        SwiftThrowHelper.ThrowIfArgumentOutOfRange(
 1701212            inputIndex < 0 || inputIndex >= _activeCount,
 1701213            inputIndex,
 1701214            nameof(inputIndex));
 1699215        int descriptorOrdinal = 0;
 1761216        while (_descriptors[descriptorOrdinal].InputIndex != inputIndex)
 62217            descriptorOrdinal++;
 1699218        return _descriptors[descriptorOrdinal];
 219    }
 220
 221    internal int GetAdmittedCount(NavigationAStarBatchWork work)
 222    {
 5223        lock (_sync)
 224        {
 5225            EnsureActive(work);
 5226            return _activeAdmittedCount;
 227        }
 5228    }
 229
 230    internal bool IsAdmissionComplete(NavigationAStarBatchWork work)
 231    {
 944232        lock (_sync)
 233        {
 944234            EnsureActive(work);
 944235            return _nextAdmission >= _activeAdmittedCount;
 236        }
 944237    }
 238
 239    internal NavigationAStarQueryStatus GetStatus(
 240        NavigationAStarBatchWork work,
 241        int inputIndex)
 242    {
 402243        lock (_sync)
 244        {
 402245            EnsureActive(work);
 400246            BatchDescriptor descriptor = GetDescriptor(inputIndex);
 398247            if (descriptor.SlotIndex < 0)
 5248                return NavigationAStarQueryStatus.CapacityExceeded;
 393249            NavigationAStarQueryWork query = _queries[descriptor.SlotIndex];
 393250            lock (query)
 393251                return query.Status;
 252        }
 398253    }
 254
 255    internal bool IsReadyToPublish(
 256        NavigationAStarBatchWork work,
 257        int inputIndex)
 258    {
 666259        lock (_sync)
 260        {
 666261            EnsureActive(work);
 666262            BatchDescriptor descriptor = GetDescriptor(inputIndex);
 666263            return descriptor.SlotIndex < 0
 666264                || _queries[descriptor.SlotIndex].IsReadyToPublish;
 265        }
 666266    }
 267
 268    internal void AdvanceAdmission(
 269        NavigationAStarBatchWork work,
 270        int lookupStepLimit,
 271        int endpointCandidateStepLimit)
 272    {
 545273        lock (_sync)
 274        {
 545275            EnsureActive(work);
 937276            while (_nextAdmission < _activeAdmittedCount)
 277            {
 548278                NavigationAStarQueryWork query = _queries[_nextAdmission];
 548279                query.PrepareSearchOrCheckout(
 548280                    lookupStepLimit,
 548281                    endpointCandidateStepLimit);
 548282                if (!query.IsPrepared)
 156283                    return;
 392284                _nextAdmission++;
 285            }
 389286        }
 545287    }
 288
 289    internal NavigationAStarQueryStatus AdvanceSearch(
 290        NavigationAStarBatchWork work,
 291        int inputIndex,
 292        int lookupStepLimit,
 293        int nodeStepLimit,
 294        int edgeStepLimit,
 295        int connectionStepLimit)
 296    {
 297        BatchDescriptor descriptor;
 298        NavigationAStarQueryWork query;
 267299        lock (_sync)
 300        {
 267301            EnsureActive(work);
 266302            descriptor = GetDescriptor(inputIndex);
 266303            if (descriptor.SlotIndex < 0)
 1304                return NavigationAStarQueryStatus.CapacityExceeded;
 265305            query = _queries[descriptor.SlotIndex];
 265306            SwiftThrowHelper.ThrowIfTrue(
 265307                !query.IsPrepared,
 265308                message: "The query has not completed sequential admission.");
 264309            Monitor.Enter(query);
 264310        }
 311        try
 312        {
 264313            return query.AdvanceSearch(
 264314                lookupStepLimit,
 264315                nodeStepLimit,
 264316                edgeStepLimit,
 264317                connectionStepLimit);
 318        }
 319        finally
 320        {
 264321            Monitor.Exit(query);
 264322        }
 265323    }
 324
 325    internal int PublishReadyPrefix(
 326        NavigationAStarBatchWork work,
 327        int maximumCount)
 328    {
 391329        SwiftThrowHelper.ThrowIfNegative(maximumCount, nameof(maximumCount));
 391330        lock (_sync)
 331        {
 391332            EnsureActive(work);
 391333            int published = 0;
 782334            while (published < maximumCount
 782335                && _nextPublication < _activeAdmittedCount)
 336            {
 393337                NavigationAStarQueryWork query = _queries[_nextPublication];
 393338                lock (query)
 339                {
 393340                    if (!query.IsReadyToPublish)
 2341                        break;
 391342                    query.Publish();
 391343                }
 391344                _nextPublication++;
 391345                published++;
 346            }
 391347            return published;
 348        }
 391349    }
 350
 351    internal NavigationAStarPayloadLease TakeResult(
 352        NavigationAStarBatchWork work,
 353        int inputIndex)
 354    {
 369355        lock (_sync)
 356        {
 369357            EnsureActive(work);
 369358            BatchDescriptor descriptor = GetDescriptor(inputIndex);
 369359            SwiftThrowHelper.ThrowIfTrue(
 369360                descriptor.SlotIndex < 0,
 369361                message: "The query was not admitted.");
 368362            return _queries[descriptor.SlotIndex].TakeResult();
 363        }
 368364    }
 365
 366    internal void Release(NavigationAStarBatchWork work)
 367    {
 409368        lock (_sync)
 369        {
 409370            if (!IsActive(work))
 1371                return;
 1634372            for (int i = 0; i < _activeAdmittedCount; i++)
 373            {
 409374                lock (_queries[i])
 409375                    _queries[i].Dispose();
 376            }
 408377            _coordinator.Release(_capacityReservation);
 408378            _capacityReservation = default;
 408379            if (_activeCount > 0)
 408380                Array.Clear(_descriptors, 0, _activeCount);
 408381            _active = false;
 408382            _activeGeneration = 0;
 408383            _activeCount = 0;
 408384            _activeAdmittedCount = 0;
 408385            _nextAdmission = 0;
 408386            _nextPublication = 0;
 408387        }
 409388    }
 389
 390    private void EnsureActive(NavigationAStarBatchWork work)
 391    {
 3589392        if (!IsActive(work))
 3393            throw new ObjectDisposedException(nameof(NavigationAStarBatchWork));
 3586394    }
 395
 396    private bool IsActive(NavigationAStarBatchWork work) =>
 3998397        _active
 3998398        && work.IsOwnedBy(this)
 3998399        && work.Generation == _activeGeneration;
 400
 401    private struct BatchDescriptor : IComparable<BatchDescriptor>
 402    {
 403        internal BatchDescriptor(long stableOrdinal, int inputIndex, PathQuery query)
 404        {
 414405            StableOrdinal = stableOrdinal;
 414406            InputIndex = inputIndex;
 414407            Query = query;
 414408            SlotIndex = -1;
 414409        }
 410
 411        internal long StableOrdinal;
 412        internal int InputIndex;
 413        internal PathQuery Query;
 414        internal int SlotIndex;
 415
 416        public readonly int CompareTo(BatchDescriptor other)
 417        {
 7418            int ordinalComparison = StableOrdinal.CompareTo(other.StableOrdinal);
 7419            return ordinalComparison != 0
 7420                ? ordinalComparison
 7421                : InputIndex.CompareTo(other.InputIndex);
 422        }
 423    }
 424}
 425
 426/// <summary>Coordinates one deterministically admitted A* query batch.</summary>
 427internal readonly struct NavigationAStarBatchWork : IDisposable
 428{
 429    private readonly NavigationAStarAdmissionGate? _owner;
 430
 431    internal NavigationAStarBatchWork(
 432        NavigationAStarAdmissionGate owner,
 433        ulong generation)
 434    {
 435        _owner = owner;
 436        Generation = generation;
 437    }
 438
 439    internal ulong Generation { get; }
 440
 441    internal int AdmittedCount => Owner.GetAdmittedCount(this);
 442
 443    internal bool IsAdmissionComplete => Owner.IsAdmissionComplete(this);
 444
 445    internal NavigationAStarQueryStatus GetStatus(int inputIndex) =>
 446        Owner.GetStatus(this, inputIndex);
 447
 448    internal bool IsReadyToPublish(int inputIndex) =>
 449        Owner.IsReadyToPublish(this, inputIndex);
 450
 451    internal void AdvanceAdmission(int lookupStepLimit, int endpointCandidateStepLimit) =>
 452        Owner.AdvanceAdmission(this, lookupStepLimit, endpointCandidateStepLimit);
 453
 454    internal NavigationAStarQueryStatus AdvanceSearch(
 455        int inputIndex,
 456        int lookupStepLimit,
 457        int nodeStepLimit,
 458        int edgeStepLimit,
 459        int connectionStepLimit) => Owner.AdvanceSearch(
 460            this,
 461            inputIndex,
 462            lookupStepLimit,
 463            nodeStepLimit,
 464            edgeStepLimit,
 465            connectionStepLimit);
 466
 467    internal int PublishReadyPrefix(int maximumCount) =>
 468        Owner.PublishReadyPrefix(this, maximumCount);
 469
 470    internal NavigationAStarPayloadLease TakeResult(int inputIndex) =>
 471        Owner.TakeResult(this, inputIndex);
 472
 473    public void Dispose() => _owner?.Release(this);
 474
 475    internal bool IsOwnedBy(NavigationAStarAdmissionGate owner) =>
 476        ReferenceEquals(_owner, owner);
 477
 478    private NavigationAStarAdmissionGate Owner =>
 479        _owner ?? throw new ObjectDisposedException(nameof(NavigationAStarBatchWork));
 480}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

.ctor(GridForge.Grids.GridWorld,Trailblazer.Pathing.NavigationWorldGraphStore,Trailblazer.Pathing.NavigationQueryLimits,Trailblazer.Pathing.NavigationQueryAdmissionCoordinator)
get_PayloadCache()
Begin(Trailblazer.Pathing.PathQuery,Trailblazer.Pathing.NavigationAStarBatchWork&)
Begin(Trailblazer.Pathing.PathQueryBatch,Trailblazer.Pathing.NavigationAStarBatchWork&)
Dispose()
CancelActive()
CanBegin()
FitsBatchEnvelope(Trailblazer.Pathing.PathQueryBatch)
FitsSingleEnvelope(Trailblazer.Pathing.PathQuery)
BeginCore(System.Int32,Trailblazer.Pathing.NavigationAStarBatchWork&)
GetDescriptor(System.Int32)
GetAdmittedCount(Trailblazer.Pathing.NavigationAStarBatchWork)
IsAdmissionComplete(Trailblazer.Pathing.NavigationAStarBatchWork)
GetStatus(Trailblazer.Pathing.NavigationAStarBatchWork,System.Int32)
IsReadyToPublish(Trailblazer.Pathing.NavigationAStarBatchWork,System.Int32)
AdvanceAdmission(Trailblazer.Pathing.NavigationAStarBatchWork,System.Int32,System.Int32)
AdvanceSearch(Trailblazer.Pathing.NavigationAStarBatchWork,System.Int32,System.Int32,System.Int32,System.Int32,System.Int32)
PublishReadyPrefix(Trailblazer.Pathing.NavigationAStarBatchWork,System.Int32)
TakeResult(Trailblazer.Pathing.NavigationAStarBatchWork,System.Int32)
Release(Trailblazer.Pathing.NavigationAStarBatchWork)
EnsureActive(Trailblazer.Pathing.NavigationAStarBatchWork)
IsActive(Trailblazer.Pathing.NavigationAStarBatchWork)
.ctor(System.Int64,System.Int32,Trailblazer.Pathing.PathQuery)
CompareTo(Trailblazer.Pathing.NavigationAStarAdmissionGate/BatchDescriptor)