| | | 1 | | using System; |
| | | 2 | | using System.Collections.Concurrent; |
| | | 3 | | using System.Collections.Generic; |
| | | 4 | | using System.IO; |
| | | 5 | | using System.Linq; |
| | | 6 | | using System.Threading; |
| | | 7 | | using System.Threading.Tasks; |
| | | 8 | | using Itinero.IO; |
| | | 9 | | |
| | | 10 | | namespace Itinero.Indexes; |
| | | 11 | | |
| | | 12 | | /// <summary> |
| | | 13 | | /// A default attribute set index using a dictionary internally. |
| | | 14 | | /// </summary> |
| | | 15 | | /// <remarks> |
| | | 16 | | /// Safe for concurrent use. <see cref="Get"/> is called while tiles are inserted from several |
| | | 17 | | /// threads — it is reached indirectly, through the <c>Func</c> handed out by |
| | | 18 | | /// <c>RouterDb.GetEdgeTypeMap()</c>, which makes it easy to miss that it is shared mutable state |
| | | 19 | | /// at all: the call site reads as a pure lookup but interning an unseen set appends here. |
| | | 20 | | /// |
| | | 21 | | /// In a production run nothing is ever appended, because the tiles were preprocessed against |
| | | 22 | | /// this same index and every type already exists. So the design optimises the hit: a lock-free |
| | | 23 | | /// dictionary read, no allocation beyond the caller's own sorted array. Only a genuine miss |
| | | 24 | | /// takes a lock. |
| | | 25 | | /// |
| | | 26 | | /// Ids have to stay contiguous from zero — <see cref="WriteTo"/> emits the sets in id order and |
| | | 27 | | /// <see cref="ReadFrom"/> restores them by position, so a gap would corrupt the format. That is |
| | | 28 | | /// why the miss path takes a lock and assigns the id itself rather than using |
| | | 29 | | /// <c>GetOrAdd</c> with an <c>Interlocked</c> counter: a concurrent dictionary may run its value |
| | | 30 | | /// factory more than once, and each spare run would burn an id and leave a hole. |
| | | 31 | | /// </remarks> |
| | | 32 | | public sealed class AttributeSetDictionaryIndex : AttributeSetIndex |
| | | 33 | | { |
| | | 34 | | private readonly ConcurrentDictionary<IReadOnlyList<(string key, string value)>, uint> _index; |
| | | 35 | | private readonly ConcurrentDictionary<uint, IReadOnlyList<(string key, string value)>> _byId; |
| | | 36 | | |
| | | 37 | | /// Guards the miss path only: assigning the next id and publishing both mappings. |
| | 1032 | 38 | | private readonly object _writeLock = new(); |
| | | 39 | | |
| | | 40 | | private int _count; |
| | | 41 | | |
| | | 42 | | /// <summary> |
| | | 43 | | /// Creates a new attribute set index. |
| | | 44 | | /// </summary> |
| | | 45 | | /// <param name="edgeProfiles"></param> |
| | 1032 | 46 | | public AttributeSetDictionaryIndex(List<IReadOnlyList<(string key, string value)>>? edgeProfiles = null) |
| | 1032 | 47 | | { |
| | 1032 | 48 | | _index = new ConcurrentDictionary<IReadOnlyList<(string key, string value)>, uint>( |
| | 1032 | 49 | | AttributeSetEqualityComparer.Default); |
| | 1032 | 50 | | _byId = new ConcurrentDictionary<uint, IReadOnlyList<(string key, string value)>>(); |
| | | 51 | | |
| | 1032 | 52 | | var initial = edgeProfiles ?? |
| | 1032 | 53 | | new List<IReadOnlyList<(string key, string value)>> |
| | 1032 | 54 | | { Array.Empty<(string key, string value)>() }; |
| | 1032 | 55 | | this.Reset(initial); |
| | 1032 | 56 | | } |
| | | 57 | | |
| | | 58 | | /// Replaces the contents wholesale. Used on construction and by <see cref="ReadFrom"/>. |
| | | 59 | | private void Reset(IReadOnlyList<IReadOnlyList<(string key, string value)>> sets) |
| | 1037 | 60 | | { |
| | 1037 | 61 | | lock (_writeLock) |
| | 1037 | 62 | | { |
| | 1037 | 63 | | _index.Clear(); |
| | 1037 | 64 | | _byId.Clear(); |
| | 4154 | 65 | | for (var p = 0; p < sets.Count; p++) |
| | 1040 | 66 | | { |
| | 1040 | 67 | | _byId[(uint)p] = sets[p]; |
| | 1040 | 68 | | _index[sets[p]] = (uint)p; |
| | 1040 | 69 | | } |
| | | 70 | | |
| | 1037 | 71 | | Volatile.Write(ref _count, sets.Count); |
| | 1037 | 72 | | } |
| | 1037 | 73 | | } |
| | | 74 | | |
| | | 75 | | /// <summary> |
| | | 76 | | /// Gets the number of distinct sets. |
| | | 77 | | /// </summary> |
| | 3 | 78 | | public override uint Count => (uint)Volatile.Read(ref _count); |
| | | 79 | | |
| | | 80 | | /// <summary> |
| | | 81 | | /// Gets the attributes for the given id. |
| | | 82 | | /// </summary> |
| | | 83 | | /// <param name="id">The id.</param> |
| | | 84 | | /// <returns>The attributes in the type.</returns> |
| | | 85 | | public override IEnumerable<(string key, string value)> GetById(uint id) |
| | 8 | 86 | | { |
| | 9 | 87 | | if (!_byId.TryGetValue(id, out var set)) throw new ArgumentOutOfRangeException(nameof(id)); |
| | | 88 | | |
| | 7 | 89 | | return set; |
| | 7 | 90 | | } |
| | | 91 | | |
| | | 92 | | /// <summary> |
| | | 93 | | /// Gets the type id for the given attributes set. |
| | | 94 | | /// </summary> |
| | | 95 | | /// <param name="attributes">The attributes.</param> |
| | | 96 | | /// <returns>The id, if any.</returns> |
| | | 97 | | public override uint Get(IEnumerable<(string key, string value)> attributes) |
| | 64457 | 98 | | { |
| | 64457 | 99 | | var attributeSet = attributes.ToArray(); |
| | | 100 | | |
| | | 101 | | // sort array. |
| | 281870 | 102 | | Array.Sort(attributeSet, (x, y) => x.CompareTo(y)); |
| | | 103 | | |
| | | 104 | | // check if profile already there - the only path a production run takes. |
| | 64457 | 105 | | if (_index.TryGetValue(attributeSet, out var edgeProfileId)) |
| | 53600 | 106 | | { |
| | 53600 | 107 | | return edgeProfileId; |
| | | 108 | | } |
| | | 109 | | |
| | 10857 | 110 | | lock (_writeLock) |
| | 10857 | 111 | | { |
| | | 112 | | // Re-check: another thread may have interned the same set while this one waited. |
| | 10857 | 113 | | if (_index.TryGetValue(attributeSet, out edgeProfileId)) |
| | 0 | 114 | | { |
| | 0 | 115 | | return edgeProfileId; |
| | | 116 | | } |
| | | 117 | | |
| | | 118 | | // Publish by id first. A reader that resolves an id from the index must always find |
| | | 119 | | // the set behind it; the other order would expose an id whose attributes are not |
| | | 120 | | // there yet. |
| | 10857 | 121 | | edgeProfileId = (uint)Volatile.Read(ref _count); |
| | 10857 | 122 | | _byId[edgeProfileId] = attributeSet; |
| | 10857 | 123 | | _index[attributeSet] = edgeProfileId; |
| | 10857 | 124 | | Volatile.Write(ref _count, (int)edgeProfileId + 1); |
| | | 125 | | |
| | 10857 | 126 | | return edgeProfileId; |
| | | 127 | | } |
| | 64457 | 128 | | } |
| | | 129 | | |
| | | 130 | | /// <inheritdoc/> |
| | | 131 | | public override Task WriteTo(Stream stream) |
| | 5 | 132 | | { |
| | | 133 | | // write version #. |
| | 5 | 134 | | stream.WriteVarInt32(2); |
| | | 135 | | |
| | | 136 | | // write type. |
| | 5 | 137 | | stream.WriteWithSize("dictionary-index"); |
| | | 138 | | |
| | | 139 | | // write pairs, in id order: ReadFrom restores them by position. |
| | 5 | 140 | | var count = Volatile.Read(ref _count); |
| | 5 | 141 | | stream.WriteVarInt32(count); |
| | 26 | 142 | | for (var id = 0; id < count; id++) |
| | 8 | 143 | | { |
| | 8 | 144 | | var attributes = _byId[(uint)id]; |
| | 8 | 145 | | stream.WriteVarInt32(attributes.Count); |
| | 32 | 146 | | foreach (var (key, value) in attributes) |
| | 4 | 147 | | { |
| | 4 | 148 | | stream.WriteWithSize(key); |
| | 4 | 149 | | stream.WriteWithSize(value); |
| | 4 | 150 | | } |
| | 8 | 151 | | } |
| | | 152 | | |
| | 5 | 153 | | return Task.CompletedTask; |
| | 5 | 154 | | } |
| | | 155 | | |
| | | 156 | | /// <inheritdoc/> |
| | | 157 | | public override Task ReadFrom(Stream stream) |
| | 5 | 158 | | { |
| | | 159 | | // get version #. |
| | 5 | 160 | | var version = stream.ReadVarInt32(); |
| | 5 | 161 | | if (version != 2) throw new InvalidDataException("Unexpected version #."); |
| | | 162 | | |
| | | 163 | | // read type. |
| | 5 | 164 | | var type = stream.ReadWithSizeString(); |
| | 5 | 165 | | if (type != "dictionary-index") throw new InvalidDataException("Unexpected index type."); |
| | | 166 | | |
| | | 167 | | // read pairs. |
| | 5 | 168 | | var count = stream.ReadVarInt32(); |
| | 5 | 169 | | var sets = new List<IReadOnlyList<(string key, string value)>>(count); |
| | 26 | 170 | | for (var i = 0; i < count; i++) |
| | 8 | 171 | | { |
| | 8 | 172 | | var c = stream.ReadVarInt32(); |
| | 8 | 173 | | var attribute = new (string key, string value)[c]; |
| | 24 | 174 | | for (var a = 0; a < c; a++) |
| | 4 | 175 | | { |
| | 4 | 176 | | var key = stream.ReadWithSizeString(); |
| | 4 | 177 | | var value = stream.ReadWithSizeString(); |
| | 4 | 178 | | attribute[a] = (key, value); |
| | 4 | 179 | | } |
| | | 180 | | |
| | 8 | 181 | | sets.Add(attribute); |
| | 8 | 182 | | } |
| | | 183 | | |
| | 5 | 184 | | this.Reset(sets); |
| | 5 | 185 | | return Task.CompletedTask; |
| | 5 | 186 | | } |
| | | 187 | | } |