< Summary

Class:Itinero.Network.DataStructures.SparseArray`1
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/DataStructures/SparseArray.cs
Covered lines:124
Uncovered lines:23
Coverable lines:147
Total lines:292
Line coverage:84.3% (124 of 147)
Covered branches:40
Total branches:50
Branch coverage:80% (40 of 50)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)50%666.66%
.ctor(...)100%1100%
ExpOf2(...)100%2100%
get_Item(...)83.33%687.5%
set_Item(...)75%888.23%
EnsureBlock(...)80%1073.91%
Resize(...)50%272.72%
EnsureSize(...)75%4100%
GrowBlocksTo(...)100%2100%
get_Length()100%1100%
Clone()100%4100%
GetEnumerator()100%6100%
System.Collections.IEnumerable.GetEnumerator()100%10%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Network/DataStructures/SparseArray.cs

#LineLine coverage
 1using System;
 2using System.Collections;
 3using System.Collections.Generic;
 4using System.Threading;
 5
 6namespace Itinero.Network.DataStructures;
 7
 8internal sealed class SparseArray<T> : IEnumerable<(long i, T value)>
 9{
 10    private T[][] _blocks;
 11    private readonly int _blockSize; // Holds the maximum array size, always needs to be a power of 2.
 12    private readonly int _arrayPow;
 13    private long _size; // the total size of this array.
 14    private readonly T _default;
 15
 16    /// <summary>
 17    /// Guards growing: replacing <see cref="_blocks"/> and allocating a block into it.
 18    /// </summary>
 19    /// <remarks>
 20    /// Growing copies the array of block references, so a block installed into the old array mid-copy
 21    /// is lost. Allocating under the same lock removes that and the double-allocate race.
 22    /// </remarks>
 121323    private readonly object _growLock = new();
 24
 87825    public SparseArray(long size, int blockSize = 1 << 16,
 87826        T emptyDefault = default)
 87827    {
 87828        if (size < 0)
 029        {
 030            throw new ArgumentOutOfRangeException(nameof(size), "Size needs to be bigger than or equal to zero.");
 31        }
 32
 87833        if (blockSize <= 0)
 034        {
 035            throw new ArgumentOutOfRangeException(nameof(blockSize),
 036                "Block size needs to be bigger than or equal to zero.");
 37        }
 38
 87839        if ((blockSize & (blockSize - 1)) != 0)
 040        {
 041            throw new ArgumentOutOfRangeException(nameof(blockSize), "Block size needs to be a power of 2.");
 42        }
 43
 87844        _default = emptyDefault;
 87845        _blockSize = blockSize;
 87846        _size = size;
 87847        _arrayPow = ExpOf2(blockSize);
 48
 87849        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 87850        _blocks = new T[blockCount][];
 87851    }
 52
 33553    private SparseArray(T[][] blocks, long size, int blockSize, int arrayPow, T @default)
 33554    {
 33555        _blocks = blocks;
 33556        _size = size;
 33557        _blockSize = blockSize;
 33558        _arrayPow = arrayPow;
 33559        _default = @default;
 33560    }
 61
 62    private static int ExpOf2(int powerOf2)
 1483063    {
 64        // this can probably be faster but it needs to run once in the constructor,
 65        // feel free to improve but not crucial.
 1483066        if (powerOf2 == 1)
 87867        {
 87868            return 0;
 69        }
 70
 1395271        return ExpOf2(powerOf2 / 2) + 1;
 1483072    }
 73
 74    /// <summary>
 75    /// Gets or sets the item at the given index.
 76    /// </summary>
 77    /// <param name="idx">The index.</param>
 78    public T this[long idx]
 79    {
 80        get
 668817881        {
 668817882            if (idx >= this.Length)
 183            {
 184                throw new ArgumentOutOfRangeException(nameof(idx));
 85            }
 86
 87            // One read of the field: reading twice could see two arrays either side of a concurrent grow,
 88            // and growth only copies block references forward.
 668817789            var blocks = Volatile.Read(ref _blocks);
 668817790            var blockId = idx >> _arrayPow;
 91
 92            // Length can be visible before the wider blocks array is. Nothing has been written
 93            // that far out yet, so the default is the right answer.
 668817794            if (blockId >= blocks.Length)
 095            {
 096                return _default;
 97            }
 98
 668817799            var block = blocks[blockId];
 6688177100            if (block == null)
 534101            {
 534102                return _default;
 103            }
 104
 6687643105            var localIdx = idx - (blockId << _arrayPow);
 6687643106            return block[localIdx];
 6688177107        }
 108        set
 3663109        {
 3663110            if (idx >= this.Length)
 1111            {
 1112                throw new ArgumentOutOfRangeException(nameof(idx));
 113            }
 114
 3662115            var blockId = idx >> _arrayPow;
 3662116            var blocks = Volatile.Read(ref _blocks);
 3662117            var block = blockId < blocks.Length ? blocks[blockId] : null;
 3662118            if (block == null)
 878119            {
 120                // don't create a new block for a default value.
 878121                if (EqualityComparer<T>.Default.Equals(value, _default))
 0122                {
 0123                    return;
 124                }
 125
 878126                block = this.EnsureBlock(blockId);
 878127            }
 128
 129            // Write through the block reference, not through _blocks[blockId] a second time: the
 130            // block object is shared across grows, so this stays correct if the array is replaced
 131            // underneath, whereas re-reading the array could land on a stale slot.
 3662132            var localIdx = idx % _blockSize;
 3662133            block[localIdx] = value;
 3662134        }
 135    }
 136
 137    /// Allocates the block for <paramref name="blockId"/>, or returns the one another thread
 138    /// allocated first.
 139    private T[] EnsureBlock(long blockId)
 878140    {
 878141        lock (_growLock)
 878142        {
 878143            var blocks = _blocks;
 902144            if (blockId < blocks.Length && blocks[blockId] != null) return blocks[blockId];
 145
 146            // A new array arrives filled with default(T), so only a _default that
 147            // differs from it needs writing. Skipping that loop matters: _blockSize
 148            // is 65536.
 854149            var block = new T[_blockSize];
 854150            if (!EqualityComparer<T>.Default.Equals(_default, default!))
 1151            {
 34152                for (var i = 0; i < _blockSize; i++)
 16153                {
 16154                    block[i] = _default;
 16155                }
 1156            }
 157
 854158            if (blockId >= blocks.Length)
 0159            {
 160                // Length said this index was in range, so the blocks array has not caught up
 161                // yet. Grow it here rather than failing.
 0162                var grown = new T[Math.Max(blockId + 1, Math.Min(blocks.Length * 2L, int.MaxValue))][];
 0163                Array.Copy(blocks, grown, blocks.Length);
 0164                blocks = grown;
 0165                Volatile.Write(ref _blocks, blocks);
 0166            }
 167
 854168            blocks[blockId] = block;
 854169            return block;
 170        }
 878171    }
 172
 173    /// <summary>
 174    /// Resizes this array to the given size.
 175    /// </summary>
 176    /// <param name="size">The size.</param>
 177    /// <exception cref="ArgumentOutOfRangeException"></exception>
 178    public void Resize(long size)
 9179    {
 9180        if (size < 0)
 0181        {
 0182            throw new ArgumentOutOfRangeException(nameof(size),
 0183                "Cannot resize an array to a size of zero or smaller.");
 184        }
 185
 186        // Grow-only, and geometrically. EnsureMinimumSize resizes to exactly i + 1, so
 187        // tile loading walked this with an Array.Resize per new block while holding the
 188        // network write lock. Never shrinking keeps that amortised: shrinking back to
 189        // blockCount would undo the headroom on the very next call.
 190        //
 191        // Blocks past _size stay unreachable - the indexer bounds-checks against Length
 192        // and the enumerator stops at _size - so the extra entries are inert.
 9193        lock (_growLock)
 9194        {
 9195            this.GrowBlocksTo(size);
 196
 197            // Published last: Length is what the indexer bounds-checks against, so widening it
 198            // before the blocks array exists would admit an index with nowhere to go.
 9199            Volatile.Write(ref _size, size);
 9200        }
 9201    }
 202
 203    /// <summary>
 204    /// Grows to at least <paramref name="minimum"/>, never shrinking.
 205    /// </summary>
 206    /// <remarks>
 207    /// Separate from Resize, which must set the size it is given. A check-then-Resize pair outside a
 208    /// lock lets a smaller Resize land last and shrink the array.
 209    /// </remarks>
 210    public void EnsureSize(long minimum)
 258364211    {
 514500212        if (Volatile.Read(ref _size) >= minimum) return;
 213
 2228214        lock (_growLock)
 2228215        {
 2228216            if (_size >= minimum) return;
 217
 2228218            this.GrowBlocksTo(minimum);
 2228219            Volatile.Write(ref _size, minimum);
 2228220        }
 258364221    }
 222
 223    /// Widens the block array to cover <paramref name="size"/>. Caller holds <see cref="_growLock"/>.
 224    private void GrowBlocksTo(long size)
 2237225    {
 2237226        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 3653227        if (blockCount <= _blocks.Length) return;
 228
 229        // Copy into a fresh array and publish it, rather than Array.Resize's ref-swap, so
 230        // a reader always observes a fully populated array.
 821231        var grown = new T[Math.Max(blockCount, Math.Min(_blocks.Length * 2L, int.MaxValue))][];
 821232        Array.Copy(_blocks, grown, _blocks.Length);
 821233        Volatile.Write(ref _blocks, grown);
 2237234    }
 235
 236    /// <summary>
 237    /// Gets the length of this array.
 238    /// </summary>
 15855081239    public long Length => Volatile.Read(ref _size);
 240
 241    /// <summary>
 242    /// Creates a clone.
 243    /// </summary>
 244    /// <returns>A copy of this array.</returns>
 245    public SparseArray<T> Clone()
 335246    {
 335247        var blocks = new T[_blocks.Length][];
 38954248        for (var b = 0; b < blocks.Length; b++)
 19142249        {
 19142250            var block = _blocks[b];
 19142251            if (block == null)
 19127252            {
 19127253                continue;
 254            }
 255
 15256            blocks[b] = (block.Clone() as T[])!;
 15257        }
 258
 335259        return new SparseArray<T>(blocks, _size, _blockSize, _arrayPow, _default);
 335260    }
 261
 262    public IEnumerator<(long i, T value)> GetEnumerator()
 435263    {
 1172582264        for (var b = 0; b < _blocks.Length; b++)
 585885265        {
 585885266            var block = _blocks[b];
 585885267            if (block == null)
 585448268            {
 585448269                continue;
 270            }
 271
 54605012272            for (var i = 0; i < block.Length; i++)
 27302098273            {
 27302098274                yield return ((_blockSize * b) + i, block[i]);
 27302069275            }
 408276        }
 406277    }
 278
 279    IEnumerator IEnumerable.GetEnumerator()
 0280    {
 0281        return this.GetEnumerator();
 0282    }
 283}
 284
 285internal static class SparseArrayExtensions
 286{
 287    internal static void EnsureMinimumSize<T>(this SparseArray<T> array, long i)
 288    {
 289        // Not a Length check plus Resize: see SparseArray.EnsureSize for why that pair races.
 290        array.EnsureSize(i + 1);
 291    }
 292}