This is an automated email from the ASF dual-hosted git repository. nightowl888 pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/lucenenet.git
commit e315e918275dd9760e12e953bc30da8f8c06689b Author: Shad Storhaug <[email protected]> AuthorDate: Thu Feb 6 20:10:55 2020 +0700 Lucene.Net.Facet, Lucene.Net.QueryParser: Factored out LurchTable in favor of J2N's implementation --- src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs | 16 +- .../Taxonomy/WriterCache/NameIntCacheLRU.cs | 31 +- .../Xml/Builders/CachedFilterBuilder.cs | 4 +- src/Lucene.Net.Tests/Support/TestLurchTable.cs | 994 ------------ .../Support/TestLurchTableThreading.cs | 278 ---- src/Lucene.Net/Support/LurchTable.cs | 1697 -------------------- 6 files changed, 16 insertions(+), 3004 deletions(-) diff --git a/src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs b/src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs index 3a673be..3db3a5b 100644 --- a/src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs +++ b/src/Lucene.Net.Facet/Taxonomy/LRUHashMap.cs @@ -1,4 +1,4 @@ -using Lucene.Net.Support; +using J2N.Collections.Concurrent; using System; using System.Collections; using System.Collections.Generic; @@ -40,7 +40,7 @@ namespace Lucene.Net.Facet.Taxonomy /// </summary> public class LRUHashMap<TKey, TValue> : IDictionary<TKey, TValue> { - private LurchTable<TKey, TValue> cache; + private readonly LurchTable<TKey, TValue> cache; /// <summary> /// Create a new hash map with a bounded size and with least recently @@ -117,7 +117,7 @@ namespace Lucene.Net.Facet.Taxonomy public TValue Put(TKey key, TValue value) { - TValue oldValue = default(TValue); + TValue oldValue = default; cache.AddOrUpdate(key, value, (k, v) => { oldValue = cache[key]; @@ -130,7 +130,7 @@ namespace Lucene.Net.Facet.Taxonomy { if (!cache.TryGetValue(key, out TValue result)) { - return default(TValue); + return default; } return result; } @@ -168,7 +168,7 @@ namespace Lucene.Net.Facet.Taxonomy public bool Contains(KeyValuePair<TKey, TValue> item) { - throw new NotSupportedException(); + return ((ICollection<KeyValuePair<TKey, TValue>>)cache).Contains(item); } public bool ContainsKey(TKey key) @@ -176,9 +176,9 @@ namespace Lucene.Net.Facet.Taxonomy return cache.ContainsKey(key); } - public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) + public void CopyTo(KeyValuePair<TKey, TValue>[] array, int index) { - throw new NotSupportedException(); + cache.CopyTo(array, index); } public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() @@ -188,7 +188,7 @@ namespace Lucene.Net.Facet.Taxonomy public bool Remove(KeyValuePair<TKey, TValue> item) { - throw new NotSupportedException(); + return cache.TryRemove(item); } public bool Remove(TKey key) diff --git a/src/Lucene.Net.Facet/Taxonomy/WriterCache/NameIntCacheLRU.cs b/src/Lucene.Net.Facet/Taxonomy/WriterCache/NameIntCacheLRU.cs index 2eedc5c..c089885 100644 --- a/src/Lucene.Net.Facet/Taxonomy/WriterCache/NameIntCacheLRU.cs +++ b/src/Lucene.Net.Facet/Taxonomy/WriterCache/NameIntCacheLRU.cs @@ -1,4 +1,4 @@ -using Lucene.Net.Support; +using J2N.Collections.Concurrent; using System.Collections.Generic; using System.Linq; @@ -38,7 +38,7 @@ namespace Lucene.Net.Facet.Taxonomy.WriterCache private IDictionary<object, int> cache; internal long nMisses = 0; // for debug internal long nHits = 0; // for debug - private int maxCacheSize; + private readonly int maxCacheSize; internal NameInt32CacheLRU(int limit) { @@ -49,24 +49,12 @@ namespace Lucene.Net.Facet.Taxonomy.WriterCache /// <summary> /// Maximum number of cache entries before eviction. /// </summary> - public virtual int Limit - { - get - { - return maxCacheSize; - } - } + public virtual int Limit => maxCacheSize; /// <summary> /// Number of entries currently in the cache. /// </summary> - public virtual int Count - { - get - { - return cache.Count; - } - } + public virtual int Count => cache.Count; private void CreateCache(int maxSize) { @@ -82,8 +70,7 @@ namespace Lucene.Net.Facet.Taxonomy.WriterCache internal virtual int Get(FacetLabel name) { - int result; - TryGetValue(name, out result); + TryGetValue(name, out int result); return result; } @@ -131,13 +118,7 @@ namespace Lucene.Net.Facet.Taxonomy.WriterCache return IsCacheFull; } - private bool IsCacheFull - { - get - { - return cache.Count > maxCacheSize; - } - } + private bool IsCacheFull => cache.Count > maxCacheSize; internal virtual void Clear() { diff --git a/src/Lucene.Net.QueryParser/Xml/Builders/CachedFilterBuilder.cs b/src/Lucene.Net.QueryParser/Xml/Builders/CachedFilterBuilder.cs index 7f573ea..63281b1 100644 --- a/src/Lucene.Net.QueryParser/Xml/Builders/CachedFilterBuilder.cs +++ b/src/Lucene.Net.QueryParser/Xml/Builders/CachedFilterBuilder.cs @@ -1,5 +1,5 @@ -using Lucene.Net.Search; -using Lucene.Net.Support; +using J2N.Collections.Concurrent; +using Lucene.Net.Search; using System.Xml; namespace Lucene.Net.QueryParsers.Xml.Builders diff --git a/src/Lucene.Net.Tests/Support/TestLurchTable.cs b/src/Lucene.Net.Tests/Support/TestLurchTable.cs deleted file mode 100644 index c2ba988..0000000 --- a/src/Lucene.Net.Tests/Support/TestLurchTable.cs +++ /dev/null @@ -1,994 +0,0 @@ -using Lucene.Net.Attributes; -using NUnit.Framework; -using System; -using System.Collections.Generic; - -namespace Lucene.Net.Support -{ - #region Copyright 2012-2014 by Roger Knapp, Licensed under the Apache License, Version 2.0 - /* Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - #endregion - - [TestFixture] - public class TestLurchTable : TestGenericCollection<TestLurchTable.LurchTableTest<int, string>, KeyValuePair<int, string>> - { - public class LurchTableTest<TKey, TValue> : LurchTable<TKey, TValue> - { - public LurchTableTest() : base(1024, LurchTableOrder.Access) - { } - public LurchTableTest(LurchTableOrder order) : base(1024, order) - { } - public LurchTableTest(IEqualityComparer<TKey> comparer) : base(1024, LurchTableOrder.Access, comparer) - { } - } - - protected override KeyValuePair<int, string>[] GetSample() - { - var results = new List<KeyValuePair<int, string>>(); - Random r = new Random(); - for (int i = 1; i < 100; i += r.Next(1, 3)) - results.Add(new KeyValuePair<int, string>(i, i.ToString())); - return results.ToArray(); - } - - class IntComparer : IEqualityComparer<int> - { - bool IEqualityComparer<int>.Equals(int x, int y) - { - return false; - } - - int IEqualityComparer<int>.GetHashCode(int obj) - { - return 0; - } - } - [Test, LuceneNetSpecific] - public void TestCTors() - { - var cmp = new IntComparer(); - const int limit = 5; - - Assert.AreEqual(LurchTableOrder.None, new LurchTable<int, int>(1).Ordering); - Assert.AreEqual(LurchTableOrder.Insertion, new LurchTable<int, int>(1, LurchTableOrder.Insertion).Ordering); - Assert.IsTrue(ReferenceEquals(cmp, new LurchTable<int, int>(1, LurchTableOrder.Insertion, cmp).Comparer)); - Assert.AreEqual(LurchTableOrder.Modified, new LurchTable<int, int>(LurchTableOrder.Modified, limit).Ordering); - Assert.AreEqual(limit, new LurchTable<int, int>(LurchTableOrder.Modified, limit).Limit); - Assert.AreEqual(LurchTableOrder.Access, new LurchTable<int, int>(LurchTableOrder.Access, limit, cmp).Ordering); - Assert.AreEqual(limit, new LurchTable<int, int>(LurchTableOrder.Access, limit, cmp).Limit); - Assert.IsTrue(ReferenceEquals(cmp, new LurchTable<int, int>(LurchTableOrder.Access, limit, cmp).Comparer)); - Assert.AreEqual(LurchTableOrder.Access, new LurchTable<int, int>(LurchTableOrder.Access, limit, 1, 1, 1, cmp).Ordering); - Assert.AreEqual(limit, new LurchTable<int, int>(LurchTableOrder.Access, limit, 1, 1, 1, cmp).Limit); - Assert.IsTrue(ReferenceEquals(cmp, new LurchTable<int, int>(LurchTableOrder.Access, limit, 1, 1, 1, cmp).Comparer)); - } - - [Test, LuceneNetSpecific] - public void TestDequeueByInsertion() - { - var test = new LurchTableTest<int, string>(LurchTableOrder.Insertion); - Assert.AreEqual(LurchTableOrder.Insertion, test.Ordering); - var sample = GetSample(); - Array.Reverse(sample); - foreach (var item in sample) - test.Add(item.Key, item.Value); - - KeyValuePair<int, string> value; - foreach (var item in sample) - { - Assert.IsTrue(test.Peek(out value)); - Assert.AreEqual(item.Key, value.Key); - Assert.AreEqual(item.Value, value.Value); - value = test.Dequeue(); - Assert.AreEqual(item.Key, value.Key); - Assert.AreEqual(item.Value, value.Value); - } - - Assert.IsFalse(test.Peek(out value)); - Assert.IsFalse(test.TryDequeue(out value)); - } - - [Test, LuceneNetSpecific] - public void TestDequeueByModified() - { - var test = new LurchTableTest<int, string>(LurchTableOrder.Modified); - Assert.AreEqual(LurchTableOrder.Modified, test.Ordering); - var sample = GetSample(); - foreach (var item in sample) - test.Add(item.Key, item.Value); - - Array.Reverse(sample); - for (int i = 0; i < sample.Length; i++) - { - var item = new KeyValuePair<int, string>(sample[i].Key, sample[i].Value + "-2"); - test[item.Key] = item.Value; - sample[i] = item; - } - - KeyValuePair<int, string> value; - foreach (var item in sample) - { - Assert.IsTrue(test.Peek(out value)); - Assert.AreEqual(item.Key, value.Key); - Assert.AreEqual(item.Value, value.Value); - value = test.Dequeue(); - Assert.AreEqual(item.Key, value.Key); - Assert.AreEqual(item.Value, value.Value); - } - - Assert.IsFalse(test.Peek(out value)); - Assert.IsFalse(test.TryDequeue(out value)); - } - - [Test, LuceneNetSpecific] - public void TestDequeueByAccess() - { - var test = new LurchTableTest<int, string>(LurchTableOrder.Access); - Assert.AreEqual(LurchTableOrder.Access, test.Ordering); - var sample = GetSample(); - foreach (var item in sample) - test.Add(item.Key, item.Value); - - Array.Reverse(sample); - foreach (var item in sample) - Assert.AreEqual(item.Value, test[item.Key]); - - KeyValuePair<int, string> value; - foreach (var item in sample) - { - Assert.IsTrue(test.TryDequeue(out value)); - Assert.AreEqual(item.Key, value.Key); - Assert.AreEqual(item.Value, value.Value); - } - - Assert.IsFalse(test.Peek(out value)); - Assert.IsFalse(test.TryDequeue(out value)); - } - - [Test, LuceneNetSpecific] - public void TestKeysEnumerator() - { - var sample = GetSample(); - var test = CreateSample(sample); - int ix = 0; - foreach (var key in test.Keys) - Assert.AreEqual(sample[ix++].Value, test[key]); - } - - [Test, LuceneNetSpecific] - public void TestValuesEnumerator() - { - var sample = GetSample(); - var test = CreateSample(sample); - int ix = 0; - foreach (var value in test.Values) - Assert.AreEqual(sample[ix++].Value, value); - } - - [Test, LuceneNetSpecific] - public void TestLimitorByAccess() - { - //multiple of prime will produce hash collision, thus testing removal of non-first elements - const int prime = 1103; - var test = new LurchTable<int, string>(LurchTableOrder.Access, 3, prime, 10, 10, EqualityComparer<int>.Default); - test[1 * prime] = "a"; - test[2 * prime] = "b"; - test[3 * prime] = "c"; - Assert.AreEqual(3, test.Count); - Assert.AreEqual("b", test[2 * prime]); //access moves to front.. - test[4] = "d"; - test[5] = "e"; - Assert.AreEqual(3, test.Count); // still 3 items - Assert.IsFalse(test.ContainsKey(1 * prime)); - Assert.IsTrue(test.ContainsKey(2 * prime)); //recently access is still there - Assert.IsFalse(test.ContainsKey(3 * prime)); - } - - class RecordEvents<TKey, TValue> - { - public KeyValuePair<TKey, TValue> LastAdded, LastUpdate, LastRemove; - - public void ItemAdded(KeyValuePair<TKey, TValue> obj) { LastAdded = obj; } - public void ItemUpdated(KeyValuePair<TKey, TValue> original, KeyValuePair<TKey, TValue> obj) { LastUpdate = obj; } - public void ItemRemoved(KeyValuePair<TKey, TValue> obj) { LastRemove = obj; } - } - - [Test, LuceneNetSpecific] - public void TestCrudEvents() - { - var recorder = new RecordEvents<int, string>(); - var test = new LurchTable<int, string>(LurchTableOrder.Access, 3, 1103, 10, 10, EqualityComparer<int>.Default); - test.ItemAdded += recorder.ItemAdded; - test.ItemUpdated += recorder.ItemUpdated; - test.ItemRemoved += recorder.ItemRemoved; - test[1] = "a"; - Assert.AreEqual("a", recorder.LastAdded.Value); - test[2] = "b"; - Assert.AreEqual("b", recorder.LastAdded.Value); - test[3] = "c"; - Assert.AreEqual("c", recorder.LastAdded.Value); - Assert.AreEqual(3, test.Count); - Assert.AreEqual("b", test[2]); //access moves to front.. - test[4] = "d"; - Assert.AreEqual("d", recorder.LastAdded.Value); - Assert.AreEqual("a", recorder.LastRemove.Value); - test[5] = "e"; - Assert.AreEqual("e", recorder.LastAdded.Value); - Assert.AreEqual("c", recorder.LastRemove.Value); - test[2] = "B"; - Assert.AreEqual("B", recorder.LastUpdate.Value); - test[6] = "f"; - Assert.AreEqual("f", recorder.LastAdded.Value); - Assert.AreEqual("d", recorder.LastRemove.Value); - - Assert.AreEqual(3, test.Count); // still 3 items - string value; - Assert.IsTrue(test.TryRemove(5, out value)); - Assert.AreEqual("e", value); - Assert.AreEqual("e", recorder.LastRemove.Value); - - Assert.AreEqual("B", test.Dequeue().Value); - Assert.AreEqual("f", test.Dequeue().Value); - Assert.AreEqual(0, test.Count); - } - - [Test, LuceneNetSpecific] - public void TestCollisionRemoval() - { - //multiple of prime will produce hash collision, thus testing removal of non-first elements - const int prime = 1103; - var test = new LurchTable<int, string>(LurchTableOrder.Access, 10, prime, 10, 10, EqualityComparer<int>.Default); - test[1 * prime] = "a"; - test[2 * prime] = "b"; - test[3 * prime] = "c"; - test[4 * prime] = "d"; - test[5 * prime] = "e"; - Assert.IsTrue(test.Remove(4 * prime)); - Assert.IsTrue(test.Remove(2 * prime)); - Assert.IsTrue(test.Remove(5 * prime)); - Assert.IsTrue(test.Remove(1 * prime)); - Assert.IsTrue(test.Remove(3 * prime)); - Assert.AreEqual(0, test.Count); - } - - [Test, LuceneNetSpecific] - public void TestAddRemoveByKey() - { - LurchTableTest<int, string> test = new LurchTableTest<int, string>(); - for (int i = 0; i < 10; i++) - test.Add(i, i.ToString()); - - for (int i = 0; i < 10; i++) - Assert.IsTrue(test.ContainsKey(i)); - - string cmp; - for (int i = 0; i < 10; i++) - Assert.IsTrue(test.TryGetValue(i, out cmp) && cmp == i.ToString()); - - for (int i = 0; i < 10; i++) - Assert.IsTrue(test.Remove(i)); - } - - [Test, LuceneNetSpecific] - public void TestComparer() - { - var test = new LurchTableTest<string, string>(StringComparer.OrdinalIgnoreCase); - test["a"] = "b"; - Assert.IsTrue(test.ContainsKey("A")); - - test = new LurchTableTest<string, string>(StringComparer.OrdinalIgnoreCase); - test["a"] = "b"; - Assert.IsTrue(test.ContainsKey("A")); - } - - [Test, LuceneNetSpecific] - public void TestKeys() - { - LurchTableTest<string, string> test = new LurchTableTest<string, string>(); - test["a"] = "b"; - string all = String.Join("", new List<string>(test.Keys).ToArray()); - Assert.AreEqual("a", all); - } - - [Test, LuceneNetSpecific] - public void TestValues() - { - LurchTableTest<string, string> test = new LurchTableTest<string, string>(); - test["a"] = "b"; - string all = String.Join("", new List<string>(test.Values).ToArray()); - Assert.AreEqual("b", all); - } - - [Test, LuceneNetSpecific] - public void TestAtomicAdd() - { - var data = new LurchTableTest<int, string>(); - int[] counter = new int[] { -1 }; - for (int i = 0; i < 100; i++) - Assert.IsTrue(data.TryAdd(i, (k) => (++counter[0]).ToString())); - Assert.AreEqual(100, data.Count); - Assert.AreEqual(100, counter[0] + 1); - - //Inserts of existing keys will not call method - Assert.IsFalse(data.TryAdd(50, (k) => { throw new InvalidOperationException(); })); - Assert.AreEqual(100, data.Count); - } - - [Test, LuceneNetSpecific] - public void TestAtomicAddOrUpdate() - { - var data = new LurchTableTest<int, string>(); - int[] counter = new int[] { -1 }; - - for (int i = 0; i < 100; i++) - data.AddOrUpdate(i, (k) => (++counter[0]).ToString(), (k, v) => { throw new InvalidOperationException(); }); - - for (int i = 0; i < 100; i++) - Assert.AreEqual((i & 1) == 1, data.TryRemove(i, (k, v) => (int.Parse(v) & 1) == 1)); - - for (int i = 0; i < 100; i++) - data.AddOrUpdate(i, (k) => (++counter[0]).ToString(), (k, v) => (++counter[0]).ToString()); - - Assert.AreEqual(100, data.Count); - Assert.AreEqual(200, counter[0] + 1); - - for (int i = 0; i < 100; i++) - Assert.IsTrue(data.TryRemove(i, (k, v) => int.Parse(v) - 100 == i)); - - Assert.AreEqual(0, data.Count); - } - - [Test, LuceneNetSpecific] - public void TestNewAddOrUpdate() - { - var data = new LurchTableTest<int, string>(); - Assert.AreEqual("a", data.AddOrUpdate(1, "a", (k, v) => k.ToString())); - Assert.AreEqual("1", data.AddOrUpdate(1, "a", (k, v) => k.ToString())); - - Assert.AreEqual("b", data.AddOrUpdate(2, k => "b", (k, v) => k.ToString())); - Assert.AreEqual("2", data.AddOrUpdate(2, k => "b", (k, v) => k.ToString())); - } - - struct AddUpdateValue : ICreateOrUpdateValue<int, string>, IRemoveValue<int, string> - { - public string OldValue; - public string Value; - public bool CreateValue(int key, out string value) - { - OldValue = null; - value = Value; - return Value != null; - } - public bool UpdateValue(int key, ref string value) - { - OldValue = value; - value = Value; - return Value != null; - } - public bool RemoveValue(int key, string value) - { - OldValue = value; - return value == Value; - } - } - - [Test, LuceneNetSpecific] - public void TestAtomicInterfaces() - { - var data = new LurchTableTest<int, string>(); - - data[1] = "a"; - - AddUpdateValue update = new AddUpdateValue(); - Assert.IsFalse(data.AddOrUpdate(1, ref update)); - Assert.AreEqual("a", update.OldValue); - Assert.IsFalse(data.AddOrUpdate(2, ref update)); - Assert.IsNull(update.OldValue); - Assert.IsFalse(data.TryRemove(1, ref update)); - Assert.AreEqual("a", update.OldValue); - - Assert.AreEqual(1, data.Count); - Assert.AreEqual("a", data[1]); - - update.Value = "b"; - Assert.IsTrue(data.AddOrUpdate(1, ref update)); - Assert.AreEqual("a", update.OldValue); - Assert.IsTrue(data.AddOrUpdate(2, ref update)); - Assert.IsNull(update.OldValue); - - Assert.AreEqual(2, data.Count); - Assert.AreEqual("b", data[1]); - Assert.AreEqual("b", data[2]); - - Assert.IsTrue(data.TryRemove(1, ref update)); - Assert.AreEqual("b", update.OldValue); - Assert.IsTrue(data.TryRemove(2, ref update)); - Assert.AreEqual("b", update.OldValue); - Assert.AreEqual(0, data.Count); - } - - [Test, LuceneNetSpecific] - public void TestGetOrAdd() - { - var data = new LurchTableTest<int, string>(); - Assert.AreEqual("a", data.GetOrAdd(1, "a")); - Assert.AreEqual("a", data.GetOrAdd(1, "b")); - - Assert.AreEqual("b", data.GetOrAdd(2, k => "b")); - Assert.AreEqual("b", data.GetOrAdd(2, k => "c")); - } - - - [Test, LuceneNetSpecific] - public void TestTryRoutines() - { - var data = new LurchTableTest<int, string>(); - - Assert.IsTrue(data.TryAdd(1, "a")); - Assert.IsFalse(data.TryAdd(1, "a")); - - Assert.IsTrue(data.TryUpdate(1, "a")); - Assert.IsTrue(data.TryUpdate(1, "c")); - Assert.IsTrue(data.TryUpdate(1, "d", "c")); - Assert.IsFalse(data.TryUpdate(1, "f", "c")); - Assert.AreEqual("d", data[1]); - Assert.IsTrue(data.TryUpdate(1, "a", data[1])); - Assert.AreEqual("a", data[1]); - Assert.IsFalse(data.TryUpdate(2, "b")); - - string val; - Assert.IsTrue(data.TryRemove(1, out val) && val == "a"); - Assert.IsFalse(data.TryRemove(2, out val)); - Assert.AreNotEqual(val, "a"); - - Assert.IsFalse(data.TryUpdate(1, (k, x) => x.ToUpper())); - data[1] = "a"; - data[1] = "b"; - Assert.IsTrue(data.TryUpdate(1, (k, x) => x.ToUpper())); - Assert.AreEqual("B", data[1]); - } - - [Test, LuceneNetSpecific] - public void TestInitialize() - { - LurchTableTest<string, string> test = new LurchTableTest<string, string>(StringComparer.Ordinal); - test["a"] = "b"; - Assert.AreEqual(1, test.Count); - test.Initialize(); - Assert.AreEqual(0, test.Count); - } - - [Test, LuceneNetSpecific] - public void TestSampleCollection() - { - var sample = GetSample(); - var items = CreateSample(sample); - IDictionary<int, string> dict = items; - VerifyCollection(new KeyValueEquality<int, string>(), new List<KeyValuePair<int, string>>(sample), items); - VerifyCollection(new KeyValueEquality<int, string>(), new List<KeyValuePair<int, string>>(sample), dict); - } - - [Test, LuceneNetSpecific] - public void TestSampleKeyCollection() - { - var sample = GetSample(); - var items = CreateSample(sample); - IDictionary<int, string> dict = items; - var keys = new List<int>(); - foreach (var kv in sample) - keys.Add(kv.Key); - VerifyCollection(EqualityComparer<int>.Default, keys.AsReadOnly(), items.Keys); - VerifyCollection(EqualityComparer<int>.Default, keys.AsReadOnly(), dict.Keys); - } - - [Test, LuceneNetSpecific] - public void TestSampleValueCollection() - { - var sample = GetSample(); - var items = CreateSample(sample); - IDictionary<int, string> dict = items; - var values = new List<string>(); - foreach (var kv in sample) - values.Add(kv.Value); - VerifyCollection(EqualityComparer<string>.Default, values.AsReadOnly(), items.Values); - VerifyCollection(EqualityComparer<string>.Default, values.AsReadOnly(), dict.Values); - } - - [Test] - public void TestDisposed() - { - IDictionary<int, string> test = new LurchTableTest<int, string>(); - var disposable = test as IDisposable; - if (disposable != null) - { - disposable.Dispose(); - } - Assert.Throws<ObjectDisposedException>(() => { test.Add(1, ""); }); - } - - class KeyValueEquality<TKey, TValue> : IEqualityComparer<KeyValuePair<TKey, TValue>> - { - IEqualityComparer<TKey> KeyComparer = EqualityComparer<TKey>.Default; - IEqualityComparer<TValue> ValueComparer = EqualityComparer<TValue>.Default; - public bool Equals(KeyValuePair<TKey, TValue> x, KeyValuePair<TKey, TValue> y) - { - return KeyComparer.Equals(x.Key, y.Key) && ValueComparer.Equals(x.Value, y.Value); - } - public int GetHashCode(KeyValuePair<TKey, TValue> obj) - { - return KeyComparer.GetHashCode(obj.Key) ^ ValueComparer.GetHashCode(obj.Value); - } - } - } - - [TestFixture] - public class TestLurchTableDictionary : TestDictionary<LurchTable<Guid, String>, TestLurchTableDictionary.Factory, Guid, String> - { - private const int SAMPLE_SIZE = 1000; - public new class Factory : IFactory<LurchTable<Guid, String>> - { - public LurchTable<Guid, string> Create() - { - return new LurchTable<Guid, string>(SAMPLE_SIZE, LurchTableOrder.Access); - } - } - - protected override KeyValuePair<Guid, string>[] GetSample() - { - var results = new List<KeyValuePair<Guid, string>>(); - for (int i = 0; i < SAMPLE_SIZE; i++) - { - Guid id = Guid.NewGuid(); - results.Add(new KeyValuePair<Guid, string>(id, id.ToString())); - } - return results.ToArray(); - } - } - - - #region Support - - #region Abstract classes - public abstract class TestGenericCollection<TList, TItem> - where TList : ICollection<TItem>, new() - { - protected abstract TItem[] GetSample(); - - protected TList CreateSample(TItem[] items) - { - TList list = new TList(); - - int count = 0; - Assert.AreEqual(count, list.Count); - - foreach (TItem item in items) - { - list.Add(item); - Assert.AreEqual(++count, list.Count); - } - return list; - } - - [Test, LuceneNetSpecific] - public virtual void TestAddRemove() - { - TList list = new TList(); - TItem[] items = GetSample(); - - int count = 0; - Assert.AreEqual(count, list.Count); - - foreach (TItem item in items) - { - list.Add(item); - Assert.AreEqual(++count, list.Count); - } - foreach (TItem item in items) - { - Assert.IsTrue(list.Remove(item)); - Assert.AreEqual(--count, list.Count); - } - } - - [Test, LuceneNetSpecific] - public virtual void TestAddReverseRemove() - { - TList list = new TList(); - TItem[] items = GetSample(); - - int count = 0; - Assert.AreEqual(count, list.Count); - - foreach (TItem item in items) - { - list.Add(item); - Assert.AreEqual(++count, list.Count); - } - for (int ix = items.Length - 1; ix >= 0; ix--) - { - Assert.IsTrue(list.Remove(items[ix])); - Assert.AreEqual(--count, list.Count); - } - } - - [Test, LuceneNetSpecific] - public virtual void TestClear() - { - TList list = new TList(); - TItem[] items = GetSample(); - - foreach (TItem item in items) - list.Add(item); - Assert.AreEqual(items.Length, list.Count); - - Assert.AreNotEqual(0, list.Count); - list.Clear(); - Assert.AreEqual(0, list.Count); - } - - [Test, LuceneNetSpecific] - public virtual void TestContains() - { - TList list = new TList(); - TItem[] items = GetSample(); - - foreach (TItem item in items) - list.Add(item); - Assert.AreEqual(items.Length, list.Count); - - foreach (TItem item in items) - Assert.IsTrue(list.Contains(item)); - } - - [Test, LuceneNetSpecific] - public virtual void TestCopyTo() - { - TList list = new TList(); - List<TItem> items = new List<TItem>(GetSample()); - - foreach (TItem item in items) - list.Add(item); - Assert.AreEqual(items.Count, list.Count); - - TItem[] copy = new TItem[items.Count + 1]; - list.CopyTo(copy, 1); - Assert.AreEqual(default(TItem), copy[0]); - - for (int i = 1; i < copy.Length; i++) - Assert.IsTrue(items.Remove(copy[i])); - - Assert.AreEqual(0, items.Count); - } - - [Test, LuceneNetSpecific] - public virtual void TestIsReadOnly() - { - Assert.IsFalse(new TList().IsReadOnly); - } - - [Test, LuceneNetSpecific] - public virtual void TestGetEnumerator() - { - TList list = new TList(); - List<TItem> items = new List<TItem>(GetSample()); - - foreach (TItem item in items) - list.Add(item); - Assert.AreEqual(items.Count, list.Count); - - foreach (TItem item in list) - Assert.IsTrue(items.Remove(item)); - - Assert.AreEqual(0, items.Count); - } - - [Test, LuceneNetSpecific] - public virtual void TestGetEnumerator2() - { - TList list = new TList(); - List<TItem> items = new List<TItem>(GetSample()); - - foreach (TItem item in items) - list.Add(item); - Assert.AreEqual(items.Count, list.Count); - - foreach (TItem item in ((System.Collections.IEnumerable)list)) - Assert.IsTrue(items.Remove(item)); - - Assert.AreEqual(0, items.Count); - } - - public static void VerifyCollection<T, TC>(IEqualityComparer<T> comparer, ICollection<T> expected, TC collection) where TC : ICollection<T> - { - Assert.AreEqual(expected.IsReadOnly, collection.IsReadOnly); - Assert.AreEqual(expected.Count, collection.Count); - CompareEnumerations(comparer, expected, collection); - using (var a = expected.GetEnumerator()) - using (var b = collection.GetEnumerator()) - { - bool result; - Assert.IsTrue(b.MoveNext()); - b.Reset(); - Assert.AreEqual(result = a.MoveNext(), b.MoveNext()); - while (result) - { - Assert.IsTrue(comparer.Equals(a.Current, b.Current)); - Assert.IsTrue(comparer.Equals(a.Current, (T)((System.Collections.IEnumerator)b).Current)); - Assert.AreEqual(result = a.MoveNext(), b.MoveNext()); - } - } - - T[] items = new T[10 + collection.Count]; - collection.CopyTo(items, 5); - Array.Copy(items, 5, items, 0, collection.Count); - Array.Resize(ref items, collection.Count); - CompareEnumerations(comparer, expected, collection); - - for (int i = 0; i < 5; i++) - Assert.IsTrue(collection.Contains(items[i])); - } - - public static void CompareEnumerations<T>(IEqualityComparer<T> comparer, IEnumerable<T> expected, IEnumerable<T> collection) - { - using (var a = expected.GetEnumerator()) - using (var b = collection.GetEnumerator()) - { - bool result; - Assert.AreEqual(result = a.MoveNext(), b.MoveNext()); - while (result) - { - Assert.IsTrue(comparer.Equals(a.Current, b.Current)); - Assert.AreEqual(result = a.MoveNext(), b.MoveNext()); - } - } - } - } - - public abstract class TestDictionary<TDictionary, TFactory, TKey, TValue> : TestCollection<TDictionary, TFactory, KeyValuePair<TKey, TValue>> - where TDictionary : IDictionary<TKey, TValue>, IDisposable - where TFactory : IFactory<TDictionary>, new() - { - [Test, LuceneNetSpecific] - public virtual void TestAddRemoveByKey() - { - KeyValuePair<TKey, TValue>[] sample = GetSample(); - - using (TDictionary test = Factory.Create()) - { - foreach (KeyValuePair<TKey, TValue> kv in sample) - test.Add(kv.Key, kv.Value); - - foreach (KeyValuePair<TKey, TValue> kv in sample) - Assert.IsTrue(test.ContainsKey(kv.Key)); - - TValue cmp; - foreach (KeyValuePair<TKey, TValue> kv in sample) - Assert.IsTrue(test.TryGetValue(kv.Key, out cmp) && kv.Value.Equals(cmp)); - - foreach (KeyValuePair<TKey, TValue> kv in sample) - Assert.IsTrue(test.Remove(kv.Key)); - } - } - - [Test, LuceneNetSpecific] - public virtual void TestKeys() - { - KeyValuePair<TKey, TValue>[] sample = GetSample(); - - using (TDictionary test = Factory.Create()) - { - List<TKey> keys = new List<TKey>(); - - foreach (KeyValuePair<TKey, TValue> kv in sample) - { - test[kv.Key] = kv.Value; - keys.Add(kv.Key); - } - - List<TKey> cmp = new List<TKey>(test.Keys); - - Assert.AreEqual(keys.Count, cmp.Count); - for (int i = 0; i < keys.Count; i++) - Assert.IsTrue(test.ContainsKey(keys[i])); - } - } - - [Test, LuceneNetSpecific] - public virtual void TestValues() - { - KeyValuePair<TKey, TValue>[] sample = GetSample(); - - using (TDictionary test = Factory.Create()) - { - List<TValue> values = new List<TValue>(); - - foreach (KeyValuePair<TKey, TValue> kv in sample) - { - test[kv.Key] = kv.Value; - values.Add(kv.Value); - } - - List<TValue> cmp = new List<TValue>(test.Values); - Assert.AreEqual(values.Count, cmp.Count); - } - } - } - - public abstract class TestCollection<TList, TFactory, TItem> - where TList : ICollection<TItem>, IDisposable - where TFactory : IFactory<TList>, new() - { - protected abstract TItem[] GetSample(); - - protected readonly TFactory Factory = new TFactory(); - - [Test, LuceneNetSpecific] - public virtual void TestAddRemove() - { - using (TList list = Factory.Create()) - { - TItem[] items = GetSample(); - - int count = 0; - Assert.AreEqual(count, list.Count); - - foreach (TItem item in items) - { - list.Add(item); - Assert.AreEqual(++count, list.Count); - } - foreach (TItem item in items) - { - Assert.IsTrue(list.Remove(item)); - Assert.AreEqual(--count, list.Count); - } - } - } - - [Test, LuceneNetSpecific] - public virtual void TestAddReverseRemove() - { - using (TList list = Factory.Create()) - { - TItem[] items = GetSample(); - - int count = 0; - Assert.AreEqual(count, list.Count); - - foreach (TItem item in items) - { - list.Add(item); - Assert.AreEqual(++count, list.Count); - } - for (int ix = items.Length - 1; ix >= 0; ix--) - { - Assert.IsTrue(list.Remove(items[ix])); - Assert.AreEqual(--count, list.Count); - } - } - } - - [Test, LuceneNetSpecific] - public virtual void TestClear() - { - using (TList list = Factory.Create()) - { - TItem[] items = GetSample(); - - foreach (TItem item in items) - list.Add(item); - Assert.AreEqual(items.Length, list.Count); - - Assert.AreNotEqual(0, list.Count); - list.Clear(); - Assert.AreEqual(0, list.Count); - } - } - - [Test, LuceneNetSpecific] - public virtual void TestContains() - { - using (TList list = Factory.Create()) - { - TItem[] items = GetSample(); - - foreach (TItem item in items) - list.Add(item); - Assert.AreEqual(items.Length, list.Count); - - foreach (TItem item in items) - Assert.IsTrue(list.Contains(item)); - } - } - - [Test, LuceneNetSpecific] - public virtual void TestCopyTo() - { - using (TList list = Factory.Create()) - { - List<TItem> items = new List<TItem>(GetSample()); - - foreach (TItem item in items) - list.Add(item); - Assert.AreEqual(items.Count, list.Count); - - TItem[] copy = new TItem[items.Count + 1]; - list.CopyTo(copy, 1); - Assert.AreEqual(default(TItem), copy[0]); - - for (int i = 1; i < copy.Length; i++) - Assert.IsTrue(items.Remove(copy[i])); - - Assert.AreEqual(0, items.Count); - } - } - - [Test, LuceneNetSpecific] - public virtual void TestIsReadOnly() - { - using (TList list = Factory.Create()) - Assert.IsFalse(list.IsReadOnly); - } - - [Test, LuceneNetSpecific] - public virtual void TestGetEnumerator() - { - using (TList list = Factory.Create()) - { - List<TItem> items = new List<TItem>(GetSample()); - - foreach (TItem item in items) - list.Add(item); - Assert.AreEqual(items.Count, list.Count); - - foreach (TItem item in list) - Assert.IsTrue(items.Remove(item)); - - Assert.AreEqual(0, items.Count); - } - } - - [Test, LuceneNetSpecific] - public virtual void TestGetEnumerator2() - { - using (TList list = Factory.Create()) - { - List<TItem> items = new List<TItem>(GetSample()); - - foreach (TItem item in items) - list.Add(item); - Assert.AreEqual(items.Count, list.Count); - - foreach (TItem item in ((System.Collections.IEnumerable)list)) - Assert.IsTrue(items.Remove(item)); - - Assert.AreEqual(0, items.Count); - } - } - } - - #endregion - - #region Interfaces - - /// <summary> Generic factory for instances of type T </summary> - public interface IFactory<T> - { - /// <summary> Creates an instance of an object assignable to type T </summary> - T Create(); - } - - #endregion - - #endregion -} diff --git a/src/Lucene.Net.Tests/Support/TestLurchTableThreading.cs b/src/Lucene.Net.Tests/Support/TestLurchTableThreading.cs deleted file mode 100644 index 0e08523..0000000 --- a/src/Lucene.Net.Tests/Support/TestLurchTableThreading.cs +++ /dev/null @@ -1,278 +0,0 @@ -/* - * - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - * -*/ - -using Lucene.Net.Attributes; -using NUnit.Framework; -using System; -using System.Collections.Concurrent; -using System.Collections.Generic; -using System.Diagnostics; -using System.Threading; - -namespace Lucene.Net.Support -{ - [TestFixture] - public class TestLurchTableThreading - { - private const int MAXTHREADS = 8; - private const int COUNT = 1000; - static LurchTable<Guid, T> CreateMap<T>() - { - var ht = new LurchTable<Guid, T>(COUNT, LurchTableOrder.Access); - return ht; - } - - private static void Parallel<T>(int loopCount, T[] args, Action<T> task) - { - var timer = Stopwatch.StartNew(); - int[] ready = new[] { 0 }; - ManualResetEvent start = new ManualResetEvent(false); - int nthreads = Math.Min(MAXTHREADS, args.Length); - var threads = new Thread[nthreads]; - for (int i = 0; i < threads.Length; i++) - { - threads[i] = new Thread((ithread) => - { - Interlocked.Increment(ref ready[0]); - start.WaitOne(); - for (int loop = 0; loop < loopCount; loop++) - for (int ix = (int)ithread; ix < args.Length; ix += nthreads) - task(args[ix]); - }); - } - - int threadIx = 0; - foreach (var t in threads) - t.Start(threadIx++); - - while (Interlocked.CompareExchange(ref ready[0], 0, 0) < nthreads) - Thread.Sleep(0); - - start.Set(); - - foreach (var t in threads) - t.Join(); - - Trace.TraceInformation("Execution time: {0}", timer.Elapsed); - } - - // LUCENENET TODO: For some reason, this logic depends on the underlying - // implementation of Guid.NewGuid(), which has changed in .NET Core 2.0. - // But the functionality of LurchTable seems unaffected by this change. -#if !NETCOREAPP - [Test, LuceneNetSpecific] - public void TestGuidHashCollision() - { - Guid id1 = Guid.NewGuid(); - Guid id2 = NextHashCollision(id1); - - Assert.AreNotEqual(id1, id2); - Assert.AreEqual(id1.GetHashCode(), id2.GetHashCode()); - } -#endif - - [Test, LuceneNetSpecific] - public void TestLimitedInsert() - { - var Map = new LurchTable<Guid, bool>(LurchTableOrder.Access, 1000); - var ids = CreateSample(Guid.NewGuid(), 1000000, 0); - - Parallel(1, ids, - id => - { - bool test; - Assert.IsTrue(Map.TryAdd(id, true)); - Map.TryGetValue(id, out test); - }); - - Assert.AreEqual(1000, Map.Count); - } - - [Test, LuceneNetSpecific] - public void TestInsert() - { - var Map = CreateMap<bool>(); - var ids = CreateSample(Guid.NewGuid(), COUNT, 4); - - bool test; - Parallel(1, ids, id => { Assert.IsTrue(Map.TryAdd(id, true)); }); - - Assert.AreEqual(ids.Length, Map.Count); - foreach (var id in ids) - Assert.IsTrue(Map.TryGetValue(id, out test) && test); - } - - [Test, LuceneNetSpecific] - public void TestDelete() - { - var Map = CreateMap<bool>(); - var ids = CreateSample(Guid.NewGuid(), COUNT, 4); - foreach (var id in ids) - Assert.IsTrue(Map.TryAdd(id, true)); - - bool test; - Parallel(1, ids, id => { Assert.IsTrue(Map.Remove(id)); }); - - Assert.AreEqual(0, Map.Count); - foreach (var id in ids) - Assert.IsTrue(!Map.TryGetValue(id, out test)); - } - - [Test, LuceneNetSpecific] - public void TestInsertDelete() - { - var Map = CreateMap<bool>(); - var ids = CreateSample(Guid.NewGuid(), COUNT, 4); - - bool test; - Parallel(100, ids, id => { Assert.IsTrue(Map.TryAdd(id, true)); Assert.IsTrue(Map.Remove(id)); }); - - Assert.AreEqual(0, Map.Count); - foreach (var id in ids) - Assert.IsTrue(!Map.TryGetValue(id, out test)); - } - - [Test, LuceneNetSpecific] - public void TestInsertUpdateDelete() - { - var Map = CreateMap<bool>(); - var ids = CreateSample(Guid.NewGuid(), COUNT, 4); - - bool test; - Parallel(100, ids, id => { Assert.IsTrue(Map.TryAdd(id, true)); Assert.IsTrue(Map.TryUpdate(id, false, true)); Assert.IsTrue(Map.Remove(id)); }); - - Assert.AreEqual(0, Map.Count); - foreach (var id in ids) - Assert.IsTrue(!Map.TryGetValue(id, out test)); - } - - [Test, LongRunningTest, LuceneNetSpecific] - public void CompareTest() - { - const int size = 1000000; - int reps = 3; - Stopwatch timer; - - IDictionary<Guid, TestValue> dict = new ConcurrentDictionary<Guid, TestValue>(new Dictionary<Guid, TestValue>(size)); - IDictionary<Guid, TestValue> test = new LurchTable<Guid, TestValue>(size); - - for (int rep = 0; rep < reps; rep++) - { - var sample = CreateSample(Guid.NewGuid(), size, 1); - - timer = Stopwatch.StartNew(); - Parallel(1, sample, item => dict.Add(item, new TestValue { Id = item, Count = rep })); - Trace.TraceInformation("Dict Add: {0}", timer.Elapsed); - - timer = Stopwatch.StartNew(); - Parallel(1, sample, item => test.Add(item, new TestValue { Id = item, Count = rep })); - Trace.TraceInformation("Test Add: {0}", timer.Elapsed); - - timer = Stopwatch.StartNew(); - Parallel(1, sample, item => dict[item] = new TestValue { Id = item, Count = rep }); - Trace.TraceInformation("Dict Update: {0}", timer.Elapsed); - - timer = Stopwatch.StartNew(); - Parallel(1, sample, item => test[item] = new TestValue { Id = item, Count = rep }); - Trace.TraceInformation("Test Update: {0}", timer.Elapsed); - - timer = Stopwatch.StartNew(); - Parallel(1, sample, item => dict.Remove(item)); - Trace.TraceInformation("Dict Rem: {0}", timer.Elapsed); - Assert.AreEqual(0, dict.Count); - - timer = Stopwatch.StartNew(); - Parallel(1, sample, item => test.Remove(item)); - Trace.TraceInformation("Test Rem: {0}", timer.Elapsed); - - test.Clear(); - dict.Clear(); - - GC.Collect(); - GC.WaitForPendingFinalizers(); - } - } - - struct TestValue - { - public Guid Id; - public int Count; - }; - -#region Guid Hash Collision Generator - - private static Random random = new Random(); - private static int iCounter = 0x01010101; - - public static Guid NextHashCollision(Guid guid) - { - var bytes = guid.ToByteArray(); - - // Modify bytes 8 & 9 with random number - Array.Copy( - BitConverter.GetBytes((short)random.Next()), - 0, - bytes, - 8, - 2 - ); - - // Increment bytes 11, 12, 13, & 14 - Array.Copy( - BitConverter.GetBytes( - BitConverter.ToInt32(bytes, 11) + - Interlocked.Increment(ref iCounter) - ), - 0, - bytes, - 11, - 4 - ); - - Guid result = new Guid(bytes); -#if !NETCOREAPP - Assert.AreEqual(guid.GetHashCode(), result.GetHashCode()); -#endif - return result; - } - - public static Guid[] CreateSample(Guid seed, int size, double collisions) - { - var sample = new Guid[size]; - int count = 0, collis = 0, uix = 0; - for (int i = 0; i < size; i++) - { - if (collis >= count * collisions) - { - sample[uix = i] = Guid.NewGuid(); - count++; - } - else - { - sample[i] = NextHashCollision(sample[uix]); - collis++; - } - } - return sample; - } -#endregion - } -} diff --git a/src/Lucene.Net/Support/LurchTable.cs b/src/Lucene.Net/Support/LurchTable.cs deleted file mode 100644 index cb496d4..0000000 --- a/src/Lucene.Net/Support/LurchTable.cs +++ /dev/null @@ -1,1697 +0,0 @@ -#region Copyright 2012-2014 by Roger Knapp, Licensed under the Apache License, Version 2.0 -/* Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - - // 2016-10-03: Modified from the original version by Shad Storhaug to - // allow read-write access to the Limit property -#endregion -using System; -using System.Collections; -using System.Collections.Generic; -using System.Threading; - -namespace Lucene.Net.Support -{ - /// <summary> - /// Defines if and how items added to a LurchTable are linked together, this defines - /// the value returned from Peek/Dequeue as the oldest entry of the specified operation. - /// </summary> - public enum LurchTableOrder - { - /// <summary> No linking </summary> - None, - /// <summary> Linked in insertion order </summary> - Insertion, - /// <summary> Linked by most recently inserted or updated </summary> - Modified, - /// <summary> Linked by most recently inserted, updated, or fetched </summary> - Access, - } - - /// <summary> - /// LurchTable stands for "Least Used Recently Concurrent Hash Table" and has definate - /// similarities to both the .NET 4 ConcurrentDictionary as well as Java's LinkedHashMap. - /// This gives you a thread-safe dictionary/hashtable that stores element ordering by - /// insertion, updates, or access. In addition it can be configured to use a 'hard-limit' - /// count of items that will automatically 'pop' the oldest item in the collection. - /// </summary> - /// <typeparam name="TKey">The type of keys in the dictionary.</typeparam> - /// <typeparam name="TValue">The type of values in the dictionary.</typeparam> - public class LurchTable<TKey, TValue> : IDictionary<TKey, TValue>, IDisposable - { - /// <summary> Method signature for the ItemUpdated event </summary> - public delegate void ItemUpdatedMethod(KeyValuePair<TKey, TValue> previous, KeyValuePair<TKey, TValue> next); - - /// <summary> Event raised after an item is removed from the collection </summary> - public event Action<KeyValuePair<TKey, TValue>> ItemRemoved; - /// <summary> Event raised after an item is updated in the collection </summary> - public event ItemUpdatedMethod ItemUpdated; - /// <summary> Event raised after an item is added to the collection </summary> - public event Action<KeyValuePair<TKey, TValue>> ItemAdded; - - private const int OverAlloc = 128; - private const int FreeSlots = 32; - - private readonly IEqualityComparer<TKey> _comparer; - private readonly int _hsize, _lsize; - private int _limit; // LUCENENET: Changed to read-write - private readonly int _allocSize, _shift, _shiftMask; - private readonly LurchTableOrder _ordering; - private readonly object[] _locks; - private readonly int[] _buckets; - private readonly FreeList[] _free; - - private Entry[][] _entries; - private int _used, _count; - private int _allocNext, _freeVersion; - - - - /// <summary>Creates a LurchTable that can store up to <paramref name="capacity"/> items efficiently.</summary> - /// <param name="capacity">The initial allowable number of items before allocation of more memory</param> - public LurchTable(int capacity) - : this(LurchTableOrder.None, int.MaxValue, capacity >> 1, capacity >> 4, capacity >> 8, null) { } - - /// <summary>Creates a LurchTable that can store up to <paramref name="capacity"/> items efficiently.</summary> - /// <param name="capacity">The initial allowable number of items before allocation of more memory</param> - /// <param name="ordering">The type of linking for the items</param> - public LurchTable(int capacity, LurchTableOrder ordering) - : this(ordering, int.MaxValue, capacity >> 1, capacity >> 4, capacity >> 8, null) { } - - /// <summary>Creates a LurchTable that can store up to <paramref name="capacity"/> items efficiently.</summary> - /// <param name="capacity">The initial allowable number of items before allocation of more memory</param> - /// <param name="ordering">The type of linking for the items</param> - /// <param name="comparer">The element hash generator for keys, or <c>null</c> to use <see cref="EqualityComparer{TKey}.Default"/></param> - public LurchTable(int capacity, LurchTableOrder ordering, IEqualityComparer<TKey> comparer) - : this(ordering, int.MaxValue, capacity >> 1, capacity >> 4, capacity >> 8, comparer) { } - - /// <summary>Creates a LurchTable that orders items by <paramref name="ordering"/> and removes items once the specified <paramref name="limit"/> is reached.</summary> - /// <param name="ordering">The type of linking for the items</param> - /// <param name="limit">The maximum allowable number of items, or int.MaxValue for unlimited</param> - public LurchTable(LurchTableOrder ordering, int limit) - : this(ordering, limit, limit >> 1, limit >> 4, limit >> 8, null) { } - - /// <summary>Creates a LurchTable that orders items by <paramref name="ordering"/> and removes items once the specified <paramref name="limit"/> is reached.</summary> - /// <param name="ordering">The type of linking for the items</param> - /// <param name="limit">The maximum allowable number of items, or int.MaxValue for unlimited</param> - /// <param name="comparer">The element hash generator for keys, or <c>null</c> to use <see cref="EqualityComparer{TKey}.Default"/></param> - public LurchTable(LurchTableOrder ordering, int limit, IEqualityComparer<TKey> comparer) - : this(ordering, limit, limit >> 1, limit >> 4, limit >> 8, comparer) { } - - /// <summary> - /// Creates a LurchTable that orders items by <paramref name="ordering"/> and removes items once the specified <paramref name="limit"/> is reached. - /// </summary> - /// <param name="ordering">The type of linking for the items</param> - /// <param name="limit">The maximum allowable number of items, or int.MaxValue for unlimited</param> - /// <param name="hashSize">The number of hash buckets to use for the collection, usually 1/2 estimated capacity</param> - /// <param name="allocSize">The number of entries to allocate at a time, usually 1/16 estimated capacity</param> - /// <param name="lockSize">The number of concurrency locks to preallocate, usually 1/256 estimated capacity</param> - /// <param name="comparer">The element hash generator for keys, or <c>null</c> to use <see cref="EqualityComparer{TKey}.Default"/></param> - public LurchTable(LurchTableOrder ordering, int limit, int hashSize, int allocSize, int lockSize, IEqualityComparer<TKey> comparer) - { - if (limit <= 0) - throw new ArgumentOutOfRangeException("limit"); - if (ordering == LurchTableOrder.None && limit < int.MaxValue) - throw new ArgumentOutOfRangeException("ordering"); - - _limit = limit <= 0 ? int.MaxValue : limit; - _comparer = comparer ?? EqualityComparer<TKey>.Default; - _ordering = ordering; - - allocSize = (int)Math.Min((long)allocSize + OverAlloc, 0x3fffffff); - //last power of 2 that is less than allocSize - for (_shift = 7; _shift < 24 && (1 << (_shift + 1)) < allocSize; _shift++) { } - _allocSize = 1 << _shift; - _shiftMask = _allocSize - 1; - - _hsize = HashUtilities.SelectPrimeNumber(Math.Max(127, hashSize)); - _buckets = new int[_hsize]; - - _lsize = HashUtilities.SelectPrimeNumber(lockSize); - _locks = new object[_lsize]; - for (int i = 0; i < _lsize; i++) - _locks[i] = new object(); - - _free = new FreeList[FreeSlots]; - Initialize(); - } - - #region IDisposable Members - - /// <summary> - /// Clears references to all objects and invalidates the collection - /// </summary> - public void Dispose() - { - _entries = null; - _used = _count = 0; - } - - #endregion - - /// <summary> - /// Gets the number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"/>. - /// </summary> - public int Count { get { return _count; } } - /// <summary> - /// Retrieves the LurchTableOrder Ordering enumeration this instance was created with. - /// </summary> - public LurchTableOrder Ordering { get { return _ordering; } } - /// <summary> - /// Retrives the key comparer being used by this instance. - /// </summary> - public IEqualityComparer<TKey> Comparer { get { return _comparer; } } - /// <summary> - /// Gets or Sets the record limit allowed in this instance. - /// </summary> - public int Limit - { - get { return _limit; } - set { _limit = value; } - } - - /// <summary> - /// WARNING: not thread-safe, reinitializes all internal structures. Use Clear() for a thread-safe - /// delete all. If you have externally provided exclusive access this method may be used to more - /// efficiently clear the collection. - /// </summary> - public void Initialize() - { - lock (this) - { - _freeVersion = _allocNext = 0; - _count = 0; - _used = 1; - - Array.Clear(_buckets, 0, _hsize); - _entries = new[] { new Entry[_allocSize] }; - for (int slot = 0; slot < FreeSlots; slot++) - { - var index = Interlocked.CompareExchange(ref _used, _used + 1, _used); - if (index != slot + 1) - throw new LurchTableCorruptionException(); - - _free[slot].Tail = index; - _free[slot].Head = index; - } - - if (_count != 0 || _used != FreeSlots + 1) - throw new LurchTableCorruptionException(); - } - } - - #region IDictionary<TKey,TValue> Members - - /// <summary> - /// Removes all items from the <see cref="T:System.Collections.Generic.ICollection`1"/>. - /// </summary> - public void Clear() - { - if (_entries == null) throw new ObjectDisposedException(GetType().Name); - foreach (var item in this) - Remove(item.Key); - } - - /// <summary> - /// Determines whether the <see cref="T:System.Collections.Generic.IDictionary`2"/> contains an element with the specified key. - /// </summary> - public bool ContainsKey(TKey key) - { - if (_entries == null) throw new ObjectDisposedException(GetType().Name); - TValue value; - return TryGetValue(key, out value); - } - - /// <summary> - /// Gets or sets the element with the specified key. - /// </summary> - public TValue this[TKey key] - { - set - { - var info = new AddInfo<TKey, TValue> { Value = value, CanUpdate = true }; - Insert(key, ref info); - } - get - { - TValue value; - if (!TryGetValue(key, out value)) - throw new ArgumentOutOfRangeException(); - return value; - } - } - - /// <summary> - /// Gets the value associated with the specified key. - /// </summary> - /// <returns> - /// true if the object that implements <see cref="T:System.Collections.Generic.IDictionary`2"/> contains an element with the specified key; otherwise, false. - /// </returns> - public bool TryGetValue(TKey key, out TValue value) - { - int hash = _comparer.GetHashCode(key) & int.MaxValue; - return InternalGetValue(hash, key, out value); - } - - /// <summary> - /// Adds an element with the provided key and value to the <see cref="T:System.Collections.Generic.IDictionary`2"/>. - /// </summary> - public void Add(TKey key, TValue value) - { - var info = new AddInfo<TKey, TValue> { Value = value }; - if (InsertResult.Inserted != Insert(key, ref info)) - throw new ArgumentOutOfRangeException(); - } - - /// <summary> - /// Removes the element with the specified key from the <see cref="T:System.Collections.Generic.IDictionary`2"/>. - /// </summary> - /// <returns> - /// true if the element is successfully removed; otherwise, false. This method also returns false if <paramref name="key"/> was not found in the original <see cref="T:System.Collections.Generic.IDictionary`2"/>. - /// </returns> - /// <param name="key">The key of the element to remove.</param> - public bool Remove(TKey key) - { - var del = new DelInfo<TKey, TValue>(); - return Delete(key, ref del); - } - - #endregion - - #region IDictionaryEx<TKey,TValue> Members - - /// <summary> - /// Adds a key/value pair to the <see cref="T:System.Collections.Generic.IDictionary`2"/> if the key does not already exist. - /// </summary> - /// <param name="key">The key of the element to add.</param> - /// <param name="value">The value to be added, if the key does not already exist.</param> - public TValue GetOrAdd(TKey key, TValue value) - { - var info = new AddInfo<TKey, TValue> { Value = value, CanUpdate = false }; - if (InsertResult.Exists == Insert(key, ref info)) - return info.Value; - return value; - } - - /// <summary> - /// Adds an element with the provided key and value to the <see cref="T:System.Collections.Generic.IDictionary`2"/>. - /// </summary> - /// <param name="key">The object to use as the key of the element to add.</param> - /// <param name="value">The object to use as the value of the element to add.</param> - public bool TryAdd(TKey key, TValue value) - { - var info = new AddInfo<TKey, TValue> { Value = value, CanUpdate = false }; - return InsertResult.Inserted == Insert(key, ref info); - } - - /// <summary> - /// Updates an element with the provided key to the value if it exists. - /// </summary> - /// <returns>Returns true if the key provided was found and updated to the value.</returns> - /// <param name="key">The object to use as the key of the element to update.</param> - /// <param name="value">The new value for the key if found.</param> - public bool TryUpdate(TKey key, TValue value) - { - var info = new UpdateInfo<TKey, TValue> { Value = value }; - return InsertResult.Updated == Insert(key, ref info); - } - - /// <summary> - /// Updates an element with the provided key to the value if it exists. - /// </summary> - /// <returns>Returns true if the key provided was found and updated to the value.</returns> - /// <param name="key">The object to use as the key of the element to update.</param> - /// <param name="value">The new value for the key if found.</param> - /// <param name="comparisonValue">The value that is compared to the value of the element with key.</param> - public bool TryUpdate(TKey key, TValue value, TValue comparisonValue) - { - var info = new UpdateInfo<TKey, TValue>(comparisonValue) { Value = value }; - return InsertResult.Updated == Insert(key, ref info); - } - - /// <summary> - /// Removes the element with the specified key from the <see cref="T:System.Collections.Generic.IDictionary`2"/>. - /// </summary> - /// <returns> - /// true if the element is successfully removed; otherwise, false. This method also returns false if <paramref name="key"/> was not found in the original <see cref="T:System.Collections.Generic.IDictionary`2"/>. - /// </returns> - /// <param name="key">The key of the element to remove.</param> - /// <param name="value">The value that was removed.</param> - public bool TryRemove(TKey key, out TValue value) - { - var info = new DelInfo<TKey, TValue>(); - if (Delete(key, ref info)) - { - value = info.Value; - return true; - } - value = default(TValue); - return false; - } - - #endregion - - #region IConcurrentDictionary<TKey,TValue> Members - - /// <summary> - /// Adds a key/value pair to the <see cref="T:System.Collections.Generic.IDictionary`2"/> if the key does not already exist. - /// </summary> - /// <param name="key">The key of the element to add.</param> - /// <param name="fnCreate">Constructs a new value for the key.</param> - public TValue GetOrAdd(TKey key, Func<TKey, TValue> fnCreate) - { - var info = new Add2Info<TKey, TValue> { Create = fnCreate }; - Insert(key, ref info); - return info.Value; - } - - /// <summary> - /// Adds a key/value pair to the <see cref="T:System.Collections.Generic.IDictionary`2"/> if the key does not already exist, - /// or updates a key/value pair if the key already exists. - /// </summary> - public TValue AddOrUpdate(TKey key, TValue addValue, KeyValueUpdate<TKey, TValue> fnUpdate) - { - var info = new Add2Info<TKey, TValue>(addValue) { Update = fnUpdate }; - Insert(key, ref info); - return info.Value; - } - - /// <summary> - /// Adds a key/value pair to the <see cref="T:System.Collections.Generic.IDictionary`2"/> if the key does not already exist, - /// or updates a key/value pair if the key already exists. - /// </summary> - /// <remarks> - /// Adds or modifies an element with the provided key and value. If the key does not exist in the collection, - /// the factory method fnCreate will be called to produce the new value, if the key exists, the converter method - /// fnUpdate will be called to create an updated value. - /// </remarks> - public TValue AddOrUpdate(TKey key, Func<TKey, TValue> fnCreate, KeyValueUpdate<TKey, TValue> fnUpdate) - { - var info = new Add2Info<TKey, TValue> { Create = fnCreate, Update = fnUpdate }; - Insert(key, ref info); - return info.Value; - } - - /// <summary> - /// Add, update, or fetche a key/value pair from the dictionary via an implementation of the - /// <see cref="T:CSharpTest.Net.Collections.ICreateOrUpdateValue`2"/> interface. - /// </summary> - public bool AddOrUpdate<T>(TKey key, ref T createOrUpdateValue) where T : ICreateOrUpdateValue<TKey, TValue> - { - var result = Insert(key, ref createOrUpdateValue); - return result == InsertResult.Inserted || result == InsertResult.Updated; - } - - /// <summary> - /// Adds an element with the provided key and value to the <see cref="T:System.Collections.Generic.IDictionary`2"/> - /// by calling the provided factory method to construct the value if the key is not already present in the collection. - /// </summary> - public bool TryAdd(TKey key, Func<TKey, TValue> fnCreate) - { - var info = new Add2Info<TKey, TValue> { Create = fnCreate }; - return InsertResult.Inserted == Insert(key, ref info); - } - - /// <summary> - /// Modify the value associated with the result of the provided update method - /// as an atomic operation, Allows for reading/writing a single record within - /// the syncronization lock. - /// </summary> - public bool TryUpdate(TKey key, KeyValueUpdate<TKey, TValue> fnUpdate) - { - var info = new Add2Info<TKey, TValue> { Update = fnUpdate }; - return InsertResult.Updated == Insert(key, ref info); - } - - /// <summary> - /// Removes the element with the specified key from the <see cref="T:System.Collections.Generic.IDictionary`2"/> - /// if the fnCondition predicate is null or returns true. - /// </summary> - public bool TryRemove(TKey key, KeyValuePredicate<TKey, TValue> fnCondition) - { - var info = new DelInfo<TKey, TValue> { Condition = fnCondition }; - return Delete(key, ref info); - } - - /// <summary> - /// Conditionally removes a key/value pair from the dictionary via an implementation of the - /// <see cref="T:CSharpTest.Net.Collections.IRemoveValue`2"/> interface. - /// </summary> - public bool TryRemove<T>(TKey key, ref T removeValue) where T : IRemoveValue<TKey, TValue> - { - return Delete(key, ref removeValue); - } - - #endregion - - #region ICollection<KeyValuePair<TKey,TValue>> Members - - bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly - { - get { return false; } - } - - void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item) - { - Add(item.Key, item.Value); - } - - bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item) - { - TValue test; - if (TryGetValue(item.Key, out test)) - return EqualityComparer<TValue>.Default.Equals(item.Value, test); - return false; - } - - void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) - { - foreach (var item in this) - array[arrayIndex++] = item; - } - - bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item) - { - var del = new DelInfo<TKey, TValue>(item.Value); - return Delete(item.Key, ref del); - } - - #endregion - - #region IEnumerator<KeyValuePair<TKey, TValue>> - - private bool MoveNext(ref EnumState state) - { - if (_entries == null) throw new ObjectDisposedException(GetType().Name); - - if (state.Current > 0) - state.Current = state.Next; - - if (state.Current > 0) - { - state.Next = _entries[state.Current >> _shift][state.Current & _shiftMask].Link; - return true; - } - - state.Unlock(); - while (++state.Bucket < _hsize) - { - if (_buckets[state.Bucket] == 0) - continue; - - state.Lock(_locks[state.Bucket % _lsize]); - - state.Current = _buckets[state.Bucket]; - if (state.Current > 0) - { - state.Next = _entries[state.Current >> _shift][state.Current & _shiftMask].Link; - return true; - } - - state.Unlock(); - } - - return false; - } - - /// <summary> - /// Provides an enumerator that iterates through the collection. - /// </summary> - public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>> - { - private readonly LurchTable<TKey, TValue> _owner; - private EnumState _state; - - internal Enumerator(LurchTable<TKey, TValue> owner) - { - _owner = owner; - _state = new EnumState(); - _state.Init(); - } - - /// <summary> - /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources. - /// </summary> - public void Dispose() - { - _state.Unlock(); - } - - object IEnumerator.Current { get { return Current; } } - - /// <summary> - /// Gets the element in the collection at the current position of the enumerator. - /// </summary> - public KeyValuePair<TKey, TValue> Current - { - get - { - int index = _state.Current; - if (index <= 0) - throw new InvalidOperationException(); - if (_owner._entries == null) - throw new ObjectDisposedException(GetType().Name); - - return new KeyValuePair<TKey, TValue> - ( - _owner._entries[index >> _owner._shift][index & _owner._shiftMask].Key, - _owner._entries[index >> _owner._shift][index & _owner._shiftMask].Value - ); - } - } - - /// <summary> - /// Advances the enumerator to the next element of the collection. - /// </summary> - public bool MoveNext() - { - return _owner.MoveNext(ref _state); - } - - /// <summary> - /// Sets the enumerator to its initial position, which is before the first element in the collection. - /// </summary> - public void Reset() - { - _state.Unlock(); - _state.Init(); - } - } - - /// <summary> - /// Returns an enumerator that iterates through the collection. - /// </summary> - public Enumerator GetEnumerator() { return new Enumerator(this); } - IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator() - { return GetEnumerator(); } - IEnumerator IEnumerable.GetEnumerator() - { return GetEnumerator(); } - #endregion - - #region KeyCollection - /// <summary> - /// Provides the collection of Keys for the LurchTable - /// </summary> - public class KeyCollection : ICollection<TKey> - { - private readonly LurchTable<TKey, TValue> _owner; - - internal KeyCollection(LurchTable<TKey, TValue> owner) - { - _owner = owner; - } - - #region ICollection<TKey> Members - - /// <summary> - /// Determines whether the <see cref="T:System.Collections.Generic.ICollection`1"/> contains a specific value. - /// </summary> - public bool Contains(TKey item) - { - return _owner.ContainsKey(item); - } - - /// <summary> - /// Copies the elements of the <see cref="T:System.Collections.Generic.ICollection`1"/> to an <see cref="T:System.Array"/>, starting at a particular <see cref="T:System.Array"/> index. - /// </summary> - public void CopyTo(TKey[] array, int arrayIndex) - { - foreach (var item in _owner) - array[arrayIndex++] = item.Key; - } - - /// <summary> - /// Gets the number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"/>. - /// </summary> - public int Count - { - get { return _owner.Count; } - } - - /// <summary> - /// Returns an enumerator that iterates through the collection. - /// </summary> - public Enumerator GetEnumerator() - { - return new Enumerator(_owner); - } - - /// <summary> - /// Provides an enumerator that iterates through the collection. - /// </summary> - public struct Enumerator : IEnumerator<TKey> - { - private readonly LurchTable<TKey, TValue> _owner; - private EnumState _state; - - internal Enumerator(LurchTable<TKey, TValue> owner) - { - _owner = owner; - _state = new EnumState(); - _state.Init(); - } - - /// <summary> - /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources. - /// </summary> - public void Dispose() - { - _state.Unlock(); - } - - object IEnumerator.Current { get { return Current; } } - - /// <summary> - /// Gets the element in the collection at the current position of the enumerator. - /// </summary> - public TKey Current - { - get - { - int index = _state.Current; - if (index <= 0) - throw new InvalidOperationException(); - if (_owner._entries == null) - throw new ObjectDisposedException(GetType().Name); - return _owner._entries[index >> _owner._shift][index & _owner._shiftMask].Key; - } - } - - /// <summary> - /// Advances the enumerator to the next element of the collection. - /// </summary> - public bool MoveNext() - { - return _owner.MoveNext(ref _state); - } - - /// <summary> - /// Sets the enumerator to its initial position, which is before the first element in the collection. - /// </summary> - public void Reset() - { - _state.Unlock(); - _state.Init(); - } - } - [Obsolete] - IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator() - { - return new Enumerator(_owner); - } - [Obsolete] - IEnumerator IEnumerable.GetEnumerator() - { - return new Enumerator(_owner); - } - [Obsolete] - bool ICollection<TKey>.IsReadOnly - { - get { return true; } - } - [Obsolete] - void ICollection<TKey>.Add(TKey item) - { - throw new NotSupportedException(); - } - [Obsolete] - void ICollection<TKey>.Clear() - { - throw new NotSupportedException(); - } - [Obsolete] - bool ICollection<TKey>.Remove(TKey item) - { - throw new NotSupportedException(); - } - - #endregion - } - - private KeyCollection _keyCollection; - /// <summary> - /// Gets an <see cref="T:System.Collections.Generic.ICollection`1"/> containing the keys of the <see cref="T:System.Collections.Generic.IDictionary`2"/>. - /// </summary> - public KeyCollection Keys { get { return _keyCollection ?? (_keyCollection = new KeyCollection(this)); } } - [Obsolete] - ICollection<TKey> IDictionary<TKey, TValue>.Keys { get { return Keys; } } - #endregion - - #region ValueCollection - /// <summary> - /// Provides the collection of Values for the LurchTable - /// </summary> - public class ValueCollection : ICollection<TValue> - { - private readonly LurchTable<TKey, TValue> _owner; - - internal ValueCollection(LurchTable<TKey, TValue> owner) - { - _owner = owner; - } - - #region ICollection<TValue> Members - - /// <summary> - /// Determines whether the <see cref="T:System.Collections.Generic.ICollection`1"/> contains a specific value. - /// </summary> - public bool Contains(TValue value) - { - var comparer = EqualityComparer<TValue>.Default; - foreach (var item in _owner) - { - if (comparer.Equals(item.Value, value)) - return true; - } - return false; - } - - /// <summary> - /// Copies the elements of the <see cref="T:System.Collections.Generic.ICollection`1"/> to an <see cref="T:System.Array"/>, starting at a particular <see cref="T:System.Array"/> index. - /// </summary> - public void CopyTo(TValue[] array, int arrayIndex) - { - foreach (var item in _owner) - array[arrayIndex++] = item.Value; - } - - /// <summary> - /// Gets the number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"/>. - /// </summary> - public int Count - { - get { return _owner.Count; } - } - - /// <summary> - /// Returns an enumerator that iterates through the collection. - /// </summary> - public Enumerator GetEnumerator() - { - return new Enumerator(_owner); - } - - /// <summary> - /// Provides an enumerator that iterates through the collection. - /// </summary> - public struct Enumerator : IEnumerator<TValue> - { - private readonly LurchTable<TKey, TValue> _owner; - private EnumState _state; - - internal Enumerator(LurchTable<TKey, TValue> owner) - { - _owner = owner; - _state = new EnumState(); - _state.Init(); - } - - /// <summary> - /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources. - /// </summary> - public void Dispose() - { - _state.Unlock(); - } - - object IEnumerator.Current { get { return Current; } } - - /// <summary> - /// Gets the element in the collection at the current position of the enumerator. - /// </summary> - public TValue Current - { - get - { - int index = _state.Current; - if (index <= 0) - throw new InvalidOperationException(); - if (_owner._entries == null) - throw new ObjectDisposedException(GetType().Name); - return _owner._entries[index >> _owner._shift][index & _owner._shiftMask].Value; - } - } - - /// <summary> - /// Advances the enumerator to the next element of the collection. - /// </summary> - public bool MoveNext() - { - return _owner.MoveNext(ref _state); - } - - /// <summary> - /// Sets the enumerator to its initial position, which is before the first element in the collection. - /// </summary> - public void Reset() - { - _state.Unlock(); - _state.Init(); - } - } - [Obsolete] - IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator() - { - return new Enumerator(_owner); - } - [Obsolete] - IEnumerator IEnumerable.GetEnumerator() - { - return new Enumerator(_owner); - } - [Obsolete] - bool ICollection<TValue>.IsReadOnly - { - get { return true; } - } - [Obsolete] - void ICollection<TValue>.Add(TValue item) - { - throw new NotSupportedException(); - } - [Obsolete] - void ICollection<TValue>.Clear() - { - throw new NotSupportedException(); - } - [Obsolete] - bool ICollection<TValue>.Remove(TValue item) - { - throw new NotSupportedException(); - } - - #endregion - } - - private ValueCollection _valueCollection; - /// <summary> - /// Gets an <see cref="T:System.Collections.Generic.ICollection`1"/> containing the values in the <see cref="T:System.Collections.Generic.IDictionary`2"/>. - /// </summary> - public ValueCollection Values { get { return _valueCollection ?? (_valueCollection = new ValueCollection(this)); } } - [Obsolete] - ICollection<TValue> IDictionary<TKey, TValue>.Values { get { return Values; } } - - #endregion - - #region Peek/Dequeue - - /// <summary> - /// Retrieves the oldest entry in the collection based on the ordering supplied to the constructor. - /// </summary> - /// <returns>True if the out parameter value was set.</returns> - /// <exception cref="System.InvalidOperationException">Raised if the table is unordered</exception> - public bool Peek(out KeyValuePair<TKey, TValue> value) - { - if (_ordering == LurchTableOrder.None) - throw new InvalidOperationException(); - if (_entries == null) - throw new ObjectDisposedException(GetType().Name); - - while (true) - { - int index = Interlocked.CompareExchange(ref _entries[0][0].Prev, 0, 0); - if (index == 0) - { - value = default(KeyValuePair<TKey, TValue>); - return false; - } - - int hash = _entries[index >> _shift][index & _shiftMask].Hash; - if (hash >= 0) - { - int bucket = hash % _hsize; - lock (_locks[bucket % _lsize]) - { - if (index == _entries[0][0].Prev && - hash == _entries[index >> _shift][index & _shiftMask].Hash) - { - value = new KeyValuePair<TKey, TValue>( - _entries[index >> _shift][index & _shiftMask].Key, - _entries[index >> _shift][index & _shiftMask].Value - ); - return true; - } - } - } - } - } - - /// <summary> - /// Removes the oldest entry in the collection based on the ordering supplied to the constructor. - /// If an item is not available a busy-wait loop is used to wait for for an item. - /// </summary> - /// <returns>The Key/Value pair removed.</returns> - /// <exception cref="System.InvalidOperationException">Raised if the table is unordered</exception> - public KeyValuePair<TKey, TValue> Dequeue() - { - if (_ordering == LurchTableOrder.None) - throw new InvalidOperationException(); - if (_entries == null) - throw new ObjectDisposedException(GetType().Name); - - KeyValuePair<TKey, TValue> value; - while (!TryDequeue(out value)) - { - while (0 == Interlocked.CompareExchange(ref _entries[0][0].Prev, 0, 0)) - Thread.Sleep(0); - } - return value; - } - - /// <summary> - /// Removes the oldest entry in the collection based on the ordering supplied to the constructor. - /// </summary> - /// <returns>False if no item was available</returns> - /// <exception cref="System.InvalidOperationException">Raised if the table is unordered</exception> - public bool TryDequeue(out KeyValuePair<TKey, TValue> value) - { - return TryDequeue(null, out value); - } - - /// <summary> - /// Removes the oldest entry in the collection based on the ordering supplied to the constructor. - /// </summary> - /// <returns>False if no item was available</returns> - /// <exception cref="System.InvalidOperationException">Raised if the table is unordered</exception> - public bool TryDequeue(Predicate<KeyValuePair<TKey, TValue>> predicate, out KeyValuePair<TKey, TValue> value) - { - if (_ordering == LurchTableOrder.None) - throw new InvalidOperationException(); - if (_entries == null) - throw new ObjectDisposedException(GetType().Name); - - while (true) - { - int index = Interlocked.CompareExchange(ref _entries[0][0].Prev, 0, 0); - if (index == 0) - { - value = default(KeyValuePair<TKey, TValue>); - return false; - } - - int hash = _entries[index >> _shift][index & _shiftMask].Hash; - if (hash >= 0) - { - int bucket = hash % _hsize; - lock (_locks[bucket % _lsize]) - { - if (index == _entries[0][0].Prev && - hash == _entries[index >> _shift][index & _shiftMask].Hash) - { - if (predicate != null) - { - var item = new KeyValuePair<TKey, TValue>( - _entries[index >> _shift][index & _shiftMask].Key, - _entries[index >> _shift][index & _shiftMask].Value - ); - if (!predicate(item)) - { - value = item; - return false; - } - } - - int next = _entries[index >> _shift][index & _shiftMask].Link; - bool removed = false; - - if (_buckets[bucket] == index) - { - _buckets[bucket] = next; - removed = true; - } - else - { - int test = _buckets[bucket]; - while (test != 0) - { - int cmp = _entries[test >> _shift][test & _shiftMask].Link; - if (cmp == index) - { - _entries[test >> _shift][test & _shiftMask].Link = next; - removed = true; - break; - } - test = cmp; - } - } - if (!removed) - throw new LurchTableCorruptionException(); - - value = new KeyValuePair<TKey, TValue>( - _entries[index >> _shift][index & _shiftMask].Key, - _entries[index >> _shift][index & _shiftMask].Value - ); - Interlocked.Decrement(ref _count); - if (_ordering != LurchTableOrder.None) - InternalUnlink(index); - FreeSlot(ref index, Interlocked.Increment(ref _freeVersion)); - - var handler = ItemRemoved; - if (handler != null) - handler(value); - - return true; - } - } - } - } - } - - #endregion - - #region Internal Implementation - - enum InsertResult { Inserted = 1, Updated = 2, Exists = 3, NotFound = 4 } - - bool InternalGetValue(int hash, TKey key, out TValue value) - { - if (_entries == null) - throw new ObjectDisposedException(GetType().Name); - - int bucket = hash % _hsize; - lock (_locks[bucket % _lsize]) - { - int index = _buckets[bucket]; - while (index != 0) - { - if (hash == _entries[index >> _shift][index & _shiftMask].Hash && - _comparer.Equals(key, _entries[index >> _shift][index & _shiftMask].Key)) - { - value = _entries[index >> _shift][index & _shiftMask].Value; - if (hash == _entries[index >> _shift][index & _shiftMask].Hash) - { - if (_ordering == LurchTableOrder.Access) - { - InternalUnlink(index); - InternalLink(index); - } - return true; - } - } - index = _entries[index >> _shift][index & _shiftMask].Link; - } - - value = default(TValue); - return false; - } - } - - InsertResult Insert<T>(TKey key, ref T value) where T : ICreateOrUpdateValue<TKey, TValue> - { - if (_entries == null) - throw new ObjectDisposedException(GetType().Name); - - int hash = _comparer.GetHashCode(key) & int.MaxValue; - int added; - - InsertResult result = InternalInsert(hash, key, out added, ref value); - - if (added > _limit && _ordering != LurchTableOrder.None) - { - KeyValuePair<TKey, TValue> ignore; - TryDequeue(out ignore); - } - return result; - } - - InsertResult InternalInsert<T>(int hash, TKey key, out int added, ref T value) where T : ICreateOrUpdateValue<TKey, TValue> - { - int bucket = hash % _hsize; - lock (_locks[bucket % _lsize]) - { - TValue temp; - int index = _buckets[bucket]; - while (index != 0) - { - if (hash == _entries[index >> _shift][index & _shiftMask].Hash && - _comparer.Equals(key, _entries[index >> _shift][index & _shiftMask].Key)) - { - temp = _entries[index >> _shift][index & _shiftMask].Value; - var original = temp; - if (value.UpdateValue(key, ref temp)) - { - _entries[index >> _shift][index & _shiftMask].Value = temp; - - if (_ordering == LurchTableOrder.Modified || _ordering == LurchTableOrder.Access) - { - InternalUnlink(index); - InternalLink(index); - } - - var handler = ItemUpdated; - if (handler != null) - handler(new KeyValuePair<TKey, TValue>(key, original), new KeyValuePair<TKey, TValue>(key, temp)); - - added = -1; - return InsertResult.Updated; - } - - added = -1; - return InsertResult.Exists; - } - index = _entries[index >> _shift][index & _shiftMask].Link; - } - if (value.CreateValue(key, out temp)) - { -#pragma warning disable 612,618 - index = AllocSlot(); -#pragma warning restore 612,618 - _entries[index >> _shift][index & _shiftMask].Hash = hash; - _entries[index >> _shift][index & _shiftMask].Key = key; - _entries[index >> _shift][index & _shiftMask].Value = temp; - _entries[index >> _shift][index & _shiftMask].Link = _buckets[bucket]; - _buckets[bucket] = index; - - added = Interlocked.Increment(ref _count); - if (_ordering != LurchTableOrder.None) - InternalLink(index); - - var handler = ItemAdded; - if (handler != null) - handler(new KeyValuePair<TKey, TValue>(key, temp)); - - return InsertResult.Inserted; - } - } - - added = -1; - return InsertResult.NotFound; - } - - bool Delete<T>(TKey key, ref T value) where T : IRemoveValue<TKey, TValue> - { - if (_entries == null) - throw new ObjectDisposedException(GetType().Name); - - int hash = _comparer.GetHashCode(key) & int.MaxValue; - int bucket = hash % _hsize; - lock (_locks[bucket % _lsize]) - { - int prev = 0; - int index = _buckets[bucket]; - while (index != 0) - { - if (hash == _entries[index >> _shift][index & _shiftMask].Hash && - _comparer.Equals(key, _entries[index >> _shift][index & _shiftMask].Key)) - { - TValue temp = _entries[index >> _shift][index & _shiftMask].Value; - - if (value.RemoveValue(key, temp)) - { - int next = _entries[index >> _shift][index & _shiftMask].Link; - if (prev == 0) - _buckets[bucket] = next; - else - _entries[prev >> _shift][prev & _shiftMask].Link = next; - - Interlocked.Decrement(ref _count); - if (_ordering != LurchTableOrder.None) - InternalUnlink(index); - FreeSlot(ref index, Interlocked.Increment(ref _freeVersion)); - - var handler = ItemRemoved; - if (handler != null) - handler(new KeyValuePair<TKey, TValue>(key, temp)); - - return true; - } - return false; - } - - prev = index; - index = _entries[index >> _shift][index & _shiftMask].Link; - } - } - return false; - } - - void InternalLink(int index) - { - Interlocked.Exchange(ref _entries[index >> _shift][index & _shiftMask].Prev, 0); - Interlocked.Exchange(ref _entries[index >> _shift][index & _shiftMask].Next, ~0); - int next = Interlocked.Exchange(ref _entries[0][0].Next, index); - if (next < 0) - throw new LurchTableCorruptionException(); - - while (0 != Interlocked.CompareExchange(ref _entries[next >> _shift][next & _shiftMask].Prev, index, 0)) - { } - - Interlocked.Exchange(ref _entries[index >> _shift][index & _shiftMask].Next, next); - } - - void InternalUnlink(int index) - { - while (true) - { - int cmp; - int prev = _entries[index >> _shift][index & _shiftMask].Prev; - while (prev >= 0 && prev != (cmp = Interlocked.CompareExchange( - ref _entries[index >> _shift][index & _shiftMask].Prev, ~prev, prev))) - prev = cmp; - if (prev < 0) - throw new LurchTableCorruptionException(); - - int next = _entries[index >> _shift][index & _shiftMask].Next; - while (next >= 0 && next != (cmp = Interlocked.CompareExchange( - ref _entries[index >> _shift][index & _shiftMask].Next, ~next, next))) - next = cmp; - if (next < 0) - throw new LurchTableCorruptionException(); - - if ((Interlocked.CompareExchange( - ref _entries[prev >> _shift][prev & _shiftMask].Next, next, index) == index)) - { - while (Interlocked.CompareExchange( - ref _entries[next >> _shift][next & _shiftMask].Prev, prev, index) != index) - { } - return; - } - - //cancel the delete markers and retry - if (~next != Interlocked.CompareExchange( - ref _entries[index >> _shift][index & _shiftMask].Next, next, ~next)) - throw new LurchTableCorruptionException(); - if (~prev != Interlocked.CompareExchange( - ref _entries[index >> _shift][index & _shiftMask].Prev, prev, ~prev)) - throw new LurchTableCorruptionException(); - } - } - - [Obsolete("Release build inlining, so we need to ignore for testing.")] - int AllocSlot() - { - while (true) - { - int allocated = _entries.Length * _allocSize; - var previous = _entries; - - while (_count + OverAlloc < allocated || _used < allocated) - { - int next; - if (_count + FreeSlots < _used) - { - int freeSlotIndex = Interlocked.Increment(ref _allocNext); - int slot = (freeSlotIndex & int.MaxValue) % FreeSlots; - next = Interlocked.Exchange(ref _free[slot].Head, 0); - if (next != 0) - { - int nextFree = _entries[next >> _shift][next & _shiftMask].Link; - if (nextFree == 0) - { - Interlocked.Exchange(ref _free[slot].Head, next); - } - else - { - Interlocked.Exchange(ref _free[slot].Head, nextFree); - return next; - } - } - } - - next = _used; - if (next < allocated) - { - int alloc = Interlocked.CompareExchange(ref _used, next + 1, next); - if (alloc == next) - { - return next; - } - } - } - - lock (this) - { - //time to grow... - if (ReferenceEquals(_entries, previous)) - { - Entry[][] arentries = new Entry[_entries.Length + 1][]; - _entries.CopyTo(arentries, 0); - arentries[arentries.Length - 1] = new Entry[_allocSize]; - - Interlocked.CompareExchange(ref _entries, arentries, previous); - } - } - } - } - - void FreeSlot(ref int index, int ver) - { - _entries[index >> _shift][index & _shiftMask].Key = default(TKey); - _entries[index >> _shift][index & _shiftMask].Value = default(TValue); - Interlocked.Exchange(ref _entries[index >> _shift][index & _shiftMask].Link, 0); - - int slot = (ver & int.MaxValue) % FreeSlots; - int prev = Interlocked.Exchange(ref _free[slot].Tail, index); - - if (prev <= 0 || 0 != Interlocked.CompareExchange(ref _entries[prev >> _shift][prev & _shiftMask].Link, index, 0)) - { - throw new LurchTableCorruptionException(); - } - } - - #endregion - - #region Internal Structures - - struct FreeList - { - public int Head; - public int Tail; - } - - struct Entry - { - public int Prev, Next; // insertion/access sequence ordering - public int Link; - public int Hash; // hash value of entry's Key - public TKey Key; // key of entry - public TValue Value; // value of entry - } - - struct EnumState - { - private object _locked; - public int Bucket, Current, Next; - public void Init() - { - Bucket = -1; - Current = 0; - Next = 0; - _locked = null; - } - - public void Unlock() - { - if (_locked != null) - { - Monitor.Exit(_locked); - _locked = null; - } - } - - public void Lock(object lck) - { - if (_locked != null) - Monitor.Exit(_locked); - Monitor.Enter(_locked = lck); - } - } - - #endregion - } - - #region LurchTable Support - - #region Internal Structures (de-nested) - - // LUCENENET NOTE: These were originally nested within LurchTable, but - // using nested generic structs without explicitly defining their parameters - // fails on Xamarin.iOS because of incomplete generics support. Therefore, - // we de-nested them and moved them here. See: LUCENENET-602 - - struct DelInfo<TKey, TValue> : IRemoveValue<TKey, TValue> - { - public TValue Value; - readonly bool _hasTestValue; - readonly TValue _testValue; - public KeyValuePredicate<TKey, TValue> Condition; - - public DelInfo(TValue expected) - { - Value = default(TValue); - _testValue = expected; - _hasTestValue = true; - Condition = null; - } - - public bool RemoveValue(TKey key, TValue value) - { - Value = value; - - if (_hasTestValue && !EqualityComparer<TValue>.Default.Equals(_testValue, value)) - return false; - if (Condition != null && !Condition(key, value)) - return false; - - return true; - } - } - - struct AddInfo<TKey, TValue> : ICreateOrUpdateValue<TKey, TValue> - { - public bool CanUpdate; - public TValue Value; - public bool CreateValue(TKey key, out TValue value) - { - value = Value; - return true; - } - - public bool UpdateValue(TKey key, ref TValue value) - { - if (!CanUpdate) - { - Value = value; - return false; - } - - value = Value; - return true; - } - } - - struct Add2Info<TKey, TValue> : ICreateOrUpdateValue<TKey, TValue> - { - readonly bool _hasAddValue; - readonly TValue _addValue; - public TValue Value; - public Func<TKey, TValue> Create; - public KeyValueUpdate<TKey, TValue> Update; - - public Add2Info(TValue addValue) : this() - { - _hasAddValue = true; - _addValue = addValue; - } - - public bool CreateValue(TKey key, out TValue value) - { - if (_hasAddValue) - { - value = Value = _addValue; - return true; - } - if (Create != null) - { - value = Value = Create(key); - return true; - } - value = Value = default(TValue); - return false; - } - - public bool UpdateValue(TKey key, ref TValue value) - { - if (Update == null) - { - Value = value; - return false; - } - - value = Value = Update(key, value); - return true; - } - } - - struct UpdateInfo<TKey, TValue> : ICreateOrUpdateValue<TKey, TValue> - { - public TValue Value; - readonly bool _hasTestValue; - readonly TValue _testValue; - - public UpdateInfo(TValue expected) - { - Value = default(TValue); - _testValue = expected; - _hasTestValue = true; - } - - bool ICreateValue<TKey, TValue>.CreateValue(TKey key, out TValue value) - { - value = default(TValue); - return false; - } - public bool UpdateValue(TKey key, ref TValue value) - { - if (_hasTestValue && !EqualityComparer<TValue>.Default.Equals(_testValue, value)) - return false; - - value = Value; - return true; - } - } - - #endregion - - #region Exceptions - - /// <summary> - /// Exception class: LurchTableCorruptionException - /// The LurchTable internal datastructure appears to be corrupted. - /// </summary> -#if FEATURE_SERIALIZABLE - [System.SerializableAttribute()] -#endif - [global::System.Diagnostics.DebuggerStepThroughAttribute()] - [global::System.Diagnostics.DebuggerNonUserCodeAttribute()] - [global::System.Runtime.CompilerServices.CompilerGeneratedAttribute()] - [global::System.CodeDom.Compiler.GeneratedCodeAttribute("CSharpTest.Net.Generators", "2.13.222.435")] - public partial class LurchTableCorruptionException : Exception - { -#if FEATURE_SERIALIZABLE - /// <summary> - /// Serialization constructor - /// </summary> - protected LurchTableCorruptionException(System.Runtime.Serialization.SerializationInfo info, System.Runtime.Serialization.StreamingContext context) : base(info, context) - { - } -#endif - /// <summary> - /// Used to create this exception from an hresult and message bypassing the message formatting - /// </summary> - internal static System.Exception Create(int hResult, string message) - { - return new LurchTableCorruptionException((System.Exception)null, hResult, message); - } - /// <summary> - /// Constructs the exception from an hresult and message bypassing the message formatting - /// </summary> - protected LurchTableCorruptionException(System.Exception innerException, int hResult, string message) : base(message, innerException) - { - base.HResult = hResult; - } - /// <summary> - /// The LurchTable internal datastructure appears to be corrupted. - /// </summary> - public LurchTableCorruptionException() - : this((System.Exception)null, -1, "The LurchTable internal datastructure appears to be corrupted.") - { - } - /// <summary> - /// The LurchTable internal datastructure appears to be corrupted. - /// </summary> - public LurchTableCorruptionException(System.Exception innerException) - : this(innerException, -1, "The LurchTable internal datastructure appears to be corrupted.") - { - } - /// <summary> - /// if(condition == false) throws The LurchTable internal datastructure appears to be corrupted. - /// </summary> - public static void Assert(bool condition) - { - if (!condition) throw new LurchTableCorruptionException(); - } - } - -#endregion // Exceptions - -#region Delegates - - /// <summary> Provides a delegate that performs an atomic update of a key/value pair </summary> - public delegate TValue KeyValueUpdate<TKey, TValue>(TKey key, TValue original); - - /// <summary> Provides a delegate that performs a test on key/value pair </summary> - public delegate bool KeyValuePredicate<TKey, TValue>(TKey key, TValue original); - -#endregion // Delegates - -#region Interfaces - - /// <summary> - /// An interface to provide conditional or custom creation logic to a concurrent dictionary. - /// </summary> - public interface ICreateValue<TKey, TValue> - { - /// <summary> - /// Called when the key was not found within the dictionary to produce a new value that can be added. - /// Return true to continue with the insertion, or false to prevent the key/value from being inserted. - /// </summary> - bool CreateValue(TKey key, out TValue value); - } - /// <summary> - /// An interface to provide conditional or custom update logic to a concurrent dictionary. - /// </summary> - public interface IUpdateValue<TKey, TValue> - { - /// <summary> - /// Called when the key was found within the dictionary to produce a modified value to update the item - /// to. Return true to continue with the update, or false to prevent the key/value from being updated. - /// </summary> - bool UpdateValue(TKey key, ref TValue value); - } - /// <summary> - /// An interface to provide conditional or custom creation or update logic to a concurrent dictionary. - /// </summary> - /// <remarks> - /// Generally implemented as a struct and passed by ref to save stack space and to retrieve the values - /// that where inserted or updated. - /// </remarks> - public interface ICreateOrUpdateValue<TKey, TValue> : ICreateValue<TKey, TValue>, IUpdateValue<TKey, TValue> - { - } - - /// <summary> - /// An interface to provide conditional removal of an item from a concurrent dictionary. - /// </summary> - /// <remarks> - /// Generally implemented as a struct and passed by ref to save stack space and to retrieve the values - /// that where inserted or updated. - /// </remarks> - public interface IRemoveValue<TKey, TValue> - { - /// <summary> - /// Called when the dictionary is about to remove the key/value pair provided, return true to allow - /// it's removal, or false to prevent it from being removed. - /// </summary> - bool RemoveValue(TKey key, TValue value); - } - -#endregion // interfaces - -#region Classes - - internal class HashUtilities - { - private static readonly int[] PrimeNumbers = - new[] - { - 17, 37, 67, 131, 257, 521, // ROK - Added smaller primes - 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, - 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437, - 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, - 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369 - }; - - internal static int SelectPrimeNumber(int hashSize) - { - int offset = Array.BinarySearch(PrimeNumbers, hashSize); - if (offset < 0) - offset = ~offset; - return PrimeNumbers[Math.Min(offset, PrimeNumbers.Length - 1)]; - } - } - -#endregion // Classes - -#endregion // LurchTable Support -}
