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