Try your search with a different keyword or use * as a wildcard.
using System.Collections.Concurrent;
using System.Diagnostics;
using FluentAssertions;
using Nop.Core.Infrastructure;
using NUnit.Framework;
namespace Nop.Tests.Nop.Core.Tests.Infrastructure;
[TestFixture]
public class ConcurrentTrieTests
{
private IConcurrentCollection<int> _sut;
private static void Profile(Action action)
{
var sw = new Stopwatch();
var memory = GC.GetTotalMemory(true) / 1024.0 / 1024.0;
sw.Start();
action.Invoke();
sw.Stop();
var delta = GC.GetTotalMemory(true) / 1024.0 / 1024.0 - memory;
Console.WriteLine("Elapsed time: {0:F} s", sw.ElapsedMilliseconds / 1000.0);
Console.WriteLine("Memory usage: {0:F} MB", delta);
}
[SetUp]
public void SetUp()
{
_sut = new ConcurrentTrie<int>();
}
[Test]
public void CanAddAndGetValue()
{
_sut.TryGetValue("a", out _).Should().BeFalse();
_sut.Add("a", 1);
_sut.TryGetValue("a", out var value).Should().BeTrue();
value.Should().Be(1);
_sut.Add("a", 2);
_sut.TryGetValue("a", out value).Should().BeTrue();
value.Should().Be(2);
}
[Test]
public void CanAddAndGetValues()
{
_sut.Add("a", 1);
_sut.TryGetValue("ab", out _).Should().BeFalse();
_sut.Add("abc", 3);
_sut.TryGetValue("ab", out _).Should().BeFalse();
_sut.TryGetValue("a", out var value).Should().BeTrue();
value.Should().Be(1);
_sut.TryGetValue("abc", out value).Should().BeTrue();
value.Should().Be(3);
_sut.Add("ab", 2);
_sut.TryGetValue("ab", out value).Should().BeTrue();
value.Should().Be(2);
}
[Test]
public void DoesNotBlockWhileEnumerating()
{
_sut.Add("a", 0);
_sut.Add("ab", 0);
foreach (var item in _sut.Keys)
_sut.Remove(item);
}
[Test]
public void CanRemoveValue()
{
_sut.Add("a", 1);
_sut.Add("b", 1);
_sut.Add("bbb", 1);
_sut.Add("ab", 1);
_sut.Add("aa", 1);
_sut.Add("abc", 1);
_sut.Add("abb", 1);
_sut.Remove("ab");
_sut.TryGetValue("ab", out _).Should().BeFalse();
_sut.Keys.Should().BeEquivalentTo(["abc", "a", "b", "aa", "abb", "bbb"]);
Assert.DoesNotThrow(() => _sut.Remove("ab"));
_sut.Remove("bb");
_sut.TryGetValue("b", out _).Should().BeTrue();
_sut.TryGetValue("bbb", out _).Should().BeTrue();
_sut.Prune("b", out _sut);
_sut.Keys.Should().BeEquivalentTo(["b", "bbb"]);
_sut.Remove("b");
_sut.Keys.Should().BeEquivalentTo(["bbb"]);
}
[Test]
public void CanGetKeys()
{
var keys = new[] { "a", "b", "abc" };
foreach (var key in keys)
_sut.Add(key, 1);
_sut.Keys.Should().BeEquivalentTo(keys);
}
[Test]
public void CanPrune()
{
_sut.Add("a", 1);
_sut.Add("b", 1);
_sut.Add("bba", 1);
_sut.Add("bbb", 1);
_sut.Add("ab", 1);
_sut.Add("abc", 1);
_sut.Add("abd", 1);
_sut.Prune("bc", out _).Should().BeFalse();
_sut.Prune("ab", out var subtree).Should().BeTrue();
subtree.Keys.Should().BeEquivalentTo(["ab", "abc", "abd"]);
_sut.Keys.Should().BeEquivalentTo(["a", "b", "bba", "bbb"]);
_sut.Prune("b", out subtree).Should().BeTrue();
subtree.Keys.Should().BeEquivalentTo(["b", "bba", "bbb"]);
_sut.Keys.Should().BeEquivalentTo(["a"]);
_sut = subtree;
_sut.Prune("bb", out subtree).Should().BeTrue();
subtree.Keys.Should().BeEquivalentTo(["bba", "bbb"]);
_sut.Keys.Should().BeEquivalentTo(["b"]);
_sut = subtree;
_sut.Prune("bba", out subtree);
subtree.Keys.Should().BeEquivalentTo(["bba"]);
_sut.Keys.Should().BeEquivalentTo(["bbb"]);
_sut = new ConcurrentTrie<int>();
_sut.Add("aaa", 1);
_sut.Prune("a", out subtree).Should().BeTrue();
subtree.Keys.Should().BeEquivalentTo(["aaa"]);
_sut.Keys.Should().BeEmpty();
_sut = subtree;
_sut.Prune("aa", out subtree).Should().BeTrue();
_sut.Keys.Should().BeEmpty();
subtree.Keys.Should().BeEquivalentTo(["aaa"]);
}
[Test]
public void CanSearch()
{
_sut.Add("a", 1);
_sut.Add("b", 1);
_sut.Add("abc", 1);
_sut.Add("abcd", 2);
var keys = _sut.Keys.ToList();
_sut.Search("ab").Should().BeEquivalentTo(new KeyValuePair<string, int>[]
{
new("abc", 1),
new("abcd", 2)
});
_sut.Keys.Should().BeEquivalentTo(keys);
}
[Test]
public void CanClear()
{
_sut.Add("a", 1);
_sut.Add("ab", 1);
_sut.Add("abc", 1);
_sut.Clear();
_sut.Keys.Should().BeEmpty();
}
[Test]
[TestCase(typeof(NopConcurrentCollection<byte>))]
[TestCase(typeof(ConcurrentTrie<byte>))]
[Ignore("Not a test, used for profiling.")]
public void Profile(Type oType)
{
var sut = Activator.CreateInstance(oType) as IConcurrentCollection<byte>;
sut.Should().NotBeNull();
Profile(() =>
{
for (var i = 0; i < 1000000; i++)
sut.Add(Guid.NewGuid().ToString(), 0);
});
}
[Test]
[TestCase(typeof(NopConcurrentCollection<int>))]
[TestCase(typeof(ConcurrentTrie<int>))]
[Ignore("Expensive concurrency test, enable manually.")]
public void DoesNotBreakDuringParallelAddRemove(Type oType)
{
var sut = Activator.CreateInstance(oType) as IConcurrentCollection<int>;
sut.Should().NotBeNull();
Profile(() =>
{
Parallel.For(0, 1000, new ParallelOptions { MaxDegreeOfParallelism = 8 }, j =>
{
for (var i = 0; i < 1000; i++)
{
var s = $"{i}-{j}";
sut.Add(s, i);
sut.TryGetValue(s, out var value).Should().BeTrue();
value.Should().Be(i);
sut.Remove(s);
sut.TryGetValue(s, out _).Should().BeFalse();
}
});
});
sut.Keys.Count().Should().Be(0);
}
[Test]
[TestCase(typeof(NopConcurrentCollection<int>))]
[TestCase(typeof(ConcurrentTrie<int>))]
[Ignore("Expensive concurrency test, enable manually.")]
public void DoesNotBreakDuringParallelAddPrune(Type oType)
{
var sut = Activator.CreateInstance(oType) as IConcurrentCollection<int>;
sut.Should().NotBeNull();
Profile(() =>
{
Parallel.For(0, 1000, new ParallelOptions { MaxDegreeOfParallelism = 8 }, j =>
{
for (var i = 0; i < 1000; i++)
{
var s = $"{j}-{i}";
sut.Add(s, i);
}
sut.Prune($"{j}-", out var st);
st.Keys.Count().Should().Be(1000);
});
});
sut.Keys.Count().Should().Be(0);
}
[Test]
[TestCase(typeof(NopConcurrentCollection<byte>))]
[TestCase(typeof(ConcurrentTrie<byte>))]
[Ignore("Not a test, used for profiling.")]
public void ProfilePrune(Type oType)
{
var sut = Activator.CreateInstance(oType) as IConcurrentCollection<byte>;
sut.Should().NotBeNull();
// insert
for (var i = 0; i < 10000; i++)
sut.Add(Guid.NewGuid().ToString(), 0);
Profile(() =>
{
Parallel.For(0, 1000, new ParallelOptions { MaxDegreeOfParallelism = 8 }, j =>
{
for (var i = 0; i < 20; i++)
{
// insert
sut.Add(Guid.NewGuid().ToString(), 0);
// remove by prefix
sut.Prune(Guid.NewGuid().ToString()[..5], out _);
}
});
});
}
#region Nested class
/// <summary>
/// A thread-safe collection based on <see cref="ConcurrentDictionary{TKey,TValue}"/>
/// </summary>
public partial class NopConcurrentCollection<TValue> : IConcurrentCollection<TValue>
{
#region Fields
protected readonly ConcurrentDictionary<string, TValue> _dictionary;
#endregion
#region Ctor
/// <summary>
/// Initializes a new instance of <see cref="NopConcurrentCollection{TValue}" />
/// </summary>
protected NopConcurrentCollection(IEnumerable<KeyValuePair<string, TValue>> subCollection)
{
_dictionary = new ConcurrentDictionary<string, TValue>(subCollection);
}
/// <summary>
/// Initializes a new empty instance of <see cref="NopConcurrentCollection{TValue}" />
/// </summary>
public NopConcurrentCollection()
{
_dictionary = new ConcurrentDictionary<string, TValue>();
}
#endregion
#region Methods
/// <summary>
/// Attempts to get the value associated with the specified key
/// </summary>
/// <param name="key">The key of the item to get (case-sensitive)</param>
/// <param name="value">The value associated with <paramref name="key"/>, if found</param>
/// <returns>
/// True if the key was found, otherwise false
/// </returns>
public bool TryGetValue(string key, out TValue value)
{
return _dictionary.TryGetValue(key, out value);
}
/// <summary>
/// Adds a key-value pair to the collection
/// </summary>
/// <param name="key">The key of the new item (case-sensitive)</param>
/// <param name="value">The value to be associated with <paramref name="key"/></param>
public void Add(string key, TValue value)
{
_dictionary[key] = value;
}
/// <summary>
/// Clears the collection
/// </summary>
public void Clear()
{
_dictionary.Clear();
}
/// <summary>
/// Gets all key-value pairs for keys starting with the given prefix
/// </summary>
/// <param name="prefix">The prefix (case-sensitive) to search for</param>
/// <returns>
/// All key-value pairs for keys starting with <paramref name="prefix"/>
/// </returns>
public IEnumerable<KeyValuePair<string, TValue>> Search(string prefix)
{
return _dictionary.Keys.Where(k => k.StartsWith(prefix))
.Select(key => new KeyValuePair<string, TValue>(key, _dictionary[key]));
}
/// <summary>
/// Removes the item with the given key, if present
/// </summary>
/// <param name="key">The key (case-sensitive) of the item to be removed</param>
public void Remove(string key)
{
_dictionary.Remove(key, out _);
}
/// <summary>
/// Attempts to remove all items with keys starting with the specified prefix
/// </summary>
/// <param name="prefix">The prefix (case-sensitive) of the items to be deleted</param>
/// <param name="subCollection">The sub-collection containing all deleted items, if found</param>
/// <returns>
/// True if the prefix was successfully removed from the collection, otherwise false
/// </returns>
public bool Prune(string prefix, out IConcurrentCollection<TValue> subCollection)
{
subCollection = new NopConcurrentCollection<TValue>(Search(prefix));
try
{
foreach (var key in subCollection.Keys)
Remove(key);
}
catch
{
return false;
}
return subCollection.Keys.Any();
}
#endregion
#region Properties
/// <summary>
/// Gets a collection that contains the keys in the <see cref="IConcurrentCollection{TValue}" />
/// </summary>
public IEnumerable<string> Keys => _dictionary.Keys;
#endregion
}
#endregion
}