< Summary

Class:Itinero.Network.RoutingNetwork
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/RoutingNetwork.cs
/home/runner/work/routing2/routing2/src/Itinero/Network/RoutingNetwork.Islands.cs
/home/runner/work/routing2/routing2/src/Itinero/Network/RoutingNetwork.Mutation.cs
/home/runner/work/routing2/routing2/src/Itinero/Network/RoutingNetwork.Writer.cs
Covered lines:127
Uncovered lines:26
Coverable lines:153
Total lines:428
Line coverage:83% (127 of 153)
Covered branches:22
Total branches:34
Branch coverage:64.7% (22 of 34)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%1100%
.ctor(...)100%1100%
GetTileForRead(...)100%6100%
get_UsageNotifier()100%1100%
GetTileEnumerator()100%2100%
Itinero.Network.Enumerators.Edges.IEdgeEnumerable.GetTileForRead(...)100%1100%
get_Zoom()100%1100%
get_RouterDb()100%1100%
TryGetVertex(...)50%255.55%
GetEdgeEnumerator()100%1100%
Itinero.Network.Writer.IRoutingNetworkWritable.GetEdgeEnumerator()100%1100%
GetVertexEnumerator()100%1100%
HasTile(...)0%20%
Itinero.Network.Writer.IRoutingNetworkWritable.get_IslandManager()100%10%
Itinero.Network.Mutation.IRoutingNetworkMutable.get_IslandManager()100%1100%
.ctor(...)100%1100%
GetAsMutable()50%2100%
Itinero.Network.Mutation.IRoutingNetworkMutable.get_Tiles()100%1100%
Itinero.Network.Mutation.IRoutingNetworkMutable.ClearMutator()100%1100%
.ctor(...)100%1100%
CreateTileLocks()100%2100%
get_HasWriter()100%10%
GetWriter()50%466.66%
GetTileInsertWriter()50%270%
Itinero.Network.Writer.IRoutingNetworkWritable.ClearWriter()100%1100%
Itinero.Network.Writer.IRoutingNetworkWritable.ReleaseTileWriter()100%1100%
Itinero.Network.Writer.IRoutingNetworkWritable.TileLockIndex(...)100%1100%
Itinero.Network.Writer.IRoutingNetworkWritable.GetTileLockByIndex(...)100%1100%
Itinero.Network.Writer.IRoutingNetworkWritable.GetTileForWrite(...)75%478.94%
Itinero.Network.Writer.IRoutingNetworkWritable.SetTile(...)50%4100%
CloneTileIfNeededForMutator(...)50%457.14%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Network/RoutingNetwork.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using Itinero.Data.Usage;
 4using Itinero.Network.DataStructures;
 5using Itinero.Network.Enumerators.Edges;
 6using Itinero.Network.Enumerators.Vertices;
 7using Itinero.Network.Mutation;
 8using Itinero.Network.Search.Islands;
 9using Itinero.Network.Tiles;
 10using Itinero.Network.Writer;
 11
 12namespace Itinero.Network;
 13
 14/// <summary>
 15/// The routing network.
 16/// </summary>
 17public sealed partial class RoutingNetwork : IEdgeEnumerable, IRoutingNetworkMutable, IRoutingNetworkWritable
 18{
 19    private readonly SparseArray<NetworkTile?> _tiles;
 20
 21    /// <summary>
 22    /// Creates a new routing network.
 23    /// </summary>
 24    /// <param name="routerDb"></param>
 25    /// <param name="zoom"></param>
 26    /// <param name="maxIslandSize"></param>
 53127    public RoutingNetwork(RouterDb routerDb, int zoom = 14, int maxIslandSize = 1024)
 53128    {
 53129        this.Zoom = zoom;
 53130        this.RouterDb = routerDb;
 31
 53132        IslandManager = new RoutingNetworkIslandManager(maxIslandSize);
 53133        _tiles = new SparseArray<NetworkTile?>(0);
 53134    }
 35
 33536    internal RoutingNetwork(RouterDb routerDb, SparseArray<NetworkTile?> tiles, int zoom, RoutingNetworkIslandManager is
 33537    {
 33538        this.Zoom = zoom;
 33539        this.RouterDb = routerDb;
 33540        IslandManager = islandManager;
 33541        _tiles = tiles;
 33542    }
 43
 44    internal NetworkTile? GetTileForRead(uint localTileId)
 893965245    {
 1152080046        if (_tiles.Length <= localTileId) return null;
 47
 48        // get tile, if any.
 635850449        var tile = _tiles[localTileId];
 866434750        if (tile == null) return null;
 51
 52        // Id only: this runs on every tile access and the full map carries a delegate that is
 53        // only needed for the clone below.
 810532154        if (tile.EdgeTypeMapId == this.RouterDb.EdgeTypeMap.Id) return tile;
 55
 56        // tile.EdgeTypeMapId indicates the version of the used edgeTypeMap
 57        // If the id is different, the loaded tile needs updating; e.g. because a cost function has been changed
 158        var edgeTypeMap = this.RouterDb.GetEdgeTypeMap();
 159        tile = tile.CloneForEdgeTypeMap(edgeTypeMap);
 160        _tiles[localTileId] = tile;
 61
 162        return tile;
 893965263    }
 64
 65    /// <summary>
 66    /// Gets the usage notifier.
 67    /// </summary>
 31762168    public DataUseNotifier UsageNotifier { get; } = new();
 69
 70    internal IEnumerator<uint> GetTileEnumerator()
 9471    {
 9472        using var enumerator = _tiles.GetEnumerator();
 488880773        while (enumerator.MoveNext())
 488874174        {
 488874175            yield return (uint)enumerator.Current.i;
 488871376        }
 6677    }
 78
 79    NetworkTile? IEdgeEnumerable.GetTileForRead(uint localTileId)
 102855080    {
 102855081        return this.GetTileForRead(localTileId);
 102855082    }
 83
 84    /// <summary>
 85    /// Gets the zoom.
 86    /// </summary>
 8703187    public int Zoom { get; }
 88
 89    /// <summary>
 90    /// Gets the routing network.
 91    /// </summary>
 430418192    public RouterDb RouterDb { get; }
 93
 94    /// <summary>
 95    /// Tries to get the given vertex.
 96    /// </summary>
 97    /// <param name="vertex">The vertex.</param>
 98    /// <param name="longitude">The longitude.</param>
 99    /// <param name="latitude">The latitude.</param>
 100    /// <param name="elevation">The elevation.</param>
 101    /// <returns>The vertex.</returns>
 102    public bool TryGetVertex(VertexId vertex, out double longitude, out double latitude, out float? elevation)
 3016662103    {
 3016662104        var localTileId = vertex.TileId;
 105
 106        // get tile.
 3016662107        var tile = this.GetTileForRead(localTileId);
 6033324108        if (tile != null) return tile.TryGetVertex(vertex, out longitude, out latitude, out elevation);
 109
 110        // no tile, no vertex.
 0111        longitude = default;
 0112        latitude = default;
 0113        elevation = null;
 0114        return false;
 3016662115    }
 116
 117    /// <summary>
 118    /// Gets an edge enumerator.
 119    /// </summary>
 120    /// <returns>The enumerator.</returns>
 121    public RoutingNetworkEdgeEnumerator GetEdgeEnumerator()
 959334122    {
 959334123        return new RoutingNetworkEdgeEnumerator(this);
 959334124    }
 125
 126    RoutingNetworkEdgeEnumerator IRoutingNetworkWritable.GetEdgeEnumerator()
 930127    {
 930128        return this.GetEdgeEnumerator();
 930129    }
 130
 131    /// <summary>
 132    /// Gets a vertex enumerator.
 133    /// </summary>
 134    /// <returns>The enumerator.</returns>
 135    internal RoutingNetworkVertexEnumerator GetVertexEnumerator()
 94136    {
 94137        return new(this);
 94138    }
 139
 140    /// <summary>
 141    /// Returns true if this network has the given tile loaded.
 142    /// </summary>
 143    /// <param name="localTileId"></param>
 144    /// <returns></returns>
 145    public bool HasTile(uint localTileId)
 0146    {
 0147        if (localTileId >= _tiles.Length) return false;
 148
 0149        return _tiles[localTileId] != null;
 0150    }
 151}

/home/runner/work/routing2/routing2/src/Itinero/Network/RoutingNetwork.Islands.cs

#LineLine coverage
 1using Itinero.Network.Mutation;
 2using Itinero.Network.Search.Islands;
 3using Itinero.Network.Writer;
 4
 5namespace Itinero.Network;
 6
 7public sealed partial class RoutingNetwork
 8{
 9    internal readonly RoutingNetworkIslandManager IslandManager;
 10
 11    RoutingNetworkIslandManager IRoutingNetworkWritable.IslandManager
 12    {
 13        get
 014        {
 015            return IslandManager;
 016        }
 17    }
 18
 19    RoutingNetworkIslandManager IRoutingNetworkMutable.IslandManager
 20    {
 21        get
 33822        {
 33823            return IslandManager;
 33824        }
 25    }
 26}

/home/runner/work/routing2/routing2/src/Itinero/Network/RoutingNetwork.Mutation.cs

#LineLine coverage
 1using System;
 2using Itinero.Network.DataStructures;
 3using Itinero.Network.Mutation;
 4using Itinero.Network.Tiles;
 5
 6namespace Itinero.Network;
 7
 8public sealed partial class RoutingNetwork
 9{
 86610    private readonly object _mutatorSync = new();
 11    private RoutingNetworkMutator? _graphMutator;
 12
 13    /// <summary>
 14    /// Gets a mutable version of this network.
 15    /// </summary>
 16    /// <returns>The mutable version.</returns>
 17    /// <exception cref="InvalidOperationException"></exception>
 18    public RoutingNetworkMutator GetAsMutable()
 33419    {
 33420        lock (_mutatorSync)
 33421        {
 33422            if (_graphMutator != null) throw new InvalidOperationException($"Only one mutable graph is allowed at one ti
 23
 33424            _graphMutator = new RoutingNetworkMutator(this);
 33425            this.RouterDb.SetAsMutable(_graphMutator);
 33426            return _graphMutator;
 27        }
 33428    }
 29
 33430    SparseArray<NetworkTile?> IRoutingNetworkMutable.Tiles => _tiles;
 31
 32    void IRoutingNetworkMutable.ClearMutator()
 33133    {
 33134        _graphMutator = null;
 33135    }
 36}

/home/runner/work/routing2/routing2/src/Itinero/Network/RoutingNetwork.Writer.cs

#LineLine coverage
 1using System;
 2using System.Collections.Concurrent;
 3using System.Collections.Generic;
 4using System.Threading;
 5using Itinero.Network.DataStructures;
 6using Itinero.Network.Tiles;
 7using Itinero.Network.Writer;
 8
 9namespace Itinero.Network;
 10
 11public sealed partial class RoutingNetwork
 12{
 86613    private readonly object _writeSync = new();
 14    private RoutingNetworkWriter? _writer;
 15
 16    /// <summary>
 17    /// Concurrent tile-insert writers currently open.
 18    /// </summary>
 19    /// <remarks>
 20    /// Tile insertion is the one write that happens constantly and from many threads, so it gets
 21    /// its own admission rule: any number at once, but never alongside the exclusive writer.
 22    ///
 23    /// That exclusion is not new behaviour, it is the old behaviour made explicit. Tile insertion
 24    /// used to call <see cref="GetWriter"/>, so an open mutator made it throw — the two were
 25    /// already mutually exclusive, by exception rather than by design. Counting the tile writers
 26    /// keeps that guarantee while letting them run in parallel with each other.
 27    /// </remarks>
 28    private int _tileWriters;
 29
 30    /// <summary>
 31    /// A lock per tile, created on demand.
 32    /// </summary>
 33    /// <remarks>
 34    /// Writes to one tile cannot overlap: a NetworkTile is an append-only byte buffer with its own
 35    /// offsets, so two threads appending at once corrupt it. Different tiles are independent,
 36    /// which is what makes concurrent insertion possible at all.
 37    ///
 38    /// Never grows beyond the tiles actually written, and the entries are plain objects.
 39    /// </remarks>
 40    /// <summary>
 41    /// Striped write locks, indexed by tile id modulo the stripe count.
 42    /// </summary>
 43    /// <remarks>
 44    /// Striped rather than one lock per tile, because both obvious alternatives are worse. A
 45    /// <c>ConcurrentDictionary</c> keyed by tile id put 31% of warm blocked time inside its own
 46    /// <c>GetOrAdd</c> — the lookup cost more than the work it guarded. A flat array indexed by
 47    /// tile id is far worse: local tile ids at zoom 14 run to 2^28, and a country's tiles sit
 48    /// around id 90,000,000, so the array grows to ~134M references — about 1 GB — to guard some
 49    /// 7,000 real tiles. That is exactly why the tiles themselves live in a
 50    /// <see cref="SparseArray{T}"/>.
 51    ///
 52    /// Stripes give bounded memory and an index calculation instead of a hash lookup. Two
 53    /// unrelated tiles sharing a stripe is harmless: it over-excludes, briefly serialising two
 54    /// writes that need not have been, and never under-excludes.
 55    /// </remarks>
 56    private const int TileLockStripes = 4096;
 57
 86658    private readonly object[] _tileLocks = CreateTileLocks();
 59
 60    private static object[] CreateTileLocks()
 86661    {
 86662        var locks = new object[TileLockStripes];
 1064314063        for (var i = 0; i < locks.Length; i++) locks[i] = new object();
 64
 86665        return locks;
 86666    }
 67
 68    /// <summary>
 69    /// Returns true if there is already a writer.
 70    /// </summary>
 071    public bool HasWriter => _writer != null;
 72
 73    /// <summary>
 74    /// Gets a writer.
 75    /// </summary>
 76    /// <returns>The writer.</returns>
 77    public RoutingNetworkWriter GetWriter()
 9778    {
 9779        lock (_writeSync)
 9780        {
 9781            if (_writer != null) throw new InvalidOperationException($"Only one writer is allowed at one time." +
 082                                                    $"Check {nameof(this.HasWriter)} for a current writer.");
 9783            if (_tileWriters > 0)
 084            {
 085                throw new InvalidOperationException(
 086                    $"Cannot open a writer while {_tileWriters} tile-insert writer(s) are open.");
 87            }
 88
 9789            _writer = new RoutingNetworkWriter(this);
 9790            return _writer;
 91        }
 9792    }
 93
 94    /// <summary>
 95    /// Gets a writer for inserting a tile, which may run concurrently with other tile inserts.
 96    /// </summary>
 97    /// <remarks>
 98    /// Any number of these may be open at once; none may be open alongside the exclusive
 99    /// <see cref="GetWriter"/>, and vice versa.
 100    ///
 101    /// Safe to use concurrently without taking any lock yourself: the write methods on the
 102    /// returned writer take the tile locks they need, in ascending tile id, which is what keeps
 103    /// concurrent inserts from deadlocking on a shared boundary.
 104    ///
 105    /// Intended for loading tiles into a live network, which is the one write that happens
 106    /// continuously and from many threads. Anything that mutates existing data still wants the
 107    /// exclusive writer.
 108    /// </remarks>
 109    public RoutingNetworkWriter GetTileInsertWriter()
 1870110    {
 1870111        lock (_writeSync)
 1870112        {
 1870113            if (_writer != null)
 0114            {
 0115                throw new InvalidOperationException(
 0116                    "Cannot insert a tile while an exclusive writer is open.");
 117            }
 118
 1870119            _tileWriters++;
 1870120            return new RoutingNetworkWriter(this, exclusive: false);
 121        }
 1870122    }
 123
 124    void IRoutingNetworkWritable.ClearWriter()
 97125    {
 97126        _writer = null;
 97127    }
 128
 129    void IRoutingNetworkWritable.ReleaseTileWriter()
 1870130    {
 1870131        lock (_writeSync)
 1870132        {
 1870133            _tileWriters--;
 1870134        }
 1870135    }
 136
 137    int IRoutingNetworkWritable.TileLockIndex(uint localTileId) =>
 9320138        (int)(localTileId & (TileLockStripes - 1));
 139
 9320140    object IRoutingNetworkWritable.GetTileLockByIndex(int index) => _tileLocks[index];
 141
 142    (NetworkTile tile, Func<IEnumerable<(string key, string value)>, uint> func) IRoutingNetworkWritable.
 143        GetTileForWrite(uint localTileId)
 8453144    {
 145        // No lock here. Every caller already holds this tile's stripe — the write methods on
 146        // RoutingNetworkWriter all go through WithTileLocks, which is where the ordering invariant
 147        // lives. Taking it again was correct (Monitor is re-entrant) but not free, and this is
 148        // called several times per inserted tile.
 149        //
 150        // ensure minimum size.
 8453151        _tiles.EnsureMinimumSize(localTileId);
 152
 8453153        var edgeTypeMap = this.RouterDb.GetEdgeTypeMap();
 8453154        var tile = _tiles[localTileId];
 8453155        if (tile != null)
 8408156        {
 8408157            if (tile.EdgeTypeMapId != edgeTypeMap.id)
 0158            {
 0159                tile = tile.CloneForEdgeTypeMap(edgeTypeMap);
 0160                _tiles[localTileId] = tile;
 0161            }
 162            else
 8408163            {
 164                // check if there is a mutable graph.
 8408165                this.CloneTileIfNeededForMutator(tile);
 8408166            }
 167
 8408168            return (tile, edgeTypeMap.func);
 169        }
 170
 171        // create a new tile.
 45172        tile = new NetworkTile(this.Zoom, localTileId, edgeTypeMap.id);
 45173        _tiles[localTileId] = tile;
 174
 45175        return (tile, edgeTypeMap.func);
 8453176    }
 177
 178    void IRoutingNetworkWritable.SetTile(NetworkTile tile)
 1928179    {
 1928180        var edgeTypeMap = this.RouterDb.GetEdgeTypeMap();
 1928181        if (tile.EdgeTypeMapId != edgeTypeMap.id) throw new ArgumentException("Cannot add an entire tile without a match
 182
 183        // No lock: the caller holds this tile's stripe for the whole write session. Check-then-set
 184        // is still one step under that lock, which is what keeps two inserts of the same tile from
 185        // losing one — though the caller also dedupes in-flight loads per tile, so it should not
 186        // arise.
 187        //
 188        // ensure minimum size.
 1928189        _tiles.EnsureMinimumSize(tile.TileId);
 190
 191        // set tile if not yet there.
 1928192        var existingTile = _tiles[tile.TileId];
 1928193        if (existingTile != null) throw new ArgumentException("Cannot overwrite a tile");
 1928194        _tiles[tile.TileId] = tile;
 1928195    }
 196
 197    private void CloneTileIfNeededForMutator(NetworkTile tile)
 8408198    {
 199        // this is weird right?
 200        //
 201        // the combination these features make this needed:
 202        // - we don't want to clone every tile when we read data in the mutable graph so we use the exiting tiles.
 203        // - a graph can be written to at all times (to lazy load data) but can be mutated at any time too.
 204        //
 205        // this makes it possible the graph is being written to and mutated at the same time.
 206        // we need to check, when writing to a graph, a mutator doesn't have the tile in use or
 207        // data from the write could bleed into the mutator creating an invalid state.
 208        // so **we have to clone tiles before writing to them and give them to the mutator**
 8408209        var mutableGraph = _graphMutator;
 8408210        if (mutableGraph != null && !mutableGraph.HasTile(tile.TileId))
 0211        {
 0212            mutableGraph.SetTile(tile.Clone());
 0213        }
 8408214    }
 215}