Skip to content

Commit c0c39b1

Browse files
sharwellsharwell
committed
Use segmented arrays internally
1 parent 677b2be commit c0c39b1

1 file changed

Lines changed: 43 additions & 43 deletions

File tree

‎src/Dependencies/Collections/SegmentedHashSet`1.cs‎

Lines changed: 43 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -47,8 +47,8 @@ private const bool SupportsComparerDevirtualization
4747
private const int ShrinkThreshold = 3;
4848
private const int StartOfFreeList = -3;
4949

50-
private int[]? _buckets;
51-
private Entry[]? _entries;
50+
private SegmentedArray<int> _buckets;
51+
private SegmentedArray<Entry> _entries;
5252
private ulong _fastModMultiplier;
5353
private int _count;
5454
private int _freeList;
@@ -111,7 +111,7 @@ public SegmentedHashSet(IEnumerable<T> collection, IEqualityComparer<T>? compare
111111

112112
UnionWith(collection);
113113

114-
if (_count > 0 && _entries!.Length / _count > ShrinkThreshold)
114+
if (_count > 0 && _entries.Length / _count > ShrinkThreshold)
115115
{
116116
TrimExcess();
117117
}
@@ -142,13 +142,13 @@ private void ConstructFrom(SegmentedHashSet<T> source)
142142
return;
143143
}
144144

145-
var capacity = source._buckets!.Length;
145+
var capacity = source._buckets.Length;
146146
var threshold = HashHelpers.ExpandPrime(source.Count + 1);
147147

148148
if (threshold >= capacity)
149149
{
150-
_buckets = (int[])source._buckets.Clone();
151-
_entries = (Entry[])source._entries!.Clone();
150+
_buckets = (SegmentedArray<int>)source._buckets.Clone();
151+
_entries = (SegmentedArray<Entry>)source._entries.Clone();
152152
_freeList = source._freeList;
153153
_freeCount = source._freeCount;
154154
_count = source._count;
@@ -161,7 +161,7 @@ private void ConstructFrom(SegmentedHashSet<T> source)
161161
var entries = source._entries;
162162
for (var i = 0; i < source._count; i++)
163163
{
164-
ref var entry = ref entries![i];
164+
ref var entry = ref entries[i];
165165
if (entry._next >= -1)
166166
{
167167
AddIfNotPresent(entry._value, out _);
@@ -184,14 +184,14 @@ public void Clear()
184184
var count = _count;
185185
if (count > 0)
186186
{
187-
Debug.Assert(_buckets != null, "_buckets should be non-null");
188-
Debug.Assert(_entries != null, "_entries should be non-null");
187+
Debug.Assert(_buckets.Length > 0, "_buckets should be non-empty");
188+
Debug.Assert(_entries.Length > 0, "_entries should be non-empty");
189189

190-
Array.Clear(_buckets, 0, _buckets.Length);
190+
SegmentedArray.Clear(_buckets, 0, _buckets.Length);
191191
_count = 0;
192192
_freeList = -1;
193193
_freeCount = 0;
194-
Array.Clear(_entries, 0, count);
194+
SegmentedArray.Clear(_entries, 0, count);
195195
}
196196
}
197197

@@ -204,10 +204,10 @@ public void Clear()
204204
private int FindItemIndex(T item)
205205
{
206206
var buckets = _buckets;
207-
if (buckets != null)
207+
if (buckets.Length > 0)
208208
{
209209
var entries = _entries;
210-
Debug.Assert(entries != null, "Expected _entries to be initialized");
210+
Debug.Assert(entries.Length > 0, "Expected _entries to be initialized");
211211

212212
uint collisionCount = 0;
213213
var comparer = _comparer;
@@ -290,16 +290,16 @@ private int FindItemIndex(T item)
290290
[MethodImpl(MethodImplOptions.AggressiveInlining)]
291291
private ref int GetBucketRef(int hashCode)
292292
{
293-
var buckets = _buckets!;
294-
return ref buckets[HashHelpers.FastMod((uint)hashCode, (uint)buckets.Length, _fastModMultiplier)];
293+
var buckets = _buckets;
294+
return ref buckets[(int)HashHelpers.FastMod((uint)hashCode, (uint)buckets.Length, _fastModMultiplier)];
295295
}
296296

297297
public bool Remove(T item)
298298
{
299-
if (_buckets != null)
299+
if (_buckets.Length > 0)
300300
{
301301
var entries = _entries;
302-
Debug.Assert(entries != null, "entries should be non-null");
302+
Debug.Assert(entries.Length > 0, "entries should be non-empty");
303303

304304
uint collisionCount = 0;
305305
var last = -1;
@@ -390,12 +390,12 @@ public bool Remove(T item)
390390
/// </remarks>
391391
public bool TryGetValue(T equalValue, [MaybeNullWhen(false)] out T actualValue)
392392
{
393-
if (_buckets != null)
393+
if (_buckets.Length > 0)
394394
{
395395
var index = FindItemIndex(equalValue);
396396
if (index >= 0)
397397
{
398-
actualValue = _entries![index]._value;
398+
actualValue = _entries[index]._value;
399399
return true;
400400
}
401401
}
@@ -801,7 +801,7 @@ public void CopyTo(T[] array, int arrayIndex, int count)
801801
var entries = _entries;
802802
for (var i = 0; i < _count && count != 0; i++)
803803
{
804-
ref var entry = ref entries![i];
804+
ref var entry = ref entries[i];
805805
if (entry._next >= -1)
806806
{
807807
array[arrayIndex++] = entry._value;
@@ -822,7 +822,7 @@ public int RemoveWhere(Predicate<T> match)
822822
var numRemoved = 0;
823823
for (var i = 0; i < _count; i++)
824824
{
825-
ref var entry = ref entries![i];
825+
ref var entry = ref entries[i];
826826
if (entry._next >= -1)
827827
{
828828
// Cache value in case delegate removes it
@@ -858,13 +858,13 @@ public int EnsureCapacity(int capacity)
858858
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
859859
}
860860

861-
var currentCapacity = _entries == null ? 0 : _entries.Length;
861+
var currentCapacity = _entries.Length;
862862
if (currentCapacity >= capacity)
863863
{
864864
return currentCapacity;
865865
}
866866

867-
if (_buckets == null)
867+
if (_buckets.Length == 0)
868868
{
869869
return Initialize(capacity);
870870
}
@@ -878,16 +878,16 @@ public int EnsureCapacity(int capacity)
878878

879879
private void Resize(int newSize)
880880
{
881-
Debug.Assert(_entries != null, "_entries should be non-null");
881+
Debug.Assert(_entries.Length > 0, "_entries should be non-empty");
882882
Debug.Assert(newSize >= _entries.Length);
883883

884-
var entries = new Entry[newSize];
884+
var entries = new SegmentedArray<Entry>(newSize);
885885

886886
var count = _count;
887-
Array.Copy(_entries, entries, count);
887+
SegmentedArray.Copy(_entries, entries, count);
888888

889889
// Assign member variables after both arrays allocated to guard against corruption from OOM if second fails
890-
_buckets = new int[newSize];
890+
_buckets = new SegmentedArray<int>(newSize);
891891
_fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)newSize);
892892
for (var i = 0; i < count; i++)
893893
{
@@ -913,7 +913,7 @@ public void TrimExcess()
913913

914914
var newSize = HashHelpers.GetPrime(capacity);
915915
var oldEntries = _entries;
916-
var currentCapacity = oldEntries == null ? 0 : oldEntries.Length;
916+
var currentCapacity = oldEntries.Length;
917917
if (newSize >= currentCapacity)
918918
{
919919
return;
@@ -926,10 +926,10 @@ public void TrimExcess()
926926
var count = 0;
927927
for (var i = 0; i < oldCount; i++)
928928
{
929-
var hashCode = oldEntries![i]._hashCode; // At this point, we know we have entries.
929+
var hashCode = oldEntries[i]._hashCode; // At this point, we know we have entries.
930930
if (oldEntries[i]._next >= -1)
931931
{
932-
ref var entry = ref entries![count];
932+
ref var entry = ref entries[count];
933933
entry = oldEntries[i];
934934
ref var bucket = ref GetBucketRef(hashCode);
935935
entry._next = bucket - 1; // Value in _buckets is 1-based
@@ -956,8 +956,8 @@ public void TrimExcess()
956956
private int Initialize(int capacity)
957957
{
958958
var size = HashHelpers.GetPrime(capacity);
959-
var buckets = new int[size];
960-
var entries = new Entry[size];
959+
var buckets = new SegmentedArray<int>(size);
960+
var entries = new SegmentedArray<Entry>(size);
961961

962962
// Assign member variables after both arrays are allocated to guard against corruption from OOM if second fails.
963963
_freeList = -1;
@@ -974,14 +974,14 @@ private int Initialize(int capacity)
974974
/// <returns>true if the element is added to the <see cref="SegmentedHashSet{T}"/> object; false if the element is already present.</returns>
975975
private bool AddIfNotPresent(T value, out int location)
976976
{
977-
if (_buckets == null)
977+
if (_buckets.Length == 0)
978978
{
979979
Initialize(0);
980980
}
981-
Debug.Assert(_buckets != null);
981+
Debug.Assert(_buckets.Length > 0);
982982

983983
var entries = _entries;
984-
Debug.Assert(entries != null, "expected entries to be non-null");
984+
Debug.Assert(entries.Length > 0, "expected entries to be non-empty");
985985

986986
var comparer = _comparer;
987987
int hashCode;
@@ -1068,7 +1068,7 @@ private bool AddIfNotPresent(T value, out int location)
10681068
{
10691069
index = _freeList;
10701070
_freeCount--;
1071-
Debug.Assert((StartOfFreeList - entries![_freeList]._next) >= -1, "shouldn't overflow because `next` cannot underflow");
1071+
Debug.Assert((StartOfFreeList - entries[_freeList]._next) >= -1, "shouldn't overflow because `next` cannot underflow");
10721072
_freeList = StartOfFreeList - entries[_freeList]._next;
10731073
}
10741074
else
@@ -1085,7 +1085,7 @@ private bool AddIfNotPresent(T value, out int location)
10851085
}
10861086

10871087
{
1088-
ref var entry = ref entries![index];
1088+
ref var entry = ref entries[index];
10891089
entry._hashCode = hashCode;
10901090
entry._next = bucket - 1; // Value in _buckets is 1-based
10911091
entry._value = value;
@@ -1147,7 +1147,7 @@ private void IntersectWithHashSetWithSameComparer(SegmentedHashSet<T> other)
11471147
var entries = _entries;
11481148
for (var i = 0; i < _count; i++)
11491149
{
1150-
ref var entry = ref entries![i];
1150+
ref var entry = ref entries[i];
11511151
if (entry._next >= -1)
11521152
{
11531153
var item = entry._value;
@@ -1167,7 +1167,7 @@ private void IntersectWithHashSetWithSameComparer(SegmentedHashSet<T> other)
11671167
/// </summary>
11681168
private unsafe void IntersectWithEnumerable(IEnumerable<T> other)
11691169
{
1170-
Debug.Assert(_buckets != null, "_buckets shouldn't be null; callers should check first");
1170+
Debug.Assert(_buckets.Length > 0, "_buckets shouldn't be empty; callers should check first");
11711171

11721172
// Keep track of current last index; don't want to move past the end of our bit array
11731173
// (could happen if another thread is modifying the collection).
@@ -1193,7 +1193,7 @@ private unsafe void IntersectWithEnumerable(IEnumerable<T> other)
11931193
// FindFirstUnmarked method.
11941194
for (var i = 0; i < originalCount; i++)
11951195
{
1196-
ref var entry = ref _entries![i];
1196+
ref var entry = ref _entries[i];
11971197
if (entry._next >= -1 && !bitHelper.IsMarked(i))
11981198
{
11991199
Remove(entry._value);
@@ -1281,7 +1281,7 @@ private unsafe void SymmetricExceptWithEnumerable(IEnumerable<T> other)
12811281
{
12821282
if (itemsToRemove.IsMarked(i))
12831283
{
1284-
Remove(_entries![i]._value);
1284+
Remove(_entries[i]._value);
12851285
}
12861286
}
12871287
}
@@ -1324,7 +1324,7 @@ private unsafe (int UniqueCount, int UnfoundCount) CheckUniqueAndUnfoundElements
13241324
return (UniqueCount: 0, UnfoundCount: numElementsInOther);
13251325
}
13261326

1327-
Debug.Assert((_buckets != null) && (_count > 0), "_buckets was null but count greater than 0");
1327+
Debug.Assert((_buckets.Length > 0) && (_count > 0), "_buckets was empty but count greater than 0");
13281328

13291329
var originalCount = _count;
13301330
int intArrayLength = BitHelper.ToIntArrayLength(originalCount);
@@ -1409,7 +1409,7 @@ public bool MoveNext()
14091409
// dictionary.count+1 could be negative if dictionary.count is int.MaxValue
14101410
while ((uint)_index < (uint)_hashSet._count)
14111411
{
1412-
ref var entry = ref _hashSet._entries![_index++];
1412+
ref var entry = ref _hashSet._entries[_index++];
14131413
if (entry._next >= -1)
14141414
{
14151415
_current = entry._value;

0 commit comments

Comments
 (0)