| | | 1 | | using System.Collections.Concurrent; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Linq; |
| | | 4 | | |
| | | 5 | | namespace Itinero.Network.Search.Islands; |
| | | 6 | | |
| | | 7 | | internal class Islands |
| | | 8 | | { |
| | | 9 | | // Read once per edge relaxation from every routing thread, written only |
| | | 10 | | // during classification. ContainsKey takes no lock, so readers never |
| | | 11 | | // contend. The byte value is unused — ConcurrentDictionary is the only |
| | | 12 | | // lock-free set in the framework. |
| | | 13 | | private readonly ConcurrentDictionary<uint, byte> _tiles; // tiles that have been processed. |
| | | 14 | | private readonly ConcurrentDictionary<EdgeId, byte> _islandEdges; |
| | | 15 | | private readonly ConcurrentDictionary<EdgeId, byte> _localEdges; |
| | | 16 | | |
| | | 17 | | // Transient state used during the NonLocal classification pass: each |
| | | 18 | | // edge the classifier identifies as Island in the N-only subgraph is |
| | | 19 | | // recorded here. Once both passes complete and the coordinator has |
| | | 20 | | // computed _localEdges from the gap (NonLocal-Island ∩ NotIsland-Full |
| | | 21 | | // ∩ non-L), this set can be cleared. Not part of the persistent |
| | | 22 | | // storage contract. |
| | | 23 | | private readonly ConcurrentDictionary<EdgeId, byte> _nonLocalIslandEdges; |
| | | 24 | | |
| | 44 | 25 | | internal Islands() |
| | 44 | 26 | | { |
| | 44 | 27 | | _tiles = new ConcurrentDictionary<uint, byte>(); |
| | 44 | 28 | | _islandEdges = new ConcurrentDictionary<EdgeId, byte>(); |
| | 44 | 29 | | _localEdges = new ConcurrentDictionary<EdgeId, byte>(); |
| | 44 | 30 | | _nonLocalIslandEdges = new ConcurrentDictionary<EdgeId, byte>(); |
| | 44 | 31 | | } |
| | | 32 | | |
| | 0 | 33 | | private Islands(IEnumerable<uint> tiles, IEnumerable<EdgeId> islandEdges, IEnumerable<EdgeId> localEdges) |
| | 0 | 34 | | { |
| | 0 | 35 | | _tiles = new ConcurrentDictionary<uint, byte>(tiles.Select(t => new KeyValuePair<uint, byte>(t, 0))); |
| | 0 | 36 | | _islandEdges = new ConcurrentDictionary<EdgeId, byte>(islandEdges.Select(e => new KeyValuePair<EdgeId, byte>(e, |
| | 0 | 37 | | _localEdges = new ConcurrentDictionary<EdgeId, byte>(localEdges.Select(e => new KeyValuePair<EdgeId, byte>(e, 0) |
| | 0 | 38 | | _nonLocalIslandEdges = new ConcurrentDictionary<EdgeId, byte>(); |
| | 0 | 39 | | } |
| | | 40 | | |
| | | 41 | | /// <summary> |
| | | 42 | | /// Sets the tile as done. |
| | | 43 | | /// </summary> |
| | | 44 | | /// <param name="tileId">Sets the tile as done.</param> |
| | | 45 | | /// <returns>True if the tile is done.</returns> |
| | | 46 | | /// <remarks> |
| | | 47 | | /// Called last, after every SetEdgeOnIsland and SetEdgeLocal for the tile. |
| | | 48 | | /// Readers depend on that: a tile seen as done means its edge writes are |
| | | 49 | | /// already visible. |
| | | 50 | | /// </remarks> |
| | | 51 | | public bool SetTileDone(uint tileId) |
| | 64 | 52 | | { |
| | 64 | 53 | | return _tiles.TryAdd(tileId, 0); |
| | 64 | 54 | | } |
| | | 55 | | |
| | | 56 | | /// <summary> |
| | | 57 | | /// Returns true if the given tile is done. |
| | | 58 | | /// </summary> |
| | | 59 | | /// <param name="tileId"></param> |
| | | 60 | | /// <returns></returns> |
| | | 61 | | public bool GetTileDone(uint tileId) |
| | 13551 | 62 | | { |
| | 13551 | 63 | | return _tiles.ContainsKey(tileId); |
| | 13551 | 64 | | } |
| | | 65 | | |
| | | 66 | | /// <summary> |
| | | 67 | | /// Returns true if the given edge is on an island. |
| | | 68 | | /// </summary> |
| | | 69 | | /// <param name="edge"></param> |
| | | 70 | | /// <returns></returns> |
| | | 71 | | public bool IsEdgeOnIsland(EdgeId edge) |
| | 80301 | 72 | | { |
| | 80301 | 73 | | return _islandEdges.ContainsKey(edge); |
| | 80301 | 74 | | } |
| | | 75 | | |
| | | 76 | | /// <summary> |
| | | 77 | | /// Marks the given edge as on an island. |
| | | 78 | | /// </summary> |
| | | 79 | | /// <param name="edge"></param> |
| | | 80 | | /// <returns></returns> |
| | | 81 | | public bool SetEdgeOnIsland(EdgeId edge) |
| | 25 | 82 | | { |
| | 25 | 83 | | return _islandEdges.TryAdd(edge, 0); |
| | 25 | 84 | | } |
| | | 85 | | |
| | | 86 | | /// <summary> |
| | | 87 | | /// Kind-aware overload. Reads from <c>_islandEdges</c> for Full and from |
| | | 88 | | /// the transient <c>_nonLocalIslandEdges</c> for NonLocal. The latter is |
| | | 89 | | /// only meaningful while a NonLocal classification pass is in progress |
| | | 90 | | /// or hasn't been collapsed into <c>_localEdges</c> yet. |
| | | 91 | | /// </summary> |
| | | 92 | | public bool IsEdgeOnIsland(EdgeId edge, IslandKind kind) |
| | 8 | 93 | | { |
| | 8 | 94 | | if (kind == IslandKind.NonLocal) |
| | 4 | 95 | | { |
| | 4 | 96 | | return _nonLocalIslandEdges.ContainsKey(edge); |
| | | 97 | | } |
| | | 98 | | |
| | 4 | 99 | | return this.IsEdgeOnIsland(edge); |
| | 8 | 100 | | } |
| | | 101 | | |
| | | 102 | | /// <summary> |
| | | 103 | | /// Kind-aware overload. Writes to <c>_islandEdges</c> for Full and to the |
| | | 104 | | /// transient <c>_nonLocalIslandEdges</c> for NonLocal. |
| | | 105 | | /// </summary> |
| | | 106 | | public bool SetEdgeOnIsland(EdgeId edge, IslandKind kind) |
| | 0 | 107 | | { |
| | 0 | 108 | | if (kind == IslandKind.NonLocal) |
| | 0 | 109 | | { |
| | 0 | 110 | | return _nonLocalIslandEdges.TryAdd(edge, 0); |
| | | 111 | | } |
| | | 112 | | |
| | 0 | 113 | | return this.SetEdgeOnIsland(edge); |
| | 0 | 114 | | } |
| | | 115 | | |
| | | 116 | | /// <summary> |
| | | 117 | | /// Discards the transient <c>_nonLocalIslandEdges</c> set used during |
| | | 118 | | /// NonLocal classification. Called by the build coordinator after |
| | | 119 | | /// <c>_localEdges</c> has been computed from the gap. After this, the |
| | | 120 | | /// only persistent state is <c>_islandEdges</c> and <c>_localEdges</c>. |
| | | 121 | | /// </summary> |
| | | 122 | | internal void ClearNonLocalIslandEdges() |
| | 0 | 123 | | { |
| | 0 | 124 | | _nonLocalIslandEdges.Clear(); |
| | 0 | 125 | | } |
| | | 126 | | |
| | | 127 | | /// <summary> |
| | | 128 | | /// Returns true if the edge is reachable but only via local-access edges — |
| | | 129 | | /// i.e. it is not an island, but every route to it from the main network |
| | | 130 | | /// crosses at least one L-tagged edge first. A typical example is an |
| | | 131 | | /// N-tagged road inside a residential subdivision whose only connection |
| | | 132 | | /// to the main road network goes through an <c>access=destination</c> |
| | | 133 | | /// gate road. |
| | | 134 | | /// |
| | | 135 | | /// L-tagged edges themselves are NOT stored here — they are recognised |
| | | 136 | | /// by their tag, which is build-time information on <c>EdgeFactor</c>. |
| | | 137 | | /// </summary> |
| | | 138 | | public bool IsEdgeLocal(EdgeId edge) |
| | 77556 | 139 | | { |
| | 77556 | 140 | | return _localEdges.ContainsKey(edge); |
| | 77556 | 141 | | } |
| | | 142 | | |
| | | 143 | | /// <summary> |
| | | 144 | | /// Marks the given edge as reachable only via local-access edges. See |
| | | 145 | | /// <see cref="IsEdgeLocal"/> for what that means. |
| | | 146 | | /// </summary> |
| | | 147 | | public bool SetEdgeLocal(EdgeId edge) |
| | 7 | 148 | | { |
| | 7 | 149 | | return _localEdges.TryAdd(edge, 0); |
| | 7 | 150 | | } |
| | | 151 | | |
| | | 152 | | internal Islands Clone() |
| | 0 | 153 | | { |
| | | 154 | | // Snapshot _tiles before the edge sets, so a tile seen as done always |
| | | 155 | | // comes with its edges. Reversed, the clone could hold a done tile whose |
| | | 156 | | // island edges are missing, which IsMainN reads as main-N. |
| | 0 | 157 | | var tiles = _tiles.Keys; |
| | 0 | 158 | | return new Islands(tiles, _islandEdges.Keys, _localEdges.Keys); |
| | 0 | 159 | | } |
| | | 160 | | } |