| | | 1 | | //======================================================================= |
| | | 2 | | // NavigationAreaCatalog.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 one immutable, ordinally indexed set of latest area-policy revisions.</summary> |
| | | 13 | | internal sealed class NavigationAreaCatalog |
| | | 14 | | { |
| | | 15 | | private readonly NavigationAreaPolicy[] _policies; |
| | | 16 | | private readonly long _retainedBytes; |
| | | 17 | | |
| | 720 | 18 | | private NavigationAreaCatalog(NavigationAreaPolicy[] policies, int totalRuleCount, long version) |
| | | 19 | | { |
| | 720 | 20 | | _policies = policies; |
| | 720 | 21 | | TotalRuleCount = totalRuleCount; |
| | 720 | 22 | | Version = version; |
| | 720 | 23 | | long bytes = 48L + ((long)_policies.Length * sizeof(long)); |
| | 2888 | 24 | | for (int i = 0; i < _policies.Length; i++) |
| | 724 | 25 | | bytes = checked(bytes + _policies[i].RetainedBytes); |
| | 720 | 26 | | _retainedBytes = bytes; |
| | 720 | 27 | | } |
| | | 28 | | |
| | | 29 | | internal static NavigationAreaCatalog Empty { get; } = new( |
| | | 30 | | Array.Empty<NavigationAreaPolicy>(), |
| | | 31 | | totalRuleCount: 0, |
| | | 32 | | version: 0); |
| | | 33 | | |
| | | 34 | | internal int TotalRuleCount { get; } |
| | | 35 | | |
| | | 36 | | internal long Version { get; } |
| | | 37 | | |
| | 4729 | 38 | | internal long RetainedBytes => _retainedBytes; |
| | | 39 | | |
| | 4727 | 40 | | internal int PersistentPageCount => 1 + _policies.Length; |
| | | 41 | | |
| | | 42 | | internal int GetPublishWork( |
| | | 43 | | NavigationAreaPolicy policy, |
| | | 44 | | int maxPolicies, |
| | | 45 | | int maxRules) |
| | | 46 | | { |
| | 188 | 47 | | int index = FindPolicy(policy.Key.PolicyId); |
| | 188 | 48 | | bool canInsert = index < 0 |
| | 188 | 49 | | && _policies.Length < maxPolicies |
| | 188 | 50 | | && TotalRuleCount <= maxRules - policy.RuleCount; |
| | 188 | 51 | | int copiedPolicyReferences = canInsert |
| | 188 | 52 | | ? _policies.Length + 1 |
| | 188 | 53 | | : _policies.Length; |
| | 188 | 54 | | return checked( |
| | 188 | 55 | | 1 + Math.Max(policy.RuleCount, 2 * copiedPolicyReferences)); |
| | | 56 | | } |
| | | 57 | | |
| | | 58 | | internal bool TryGet(NavigationAreaPolicyKey key, out NavigationAreaPolicy policy) |
| | | 59 | | { |
| | 28365 | 60 | | int index = FindPolicy(key.PolicyId); |
| | 28365 | 61 | | if (index >= 0 && _policies[index].Key.Equals(key)) |
| | | 62 | | { |
| | 28348 | 63 | | policy = _policies[index]; |
| | 28348 | 64 | | return true; |
| | | 65 | | } |
| | 17 | 66 | | policy = null!; |
| | 17 | 67 | | return false; |
| | | 68 | | } |
| | | 69 | | |
| | | 70 | | internal NavigationOperationRejection TryPublish( |
| | | 71 | | NavigationAreaPolicy policy, |
| | | 72 | | int maxPolicies, |
| | | 73 | | int requiredRuleCount, |
| | | 74 | | int maxRulesPerPolicy, |
| | | 75 | | int maxRules, |
| | | 76 | | out NavigationAreaCatalog next) |
| | | 77 | | { |
| | 732 | 78 | | if (policy.RuleCount != requiredRuleCount) |
| | | 79 | | { |
| | 1 | 80 | | next = this; |
| | 1 | 81 | | return NavigationOperationRejection.ValidationFailed; |
| | | 82 | | } |
| | 731 | 83 | | if (policy.RuleCount > maxRulesPerPolicy) |
| | | 84 | | { |
| | 1 | 85 | | next = this; |
| | 1 | 86 | | return NavigationOperationRejection.CapacityExceeded; |
| | | 87 | | } |
| | | 88 | | |
| | 730 | 89 | | int index = FindPolicy(policy.Key.PolicyId); |
| | 730 | 90 | | if (index >= 0) |
| | | 91 | | { |
| | 13 | 92 | | NavigationAreaPolicy current = _policies[index]; |
| | 13 | 93 | | if (policy.Key.Revision < current.Key.Revision) |
| | | 94 | | { |
| | 1 | 95 | | next = this; |
| | 1 | 96 | | return NavigationOperationRejection.Stale; |
| | | 97 | | } |
| | 12 | 98 | | if (policy.Key.Revision == current.Key.Revision) |
| | | 99 | | { |
| | 8 | 100 | | next = this; |
| | 8 | 101 | | return current.ContentEquals(policy) |
| | 8 | 102 | | ? NavigationOperationRejection.None |
| | 8 | 103 | | : NavigationOperationRejection.ValidationFailed; |
| | | 104 | | } |
| | | 105 | | |
| | 4 | 106 | | int rules = checked(TotalRuleCount - current.RuleCount + policy.RuleCount); |
| | 4 | 107 | | if (rules > maxRules) |
| | | 108 | | { |
| | 1 | 109 | | next = this; |
| | 1 | 110 | | return NavigationOperationRejection.CapacityExceeded; |
| | | 111 | | } |
| | 3 | 112 | | var replacement = (NavigationAreaPolicy[])_policies.Clone(); |
| | 3 | 113 | | replacement[index] = policy; |
| | 3 | 114 | | next = new NavigationAreaCatalog(replacement, rules, Version + 1); |
| | 3 | 115 | | return NavigationOperationRejection.None; |
| | | 116 | | } |
| | | 117 | | |
| | 717 | 118 | | if (_policies.Length >= maxPolicies || TotalRuleCount + policy.RuleCount > maxRules) |
| | | 119 | | { |
| | 1 | 120 | | next = this; |
| | 1 | 121 | | return NavigationOperationRejection.CapacityExceeded; |
| | | 122 | | } |
| | | 123 | | |
| | 716 | 124 | | int insertion = ~index; |
| | 716 | 125 | | var added = new NavigationAreaPolicy[_policies.Length + 1]; |
| | 716 | 126 | | Array.Copy(_policies, 0, added, 0, insertion); |
| | 716 | 127 | | added[insertion] = policy; |
| | 716 | 128 | | Array.Copy(_policies, insertion, added, insertion + 1, _policies.Length - insertion); |
| | 716 | 129 | | next = new NavigationAreaCatalog(added, TotalRuleCount + policy.RuleCount, Version + 1); |
| | 716 | 130 | | return NavigationOperationRejection.None; |
| | | 131 | | } |
| | | 132 | | |
| | | 133 | | private int FindPolicy(string policyId) |
| | | 134 | | { |
| | 29283 | 135 | | int low = 0; |
| | 29283 | 136 | | int high = _policies.Length - 1; |
| | 29295 | 137 | | while (low <= high) |
| | | 138 | | { |
| | 28391 | 139 | | int middle = low + ((high - low) >> 1); |
| | 28391 | 140 | | int comparison = string.CompareOrdinal(_policies[middle].Key.PolicyId, policyId); |
| | 28391 | 141 | | if (comparison == 0) |
| | 28379 | 142 | | return middle; |
| | 12 | 143 | | if (comparison < 0) |
| | 7 | 144 | | low = middle + 1; |
| | | 145 | | else |
| | 5 | 146 | | high = middle - 1; |
| | | 147 | | } |
| | 904 | 148 | | return ~low; |
| | | 149 | | } |
| | | 150 | | } |