< Summary

Class:Itinero.Network.Search.Islands.RoutingNetworkIslandManager
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Islands/RoutingNetworkIslandManager.cs
Covered lines:86
Uncovered lines:25
Coverable lines:111
Total lines:242
Line coverage:77.4% (86 of 111)
Covered branches:18
Total branches:28
Branch coverage:64.2% (18 of 28)
Tag:275_35836194538

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%1100%
GetBuildSerialiser(...)100%10%
.ctor(...)100%1100%
IsEdgeOnIsland(...)100%10%
IsEdgeOnIsland(...)0%80%
GetOrCreateDirectedGraph(...)100%2100%
get_MaxIslandSize()100%1100%
TryGetIslandsFor(...)100%10%
GetIslandsFor(...)100%1100%
IsMainN(...)100%10100%
BuildForTileAsync()75%4100%
Clone()50%262.5%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Islands/RoutingNetworkIslandManager.cs

#LineLine coverage
 1using System;
 2using System.Collections.Concurrent;
 3using System.Collections.Generic;
 4using System.Diagnostics.CodeAnalysis;
 5using System.Threading;
 6using System.Threading.Tasks;
 7using Itinero.Profiles;
 8
 9namespace Itinero.Network.Search.Islands;
 10
 11internal class RoutingNetworkIslandManager
 12{
 13    // Concurrent: every snap enters BuildForTileAsync, and a ReaderWriterLockSlim
 14    // admits only one upgradeable reader at a time, so guarding this dictionary
 15    // with one serialised every snapping thread against every other — including
 16    // threads asking about entirely different tiles.
 62017    private readonly ConcurrentDictionary<(string profile, uint tile), Lazy<Task>> _tilesInProgress = new();
 18
 19    // Looked up once per edge relaxation (IsMainN); concurrent so that lookup
 20    // takes no lock.
 21    private readonly ConcurrentDictionary<string, Islands> _islands;
 22
 62023    private readonly Dictionary<(string profile, IslandKind kind), IslandDirectedGraph> _directedGraphs = new();
 62024    private readonly ReaderWriterLockSlim _directedGraphsLock = new();
 25
 26    // Per-profile semaphore that serialises IslandClassifier.BuildForTileAsync
 27    // calls against each other for the same profile. The shared Full+NonLocal
 28    // dgs are reset to their initial state at the end of each call (per spec);
 29    // running two classifications for the same profile concurrently would let
 30    // one wipe the other's working state mid-flight. Different profiles still
 31    // run in parallel — each has its own dg pair and its own semaphore.
 62032    private readonly ConcurrentDictionary<string, SemaphoreSlim> _buildSerialisers = new();
 33
 34    internal SemaphoreSlim GetBuildSerialiser(string profileName) =>
 035        _buildSerialisers.GetOrAdd(profileName, _ => new SemaphoreSlim(1, 1));
 36
 35537    internal RoutingNetworkIslandManager(int maxIslandSize)
 35538    {
 35539        this.MaxIslandSize = maxIslandSize;
 35540        _islands = new ConcurrentDictionary<string, Islands>();
 35541    }
 42
 26543    private RoutingNetworkIslandManager(int maxIslandSize, ConcurrentDictionary<string, Islands> islands)
 26544    {
 26545        this.MaxIslandSize = maxIslandSize;
 26546        _islands = islands;
 26547    }
 48
 49    /// <summary>
 50    /// Checks if an edge is on an island using the directed graph.
 51    /// Returns true if island, false if not island, null if inconclusive.
 52    /// </summary>
 53    internal bool? IsEdgeOnIsland(Profile profile, EdgeId edgeId) =>
 054        this.IsEdgeOnIsland(profile.Name, edgeId);
 55
 56    internal bool? IsEdgeOnIsland(string profileName, EdgeId edgeId)
 057    {
 58        // Snapping is a Full-classification concern, so the existing
 59        // single-DG semantics route through the Full DG.
 60        IslandDirectedGraph? dg;
 61        try
 062        {
 063            _directedGraphsLock.EnterReadLock();
 64
 065            if (!_directedGraphs.TryGetValue((profileName, IslandKind.Full), out dg))
 066                return null;
 067        }
 68        finally
 069        {
 070            _directedGraphsLock.ExitReadLock();
 071        }
 72
 73        // The lock covers the dictionary lookup only; dg's own reads and
 74        // _islands need no lock.
 075        if (!_islands.TryGetValue(profileName, out var profileIslands))
 076            return null;
 077        if (profileIslands.IsEdgeOnIsland(edgeId))
 078            return true;
 79
 080        if (dg.IsNotIsland(edgeId))
 081            return false;
 82
 083        return null;
 084    }
 85
 86    internal IslandDirectedGraph GetOrCreateDirectedGraph(Profile profile, IslandKind kind = IslandKind.Full)
 587    {
 588        var key = (profile.Name, kind);
 89        try
 590        {
 591            _directedGraphsLock.EnterUpgradeableReadLock();
 92
 693            if (_directedGraphs.TryGetValue(key, out var dg)) return dg;
 94
 95            try
 496            {
 497                _directedGraphsLock.EnterWriteLock();
 98
 499                dg = new IslandDirectedGraph();
 4100                _directedGraphs[key] = dg;
 4101                return dg;
 102            }
 103            finally
 4104            {
 4105                _directedGraphsLock.ExitWriteLock();
 4106            }
 107        }
 108        finally
 5109        {
 5110            _directedGraphsLock.ExitUpgradeableReadLock();
 5111        }
 5112    }
 113
 2782114    internal int MaxIslandSize { get; }
 115
 116    internal bool TryGetIslandsFor(string profileName, out Islands islands)
 0117    {
 0118        return _islands.TryGetValue(profileName, out islands);
 0119    }
 120
 121    internal Islands GetIslandsFor(Profile profile)
 2433122    {
 123        // The factory can run more than once under a race, but only one instance
 124        // is published and every caller gets that one.
 2477125        return _islands.GetOrAdd(profile.Name, _ => new Islands());
 2433126    }
 127
 128    /// <summary>
 129    /// Returns whether the edge is in the profile's main-N component — the
 130    /// dominant SCC of the N-only subgraph, i.e. the "mainland" without
 131    /// L-edges.
 132    ///
 133    /// <list type="bullet">
 134    /// <item><c>true</c>: edge is in main-N. Default for any edge in a done tile
 135    /// that is neither L-tagged, on an island, nor a non-main-N pocket member.</item>
 136    /// <item><c>false</c>: edge is not in main-N. Either L-tagged (passed in via
 137    /// <paramref name="isLocalAccess"/>), on an island (unreachable in Full), or
 138    /// recorded as a local edge (non-main-N pocket).</item>
 139    /// <item><c>null</c>: classification has not yet produced a verdict for this
 140    /// tile.</item>
 141    /// </list>
 142    ///
 143    /// The L-tag check is tag-driven and resolved by the caller (typically via
 144    /// the cost function's <c>localAccess</c> field on the result of <c>Get</c>),
 145    /// then passed in. The manager itself does not consult any tag storage.
 146    /// </summary>
 147    internal bool? IsMainN(Profile profile, EdgeId edgeId, bool isLocalAccess)
 788377148    {
 149        // L-tagged edge — never main-N, no storage lookup needed.
 788379150        if (isLocalAccess) return false;
 151
 1568830152        if (!_islands.TryGetValue(profile.Name, out var islands)) return null;
 153
 154        // Read the tile flag before the edge sets: the classifier marks a tile
 155        // done only after writing its island and local edges, so a tile seen as
 156        // done guarantees the edge reads below see those writes. Sampling the
 157        // edge sets first would let a not-yet-written island edge pair with a
 158        // tile marked done since, reporting main-N for an edge on an island.
 7920159        var tileDone = islands.GetTileDone(edgeId.TileId);
 160
 161        // Unreachable in the Full classification → not in main-N.
 7921162        if (islands.IsEdgeOnIsland(edgeId)) return false;
 163
 164        // Non-main-N pocket → not in main-N.
 7920165        if (islands.IsEdgeLocal(edgeId)) return false;
 166
 167        // Tile finished classifying and the edge is in neither set → main-N.
 168        // Otherwise we don't yet know.
 7918169        return tileDone ? true : null;
 788377170    }
 171
 172    internal async Task BuildForTileAsync(RoutingNetwork network, Profile profile, uint tileId,
 173        IslandDirectedGraph dgFull, IslandDirectedGraph dgNonLocal,
 174        CancellationToken cancellationToken)
 7175    {
 176        // Already classified: nothing to queue and nothing to await. Checked
 177        // before touching the queue because a classified tile is the common case
 178        // once a region is warm, and everything below costs more than this does.
 179        // IslandClassifier.BuildForTileAsync makes the same check first, so this
 180        // only moves it earlier. GetTileDone is a concurrent-set lookup.
 7181        if (this.GetIslandsFor(profile).GetTileDone(tileId)) return;
 182
 7183        var key = (profile.Name, tileId);
 184
 7185        if (!_tilesInProgress.TryGetValue(key, out var pending))
 7186        {
 187            // Lazy, not a bare Task: GetOrAdd may invoke a factory more than
 188            // once under a race, and starting a tile's classification twice
 189            // would put a second run behind the per-profile serialiser for work
 190            // already being done. Only the Lazy that wins publication ever has
 191            // Value read, so the classification starts exactly once.
 7192            Lazy<Task>? mine = null;
 7193            mine = new Lazy<Task>(() =>
 7194            {
 7195                // CancellationToken.None, deliberately: this task is shared with every later
 7196                // caller for the same tile, so it must not carry the token of whoever happened
 7197                // to ask first. Passing that token let one caller going away cancel the work
 7198                // everyone else was waiting on — and, because the entry was only removed
 7199                // after a successful await, the cancelled task stayed in the dictionary and was
 7200                // handed to every subsequent caller, each of which got an
 7201                // OperationCanceledException for a request it never cancelled. That poisoned
 7202                // the tile for the lifetime of the network. Callers stay cancellable through
 7203                // their own WaitAsync below.
 7204                // The graphs belong to whichever request wins publication. A caller that
 7205                // merely awaits this task does not get them populated — but the tile is
 7206                // done by then, so its durable Islands entry answers instead.
 7207                var started = IslandClassifier.BuildForTileAsync(network, profile, tileId,
 7208                    dgFull, dgNonLocal, CancellationToken.None);
 7209
 7210                // Remove on completion whatever the outcome, so a task that failed is retried by
 7211                // the next caller rather than replayed at it forever. Removal is matched on this
 7212                // exact Lazy: if a later caller has already published a replacement, a stale
 7213                // continuation must not evict it and let a third caller start a duplicate run.
 7214                _ = started.ContinueWith(
 7215                    _ => _tilesInProgress.TryRemove(
 7216                        new KeyValuePair<(string profile, uint tile), Lazy<Task>>(key, mine!)),
 7217                    TaskContinuationOptions.ExecuteSynchronously);
 7218
 7219                return started;
 14220            });
 221
 7222            pending = _tilesInProgress.GetOrAdd(key, mine);
 7223        }
 224
 225        // Await the shared task, but only for as long as this caller is still interested. Giving up
 226        // here does not stop the classification for anyone else.
 7227        await pending.Value.WaitAsync(cancellationToken);
 7228    }
 229
 230    internal RoutingNetworkIslandManager Clone()
 265231    {
 232        // A profile added while iterating may or may not make it into the clone;
 233        // either is correct, it was not part of the network being cloned.
 265234        var islands = new ConcurrentDictionary<string, Islands>();
 795235        foreach (var (profileName, profileIslands) in _islands)
 0236        {
 0237            islands[profileName] = profileIslands.Clone();
 0238        }
 239
 265240        return new RoutingNetworkIslandManager(this.MaxIslandSize, islands);
 265241    }
 242}
Generated by: ReportGenerator 4.8.2.0
09/23/2026 - 08:18:38
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
GetBuildSerialiser(...)
.ctor(...)
IsEdgeOnIsland(...)
IsEdgeOnIsland(...)
GetOrCreateDirectedGraph(...)
get_MaxIslandSize()
TryGetIslandsFor(...)
GetIslandsFor(...)
IsMainN(...)
BuildForTileAsync()
Clone()