< Summary

Class:Itinero.Network.Writer.RoutingNetworkWriter
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/Writer/RoutingNetworkWriter.cs
Covered lines:132
Uncovered lines:13
Coverable lines:145
Total lines:344
Line coverage:91% (132 of 145)
Covered branches:64
Total branches:72
Branch coverage:88.8% (64 of 72)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%1100%
GetEdgeEnumerator()100%1100%
.ctor(...)94.44%18100%
Dispose()100%4100%
LockTiles(...)100%1100%
AddVertex(...)100%1100%
ComputeEdgeLength(...)50%460%
AddEdge(...)87.5%8100%
AddTurnCosts(...)80%1091.3%
AddTurnCostsCore(...)91.66%2487.87%
TrimTile(...)100%2100%
AddTile(...)100%1100%
HasTile(...)100%10%
Dispose()100%2100%

File(s)

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

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Linq;
 4using System.Threading;
 5using Itinero.Geo;
 6using Itinero.Network.Enumerators.Edges;
 7using Itinero.Network.Tiles;
 8using Itinero.Network.Tiles.Standalone.Global;
 9// ReSharper disable PossibleMultipleEnumeration
 10
 11namespace Itinero.Network.Writer;
 12
 13/// <summary>
 14/// A writer to write to a network. This writer will never change existing data, only add new data.
 15///
 16/// This writer can:
 17/// - add new vertices
 18/// - add new edges.
 19///
 20/// This writer cannot mutate existing data, only add new.
 21/// </summary>
 22public class RoutingNetworkWriter : IDisposable
 23{
 24    private readonly IRoutingNetworkWritable _network;
 25
 26    /// <summary>
 27    /// Whether this writer holds the network's exclusive write slot.
 28    /// </summary>
 29    /// <remarks>
 30    /// False for tile-insert writers, of which there can be many at once. They are excluded from
 31    /// the exclusive slot rather than sharing it, so disposing one must not release a slot it
 32    /// never took — that would let a mutator open while inserts are still running.
 33    /// </remarks>
 34    private readonly bool _exclusive;
 35
 196736    internal RoutingNetworkWriter(IRoutingNetworkWritable network, bool exclusive = true)
 196737    {
 196738        _network = network;
 196739        _exclusive = exclusive;
 196740    }
 41
 42    /// <summary>
 43    /// Gets an edge enumerator.
 44    /// </summary>
 45    /// <returns>The enumerator.</returns>
 46    internal RoutingNetworkEdgeEnumerator GetEdgeEnumerator()
 93047    {
 93048        return _network.GetEdgeEnumerator();
 93049    }
 50
 51    /// <summary>
 52    /// Runs <paramref name="write"/> holding the lock of every tile it may write.
 53    /// </summary>
 54    /// <remarks>
 55    /// Always ascending by tile id, and that is the single rule keeping concurrent insertion
 56    /// deadlock-free. It only works if EVERY acquisition anywhere follows it: two writes that
 57    /// each hold one of the same pair and wait for the other is the only cycle available here, and
 58    /// a consistent global order makes it unconstructable.
 59    ///
 60    /// The set is passed in rather than discovered while locking, because a write that finds out
 61    /// which tiles it needs as it goes cannot order them.
 62    ///
 63    /// Monitor is re-entrant, so nesting these (a caller that already holds one of the locks) is
 64    /// free rather than a self-deadlock.
 65    /// </remarks>
 66    /// <summary>
 67    /// Holds the write locks for a set of tiles until disposed.
 68    /// </summary>
 69    /// <remarks>
 70    /// Taken ONCE around all of a tile's writes, not per write. An earlier version locked inside
 71    /// every <c>AddEdge</c>/<c>AddVertex</c> call, which is the wrong granularity: the cost of
 72    /// acquiring and releasing, plus a closure and an array per call, is paid on every edge while
 73    /// the work it protects is a few array writes. That measured as roughly a third more CPU per
 74    /// route than serialised insertion, for identical output.
 75    ///
 76    /// The whole set must be passed at once. Acquiring one stripe and then reaching for another is
 77    /// what creates cycles — a caller holding its own tile's stripe and then asking for a
 78    /// partner's can deadlock against the mirror-image insert — so every lock a write session
 79    /// needs has to be known before the first one is taken.
 80    /// </remarks>
 81    internal readonly struct TileWriteScope : IDisposable
 82    {
 83        private readonly object[]? _taken;
 84
 85        internal TileWriteScope(IRoutingNetworkWritable network, ReadOnlySpan<uint> tileIds)
 658886        {
 87            // Stripe indices, deduplicated and ascending. Ordering is over STRIPES, not tile ids:
 88            // see IRoutingNetworkWritable.TileLockIndex.
 658889            Span<int> indices = stackalloc int[tileIds.Length];
 658890            var count = 0;
 3840491            foreach (var tileId in tileIds)
 932092            {
 932093                var index = network.TileLockIndex(tileId);
 932094                var insertAt = count;
 1084495                while (insertAt > 0 && indices[insertAt - 1] > index)
 152496                {
 152497                    indices[insertAt] = indices[insertAt - 1];
 152498                    insertAt--;
 152499                }
 100
 9320101                if (insertAt > 0 && indices[insertAt - 1] == index) continue;
 9320102                if (insertAt < count && indices[insertAt] == index) continue;
 103
 9320104                indices[insertAt] = index;
 9320105                count++;
 9320106            }
 107
 6588108            _taken = count == 0 ? null : new object[count];
 31816109            for (var i = 0; i < count; i++)
 9320110            {
 9320111                var stripe = network.GetTileLockByIndex(indices[i]);
 9320112                Monitor.Enter(stripe);
 9320113                _taken[i] = stripe;
 9320114            }
 6588115        }
 116
 117        public void Dispose()
 6588118        {
 6588119            if (_taken == null) return;
 120
 31816121            for (var i = _taken.Length - 1; i >= 0; i--)
 9320122            {
 9320123                Monitor.Exit(_taken[i]);
 9320124            }
 6588125        }
 126    }
 127
 128    /// <summary>
 129    /// Locks every tile a write session will touch, in a deadlock-free order.
 130    /// </summary>
 6588131    internal TileWriteScope LockTiles(ReadOnlySpan<uint> tileIds) => new(_network, tileIds);
 132
 133    /// <summary>
 134    /// Adds a new vertex.
 135    /// </summary>
 136    /// <param name="longitude">The longitude.</param>
 137    /// <param name="latitude">The latitude.</param>
 138    /// <param name="elevation">The elevation.</param>
 139    /// <returns>The vertex id.</returns>
 140    public VertexId AddVertex(double longitude, double latitude, float? elevation = null)
 85141    {
 142        // get the local tile id.
 85143        var (x, y) = TileStatic.WorldToTile(longitude, latitude, _network.Zoom);
 85144        var localTileId = TileStatic.ToLocalId(x, y, _network.Zoom);
 145
 146        // get the tile (or create it).
 85147        var (tile, _) = _network.GetTileForWrite(localTileId);
 148
 85149        return tile.AddVertex(longitude, latitude, elevation);
 85150    }
 151
 152    /// <summary>
 153    /// Computes the edge length in centimeters from vertex locations and shape.
 154    /// </summary>
 155    public uint ComputeEdgeLength(VertexId tail, VertexId head,
 156        IEnumerable<(double longitude, double latitude, float? e)>? shape = null)
 1845157    {
 1845158        if (!_network.TryGetVertex(tail, out var lon1, out var lat1, out var e1))
 0159        {
 0160            throw new ArgumentOutOfRangeException(nameof(tail), $"Vertex {tail} not found.");
 161        }
 162
 1845163        if (!_network.TryGetVertex(head, out var lon2, out var lat2, out var e2))
 0164        {
 0165            throw new ArgumentOutOfRangeException(nameof(head), $"Vertex {head} not found.");
 166        }
 167
 1845168        return (uint)((lon1, lat1, e1).DistanceEstimateInMeterShape(
 1845169            (lon2, lat2, e2), shape) * 100);
 1845170    }
 171
 172    /// <summary>
 173    /// Adds a new edge.
 174    /// </summary>
 175    /// <param name="tail">The tail vertex.</param>
 176    /// <param name="head">The head vertex.</param>
 177    /// <param name="shape">The shape, if any.</param>
 178    /// <param name="attributes">The attributes, if any.</param>
 179    /// <param name="edgeTypeId">The edge type id, if any.</param>
 180    /// <param name="length">The length in centimeters. Use <see cref="ComputeEdgeLength"/> if not known.</param>
 181    /// <param name="globalEdgeId">The global edge id, if any.</param>
 182    /// <returns></returns>
 183    /// <exception cref="ArgumentException"></exception>
 184    /// <exception cref="ArgumentOutOfRangeException"></exception>
 185    public EdgeId AddEdge(VertexId tail, VertexId head,
 186        IEnumerable<(double longitude, double latitude, float? e)>? shape,
 187        IEnumerable<(string key, string value)>? attributes, uint? edgeTypeId,
 188        uint length, GlobalEdgeId? globalEdgeId = null)
 1845189    {
 190        // get the tile (or create it).
 1845191        var (tile, edgeTypeMap) = _network.GetTileForWrite(tail.TileId);
 1845192        if (tile == null) throw new ArgumentException($"Cannot add edge with a vertex that doesn't exist.");
 193
 194        // get the edge type id.
 1845195        edgeTypeId ??= attributes != null ? edgeTypeMap(attributes) : null;
 196
 1845197        var edge1 = tile.AddEdge(tail, head, shape, attributes, null, edgeTypeId, length, globalEdgeId);
 1845198        if (tail.TileId == head.TileId)
 40199        {
 40200            return edge1;
 201        }
 202
 203        // this edge crosses tiles, also add an extra edge to the other tile.
 1805204        (tile, _) = _network.GetTileForWrite(head.TileId);
 1805205        tile.AddEdge(tail, head, shape, attributes, edge1, edgeTypeId, length, globalEdgeId);
 206
 1805207        return edge1;
 1845208    }
 209
 210    /// Returns false when the vertex has no order budget left, see OrderCoder.
 211    public bool AddTurnCosts(VertexId vertex, IEnumerable<(string key, string value)> attributes,
 212        EdgeId[] edges, uint[,] costs, IEnumerable<EdgeId>? prefix, uint? turnCostType = null)
 930213    {
 930214        prefix ??= ArraySegment<EdgeId>.Empty;
 215
 216        // Which tiles this will write, decided before any lock is taken. Beyond the vertex's own
 217        // tile, the order bytes are synced into every neighbouring tile that shares a cross-tile
 218        // edge at this vertex — so the set is not predictable from the vertex alone and has to be
 219        // read off the network first. A write that discovered these while already holding locks
 220        // could not order them, and ordering is the whole deadlock argument.
 930221        var tileIds = new List<uint> { vertex.TileId };
 930222        {
 930223            var (vertexTile, _) = _network.GetTileForWrite(vertex.TileId);
 930224            if (vertexTile == null)
 0225            {
 0226                throw new ArgumentException($"Cannot add turn costs to a vertex that doesn't exist.");
 227            }
 228
 930229            var scan = new NetworkTileEnumerator();
 930230            scan.MoveTo(vertexTile);
 930231            if (scan.MoveTo(vertex))
 930232            {
 2790233                while (scan.MoveNext())
 1860234                {
 2790235                    if (scan.Tail.TileId == scan.Head.TileId) continue;
 930236                    tileIds.Add(scan.Head.TileId);
 930237                }
 930238            }
 930239        }
 240
 241        // Locks here rather than at the caller, because which tiles this touches is only
 242        // discoverable by reading the network. Restrictions are rare compared to edges, so paying
 243        // per call is acceptable where it would not be for AddEdge.
 930244        using var scope = this.LockTiles(System.Runtime.InteropServices.CollectionsMarshal
 930245            .AsSpan(tileIds));
 246
 930247        return this.AddTurnCostsCore(vertex, attributes, edges, costs, prefix, turnCostType);
 930248    }
 249
 250    /// The turn-cost write itself. Caller holds every tile lock it touches.
 251    private bool AddTurnCostsCore(VertexId vertex, IEnumerable<(string key, string value)> attributes,
 252        EdgeId[] edges, uint[,] costs, IEnumerable<EdgeId> prefix, uint? turnCostType)
 930253    {
 254        // get the tile (or create it).
 930255        var (tile, _) = _network.GetTileForWrite(vertex.TileId);
 930256        if (tile == null)
 0257        {
 0258            throw new ArgumentException($"Cannot add turn costs to a vertex that doesn't exist.");
 259        }
 260
 261        // get the turn cost type id.
 930262        var turnCostMap = _network.RouterDb.GetTurnCostTypeMap();
 930263        turnCostType ??= turnCostMap.func(attributes);
 264
 265        // add the turn cost table using the type id.
 930266        if (!tile.AddTurnCosts(vertex, turnCostType.Value, edges, costs, attributes, prefix))
 0267        {
 0268            return false;
 269        }
 270
 271        // for cross-tile edges, the order was set on this tile's copy.
 272        // sync the order to the other tile's copy so routing from either side sees it.
 930273        var enumerator = new NetworkTileEnumerator();
 930274        enumerator.MoveTo(tile);
 930275        if (enumerator.MoveTo(vertex))
 930276        {
 2790277            while (enumerator.MoveNext())
 1860278            {
 279                // only cross-tile edges need syncing.
 2790280                if (enumerator.Tail.TileId == enumerator.Head.TileId) continue;
 281
 282                // Head is always the other vertex (Tail = turn cost vertex we enumerated from).
 930283                var (otherTile, _) = _network.GetTileForWrite(enumerator.Head.TileId);
 930284                if (otherTile == null) continue;
 285
 286                // find the same edge in the other tile by iterating from the other vertex.
 930287                var otherEnumerator = new NetworkTileEnumerator();
 930288                otherEnumerator.MoveTo(otherTile);
 930289                if (!otherEnumerator.MoveTo(enumerator.Head)) continue;
 290
 930291                while (otherEnumerator.MoveNext())
 930292                {
 930293                    if (otherEnumerator.EdgeId != enumerator.EdgeId) continue;
 294
 295                    // found the same edge — copy the order bytes.
 296                    // SetTailHeadOrder takes STORED tail/head orders (for vertex1/vertex2 as encoded).
 297                    // enumerator.TailOrder = order at turn cost vertex, HeadOrder = order at other vertex.
 298                    // Map these to stored positions based on otherEnumerator.Forward:
 299                    // Forward=true: vertex1=otherVertex → stored tail=HeadOrder, stored head=TailOrder
 300                    // Forward=false: vertex1=turnCostVertex → stored tail=TailOrder, stored head=HeadOrder
 930301                    otherTile.SetTailHeadOrder(otherEnumerator.EdgePointer,
 930302                        otherEnumerator.Forward ? enumerator.HeadOrder : enumerator.TailOrder,
 930303                        otherEnumerator.Forward ? enumerator.TailOrder : enumerator.HeadOrder);
 930304                    break;
 305                }
 930306            }
 930307        }
 308
 930309        return true;
 930310    }
 311
 312    /// <summary>
 313    /// Shrinks a tile's buffers to what they hold, taking its lock.
 314    /// </summary>
 315    internal void TrimTile(uint localTileId)
 1928316    {
 1928317        using var scope = this.LockTiles(stackalloc[] { localTileId });
 1928318        var (tile, _) = _network.GetTileForWrite(localTileId);
 1928319        tile?.Trim();
 3856320    }
 321
 322    internal void AddTile(NetworkTile tile)
 1928323    {
 1928324        _network.SetTile(tile);
 1928325    }
 326
 327    internal bool HasTile(uint localTileId)
 0328    {
 0329        return _network.HasTile(localTileId);
 0330    }
 331
 332    /// <inheritdoc/>
 333    public void Dispose()
 1967334    {
 1967335        if (_exclusive)
 97336        {
 97337            _network.ClearWriter();
 97338        }
 339        else
 1870340        {
 1870341            _network.ReleaseTileWriter();
 1870342        }
 1967343    }
 344}