| | | 1 | | //======================================================================= |
| | | 2 | | // NavigationPagedSequence.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>Stores an immutable ordered sequence in fixed-size allocation pages.</summary> |
| | | 13 | | internal sealed class NavigationPagedSequence<T> |
| | | 14 | | { |
| | | 15 | | private const int PageCapacity = 8; |
| | | 16 | | private const long WrapperBytes = 32L; |
| | | 17 | | private const long BuilderBytes = 40L; |
| | | 18 | | private const long PageAndArrayHeadersBytes = 56L; |
| | | 19 | | |
| | | 20 | | internal static NavigationPagedSequence<T> Empty { get; } = new(null, 0, 0, 0); |
| | | 21 | | |
| | | 22 | | private readonly Page? _head; |
| | | 23 | | private readonly int _pageCount; |
| | | 24 | | private readonly int _elementBytes; |
| | | 25 | | |
| | 24152 | 26 | | private NavigationPagedSequence(Page? head, int count, int pageCount, int elementBytes) |
| | | 27 | | { |
| | 24152 | 28 | | _head = head; |
| | 24152 | 29 | | Count = count; |
| | 24152 | 30 | | _pageCount = pageCount; |
| | 24152 | 31 | | _elementBytes = elementBytes; |
| | 24152 | 32 | | } |
| | | 33 | | |
| | | 34 | | internal int Count { get; } |
| | | 35 | | |
| | 93604 | 36 | | internal long RetainedBytes => Count == 0 |
| | 93604 | 37 | | ? 0L |
| | 93604 | 38 | | : checked( |
| | 93604 | 39 | | WrapperBytes |
| | 93604 | 40 | | + ((long)_pageCount |
| | 93604 | 41 | | * (PageAndArrayHeadersBytes + ((long)PageCapacity * _elementBytes)))); |
| | | 42 | | |
| | 93599 | 43 | | internal int PersistentPageCount => Count == 0 ? 0 : checked(1 + (_pageCount * 2)); |
| | | 44 | | |
| | | 45 | | internal T this[int index] |
| | | 46 | | { |
| | | 47 | | get |
| | | 48 | | { |
| | 48 | 49 | | if ((uint)index >= (uint)Count) |
| | 2 | 50 | | throw new ArgumentOutOfRangeException(nameof(index)); |
| | 46 | 51 | | Page page = _head!; |
| | 47 | 52 | | while (index >= page.Count) |
| | | 53 | | { |
| | 1 | 54 | | index -= page.Count; |
| | 1 | 55 | | page = page.Next!; |
| | | 56 | | } |
| | 46 | 57 | | return page.Values[index]; |
| | | 58 | | } |
| | | 59 | | } |
| | | 60 | | |
| | 1533694 | 61 | | internal Enumerator GetEnumerator() => new(_head, Count); |
| | | 62 | | |
| | | 63 | | internal struct Enumerator |
| | | 64 | | { |
| | | 65 | | private Page? _page; |
| | | 66 | | private int _pageIndex; |
| | | 67 | | private int _remaining; |
| | | 68 | | |
| | | 69 | | internal Enumerator(Page? page, int count) |
| | | 70 | | { |
| | 1533694 | 71 | | _page = page; |
| | 1533694 | 72 | | _pageIndex = 0; |
| | 1533694 | 73 | | _remaining = count; |
| | 1533694 | 74 | | Current = default!; |
| | 1533694 | 75 | | } |
| | | 76 | | |
| | | 77 | | internal T Current { get; private set; } |
| | | 78 | | |
| | | 79 | | internal bool MoveNext() |
| | | 80 | | { |
| | 2720908 | 81 | | if (_remaining == 0) |
| | | 82 | | { |
| | 1358736 | 83 | | Current = default!; |
| | 1358736 | 84 | | return false; |
| | | 85 | | } |
| | 1362172 | 86 | | if (_pageIndex == _page!.Count) |
| | | 87 | | { |
| | 9556 | 88 | | _page = _page.Next; |
| | 9556 | 89 | | _pageIndex = 0; |
| | | 90 | | } |
| | 1362172 | 91 | | Current = _page!.Values[_pageIndex++]; |
| | 1362172 | 92 | | _remaining--; |
| | 1362172 | 93 | | return true; |
| | | 94 | | } |
| | | 95 | | } |
| | | 96 | | |
| | | 97 | | internal sealed class Builder |
| | | 98 | | { |
| | | 99 | | private readonly int _elementBytes; |
| | | 100 | | private Page? _head; |
| | | 101 | | private Page? _tail; |
| | | 102 | | private int _count; |
| | | 103 | | private int _pageCount; |
| | | 104 | | |
| | 24156 | 105 | | internal Builder(int elementBytes) |
| | | 106 | | { |
| | 24156 | 107 | | if (elementBytes <= 0) |
| | 2 | 108 | | throw new ArgumentOutOfRangeException(nameof(elementBytes)); |
| | 24154 | 109 | | _elementBytes = elementBytes; |
| | 24154 | 110 | | } |
| | | 111 | | |
| | 89431 | 112 | | internal long RetainedBytes => checked( |
| | 89431 | 113 | | BuilderBytes |
| | 89431 | 114 | | + ((long)_pageCount |
| | 89431 | 115 | | * (PageAndArrayHeadersBytes + ((long)PageCapacity * _elementBytes)))); |
| | | 116 | | |
| | 89557 | 117 | | internal int PersistentPageCount => checked(1 + (_pageCount * 2)); |
| | | 118 | | |
| | | 119 | | internal void Append(T value) |
| | | 120 | | { |
| | 110320 | 121 | | if (_tail == null || _tail.Count == PageCapacity) |
| | | 122 | | { |
| | 32115 | 123 | | var page = new Page(); |
| | 32115 | 124 | | if (_tail == null) |
| | 24151 | 125 | | _head = page; |
| | | 126 | | else |
| | 7964 | 127 | | _tail.Next = page; |
| | 32115 | 128 | | _tail = page; |
| | 32115 | 129 | | _pageCount++; |
| | | 130 | | } |
| | 110320 | 131 | | _tail.Values[_tail.Count++] = value; |
| | 110320 | 132 | | _count++; |
| | 110320 | 133 | | } |
| | | 134 | | |
| | 24148 | 135 | | internal NavigationPagedSequence<T> Seal() => _count == 0 |
| | 24148 | 136 | | ? Empty |
| | 24148 | 137 | | : new NavigationPagedSequence<T>(_head, _count, _pageCount, _elementBytes); |
| | | 138 | | } |
| | | 139 | | |
| | | 140 | | internal sealed class Page |
| | | 141 | | { |
| | 32115 | 142 | | internal readonly T[] Values = new T[PageCapacity]; |
| | | 143 | | internal Page? Next; |
| | | 144 | | internal int Count; |
| | | 145 | | } |
| | | 146 | | } |