Raw.cs (41018B)
1 using Std.Clone; 2 using Std.Convert; 3 using static Std.Hashbrown.Raw.Functions; 4 using Std.Hashbrown.Raw.Bitmask; 5 using Std.Hashbrown.Raw.SSE2; 6 using Std.Iter; 7 using Std.Maybe; 8 using Std.Num; 9 using Std.Ops; 10 using Std.Result; 11 using System; 12 using System.Runtime.CompilerServices; 13 using System.Runtime.InteropServices; 14 #region Namespaces 15 namespace Std.Hashbrown.Raw { 16 #region Types 17 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 18 readonly struct NonNull<T>: IClone<NonNull<T>>, IInto<NonNull<T>> where T: notnull { 19 20 #region Type-level Constructors 21 #endregion 22 23 #region Instance Constructors 24 public NonNull() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 25 [MethodImpl(MethodImplOptions.AggressiveInlining)] 26 internal NonNull(T[] ptr, ulong index) => (_ptr, _index) = (ptr, index); 27 #endregion 28 29 #region Type-level Fields 30 #endregion 31 32 #region Instance Fields 33 internal readonly T[] _ptr; 34 internal readonly ulong _index; 35 #endregion 36 37 #region Type-level Properties 38 #endregion 39 40 #region Instance Properties 41 internal readonly ref readonly T Get() => ref _ptr[(int)_index]; 42 internal readonly ref T GetMut() => ref _ptr[(int)_index]; 43 #endregion 44 45 #region Type-level Functions 46 #endregion 47 48 #region Instance Functions 49 [MethodImpl(MethodImplOptions.AggressiveInlining)] 50 internal readonly NonNull<T> Add(ulong count) => new(_ptr, _index + count); 51 [MethodImpl(MethodImplOptions.AggressiveInlining)] 52 internal readonly NonNull<T> AsPtr() => this; 53 public readonly NonNull<T> Clone() => this; 54 [MethodImpl(MethodImplOptions.AggressiveInlining)] 55 internal readonly Unit CopyFromNonoverlapping(NonNull<T> src, ulong count) { 56 57 Array.Copy(src._ptr, (long)src._index, _ptr, (long)_index, (long)count); 58 return new Unit(); 59 } 60 public override readonly bool Equals(object? _) => false; 61 public override readonly int GetHashCode() => 0; 62 public readonly NonNull<T> Into() => this; 63 [MethodImpl(MethodImplOptions.AggressiveInlining)] 64 internal readonly ulong OffsetFrom(NonNull<T> from) => _index - from._index; 65 [MethodImpl(MethodImplOptions.AggressiveInlining)] 66 internal readonly T Read() => _ptr[(int)_index]; 67 [MethodImpl(MethodImplOptions.AggressiveInlining)] 68 internal readonly NonNull<T> Sub(ulong count) => new(_ptr, _index - count); 69 public override readonly string ToString() => string.Empty; 70 [MethodImpl(MethodImplOptions.AggressiveInlining)] 71 readonly Result<NonNull<T>, Bottom> ITryInto<NonNull<T>, Bottom>.TryInto() => new(this); 72 [MethodImpl(MethodImplOptions.AggressiveInlining)] 73 internal readonly Unit Write(T val) { 74 75 _ptr[(int)_index] = val; 76 return new Unit(); 77 } 78 #endregion 79 80 #region Operators 81 [MethodImpl(MethodImplOptions.AggressiveInlining)] 82 public static bool operator !=(NonNull<T> val0, NonNull<T> val1) => !(val0 == val1); 83 [MethodImpl(MethodImplOptions.AggressiveInlining)] 84 public static bool operator <(NonNull<T> val0, NonNull<T> val1){ 85 86 unsafe { 87 var reference0 = __makeref(val0._ptr[0]); 88 var reference1 = __makeref(val1._ptr[0]); 89 var val = (*(ulong*)&reference0).CompareTo(*(ulong*)&reference1); 90 return val < 0 || (val == 0 && val0._index < val1._index); 91 } 92 } 93 [MethodImpl(MethodImplOptions.AggressiveInlining)] 94 public static bool operator <=(NonNull<T> val0, NonNull<T> val1) => val0 < val1 || val0 == val1; 95 [MethodImpl(MethodImplOptions.AggressiveInlining)] 96 public static bool operator ==(NonNull<T> val0, NonNull<T> val1) => ReferenceEquals(val0._ptr, val1._ptr) && val0._index == val1._index; 97 [MethodImpl(MethodImplOptions.AggressiveInlining)] 98 public static bool operator >(NonNull<T> val0, NonNull<T> val1) => !(val0 <= val1); 99 [MethodImpl(MethodImplOptions.AggressiveInlining)] 100 public static bool operator >=(NonNull<T> val0, NonNull<T> val1) => !(val0 < val1); 101 #endregion 102 103 #region Types 104 #endregion 105 } 106 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 107 readonly struct Bucket<T>: IClone<Bucket<T>>, IInto<Bucket<T>> where T: notnull { 108 109 #region Type-level Constructors 110 #endregion 111 112 #region Instance Constructors 113 public Bucket() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 114 [MethodImpl(MethodImplOptions.AggressiveInlining)] 115 Bucket(NonNull<T> ptr) => _ptr = ptr; 116 #endregion 117 118 #region Type-level Fields 119 #endregion 120 121 #region Instance Fields 122 readonly NonNull<T> _ptr; 123 #endregion 124 125 #region Type-level Properties 126 #endregion 127 128 #region Instance Properties 129 #endregion 130 131 #region Type-level Functions 132 [MethodImpl(MethodImplOptions.AggressiveInlining)] 133 internal static Bucket<T> FromBaseIndex(NonNull<T> @base, ulong index) => new(@base.AsPtr().Sub(index)); 134 #endregion 135 136 #region Instance Functions 137 [MethodImpl(MethodImplOptions.AggressiveInlining)] 138 internal readonly ref T AsMut() => ref AsPtr().GetMut(); 139 [MethodImpl(MethodImplOptions.AggressiveInlining)] 140 readonly NonNull<T> AsPtr() => _ptr.AsPtr().Sub(1ul); 141 [MethodImpl(MethodImplOptions.AggressiveInlining)] 142 internal readonly ref readonly T AsRef() => ref AsPtr().Get(); 143 public readonly Bucket<T> Clone() => new(_ptr); 144 [MethodImpl(MethodImplOptions.AggressiveInlining)] 145 internal readonly Unit CopyFromNonoverlapping(in Bucket<T> other) => AsPtr().CopyFromNonoverlapping(other.AsPtr(), 1ul); 146 public override readonly bool Equals(object? _) => false; 147 public override readonly int GetHashCode() => 0; 148 public readonly Bucket<T> Into() => this; 149 [MethodImpl(MethodImplOptions.AggressiveInlining)] 150 internal readonly Bucket<T> NextN(ulong offset) => new(_ptr.AsPtr().Sub(offset)); 151 [MethodImpl(MethodImplOptions.AggressiveInlining)] 152 internal readonly T Read() => AsPtr().Read(); 153 [MethodImpl(MethodImplOptions.AggressiveInlining)] 154 internal readonly ulong ToBaseIndex(NonNull<T> @base) => @base.AsPtr().OffsetFrom(_ptr.AsPtr()); 155 public override readonly string ToString() => string.Empty; 156 readonly Result<Bucket<T>, Bottom> ITryInto<Bucket<T>, Bottom>.TryInto() => new(this); 157 [MethodImpl(MethodImplOptions.AggressiveInlining)] 158 internal readonly Unit Write(T val) => AsPtr().Write(val); 159 #endregion 160 161 #region Operators 162 #endregion 163 164 #region Types 165 #endregion 166 } 167 [StructLayout(LayoutKind.Explicit, CharSet = CharSet.Unicode, Pack = 8, Size = 24)] 168 struct ProbeSeq: IInto<ProbeSeq>, IIterator<ulong> { 169 170 #region Type-level Constructors 171 #endregion 172 173 #region Instance Constructors 174 public ProbeSeq() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 175 [MethodImpl(MethodImplOptions.AggressiveInlining)] 176 internal ProbeSeq(ulong bucketMask, ulong pos, ulong stride) => (_bucketMask, _pos, _stride) = (bucketMask, pos, stride); 177 #endregion 178 179 #region Type-level Fields 180 #endregion 181 182 #region Instance Fields 183 [FieldOffset(0)] readonly ulong _bucketMask; 184 [FieldOffset(8)] internal ulong _pos; 185 [FieldOffset(16)] ulong _stride; 186 #endregion 187 188 #region Type-level Properties 189 #endregion 190 191 #region Instance Properties 192 #endregion 193 194 #region Type-level Functions 195 #endregion 196 197 #region Instance Functions 198 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<ulong>.AdvanceByDefault(ref this, n); 199 public ulong Count() => IIterator<ulong>.CountDefault(ref this); 200 public TInit Fold<TInit>(TInit init, Fn<TInit, ulong, TInit> f) where TInit: notnull => IIterator<ulong>.FoldDefault(ref this, init, f); 201 public override readonly bool Equals(object? _) => false; 202 public override readonly int GetHashCode() => 0; 203 public readonly ProbeSeq Into() => this; 204 public Maybe<ulong> Last() => IIterator<ulong>.LastDefault(ref this); 205 [MethodImpl(MethodImplOptions.AggressiveInlining)] 206 public Maybe<ulong> Next() { 207 System.Diagnostics.Debug.Assert(_stride <= _bucketMask); 208 var res = _pos; 209 _stride += Group.WIDTH; 210 _pos += _stride; 211 _pos &= _bucketMask; 212 return new(res); 213 } 214 public override readonly string ToString() => string.Empty; 215 public Result<TInit, TErr> TryFold<TInit, TErr>(TInit init, Fn<TInit, ulong, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull => IIterator<ulong>.TryFoldDefault(ref this, init, f); 216 readonly Result<ProbeSeq, Bottom> ITryInto<ProbeSeq, Bottom>.TryInto() => new(this); 217 #endregion 218 219 #region Operators 220 #endregion 221 222 #region Types 223 #endregion 224 } 225 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 226 struct RawIterRange<T>: IClone<RawIterRange<T>>, IInto<RawIterRange<T>>, IFusedIterator<Bucket<T>> where T: notnull { 227 228 #region Type-level Constructors 229 #endregion 230 231 #region Instance Constructors 232 public RawIterRange() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 233 [MethodImpl(MethodImplOptions.AggressiveInlining)] 234 RawIterRange(Bucket<T> data, NonNull<byte> nextCtrl, NonNull<byte> end, BitMask currentGroup) => (_data, _nextCtrl, _end, _currentGroup) = (data, nextCtrl, end, currentGroup); 235 #endregion 236 237 #region Type-level Fields 238 #endregion 239 240 #region Instance Fields 241 Bucket<T> _data; 242 NonNull<byte> _nextCtrl; 243 readonly NonNull<byte> _end; 244 BitMask _currentGroup; 245 #endregion 246 247 #region Type-level Properties 248 #endregion 249 250 #region Instance Properties 251 #endregion 252 253 #region Type-level Functions 254 [MethodImpl(MethodImplOptions.AggressiveInlining)] 255 internal static RawIterRange<T> New(NonNull<byte> ctrl, Bucket<T> data, ulong len) { 256 System.Diagnostics.Debug.Assert(len != ulong.MinValue); 257 var end = ctrl.Add(len); 258 BitMask currentGroup; 259 unsafe { 260 fixed (byte* ptr = &ctrl._ptr[(int)ctrl._index]) { 261 currentGroup = Group.LoadAligned(ptr).MatchFull(); 262 } 263 } 264 var nextCtrl = ctrl.Add(Group.WIDTH); 265 return new(data, nextCtrl, end, currentGroup); 266 } 267 #endregion 268 269 #region Instance Functions 270 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<Bucket<T>>.AdvanceByDefault(ref this, n); 271 public readonly RawIterRange<T> Clone() => new(_data.Clone(), _nextCtrl.Clone(), _end, _currentGroup); 272 public ulong Count() => IIterator<Bucket<T>>.CountDefault(ref this); 273 public TInit Fold<TInit>(TInit init, Fn<TInit, Bucket<T>, TInit> f) where TInit: notnull => IIterator<Bucket<T>>.FoldDefault(ref this, init, f); 274 public override readonly bool Equals(object? _) => false; 275 public override readonly int GetHashCode() => 0; 276 public readonly RawIterRange<T> Into() => this; 277 public Maybe<Bucket<T>> Last() => IIterator<Bucket<T>>.LastDefault(ref this); 278 [MethodImpl(MethodImplOptions.AggressiveInlining)] 279 public Maybe<Bucket<T>> Next() { 280 281 unsafe { 282 while (true) { 283 var index = _currentGroup.LowestSetBit(); 284 285 if (index.IsSome) { 286 _currentGroup = _currentGroup.RemoveLowestBit(); 287 return new(_data.NextN(index._some)); 288 } else if (_nextCtrl >= _end) { 289 return Maybe<Bucket<T>>.None(); 290 } else { 291 292 fixed (byte* ptr = &_nextCtrl._ptr[(int)_nextCtrl._index]) { 293 _currentGroup = Group.LoadAligned(ptr).MatchFull(); 294 } 295 _data = _data.NextN(Group.WIDTH); 296 _nextCtrl = _nextCtrl.Add(Group.WIDTH); 297 } 298 } 299 } 300 } 301 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => new(ulong.MinValue, new(_end.OffsetFrom(_nextCtrl) + Group.WIDTH)); 302 public override readonly string ToString() => string.Empty; 303 public Result<TInit, TErr> TryFold<TInit, TErr>(TInit init, Fn<TInit, Bucket<T>, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull => IIterator<Bucket<T>>.TryFoldDefault(ref this, init, f); 304 readonly Result<RawIterRange<T>, Bottom> ITryInto<RawIterRange<T>, Bottom>.TryInto() => new(this); 305 #endregion 306 307 #region Operators 308 #endregion 309 310 #region Types 311 #endregion 312 } 313 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 314 struct RawIter<T>: IClone<RawIter<T>>, IInto<RawIter<T>>, IExactSizeIterator<Bucket<T>>, IFusedIterator<Bucket<T>> where T: notnull { 315 316 #region Type-level Constructors 317 #endregion 318 319 #region Instance Constructors 320 public RawIter() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 321 [MethodImpl(MethodImplOptions.AggressiveInlining)] 322 internal RawIter(RawIterRange<T> iter, ulong items) => (_iter, _items) = (iter, items); 323 #endregion 324 325 #region Type-level Fields 326 #endregion 327 328 #region Instance Fields 329 RawIterRange<T> _iter; 330 ulong _items; 331 #endregion 332 333 #region Type-level Properties 334 #endregion 335 336 #region Instance Properties 337 #endregion 338 339 #region Type-level Functions 340 #endregion 341 342 #region Instance Functions 343 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<Bucket<T>>.AdvanceByDefault(ref this, n); 344 public readonly RawIter<T> Clone() => new(_iter.Clone(), _items); 345 public ulong Count() => IIterator<Bucket<T>>.CountDefault(ref this); 346 public TInit Fold<TInit>(TInit init, Fn<TInit, Bucket<T>, TInit> f) where TInit: notnull => IIterator<Bucket<T>>.FoldDefault(ref this, init, f); 347 public override readonly bool Equals(object? _) => false; 348 public override readonly int GetHashCode() => 0; 349 public readonly RawIter<T> Into() => this; 350 public readonly bool IsEmpty() => Len() == ulong.MinValue; 351 public Maybe<Bucket<T>> Last() => IIterator<Bucket<T>>.LastDefault(ref this); 352 public readonly ulong Len() => SizeHint().Item0; 353 [MethodImpl(MethodImplOptions.AggressiveInlining)] 354 public Maybe<Bucket<T>> Next() { 355 356 var val = _iter.Next(); 357 358 if (val.IsSome) { 359 _items -= 1ul; 360 return val; 361 } else { 362 System.Diagnostics.Debug.Assert(_items == ulong.MinValue); 363 return Maybe<Bucket<T>>.None(); 364 } 365 } 366 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => new(_items, new(_items)); 367 public override readonly string ToString() => string.Empty; 368 public Result<TInit, TErr> TryFold<TInit, TErr>(TInit init, Fn<TInit, Bucket<T>, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull => IIterator<Bucket<T>>.TryFoldDefault(ref this, init, f); 369 readonly Result<RawIter<T>, Bottom> ITryInto<RawIter<T>, Bottom>.TryInto() => new(this); 370 #endregion 371 372 #region Operators 373 #endregion 374 375 #region Types 376 #endregion 377 } 378 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 379 struct RawIntoIter<T>: IInto<RawIntoIter<T>>, IExactSizeIterator<T>, IFusedIterator<T> where T: notnull { 380 381 #region Type-level Constructors 382 #endregion 383 384 #region Instance Constructors 385 public RawIntoIter() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 386 [MethodImpl(MethodImplOptions.AggressiveInlining)] 387 internal RawIntoIter(RawIter<T> iter) => _iter = iter; 388 #endregion 389 390 #region Type-level Fields 391 #endregion 392 393 #region Instance Fields 394 RawIter<T> _iter; 395 #endregion 396 397 #region Type-level Properties 398 #endregion 399 400 #region Instance Properties 401 #endregion 402 403 #region Type-level Functions 404 #endregion 405 406 #region Instance Functions 407 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<T>.AdvanceByDefault(ref this, n); 408 public ulong Count() => IIterator<T>.CountDefault(ref this); 409 public TInit Fold<TInit>(TInit init, Fn<TInit, T, TInit> f) where TInit: notnull => IIterator<T>.FoldDefault(ref this, init, f); 410 public override readonly bool Equals(object? _) => false; 411 public override readonly int GetHashCode() => 0; 412 public readonly RawIntoIter<T> Into() => this; 413 public readonly bool IsEmpty() => Len() == ulong.MinValue; 414 public readonly RawIter<T> Iter() => _iter.Clone(); 415 public Maybe<T> Last() => IIterator<T>.LastDefault(ref this); 416 public readonly ulong Len() => SizeHint().Item0; 417 [MethodImpl(MethodImplOptions.AggressiveInlining)] 418 public Maybe<T> Next() { 419 var next = _iter.Next(); 420 return next.IsSome ? new(next._some.Read()) : Maybe<T>.None(); 421 } 422 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => _iter.SizeHint(); 423 public override readonly string ToString() => string.Empty; 424 public Result<TInit, TErr> TryFold<TInit, TErr>(TInit init, Fn<TInit, T, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull => IIterator<T>.TryFoldDefault(ref this, init, f); 425 readonly Result<RawIntoIter<T>, Bottom> ITryInto<RawIntoIter<T>, Bottom>.TryInto() => new(this); 426 #endregion 427 428 #region Operators 429 #endregion 430 431 #region Types 432 #endregion 433 } 434 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Ansi, Pack = 0)] 435 struct RawTable<T>: IInto<RawTable<T>>, IIntoIterator<T, RawIntoIter<T>> where T: notnull { 436 437 #region Type-level Constructors 438 #endregion 439 440 #region Instance Constructors 441 public RawTable() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 442 [MethodImpl(MethodImplOptions.AggressiveInlining)] 443 internal RawTable(ulong bucketMask, byte[] ctrl, ulong growthLeft, ulong items, T[] table) => (_bucketMask, _ctrl, _growthLeft, _items, _table) = (bucketMask, ctrl, growthLeft, items, table); 444 #endregion 445 446 #region Type-level Fields 447 #endregion 448 449 #region Instance Fields 450 internal byte[] _ctrl; 451 internal T[] _table; 452 internal ulong _bucketMask; 453 internal ulong _growthLeft; 454 internal ulong _items; 455 #endregion 456 457 #region Type-level Properties 458 #endregion 459 460 #region Instance Properties 461 #endregion 462 463 #region Type-level Functions 464 [MethodImpl(MethodImplOptions.AggressiveInlining)] 465 internal static RawTable<T> New() => new(ulong.MinValue, Group.EMPTY_GROUP, ulong.MinValue, ulong.MinValue, Array.Empty<T>()); 466 [MethodImpl(MethodImplOptions.AggressiveInlining)] 467 static RawTable<T> NewUninitialized(ulong buckets) { 468 System.Diagnostics.Debug.Assert(buckets.IsPowerOfTwo()); 469 var val = CalculateLayout<T>(buckets); 470 return new(buckets - 1ul, val.Item1, BucketMaskToCapacity(buckets - 1ul), ulong.MinValue, val.Item0); 471 } 472 [MethodImpl(MethodImplOptions.AggressiveInlining)] 473 internal static RawTable<T> WithCapacity(ulong capacity) { 474 475 if (capacity == ulong.MinValue) { 476 return New(); 477 } else { 478 var buckets = CapacityToBuckets<ulong>(capacity).Unwrap(); 479 var result = NewUninitialized(buckets); 480 _ = result._ctrl.WriteBytes(ulong.MinValue, EMPTY, result.NumCtrlBytes()); 481 return result; 482 } 483 } 484 #endregion 485 486 #region Instance Functions 487 [MethodImpl(MethodImplOptions.AggressiveInlining)] 488 internal readonly Bucket<T> Bucket(ulong index) { 489 System.Diagnostics.Debug.Assert(_bucketMask != ulong.MinValue); 490 System.Diagnostics.Debug.Assert(index < Buckets()); 491 return Bucket<T>.FromBaseIndex(new(_table, DataEnd()), index); 492 } 493 [MethodImpl(MethodImplOptions.AggressiveInlining)] 494 readonly ulong BucketIndex(in Bucket<T> bucket) => bucket.ToBaseIndex(new(_table, DataEnd())); 495 [MethodImpl(MethodImplOptions.AggressiveInlining)] 496 internal readonly ulong Buckets() => _bucketMask + 1ul; 497 [MethodImpl(MethodImplOptions.AggressiveInlining)] 498 internal readonly ulong Capacity() => _items + _growthLeft; 499 [MethodImpl(MethodImplOptions.AggressiveInlining)] 500 internal Unit Clear() { 501 502 if (!IsEmptySingleton()) { 503 _ = _ctrl.WriteBytes(ulong.MinValue, EMPTY, NumCtrlBytes()); 504 } 505 _items = ulong.MinValue; 506 _growthLeft = BucketMaskToCapacity(_bucketMask); 507 return new Unit(); 508 } 509 [MethodImpl(MethodImplOptions.AggressiveInlining)] 510 readonly ulong DataEnd() => (ulong)_table.Length; 511 public override readonly bool Equals(object? _) => false; 512 [MethodImpl(MethodImplOptions.AggressiveInlining)] 513 internal Unit Erase(Bucket<T> item) { 514 515 var index = BucketIndex(in item); 516 System.Diagnostics.Debug.Assert(IsFull(_ctrl[(int)index])); 517 var indexBefore = (index.WrappingSub(Group.WIDTH)) & _bucketMask; 518 BitMask emptyBefore; 519 unsafe { 520 fixed (byte* ptr = &_ctrl[(int)indexBefore]) { 521 emptyBefore = Group.Load(ptr).MatchEmpty(); 522 } 523 } 524 BitMask emptyAfter; 525 unsafe { 526 fixed (byte* ptr = &_ctrl[(int)index]) { 527 emptyAfter = Group.Load(ptr).MatchEmpty(); 528 } 529 } 530 byte ctrl; 531 532 if (emptyBefore.LeadingZeros() + emptyAfter.TrailingZeros() >= Group.WIDTH) { 533 ctrl = DELETED; 534 } else { 535 _growthLeft += 1ul; 536 ctrl = EMPTY; 537 } 538 _items -= 1ul; 539 return SetCtrl(index, ctrl); 540 } 541 [MethodImpl(MethodImplOptions.AggressiveInlining)] 542 internal readonly Maybe<Bucket<T>> Find(ulong hash, FnIn<T, bool> eq) { 543 var iterHash = IterHash(hash); 544 Maybe<Bucket<T>> bucket; 545 546 while ((bucket = iterHash.Next()).IsSome) { 547 ref readonly var elm = ref bucket._some.AsRef(); 548 549 if (eq(in elm)) { 550 return new(bucket._some); 551 } 552 } 553 return Maybe<Bucket<T>>.None(); 554 } 555 [MethodImpl(MethodImplOptions.AggressiveInlining)] 556 readonly ulong FindInsertSlot(ulong hash) { 557 558 var probe = ProbeSeq(hash); 559 Maybe<ulong> pos; 560 unsafe { 561 while ((pos = probe.Next()).IsSome) { 562 563 Maybe<ulong> bit; 564 fixed (byte* ptr = &_ctrl[(int)pos._some]) { 565 bit = Group.Load(ptr).MatchEmptyOrDeleted().LowestSetBit(); 566 } 567 568 if (bit.IsSome) { 569 var result = (pos._some + bit._some) & _bucketMask; 570 571 if (IsFull(_ctrl[(int)result])) { 572 System.Diagnostics.Debug.Assert(_bucketMask < Group.WIDTH); 573 System.Diagnostics.Debug.Assert(pos._some != ulong.MinValue); 574 575 fixed (byte* ptr = &_ctrl[0]) { 576 return Group.LoadAligned(ptr).MatchEmptyOrDeleted().LowestSetBitNonZero(); 577 } 578 } else { 579 return result; 580 } 581 } 582 } 583 } 584 throw new InvalidOperationException("There is a bug in Std.Hashbrown.Raw.RawTable.FindInsertSlot! An empty slot in the hash map was never found which should be impossible."); 585 } 586 public override readonly int GetHashCode() => 0; 587 [MethodImpl(MethodImplOptions.AggressiveInlining)] 588 internal Bucket<T> Insert(ulong hash, T value, FnIn<T, ulong> hasher) { 589 var index = FindInsertSlot(hash); 590 var oldCtrl = _ctrl[(int)index]; 591 592 if (_growthLeft == ulong.MinValue && SpecialIsEmpty(oldCtrl)) { 593 _ = Reserve(1ul, hasher); 594 index = FindInsertSlot(hash); 595 } 596 var bucket = Bucket(index); 597 _growthLeft -= SpecialIsEmpty(oldCtrl) ? 1ul : ulong.MinValue; 598 _ = SetCtrl(index, H2(hash)); 599 _ = bucket.Write(value); 600 _items += 1ul; 601 return bucket; 602 } 603 public readonly RawTable<T> Into() => this; 604 [MethodImpl(MethodImplOptions.AggressiveInlining)] 605 public readonly RawIntoIter<T> IntoIter() { 606 var iter = Iter(); 607 return IntoIterFrom(in iter); 608 } 609 [MethodImpl(MethodImplOptions.AggressiveInlining)] 610 internal readonly RawIntoIter<T> IntoIterFrom(in RawIter<T> iter) { 611 System.Diagnostics.Debug.Assert(iter.Len() == Len()); 612 return new(iter); 613 } 614 [MethodImpl(MethodImplOptions.AggressiveInlining)] 615 readonly bool IsEmptySingleton() => _bucketMask == ulong.MinValue; 616 [MethodImpl(MethodImplOptions.AggressiveInlining)] 617 internal readonly RawIter<T> Iter() { 618 619 var data = Bucket<T>.FromBaseIndex(new(_table, DataEnd()), ulong.MinValue); 620 return new(RawIterRange<T>.New(new(_ctrl, ulong.MinValue), data, Buckets()), _items); 621 } 622 readonly RawIterHash<T> IterHash(ulong hash) => RawIterHash<T>.New(this, hash); 623 [MethodImpl(MethodImplOptions.AggressiveInlining)] 624 internal readonly ulong Len() => _items; 625 [MethodImpl(MethodImplOptions.AggressiveInlining)] 626 readonly ulong NumCtrlBytes() => _bucketMask + 1ul + Group.WIDTH; 627 [MethodImpl(MethodImplOptions.AggressiveInlining)] 628 internal readonly ProbeSeq ProbeSeq(ulong hash) => new(_bucketMask, H1(hash) & _bucketMask, ulong.MinValue); 629 [MethodImpl(MethodImplOptions.NoInlining)] 630 Unit RehashInPlace(FnIn<T, ulong> hasher) { 631 unsafe { 632 fixed (byte* ptr = _ctrl) { 633 for (var i = ulong.MinValue; i < Buckets(); i += Group.WIDTH) { 634 _ = Group.LoadAligned(ptr + i).ConvertSpecialToEmptyAndFullToDeleted().StoreAligned(ptr + i); 635 } 636 } 637 } 638 if (Buckets() < Group.WIDTH) { 639 Array.Copy(_ctrl, 0L, _ctrl, (long)Group.WIDTH, (long)Buckets()); 640 } else { 641 Array.Copy(_ctrl, 0L, _ctrl, (long)Buckets(), (long)Group.WIDTH); 642 } 643 644 for (var i = ulong.MinValue; i < Buckets(); i++) { 645 646 if (_ctrl[(int)i] != DELETED) { 647 continue; 648 } 649 while (true) { 650 var item = Bucket(i); 651 var hash = hasher(in item.AsRef()); 652 var newI = FindInsertSlot(hash); 653 var copy = this; 654 ulong probeIndex(ulong pos) => ((pos - copy.ProbeSeq(hash)._pos) & copy._bucketMask) / Group.WIDTH; 655 656 if (probeIndex(i) == probeIndex(newI)) { 657 _ = SetCtrl(i, H2(hash)); 658 break; 659 } 660 var prevCtrl = _ctrl[(int)newI]; 661 _ = SetCtrl(newI, H2(hash)); 662 663 if (prevCtrl == EMPTY) { 664 _ = SetCtrl(i, EMPTY); 665 _ = Bucket(newI).CopyFromNonoverlapping(in item); 666 break; 667 } else { 668 System.Diagnostics.Debug.Assert(prevCtrl == DELETED); 669 (Bucket(newI).AsMut(), item.AsMut()) = (item.AsMut(), Bucket(newI).AsMut()); 670 continue; 671 } 672 } 673 } 674 _growthLeft = BucketMaskToCapacity(_bucketMask) - _items; 675 return new Unit(); 676 } 677 [MethodImpl(MethodImplOptions.AggressiveInlining)] 678 internal T Remove(Bucket<T> item) { 679 680 var index = BucketIndex(in item); 681 System.Diagnostics.Debug.Assert(IsFull(_ctrl[(int)index])); 682 var indexBefore = (index - Group.WIDTH) & _bucketMask; 683 BitMask emptyBefore; 684 unsafe { 685 fixed (byte* ptr = &_ctrl[(int)indexBefore]) { 686 emptyBefore = Group.Load(ptr).MatchEmpty(); 687 } 688 } 689 BitMask emptyAfter; 690 unsafe { 691 fixed (byte* ptr = &_ctrl[(int)index]) { 692 emptyAfter = Group.Load(ptr).MatchEmpty(); 693 } 694 } 695 byte ctrl; 696 697 if (emptyBefore.LeadingZeros() + emptyAfter.TrailingZeros() >= Group.WIDTH) { 698 ctrl = DELETED; 699 } else { 700 _growthLeft += 1ul; 701 ctrl = EMPTY; 702 } 703 _items -= 1ul; 704 _ = SetCtrl(index, ctrl); 705 return item.Read(); 706 } 707 [MethodImpl(MethodImplOptions.AggressiveInlining)] 708 internal Unit Reserve(ulong additional, FnIn<T, ulong> hasher) { 709 710 if (additional > _growthLeft) { 711 _ = ReserveRehash(additional, hasher); 712 } 713 return new Unit(); 714 } 715 [MethodImpl(MethodImplOptions.NoInlining)] 716 Unit ReserveRehash(ulong additional, FnIn<T, ulong> hasher) { 717 718 var newItems = _items.CheckedAdd(additional).Unwrap(); 719 var fullCapacity = BucketMaskToCapacity(_bucketMask); 720 return newItems <= fullCapacity / 2ul ? RehashInPlace(hasher) : Resize(newItems >= fullCapacity + 1ul ? newItems : fullCapacity + 1ul, hasher); 721 } 722 [MethodImpl(MethodImplOptions.AggressiveInlining)] 723 Unit Resize(ulong capacity, FnIn<T, ulong> hasher) { 724 System.Diagnostics.Debug.Assert(_items <= capacity); 725 var newTable = WithCapacity(capacity); 726 newTable._growthLeft -= _items; 727 newTable._items = _items; 728 var iter = Iter(); 729 Maybe<Bucket<T>> item; 730 731 while ((item = iter.Next()).IsSome) { 732 var hash = hasher(in item._some.AsRef()); 733 var index = newTable.FindInsertSlot(hash); 734 _ = newTable.SetCtrl(index, H2(hash)); 735 _ = newTable.Bucket(index).CopyFromNonoverlapping(in item._some); 736 } 737 this = newTable; 738 return new Unit(); 739 } 740 [MethodImpl(MethodImplOptions.AggressiveInlining)] 741 readonly Unit SetCtrl(ulong index, byte ctrl) { 742 743 var index2 = ((index.WrappingSub(Group.WIDTH)) & _bucketMask) + Group.WIDTH; 744 _ctrl[(int)index] = ctrl; 745 _ctrl[(int)index2] = ctrl; 746 return new Unit(); 747 } 748 [MethodImpl(MethodImplOptions.AggressiveInlining)] 749 internal Unit ShrinkTo(ulong minSize, FnIn<T, ulong> hasher) { 750 751 minSize = minSize >= _items ? minSize : _items; 752 753 if (minSize == ulong.MinValue) { 754 this = New(); 755 return new Unit(); 756 } 757 var minBuckets = CapacityToBuckets<ulong>(minSize); 758 759 if (minBuckets.IsNone) { 760 return new Unit(); 761 } 762 763 if (minBuckets._some < Buckets()) { 764 765 if (_items == ulong.MinValue) { 766 this = WithCapacity(minSize); 767 } else { 768 _ = Resize(minSize, hasher); 769 } 770 } 771 return new Unit(); 772 } 773 public override readonly string ToString() => string.Empty; 774 readonly Result<RawTable<T>, Bottom> ITryInto<RawTable<T>, Bottom>.TryInto() => new(this); 775 #endregion 776 777 #region Operators 778 #endregion 779 780 #region Types 781 #endregion 782 } 783 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 784 struct RawIterHash<T>: IInto<RawIterHash<T>>, IIterator<Bucket<T>> where T: notnull { 785 786 #region Type-level Constructors 787 #endregion 788 789 #region Instance Constructors 790 public RawIterHash() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 791 [MethodImpl(MethodImplOptions.AggressiveInlining)] 792 RawIterHash(RawTable<T> table, byte h2Hash, ProbeSeq probeSeq, ulong pos, Group group, BitMaskIter bitmask) => (_table, _h2Hash, _probeSeq, _pos, _group, _bitmask) = (table, h2Hash, probeSeq, pos, group, bitmask); 793 #endregion 794 795 #region Type-level Fields 796 #endregion 797 798 #region Instance Fields 799 readonly RawTable<T> _table; 800 ProbeSeq _probeSeq; 801 Group _group; 802 ulong _pos; 803 BitMaskIter _bitmask; 804 readonly byte _h2Hash; 805 #endregion 806 807 #region Type-level Properties 808 #endregion 809 810 #region Instance Properties 811 #endregion 812 813 #region Type-level Functions 814 [MethodImpl(MethodImplOptions.AggressiveInlining)] 815 internal static RawIterHash<T> New(RawTable<T> table, ulong hash) { 816 var h2Hash = H2(hash); 817 var probeSeq = table.ProbeSeq(hash); 818 var pos = probeSeq.Next().Unwrap(); 819 Group group; 820 unsafe { 821 fixed (byte* ptr = &table._ctrl[(int)pos]) { 822 group = Group.Load(ptr); 823 } 824 } 825 var bitmask = group.MatchByte(h2Hash).IntoIter(); 826 return new(table, h2Hash, probeSeq, pos, group, bitmask); 827 } 828 #endregion 829 830 #region Instance Functions 831 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<Bucket<T>>.AdvanceByDefault(ref this, n); 832 public ulong Count() => IIterator<Bucket<T>>.CountDefault(ref this); 833 public TInit Fold<TInit>(TInit init, Fn<TInit, Bucket<T>, TInit> f) where TInit: notnull => IIterator<Bucket<T>>.FoldDefault(ref this, init, f); 834 public override readonly bool Equals(object? _) => false; 835 public override readonly int GetHashCode() => 0; 836 public readonly RawIterHash<T> Into() => this; 837 public Maybe<Bucket<T>> Last() => IIterator<Bucket<T>>.LastDefault(ref this); 838 [MethodImpl(MethodImplOptions.AggressiveInlining)] 839 public Maybe<Bucket<T>> Next() { 840 841 unsafe { 842 while (true) { 843 var bit = _bitmask.Next(); 844 845 if (bit.IsSome) { 846 var index = (_pos + bit._some) & _table._bucketMask; 847 var bucket = _table.Bucket(index); 848 return new(bucket); 849 } else if (_group.MatchEmpty().AnyBitSet()) { 850 return Maybe<Bucket<T>>.None(); 851 } else { 852 _pos = _probeSeq.Next().Unwrap(); 853 854 fixed (byte* ptr = &_table._ctrl[(int)_pos]) { 855 _group = Group.Load(ptr); 856 } 857 _bitmask = _group.MatchByte(_h2Hash).IntoIter(); 858 } 859 } 860 } 861 } 862 public override readonly string ToString() => string.Empty; 863 public Result<TInit, TErr> TryFold<TInit, TErr>(TInit init, Fn<TInit, Bucket<T>, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull => IIterator<Bucket<T>>.TryFoldDefault(ref this, init, f); 864 readonly Result<RawIterHash<T>, Bottom> ITryInto<RawIterHash<T>, Bottom>.TryInto() => new(this); 865 #endregion 866 867 #region Operators 868 #endregion 869 870 #region Types 871 #endregion 872 } 873 static class Functions { 874 875 #region Type-level Constructors 876 #endregion 877 878 #region Instance Constructors 879 #endregion 880 881 #region Type-level Fields 882 internal const byte DELETED = 0b1000_0000; 883 internal const byte EMPTY = 0b1111_1111; 884 #endregion 885 886 #region Instance Fields 887 #endregion 888 889 #region Type-level Properties 890 #endregion 891 892 #region Instance Properties 893 #endregion 894 895 #region Type-level Functions 896 [MethodImpl(MethodImplOptions.AggressiveInlining)] 897 internal static ulong BucketMaskToCapacity(ulong bucketMask) => bucketMask < 8ul ? bucketMask : (bucketMask + 1ul) / 8ul * 7ul; 898 [MethodImpl(MethodImplOptions.AggressiveInlining)] 899 internal static Prod<T[], byte[]> CalculateLayout<T>(ulong buckets) where T: notnull { 900 System.Diagnostics.Debug.Assert(buckets.IsPowerOfTwo()); 901 var size = buckets + Group.WIDTH; 902 var div = size / Group.WIDTH; 903 return new(new T[(int)buckets], new byte[(int)(Group.WIDTH * ((size & (Group.WIDTH - 1ul)) == ulong.MinValue ? div : div + 1ul))]); 904 } 905 [MethodImpl(MethodImplOptions.AggressiveInlining)] 906 internal static Maybe<ulong> CapacityToBuckets<T>(ulong cap) where T: notnull { 907 System.Diagnostics.Debug.Assert(cap != ulong.MinValue); 908 if (cap < 8ul) { 909 return new(cap < 4ul ? 4ul : 8ul); 910 } 911 checked { 912 913 try { 914 cap *= 8ul; 915 } catch (OverflowException) { 916 return Maybe<ulong>.None(); 917 } 918 } 919 return new((cap / 7ul).NextPowerOfTwo()); 920 } 921 [MethodImpl(MethodImplOptions.AggressiveInlining)] 922 internal static RawTable<ProdMut<TKey, TValue>> Clone<TKey, TValue>(in this RawTable<ProdMut<TKey, TValue>> self) where TKey: notnull, IClone<TKey> where TValue: notnull, IClone<TValue> { 923 924 var val = new byte[self._ctrl.Length]; 925 926 for (var i = 0; i < val.Length; i++) { 927 val[i] = self._ctrl[i]; 928 } 929 var val2 = new ProdMut<TKey, TValue>[self._table.Length]; 930 931 for (var i = 0; i < val2.Length; i++) { 932 val2[i] = self._table[i].Clone(); 933 } 934 return new(self._bucketMask, val, self._growthLeft, self._items, val2); 935 } 936 [MethodImpl(MethodImplOptions.AggressiveInlining)] 937 internal static ulong H1(ulong hash) => hash; 938 [MethodImpl(MethodImplOptions.AggressiveInlining)] 939 internal static byte H2(ulong hash) => (byte)(hash >> 57); 940 [MethodImpl(MethodImplOptions.AggressiveInlining)] 941 internal static bool IsFull(byte ctrl) => (ctrl & 0x80u) == uint.MinValue; 942 [MethodImpl(MethodImplOptions.AggressiveInlining)] 943 internal static bool IsSpecial(byte ctrl) => (ctrl & 0x80u) != uint.MinValue; 944 [MethodImpl(MethodImplOptions.AggressiveInlining)] 945 internal static bool SpecialIsEmpty(byte ctrl) { 946 System.Diagnostics.Debug.Assert(IsSpecial(ctrl)); 947 return (ctrl & 0x01u) != uint.MinValue; 948 } 949 [MethodImpl(MethodImplOptions.AggressiveInlining)] 950 internal static Unit WriteBytes(this byte[] self, ulong start, byte val, ulong count) { 951 952 for (var i = (int)start; i < (int)(count + start); i++) { 953 self[i] = val; 954 } 955 return new Unit(); 956 } 957 [MethodImpl(MethodImplOptions.AggressiveInlining)] 958 internal static Unit WriteBytes(this NonNull<byte> self, byte val, ulong count) { 959 960 for (var i = (int)self._index; i < (int)(count + self._index); i++) { 961 self._ptr[i] = val; 962 } 963 return new Unit(); 964 } 965 #endregion 966 967 #region Instance Functions 968 #endregion 969 970 #region Operators 971 #endregion 972 973 #region Types 974 #endregion 975 } 976 #endregion 977 978 #region Namespaces 979 #endregion 980 } 981 #endregion