| | | 1 | | //======================================================================= |
| | | 2 | | // NavigationPageStampSet.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 SwiftCollections.Utility; |
| | | 10 | | |
| | | 11 | | namespace Trailblazer.Pathing; |
| | | 12 | | |
| | | 13 | | /// <summary>Provides fixed-capacity deterministic page-address membership.</summary> |
| | | 14 | | internal sealed class NavigationPageStampSet |
| | | 15 | | { |
| | | 16 | | private readonly string[] _mapIds; |
| | | 17 | | private readonly int[] _pageIndices; |
| | | 18 | | private readonly long[] _stamps; |
| | | 19 | | private readonly int _mask; |
| | | 20 | | private int _count; |
| | 34633 | 21 | | private long _generation = 1; |
| | | 22 | | |
| | 34633 | 23 | | internal NavigationPageStampSet(int capacity) |
| | | 24 | | { |
| | 34633 | 25 | | int required = checked(capacity * 2); |
| | 34633 | 26 | | int tableSize = 1; |
| | 372119 | 27 | | while (tableSize < required) |
| | 337486 | 28 | | tableSize = checked(tableSize * 2); |
| | 34633 | 29 | | _mapIds = new string[tableSize]; |
| | 34633 | 30 | | _pageIndices = new int[tableSize]; |
| | 34633 | 31 | | _stamps = new long[tableSize]; |
| | 34633 | 32 | | _mask = tableSize - 1; |
| | 34633 | 33 | | } |
| | | 34 | | |
| | | 35 | | internal void Reset() |
| | | 36 | | { |
| | | 37 | | unchecked |
| | | 38 | | { |
| | 8466 | 39 | | _generation++; |
| | | 40 | | } |
| | 8466 | 41 | | _count = 0; |
| | 8466 | 42 | | } |
| | | 43 | | |
| | | 44 | | internal bool Contains(string mapId, int pageIndex) => |
| | 1652 | 45 | | Find(mapId, pageIndex, out _); |
| | | 46 | | |
| | | 47 | | internal bool Add(string mapId, int pageIndex) |
| | | 48 | | { |
| | 47343 | 49 | | if (Find(mapId, pageIndex, out int index)) |
| | 43535 | 50 | | return false; |
| | 3808 | 51 | | _mapIds[index] = mapId; |
| | 3808 | 52 | | _pageIndices[index] = pageIndex; |
| | 3808 | 53 | | _stamps[index] = _generation; |
| | 3808 | 54 | | _count++; |
| | 3808 | 55 | | return true; |
| | | 56 | | } |
| | | 57 | | |
| | | 58 | | private bool Find(string mapId, int pageIndex, out int index) |
| | | 59 | | { |
| | 48995 | 60 | | int mapHash = SwiftHashTools.GetDeterministicStringEqualityComparer().GetHashCode(mapId); |
| | 48995 | 61 | | index = SwiftHashTools.CombineHashCodes(mapHash, pageIndex) & _mask; |
| | 49023 | 62 | | while (_stamps[index] == _generation) |
| | | 63 | | { |
| | 45188 | 64 | | if (_pageIndices[index] == pageIndex |
| | 45188 | 65 | | && string.Equals(_mapIds[index], mapId, StringComparison.Ordinal)) |
| | | 66 | | { |
| | 45160 | 67 | | return true; |
| | | 68 | | } |
| | 28 | 69 | | index = (index + 1) & _mask; |
| | | 70 | | } |
| | 3835 | 71 | | return false; |
| | | 72 | | } |
| | | 73 | | } |