| | | 1 | | //======================================================================= |
| | | 2 | | // NavigationQueryAdmissionCoordinator.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 | | |
| | | 8 | | using System; |
| | | 9 | | |
| | | 10 | | namespace Trailblazer.Pathing; |
| | | 11 | | |
| | | 12 | | /// <summary>Identifies one generation-safe aggregate query-capacity reservation.</summary> |
| | | 13 | | internal readonly struct NavigationQueryCapacityReservation |
| | | 14 | | { |
| | | 15 | | internal NavigationQueryCapacityReservation( |
| | | 16 | | NavigationQueryAdmissionCoordinator owner, |
| | | 17 | | int lane, |
| | | 18 | | ulong generation, |
| | | 19 | | int count) |
| | | 20 | | { |
| | 1333 | 21 | | Owner = owner; |
| | 1333 | 22 | | Lane = lane; |
| | 1333 | 23 | | Generation = generation; |
| | 1333 | 24 | | Count = count; |
| | 1333 | 25 | | } |
| | | 26 | | |
| | | 27 | | internal NavigationQueryAdmissionCoordinator? Owner { get; } |
| | | 28 | | internal int Lane { get; } |
| | | 29 | | internal ulong Generation { get; } |
| | | 30 | | internal int Count { get; } |
| | | 31 | | } |
| | | 32 | | |
| | | 33 | | /// <summary>Bounds aggregate A* and Flow admission without sharing their workers.</summary> |
| | | 34 | | internal sealed class NavigationQueryAdmissionCoordinator |
| | | 35 | | { |
| | | 36 | | private readonly object _sync = new(); |
| | | 37 | | private readonly LaneState[] _lanes = new LaneState[2]; |
| | | 38 | | private readonly int _maximumCount; |
| | | 39 | | private int _activeCount; |
| | | 40 | | |
| | | 41 | | internal NavigationQueryAdmissionCoordinator(int maximumCount) |
| | | 42 | | { |
| | | 43 | | SwiftThrowHelper.ThrowIfArgumentOutOfRange( |
| | | 44 | | maximumCount <= 0, |
| | | 45 | | maximumCount, |
| | | 46 | | nameof(maximumCount)); |
| | | 47 | | _maximumCount = maximumCount; |
| | | 48 | | } |
| | | 49 | | |
| | | 50 | | internal int ActiveCount |
| | | 51 | | { |
| | | 52 | | get |
| | | 53 | | { |
| | | 54 | | lock (_sync) |
| | | 55 | | return _activeCount; |
| | | 56 | | } |
| | | 57 | | } |
| | | 58 | | |
| | | 59 | | internal int TryReservePrefix( |
| | | 60 | | PathAlgorithm algorithm, |
| | | 61 | | int requestedCount, |
| | | 62 | | out NavigationQueryCapacityReservation reservation) |
| | | 63 | | { |
| | | 64 | | SwiftThrowHelper.ThrowIfNegative(requestedCount, nameof(requestedCount)); |
| | | 65 | | int lane = GetLane(algorithm); |
| | | 66 | | lock (_sync) |
| | | 67 | | { |
| | | 68 | | ref LaneState state = ref _lanes[lane]; |
| | | 69 | | int count = Math.Min(requestedCount, _maximumCount - _activeCount); |
| | | 70 | | if (requestedCount == 0 |
| | | 71 | | || state.Active |
| | | 72 | | || count == 0) |
| | | 73 | | { |
| | | 74 | | reservation = default; |
| | | 75 | | return 0; |
| | | 76 | | } |
| | | 77 | | state.Generation = unchecked(state.Generation + 1UL); |
| | | 78 | | state.Count = count; |
| | | 79 | | state.Active = true; |
| | | 80 | | _activeCount += count; |
| | | 81 | | reservation = new NavigationQueryCapacityReservation( |
| | | 82 | | this, |
| | | 83 | | lane, |
| | | 84 | | state.Generation, |
| | | 85 | | count); |
| | | 86 | | return count; |
| | | 87 | | } |
| | | 88 | | } |
| | | 89 | | |
| | | 90 | | internal NavigationQueryCapacityReservation Trim( |
| | | 91 | | NavigationQueryCapacityReservation reservation, |
| | | 92 | | int retainedCount) |
| | | 93 | | { |
| | | 94 | | lock (_sync) |
| | | 95 | | { |
| | | 96 | | if (!TryGetActiveLane(reservation, out int lane)) |
| | | 97 | | return default; |
| | | 98 | | ref LaneState state = ref _lanes[lane]; |
| | | 99 | | _activeCount -= state.Count - retainedCount; |
| | | 100 | | state.Count = retainedCount; |
| | | 101 | | if (retainedCount == 0) |
| | | 102 | | { |
| | | 103 | | state.Active = false; |
| | | 104 | | return default; |
| | | 105 | | } |
| | | 106 | | return new NavigationQueryCapacityReservation( |
| | | 107 | | this, |
| | | 108 | | lane, |
| | | 109 | | state.Generation, |
| | | 110 | | retainedCount); |
| | | 111 | | } |
| | | 112 | | } |
| | | 113 | | |
| | | 114 | | internal void Release(NavigationQueryCapacityReservation reservation) |
| | | 115 | | { |
| | | 116 | | lock (_sync) |
| | | 117 | | { |
| | | 118 | | if (!TryGetActiveLane(reservation, out int lane)) |
| | | 119 | | return; |
| | | 120 | | ref LaneState state = ref _lanes[lane]; |
| | | 121 | | _activeCount -= state.Count; |
| | | 122 | | state.Count = 0; |
| | | 123 | | state.Active = false; |
| | | 124 | | } |
| | | 125 | | } |
| | | 126 | | |
| | | 127 | | private bool TryGetActiveLane( |
| | | 128 | | NavigationQueryCapacityReservation reservation, |
| | | 129 | | out int lane) |
| | | 130 | | { |
| | | 131 | | lane = reservation.Lane; |
| | | 132 | | return ReferenceEquals(reservation.Owner, this) |
| | | 133 | | && (uint)lane < (uint)_lanes.Length |
| | | 134 | | && _lanes[lane].Active |
| | | 135 | | && _lanes[lane].Generation == reservation.Generation |
| | | 136 | | && _lanes[lane].Count == reservation.Count; |
| | | 137 | | } |
| | | 138 | | |
| | | 139 | | private static int GetLane(PathAlgorithm algorithm) => |
| | | 140 | | algorithm == PathAlgorithm.AStar ? 0 : 1; |
| | | 141 | | |
| | | 142 | | private struct LaneState |
| | | 143 | | { |
| | | 144 | | internal ulong Generation; |
| | | 145 | | internal int Count; |
| | | 146 | | internal bool Active; |
| | | 147 | | } |
| | | 148 | | } |