| | | 1 | | using System; |
| | | 2 | | using System.Collections; |
| | | 3 | | using System.Collections.Generic; |
| | | 4 | | using System.Threading; |
| | | 5 | | |
| | | 6 | | namespace Itinero.Network.DataStructures; |
| | | 7 | | |
| | | 8 | | internal 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> |
| | 1213 | 23 | | private readonly object _growLock = new(); |
| | | 24 | | |
| | 878 | 25 | | public SparseArray(long size, int blockSize = 1 << 16, |
| | 878 | 26 | | T emptyDefault = default) |
| | 878 | 27 | | { |
| | 878 | 28 | | if (size < 0) |
| | 0 | 29 | | { |
| | 0 | 30 | | throw new ArgumentOutOfRangeException(nameof(size), "Size needs to be bigger than or equal to zero."); |
| | | 31 | | } |
| | | 32 | | |
| | 878 | 33 | | if (blockSize <= 0) |
| | 0 | 34 | | { |
| | 0 | 35 | | throw new ArgumentOutOfRangeException(nameof(blockSize), |
| | 0 | 36 | | "Block size needs to be bigger than or equal to zero."); |
| | | 37 | | } |
| | | 38 | | |
| | 878 | 39 | | if ((blockSize & (blockSize - 1)) != 0) |
| | 0 | 40 | | { |
| | 0 | 41 | | throw new ArgumentOutOfRangeException(nameof(blockSize), "Block size needs to be a power of 2."); |
| | | 42 | | } |
| | | 43 | | |
| | 878 | 44 | | _default = emptyDefault; |
| | 878 | 45 | | _blockSize = blockSize; |
| | 878 | 46 | | _size = size; |
| | 878 | 47 | | _arrayPow = ExpOf2(blockSize); |
| | | 48 | | |
| | 878 | 49 | | var blockCount = (long)Math.Ceiling((double)size / _blockSize); |
| | 878 | 50 | | _blocks = new T[blockCount][]; |
| | 878 | 51 | | } |
| | | 52 | | |
| | 335 | 53 | | private SparseArray(T[][] blocks, long size, int blockSize, int arrayPow, T @default) |
| | 335 | 54 | | { |
| | 335 | 55 | | _blocks = blocks; |
| | 335 | 56 | | _size = size; |
| | 335 | 57 | | _blockSize = blockSize; |
| | 335 | 58 | | _arrayPow = arrayPow; |
| | 335 | 59 | | _default = @default; |
| | 335 | 60 | | } |
| | | 61 | | |
| | | 62 | | private static int ExpOf2(int powerOf2) |
| | 14830 | 63 | | { |
| | | 64 | | // this can probably be faster but it needs to run once in the constructor, |
| | | 65 | | // feel free to improve but not crucial. |
| | 14830 | 66 | | if (powerOf2 == 1) |
| | 878 | 67 | | { |
| | 878 | 68 | | return 0; |
| | | 69 | | } |
| | | 70 | | |
| | 13952 | 71 | | return ExpOf2(powerOf2 / 2) + 1; |
| | 14830 | 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 |
| | 6688178 | 81 | | { |
| | 6688178 | 82 | | if (idx >= this.Length) |
| | 1 | 83 | | { |
| | 1 | 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. |
| | 6688177 | 89 | | var blocks = Volatile.Read(ref _blocks); |
| | 6688177 | 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. |
| | 6688177 | 94 | | if (blockId >= blocks.Length) |
| | 0 | 95 | | { |
| | 0 | 96 | | return _default; |
| | | 97 | | } |
| | | 98 | | |
| | 6688177 | 99 | | var block = blocks[blockId]; |
| | 6688177 | 100 | | if (block == null) |
| | 534 | 101 | | { |
| | 534 | 102 | | return _default; |
| | | 103 | | } |
| | | 104 | | |
| | 6687643 | 105 | | var localIdx = idx - (blockId << _arrayPow); |
| | 6687643 | 106 | | return block[localIdx]; |
| | 6688177 | 107 | | } |
| | | 108 | | set |
| | 3663 | 109 | | { |
| | 3663 | 110 | | if (idx >= this.Length) |
| | 1 | 111 | | { |
| | 1 | 112 | | throw new ArgumentOutOfRangeException(nameof(idx)); |
| | | 113 | | } |
| | | 114 | | |
| | 3662 | 115 | | var blockId = idx >> _arrayPow; |
| | 3662 | 116 | | var blocks = Volatile.Read(ref _blocks); |
| | 3662 | 117 | | var block = blockId < blocks.Length ? blocks[blockId] : null; |
| | 3662 | 118 | | if (block == null) |
| | 878 | 119 | | { |
| | | 120 | | // don't create a new block for a default value. |
| | 878 | 121 | | if (EqualityComparer<T>.Default.Equals(value, _default)) |
| | 0 | 122 | | { |
| | 0 | 123 | | return; |
| | | 124 | | } |
| | | 125 | | |
| | 878 | 126 | | block = this.EnsureBlock(blockId); |
| | 878 | 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. |
| | 3662 | 132 | | var localIdx = idx % _blockSize; |
| | 3662 | 133 | | block[localIdx] = value; |
| | 3662 | 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) |
| | 878 | 140 | | { |
| | 878 | 141 | | lock (_growLock) |
| | 878 | 142 | | { |
| | 878 | 143 | | var blocks = _blocks; |
| | 902 | 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. |
| | 854 | 149 | | var block = new T[_blockSize]; |
| | 854 | 150 | | if (!EqualityComparer<T>.Default.Equals(_default, default!)) |
| | 1 | 151 | | { |
| | 34 | 152 | | for (var i = 0; i < _blockSize; i++) |
| | 16 | 153 | | { |
| | 16 | 154 | | block[i] = _default; |
| | 16 | 155 | | } |
| | 1 | 156 | | } |
| | | 157 | | |
| | 854 | 158 | | if (blockId >= blocks.Length) |
| | 0 | 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. |
| | 0 | 162 | | var grown = new T[Math.Max(blockId + 1, Math.Min(blocks.Length * 2L, int.MaxValue))][]; |
| | 0 | 163 | | Array.Copy(blocks, grown, blocks.Length); |
| | 0 | 164 | | blocks = grown; |
| | 0 | 165 | | Volatile.Write(ref _blocks, blocks); |
| | 0 | 166 | | } |
| | | 167 | | |
| | 854 | 168 | | blocks[blockId] = block; |
| | 854 | 169 | | return block; |
| | | 170 | | } |
| | 878 | 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) |
| | 9 | 179 | | { |
| | 9 | 180 | | if (size < 0) |
| | 0 | 181 | | { |
| | 0 | 182 | | throw new ArgumentOutOfRangeException(nameof(size), |
| | 0 | 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. |
| | 9 | 193 | | lock (_growLock) |
| | 9 | 194 | | { |
| | 9 | 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. |
| | 9 | 199 | | Volatile.Write(ref _size, size); |
| | 9 | 200 | | } |
| | 9 | 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) |
| | 258364 | 211 | | { |
| | 514500 | 212 | | if (Volatile.Read(ref _size) >= minimum) return; |
| | | 213 | | |
| | 2228 | 214 | | lock (_growLock) |
| | 2228 | 215 | | { |
| | 2228 | 216 | | if (_size >= minimum) return; |
| | | 217 | | |
| | 2228 | 218 | | this.GrowBlocksTo(minimum); |
| | 2228 | 219 | | Volatile.Write(ref _size, minimum); |
| | 2228 | 220 | | } |
| | 258364 | 221 | | } |
| | | 222 | | |
| | | 223 | | /// Widens the block array to cover <paramref name="size"/>. Caller holds <see cref="_growLock"/>. |
| | | 224 | | private void GrowBlocksTo(long size) |
| | 2237 | 225 | | { |
| | 2237 | 226 | | var blockCount = (long)Math.Ceiling((double)size / _blockSize); |
| | 3653 | 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. |
| | 821 | 231 | | var grown = new T[Math.Max(blockCount, Math.Min(_blocks.Length * 2L, int.MaxValue))][]; |
| | 821 | 232 | | Array.Copy(_blocks, grown, _blocks.Length); |
| | 821 | 233 | | Volatile.Write(ref _blocks, grown); |
| | 2237 | 234 | | } |
| | | 235 | | |
| | | 236 | | /// <summary> |
| | | 237 | | /// Gets the length of this array. |
| | | 238 | | /// </summary> |
| | 15855081 | 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() |
| | 335 | 246 | | { |
| | 335 | 247 | | var blocks = new T[_blocks.Length][]; |
| | 38954 | 248 | | for (var b = 0; b < blocks.Length; b++) |
| | 19142 | 249 | | { |
| | 19142 | 250 | | var block = _blocks[b]; |
| | 19142 | 251 | | if (block == null) |
| | 19127 | 252 | | { |
| | 19127 | 253 | | continue; |
| | | 254 | | } |
| | | 255 | | |
| | 15 | 256 | | blocks[b] = (block.Clone() as T[])!; |
| | 15 | 257 | | } |
| | | 258 | | |
| | 335 | 259 | | return new SparseArray<T>(blocks, _size, _blockSize, _arrayPow, _default); |
| | 335 | 260 | | } |
| | | 261 | | |
| | | 262 | | public IEnumerator<(long i, T value)> GetEnumerator() |
| | 435 | 263 | | { |
| | 1172582 | 264 | | for (var b = 0; b < _blocks.Length; b++) |
| | 585885 | 265 | | { |
| | 585885 | 266 | | var block = _blocks[b]; |
| | 585885 | 267 | | if (block == null) |
| | 585448 | 268 | | { |
| | 585448 | 269 | | continue; |
| | | 270 | | } |
| | | 271 | | |
| | 54605012 | 272 | | for (var i = 0; i < block.Length; i++) |
| | 27302098 | 273 | | { |
| | 27302098 | 274 | | yield return ((_blockSize * b) + i, block[i]); |
| | 27302069 | 275 | | } |
| | 408 | 276 | | } |
| | 406 | 277 | | } |
| | | 278 | | |
| | | 279 | | IEnumerator IEnumerable.GetEnumerator() |
| | 0 | 280 | | { |
| | 0 | 281 | | return this.GetEnumerator(); |
| | 0 | 282 | | } |
| | | 283 | | } |
| | | 284 | | |
| | | 285 | | internal 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 | | } |