< Summary

Class:Itinero.Data.GlobalEdgeIdSet
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Data/GlobalEdgeIdSet.cs
Covered lines:57
Uncovered lines:73
Coverable lines:130
Total lines:239
Line coverage:43.8% (57 of 130)
Covered branches:11
Total branches:38
Branch coverage:28.9% (11 of 38)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
.ctor()100%1100%
CreateStripes()100%2100%
HashOf(...)100%1100%
Set(...)50%2100%
Insert(...)12.5%857.14%
Grow(...)0%40%
Remove(...)0%40%
TryFind(...)62.5%884.61%
TryGet(...)100%2100%
GetEnumerator()0%80%
System.Collections.IEnumerable.GetEnumerator()100%10%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Data/GlobalEdgeIdSet.cs

#LineLine coverage
 1using System;
 2using System.Collections;
 3using System.Collections.Generic;
 4using System.Runtime.CompilerServices;
 5using Itinero.Network;
 6using Itinero.Network.Tiles.Standalone.Global;
 7
 8namespace 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>
 17public 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    {
 806432        public long[] Ways = new long[InitialStripeCapacity];
 806433        public ushort[] Tails = new ushort[InitialStripeCapacity];
 806434        public ushort[] Heads = new ushort[InitialStripeCapacity];
 806435        public uint[] TileIds = new uint[InitialStripeCapacity];
 806436        public uint[] LocalIds = new uint[InitialStripeCapacity];
 37
 38        // Its own array because any key value is legal, including zero.
 806439        public bool[] Occupied = new bool[InitialStripeCapacity];
 40
 41        public int Count;
 42    }
 43
 12644    private readonly Stripe[] _stripes = CreateStripes();
 45
 46    private static Stripe[] CreateStripes()
 12647    {
 12648        var stripes = new Stripe[Stripes];
 2444449        for (var s = 0; s < Stripes; s++) stripes[s] = new Stripe();
 50
 12651        return stripes;
 12652    }
 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) =>
 65310657        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)
 550065    {
 550066        var hash = HashOf(globalEdgeId);
 550067        var stripe = _stripes[hash & StripeMask];
 550068        lock (stripe)
 550069        {
 70            // Grow before inserting: the probe loop relies on there always being a free slot.
 550071            if ((stripe.Count + 1) * 10 >= stripe.Ways.Length * 7) Grow(stripe);
 72
 550073            Insert(stripe, globalEdgeId, edgeId, hash);
 550074        }
 550075    }
 76
 77    private static void Insert(Stripe stripe, GlobalEdgeId id, EdgeId edgeId, int hash)
 550078    {
 550079        var mask = stripe.Ways.Length - 1;
 550080        var slot = (hash >>> 6) & mask;
 550081        while (stripe.Occupied[slot])
 082        {
 083            if (stripe.Ways[slot] == id.EdgeId && stripe.Tails[slot] == id.Tail &&
 084                stripe.Heads[slot] == id.Head)
 085            {
 86                // Overwrite, matching the dictionary indexer this replaced.
 087                stripe.TileIds[slot] = edgeId.TileId;
 088                stripe.LocalIds[slot] = edgeId.LocalId;
 089                return;
 90            }
 91
 092            slot = (slot + 1) & mask;
 093        }
 94
 550095        stripe.Occupied[slot] = true;
 550096        stripe.Ways[slot] = id.EdgeId;
 550097        stripe.Tails[slot] = id.Tail;
 550098        stripe.Heads[slot] = id.Head;
 550099        stripe.TileIds[slot] = edgeId.TileId;
 5500100        stripe.LocalIds[slot] = edgeId.LocalId;
 5500101        stripe.Count++;
 5500102    }
 103
 104    // Doubles a stripe and rehashes it. Caller holds the stripe.
 105    private static void Grow(Stripe stripe)
 0106    {
 0107        var oldWays = stripe.Ways;
 0108        var oldTails = stripe.Tails;
 0109        var oldHeads = stripe.Heads;
 0110        var oldTileIds = stripe.TileIds;
 0111        var oldLocalIds = stripe.LocalIds;
 0112        var oldOccupied = stripe.Occupied;
 0113        var capacity = oldWays.Length * 2;
 114
 0115        stripe.Ways = new long[capacity];
 0116        stripe.Tails = new ushort[capacity];
 0117        stripe.Heads = new ushort[capacity];
 0118        stripe.TileIds = new uint[capacity];
 0119        stripe.LocalIds = new uint[capacity];
 0120        stripe.Occupied = new bool[capacity];
 0121        stripe.Count = 0;
 122
 0123        for (var i = 0; i < oldWays.Length; i++)
 0124        {
 0125            if (!oldOccupied[i]) continue;
 126
 0127            var id = GlobalEdgeId.Create(oldWays[i], oldTails[i], oldHeads[i]);
 0128            Insert(stripe, id, new EdgeId(oldTileIds[i], oldLocalIds[i]), HashOf(id));
 0129        }
 0130    }
 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)
 0141    {
 0142        var hash = HashOf(globalEdgeId);
 0143        var stripe = _stripes[hash & StripeMask];
 0144        lock (stripe)
 0145        {
 0146            if (!TryFind(stripe, globalEdgeId, hash, out var slot)) return;
 147
 0148            var mask = stripe.Ways.Length - 1;
 0149            stripe.Occupied[slot] = false;
 0150            stripe.Count--;
 151
 0152            var next = (slot + 1) & mask;
 0153            while (stripe.Occupied[next])
 0154            {
 0155                var id = GlobalEdgeId.Create(stripe.Ways[next], stripe.Tails[next], stripe.Heads[next]);
 0156                var edgeId = new EdgeId(stripe.TileIds[next], stripe.LocalIds[next]);
 0157                stripe.Occupied[next] = false;
 0158                stripe.Count--;
 0159                Insert(stripe, id, edgeId, HashOf(id));
 0160                next = (next + 1) & mask;
 0161            }
 0162        }
 0163    }
 164
 165    private static bool TryFind(Stripe stripe, GlobalEdgeId id, int hash, out int slot)
 647606166    {
 647606167        var mask = stripe.Ways.Length - 1;
 647606168        slot = (hash >>> 6) & mask;
 647606169        while (stripe.Occupied[slot])
 2655170        {
 2655171            if (stripe.Ways[slot] == id.EdgeId && stripe.Tails[slot] == id.Tail &&
 2655172                stripe.Heads[slot] == id.Head)
 2655173            {
 2655174                return true;
 175            }
 176
 0177            slot = (slot + 1) & mask;
 0178        }
 179
 644951180        return false;
 647606181    }
 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)
 647606190    {
 647606191        var hash = HashOf(globalEdgeId);
 647606192        var stripe = _stripes[hash & StripeMask];
 647606193        lock (stripe)
 647606194        {
 647606195            if (!TryFind(stripe, globalEdgeId, hash, out var slot))
 644951196            {
 644951197                edgeId = default;
 644951198                return false;
 199            }
 200
 2655201            edgeId = new EdgeId(stripe.TileIds[slot], stripe.LocalIds[slot]);
 2655202            return true;
 203        }
 647606204    }
 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()
 0215    {
 0216        foreach (var stripe in _stripes)
 0217        {
 218            List<(GlobalEdgeId, EdgeId)> snapshot;
 0219            lock (stripe)
 0220            {
 0221                snapshot = new List<(GlobalEdgeId, EdgeId)>(stripe.Count);
 0222                for (var i = 0; i < stripe.Ways.Length; i++)
 0223                {
 0224                    if (!stripe.Occupied[i]) continue;
 225
 0226                    snapshot.Add((GlobalEdgeId.Create(stripe.Ways[i], stripe.Tails[i], stripe.Heads[i]),
 0227                        new EdgeId(stripe.TileIds[i], stripe.LocalIds[i])));
 0228                }
 0229            }
 230
 0231            foreach (var entry in snapshot) yield return entry;
 0232        }
 0233    }
 234
 235    IEnumerator IEnumerable.GetEnumerator()
 0236    {
 0237        return this.GetEnumerator();
 0238    }
 239}