< Summary

Class:Itinero.Network.DataStructures.SparseArrayExtensions
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/DataStructures/SparseArray.cs
Covered lines:3
Uncovered lines:0
Coverable lines:3
Total lines:292
Line coverage:100% (3 of 3)
Covered branches:0
Total branches:0
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
EnsureMinimumSize(...)100%1100%

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>
 23    private readonly object _growLock = new();
 24
 25    public SparseArray(long size, int blockSize = 1 << 16,
 26        T emptyDefault = default)
 27    {
 28        if (size < 0)
 29        {
 30            throw new ArgumentOutOfRangeException(nameof(size), "Size needs to be bigger than or equal to zero.");
 31        }
 32
 33        if (blockSize <= 0)
 34        {
 35            throw new ArgumentOutOfRangeException(nameof(blockSize),
 36                "Block size needs to be bigger than or equal to zero.");
 37        }
 38
 39        if ((blockSize & (blockSize - 1)) != 0)
 40        {
 41            throw new ArgumentOutOfRangeException(nameof(blockSize), "Block size needs to be a power of 2.");
 42        }
 43
 44        _default = emptyDefault;
 45        _blockSize = blockSize;
 46        _size = size;
 47        _arrayPow = ExpOf2(blockSize);
 48
 49        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 50        _blocks = new T[blockCount][];
 51    }
 52
 53    private SparseArray(T[][] blocks, long size, int blockSize, int arrayPow, T @default)
 54    {
 55        _blocks = blocks;
 56        _size = size;
 57        _blockSize = blockSize;
 58        _arrayPow = arrayPow;
 59        _default = @default;
 60    }
 61
 62    private static int ExpOf2(int powerOf2)
 63    {
 64        // this can probably be faster but it needs to run once in the constructor,
 65        // feel free to improve but not crucial.
 66        if (powerOf2 == 1)
 67        {
 68            return 0;
 69        }
 70
 71        return ExpOf2(powerOf2 / 2) + 1;
 72    }
 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
 81        {
 82            if (idx >= this.Length)
 83            {
 84                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.
 89            var blocks = Volatile.Read(ref _blocks);
 90            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.
 94            if (blockId >= blocks.Length)
 95            {
 96                return _default;
 97            }
 98
 99            var block = blocks[blockId];
 100            if (block == null)
 101            {
 102                return _default;
 103            }
 104
 105            var localIdx = idx - (blockId << _arrayPow);
 106            return block[localIdx];
 107        }
 108        set
 109        {
 110            if (idx >= this.Length)
 111            {
 112                throw new ArgumentOutOfRangeException(nameof(idx));
 113            }
 114
 115            var blockId = idx >> _arrayPow;
 116            var blocks = Volatile.Read(ref _blocks);
 117            var block = blockId < blocks.Length ? blocks[blockId] : null;
 118            if (block == null)
 119            {
 120                // don't create a new block for a default value.
 121                if (EqualityComparer<T>.Default.Equals(value, _default))
 122                {
 123                    return;
 124                }
 125
 126                block = this.EnsureBlock(blockId);
 127            }
 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.
 132            var localIdx = idx % _blockSize;
 133            block[localIdx] = value;
 134        }
 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)
 140    {
 141        lock (_growLock)
 142        {
 143            var blocks = _blocks;
 144            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.
 149            var block = new T[_blockSize];
 150            if (!EqualityComparer<T>.Default.Equals(_default, default!))
 151            {
 152                for (var i = 0; i < _blockSize; i++)
 153                {
 154                    block[i] = _default;
 155                }
 156            }
 157
 158            if (blockId >= blocks.Length)
 159            {
 160                // Length said this index was in range, so the blocks array has not caught up
 161                // yet. Grow it here rather than failing.
 162                var grown = new T[Math.Max(blockId + 1, Math.Min(blocks.Length * 2L, int.MaxValue))][];
 163                Array.Copy(blocks, grown, blocks.Length);
 164                blocks = grown;
 165                Volatile.Write(ref _blocks, blocks);
 166            }
 167
 168            blocks[blockId] = block;
 169            return block;
 170        }
 171    }
 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)
 179    {
 180        if (size < 0)
 181        {
 182            throw new ArgumentOutOfRangeException(nameof(size),
 183                "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.
 193        lock (_growLock)
 194        {
 195            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.
 199            Volatile.Write(ref _size, size);
 200        }
 201    }
 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)
 211    {
 212        if (Volatile.Read(ref _size) >= minimum) return;
 213
 214        lock (_growLock)
 215        {
 216            if (_size >= minimum) return;
 217
 218            this.GrowBlocksTo(minimum);
 219            Volatile.Write(ref _size, minimum);
 220        }
 221    }
 222
 223    /// Widens the block array to cover <paramref name="size"/>. Caller holds <see cref="_growLock"/>.
 224    private void GrowBlocksTo(long size)
 225    {
 226        var blockCount = (long)Math.Ceiling((double)size / _blockSize);
 227        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.
 231        var grown = new T[Math.Max(blockCount, Math.Min(_blocks.Length * 2L, int.MaxValue))][];
 232        Array.Copy(_blocks, grown, _blocks.Length);
 233        Volatile.Write(ref _blocks, grown);
 234    }
 235
 236    /// <summary>
 237    /// Gets the length of this array.
 238    /// </summary>
 239    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()
 246    {
 247        var blocks = new T[_blocks.Length][];
 248        for (var b = 0; b < blocks.Length; b++)
 249        {
 250            var block = _blocks[b];
 251            if (block == null)
 252            {
 253                continue;
 254            }
 255
 256            blocks[b] = (block.Clone() as T[])!;
 257        }
 258
 259        return new SparseArray<T>(blocks, _size, _blockSize, _arrayPow, _default);
 260    }
 261
 262    public IEnumerator<(long i, T value)> GetEnumerator()
 263    {
 264        for (var b = 0; b < _blocks.Length; b++)
 265        {
 266            var block = _blocks[b];
 267            if (block == null)
 268            {
 269                continue;
 270            }
 271
 272            for (var i = 0; i < block.Length; i++)
 273            {
 274                yield return ((_blockSize * b) + i, block[i]);
 275            }
 276        }
 277    }
 278
 279    IEnumerator IEnumerable.GetEnumerator()
 280    {
 281        return this.GetEnumerator();
 282    }
 283}
 284
 285internal static class SparseArrayExtensions
 286{
 287    internal static void EnsureMinimumSize<T>(this SparseArray<T> array, long i)
 258364288    {
 289        // Not a Length check plus Resize: see SparseArray.EnsureSize for why that pair races.
 258364290        array.EnsureSize(i + 1);
 258364291    }
 292}

Methods/Properties

EnsureMinimumSize(...)