Hm

QuickDictionaryTests.cs

using System.Collections.Generic;
using System.Runtime.CompilerServices;
using FluentAssertions;
using McUtilities.Memory;
using NUnit.Framework;

namespace McUtilitiesTest
{
    public class QuickDictionaryTests
    {
        private struct QDOpts: IQuickDictionaryOptions<ulong>
        {
            public static bool TombstoneKeyIsUsed()
            {
                return false;
            }

            public static ulong GetTombstoneKey()
            {
                return TombStoneKey;
            }
            
            public static bool AllocateCollisionMetadata()
            {
                return true;
            }

            public static bool UseFastModulo()
            {
                return true;
            }

            public static int KeyGetHashCode(ulong Key)
            {
                return Key.GetHashCode();
            }

            public static bool KeyEquals(ulong Left, ulong Right)
            {
                return Left == Right;
            }

            public static bool IsDebugMode()
            {
                return true;
            }
        }

        private const int MinEntrySize = 1024, MinTableSize = MinEntrySize * 2;

        private const ulong TombStoneKey = 0, EntryKey = 69, EntryVal = 1258;
        
        private QuickDictionary<ulong, ulong, QDOpts> Dict;

        [SetUp]
        public void Setup()
        {
            Dict = new QuickDictionary<ulong, ulong, QDOpts>(MinEntrySize, MinTableSize);
        }

        [Test]
        public void EnsureSufficientCapacity()
        {
            Dict.EntryCapacity.Should().BeGreaterThanOrEqualTo(MinEntrySize);
        }
        
        [Test]
        public void AddShouldWorkAndPreventDupeKeys()
        {
            ref var Slot = ref Dict.TryAdd(EntryKey, out var Exists);

            Slot.Key.Should().Be(EntryKey);

            Exists.Should().BeFalse();
            
            ref var Slot2 = ref Dict.TryAdd(EntryKey, out Exists);
            
            Slot2.Key.Should().Be(EntryKey);
            
            Exists.Should().BeTrue();
           
            Assert.True(Unsafe.AreSame(ref Slot, ref Slot2));
        }

        [Test]
        public void RemoveShouldWorkAndAllowSubsequentAddOfTheSameKey()
        {
            ref var Slot = ref Dict.TryAdd(EntryKey, out var Exists);
            
            Slot.Key.Should().Be(EntryKey);
            
            Exists.Should().BeFalse();

            Slot.Value = EntryVal;

            Dict.Count.Should().Be(1);
            
            Dict.TryRemove(EntryKey, out var RemovedVal).Should().BeTrue();

            RemovedVal.Should().Be(EntryVal);

            Dict.Count.Should().Be(0);

            //An entry shouldn't exist
            Assert.True(Unsafe.IsNullRef(ref Dict.TryGet(EntryKey)));

            Dict.TryAdd(EntryKey, out Exists).Key.Should().Be(EntryKey);
            
            Exists.Should().BeFalse();
            
            Dict.Count.Should().Be(1);
        }

        private ulong GetNextCollision(ulong Num)
        {
            var TC = (ulong) Dict.TableCapacity;

            var TSIndex = Num % TC;

            while ((++Num % TC) != TSIndex);

            return Num;
        }
        
        [Test]
        public void CollidingAddsShouldWork()
        {
            var CurrentKey = EntryKey;
            
            ref var HeaderEntrySlot = ref Dict.TryAdd(CurrentKey, out var Exists);

            HeaderEntrySlot.Key.Should().Be(CurrentKey);

            Exists.Should().BeFalse();

            HeaderEntrySlot.Value = CurrentKey;

            const int Entries = 69;

            //This is just so we could use the ref outside of the subsequent for loop
            ref var LastEntrySlot = ref HeaderEntrySlot;

            var ExpectedCollisionsList = new List<ulong>(Entries) { CurrentKey };

            for (int I = 1; I < Entries; I++)
            {
                CurrentKey = GetNextCollision(CurrentKey);

                ExpectedCollisionsList.Add(CurrentKey);
                
                LastEntrySlot = ref Dict.TryAdd(CurrentKey, out Exists);

                LastEntrySlot.Key.Should().Be(CurrentKey);
                
                Exists.Should().BeFalse();
                
                LastEntrySlot.Value = CurrentKey;
            }

            Dict.Count.Should().Be(Entries);

            /*var Table = Dict.TableMemory;

            var Entry = Dict.EntryMemory;*/
            
            var TSDebugger = Dict.GetTableSlotDebugger(EntryKey);

            foreach (var CurrentCollision in TSDebugger)
            {
                CurrentKey = CurrentCollision.Key;

                CurrentKey.Should().Be(CurrentCollision.Value);
                
                ExpectedCollisionsList.Should().Contain(CurrentKey);
            }
        }

