| | | 1 | | //======================================================================= |
| | | 2 | | // SwiftDictionary.cs |
| | | 3 | | //======================================================================= |
| | | 4 | | // MIT License, Copyright (c) 2024-present David Oravsky (mrdav30) |
| | | 5 | | // See LICENSE file in the project root for full license information. |
| | | 6 | | //======================================================================= |
| | | 7 | | |
| | | 8 | | using System; |
| | | 9 | | using System.Collections; |
| | | 10 | | using System.Collections.Generic; |
| | | 11 | | using System.Runtime.CompilerServices; |
| | | 12 | | using System.Text.Json.Serialization; |
| | | 13 | | using Chronicler; |
| | | 14 | | using Chronicler.Diagnostics; |
| | | 15 | | using Chronicler.Serialization; |
| | | 16 | | using MemoryPack; |
| | | 17 | | using SwiftCollections.Utility; |
| | | 18 | | |
| | | 19 | | namespace SwiftCollections; |
| | | 20 | | |
| | | 21 | | |
| | | 22 | | |
| | | 23 | | /// <summary> |
| | | 24 | | /// A high-performance, memory-efficient dictionary providing lightning-fast O(1) operations for addition, retrieval, an |
| | | 25 | | /// </summary> |
| | | 26 | | /// <typeparam name="TKey">Specifies the type of keys in the dictionary.</typeparam> |
| | | 27 | | /// <typeparam name="TValue">Specifies the type of values in the dictionary.</typeparam> |
| | | 28 | | /// <remarks> |
| | | 29 | | /// The comparer is not serialized. After deserialization the dictionary reverts |
| | | 30 | | /// to the same default comparer selection used by a new instance. String keys |
| | | 31 | | /// use SwiftCollections' deterministic default comparer. Object keys use a |
| | | 32 | | /// SwiftCollections comparer that hashes strings deterministically, while other |
| | | 33 | | /// object-key determinism still depends on the underlying key type's |
| | | 34 | | /// <see cref="object.GetHashCode()"/> implementation. Other key types use |
| | | 35 | | /// <see cref="EqualityComparer{TKey}.Default"/>. |
| | | 36 | | /// |
| | | 37 | | /// If a custom comparer is required it can be reapplied using |
| | | 38 | | /// <see cref="SetComparer(IEqualityComparer{TKey})"/>. |
| | | 39 | | /// </remarks> |
| | | 40 | | [Serializable] |
| | | 41 | | [JsonConverter(typeof(StateJsonConverterFactory))] |
| | | 42 | | [MemoryPackable] |
| | | 43 | | public partial class SwiftDictionary<TKey, TValue> : IStateBacked<SwiftDictionaryState<TKey, TValue>>, IDictionary<TKey, |
| | | 44 | | where TKey : notnull |
| | | 45 | | { |
| | | 46 | | #region Constants |
| | | 47 | | |
| | | 48 | | /// <summary> |
| | | 49 | | /// The default initial capacity of the dictionary. |
| | | 50 | | /// </summary> |
| | | 51 | | public const int DefaultCapacity = 8; |
| | | 52 | | |
| | | 53 | | /// <summary> |
| | | 54 | | /// Determines the maximum allowable load factor before resizing the hash set to maintain performance. |
| | | 55 | | /// </summary> |
| | | 56 | | private const double _LoadFactorThreshold = 0.82; |
| | | 57 | | |
| | | 58 | | #endregion |
| | | 59 | | |
| | | 60 | | #region Fields |
| | | 61 | | |
| | | 62 | | // Skip per-operation boxing for non-nullable value keys, including in Debug builds. |
| | | 63 | | // A cold lookup must not box a default value while initializing this flag. |
| | 15 | 64 | | private static readonly bool _KeyCanBeNull = !typeof(TKey).IsValueType |
| | 15 | 65 | | || (typeof(TKey).IsGenericType && typeof(TKey).GetGenericTypeDefinition() == typeof(Nullable<>)); |
| | | 66 | | |
| | | 67 | | /// <summary> |
| | | 68 | | /// The array containing the entries of the dictionary. |
| | | 69 | | /// </summary> |
| | | 70 | | protected internal Entry[] _entries; |
| | | 71 | | |
| | | 72 | | /// <summary> |
| | | 73 | | /// The total number of entries in the dictionary |
| | | 74 | | /// </summary> |
| | | 75 | | private int _count; |
| | | 76 | | |
| | | 77 | | /// <summary> |
| | | 78 | | /// The index of the last used entry in the dictionary. |
| | | 79 | | /// </summary> |
| | | 80 | | private int _lastIndex; |
| | | 81 | | |
| | | 82 | | /// <summary> |
| | | 83 | | /// A mask used for efficiently computing the entry arrayIndex from a hash code. |
| | | 84 | | /// This is typically the size of the entry array minus one, assuming the size is a power of two. |
| | | 85 | | /// </summary> |
| | | 86 | | private int _entryMask; |
| | | 87 | | |
| | | 88 | | /// <summary> |
| | | 89 | | /// The comparer used to determine equality of keys and to generate hash codes. |
| | | 90 | | /// </summary> |
| | | 91 | | protected IEqualityComparer<TKey> _comparer; |
| | | 92 | | |
| | | 93 | | /// <summary> |
| | | 94 | | /// Specifies the dynamic growth factor for resizing, adjusted based on recent usage patterns. |
| | | 95 | | /// </summary> |
| | | 96 | | private int _adaptiveResizeFactor; |
| | | 97 | | |
| | | 98 | | /// <summary> |
| | | 99 | | /// Tracks the count threshold at which the hash set should resize based on the load factor. |
| | | 100 | | /// </summary> |
| | | 101 | | private uint _nextResizeCount; |
| | | 102 | | |
| | | 103 | | /// <summary> |
| | | 104 | | /// Represents the moving average of the fill rate, used to dynamically adjust resizing behavior. |
| | | 105 | | /// </summary> |
| | | 106 | | private double _movingFillRate; |
| | | 107 | | |
| | | 108 | | /// <summary> |
| | | 109 | | /// The maximum number of steps allowed during probing to resolve collisions. |
| | | 110 | | /// </summary> |
| | | 111 | | private int _maxStepCount; |
| | | 112 | | |
| | | 113 | | /// <summary> |
| | | 114 | | /// A version counter used to track modifications to the dictionary. |
| | | 115 | | /// Incremented on mutations to detect changes during enumeration and ensure enumerator validity. |
| | | 116 | | /// </summary> |
| | | 117 | | [NonSerialized] |
| | | 118 | | protected uint _version; |
| | | 119 | | |
| | | 120 | | /// <summary> |
| | | 121 | | /// An object that can be used to synchronize access to the SwiftDictionary. |
| | | 122 | | /// </summary> |
| | | 123 | | [NonSerialized] |
| | | 124 | | private object? _syncRoot; |
| | | 125 | | |
| | | 126 | | #endregion |
| | | 127 | | |
| | | 128 | | #region Constructors |
| | | 129 | | |
| | | 130 | | /// <summary> |
| | | 131 | | /// Initialize a new instance of <see cref="SwiftDictionary{TKey, TValue}"/> with customizable capacity and comparer |
| | | 132 | | /// </summary> |
| | 354 | 133 | | public SwiftDictionary() : this(DefaultCapacity, null) { } |
| | | 134 | | |
| | | 135 | | /// <inheritdoc cref="SwiftDictionary()"/> |
| | 427 | 136 | | public SwiftDictionary(int capacity, IEqualityComparer<TKey>? comparer = null) |
| | | 137 | | { |
| | 427 | 138 | | Initialize(capacity, comparer); |
| | | 139 | | |
| | 427 | 140 | | ChronicleGuard.ThrowIfNull(_entries, nameof(_entries)); |
| | 427 | 141 | | ChronicleGuard.ThrowIfNull(_comparer, nameof(_comparer)); |
| | 427 | 142 | | } |
| | | 143 | | |
| | | 144 | | /// <inheritdoc cref="SwiftDictionary()"/> |
| | 2 | 145 | | public SwiftDictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey>? comparer = null) |
| | | 146 | | { |
| | 2 | 147 | | ChronicleGuard.ThrowIfNull(dictionary, nameof(dictionary)); |
| | | 148 | | |
| | 1 | 149 | | Initialize(dictionary.Count, comparer); |
| | | 150 | | |
| | 1 | 151 | | ChronicleGuard.ThrowIfNull(_entries, nameof(_entries)); |
| | 1 | 152 | | ChronicleGuard.ThrowIfNull(_comparer, nameof(_comparer)); |
| | | 153 | | |
| | 6 | 154 | | foreach (KeyValuePair<TKey, TValue> kvp in dictionary) |
| | 2 | 155 | | InsertIfNotExist(kvp.Key, kvp.Value); |
| | 1 | 156 | | } |
| | | 157 | | |
| | | 158 | | /// <inheritdoc cref="SwiftDictionary()"/> |
| | 3 | 159 | | public SwiftDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey>? comparer = null) |
| | | 160 | | { |
| | 3 | 161 | | ChronicleGuard.ThrowIfNull(collection, nameof(collection)); |
| | | 162 | | |
| | 2 | 163 | | int count = (collection as ICollection<KeyValuePair<TKey, TValue>>)?.Count ?? DefaultCapacity; |
| | | 164 | | // Dynamic padding based on collision estimation |
| | 2 | 165 | | int size = (int)(count / _LoadFactorThreshold); |
| | 2 | 166 | | Initialize(size, comparer); |
| | | 167 | | |
| | 2 | 168 | | ChronicleGuard.ThrowIfNull(_entries, nameof(_entries)); |
| | 2 | 169 | | ChronicleGuard.ThrowIfNull(_comparer, nameof(_comparer)); |
| | | 170 | | |
| | 74 | 171 | | foreach (KeyValuePair<TKey, TValue> kvp in collection) |
| | 35 | 172 | | InsertIfNotExist(kvp.Key, kvp.Value); |
| | 2 | 173 | | } |
| | | 174 | | |
| | | 175 | | /// <summary> |
| | | 176 | | /// Initializes a new instance of the <see cref="SwiftDictionary{TKey, TValue}"/> class with the specified <see cre |
| | | 177 | | /// </summary> |
| | | 178 | | /// <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa |
| | | 179 | | [MemoryPackConstructor] |
| | 11 | 180 | | public SwiftDictionary(SwiftDictionaryState<TKey, TValue> state) |
| | | 181 | | { |
| | 11 | 182 | | State = state; |
| | | 183 | | |
| | 11 | 184 | | ChronicleGuard.ThrowIfNull(_entries, nameof(_entries)); |
| | 11 | 185 | | ChronicleGuard.ThrowIfNull(_comparer, nameof(_comparer)); |
| | 11 | 186 | | } |
| | | 187 | | |
| | | 188 | | #endregion |
| | | 189 | | |
| | | 190 | | #region Properties |
| | | 191 | | |
| | | 192 | | /// <summary> |
| | | 193 | | /// Gets the number of elements contained in the dictionary. |
| | | 194 | | /// </summary> |
| | | 195 | | [JsonIgnore] |
| | | 196 | | [MemoryPackIgnore] |
| | 34 | 197 | | public int Count => _count; |
| | | 198 | | |
| | | 199 | | /// <summary> |
| | | 200 | | /// Gets the total number of elements that the collection can hold without resizing. |
| | | 201 | | /// </summary> |
| | | 202 | | [JsonIgnore] |
| | | 203 | | [MemoryPackIgnore] |
| | 17 | 204 | | public int Capacity => _entries.Length; |
| | | 205 | | |
| | | 206 | | /// <summary> |
| | | 207 | | /// Gets the equality comparer used to determine equality of keys in the collection. |
| | | 208 | | /// </summary> |
| | | 209 | | [JsonIgnore] |
| | | 210 | | [MemoryPackIgnore] |
| | 12 | 211 | | public IEqualityComparer<TKey> Comparer => _comparer; |
| | | 212 | | |
| | | 213 | | /// <summary> |
| | | 214 | | /// Gets or sets the value associated with the specified key. |
| | | 215 | | /// </summary> |
| | | 216 | | /// <remarks> |
| | | 217 | | /// Getting a value with a key that does not exist will throw an exception. |
| | | 218 | | /// Setting a value for a key that does not exist will add a new entry with the specified key and value. |
| | | 219 | | /// </remarks> |
| | | 220 | | /// <param name="key">The key whose value to get or set.</param> |
| | | 221 | | [JsonIgnore] |
| | | 222 | | [MemoryPackIgnore] |
| | | 223 | | public TValue this[TKey key] |
| | | 224 | | { |
| | | 225 | | get |
| | | 226 | | { |
| | 5479 | 227 | | int index = FindEntry(key); |
| | | 228 | | // The object-based error helper would box a value key even on a successful lookup. |
| | 5479 | 229 | | if (index < 0) |
| | 4 | 230 | | ChronicleGuard.ThrowIfKeyInvalid(index, key); |
| | 5475 | 231 | | return _entries[index].Value; |
| | | 232 | | } |
| | | 233 | | set |
| | | 234 | | { |
| | 9913 | 235 | | int index = FindEntry(key); |
| | 9913 | 236 | | if (index >= 0) |
| | 6512 | 237 | | _entries[index].Value = value; |
| | | 238 | | else |
| | | 239 | | { |
| | 3401 | 240 | | CheckLoadThreshold(); |
| | 3401 | 241 | | InsertIfNotExist(key, value); |
| | | 242 | | } |
| | 3399 | 243 | | } |
| | | 244 | | } |
| | | 245 | | |
| | | 246 | | /// <inheritdoc/> |
| | | 247 | | [JsonIgnore] |
| | | 248 | | [MemoryPackIgnore] |
| | | 249 | | object? IDictionary.this[object obj] |
| | | 250 | | { |
| | | 251 | | get |
| | | 252 | | { |
| | 19 | 253 | | ChronicleGuard.ThrowIfNull(obj, nameof(obj)); |
| | | 254 | | |
| | 18 | 255 | | if (obj is TKey key) |
| | | 256 | | { |
| | 17 | 257 | | int index = FindEntry(key); |
| | 33 | 258 | | if (index >= 0) return _entries[index].Value; |
| | | 259 | | } |
| | 2 | 260 | | return null; |
| | | 261 | | } |
| | | 262 | | set |
| | | 263 | | { |
| | 5 | 264 | | ChronicleGuard.ThrowIfNullAndNullsAreIllegal(value, default(TValue)); |
| | | 265 | | try |
| | | 266 | | { |
| | 5 | 267 | | TKey tempKey = (TKey)obj; |
| | | 268 | | try |
| | | 269 | | { |
| | 3 | 270 | | this[tempKey] = (TValue)value!; |
| | 1 | 271 | | } |
| | 2 | 272 | | catch (InvalidCastException) |
| | | 273 | | { |
| | 2 | 274 | | throw new ArgumentException($"Value {value} does not match expected {typeof(TValue)}"); |
| | | 275 | | } |
| | 1 | 276 | | } |
| | 2 | 277 | | catch (InvalidCastException) |
| | | 278 | | { |
| | 2 | 279 | | throw new ArgumentException($"Key {obj} does not match expected {typeof(TKey)}"); |
| | | 280 | | } |
| | 1 | 281 | | } |
| | | 282 | | } |
| | | 283 | | |
| | | 284 | | /// <summary> |
| | | 285 | | /// The collection containing the keys of the dictionary. |
| | | 286 | | /// </summary> |
| | | 287 | | [JsonIgnore] |
| | | 288 | | [MemoryPackIgnore] |
| | | 289 | | private KeyCollection? _keyCollection; |
| | | 290 | | |
| | | 291 | | /// <inheritdoc/> |
| | | 292 | | [JsonIgnore] |
| | | 293 | | [MemoryPackIgnore] |
| | 29 | 294 | | public ICollection<TKey> Keys => _keyCollection ??= new KeyCollection(this); |
| | | 295 | | |
| | | 296 | | [JsonIgnore] |
| | | 297 | | [MemoryPackIgnore] |
| | 8 | 298 | | ICollection IDictionary.Keys => _keyCollection ??= new KeyCollection(this); |
| | | 299 | | |
| | | 300 | | /// <summary> |
| | | 301 | | /// The collection containing the values of the dictionary. |
| | | 302 | | /// </summary> |
| | | 303 | | [JsonIgnore] |
| | | 304 | | [MemoryPackIgnore] |
| | | 305 | | private ValueCollection? _valueCollection; |
| | | 306 | | |
| | | 307 | | /// <inheritdoc/> |
| | | 308 | | [JsonIgnore] |
| | | 309 | | [MemoryPackIgnore] |
| | 30 | 310 | | public ICollection<TValue> Values => _valueCollection ??= new ValueCollection(this); |
| | | 311 | | |
| | | 312 | | [JsonIgnore] |
| | | 313 | | [MemoryPackIgnore] |
| | 3 | 314 | | ICollection IDictionary.Values => _valueCollection ??= new ValueCollection(this); |
| | | 315 | | |
| | | 316 | | [JsonIgnore] |
| | | 317 | | [MemoryPackIgnore] |
| | 1 | 318 | | bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly => false; |
| | | 319 | | |
| | | 320 | | [JsonIgnore] |
| | 1 | 321 | | [MemoryPackIgnore] bool IDictionary.IsReadOnly => false; |
| | 1 | 322 | | bool IDictionary.IsFixedSize => false; |
| | | 323 | | |
| | | 324 | | [JsonIgnore] |
| | | 325 | | [MemoryPackIgnore] |
| | 1 | 326 | | bool ICollection.IsSynchronized => false; |
| | | 327 | | |
| | | 328 | | /// <inheritdoc/> |
| | | 329 | | [JsonIgnore] |
| | | 330 | | [MemoryPackIgnore] |
| | 3 | 331 | | public object SyncRoot => _syncRoot ??= new object(); |
| | | 332 | | |
| | | 333 | | /// <summary> |
| | | 334 | | /// Gets or sets the current state of the dictionary, including all key-value pairs. |
| | | 335 | | /// </summary> |
| | | 336 | | /// <remarks> |
| | | 337 | | /// The state can be used to serialize or restore the contents of the dictionary. |
| | | 338 | | /// Setting this property replaces the entire contents of the dictionary with the provided state. |
| | | 339 | | /// The setter is intended for internal use and is not accessible to external callers. |
| | | 340 | | /// </remarks> |
| | | 341 | | [JsonInclude] |
| | | 342 | | [MemoryPackInclude] |
| | | 343 | | public SwiftDictionaryState<TKey, TValue> State |
| | | 344 | | { |
| | | 345 | | get |
| | | 346 | | { |
| | 15 | 347 | | if (_count == 0) |
| | 2 | 348 | | return new SwiftDictionaryState<TKey, TValue>(Array.Empty<KeyValuePair<TKey, TValue>>()); |
| | | 349 | | |
| | 13 | 350 | | var items = new KeyValuePair<TKey, TValue>[_count]; |
| | 13 | 351 | | CopyTo(items, 0); |
| | | 352 | | |
| | 13 | 353 | | return new SwiftDictionaryState<TKey, TValue>(items); |
| | | 354 | | } |
| | | 355 | | internal set |
| | | 356 | | { |
| | 17 | 357 | | ChronicleGuard.ThrowIfNull(value.Items, nameof(value.Items)); |
| | | 358 | | |
| | 17 | 359 | | var items = value.Items; |
| | 17 | 360 | | int count = items.Length; |
| | | 361 | | |
| | 17 | 362 | | if (count == 0) |
| | | 363 | | { |
| | 3 | 364 | | Initialize(DefaultCapacity); |
| | 3 | 365 | | _count = 0; |
| | 3 | 366 | | _version = 0; |
| | 3 | 367 | | return; |
| | | 368 | | } |
| | | 369 | | |
| | 14 | 370 | | int size = (int)(count / _LoadFactorThreshold); |
| | 14 | 371 | | Initialize(size); |
| | | 372 | | |
| | 108 | 373 | | foreach (var kvp in items) |
| | 40 | 374 | | InsertIfNotExist(kvp.Key, kvp.Value); |
| | | 375 | | |
| | 14 | 376 | | _version = 0; |
| | 14 | 377 | | } |
| | | 378 | | } |
| | | 379 | | |
| | | 380 | | #endregion |
| | | 381 | | |
| | | 382 | | #region Collection Manipulation |
| | | 383 | | |
| | | 384 | | /// <summary> |
| | | 385 | | /// Attempts to add the specified key and value to the dictionary. |
| | | 386 | | /// </summary> |
| | | 387 | | /// <param name="key">The key of the element to add.</param> |
| | | 388 | | /// <param name="value">The value of the element to add.</param> |
| | | 389 | | /// <returns> |
| | | 390 | | /// true if the key/value pair was added to the dictionary successfully; |
| | | 391 | | /// false if the key already exists. |
| | | 392 | | /// </returns> |
| | | 393 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 394 | | public virtual bool Add(TKey key, TValue value) |
| | | 395 | | { |
| | 23331 | 396 | | CheckLoadThreshold(); |
| | 23331 | 397 | | return InsertIfNotExist(key, value); |
| | | 398 | | } |
| | | 399 | | |
| | | 400 | | /// <inheritdoc/> |
| | 1 | 401 | | public void Add(KeyValuePair<TKey, TValue> item) => Add(item.Key, item.Value); |
| | | 402 | | |
| | 1 | 403 | | void IDictionary<TKey, TValue>.Add(TKey key, TValue value) => Add(key, value); |
| | | 404 | | |
| | | 405 | | /// <inheritdoc/> |
| | | 406 | | public void Add(object key, object? value) |
| | | 407 | | { |
| | 14 | 408 | | ChronicleGuard.ThrowIfNullAndNullsAreIllegal(value, default(TValue)); |
| | | 409 | | |
| | | 410 | | try |
| | | 411 | | { |
| | 14 | 412 | | TKey tempKey = (TKey)key; |
| | | 413 | | try |
| | | 414 | | { |
| | 12 | 415 | | Add(tempKey, (TValue)value!); |
| | 9 | 416 | | } |
| | 2 | 417 | | catch (InvalidCastException) |
| | | 418 | | { |
| | 2 | 419 | | throw new ArgumentException($"Value {value} does not match expected {typeof(TValue)}"); |
| | | 420 | | } |
| | 9 | 421 | | } |
| | 2 | 422 | | catch (InvalidCastException) |
| | | 423 | | { |
| | 2 | 424 | | throw new ArgumentException($"Key {key} does not match expected {typeof(TKey)}"); |
| | | 425 | | } |
| | 9 | 426 | | } |
| | | 427 | | |
| | | 428 | | /// <summary> |
| | | 429 | | /// Inserts a key/value pair into the dictionary. If the key already exists and |
| | | 430 | | /// pair is added, or the method returns false if the key already exists. |
| | | 431 | | /// </summary> |
| | | 432 | | /// <param name="key">The key to insert or update.</param> |
| | | 433 | | /// <param name="value">The value to insert or update.</param> |
| | | 434 | | /// <returns> |
| | | 435 | | /// true if the key/value pair was added to the dictionary successfully; |
| | | 436 | | /// false if the key already exists. |
| | | 437 | | /// </returns> |
| | | 438 | | /// <exception cref="ArgumentNullException">Thrown when the key is null.</exception> |
| | | 439 | | internal virtual bool InsertIfNotExist(TKey key, TValue value) |
| | | 440 | | { |
| | 26811 | 441 | | ChronicleGuard.ThrowIfNullGeneric(key, nameof(key)); |
| | | 442 | | |
| | 26805 | 443 | | int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF; |
| | 26805 | 444 | | int entryIndex = hashCode & _entryMask; |
| | | 445 | | |
| | 26805 | 446 | | int firstDeletedIndex = -1; |
| | 26805 | 447 | | int step = 1; |
| | | 448 | | // Cumulative square offsets repeat after 2 * capacity for power-of-two tables. |
| | | 449 | | // One capacity can revisit buckets before reaching every slot, including after trim. |
| | 26805 | 450 | | uint probeLimit = (uint)_entries.Length * 2; |
| | 48217 | 451 | | while ((uint)step <= probeLimit) |
| | | 452 | | { |
| | 48216 | 453 | | ref Entry entry = ref _entries[entryIndex]; |
| | 48216 | 454 | | if (entry.IsUsed) |
| | | 455 | | { |
| | 20456 | 456 | | if (entry.HashCode == hashCode && _comparer.Equals(entry.Key, key)) |
| | 77 | 457 | | return false; // Item already exists |
| | | 458 | | } |
| | 27760 | 459 | | else if (entry.HashCode == -1) |
| | | 460 | | { |
| | 2065 | 461 | | if (firstDeletedIndex < 0) firstDeletedIndex = entryIndex; |
| | | 462 | | } |
| | | 463 | | else |
| | | 464 | | { |
| | | 465 | | break; |
| | | 466 | | } |
| | | 467 | | |
| | 21412 | 468 | | entryIndex = (entryIndex + step * step) & _entryMask; // Quadratic probing |
| | 21412 | 469 | | step++; |
| | | 470 | | } |
| | | 471 | | |
| | 26728 | 472 | | if (firstDeletedIndex >= 0) |
| | 1031 | 473 | | entryIndex = firstDeletedIndex; |
| | 25697 | 474 | | else if ((uint)step > probeLimit) |
| | | 475 | | { |
| | 1 | 476 | | Resize(_entries.Length * _adaptiveResizeFactor); |
| | 1 | 477 | | return InsertIfNotExist(key, value); |
| | | 478 | | } |
| | | 479 | | |
| | 44736 | 480 | | if ((uint)entryIndex > (uint)_lastIndex) _lastIndex = entryIndex; |
| | | 481 | | |
| | 26727 | 482 | | _entries[entryIndex].HashCode = hashCode; |
| | 26727 | 483 | | _entries[entryIndex].Key = key; |
| | 26727 | 484 | | _entries[entryIndex].Value = value; |
| | 26727 | 485 | | _entries[entryIndex].IsUsed = true; |
| | 26727 | 486 | | _count++; |
| | 26727 | 487 | | _version++; |
| | | 488 | | |
| | 26727 | 489 | | if ((uint)step > (uint)_maxStepCount) |
| | | 490 | | { |
| | 2025 | 491 | | _maxStepCount = step; |
| | 2025 | 492 | | if (_comparer is not IRandomedEqualityComparer && |
| | 2025 | 493 | | _maxStepCount > 100 && |
| | 2025 | 494 | | SwiftHashTools.IsWellKnownEqualityComparer(_comparer)) |
| | 1 | 495 | | SwitchToRandomizedComparer(); // Attempt to recompute hash code with potential randomization for better |
| | | 496 | | } |
| | | 497 | | |
| | | 498 | | |
| | 26727 | 499 | | return true; |
| | | 500 | | } |
| | | 501 | | |
| | | 502 | | /// <inheritdoc/> |
| | | 503 | | public virtual bool Remove(TKey key) |
| | | 504 | | { |
| | 8200 | 505 | | if (_KeyCanBeNull && key is null) return false; |
| | | 506 | | |
| | 8194 | 507 | | int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF; |
| | 8194 | 508 | | int entryIndex = hashCode & _entryMask; |
| | | 509 | | |
| | 8194 | 510 | | int step = 0; |
| | | 511 | | // A bucket index is not a probe distance: wrapped chains can take more steps. |
| | | 512 | | // Use the same complete cumulative-square period as insertion. |
| | 9667 | 513 | | while ((uint)step < (uint)_entries.Length * 2) |
| | | 514 | | { |
| | 9664 | 515 | | ref Entry entry = ref _entries[entryIndex]; |
| | | 516 | | // Stop probing if an unused entry is found (not deleted) |
| | 9664 | 517 | | if (!entry.IsUsed && entry.HashCode != -1) |
| | 1026 | 518 | | return false; |
| | 8638 | 519 | | if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Key, key)) |
| | | 520 | | { |
| | | 521 | | // Mark entry as deleted |
| | 7165 | 522 | | entry.IsUsed = false; |
| | 7165 | 523 | | entry.Key = default!; |
| | 7165 | 524 | | entry.Value = default!; |
| | 7165 | 525 | | entry.HashCode = -1; |
| | 7165 | 526 | | _count--; |
| | 8209 | 527 | | if ((uint)_count == 0) _lastIndex = 0; |
| | 7165 | 528 | | _version++; |
| | 7165 | 529 | | return true; |
| | | 530 | | } |
| | | 531 | | |
| | | 532 | | // Move to the next entry using linear probing |
| | 1473 | 533 | | step++; |
| | 1473 | 534 | | entryIndex = (entryIndex + step * step) & _entryMask; |
| | | 535 | | } |
| | 3 | 536 | | return false; // Item not found after full loop |
| | | 537 | | } |
| | | 538 | | |
| | | 539 | | void IDictionary.Remove(object obj) |
| | | 540 | | { |
| | 3 | 541 | | ChronicleGuard.ThrowIfNull(obj, nameof(obj)); |
| | 5 | 542 | | if (obj is TKey key) Remove(key); |
| | 3 | 543 | | } |
| | | 544 | | |
| | | 545 | | /// <inheritdoc/> |
| | | 546 | | public bool Remove(KeyValuePair<TKey, TValue> item) |
| | | 547 | | { |
| | 5 | 548 | | int index = FindEntry(item.Key); |
| | 5 | 549 | | if (index >= 0 && EqualityComparer<TValue>.Default.Equals(_entries[index].Value, item.Value)) |
| | | 550 | | { |
| | 1 | 551 | | Remove(item.Key); |
| | 1 | 552 | | return true; |
| | | 553 | | } |
| | 4 | 554 | | return false; |
| | | 555 | | } |
| | | 556 | | |
| | | 557 | | /// <inheritdoc/> |
| | | 558 | | public virtual void Clear() |
| | | 559 | | { |
| | 1626 | 560 | | if ((uint)_count == 0) return; |
| | | 561 | | |
| | 11240 | 562 | | for (uint i = 0; i <= (uint)_lastIndex; i++) |
| | | 563 | | { |
| | | 564 | | // Clear is a full reset, not a delete; future probes must be able to stop |
| | | 565 | | // at these now-empty slots instead of treating them as tombstones. |
| | 4286 | 566 | | _entries[i].HashCode = 0; |
| | 4286 | 567 | | _entries[i].Key = default!; |
| | 4286 | 568 | | _entries[i].Value = default!; |
| | 4286 | 569 | | _entries[i].IsUsed = false; |
| | | 570 | | } |
| | | 571 | | |
| | 1334 | 572 | | _count = 0; |
| | 1334 | 573 | | _lastIndex = 0; |
| | 1334 | 574 | | _maxStepCount = 0; |
| | 1334 | 575 | | _movingFillRate = 0; |
| | 1334 | 576 | | _adaptiveResizeFactor = 4; |
| | | 577 | | |
| | 1334 | 578 | | _version++; |
| | 1334 | 579 | | } |
| | | 580 | | |
| | | 581 | | /// <summary> |
| | | 582 | | /// Removes all elements, optionally releasing references throughout retained backing storage. |
| | | 583 | | /// </summary> |
| | | 584 | | /// <param name="clearRetainedReferences">If true, also releases references outside the live range; otherwise uses o |
| | | 585 | | /// <remarks>Capacity is preserved. Full reference cleanup can take time proportional to retained capacity.</remarks |
| | | 586 | | public void Clear(bool clearRetainedReferences) |
| | | 587 | | { |
| | 282 | 588 | | if (clearRetainedReferences && RuntimeHelpers.IsReferenceOrContainsReferences<Entry>()) |
| | | 589 | | { |
| | 270 | 590 | | int start = _count == 0 ? 0 : _lastIndex + 1; |
| | 270 | 591 | | Array.Clear(_entries, start, _entries.Length - start); |
| | | 592 | | } |
| | 282 | 593 | | Clear(); |
| | 282 | 594 | | } |
| | | 595 | | |
| | | 596 | | #endregion |
| | | 597 | | |
| | | 598 | | #region Capacity Management |
| | | 599 | | |
| | | 600 | | /// <summary> |
| | | 601 | | /// Ensures that the dictionary is resized when the current load factor exceeds the predefined threshold. |
| | | 602 | | /// </summary> |
| | | 603 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 604 | | protected void CheckLoadThreshold() |
| | | 605 | | { |
| | 26734 | 606 | | if ((uint)_count >= _nextResizeCount) |
| | 59 | 607 | | Resize(_entries.Length * _adaptiveResizeFactor); |
| | 26734 | 608 | | } |
| | | 609 | | |
| | | 610 | | /// <summary> |
| | | 611 | | /// Ensures that the dictionary can hold up to the specified number of entries, if not it resizes. |
| | | 612 | | /// </summary> |
| | | 613 | | /// <param name="capacity">The minimum capacity to ensure.</param> |
| | | 614 | | /// <returns>The new capacity of the dictionary.</returns> |
| | | 615 | | /// <exception cref="ArgumentOutOfRangeException">The capacity is less than zero.</exception> |
| | | 616 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 617 | | public void EnsureCapacity(int capacity) |
| | | 618 | | { |
| | 7 | 619 | | capacity = SwiftHashTools.NextPowerOfTwo(capacity); // Capacity must be a power of 2 for proper masking |
| | 7 | 620 | | if (capacity > _entries.Length) |
| | 4 | 621 | | Resize(capacity); |
| | 7 | 622 | | } |
| | | 623 | | |
| | | 624 | | /// <summary> |
| | | 625 | | /// Resizes the internal arrays to the specified new size. |
| | | 626 | | /// </summary> |
| | | 627 | | /// <param name="newSize">The new size for the internal arrays.</param> |
| | | 628 | | private void Resize(int newSize) |
| | | 629 | | { |
| | 64 | 630 | | Entry[] newEntries = new Entry[newSize]; |
| | 64 | 631 | | int newMask = newSize - 1; |
| | | 632 | | |
| | 64 | 633 | | int lastIndex = 0; |
| | 35412 | 634 | | for (uint i = 0; i <= (uint)_lastIndex; i++) |
| | | 635 | | { |
| | 17642 | 636 | | if (_entries[i].IsUsed) // Only rehash valid entries |
| | | 637 | | { |
| | 16621 | 638 | | ref Entry oldEntry = ref _entries[i]; |
| | 16621 | 639 | | int newIndex = oldEntry.HashCode & newMask; |
| | | 640 | | // If current entry not available, perform Quadratic probing to find the next available entry |
| | 16621 | 641 | | int step = 1; |
| | 17284 | 642 | | while (newEntries[newIndex].IsUsed) |
| | | 643 | | { |
| | 663 | 644 | | newIndex = (newIndex + step * step) & newMask; |
| | 663 | 645 | | step++; |
| | | 646 | | } |
| | 16621 | 647 | | newEntries[newIndex] = oldEntry; |
| | 28969 | 648 | | if (newIndex > lastIndex) lastIndex = newIndex; |
| | | 649 | | } |
| | | 650 | | } |
| | | 651 | | |
| | 64 | 652 | | _lastIndex = lastIndex; |
| | | 653 | | |
| | 64 | 654 | | CalculateAdaptiveResizeFactors(newSize); |
| | | 655 | | |
| | 64 | 656 | | _entries = newEntries; |
| | 64 | 657 | | _entryMask = newMask; |
| | | 658 | | |
| | 64 | 659 | | _version++; |
| | 64 | 660 | | } |
| | | 661 | | |
| | | 662 | | /// <summary> |
| | | 663 | | /// Sets the capacity of a <see cref="SwiftDictionary{TKey, TValue}"/> to the actual |
| | | 664 | | /// number of elements it contains, rounded up to a nearby next power of 2 value. |
| | | 665 | | /// </summary> |
| | | 666 | | public void TrimExcess() |
| | | 667 | | { |
| | 6 | 668 | | int newSize = _count <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(_count); |
| | 7 | 669 | | if (newSize >= _entries.Length) return; |
| | | 670 | | |
| | 5 | 671 | | Entry[] newEntries = new Entry[newSize]; |
| | 5 | 672 | | int newMask = newSize - 1; |
| | | 673 | | |
| | 5 | 674 | | int lastIndex = 0; |
| | 478 | 675 | | for (int i = 0; i <= (uint)_lastIndex; i++) |
| | | 676 | | { |
| | 234 | 677 | | if (_entries[i].IsUsed) |
| | | 678 | | { |
| | 71 | 679 | | ref Entry oldEntry = ref _entries[i]; |
| | 71 | 680 | | int newIndex = oldEntry.HashCode & newMask; |
| | | 681 | | // If current entry not available, perform quadratic probing to find the next available entry |
| | 71 | 682 | | int step = 1; |
| | 1015 | 683 | | while (newEntries[newIndex].IsUsed) |
| | | 684 | | { |
| | 944 | 685 | | newIndex = (newIndex + step * step) & newMask; |
| | 944 | 686 | | step++; |
| | | 687 | | } |
| | 71 | 688 | | newEntries[newIndex] = oldEntry; |
| | 97 | 689 | | if (newIndex > lastIndex) lastIndex = newIndex; |
| | | 690 | | } |
| | | 691 | | } |
| | | 692 | | |
| | 5 | 693 | | _lastIndex = lastIndex; |
| | | 694 | | |
| | 5 | 695 | | CalculateAdaptiveResizeFactors(newSize); |
| | | 696 | | |
| | 5 | 697 | | _entryMask = newMask; |
| | 5 | 698 | | _entries = newEntries; |
| | | 699 | | |
| | 5 | 700 | | _version++; |
| | 5 | 701 | | } |
| | | 702 | | |
| | | 703 | | /// <summary> |
| | | 704 | | /// Updates adaptive resize parameters based on the current fill rate to balance memory usage and performance. |
| | | 705 | | /// </summary> |
| | | 706 | | /// <param name="newSize"></param> |
| | | 707 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 708 | | private void CalculateAdaptiveResizeFactors(int newSize) |
| | | 709 | | { |
| | | 710 | | // Calculate current fill rate and update moving average |
| | 69 | 711 | | double currentFillRate = (double)_count / newSize; |
| | 69 | 712 | | _movingFillRate = _movingFillRate == 0 ? currentFillRate : (_movingFillRate * 0.7 + currentFillRate * 0.3); |
| | | 713 | | |
| | 69 | 714 | | if (_movingFillRate > 0.3f) |
| | 5 | 715 | | _adaptiveResizeFactor = 2; // Growth stabilizing |
| | 64 | 716 | | else if (_movingFillRate < 0.28f) |
| | 63 | 717 | | _adaptiveResizeFactor = 4; // Rapid growth |
| | | 718 | | |
| | | 719 | | // Reset the resize threshold based on the new size |
| | 69 | 720 | | _nextResizeCount = (uint)(newSize * _LoadFactorThreshold); |
| | 69 | 721 | | } |
| | | 722 | | |
| | | 723 | | #endregion |
| | | 724 | | |
| | | 725 | | #region Utility Methods |
| | | 726 | | |
| | | 727 | | /// <summary> |
| | | 728 | | /// Initializes the dictionary with the specified capacity. |
| | | 729 | | /// </summary> |
| | | 730 | | /// <param name="capacity">The initial number of elements that the dictionary can contain.</param> |
| | | 731 | | /// <param name="comparer">The comparer to use for the dictionary.</param> |
| | | 732 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 733 | | [MemberNotNull(nameof(_comparer))] |
| | | 734 | | private void Initialize(int capacity, IEqualityComparer<TKey>? comparer = null) |
| | | 735 | | { |
| | 447 | 736 | | _comparer = SwiftHashTools.GetDefaultEqualityComparer(comparer); |
| | | 737 | | |
| | 447 | 738 | | int size = capacity < DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity); |
| | 447 | 739 | | _entries = new Entry[size]; |
| | 447 | 740 | | _entryMask = size - 1; |
| | | 741 | | |
| | 447 | 742 | | _nextResizeCount = (uint)(size * _LoadFactorThreshold); |
| | 447 | 743 | | _adaptiveResizeFactor = 4; // start agressive |
| | 447 | 744 | | _movingFillRate = 0.0; |
| | 447 | 745 | | } |
| | | 746 | | |
| | | 747 | | /// <summary> |
| | | 748 | | /// Determines whether the dictionary contains an element with the specified key. |
| | | 749 | | /// </summary> |
| | | 750 | | /// <param name="key">The key to locate in the dictionary.</param> |
| | | 751 | | /// <returns>true if the dictionary contains an element with the specified key; otherwise, false.</returns> |
| | | 752 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 19589 | 753 | | public bool ContainsKey(TKey key) => FindEntry(key) >= 0; |
| | | 754 | | |
| | | 755 | | bool IDictionary.Contains(object obj) |
| | | 756 | | { |
| | 5 | 757 | | ChronicleGuard.ThrowIfNull(obj, nameof(obj)); |
| | | 758 | | |
| | 9 | 759 | | if (obj is TKey key) return ContainsKey(key); |
| | 1 | 760 | | return false; |
| | | 761 | | } |
| | | 762 | | |
| | | 763 | | /// <inheritdoc/> |
| | | 764 | | public bool Contains(KeyValuePair<TKey, TValue> item) |
| | | 765 | | { |
| | 4 | 766 | | int index = FindEntry(item.Key); |
| | 4 | 767 | | if (index >= 0 && EqualityComparer<TValue>.Default.Equals(_entries[index].Value, item.Value)) |
| | 1 | 768 | | return true; |
| | 3 | 769 | | return false; |
| | | 770 | | } |
| | | 771 | | |
| | | 772 | | /// <inheritdoc/> |
| | | 773 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 774 | | public bool TryGetValue(TKey key, out TValue value) |
| | | 775 | | { |
| | 9095 | 776 | | int index = FindEntry(key); |
| | 9095 | 777 | | if (index >= 0) |
| | | 778 | | { |
| | 7322 | 779 | | value = _entries[index].Value; |
| | 7322 | 780 | | return true; |
| | | 781 | | } |
| | 1773 | 782 | | value = default!; |
| | 1773 | 783 | | return false; |
| | | 784 | | } |
| | | 785 | | |
| | | 786 | | /// <summary> |
| | | 787 | | /// Copies the elements of the collection to the specified array, starting at the given array index. |
| | | 788 | | /// </summary> |
| | | 789 | | /// <param name="array"> |
| | | 790 | | /// The one-dimensional array of key/value pairs that is the destination of the elements copied from the collection. |
| | | 791 | | /// The array must have zero-based indexing. |
| | | 792 | | /// </param> |
| | | 793 | | /// <param name="arrayIndex">The zero-based index in the destination array at which copying begins.</param> |
| | | 794 | | /// <exception cref="ArgumentOutOfRangeException">Thrown if arrayIndex is less than 0 or greater than the length of |
| | | 795 | | /// <exception cref="ArgumentException"> |
| | | 796 | | /// Thrown if the number of elements in the source collection is greater than the available space from arrayIndex to |
| | | 797 | | /// the end of the destination array. |
| | | 798 | | /// </exception> |
| | | 799 | | public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) |
| | | 800 | | { |
| | 15 | 801 | | ChronicleGuard.ThrowIfNull(array, nameof(array)); |
| | 15 | 802 | | ChronicleGuard.ThrowIfArrayIndexInvalid(arrayIndex, array.Length); |
| | 15 | 803 | | ChronicleGuard.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "Insufficient space in the tar |
| | | 804 | | |
| | 250 | 805 | | for (uint i = 0; i <= (uint)_lastIndex; i++) |
| | | 806 | | { |
| | 110 | 807 | | if (_entries[i].IsUsed) |
| | 42 | 808 | | array[arrayIndex++] = new KeyValuePair<TKey, TValue>(_entries[i].Key, _entries[i].Value); |
| | | 809 | | } |
| | 15 | 810 | | } |
| | | 811 | | |
| | | 812 | | /// <inheritdoc/> |
| | | 813 | | public void CopyTo(Array array, int arrayIndex) |
| | | 814 | | { |
| | 10 | 815 | | ChronicleGuard.ThrowIfNull(array, nameof(array)); |
| | 10 | 816 | | ChronicleGuard.ThrowIfArgument(array.Rank != 1, nameof(array), "Multidimensional array not supported"); |
| | 9 | 817 | | ChronicleGuard.ThrowIfArgument(array.GetLowerBound(0) != 0, nameof(array), "Non-zero lower bound"); |
| | 8 | 818 | | ChronicleGuard.ThrowIfArrayIndexInvalid(arrayIndex, array.Length); |
| | 8 | 819 | | ChronicleGuard.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "Insufficient space in the tar |
| | | 820 | | |
| | 7 | 821 | | if (array is KeyValuePair<TKey, TValue>[] pairs) |
| | 1 | 822 | | ((ICollection<KeyValuePair<TKey, TValue>>)this).CopyTo(pairs, arrayIndex); |
| | 6 | 823 | | else if (array is DictionaryEntry[] dictEntryArray) |
| | 2 | 824 | | CopyToDictionaryEntries(dictEntryArray, arrayIndex); |
| | | 825 | | else |
| | 4 | 826 | | CopyToObjects(array, arrayIndex); |
| | 2 | 827 | | } |
| | | 828 | | |
| | | 829 | | private void CopyToDictionaryEntries(DictionaryEntry[] array, int arrayIndex) |
| | | 830 | | { |
| | 16 | 831 | | for (uint i = 0; i <= (uint)_lastIndex; i++) |
| | | 832 | | { |
| | 6 | 833 | | if (_entries[i].IsUsed) |
| | 4 | 834 | | array[arrayIndex++] = new DictionaryEntry(_entries[i].Key, _entries[i].Value); |
| | | 835 | | } |
| | 2 | 836 | | } |
| | | 837 | | |
| | | 838 | | private void CopyToObjects(Array array, int arrayIndex) |
| | | 839 | | { |
| | 4 | 840 | | if (array is not object[] objects) |
| | 1 | 841 | | throw new ArgumentException("Invalid array type", nameof(array)); |
| | | 842 | | |
| | | 843 | | try |
| | | 844 | | { |
| | 3 | 845 | | CopyToObjects(objects, arrayIndex); |
| | 2 | 846 | | } |
| | 1 | 847 | | catch (ArrayTypeMismatchException) |
| | | 848 | | { |
| | 1 | 849 | | throw new ArgumentException("Invalid array type", nameof(array)); |
| | | 850 | | } |
| | 2 | 851 | | } |
| | | 852 | | |
| | | 853 | | private void CopyToObjects(object[] array, int arrayIndex) |
| | | 854 | | { |
| | 20 | 855 | | for (uint i = 0; i <= (uint)_lastIndex; i++) |
| | | 856 | | { |
| | 8 | 857 | | if (_entries[i].IsUsed) |
| | 5 | 858 | | array[arrayIndex++] = new KeyValuePair<TKey, TValue>(_entries[i].Key, _entries[i].Value); |
| | | 859 | | } |
| | 2 | 860 | | } |
| | | 861 | | |
| | | 862 | | /// <summary> |
| | | 863 | | /// Sets a new comparer for the dictionary and rehashes the entries. |
| | | 864 | | /// </summary> |
| | | 865 | | /// <param name="comparer">The new comparer to use.</param> |
| | | 866 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 867 | | public void SetComparer(IEqualityComparer<TKey> comparer) |
| | | 868 | | { |
| | 5 | 869 | | ChronicleGuard.ThrowIfNull(comparer, nameof(comparer)); |
| | 5 | 870 | | if (ReferenceEquals(comparer, _comparer)) |
| | 1 | 871 | | return; |
| | | 872 | | |
| | 4 | 873 | | _comparer = comparer; |
| | 4 | 874 | | RehashEntries(); |
| | 4 | 875 | | _maxStepCount = 0; |
| | 4 | 876 | | } |
| | | 877 | | |
| | | 878 | | /// <summary> |
| | | 879 | | /// Switches the dictionary's comparer to a randomized comparer to mitigate the effects of high collision counts, |
| | | 880 | | /// and rehashes all entries using the new comparer to redistribute them across <see cref="_entries"/>. |
| | | 881 | | /// </summary> |
| | | 882 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 883 | | private void SwitchToRandomizedComparer() |
| | | 884 | | { |
| | 1 | 885 | | _comparer = (IEqualityComparer<TKey>)SwiftHashTools.GetSwiftEqualityComparer(_comparer); |
| | | 886 | | |
| | 1 | 887 | | RehashEntries(); |
| | 1 | 888 | | _maxStepCount = 0; |
| | | 889 | | |
| | 1 | 890 | | _version++; |
| | 1 | 891 | | } |
| | | 892 | | |
| | | 893 | | /// <summary> |
| | | 894 | | /// Reconstructs the internal entry structure to align with updated hash codes, ensuring efficient access and storag |
| | | 895 | | /// </summary> |
| | | 896 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 897 | | private void RehashEntries() |
| | | 898 | | { |
| | 5 | 899 | | Entry[] newEntries = new Entry[_entries.Length]; |
| | 5 | 900 | | int newMask = newEntries.Length - 1; |
| | | 901 | | |
| | 5 | 902 | | int lastIndex = 0; |
| | 612 | 903 | | for (uint i = 0; i <= (uint)_lastIndex; i++) |
| | | 904 | | { |
| | 301 | 905 | | if (_entries[i].IsUsed) |
| | | 906 | | { |
| | 109 | 907 | | ref Entry oldEntry = ref _entries[i]; |
| | 109 | 908 | | oldEntry.HashCode = _comparer.GetHashCode(oldEntry.Key) & 0x7FFFFFFF; |
| | 109 | 909 | | int newIndex = oldEntry.HashCode & newMask; |
| | 109 | 910 | | int step = 1; |
| | 128 | 911 | | while (newEntries[newIndex].IsUsed) |
| | | 912 | | { |
| | 19 | 913 | | newIndex = (newIndex + step * step) & newMask; // Quadratic probing |
| | 19 | 914 | | step++; |
| | | 915 | | } |
| | 109 | 916 | | newEntries[newIndex] = _entries[i]; |
| | 132 | 917 | | if (newIndex > lastIndex) lastIndex = newIndex; |
| | | 918 | | } |
| | | 919 | | } |
| | | 920 | | |
| | 5 | 921 | | _lastIndex = lastIndex; |
| | | 922 | | |
| | 5 | 923 | | _entryMask = newMask; |
| | 5 | 924 | | _entries = newEntries; |
| | | 925 | | |
| | 5 | 926 | | _version++; |
| | 5 | 927 | | } |
| | | 928 | | |
| | | 929 | | /// <summary> |
| | | 930 | | /// Finds the array index of the entry with the specified key. |
| | | 931 | | /// </summary> |
| | | 932 | | /// <param name="key">The key to locate in the dictionary.</param> |
| | | 933 | | /// <returns>The array index of the entry if found; otherwise, -1, including for a null key.</returns> |
| | | 934 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 935 | | protected int FindEntry(TKey key) |
| | | 936 | | { |
| | 44117 | 937 | | if (_KeyCanBeNull && key is null) return -1; |
| | | 938 | | |
| | 44091 | 939 | | int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF; |
| | 44091 | 940 | | int entryIndex = hashCode & _entryMask; |
| | | 941 | | |
| | 44091 | 942 | | int step = 0; |
| | | 943 | | // A bucket index is not a probe distance: wrapped chains can take more steps. |
| | | 944 | | // Use the same complete cumulative-square period as insertion. |
| | 58822 | 945 | | while ((uint)step < (uint)_entries.Length * 2) |
| | | 946 | | { |
| | 58819 | 947 | | ref Entry entry = ref _entries[entryIndex]; |
| | | 948 | | // Stop probing if an unused entry is found (not deleted) |
| | 58819 | 949 | | if (!entry.IsUsed && entry.HashCode != -1) |
| | 19699 | 950 | | return -1; |
| | 39120 | 951 | | if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Key, key)) |
| | 24389 | 952 | | return entryIndex; // Match found |
| | | 953 | | |
| | | 954 | | // Perform quadratic probing to see if maybe the entry was shifted. |
| | 14731 | 955 | | step++; |
| | 14731 | 956 | | entryIndex = (entryIndex + step * step) & _entryMask; |
| | | 957 | | } |
| | 3 | 958 | | return -1; // Item not found, full loop completed |
| | | 959 | | } |
| | | 960 | | |
| | | 961 | | #endregion |
| | | 962 | | |
| | | 963 | | #region IEnumerable Implementation |
| | | 964 | | |
| | | 965 | | /// <inheritdoc cref="IEnumerable.GetEnumerator()"/> |
| | 174 | 966 | | public SwiftDictionaryEnumerator GetEnumerator() => new(this); |
| | 107 | 967 | | IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator() => GetEnumerator(); |
| | 55 | 968 | | IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); |
| | 4 | 969 | | IDictionaryEnumerator IDictionary.GetEnumerator() => new SwiftDictionaryEnumerator(this, true); |
| | | 970 | | |
| | | 971 | | |
| | | 972 | | |
| | | 973 | | #endregion |
| | | 974 | | |
| | | 975 | | #region Key & Value Collections |
| | | 976 | | |
| | | 977 | | |
| | | 978 | | |
| | | 979 | | |
| | | 980 | | |
| | | 981 | | #endregion |
| | | 982 | | } |