| | | 1 | | //======================================================================= |
| | | 2 | | // NavigationAStarPayloadCache.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 | | using GridForge.Grids; |
| | | 10 | | |
| | | 11 | | namespace Trailblazer.Pathing; |
| | | 12 | | |
| | | 13 | | internal struct NavigationAStarPayloadReservation |
| | | 14 | | { |
| | | 15 | | internal NavigationAStarPayloadReservation( |
| | | 16 | | NavigationAStarPayloadCache owner, |
| | | 17 | | NavigationAStarPayloadReservationSlot slot, |
| | | 18 | | ulong generation, |
| | | 19 | | long maximumBytes) |
| | | 20 | | { |
| | | 21 | | Owner = owner; |
| | | 22 | | Slot = slot; |
| | | 23 | | Generation = generation; |
| | | 24 | | MaximumBytes = maximumBytes; |
| | | 25 | | } |
| | | 26 | | |
| | | 27 | | internal readonly NavigationAStarPayloadCache? Owner; |
| | | 28 | | internal readonly NavigationAStarPayloadReservationSlot? Slot; |
| | | 29 | | internal readonly ulong Generation; |
| | | 30 | | internal readonly long MaximumBytes; |
| | | 31 | | internal readonly bool HasLeaseSlot => Owner != null; |
| | | 32 | | } |
| | | 33 | | |
| | | 34 | | internal sealed class NavigationAStarPayloadReservationSlot |
| | | 35 | | { |
| | | 36 | | internal ulong Generation; |
| | | 37 | | internal long MaximumBytes; |
| | | 38 | | internal bool IsReserved; |
| | | 39 | | internal NavigationAStarPayloadReservationSlot? NextPooled; |
| | | 40 | | } |
| | | 41 | | |
| | | 42 | | /// <summary>Stores a bounded concrete set of dependency-validated A* payloads.</summary> |
| | | 43 | | internal sealed class NavigationAStarPayloadCache |
| | | 44 | | { |
| | 1052 | 45 | | private readonly object _sync = new(); |
| | | 46 | | private readonly GridWorld _world; |
| | | 47 | | private readonly NavigationAStarPayloadKey[] _keys; |
| | | 48 | | private readonly CacheEntry?[] _entries; |
| | | 49 | | private readonly byte[] _states; |
| | | 50 | | private readonly int[] _previous; |
| | | 51 | | private readonly int[] _next; |
| | | 52 | | private readonly int _mask; |
| | | 53 | | private readonly int _maximumEntries; |
| | | 54 | | private readonly long _maximumReusableBytes; |
| | | 55 | | private readonly long _maximumSinglePayloadBytes; |
| | | 56 | | private readonly long _maximumActivePayloadBytes; |
| | | 57 | | private readonly int _maximumActiveLeases; |
| | 1052 | 58 | | private int _leastRecent = -1; |
| | 1052 | 59 | | private int _mostRecent = -1; |
| | | 60 | | private int _count; |
| | | 61 | | private int _activeLeaseCount; |
| | | 62 | | private int _reservedLeaseCount; |
| | | 63 | | private long _cachedBytes; |
| | | 64 | | private long _leasedBytes; |
| | | 65 | | private long _detachedBytes; |
| | | 66 | | private long _reservedPayloadBytes; |
| | | 67 | | private NavigationAStarPayloadLease? _freeLeases; |
| | | 68 | | private NavigationAStarGuideLease? _freeGuides; |
| | | 69 | | private NavigationAStarPayloadReservationSlot? _freeReservationSlots; |
| | | 70 | | |
| | 1052 | 71 | | internal NavigationAStarPayloadCache( |
| | 1052 | 72 | | GridWorld world, |
| | 1052 | 73 | | int maxEntries, |
| | 1052 | 74 | | long maxReusableBytes = long.MaxValue, |
| | 1052 | 75 | | long maxSinglePayloadBytes = long.MaxValue, |
| | 1052 | 76 | | long maxActivePayloadBytes = long.MaxValue, |
| | 1052 | 77 | | int maxActiveLeases = int.MaxValue) |
| | | 78 | | { |
| | 1052 | 79 | | SwiftThrowHelper.ThrowIfNull(world, nameof(world)); |
| | 1052 | 80 | | SwiftThrowHelper.ThrowIfNegative(maxEntries, nameof(maxEntries)); |
| | 1052 | 81 | | if (maxReusableBytes < 0) |
| | 1 | 82 | | throw new ArgumentOutOfRangeException(nameof(maxReusableBytes)); |
| | 1051 | 83 | | if (maxSinglePayloadBytes < 0) |
| | 1 | 84 | | throw new ArgumentOutOfRangeException(nameof(maxSinglePayloadBytes)); |
| | 1050 | 85 | | if (maxActivePayloadBytes < 0) |
| | 1 | 86 | | throw new ArgumentOutOfRangeException(nameof(maxActivePayloadBytes)); |
| | 1049 | 87 | | SwiftThrowHelper.ThrowIfNegative(maxActiveLeases, nameof(maxActiveLeases)); |
| | 1049 | 88 | | SwiftThrowHelper.ThrowIfArgument( |
| | 1049 | 89 | | maxSinglePayloadBytes > maxActivePayloadBytes, |
| | 1049 | 90 | | nameof(maxSinglePayloadBytes), |
| | 1049 | 91 | | "A single payload cannot exceed the complete active-payload byte ceiling."); |
| | 1049 | 92 | | int tableSize = 1; |
| | 1049 | 93 | | int required = checked(Math.Max(1, maxEntries * 2)); |
| | 9057 | 94 | | while (tableSize < required) |
| | 8008 | 95 | | tableSize = checked(tableSize * 2); |
| | 1049 | 96 | | _world = world; |
| | 1049 | 97 | | _keys = new NavigationAStarPayloadKey[tableSize]; |
| | 1049 | 98 | | _entries = new CacheEntry[tableSize]; |
| | 1049 | 99 | | _states = new byte[tableSize]; |
| | 1049 | 100 | | _previous = new int[tableSize]; |
| | 1049 | 101 | | _next = new int[tableSize]; |
| | 1049 | 102 | | Array.Fill(_previous, -1); |
| | 1049 | 103 | | Array.Fill(_next, -1); |
| | 1049 | 104 | | _mask = tableSize - 1; |
| | 1049 | 105 | | _maximumEntries = maxEntries; |
| | 1049 | 106 | | _maximumReusableBytes = maxReusableBytes; |
| | 1049 | 107 | | _maximumSinglePayloadBytes = maxSinglePayloadBytes; |
| | 1049 | 108 | | _maximumActivePayloadBytes = maxActivePayloadBytes; |
| | 1049 | 109 | | _maximumActiveLeases = maxActiveLeases; |
| | 1049 | 110 | | } |
| | | 111 | | |
| | | 112 | | internal long CachedBytes |
| | | 113 | | { |
| | | 114 | | get |
| | | 115 | | { |
| | 68 | 116 | | lock (_sync) |
| | 68 | 117 | | return _cachedBytes; |
| | 68 | 118 | | } |
| | | 119 | | } |
| | | 120 | | |
| | | 121 | | internal long LeasedBytes |
| | | 122 | | { |
| | | 123 | | get |
| | | 124 | | { |
| | 8 | 125 | | lock (_sync) |
| | 8 | 126 | | return _leasedBytes; |
| | 8 | 127 | | } |
| | | 128 | | } |
| | | 129 | | |
| | | 130 | | internal long DetachedBytes |
| | | 131 | | { |
| | | 132 | | get |
| | | 133 | | { |
| | 7 | 134 | | lock (_sync) |
| | 7 | 135 | | return _detachedBytes; |
| | 7 | 136 | | } |
| | | 137 | | } |
| | | 138 | | |
| | | 139 | | internal int Count |
| | | 140 | | { |
| | | 141 | | get |
| | | 142 | | { |
| | 81 | 143 | | lock (_sync) |
| | 81 | 144 | | return _count; |
| | 81 | 145 | | } |
| | | 146 | | } |
| | | 147 | | |
| | | 148 | | internal int ActiveLeaseCount |
| | | 149 | | { |
| | | 150 | | get |
| | | 151 | | { |
| | 60 | 152 | | lock (_sync) |
| | 60 | 153 | | return _activeLeaseCount; |
| | 60 | 154 | | } |
| | | 155 | | } |
| | | 156 | | |
| | | 157 | | internal int ReservedLeaseCount |
| | | 158 | | { |
| | | 159 | | get |
| | | 160 | | { |
| | 33 | 161 | | lock (_sync) |
| | 33 | 162 | | return _reservedLeaseCount; |
| | 33 | 163 | | } |
| | | 164 | | } |
| | | 165 | | |
| | | 166 | | internal long ReservedPayloadBytes |
| | | 167 | | { |
| | | 168 | | get |
| | | 169 | | { |
| | 14 | 170 | | lock (_sync) |
| | 14 | 171 | | return _reservedPayloadBytes; |
| | 14 | 172 | | } |
| | | 173 | | } |
| | | 174 | | |
| | 127 | 175 | | internal GridWorld World => _world; |
| | | 176 | | |
| | | 177 | | internal bool IsWorldCurrent(NavigationAStarPayload payload) => |
| | 9766 | 178 | | payload.WorldChangeSequence is not ulong sequence |
| | 9766 | 179 | | || _world.ChangeSequence == sequence; |
| | | 180 | | |
| | | 181 | | internal NavigationAStarQueryStatus TryCreateGuide( |
| | | 182 | | NavigationWorldGraphStore store, |
| | | 183 | | NavigationAStarPayloadLease payloadLease, |
| | | 184 | | out NavigationAStarGuideLease? guide) |
| | | 185 | | { |
| | 633 | 186 | | SwiftThrowHelper.ThrowIfNull(store, nameof(store)); |
| | 633 | 187 | | SwiftThrowHelper.ThrowIfNull(payloadLease, nameof(payloadLease)); |
| | 633 | 188 | | NavigationAStarPayload payload = payloadLease.Payload; |
| | 633 | 189 | | if (!payload.HasPath) |
| | | 190 | | { |
| | 1 | 191 | | payloadLease.Dispose(); |
| | 1 | 192 | | guide = null; |
| | 1 | 193 | | return NavigationAStarQueryStatus.NoPath; |
| | | 194 | | } |
| | 632 | 195 | | NavigationWorldGraphLease? graphLease = store.TryAcquire(); |
| | 632 | 196 | | if (graphLease == null) |
| | | 197 | | { |
| | 2 | 198 | | payloadLease.Dispose(); |
| | 2 | 199 | | guide = null; |
| | 2 | 200 | | return NavigationAStarQueryStatus.CapacityExceeded; |
| | | 201 | | } |
| | 630 | 202 | | using (graphLease) |
| | | 203 | | { |
| | 630 | 204 | | if (!graphLease.Graph.IsDependencyCurrent(payload.Dependencies) |
| | 630 | 205 | | || !store.Current.IsDependencyCurrent(payload.Dependencies) |
| | 630 | 206 | | || !IsWorldCurrent(payload)) |
| | | 207 | | { |
| | 2 | 208 | | payloadLease.Dispose(); |
| | 2 | 209 | | guide = null; |
| | 2 | 210 | | return NavigationAStarQueryStatus.Stale; |
| | | 211 | | } |
| | 628 | 212 | | } |
| | 628 | 213 | | lock (_sync) |
| | | 214 | | { |
| | 628 | 215 | | guide = _freeGuides; |
| | 628 | 216 | | if (guide == null) |
| | 73 | 217 | | guide = new NavigationAStarGuideLease(this); |
| | | 218 | | else |
| | | 219 | | { |
| | 555 | 220 | | _freeGuides = guide.NextPooled; |
| | 555 | 221 | | guide.NextPooled = null; |
| | | 222 | | } |
| | 555 | 223 | | } |
| | 628 | 224 | | guide.Bind(store, payloadLease); |
| | 628 | 225 | | return NavigationAStarQueryStatus.Success; |
| | 2 | 226 | | } |
| | | 227 | | |
| | | 228 | | internal NavigationGuideStatus TryCreatePublicGuide( |
| | | 229 | | NavigationWorldGraphStore store, |
| | | 230 | | NavigationAStarPayloadLease payloadLease, |
| | | 231 | | out NavigationGuideLease? guide) |
| | | 232 | | { |
| | 358 | 233 | | NavigationAStarQueryStatus status = TryCreateGuide( |
| | 358 | 234 | | store, |
| | 358 | 235 | | payloadLease, |
| | 358 | 236 | | out NavigationAStarGuideLease? inner); |
| | 358 | 237 | | if (status != NavigationAStarQueryStatus.Success) |
| | | 238 | | { |
| | 1 | 239 | | guide = null; |
| | 1 | 240 | | return NavigationGuideStatusMapper.ToPublic(status); |
| | | 241 | | } |
| | 357 | 242 | | guide = new NavigationGuideLease(inner!); |
| | 357 | 243 | | return NavigationGuideStatus.Success; |
| | | 244 | | } |
| | | 245 | | |
| | | 246 | | internal bool TryReservePayload( |
| | | 247 | | long maximumBytes, |
| | | 248 | | out NavigationAStarPayloadReservation reservation) |
| | | 249 | | { |
| | 1158 | 250 | | if (maximumBytes < 0) |
| | 1 | 251 | | throw new ArgumentOutOfRangeException(nameof(maximumBytes)); |
| | 1157 | 252 | | reservation = default; |
| | 1157 | 253 | | if (maximumBytes > _maximumSinglePayloadBytes) |
| | 4 | 254 | | return false; |
| | 1153 | 255 | | lock (_sync) |
| | | 256 | | { |
| | 1153 | 257 | | if (_activeLeaseCount + _reservedLeaseCount >= _maximumActiveLeases |
| | 1153 | 258 | | || maximumBytes > _maximumActivePayloadBytes |
| | 1153 | 259 | | - _leasedBytes |
| | 1153 | 260 | | - _reservedPayloadBytes) |
| | | 261 | | { |
| | 5 | 262 | | return false; |
| | | 263 | | } |
| | 1148 | 264 | | _reservedPayloadBytes = checked(_reservedPayloadBytes + maximumBytes); |
| | 1148 | 265 | | _reservedLeaseCount++; |
| | 1148 | 266 | | NavigationAStarPayloadReservationSlot? slot = _freeReservationSlots; |
| | 1148 | 267 | | if (slot == null) |
| | | 268 | | { |
| | 122 | 269 | | slot = new NavigationAStarPayloadReservationSlot(); |
| | | 270 | | } |
| | | 271 | | else |
| | | 272 | | { |
| | 1026 | 273 | | _freeReservationSlots = slot.NextPooled; |
| | 1026 | 274 | | slot.NextPooled = null; |
| | | 275 | | } |
| | 1148 | 276 | | slot.Generation = unchecked(slot.Generation + 1UL); |
| | 1148 | 277 | | slot.MaximumBytes = maximumBytes; |
| | 1148 | 278 | | slot.IsReserved = true; |
| | 1148 | 279 | | reservation = new NavigationAStarPayloadReservation( |
| | 1148 | 280 | | this, |
| | 1148 | 281 | | slot, |
| | 1148 | 282 | | slot.Generation, |
| | 1148 | 283 | | maximumBytes); |
| | 1148 | 284 | | return true; |
| | | 285 | | } |
| | 1153 | 286 | | } |
| | | 287 | | |
| | | 288 | | internal void ReleasePayloadReservation( |
| | | 289 | | ref NavigationAStarPayloadReservation reservation) |
| | | 290 | | { |
| | 1480 | 291 | | if (reservation.Owner == null) |
| | | 292 | | { |
| | 1422 | 293 | | reservation = default; |
| | 1422 | 294 | | return; |
| | | 295 | | } |
| | 58 | 296 | | if (!ReferenceEquals(reservation.Owner, this)) |
| | 1 | 297 | | return; |
| | 57 | 298 | | NavigationAStarPayloadReservation released = reservation; |
| | 57 | 299 | | reservation = default; |
| | 57 | 300 | | lock (_sync) |
| | | 301 | | { |
| | 57 | 302 | | if (IsReservationCurrentUnderLock(released)) |
| | 55 | 303 | | ReleasePayloadReservationUnderLock(released); |
| | 57 | 304 | | } |
| | 57 | 305 | | } |
| | | 306 | | |
| | | 307 | | internal bool TryCheckoutReserved( |
| | | 308 | | NavigationAStarPayloadKey key, |
| | | 309 | | NavigationWorldGraph graph, |
| | | 310 | | ref NavigationAStarPayloadReservation reservation, |
| | | 311 | | out NavigationAStarPayloadLease lease) |
| | | 312 | | { |
| | 1022 | 313 | | SwiftThrowHelper.ThrowIfNull(graph, nameof(graph)); |
| | 1022 | 314 | | lease = null!; |
| | 1022 | 315 | | lock (_sync) |
| | | 316 | | { |
| | 1022 | 317 | | if (!IsReservationCurrentUnderLock(reservation)) |
| | 1 | 318 | | return false; |
| | 1021 | 319 | | FindSlot(key, out int slot, out bool found); |
| | 1021 | 320 | | if (!found) |
| | 111 | 321 | | return false; |
| | 910 | 322 | | CacheEntry current = _entries[slot]!; |
| | 910 | 323 | | if (!graph.IsDependencyCurrent(current.Payload.Dependencies) |
| | 910 | 324 | | || !IsWorldCurrent(current.Payload)) |
| | | 325 | | { |
| | 22 | 326 | | RemoveAt(slot); |
| | 22 | 327 | | return false; |
| | | 328 | | } |
| | 888 | 329 | | long otherReservations = |
| | 888 | 330 | | _reservedPayloadBytes - reservation.MaximumBytes; |
| | 888 | 331 | | if (current.Payload.RetainedBytes > reservation.MaximumBytes |
| | 888 | 332 | | || (current.LeaseCount == 0 |
| | 888 | 333 | | && current.Payload.RetainedBytes > _maximumActivePayloadBytes |
| | 888 | 334 | | - _leasedBytes |
| | 888 | 335 | | - otherReservations)) |
| | | 336 | | { |
| | 1 | 337 | | return false; |
| | | 338 | | } |
| | 887 | 339 | | ReleasePayloadReservationUnderLock(reservation); |
| | 887 | 340 | | reservation = default; |
| | 887 | 341 | | lease = Checkout(current); |
| | 887 | 342 | | Touch(slot); |
| | 887 | 343 | | return true; |
| | | 344 | | } |
| | 1022 | 345 | | } |
| | | 346 | | |
| | | 347 | | internal bool TryPublish( |
| | | 348 | | NavigationAStarPayload payload, |
| | | 349 | | NavigationWorldGraphStore store, |
| | | 350 | | ref NavigationAStarPayloadReservation reservation, |
| | | 351 | | out NavigationAStarPayloadLease lease) |
| | | 352 | | { |
| | 213 | 353 | | SwiftThrowHelper.ThrowIfNull(payload, nameof(payload)); |
| | 213 | 354 | | SwiftThrowHelper.ThrowIfNull(store, nameof(store)); |
| | 213 | 355 | | lease = null!; |
| | 213 | 356 | | long retainedBytes = payload.RetainedBytes; |
| | 213 | 357 | | if (!ReferenceEquals(reservation.Owner, this) |
| | 213 | 358 | | || retainedBytes > reservation.MaximumBytes) |
| | | 359 | | { |
| | 1 | 360 | | return false; |
| | | 361 | | } |
| | 212 | 362 | | lock (_sync) |
| | | 363 | | { |
| | 212 | 364 | | if (!IsReservationCurrentUnderLock(reservation)) |
| | 1 | 365 | | return false; |
| | 211 | 366 | | NavigationWorldGraph graph = store.Current; |
| | 211 | 367 | | if (!graph.IsDependencyCurrent(payload.Dependencies) |
| | 211 | 368 | | || !IsWorldCurrent(payload)) |
| | 4 | 369 | | return false; |
| | 207 | 370 | | long otherReservations = |
| | 207 | 371 | | _reservedPayloadBytes - reservation.MaximumBytes; |
| | 207 | 372 | | FindSlot(payload.Key, out int slot, out bool found); |
| | 207 | 373 | | if (found) |
| | | 374 | | { |
| | 7 | 375 | | CacheEntry current = _entries[slot]!; |
| | 7 | 376 | | if (graph.IsDependencyCurrent(current.Payload.Dependencies) |
| | 7 | 377 | | && IsWorldCurrent(current.Payload)) |
| | | 378 | | { |
| | 6 | 379 | | if (current.LeaseCount == 0 |
| | 6 | 380 | | && current.Payload.RetainedBytes > _maximumActivePayloadBytes |
| | 6 | 381 | | - _leasedBytes |
| | 6 | 382 | | - otherReservations) |
| | | 383 | | { |
| | 1 | 384 | | return false; |
| | | 385 | | } |
| | 5 | 386 | | ReleasePayloadReservationUnderLock(reservation); |
| | 5 | 387 | | reservation = default; |
| | 5 | 388 | | lease = Checkout(current); |
| | 5 | 389 | | Touch(slot); |
| | 5 | 390 | | return true; |
| | | 391 | | } |
| | 1 | 392 | | RemoveAt(slot); |
| | | 393 | | } |
| | | 394 | | |
| | 201 | 395 | | if (_maximumEntries == 0 || retainedBytes > _maximumReusableBytes) |
| | | 396 | | { |
| | 2 | 397 | | var detached = new CacheEntry(payload, isCached: false); |
| | 2 | 398 | | _detachedBytes = checked(_detachedBytes + retainedBytes); |
| | 2 | 399 | | ReleasePayloadReservationUnderLock(reservation); |
| | 2 | 400 | | reservation = default; |
| | 2 | 401 | | lease = Checkout(detached); |
| | 2 | 402 | | return true; |
| | | 403 | | } |
| | | 404 | | |
| | 265 | 405 | | while (_count >= _maximumEntries |
| | 265 | 406 | | || retainedBytes > _maximumReusableBytes - _cachedBytes) |
| | 66 | 407 | | RemoveAt(_leastRecent); |
| | | 408 | | |
| | 199 | 409 | | FindSlot(payload.Key, out slot, out found); |
| | 199 | 410 | | var entry = new CacheEntry(payload, isCached: true); |
| | 199 | 411 | | _states[slot] = 1; |
| | 199 | 412 | | _keys[slot] = payload.Key; |
| | 199 | 413 | | _entries[slot] = entry; |
| | 199 | 414 | | LinkMostRecent(slot); |
| | 199 | 415 | | _count++; |
| | 199 | 416 | | _cachedBytes = checked(_cachedBytes + retainedBytes); |
| | 199 | 417 | | ReleasePayloadReservationUnderLock(reservation); |
| | 199 | 418 | | reservation = default; |
| | 199 | 419 | | lease = Checkout(entry); |
| | 199 | 420 | | return true; |
| | | 421 | | } |
| | 212 | 422 | | } |
| | | 423 | | |
| | | 424 | | internal void RemoveExact(NavigationAStarPayload payload) |
| | | 425 | | { |
| | 1 | 426 | | SwiftThrowHelper.ThrowIfNull(payload, nameof(payload)); |
| | 1 | 427 | | lock (_sync) |
| | | 428 | | { |
| | 1 | 429 | | FindSlot(payload.Key, out int slot, out bool found); |
| | 1 | 430 | | if (found && ReferenceEquals(_entries[slot]!.Payload, payload)) |
| | 1 | 431 | | RemoveAt(slot); |
| | 1 | 432 | | } |
| | 1 | 433 | | } |
| | | 434 | | |
| | | 435 | | internal void Return(NavigationAStarPayloadLease lease) |
| | | 436 | | { |
| | 1074 | 437 | | CacheEntry? entry = lease.DetachEntry(); |
| | 1074 | 438 | | if (entry == null) |
| | 1 | 439 | | return; |
| | 1073 | 440 | | lock (_sync) |
| | | 441 | | { |
| | 1073 | 442 | | entry.LeaseCount--; |
| | 1073 | 443 | | _activeLeaseCount--; |
| | 1073 | 444 | | if (entry.LeaseCount == 0) |
| | | 445 | | { |
| | 798 | 446 | | _leasedBytes = checked(_leasedBytes - entry.Payload.RetainedBytes); |
| | 798 | 447 | | if (!entry.IsCached) |
| | 12 | 448 | | _detachedBytes = checked(_detachedBytes - entry.Payload.RetainedBytes); |
| | | 449 | | } |
| | 1073 | 450 | | RecycleLease(lease); |
| | 1073 | 451 | | } |
| | 1073 | 452 | | } |
| | | 453 | | |
| | | 454 | | internal void ReturnGuide(NavigationAStarGuideLease guide, long generation) |
| | | 455 | | { |
| | 613 | 456 | | if (!guide.TryDetach( |
| | 613 | 457 | | generation, |
| | 613 | 458 | | out NavigationAStarPayloadLease payloadLease)) |
| | 5 | 459 | | return; |
| | 608 | 460 | | payloadLease.Dispose(); |
| | 608 | 461 | | lock (_sync) |
| | 608 | 462 | | RetainGuideIfReusable(generation, guide, ref _freeGuides); |
| | 608 | 463 | | } |
| | | 464 | | |
| | | 465 | | internal static void RetainGuideIfReusable( |
| | | 466 | | long generation, |
| | | 467 | | NavigationAStarGuideLease guide, |
| | | 468 | | ref NavigationAStarGuideLease? freeGuides) |
| | | 469 | | { |
| | 610 | 470 | | if (!NavigationGenerationCounter.CanAdvance(generation)) |
| | 1 | 471 | | return; |
| | 609 | 472 | | guide.NextPooled = freeGuides; |
| | 609 | 473 | | freeGuides = guide; |
| | 609 | 474 | | } |
| | | 475 | | |
| | | 476 | | private NavigationAStarPayloadLease Checkout(CacheEntry entry) |
| | | 477 | | { |
| | 1093 | 478 | | if (entry.LeaseCount == 0) |
| | 818 | 479 | | _leasedBytes = checked(_leasedBytes + entry.Payload.RetainedBytes); |
| | 1093 | 480 | | entry.LeaseCount++; |
| | 1093 | 481 | | _activeLeaseCount++; |
| | 1093 | 482 | | NavigationAStarPayloadLease? lease = _freeLeases; |
| | 1093 | 483 | | if (lease == null) |
| | 110 | 484 | | lease = new NavigationAStarPayloadLease(this); |
| | | 485 | | else |
| | | 486 | | { |
| | 983 | 487 | | _freeLeases = lease.NextPooled; |
| | 983 | 488 | | lease.NextPooled = null; |
| | | 489 | | } |
| | 1093 | 490 | | lease.Bind(entry); |
| | 1093 | 491 | | return lease; |
| | | 492 | | } |
| | | 493 | | |
| | | 494 | | private void RecycleLease(NavigationAStarPayloadLease lease) |
| | | 495 | | { |
| | 1073 | 496 | | lease.NextPooled = _freeLeases; |
| | 1073 | 497 | | _freeLeases = lease; |
| | 1073 | 498 | | } |
| | | 499 | | |
| | | 500 | | private bool IsReservationCurrentUnderLock( |
| | | 501 | | NavigationAStarPayloadReservation reservation) => |
| | 1291 | 502 | | ReferenceEquals(reservation.Owner, this) |
| | 1291 | 503 | | && reservation.Slot != null |
| | 1291 | 504 | | && reservation.Slot.Generation == reservation.Generation |
| | 1291 | 505 | | && reservation.Slot.IsReserved; |
| | | 506 | | |
| | | 507 | | private void ReleasePayloadReservationUnderLock( |
| | | 508 | | NavigationAStarPayloadReservation reservation) |
| | | 509 | | { |
| | 1148 | 510 | | NavigationAStarPayloadReservationSlot slot = reservation.Slot!; |
| | 1148 | 511 | | _reservedPayloadBytes -= slot.MaximumBytes; |
| | 1148 | 512 | | _reservedLeaseCount--; |
| | 1148 | 513 | | slot.MaximumBytes = 0; |
| | 1148 | 514 | | slot.IsReserved = false; |
| | 1148 | 515 | | slot.NextPooled = _freeReservationSlots; |
| | 1148 | 516 | | _freeReservationSlots = slot; |
| | 1148 | 517 | | } |
| | | 518 | | |
| | | 519 | | private void FindSlot( |
| | | 520 | | NavigationAStarPayloadKey key, |
| | | 521 | | out int slot, |
| | | 522 | | out bool found) |
| | | 523 | | { |
| | 1428 | 524 | | slot = key.GetHashCode() & _mask; |
| | 1428 | 525 | | int firstRemoved = -1; |
| | 3448 | 526 | | for (int probe = 0; probe < _states.Length; probe++) |
| | | 527 | | { |
| | 1600 | 528 | | byte state = _states[slot]; |
| | 1600 | 529 | | if (state == 0) |
| | | 530 | | { |
| | 386 | 531 | | found = false; |
| | 386 | 532 | | if (firstRemoved >= 0) |
| | 42 | 533 | | slot = firstRemoved; |
| | 386 | 534 | | return; |
| | | 535 | | } |
| | 1214 | 536 | | if (state == 1 && _keys[slot].Equals(key)) |
| | | 537 | | { |
| | 918 | 538 | | found = true; |
| | 918 | 539 | | return; |
| | | 540 | | } |
| | 296 | 541 | | if (state == 2 && firstRemoved < 0) |
| | 166 | 542 | | firstRemoved = slot; |
| | 296 | 543 | | slot = (slot + 1) & _mask; |
| | | 544 | | } |
| | 124 | 545 | | found = false; |
| | 124 | 546 | | slot = firstRemoved; |
| | 124 | 547 | | } |
| | | 548 | | |
| | | 549 | | private void Touch(int slot) |
| | | 550 | | { |
| | 892 | 551 | | if (_mostRecent == slot) |
| | 882 | 552 | | return; |
| | 10 | 553 | | Unlink(slot); |
| | 10 | 554 | | LinkMostRecent(slot); |
| | 10 | 555 | | } |
| | | 556 | | |
| | | 557 | | private void LinkMostRecent(int slot) |
| | | 558 | | { |
| | 209 | 559 | | _previous[slot] = _mostRecent; |
| | 209 | 560 | | _next[slot] = -1; |
| | 209 | 561 | | if (_mostRecent >= 0) |
| | 54 | 562 | | _next[_mostRecent] = slot; |
| | | 563 | | else |
| | 155 | 564 | | _leastRecent = slot; |
| | 209 | 565 | | _mostRecent = slot; |
| | 209 | 566 | | } |
| | | 567 | | |
| | | 568 | | private void Unlink(int slot) |
| | | 569 | | { |
| | 100 | 570 | | int previous = _previous[slot]; |
| | 100 | 571 | | int next = _next[slot]; |
| | 100 | 572 | | if (previous >= 0) |
| | 12 | 573 | | _next[previous] = next; |
| | | 574 | | else |
| | 88 | 575 | | _leastRecent = next; |
| | 100 | 576 | | if (next >= 0) |
| | 17 | 577 | | _previous[next] = previous; |
| | | 578 | | else |
| | 83 | 579 | | _mostRecent = previous; |
| | 100 | 580 | | _previous[slot] = -1; |
| | 100 | 581 | | _next[slot] = -1; |
| | 100 | 582 | | } |
| | | 583 | | |
| | | 584 | | private void RemoveAt(int slot) |
| | | 585 | | { |
| | 90 | 586 | | CacheEntry entry = _entries[slot]!; |
| | 90 | 587 | | _cachedBytes = checked(_cachedBytes - entry.Payload.RetainedBytes); |
| | 90 | 588 | | entry.IsCached = false; |
| | 90 | 589 | | if (entry.LeaseCount != 0) |
| | 10 | 590 | | _detachedBytes = checked(_detachedBytes + entry.Payload.RetainedBytes); |
| | 90 | 591 | | Unlink(slot); |
| | 90 | 592 | | _keys[slot] = default; |
| | 90 | 593 | | _entries[slot] = null; |
| | 90 | 594 | | _states[slot] = 2; |
| | 90 | 595 | | _count--; |
| | 90 | 596 | | } |
| | | 597 | | |
| | | 598 | | internal sealed class CacheEntry |
| | | 599 | | { |
| | 201 | 600 | | internal CacheEntry(NavigationAStarPayload payload, bool isCached) |
| | | 601 | | { |
| | 201 | 602 | | Payload = payload; |
| | 201 | 603 | | IsCached = isCached; |
| | 201 | 604 | | } |
| | | 605 | | |
| | | 606 | | internal NavigationAStarPayload Payload { get; } |
| | | 607 | | |
| | | 608 | | internal int LeaseCount { get; set; } |
| | | 609 | | |
| | | 610 | | internal bool IsCached { get; set; } |
| | | 611 | | } |
| | | 612 | | } |