        [Test]
        public void NonCollidingToCollidingTSTransitionShouldWork()
        {
            var FirstKey = EntryKey;

            var SecondKey = FirstKey + 1;

            var ThirdKey = GetNextCollision(FirstKey);

            ref var FirstSlot = ref Dict.TryAdd(FirstKey, out var Exists);

            Exists.Should().BeFalse();
            
            FirstSlot.Key.Should().Be(FirstKey);

            ref var SecondSlot = ref Dict.TryAdd(SecondKey, out Exists);
            
            Exists.Should().BeFalse();
            
            SecondSlot.Key.Should().Be(SecondKey);

            ref var ThirdSlot = ref Dict.TryAdd(ThirdKey, out Exists);

            Exists.Should().BeFalse();

            ThirdSlot.Key.Should().Be(ThirdKey);

            var EntryMemory = Dict.GetEntryMemoryUnsafe();
            
            EntryMemory[1].Key.Should().Be(SecondKey);

            EntryMemory[2].Key.Should().Be(FirstKey);

            EntryMemory[3].Key.Should().Be(ThirdKey);
        }
        
        [Test]
        public void TryGetShouldWork()
        {
            var Key = EntryKey;

            ref var Slot = ref Dict.TryAdd(Key, out var Exists);

            Slot.Key.Should().Be(Key);
            
            Exists.Should().BeFalse();

            ref var Slot2 = ref Dict.TryGet(Key);

            Unsafe.AreSame(ref Slot, ref Slot2).Should().BeTrue();
        }
        
        [Test]
        public void TryGetShouldWorkForCollidingAdds()
        {
            var CurrentKey = EntryKey;

            const int Entries = 69;

            var Collisions = new List<ulong>(Entries);

            for (int I = 1; I <= Entries; I++, CurrentKey = GetNextCollision(CurrentKey))
            {
                ref var CurrentSlot = ref Dict.TryAdd(CurrentKey, out var Exists);

                CurrentSlot.Key.Should().Be(CurrentKey);
            
                Exists.Should().BeFalse();

                CurrentSlot.Value = CurrentKey;
                
                Collisions.Add(CurrentKey);
            }
            
            Dict.Count.Should().Be(Entries);

            foreach (var Collision in Collisions)
            {
                Dict.TryGet(Collision).Value.Should().Be(Collision);
            }
        }
        
        [Test]
        public void TryRemoveShouldWork()
        {
            var Key = EntryKey;

            Dict.TryAdd(Key, out var Exists).Value = Key;

            Exists.Should().BeFalse();

            Dict.TryRemove(Key, out var Val).Should().BeTrue();

            Val.Should().Be(Key);
        }
        
        [Test]
        public void TryRemoveShouldWorkForCollidingAdds_LeftToRight()
        {
            var CurrentKey = EntryKey;

            const int Entries = 69;

            var Collisions = new List<ulong>(Entries);

            for (int I = 1; I <= Entries; I++, CurrentKey = GetNextCollision(CurrentKey))
            {
                ref var CurrentSlot = ref Dict.TryAdd(CurrentKey, out var Exists);

                CurrentSlot.Key.Should().Be(CurrentKey);
            
                Exists.Should().BeFalse();

                CurrentSlot.Value = CurrentKey;
                
                Collisions.Add(CurrentKey);
            }
            
            Dict.Count.Should().Be(Entries);

            foreach (var Collision in Collisions)
            {
                Dict.TryRemove(Collision, out var RemovedVal).Should().BeTrue();

                RemovedVal.Should().Be(Collision);
            }

            Dict.Count.Should().Be(0);
        }
        
        [Test]
        public void TryRemoveShouldWorkForCollidingAdds_RightToLeft()
        {
            var CurrentKey = EntryKey;

            const int Entries = 69;

            var Collisions = new Stack<ulong>(Entries);

            for (int I = 1; I <= Entries; I++, CurrentKey = GetNextCollision(CurrentKey))
            {
                ref var CurrentSlot = ref Dict.TryAdd(CurrentKey, out var Exists);

                CurrentSlot.Key.Should().Be(CurrentKey);
            
                Exists.Should().BeFalse();

                CurrentSlot.Value = CurrentKey;
                
                Collisions.Push(CurrentKey);
            }
            
            Dict.Count.Should().Be(Entries);

            foreach (var Collision in Collisions)
            {
                Dict.TryRemove(Collision, out var RemovedVal).Should().BeTrue();

                RemovedVal.Should().Be(Collision);
            }

            Dict.Count.Should().Be(0);
        }
        
        [Test]
        public void IteratorShouldWork()
        {
            var CurrentKey = EntryKey;

            const int Entries = 69;

            var Collisions = new List<ulong>(Entries);

            var I = 1;
            
            for (; I <= Entries; I++, CurrentKey = GetNextCollision(CurrentKey))
            {
                ref var CurrentSlot = ref Dict.TryAdd(CurrentKey, out var Exists);

                CurrentSlot.Key.Should().Be(CurrentKey);
            
                Exists.Should().BeFalse();

                CurrentSlot.Value = CurrentKey;
                
                Collisions.Add(CurrentKey);
            }
            
            Dict.Count.Should().Be(Entries);

            I = 0;

            foreach (ref var Entry in Dict)
            {
                Collisions[I++].Should().Be(Entry.Value);
            }
        }
    }
}