| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Linq; |
| | | 4 | | using System.Threading; |
| | | 5 | | using Itinero.Geo; |
| | | 6 | | using Itinero.Network.Enumerators.Edges; |
| | | 7 | | using Itinero.Network.Tiles; |
| | | 8 | | using Itinero.Network.Tiles.Standalone.Global; |
| | | 9 | | // ReSharper disable PossibleMultipleEnumeration |
| | | 10 | | |
| | | 11 | | namespace 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> |
| | | 22 | | public 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 | | |
| | 1967 | 36 | | internal RoutingNetworkWriter(IRoutingNetworkWritable network, bool exclusive = true) |
| | 1967 | 37 | | { |
| | 1967 | 38 | | _network = network; |
| | 1967 | 39 | | _exclusive = exclusive; |
| | 1967 | 40 | | } |
| | | 41 | | |
| | | 42 | | /// <summary> |
| | | 43 | | /// Gets an edge enumerator. |
| | | 44 | | /// </summary> |
| | | 45 | | /// <returns>The enumerator.</returns> |
| | | 46 | | internal RoutingNetworkEdgeEnumerator GetEdgeEnumerator() |
| | 930 | 47 | | { |
| | 930 | 48 | | return _network.GetEdgeEnumerator(); |
| | 930 | 49 | | } |
| | | 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) |
| | 6588 | 86 | | { |
| | | 87 | | // Stripe indices, deduplicated and ascending. Ordering is over STRIPES, not tile ids: |
| | | 88 | | // see IRoutingNetworkWritable.TileLockIndex. |
| | 6588 | 89 | | Span<int> indices = stackalloc int[tileIds.Length]; |
| | 6588 | 90 | | var count = 0; |
| | 38404 | 91 | | foreach (var tileId in tileIds) |
| | 9320 | 92 | | { |
| | 9320 | 93 | | var index = network.TileLockIndex(tileId); |
| | 9320 | 94 | | var insertAt = count; |
| | 10844 | 95 | | while (insertAt > 0 && indices[insertAt - 1] > index) |
| | 1524 | 96 | | { |
| | 1524 | 97 | | indices[insertAt] = indices[insertAt - 1]; |
| | 1524 | 98 | | insertAt--; |
| | 1524 | 99 | | } |
| | | 100 | | |
| | 9320 | 101 | | if (insertAt > 0 && indices[insertAt - 1] == index) continue; |
| | 9320 | 102 | | if (insertAt < count && indices[insertAt] == index) continue; |
| | | 103 | | |
| | 9320 | 104 | | indices[insertAt] = index; |
| | 9320 | 105 | | count++; |
| | 9320 | 106 | | } |
| | | 107 | | |
| | 6588 | 108 | | _taken = count == 0 ? null : new object[count]; |
| | 31816 | 109 | | for (var i = 0; i < count; i++) |
| | 9320 | 110 | | { |
| | 9320 | 111 | | var stripe = network.GetTileLockByIndex(indices[i]); |
| | 9320 | 112 | | Monitor.Enter(stripe); |
| | 9320 | 113 | | _taken[i] = stripe; |
| | 9320 | 114 | | } |
| | 6588 | 115 | | } |
| | | 116 | | |
| | | 117 | | public void Dispose() |
| | 6588 | 118 | | { |
| | 6588 | 119 | | if (_taken == null) return; |
| | | 120 | | |
| | 31816 | 121 | | for (var i = _taken.Length - 1; i >= 0; i--) |
| | 9320 | 122 | | { |
| | 9320 | 123 | | Monitor.Exit(_taken[i]); |
| | 9320 | 124 | | } |
| | 6588 | 125 | | } |
| | | 126 | | } |
| | | 127 | | |
| | | 128 | | /// <summary> |
| | | 129 | | /// Locks every tile a write session will touch, in a deadlock-free order. |
| | | 130 | | /// </summary> |
| | 6588 | 131 | | 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) |
| | 85 | 141 | | { |
| | | 142 | | // get the local tile id. |
| | 85 | 143 | | var (x, y) = TileStatic.WorldToTile(longitude, latitude, _network.Zoom); |
| | 85 | 144 | | var localTileId = TileStatic.ToLocalId(x, y, _network.Zoom); |
| | | 145 | | |
| | | 146 | | // get the tile (or create it). |
| | 85 | 147 | | var (tile, _) = _network.GetTileForWrite(localTileId); |
| | | 148 | | |
| | 85 | 149 | | return tile.AddVertex(longitude, latitude, elevation); |
| | 85 | 150 | | } |
| | | 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) |
| | 1845 | 157 | | { |
| | 1845 | 158 | | if (!_network.TryGetVertex(tail, out var lon1, out var lat1, out var e1)) |
| | 0 | 159 | | { |
| | 0 | 160 | | throw new ArgumentOutOfRangeException(nameof(tail), $"Vertex {tail} not found."); |
| | | 161 | | } |
| | | 162 | | |
| | 1845 | 163 | | if (!_network.TryGetVertex(head, out var lon2, out var lat2, out var e2)) |
| | 0 | 164 | | { |
| | 0 | 165 | | throw new ArgumentOutOfRangeException(nameof(head), $"Vertex {head} not found."); |
| | | 166 | | } |
| | | 167 | | |
| | 1845 | 168 | | return (uint)((lon1, lat1, e1).DistanceEstimateInMeterShape( |
| | 1845 | 169 | | (lon2, lat2, e2), shape) * 100); |
| | 1845 | 170 | | } |
| | | 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) |
| | 1845 | 189 | | { |
| | | 190 | | // get the tile (or create it). |
| | 1845 | 191 | | var (tile, edgeTypeMap) = _network.GetTileForWrite(tail.TileId); |
| | 1845 | 192 | | if (tile == null) throw new ArgumentException($"Cannot add edge with a vertex that doesn't exist."); |
| | | 193 | | |
| | | 194 | | // get the edge type id. |
| | 1845 | 195 | | edgeTypeId ??= attributes != null ? edgeTypeMap(attributes) : null; |
| | | 196 | | |
| | 1845 | 197 | | var edge1 = tile.AddEdge(tail, head, shape, attributes, null, edgeTypeId, length, globalEdgeId); |
| | 1845 | 198 | | if (tail.TileId == head.TileId) |
| | 40 | 199 | | { |
| | 40 | 200 | | return edge1; |
| | | 201 | | } |
| | | 202 | | |
| | | 203 | | // this edge crosses tiles, also add an extra edge to the other tile. |
| | 1805 | 204 | | (tile, _) = _network.GetTileForWrite(head.TileId); |
| | 1805 | 205 | | tile.AddEdge(tail, head, shape, attributes, edge1, edgeTypeId, length, globalEdgeId); |
| | | 206 | | |
| | 1805 | 207 | | return edge1; |
| | 1845 | 208 | | } |
| | | 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) |
| | 930 | 213 | | { |
| | 930 | 214 | | 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. |
| | 930 | 221 | | var tileIds = new List<uint> { vertex.TileId }; |
| | 930 | 222 | | { |
| | 930 | 223 | | var (vertexTile, _) = _network.GetTileForWrite(vertex.TileId); |
| | 930 | 224 | | if (vertexTile == null) |
| | 0 | 225 | | { |
| | 0 | 226 | | throw new ArgumentException($"Cannot add turn costs to a vertex that doesn't exist."); |
| | | 227 | | } |
| | | 228 | | |
| | 930 | 229 | | var scan = new NetworkTileEnumerator(); |
| | 930 | 230 | | scan.MoveTo(vertexTile); |
| | 930 | 231 | | if (scan.MoveTo(vertex)) |
| | 930 | 232 | | { |
| | 2790 | 233 | | while (scan.MoveNext()) |
| | 1860 | 234 | | { |
| | 2790 | 235 | | if (scan.Tail.TileId == scan.Head.TileId) continue; |
| | 930 | 236 | | tileIds.Add(scan.Head.TileId); |
| | 930 | 237 | | } |
| | 930 | 238 | | } |
| | 930 | 239 | | } |
| | | 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. |
| | 930 | 244 | | using var scope = this.LockTiles(System.Runtime.InteropServices.CollectionsMarshal |
| | 930 | 245 | | .AsSpan(tileIds)); |
| | | 246 | | |
| | 930 | 247 | | return this.AddTurnCostsCore(vertex, attributes, edges, costs, prefix, turnCostType); |
| | 930 | 248 | | } |
| | | 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) |
| | 930 | 253 | | { |
| | | 254 | | // get the tile (or create it). |
| | 930 | 255 | | var (tile, _) = _network.GetTileForWrite(vertex.TileId); |
| | 930 | 256 | | if (tile == null) |
| | 0 | 257 | | { |
| | 0 | 258 | | throw new ArgumentException($"Cannot add turn costs to a vertex that doesn't exist."); |
| | | 259 | | } |
| | | 260 | | |
| | | 261 | | // get the turn cost type id. |
| | 930 | 262 | | var turnCostMap = _network.RouterDb.GetTurnCostTypeMap(); |
| | 930 | 263 | | turnCostType ??= turnCostMap.func(attributes); |
| | | 264 | | |
| | | 265 | | // add the turn cost table using the type id. |
| | 930 | 266 | | if (!tile.AddTurnCosts(vertex, turnCostType.Value, edges, costs, attributes, prefix)) |
| | 0 | 267 | | { |
| | 0 | 268 | | 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. |
| | 930 | 273 | | var enumerator = new NetworkTileEnumerator(); |
| | 930 | 274 | | enumerator.MoveTo(tile); |
| | 930 | 275 | | if (enumerator.MoveTo(vertex)) |
| | 930 | 276 | | { |
| | 2790 | 277 | | while (enumerator.MoveNext()) |
| | 1860 | 278 | | { |
| | | 279 | | // only cross-tile edges need syncing. |
| | 2790 | 280 | | if (enumerator.Tail.TileId == enumerator.Head.TileId) continue; |
| | | 281 | | |
| | | 282 | | // Head is always the other vertex (Tail = turn cost vertex we enumerated from). |
| | 930 | 283 | | var (otherTile, _) = _network.GetTileForWrite(enumerator.Head.TileId); |
| | 930 | 284 | | if (otherTile == null) continue; |
| | | 285 | | |
| | | 286 | | // find the same edge in the other tile by iterating from the other vertex. |
| | 930 | 287 | | var otherEnumerator = new NetworkTileEnumerator(); |
| | 930 | 288 | | otherEnumerator.MoveTo(otherTile); |
| | 930 | 289 | | if (!otherEnumerator.MoveTo(enumerator.Head)) continue; |
| | | 290 | | |
| | 930 | 291 | | while (otherEnumerator.MoveNext()) |
| | 930 | 292 | | { |
| | 930 | 293 | | 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 |
| | 930 | 301 | | otherTile.SetTailHeadOrder(otherEnumerator.EdgePointer, |
| | 930 | 302 | | otherEnumerator.Forward ? enumerator.HeadOrder : enumerator.TailOrder, |
| | 930 | 303 | | otherEnumerator.Forward ? enumerator.TailOrder : enumerator.HeadOrder); |
| | 930 | 304 | | break; |
| | | 305 | | } |
| | 930 | 306 | | } |
| | 930 | 307 | | } |
| | | 308 | | |
| | 930 | 309 | | return true; |
| | 930 | 310 | | } |
| | | 311 | | |
| | | 312 | | /// <summary> |
| | | 313 | | /// Shrinks a tile's buffers to what they hold, taking its lock. |
| | | 314 | | /// </summary> |
| | | 315 | | internal void TrimTile(uint localTileId) |
| | 1928 | 316 | | { |
| | 1928 | 317 | | using var scope = this.LockTiles(stackalloc[] { localTileId }); |
| | 1928 | 318 | | var (tile, _) = _network.GetTileForWrite(localTileId); |
| | 1928 | 319 | | tile?.Trim(); |
| | 3856 | 320 | | } |
| | | 321 | | |
| | | 322 | | internal void AddTile(NetworkTile tile) |
| | 1928 | 323 | | { |
| | 1928 | 324 | | _network.SetTile(tile); |
| | 1928 | 325 | | } |
| | | 326 | | |
| | | 327 | | internal bool HasTile(uint localTileId) |
| | 0 | 328 | | { |
| | 0 | 329 | | return _network.HasTile(localTileId); |
| | 0 | 330 | | } |
| | | 331 | | |
| | | 332 | | /// <inheritdoc/> |
| | | 333 | | public void Dispose() |
| | 1967 | 334 | | { |
| | 1967 | 335 | | if (_exclusive) |
| | 97 | 336 | | { |
| | 97 | 337 | | _network.ClearWriter(); |
| | 97 | 338 | | } |
| | | 339 | | else |
| | 1870 | 340 | | { |
| | 1870 | 341 | | _network.ReleaseTileWriter(); |
| | 1870 | 342 | | } |
| | 1967 | 343 | | } |
| | | 344 | | } |