| | | 1 | | //======================================================================= |
| | | 2 | | // NavigationAddressStampSet.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>Provides fixed-capacity address deduplication with constant-time logical reset.</summary> |
| | | 13 | | internal sealed class NavigationAddressStampSet |
| | | 14 | | { |
| | | 15 | | private readonly NavigationCellAddress[] _values; |
| | | 16 | | private readonly long[] _stamps; |
| | | 17 | | private readonly int _mask; |
| | 39357 | 18 | | private long _generation = 1; |
| | | 19 | | |
| | 39357 | 20 | | internal NavigationAddressStampSet(int capacity) |
| | | 21 | | { |
| | 39357 | 22 | | if (capacity <= 0) |
| | 1 | 23 | | throw new ArgumentOutOfRangeException(nameof(capacity)); |
| | 39356 | 24 | | int required = checked(capacity * 2); |
| | 39356 | 25 | | int tableSize = 1; |
| | 399478 | 26 | | while (tableSize < required) |
| | 360122 | 27 | | tableSize = checked(tableSize * 2); |
| | 39356 | 28 | | _values = new NavigationCellAddress[tableSize]; |
| | 39356 | 29 | | _stamps = new long[tableSize]; |
| | 39356 | 30 | | _mask = tableSize - 1; |
| | 39356 | 31 | | } |
| | | 32 | | |
| | | 33 | | internal void Reset() |
| | | 34 | | { |
| | 20621 | 35 | | _generation = NavigationGenerationCounter.Advance( |
| | 20621 | 36 | | _generation, |
| | 20621 | 37 | | "Address stamp generation capacity is exhausted."); |
| | 20621 | 38 | | } |
| | | 39 | | |
| | | 40 | | internal bool Add(NavigationCellAddress value) |
| | | 41 | | { |
| | 297639 | 42 | | int index = value.GetHashCode() & _mask; |
| | 298583 | 43 | | while (_stamps[index] == _generation) |
| | | 44 | | { |
| | 179981 | 45 | | if (_values[index].Equals(value)) |
| | 179037 | 46 | | return false; |
| | 944 | 47 | | index = (index + 1) & _mask; |
| | | 48 | | } |
| | 118602 | 49 | | _values[index] = value; |
| | 118602 | 50 | | _stamps[index] = _generation; |
| | 118602 | 51 | | return true; |
| | | 52 | | } |
| | | 53 | | |
| | | 54 | | internal bool Contains(NavigationCellAddress value) |
| | | 55 | | { |
| | 52268 | 56 | | int index = value.GetHashCode() & _mask; |
| | 52482 | 57 | | while (_stamps[index] == _generation) |
| | | 58 | | { |
| | 52465 | 59 | | if (_values[index].Equals(value)) |
| | 52251 | 60 | | return true; |
| | 214 | 61 | | index = (index + 1) & _mask; |
| | | 62 | | } |
| | 17 | 63 | | return false; |
| | | 64 | | } |
| | | 65 | | } |