< Summary

Class:Itinero.Indexes.AttributeSetDictionaryIndex
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Indexes/AttributeSetDictionaryIndex.cs
Covered lines:83
Uncovered lines:2
Coverable lines:85
Total lines:187
Line coverage:97.6% (83 of 85)
Covered branches:19
Total branches:22
Branch coverage:86.3% (19 of 22)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%2100%
Reset(...)100%2100%
get_Count()100%1100%
GetById(...)100%2100%
Get(...)75%488.23%
WriteTo(...)100%4100%
ReadFrom(...)75%8100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Indexes/AttributeSetDictionaryIndex.cs

#LineLine coverage
 1using System;
 2using System.Collections.Concurrent;
 3using System.Collections.Generic;
 4using System.IO;
 5using System.Linq;
 6using System.Threading;
 7using System.Threading.Tasks;
 8using Itinero.IO;
 9
 10namespace 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>
 32public 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.
 103238    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>
 103246    public AttributeSetDictionaryIndex(List<IReadOnlyList<(string key, string value)>>? edgeProfiles = null)
 103247    {
 103248        _index = new ConcurrentDictionary<IReadOnlyList<(string key, string value)>, uint>(
 103249            AttributeSetEqualityComparer.Default);
 103250        _byId = new ConcurrentDictionary<uint, IReadOnlyList<(string key, string value)>>();
 51
 103252        var initial = edgeProfiles ??
 103253                      new List<IReadOnlyList<(string key, string value)>>
 103254                          { Array.Empty<(string key, string value)>() };
 103255        this.Reset(initial);
 103256    }
 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)
 103760    {
 103761        lock (_writeLock)
 103762        {
 103763            _index.Clear();
 103764            _byId.Clear();
 415465            for (var p = 0; p < sets.Count; p++)
 104066            {
 104067                _byId[(uint)p] = sets[p];
 104068                _index[sets[p]] = (uint)p;
 104069            }
 70
 103771            Volatile.Write(ref _count, sets.Count);
 103772        }
 103773    }
 74
 75    /// <summary>
 76    /// Gets the number of distinct sets.
 77    /// </summary>
 378    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)
 886    {
 987        if (!_byId.TryGetValue(id, out var set)) throw new ArgumentOutOfRangeException(nameof(id));
 88
 789        return set;
 790    }
 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)
 6445798    {
 6445799        var attributeSet = attributes.ToArray();
 100
 101        // sort array.
 281870102        Array.Sort(attributeSet, (x, y) => x.CompareTo(y));
 103
 104        // check if profile already there - the only path a production run takes.
 64457105        if (_index.TryGetValue(attributeSet, out var edgeProfileId))
 53600106        {
 53600107            return edgeProfileId;
 108        }
 109
 10857110        lock (_writeLock)
 10857111        {
 112            // Re-check: another thread may have interned the same set while this one waited.
 10857113            if (_index.TryGetValue(attributeSet, out edgeProfileId))
 0114            {
 0115                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.
 10857121            edgeProfileId = (uint)Volatile.Read(ref _count);
 10857122            _byId[edgeProfileId] = attributeSet;
 10857123            _index[attributeSet] = edgeProfileId;
 10857124            Volatile.Write(ref _count, (int)edgeProfileId + 1);
 125
 10857126            return edgeProfileId;
 127        }
 64457128    }
 129
 130    /// <inheritdoc/>
 131    public override Task WriteTo(Stream stream)
 5132    {
 133        // write version #.
 5134        stream.WriteVarInt32(2);
 135
 136        // write type.
 5137        stream.WriteWithSize("dictionary-index");
 138
 139        // write pairs, in id order: ReadFrom restores them by position.
 5140        var count = Volatile.Read(ref _count);
 5141        stream.WriteVarInt32(count);
 26142        for (var id = 0; id < count; id++)
 8143        {
 8144            var attributes = _byId[(uint)id];
 8145            stream.WriteVarInt32(attributes.Count);
 32146            foreach (var (key, value) in attributes)
 4147            {
 4148                stream.WriteWithSize(key);
 4149                stream.WriteWithSize(value);
 4150            }
 8151        }
 152
 5153        return Task.CompletedTask;
 5154    }
 155
 156    /// <inheritdoc/>
 157    public override Task ReadFrom(Stream stream)
 5158    {
 159        // get version #.
 5160        var version = stream.ReadVarInt32();
 5161        if (version != 2) throw new InvalidDataException("Unexpected version #.");
 162
 163        // read type.
 5164        var type = stream.ReadWithSizeString();
 5165        if (type != "dictionary-index") throw new InvalidDataException("Unexpected index type.");
 166
 167        // read pairs.
 5168        var count = stream.ReadVarInt32();
 5169        var sets = new List<IReadOnlyList<(string key, string value)>>(count);
 26170        for (var i = 0; i < count; i++)
 8171        {
 8172            var c = stream.ReadVarInt32();
 8173            var attribute = new (string key, string value)[c];
 24174            for (var a = 0; a < c; a++)
 4175            {
 4176                var key = stream.ReadWithSizeString();
 4177                var value = stream.ReadWithSizeString();
 4178                attribute[a] = (key, value);
 4179            }
 180
 8181            sets.Add(attribute);
 8182        }
 183
 5184        this.Reset(sets);
 5185        return Task.CompletedTask;
 5186    }
 187}