| | | 1 | | using System; |
| | | 2 | | using System.Collections; |
| | | 3 | | using System.Collections.Generic; |
| | | 4 | | using System.Runtime.CompilerServices; |
| | | 5 | | using Itinero.Network; |
| | | 6 | | using Itinero.Network.Tiles.Standalone.Global; |
| | | 7 | | |
| | | 8 | | namespace Itinero.Data; |
| | | 9 | | |
| | | 10 | | /// <summary> |
| | | 11 | | /// A global id set mapping global edge ids to local edge ids. |
| | | 12 | | /// </summary> |
| | | 13 | | /// <remarks> |
| | | 14 | | /// Open-addressed over flat arrays instead of a dictionary: at one write per forward internal edge |
| | | 15 | | /// of every inserted tile, a node per entry means an allocation plus a random-address probe. |
| | | 16 | | /// </remarks> |
| | | 17 | | public sealed class GlobalEdgeIdSet : IEnumerable<(GlobalEdgeId globalId, EdgeId edgeId)> |
| | | 18 | | { |
| | | 19 | | // Well above the core count so a resize, which holds one stripe for a rehash, blocks a small |
| | | 20 | | // fraction of writers rather than all of them. |
| | | 21 | | private const int Stripes = 64; |
| | | 22 | | |
| | | 23 | | private const int StripeMask = Stripes - 1; |
| | | 24 | | |
| | | 25 | | // Sized so the whole table starts around 2^20 slots, reached without rehashing. |
| | | 26 | | private const int InitialStripeCapacity = 1 << 14; |
| | | 27 | | |
| | | 28 | | // Keys unpacked rather than kept as a GlobalEdgeId so a probe compares a long first and only |
| | | 29 | | // looks at the node indices on a hit. |
| | | 30 | | private sealed class Stripe |
| | | 31 | | { |
| | 8064 | 32 | | public long[] Ways = new long[InitialStripeCapacity]; |
| | 8064 | 33 | | public ushort[] Tails = new ushort[InitialStripeCapacity]; |
| | 8064 | 34 | | public ushort[] Heads = new ushort[InitialStripeCapacity]; |
| | 8064 | 35 | | public uint[] TileIds = new uint[InitialStripeCapacity]; |
| | 8064 | 36 | | public uint[] LocalIds = new uint[InitialStripeCapacity]; |
| | | 37 | | |
| | | 38 | | // Its own array because any key value is legal, including zero. |
| | 8064 | 39 | | public bool[] Occupied = new bool[InitialStripeCapacity]; |
| | | 40 | | |
| | | 41 | | public int Count; |
| | | 42 | | } |
| | | 43 | | |
| | 126 | 44 | | private readonly Stripe[] _stripes = CreateStripes(); |
| | | 45 | | |
| | | 46 | | private static Stripe[] CreateStripes() |
| | 126 | 47 | | { |
| | 126 | 48 | | var stripes = new Stripe[Stripes]; |
| | 24444 | 49 | | for (var s = 0; s < Stripes; s++) stripes[s] = new Stripe(); |
| | | 50 | | |
| | 126 | 51 | | return stripes; |
| | 126 | 52 | | } |
| | | 53 | | |
| | | 54 | | // Stripe from the high bits, slot from the low bits, so the two are independent. |
| | | 55 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 56 | | private static int HashOf(GlobalEdgeId id) => |
| | 653106 | 57 | | HashCode.Combine(id.EdgeId, id.Tail, id.Head); |
| | | 58 | | |
| | | 59 | | /// <summary> |
| | | 60 | | /// Sets a new mapping. |
| | | 61 | | /// </summary> |
| | | 62 | | /// <param name="globalEdgeId">The global edge id.</param> |
| | | 63 | | /// <param name="edgeId">The local edge id.</param> |
| | | 64 | | public void Set(GlobalEdgeId globalEdgeId, EdgeId edgeId) |
| | 5500 | 65 | | { |
| | 5500 | 66 | | var hash = HashOf(globalEdgeId); |
| | 5500 | 67 | | var stripe = _stripes[hash & StripeMask]; |
| | 5500 | 68 | | lock (stripe) |
| | 5500 | 69 | | { |
| | | 70 | | // Grow before inserting: the probe loop relies on there always being a free slot. |
| | 5500 | 71 | | if ((stripe.Count + 1) * 10 >= stripe.Ways.Length * 7) Grow(stripe); |
| | | 72 | | |
| | 5500 | 73 | | Insert(stripe, globalEdgeId, edgeId, hash); |
| | 5500 | 74 | | } |
| | 5500 | 75 | | } |
| | | 76 | | |
| | | 77 | | private static void Insert(Stripe stripe, GlobalEdgeId id, EdgeId edgeId, int hash) |
| | 5500 | 78 | | { |
| | 5500 | 79 | | var mask = stripe.Ways.Length - 1; |
| | 5500 | 80 | | var slot = (hash >>> 6) & mask; |
| | 5500 | 81 | | while (stripe.Occupied[slot]) |
| | 0 | 82 | | { |
| | 0 | 83 | | if (stripe.Ways[slot] == id.EdgeId && stripe.Tails[slot] == id.Tail && |
| | 0 | 84 | | stripe.Heads[slot] == id.Head) |
| | 0 | 85 | | { |
| | | 86 | | // Overwrite, matching the dictionary indexer this replaced. |
| | 0 | 87 | | stripe.TileIds[slot] = edgeId.TileId; |
| | 0 | 88 | | stripe.LocalIds[slot] = edgeId.LocalId; |
| | 0 | 89 | | return; |
| | | 90 | | } |
| | | 91 | | |
| | 0 | 92 | | slot = (slot + 1) & mask; |
| | 0 | 93 | | } |
| | | 94 | | |
| | 5500 | 95 | | stripe.Occupied[slot] = true; |
| | 5500 | 96 | | stripe.Ways[slot] = id.EdgeId; |
| | 5500 | 97 | | stripe.Tails[slot] = id.Tail; |
| | 5500 | 98 | | stripe.Heads[slot] = id.Head; |
| | 5500 | 99 | | stripe.TileIds[slot] = edgeId.TileId; |
| | 5500 | 100 | | stripe.LocalIds[slot] = edgeId.LocalId; |
| | 5500 | 101 | | stripe.Count++; |
| | 5500 | 102 | | } |
| | | 103 | | |
| | | 104 | | // Doubles a stripe and rehashes it. Caller holds the stripe. |
| | | 105 | | private static void Grow(Stripe stripe) |
| | 0 | 106 | | { |
| | 0 | 107 | | var oldWays = stripe.Ways; |
| | 0 | 108 | | var oldTails = stripe.Tails; |
| | 0 | 109 | | var oldHeads = stripe.Heads; |
| | 0 | 110 | | var oldTileIds = stripe.TileIds; |
| | 0 | 111 | | var oldLocalIds = stripe.LocalIds; |
| | 0 | 112 | | var oldOccupied = stripe.Occupied; |
| | 0 | 113 | | var capacity = oldWays.Length * 2; |
| | | 114 | | |
| | 0 | 115 | | stripe.Ways = new long[capacity]; |
| | 0 | 116 | | stripe.Tails = new ushort[capacity]; |
| | 0 | 117 | | stripe.Heads = new ushort[capacity]; |
| | 0 | 118 | | stripe.TileIds = new uint[capacity]; |
| | 0 | 119 | | stripe.LocalIds = new uint[capacity]; |
| | 0 | 120 | | stripe.Occupied = new bool[capacity]; |
| | 0 | 121 | | stripe.Count = 0; |
| | | 122 | | |
| | 0 | 123 | | for (var i = 0; i < oldWays.Length; i++) |
| | 0 | 124 | | { |
| | 0 | 125 | | if (!oldOccupied[i]) continue; |
| | | 126 | | |
| | 0 | 127 | | var id = GlobalEdgeId.Create(oldWays[i], oldTails[i], oldHeads[i]); |
| | 0 | 128 | | Insert(stripe, id, new EdgeId(oldTileIds[i], oldLocalIds[i]), HashOf(id)); |
| | 0 | 129 | | } |
| | 0 | 130 | | } |
| | | 131 | | |
| | | 132 | | /// <summary> |
| | | 133 | | /// Removes a mapping. |
| | | 134 | | /// </summary> |
| | | 135 | | /// <param name="globalEdgeId">The global edge id.</param> |
| | | 136 | | /// <remarks> |
| | | 137 | | /// Tombstone-free: the rest of the probe run is reinserted, so every probe can still stop at the |
| | | 138 | | /// first free slot. |
| | | 139 | | /// </remarks> |
| | | 140 | | public void Remove(GlobalEdgeId globalEdgeId) |
| | 0 | 141 | | { |
| | 0 | 142 | | var hash = HashOf(globalEdgeId); |
| | 0 | 143 | | var stripe = _stripes[hash & StripeMask]; |
| | 0 | 144 | | lock (stripe) |
| | 0 | 145 | | { |
| | 0 | 146 | | if (!TryFind(stripe, globalEdgeId, hash, out var slot)) return; |
| | | 147 | | |
| | 0 | 148 | | var mask = stripe.Ways.Length - 1; |
| | 0 | 149 | | stripe.Occupied[slot] = false; |
| | 0 | 150 | | stripe.Count--; |
| | | 151 | | |
| | 0 | 152 | | var next = (slot + 1) & mask; |
| | 0 | 153 | | while (stripe.Occupied[next]) |
| | 0 | 154 | | { |
| | 0 | 155 | | var id = GlobalEdgeId.Create(stripe.Ways[next], stripe.Tails[next], stripe.Heads[next]); |
| | 0 | 156 | | var edgeId = new EdgeId(stripe.TileIds[next], stripe.LocalIds[next]); |
| | 0 | 157 | | stripe.Occupied[next] = false; |
| | 0 | 158 | | stripe.Count--; |
| | 0 | 159 | | Insert(stripe, id, edgeId, HashOf(id)); |
| | 0 | 160 | | next = (next + 1) & mask; |
| | 0 | 161 | | } |
| | 0 | 162 | | } |
| | 0 | 163 | | } |
| | | 164 | | |
| | | 165 | | private static bool TryFind(Stripe stripe, GlobalEdgeId id, int hash, out int slot) |
| | 647606 | 166 | | { |
| | 647606 | 167 | | var mask = stripe.Ways.Length - 1; |
| | 647606 | 168 | | slot = (hash >>> 6) & mask; |
| | 647606 | 169 | | while (stripe.Occupied[slot]) |
| | 2655 | 170 | | { |
| | 2655 | 171 | | if (stripe.Ways[slot] == id.EdgeId && stripe.Tails[slot] == id.Tail && |
| | 2655 | 172 | | stripe.Heads[slot] == id.Head) |
| | 2655 | 173 | | { |
| | 2655 | 174 | | return true; |
| | | 175 | | } |
| | | 176 | | |
| | 0 | 177 | | slot = (slot + 1) & mask; |
| | 0 | 178 | | } |
| | | 179 | | |
| | 644951 | 180 | | return false; |
| | 647606 | 181 | | } |
| | | 182 | | |
| | | 183 | | /// <summary> |
| | | 184 | | /// Gets a mapping if it exists. |
| | | 185 | | /// </summary> |
| | | 186 | | /// <param name="globalEdgeId">The global edge id.</param> |
| | | 187 | | /// <param name="edgeId">The edge associated with the given global edge, if any.</param> |
| | | 188 | | /// <returns>True if a mapping exists, false otherwise.</returns> |
| | | 189 | | public bool TryGet(GlobalEdgeId globalEdgeId, out EdgeId edgeId) |
| | 647606 | 190 | | { |
| | 647606 | 191 | | var hash = HashOf(globalEdgeId); |
| | 647606 | 192 | | var stripe = _stripes[hash & StripeMask]; |
| | 647606 | 193 | | lock (stripe) |
| | 647606 | 194 | | { |
| | 647606 | 195 | | if (!TryFind(stripe, globalEdgeId, hash, out var slot)) |
| | 644951 | 196 | | { |
| | 644951 | 197 | | edgeId = default; |
| | 644951 | 198 | | return false; |
| | | 199 | | } |
| | | 200 | | |
| | 2655 | 201 | | edgeId = new EdgeId(stripe.TileIds[slot], stripe.LocalIds[slot]); |
| | 2655 | 202 | | return true; |
| | | 203 | | } |
| | 647606 | 204 | | } |
| | | 205 | | |
| | | 206 | | /// <summary> |
| | | 207 | | /// Returns an enumerator that iterates through the collection. |
| | | 208 | | /// </summary> |
| | | 209 | | /// <returns>An enumerator that can be used to iterate through the collection.</returns> |
| | | 210 | | /// <remarks> |
| | | 211 | | /// Snapshots each stripe under its lock rather than yielding while holding it, so a slow |
| | | 212 | | /// consumer cannot block inserts. |
| | | 213 | | /// </remarks> |
| | | 214 | | public IEnumerator<(GlobalEdgeId globalId, EdgeId edgeId)> GetEnumerator() |
| | 0 | 215 | | { |
| | 0 | 216 | | foreach (var stripe in _stripes) |
| | 0 | 217 | | { |
| | | 218 | | List<(GlobalEdgeId, EdgeId)> snapshot; |
| | 0 | 219 | | lock (stripe) |
| | 0 | 220 | | { |
| | 0 | 221 | | snapshot = new List<(GlobalEdgeId, EdgeId)>(stripe.Count); |
| | 0 | 222 | | for (var i = 0; i < stripe.Ways.Length; i++) |
| | 0 | 223 | | { |
| | 0 | 224 | | if (!stripe.Occupied[i]) continue; |
| | | 225 | | |
| | 0 | 226 | | snapshot.Add((GlobalEdgeId.Create(stripe.Ways[i], stripe.Tails[i], stripe.Heads[i]), |
| | 0 | 227 | | new EdgeId(stripe.TileIds[i], stripe.LocalIds[i]))); |
| | 0 | 228 | | } |
| | 0 | 229 | | } |
| | | 230 | | |
| | 0 | 231 | | foreach (var entry in snapshot) yield return entry; |
| | 0 | 232 | | } |
| | 0 | 233 | | } |
| | | 234 | | |
| | | 235 | | IEnumerator IEnumerable.GetEnumerator() |
| | 0 | 236 | | { |
| | 0 | 237 | | return this.GetEnumerator(); |
| | 0 | 238 | | } |
| | | 239 | | } |