HashMap.cs (18250B)
1 using Std.Clone; 2 using Std.Cmp; 3 using Std.Convert; 4 using static Std.Hashbrown.HashMap.Functions; 5 using Std.Hashbrown.Raw; 6 using Std.Hashing; 7 using Std.Iter; 8 using Std.Maybe; 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.HashMap { 16 #region Types 17 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 18 struct HashMap<TKey, TValue, THasher, TBuildHasher>: IExtend<ProdMut<TKey, TValue>>, IIndex<TKey, TValue>, IInto<HashMap<TKey, TValue, THasher, TBuildHasher>>, IIntoIterator<ProdMut<TKey, TValue>, IntoIter<TKey, TValue>> where TKey: notnull, IEq<TKey>, IHashable where TValue: notnull where THasher: notnull, IHasher where TBuildHasher: notnull, IBuildHasher<THasher> { 19 20 #region Type-level Constructors 21 #endregion 22 23 #region Instance Constructors 24 public HashMap() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 25 [MethodImpl(MethodImplOptions.AggressiveInlining)] 26 internal HashMap(RawTable<ProdMut<TKey, TValue>> table, TBuildHasher hashBuilder) => (_table, _hashBuilder) = (table, hashBuilder); 27 #endregion 28 29 #region Type-level Fields 30 static TValue? _dummy = default; 31 #endregion 32 33 #region Instance Fields 34 internal RawTable<ProdMut<TKey, TValue>> _table; 35 internal readonly TBuildHasher _hashBuilder; 36 #endregion 37 38 #region Type-level Properties 39 #endregion 40 41 #region Instance Properties 42 public readonly ref readonly TValue this[TKey key] { 43 [MethodImpl(MethodImplOptions.AggressiveInlining)] 44 get { 45 var hash = MakeHash<TKey, THasher, TBuildHasher>(_hashBuilder, key); 46 var item = _table.Find(hash, (in ProdMut<TKey, TValue> tup) => key == tup.Item0); 47 48 if (item.IsSome) { 49 return ref item._some.AsRef().Item1; 50 } else { 51 throw new InvalidOperationException($"No entry found for {key.ToString()}."); 52 } 53 } 54 } 55 #endregion 56 57 #region Type-level Functions 58 [MethodImpl(MethodImplOptions.AggressiveInlining)] 59 internal static HashMap<TKey, TValue, THasher, TBuildHasher> WithCapacityAndHasher(ulong capacity, TBuildHasher hashBuilder) => new(RawTable<ProdMut<TKey, TValue>>.WithCapacity(capacity), hashBuilder); 60 [MethodImpl(MethodImplOptions.AggressiveInlining)] 61 internal static HashMap<TKey, TValue, THasher, TBuildHasher> WithHasher(TBuildHasher hashBuilder) => new(RawTable<ProdMut<TKey, TValue>>.New(), hashBuilder); 62 #endregion 63 64 #region Instance Functions 65 [MethodImpl(MethodImplOptions.AggressiveInlining)] 66 internal readonly ulong Capacity() => _table.Capacity(); 67 [MethodImpl(MethodImplOptions.AggressiveInlining)] 68 internal Unit Clear() => _table.Clear(); 69 [MethodImpl(MethodImplOptions.AggressiveInlining)] 70 internal readonly bool ContainsKey(in TKey k) => Get(in k).IsSome; 71 public override readonly bool Equals(object? _) => false; 72 [MethodImpl(MethodImplOptions.AggressiveInlining)] 73 public Unit Extend<TIter>(TIter iter) where TIter: notnull, IIterator<ProdMut<TKey, TValue>> { 74 75 _ = Reserve(IsEmpty() ? iter.SizeHint().Item0 : (iter.SizeHint().Item0 + 1ul) / 2ul); 76 var cpy = this; 77 _ = iter.ForEach<TIter, ProdMut<TKey, TValue>>((tup) => { _ = cpy.Insert(tup.Item0, tup.Item1); return new Unit(); }); 78 _table = cpy._table; 79 return new Unit(); 80 } 81 [MethodImpl(MethodImplOptions.AggressiveInlining)] 82 public Unit ExtendOne(ProdMut<TKey, TValue> val) { 83 _ = Insert(val.Item0, val.Item1); 84 return new Unit(); 85 } 86 [MethodImpl(MethodImplOptions.AggressiveInlining)] 87 public Unit ExtendReserve(uint additional) => Reserve(IsEmpty() ? additional : (additional + 1u) / 2u); 88 [MethodImpl(MethodImplOptions.AggressiveInlining)] 89 internal readonly Maybe<TValue> Get(in TKey k) { 90 91 var val = GetKeyValue(in k); 92 return val.IsSome ? new(val._some.Item1) : Maybe<TValue>.None(); 93 } 94 public override readonly int GetHashCode() => 0; 95 [MethodImpl(MethodImplOptions.AggressiveInlining)] 96 internal readonly Maybe<ProdMut<TKey, TValue>> GetKeyValue(in TKey k) { 97 98 var cpy = k; 99 var hash = MakeHash<TKey, THasher, TBuildHasher>(_hashBuilder, cpy); 100 var item = _table.Find(hash, (in ProdMut<TKey, TValue> tup) => cpy == tup.Item0); 101 return item.IsSome ? new(item._some.AsRef()) : Maybe<ProdMut<TKey, TValue>>.None(); 102 } 103 [MethodImpl(MethodImplOptions.AggressiveInlining)] 104 internal readonly ref TValue GetMut(in TKey k, out bool exists) { 105 106 var cpy = k; 107 var hash = MakeHash<TKey, THasher, TBuildHasher>(_hashBuilder, cpy); 108 var item = _table.Find(hash, (in ProdMut<TKey, TValue> tup) => cpy == tup.Item0); 109 110 if (item.IsSome) { 111 exists = true; 112 return ref item._some.AsMut().Item1; 113 } else { 114 exists = false; 115 return ref _dummy!; 116 } 117 } 118 [MethodImpl(MethodImplOptions.AggressiveInlining)] 119 internal ref TValue GetOrInsert(TKey key, TValue v) { 120 121 var hash = MakeHash<TKey, THasher, TBuildHasher>(_hashBuilder, key); 122 var item = _table.Find(hash, (in ProdMut<TKey, TValue> tup) => tup.Item0 == key); 123 124 if (item.IsSome) { 125 return ref item._some.AsMut().Item1; 126 } else { 127 var hashBuilder = _hashBuilder; 128 var bucket = _table.Insert(hash, new(key, v), (in ProdMut<TKey, TValue> tup) => MakeHash<TKey, THasher, TBuildHasher>(hashBuilder, tup.Item0)); 129 return ref bucket.AsMut().Item1; 130 } 131 } 132 [MethodImpl(MethodImplOptions.AggressiveInlining)] 133 internal ref TValue GetOrInsertWith(TKey key, Fn<TValue> f) { 134 135 var hash = MakeHash<TKey, THasher, TBuildHasher>(_hashBuilder, key); 136 var item = _table.Find(hash, (in ProdMut<TKey, TValue> tup) => tup.Item0 == key); 137 138 if (item.IsSome) { 139 return ref item._some.AsMut().Item1; 140 } else { 141 var hashBuilder = _hashBuilder; 142 var bucket = _table.Insert(hash, new(key, f()), (in ProdMut<TKey, TValue> tup) => MakeHash<TKey, THasher, TBuildHasher>(hashBuilder, tup.Item0)); 143 return ref bucket.AsMut().Item1; 144 } 145 } 146 [MethodImpl(MethodImplOptions.AggressiveInlining)] 147 internal readonly ref readonly TValue GetRef(in TKey k, out bool exists) { 148 149 var cpy = k; 150 var hash = MakeHash<TKey, THasher, TBuildHasher>(_hashBuilder, cpy); 151 var item = _table.Find(hash, (in ProdMut<TKey, TValue> tup) => cpy == tup.Item0); 152 153 if (item.IsSome) { 154 exists = true; 155 return ref item._some.AsRef().Item1; 156 } else { 157 exists = false; 158 return ref _dummy!; 159 } 160 } 161 [MethodImpl(MethodImplOptions.AggressiveInlining)] 162 internal readonly TBuildHasher Hasher() => _hashBuilder; 163 [MethodImpl(MethodImplOptions.AggressiveInlining)] 164 internal Maybe<TValue> Insert(TKey k, TValue v) { 165 var hash = MakeHash<TKey, THasher, TBuildHasher>(_hashBuilder, k); 166 var item = _table.Find(hash, (in ProdMut<TKey, TValue> tup) => k == tup.Item0); 167 168 if (item.IsSome) { 169 ref var val = ref item._some.AsMut().Item1; 170 var old = val; 171 val = v; 172 return new(old); 173 } else { 174 var hashBuilder = _hashBuilder; 175 _ = _table.Insert(hash, new(k, v), (in ProdMut<TKey, TValue> tup) => MakeHash<TKey, THasher, TBuildHasher>(hashBuilder, tup.Item0)); 176 return Maybe<TValue>.None(); 177 } 178 } 179 [MethodImpl(MethodImplOptions.AggressiveInlining)] 180 public readonly HashMap<TKey, TValue, THasher, TBuildHasher> Into() => this; 181 [MethodImpl(MethodImplOptions.AggressiveInlining)] 182 public readonly IntoIter<TKey, TValue> IntoIter() => new(_table.IntoIter()); 183 [MethodImpl(MethodImplOptions.AggressiveInlining)] 184 internal readonly bool IsEmpty() => Len() == ulong.MinValue; 185 [MethodImpl(MethodImplOptions.AggressiveInlining)] 186 readonly Iter<TKey, TValue> Iter() => new(_table.Iter()); 187 [MethodImpl(MethodImplOptions.AggressiveInlining)] 188 internal readonly ulong Len() => _table.Len(); 189 [MethodImpl(MethodImplOptions.AggressiveInlining)] 190 internal Maybe<TValue> Remove(in TKey k) { 191 192 var entry = RemoveEntry(in k); 193 return entry.IsSome ? new(entry._some.Item1) : Maybe<TValue>.None(); 194 } 195 [MethodImpl(MethodImplOptions.AggressiveInlining)] 196 internal Maybe<ProdMut<TKey, TValue>> RemoveEntry(in TKey k) { 197 var cpy = k; 198 var hash = MakeHash<TKey, THasher, TBuildHasher>(_hashBuilder, cpy); 199 var item = _table.Find(hash, (in ProdMut<TKey, TValue> tup) => cpy == tup.Item0); 200 return item.IsSome ? new(_table.Remove(item._some)) : Maybe<ProdMut<TKey, TValue>>.None(); 201 } 202 [MethodImpl(MethodImplOptions.AggressiveInlining)] 203 internal Unit Reserve(ulong additional) { 204 205 var hashBuilder = _hashBuilder; 206 return _table.Reserve(additional, (in ProdMut<TKey, TValue> tup) => MakeHash<TKey, THasher, TBuildHasher>(hashBuilder, tup.Item0)); 207 } 208 [MethodImpl(MethodImplOptions.AggressiveInlining)] 209 internal Unit Retain(FnRef<TKey, TValue, bool> f) { 210 var iter = _table.Iter(); 211 Maybe<Bucket<ProdMut<TKey, TValue>>> item; 212 213 while ((item = iter.Next()).IsSome) { 214 ref var val = ref item._some.AsMut(); 215 216 if (!f(ref val.Item0, ref val.Item1)) { 217 _ = _table.Erase(item._some); 218 } 219 } 220 return new Unit(); 221 } 222 [MethodImpl(MethodImplOptions.AggressiveInlining)] 223 internal Unit ShrinkTo(ulong minCapacity) { 224 225 var hashBuilder = _hashBuilder; 226 return _table.ShrinkTo(minCapacity, (in ProdMut<TKey, TValue> tup) => MakeHash<TKey, THasher, TBuildHasher>(hashBuilder, tup.Item0)); 227 } 228 [MethodImpl(MethodImplOptions.AggressiveInlining)] 229 internal Unit ShrinkToFit() { 230 231 var hashBuilder = _hashBuilder; 232 return _table.ShrinkTo(ulong.MinValue, (in ProdMut<TKey, TValue> tup) => MakeHash<TKey, THasher, TBuildHasher>(hashBuilder, tup.Item0)); 233 } 234 public override readonly string ToString() => string.Empty; 235 [MethodImpl(MethodImplOptions.AggressiveInlining)] 236 readonly Result<HashMap<TKey, TValue, THasher, TBuildHasher>, Bottom> ITryInto<HashMap<TKey, TValue, THasher, TBuildHasher>, Bottom>.TryInto() => new(this); 237 #endregion 238 239 #region Operators 240 #endregion 241 242 #region Types 243 #endregion 244 } 245 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 246 struct IntoIter<TKey, TValue>: IInto<IntoIter<TKey, TValue>>, IExactSizeIterator<ProdMut<TKey, TValue>>, IFusedIterator<ProdMut<TKey, TValue>> where TKey: notnull where TValue: notnull { 247 248 #region Type-level Constructors 249 #endregion 250 251 #region Instance Constructors 252 public IntoIter() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 253 [MethodImpl(MethodImplOptions.AggressiveInlining)] 254 internal IntoIter(RawIntoIter<ProdMut<TKey, TValue>> inner) => _inner = inner; 255 #endregion 256 257 #region Type-level Fields 258 #endregion 259 260 #region Instance Fields 261 RawIntoIter<ProdMut<TKey, TValue>> _inner; 262 #endregion 263 264 #region Type-level Properties 265 #endregion 266 267 #region Instance Properties 268 #endregion 269 270 #region Type-level Functions 271 #endregion 272 273 #region Instance Functions 274 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<ProdMut<TKey, TValue>>.AdvanceByDefault(ref this, n); 275 public ulong Count() => IIterator<ProdMut<TKey, TValue>>.CountDefault(ref this); 276 public TInit Fold<TInit>(TInit init, Fn<TInit, ProdMut<TKey, TValue>, TInit> f) where TInit: notnull => IIterator<ProdMut<TKey, TValue>>.FoldDefault(ref this, init, f); 277 public override readonly bool Equals(object? _) => false; 278 public override readonly int GetHashCode() => 0; 279 public readonly IntoIter<TKey, TValue> Into() => this; 280 public readonly bool IsEmpty() => _inner.IsEmpty(); 281 internal readonly Iter<TKey, TValue> Iter() => new(_inner.Iter()); 282 public Maybe<ProdMut<TKey, TValue>> Last() => IIterator<ProdMut<TKey, TValue>>.LastDefault(ref this); 283 public readonly ulong Len() => _inner.Len(); 284 [MethodImpl(MethodImplOptions.AggressiveInlining)] 285 public Maybe<ProdMut<TKey, TValue>> Next() => _inner.Next(); 286 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => _inner.SizeHint(); 287 public override readonly string ToString() => string.Empty; 288 public Result<TInit, TErr> TryFold<TInit, TErr>(TInit init, Fn<TInit, ProdMut<TKey, TValue>, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull => IIterator<ProdMut<TKey, TValue>>.TryFoldDefault(ref this, init, f); 289 readonly Result<IntoIter<TKey, TValue>, Bottom> ITryInto<IntoIter<TKey, TValue>, Bottom>.TryInto() => new(this); 290 #endregion 291 292 #region Operators 293 #endregion 294 295 #region Types 296 #endregion 297 } 298 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 299 struct Iter<TKey, TValue>: IInto<Iter<TKey, TValue>>, IExactSizeIterator<ProdMut<TKey, TValue>>, IFusedIterator<ProdMut<TKey, TValue>> where TKey: notnull where TValue: notnull { 300 301 #region Type-level Constructors 302 #endregion 303 304 #region Instance Constructors 305 public Iter() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 306 [MethodImpl(MethodImplOptions.AggressiveInlining)] 307 internal Iter(RawIter<ProdMut<TKey, TValue>> inner) => _inner = inner; 308 #endregion 309 310 #region Type-level Fields 311 #endregion 312 313 #region Instance Fields 314 RawIter<ProdMut<TKey, TValue>> _inner; 315 #endregion 316 317 #region Type-level Properties 318 #endregion 319 320 #region Instance Properties 321 #endregion 322 323 #region Type-level Functions 324 #endregion 325 326 #region Instance Functions 327 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<ProdMut<TKey, TValue>>.AdvanceByDefault(ref this, n); 328 public ulong Count() => IIterator<ProdMut<TKey, TValue>>.CountDefault(ref this); 329 public TInit Fold<TInit>(TInit init, Fn<TInit, ProdMut<TKey, TValue>, TInit> f) where TInit: notnull => IIterator<ProdMut<TKey, TValue>>.FoldDefault(ref this, init, f); 330 public override readonly bool Equals(object? _) => false; 331 public override readonly int GetHashCode() => 0; 332 public readonly Iter<TKey, TValue> Into() => this; 333 public readonly bool IsEmpty() => _inner.IsEmpty(); 334 public Maybe<ProdMut<TKey, TValue>> Last() => IIterator<ProdMut<TKey, TValue>>.LastDefault(ref this); 335 public readonly ulong Len() => _inner.Len(); 336 [MethodImpl(MethodImplOptions.AggressiveInlining)] 337 public Maybe<ProdMut<TKey, TValue>> Next() { 338 339 var val = _inner.Next(); 340 return val.IsSome ? new(val._some.AsRef()) : Maybe<ProdMut<TKey, TValue>>.None(); 341 } 342 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => _inner.SizeHint(); 343 public override readonly string ToString() => string.Empty; 344 public Result<TInit, TErr> TryFold<TInit, TErr>(TInit init, Fn<TInit, ProdMut<TKey, TValue>, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull => IIterator<ProdMut<TKey, TValue>>.TryFoldDefault(ref this, init, f); 345 readonly Result<Iter<TKey, TValue>, Bottom> ITryInto<Iter<TKey, TValue>, Bottom>.TryInto() => new(this); 346 #endregion 347 348 #region Operators 349 #endregion 350 351 #region Types 352 #endregion 353 } 354 static class Functions { 355 356 #region Type-level Constructors 357 #endregion 358 359 #region Instance Constructors 360 #endregion 361 362 #region Type-level Fields 363 #endregion 364 365 #region Instance Fields 366 #endregion 367 368 #region Type-level Properties 369 #endregion 370 371 #region Instance Properties 372 #endregion 373 374 #region Type-level Functions 375 [MethodImpl(MethodImplOptions.AggressiveInlining)] 376 internal static HashMap<TKey, TValue, THasher, TBuildHasher> Clone<TKey, TValue, THasher, TBuildHasher>(in this HashMap<TKey, TValue, THasher, TBuildHasher> self) where TKey: notnull, IClone<TKey>, IEq<TKey>, IHashable where TValue: notnull, IClone<TValue> where THasher: notnull, IHasher where TBuildHasher: notnull, IBuildHasher<THasher>, IClone<TBuildHasher> => new(self._table.Clone(), self._hashBuilder.Clone()); 377 [MethodImpl(MethodImplOptions.AggressiveInlining)] 378 internal static ulong MakeHash<TKey, THasher, TBuildHasher>(TBuildHasher hashBuilder, TKey val) where TKey: notnull, IHashable where THasher: notnull, IHasher where TBuildHasher: notnull, IBuildHasher<THasher> { 379 380 var state = hashBuilder.BuildHasher(); 381 _ = val.Hash(ref state); 382 return state.Finish(); 383 } 384 #endregion 385 386 #region Instance Functions 387 #endregion 388 389 #region Operators 390 #endregion 391 392 #region Types 393 #endregion 394 } 395 #endregion 396 397 #region Namespaces 398 #endregion 399 } 400 #endregion