#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 using System; using System.Collections; using System.Collections.Generic; using System.Threading; namespace CSharpTest.Net.Collections { /// /// 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. /// public enum LurchTableOrder { /// No linking None, /// Linked in insertion order Insertion, /// Linked by most recently inserted or updated Modified, /// Linked by most recently inserted, updated, or fetched Access, } /// /// 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. /// /// The type of keys in the dictionary. /// The type of values in the dictionary. public class LurchTable : IDictionary, IDictionaryEx, IConcurrentDictionary { /// Method signature for the ItemUpdated event public delegate void ItemUpdatedMethod(KeyValuePair previous, KeyValuePair next); /// Event raised after an item is removed from the collection public event Action> ItemRemoved; /// Event raised after an item is updated in the collection public event ItemUpdatedMethod ItemUpdated; /// Event raised after an item is added to the collection public event Action> ItemAdded; private const int OverAlloc = 128; private const int FreeSlots = 32; private readonly IEqualityComparer _comparer; private readonly int _hsize, _lsize, _limit; 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; /// Creates a LurchTable that can store up to (capacity) items efficiently. public LurchTable(int capacity) : this(LurchTableOrder.None, int.MaxValue, capacity >> 1, capacity >> 4, capacity >> 8, EqualityComparer.Default) { } /// Creates a LurchTable that can store up to (capacity) items efficiently. public LurchTable(int capacity, LurchTableOrder ordering) : this(ordering, int.MaxValue, capacity >> 1, capacity >> 4, capacity >> 8, EqualityComparer.Default) { } /// Creates a LurchTable that can store up to (capacity) items efficiently. public LurchTable(int capacity, LurchTableOrder ordering, IEqualityComparer comparer) : this(ordering, int.MaxValue, capacity >> 1, capacity >> 4, capacity >> 8, comparer) { } /// Creates a LurchTable that orders items by (ordering) and removes items once the specified (limit) is reached. public LurchTable(LurchTableOrder ordering, int limit) : this(ordering, limit, limit >> 1, limit >> 4, limit >> 8, EqualityComparer.Default) { } /// Creates a LurchTable that orders items by (ordering) and removes items once the specified (limit) is reached. public LurchTable(LurchTableOrder ordering, int limit, IEqualityComparer comparer) : this(ordering, limit, limit >> 1, limit >> 4, limit >> 8, comparer) { } /// /// Creates a LurchTable that orders items by (ordering) and removes items once the specified (limit) is reached. /// /// The type of linking for the items /// The maximum allowable number of items, or int.MaxValue for unlimited /// The number of hash buckets to use for the collection, usually 1/2 estimated capacity /// The number of entries to allocate at a time, usually 1/16 estimated capacity /// The number of concurrency locks to preallocate, usually 1/256 estimated capacity /// The element hash generator for keys public LurchTable(LurchTableOrder ordering, int limit, int hashSize, int allocSize, int lockSize, IEqualityComparer 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; _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 /// /// Clears references to all objects and invalidates the collection /// public void Dispose() { _entries = null; _used = _count = 0; } #endregion /// /// Gets the number of elements contained in the . /// public int Count { get { return _count; } } /// /// Retrieves the LurchTableOrder Ordering enumeration this instance was created with. /// public LurchTableOrder Ordering { get { return _ordering; } } /// /// Retrives the key comparer being used by this instance. /// public IEqualityComparer Comparer { get { return _comparer; } } /// /// Retrives the record limit allowed in this instance. /// public int Limit { get { return _limit; } } /// /// 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. /// 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 Members /// /// Removes all items from the . /// public void Clear() { if (_entries == null) throw new ObjectDisposedException(GetType().Name); foreach (var item in this) Remove(item.Key); } /// /// Determines whether the contains an element with the specified key. /// public bool ContainsKey(TKey key) { if (_entries == null) throw new ObjectDisposedException(GetType().Name); TValue value; return TryGetValue(key, out value); } /// /// Gets or sets the element with the specified key. /// public TValue this[TKey key] { set { var info = new AddInfo { Value = value, CanUpdate = true }; Insert(key, ref info); } get { TValue value; if (!TryGetValue(key, out value)) throw new ArgumentOutOfRangeException(); return value; } } /// /// Gets the value associated with the specified key. /// /// /// true if the object that implements contains an element with the specified key; otherwise, false. /// public bool TryGetValue(TKey key, out TValue value) { int hash = _comparer.GetHashCode(key) & int.MaxValue; return InternalGetValue(hash, key, out value); } /// /// Adds an element with the provided key and value to the . /// public void Add(TKey key, TValue value) { var info = new AddInfo { Value = value }; if (InsertResult.Inserted != Insert(key, ref info)) throw new ArgumentOutOfRangeException(); } /// /// Removes the element with the specified key from the . /// /// /// true if the element is successfully removed; otherwise, false. This method also returns false if was not found in the original . /// /// The key of the element to remove. public bool Remove(TKey key) { var del = new DelInfo(); return Delete(key, ref del); } #endregion #region IDictionaryEx Members /// /// Adds a key/value pair to the if the key does not already exist. /// /// The key of the element to add. /// The value to be added, if the key does not already exist. public TValue GetOrAdd(TKey key, TValue value) { var info = new AddInfo { Value = value, CanUpdate = false }; if (InsertResult.Exists == Insert(key, ref info)) return info.Value; return value; } /// /// Adds an element with the provided key and value to the . /// /// The object to use as the key of the element to add. /// The object to use as the value of the element to add. public bool TryAdd(TKey key, TValue value) { var info = new AddInfo { Value = value, CanUpdate = false }; return InsertResult.Inserted == Insert(key, ref info); } /// /// Updates an element with the provided key to the value if it exists. /// /// Returns true if the key provided was found and updated to the value. /// The object to use as the key of the element to update. /// The new value for the key if found. public bool TryUpdate(TKey key, TValue value) { var info = new UpdateInfo { Value = value }; return InsertResult.Updated == Insert(key, ref info); } /// /// Updates an element with the provided key to the value if it exists. /// /// Returns true if the key provided was found and updated to the value. /// The object to use as the key of the element to update. /// The new value for the key if found. /// The value that is compared to the value of the element with key. public bool TryUpdate(TKey key, TValue value, TValue comparisonValue) { var info = new UpdateInfo(comparisonValue) { Value = value }; return InsertResult.Updated == Insert(key, ref info); } /// /// Removes the element with the specified key from the . /// /// /// true if the element is successfully removed; otherwise, false. This method also returns false if was not found in the original . /// /// The key of the element to remove. /// The value that was removed. public bool TryRemove(TKey key, out TValue value) { var info = new DelInfo(); if (Delete(key, ref info)) { value = info.Value; return true; } value = default(TValue); return false; } #endregion #region IConcurrentDictionary Members /// /// Adds a key/value pair to the if the key does not already exist. /// /// The key of the element to add. /// Constructs a new value for the key. public TValue GetOrAdd(TKey key, Converter fnCreate) { var info = new Add2Info {Create = fnCreate}; Insert(key, ref info); return info.Value; } /// /// Adds a key/value pair to the if the key does not already exist, /// or updates a key/value pair if the key already exists. /// public TValue AddOrUpdate(TKey key, TValue addValue, KeyValueUpdate fnUpdate) { var info = new Add2Info(addValue) { Update = fnUpdate }; Insert(key, ref info); return info.Value; } /// /// Adds a key/value pair to the if the key does not already exist, /// or updates a key/value pair if the key already exists. /// /// /// 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. /// public TValue AddOrUpdate(TKey key, Converter fnCreate, KeyValueUpdate fnUpdate) { var info = new Add2Info { Create = fnCreate, Update = fnUpdate }; Insert(key, ref info); return info.Value; } /// /// Add, update, or fetche a key/value pair from the dictionary via an implementation of the /// interface. /// public bool AddOrUpdate(TKey key, ref T createOrUpdateValue) where T : ICreateOrUpdateValue { var result = Insert(key, ref createOrUpdateValue); return result == InsertResult.Inserted || result == InsertResult.Updated; } /// /// Adds an element with the provided key and value to the /// by calling the provided factory method to construct the value if the key is not already present in the collection. /// public bool TryAdd(TKey key, Converter fnCreate) { var info = new Add2Info { Create = fnCreate }; return InsertResult.Inserted == Insert(key, ref info); } /// /// 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. /// public bool TryUpdate(TKey key, KeyValueUpdate fnUpdate) { var info = new Add2Info { Update = fnUpdate }; return InsertResult.Updated == Insert(key, ref info); } /// /// Removes the element with the specified key from the /// if the fnCondition predicate is null or returns true. /// public bool TryRemove(TKey key, KeyValuePredicate fnCondition) { var info = new DelInfo {Condition = fnCondition}; return Delete(key, ref info); } /// /// Conditionally removes a key/value pair from the dictionary via an implementation of the /// interface. /// public bool TryRemove(TKey key, ref T removeValue) where T : IRemoveValue { return Delete(key, ref removeValue); } #endregion #region ICollection> Members bool ICollection>.IsReadOnly { get { return false; } } void ICollection>.Add(KeyValuePair item) { Add(item.Key, item.Value); } bool ICollection>.Contains(KeyValuePair item) { TValue test; if (TryGetValue(item.Key, out test)) return EqualityComparer.Default.Equals(item.Value, test); return false; } void ICollection>.CopyTo(KeyValuePair[] array, int arrayIndex) { foreach (var item in this) array[arrayIndex++] = item; } bool ICollection>.Remove(KeyValuePair item) { var del = new DelInfo(item.Value); return Delete(item.Key, ref del); } #endregion #region IEnumerator> 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; } /// /// Provides an enumerator that iterates through the collection. /// public struct Enumerator : IEnumerator> { private readonly LurchTable _owner; private EnumState _state; internal Enumerator(LurchTable owner) { _owner = owner; _state = new EnumState(); _state.Init(); } /// /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources. /// public void Dispose() { _state.Unlock(); } object IEnumerator.Current { get { return Current; } } /// /// Gets the element in the collection at the current position of the enumerator. /// public KeyValuePair Current { get { int index = _state.Current; if (index <= 0) throw new InvalidOperationException(); if (_owner._entries == null) throw new ObjectDisposedException(GetType().Name); return new KeyValuePair ( _owner._entries[index >> _owner._shift][index & _owner._shiftMask].Key, _owner._entries[index >> _owner._shift][index & _owner._shiftMask].Value ); } } /// /// Advances the enumerator to the next element of the collection. /// public bool MoveNext() { return _owner.MoveNext(ref _state); } /// /// Sets the enumerator to its initial position, which is before the first element in the collection. /// public void Reset() { _state.Unlock(); _state.Init(); } } /// /// Returns an enumerator that iterates through the collection. /// public Enumerator GetEnumerator() { return new Enumerator(this); } IEnumerator> IEnumerable>.GetEnumerator() { return GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } #endregion #region KeyCollection /// /// Provides the collection of Keys for the LurchTable /// public class KeyCollection : ICollection { private readonly LurchTable _owner; internal KeyCollection(LurchTable owner) { _owner = owner; } #region ICollection Members /// /// Determines whether the contains a specific value. /// public bool Contains(TKey item) { return _owner.ContainsKey(item); } /// /// Copies the elements of the to an , starting at a particular index. /// public void CopyTo(TKey[] array, int arrayIndex) { foreach (var item in _owner) array[arrayIndex++] = item.Key; } /// /// Gets the number of elements contained in the . /// public int Count { get { return _owner.Count; } } /// /// Returns an enumerator that iterates through the collection. /// public Enumerator GetEnumerator() { return new Enumerator(_owner); } /// /// Provides an enumerator that iterates through the collection. /// public struct Enumerator : IEnumerator { private readonly LurchTable _owner; private EnumState _state; internal Enumerator(LurchTable owner) { _owner = owner; _state = new EnumState(); _state.Init(); } /// /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources. /// public void Dispose() { _state.Unlock(); } object IEnumerator.Current { get { return Current; } } /// /// Gets the element in the collection at the current position of the enumerator. /// 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; } } /// /// Advances the enumerator to the next element of the collection. /// public bool MoveNext() { return _owner.MoveNext(ref _state); } /// /// Sets the enumerator to its initial position, which is before the first element in the collection. /// public void Reset() { _state.Unlock(); _state.Init(); } } [Obsolete] IEnumerator IEnumerable.GetEnumerator() { return new Enumerator(_owner); } [Obsolete] IEnumerator IEnumerable.GetEnumerator() { return new Enumerator(_owner); } [Obsolete] bool ICollection.IsReadOnly { get { return true; } } [Obsolete] void ICollection.Add(TKey item) { throw new NotSupportedException(); } [Obsolete] void ICollection.Clear() { throw new NotSupportedException(); } [Obsolete] bool ICollection.Remove(TKey item) { throw new NotSupportedException(); } #endregion } private KeyCollection _keyCollection; /// /// Gets an containing the keys of the . /// public KeyCollection Keys { get { return _keyCollection ?? (_keyCollection = new KeyCollection(this)); } } [Obsolete] ICollection IDictionary.Keys { get { return Keys; } } #endregion #region ValueCollection /// /// Provides the collection of Values for the LurchTable /// public class ValueCollection : ICollection { private readonly LurchTable _owner; internal ValueCollection(LurchTable owner) { _owner = owner; } #region ICollection Members /// /// Determines whether the contains a specific value. /// public bool Contains(TValue value) { var comparer = EqualityComparer.Default; foreach (var item in _owner) { if (comparer.Equals(item.Value, value)) return true; } return false; } /// /// Copies the elements of the to an , starting at a particular index. /// public void CopyTo(TValue[] array, int arrayIndex) { foreach (var item in _owner) array[arrayIndex++] = item.Value; } /// /// Gets the number of elements contained in the . /// public int Count { get { return _owner.Count; } } /// /// Returns an enumerator that iterates through the collection. /// public Enumerator GetEnumerator() { return new Enumerator(_owner); } /// /// Provides an enumerator that iterates through the collection. /// public struct Enumerator : IEnumerator { private readonly LurchTable _owner; private EnumState _state; internal Enumerator(LurchTable owner) { _owner = owner; _state = new EnumState(); _state.Init(); } /// /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources. /// public void Dispose() { _state.Unlock(); } object IEnumerator.Current { get { return Current; } } /// /// Gets the element in the collection at the current position of the enumerator. /// 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; } } /// /// Advances the enumerator to the next element of the collection. /// public bool MoveNext() { return _owner.MoveNext(ref _state); } /// /// Sets the enumerator to its initial position, which is before the first element in the collection. /// public void Reset() { _state.Unlock(); _state.Init(); } } [Obsolete] IEnumerator IEnumerable.GetEnumerator() { return new Enumerator(_owner); } [Obsolete] IEnumerator IEnumerable.GetEnumerator() { return new Enumerator(_owner); } [Obsolete] bool ICollection.IsReadOnly { get { return true; } } [Obsolete] void ICollection.Add(TValue item) { throw new NotSupportedException(); } [Obsolete] void ICollection.Clear() { throw new NotSupportedException(); } [Obsolete] bool ICollection.Remove(TValue item) { throw new NotSupportedException(); } #endregion } private ValueCollection _valueCollection; /// /// Gets an containing the values in the . /// public ValueCollection Values { get { return _valueCollection ?? (_valueCollection = new ValueCollection(this)); } } [Obsolete] ICollection IDictionary.Values { get { return Values; } } #endregion #region Peek/Dequeue /// /// Retrieves the oldest entry in the collection based on the ordering supplied to the constructor. /// /// True if the out parameter value was set. /// Raised if the table is unordered public bool Peek(out KeyValuePair 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); 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( _entries[index >> _shift][index & _shiftMask].Key, _entries[index >> _shift][index & _shiftMask].Value ); return true; } } } } } /// /// 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. /// /// The Key/Value pair removed. /// Raised if the table is unordered public KeyValuePair Dequeue() { if (_ordering == LurchTableOrder.None) throw new InvalidOperationException(); if (_entries == null) throw new ObjectDisposedException(GetType().Name); KeyValuePair value; while (!TryDequeue(out value)) { while (0 == Interlocked.CompareExchange(ref _entries[0][0].Prev, 0, 0)) Thread.Sleep(0); } return value; } /// /// Removes the oldest entry in the collection based on the ordering supplied to the constructor. /// /// False if no item was available /// Raised if the table is unordered public bool TryDequeue(out KeyValuePair value) { return TryDequeue(null, out value); } /// /// Removes the oldest entry in the collection based on the ordering supplied to the constructor. /// /// False if no item was available /// Raised if the table is unordered public bool TryDequeue(Predicate> predicate, out KeyValuePair 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); 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( _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( _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(TKey key, ref T value) where T : ICreateOrUpdateValue { 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 ignore; TryDequeue(out ignore); } return result; } InsertResult InternalInsert(int hash, TKey key, out int added, ref T value) where T : ICreateOrUpdateValue { 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(key, original), new KeyValuePair(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(key, temp)); return InsertResult.Inserted; } } added = -1; return InsertResult.NotFound; } bool Delete(TKey key, ref T value) where T : IRemoveValue { 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(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); } } struct DelInfo : IRemoveValue { public TValue Value; readonly bool _hasTestValue; readonly TValue _testValue; public KeyValuePredicate 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.Default.Equals(_testValue, value)) return false; if (Condition != null && !Condition(key, value)) return false; return true; } } struct AddInfo : ICreateOrUpdateValue { 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 : ICreateOrUpdateValue { readonly bool _hasAddValue; readonly TValue _addValue; public TValue Value; public Converter Create; public KeyValueUpdate 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 : ICreateOrUpdateValue { public TValue Value; readonly bool _hasTestValue; readonly TValue _testValue; public UpdateInfo(TValue expected) { Value = default(TValue); _testValue = expected; _hasTestValue = true; } bool ICreateValue.CreateValue(TKey key, out TValue value) { value = default(TValue); return false; } public bool UpdateValue(TKey key, ref TValue value) { if (_hasTestValue && !EqualityComparer.Default.Equals(_testValue, value)) return false; value = Value; return true; } } #endregion } }