diff options
author | Jiyoung Yun <jy910.yun@samsung.com> | 2017-02-10 20:35:12 +0900 |
---|---|---|
committer | Jiyoung Yun <jy910.yun@samsung.com> | 2017-02-10 20:35:12 +0900 |
commit | 4b11dc566a5bbfa1378d6266525c281b028abcc8 (patch) | |
tree | b48831a898906734f8884d08b6e18f1144ee2b82 /src/mscorlib/src/System/Collections | |
parent | db20f3f1bb8595633a7e16c8900fd401a453a6b5 (diff) | |
download | coreclr-4b11dc566a5bbfa1378d6266525c281b028abcc8.tar.gz coreclr-4b11dc566a5bbfa1378d6266525c281b028abcc8.tar.bz2 coreclr-4b11dc566a5bbfa1378d6266525c281b028abcc8.zip |
Imported Upstream version 1.0.0.9910upstream/1.0.0.9910
Diffstat (limited to 'src/mscorlib/src/System/Collections')
35 files changed, 857 insertions, 7538 deletions
diff --git a/src/mscorlib/src/System/Collections/ArrayList.cs b/src/mscorlib/src/System/Collections/ArrayList.cs index e7f121370b..53746e224e 100644 --- a/src/mscorlib/src/System/Collections/ArrayList.cs +++ b/src/mscorlib/src/System/Collections/ArrayList.cs @@ -18,7 +18,6 @@ namespace System.Collections { using System; using System.Runtime; using System.Security; - using System.Security.Permissions; using System.Diagnostics; using System.Runtime.CompilerServices; using System.Runtime.Serialization; @@ -35,8 +34,7 @@ namespace System.Collections { [DebuggerTypeProxy(typeof(System.Collections.ArrayList.ArrayListDebugView))] [DebuggerDisplay("Count = {Count}")] [Serializable] - [System.Runtime.InteropServices.ComVisible(true)] - public class ArrayList : IList, ICloneable + internal class ArrayList : IList, ICloneable { private Object[] _items; [ContractPublicPropertyName("Count")] @@ -47,12 +45,6 @@ namespace System.Collections { private const int _defaultCapacity = 4; private static readonly Object[] emptyArray = EmptyArray<Object>.Value; - - // Note: this constructor is a bogus constructor that does nothing - // and is for use only with SyncArrayList. - internal ArrayList( bool trash ) - { - } // Constructs a ArrayList. The list is initially empty and has a capacity // of zero. Upon adding the first element to the list the capacity is @@ -175,22 +167,6 @@ namespace System.Collections { _version++; } } - - // Creates a ArrayList wrapper for a particular IList. This does not - // copy the contents of the IList, but only wraps the ILIst. So any - // changes to the underlying list will affect the ArrayList. This would - // be useful if you want to Reverse a subrange of an IList, or want to - // use a generic BinarySearch or Sort method without implementing one yourself. - // However, since these methods are generic, the performance may not be - // nearly as good for some operations as they would be on the IList itself. - // - public static ArrayList Adapter(IList list) { - if (list==null) - throw new ArgumentNullException(nameof(list)); - Contract.Ensures(Contract.Result<ArrayList>() != null); - Contract.EndContractBlock(); - return new IListWrapper(list); - } // Adds the given object to the end of this list. The size of the list is // increased by one. If required, the capacity of the list is doubled @@ -211,52 +187,6 @@ namespace System.Collections { public virtual void AddRange(ICollection c) { InsertRange(_size, c); } - - // Searches a section of the list for a given element using a binary search - // algorithm. Elements of the list are compared to the search value using - // the given IComparer interface. If comparer is null, elements of - // the list are compared to the search value using the IComparable - // interface, which in that case must be implemented by all elements of the - // list and the given search value. This method assumes that the given - // section of the list is already sorted; if this is not the case, the - // result will be incorrect. - // - // The method returns the index of the given value in the list. If the - // list does not contain the given value, the method returns a negative - // integer. The bitwise complement operator (~) can be applied to a - // negative result to produce the index of the first element (if any) that - // is larger than the given search value. This is also the index at which - // the search value should be inserted into the list in order for the list - // to remain sorted. - // - // The method uses the Array.BinarySearch method to perform the - // search. - // - public virtual int BinarySearch(int index, int count, Object value, IComparer comparer) { - if (index < 0) - throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (count < 0) - throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_size - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.Ensures(Contract.Result<int>() < Count); - Contract.Ensures(Contract.Result<int>() < index + count); - Contract.EndContractBlock(); - - return Array.BinarySearch((Array)_items, index, count, value, comparer); - } - - public virtual int BinarySearch(Object value) - { - Contract.Ensures(Contract.Result<int>() < Count); - return BinarySearch(0, Count, value, null); - } - - public virtual int BinarySearch(Object value, IComparer comparer) - { - Contract.Ensures(Contract.Result<int>() < Count); - return BinarySearch(0, Count, value, comparer); - } // Clears the contents of ArrayList. @@ -301,13 +231,6 @@ namespace System.Collections { return false; } } - - // Copies this ArrayList into array, which must be of a - // compatible array type. - // - public virtual void CopyTo(Array array) { - CopyTo(array, 0); - } // Copies this ArrayList into array, which must be of a // compatible array type. @@ -319,20 +242,6 @@ namespace System.Collections { // Delegate rest of error checking to Array.Copy. Array.Copy(_items, 0, array, arrayIndex, _size); } - - // Copies a section of this list to the given array at the given index. - // - // The method uses the Array.Copy method to copy the elements. - // - public virtual void CopyTo(int index, Array array, int arrayIndex, int count) { - if (_size - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - if ((array != null) && (array.Rank != 1)) - throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); - Contract.EndContractBlock(); - // Delegate rest of error checking to Array.Copy. - Array.Copy(_items, index, array, arrayIndex, count); - } // Ensures that the capacity of this list is at least the given minimum // value. If the currect capacity of the list is less than min, the @@ -349,28 +258,6 @@ namespace System.Collections { } } - // Returns a list wrapper that is fixed at the current size. Operations - // that add or remove items will fail, however, replacing items is allowed. - // - public static IList FixedSize(IList list) { - if (list==null) - throw new ArgumentNullException(nameof(list)); - Contract.Ensures(Contract.Result<IList>() != null); - Contract.EndContractBlock(); - return new FixedSizeList(list); - } - - // Returns a list wrapper that is fixed at the current size. Operations - // that add or remove items will fail, however, replacing items is allowed. - // - public static ArrayList FixedSize(ArrayList list) { - if (list==null) - throw new ArgumentNullException(nameof(list)); - Contract.Ensures(Contract.Result<ArrayList>() != null); - Contract.EndContractBlock(); - return new FixedSizeArrayList(list); - } - // Returns an enumerator for this list with the given // permission for removal of elements. If modifications made to the list // while an enumeration is in progress, the MoveNext and @@ -381,24 +268,6 @@ namespace System.Collections { return new ArrayListEnumeratorSimple(this); } - // Returns an enumerator for a section of this list with the given - // permission for removal of elements. If modifications made to the list - // while an enumeration is in progress, the MoveNext and - // GetObject methods of the enumerator will throw an exception. - // - public virtual IEnumerator GetEnumerator(int index, int count) { - if (index < 0) - throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (count < 0) - throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_size - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.Ensures(Contract.Result<IEnumerator>() != null); - Contract.EndContractBlock(); - - return new ArrayListEnumerator(this, index, count); - } - // Returns the index of the first occurrence of a given value in a range of // this list. The list is searched forwards from beginning to end. // The elements of the list are compared to the given value using the @@ -412,41 +281,6 @@ namespace System.Collections { return Array.IndexOf((Array)_items, value, 0, _size); } - // Returns the index of the first occurrence of a given value in a range of - // this list. The list is searched forwards, starting at index - // startIndex and ending at count number of elements. The - // elements of the list are compared to the given value using the - // Object.Equals method. - // - // This method uses the Array.IndexOf method to perform the - // search. - // - public virtual int IndexOf(Object value, int startIndex) { - if (startIndex > _size) - throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_Index")); - Contract.Ensures(Contract.Result<int>() < Count); - Contract.EndContractBlock(); - return Array.IndexOf((Array)_items, value, startIndex, _size - startIndex); - } - - // Returns the index of the first occurrence of a given value in a range of - // this list. The list is searched forwards, starting at index - // startIndex and upto count number of elements. The - // elements of the list are compared to the given value using the - // Object.Equals method. - // - // This method uses the Array.IndexOf method to perform the - // search. - // - public virtual int IndexOf(Object value, int startIndex, int count) { - if (startIndex > _size) - throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_Index")); - if (count <0 || startIndex > _size - count) throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_Count")); - Contract.Ensures(Contract.Result<int>() < Count); - Contract.EndContractBlock(); - return Array.IndexOf((Array)_items, value, startIndex, count); - } - // Inserts an element into this list at a given index. The size of the list // is increased by one. If required, the capacity of the list is doubled // before inserting the new element. @@ -494,62 +328,6 @@ namespace System.Collections { } } - // Returns the index of the last occurrence of a given value in a range of - // this list. The list is searched backwards, starting at the end - // and ending at the first element in the list. The elements of the list - // are compared to the given value using the Object.Equals method. - // - // This method uses the Array.LastIndexOf method to perform the - // search. - // - public virtual int LastIndexOf(Object value) - { - Contract.Ensures(Contract.Result<int>() < _size); - return LastIndexOf(value, _size - 1, _size); - } - - // Returns the index of the last occurrence of a given value in a range of - // this list. The list is searched backwards, starting at index - // startIndex and ending at the first element in the list. The - // elements of the list are compared to the given value using the - // Object.Equals method. - // - // This method uses the Array.LastIndexOf method to perform the - // search. - // - public virtual int LastIndexOf(Object value, int startIndex) - { - if (startIndex >= _size) - throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_Index")); - Contract.Ensures(Contract.Result<int>() < Count); - Contract.EndContractBlock(); - return LastIndexOf(value, startIndex, startIndex + 1); - } - - // Returns the index of the last occurrence of a given value in a range of - // this list. The list is searched backwards, starting at index - // startIndex and upto count elements. The elements of - // the list are compared to the given value using the Object.Equals - // method. - // - // This method uses the Array.LastIndexOf method to perform the - // search. - // - public virtual int LastIndexOf(Object value, int startIndex, int count) { - if (Count != 0 && (startIndex < 0 || count < 0)) - throw new ArgumentOutOfRangeException((startIndex<0 ? nameof(startIndex) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - Contract.Ensures(Contract.Result<int>() < Count); - Contract.EndContractBlock(); - - if (_size == 0) // Special case for an empty list - return -1; - - if (startIndex >= _size || count > startIndex + 1) - throw new ArgumentOutOfRangeException((startIndex>=_size ? nameof(startIndex) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_BiggerThanCollection")); - - return Array.LastIndexOf((Array)_items, value, startIndex, count); - } - // Returns a read-only IList wrapper for the given IList. // [FriendAccessAllowed] @@ -560,16 +338,6 @@ namespace System.Collections { Contract.EndContractBlock(); return new ReadOnlyList(list); } - - // Returns a read-only ArrayList wrapper for the given ArrayList. - // - public static ArrayList ReadOnly(ArrayList list) { - if (list==null) - throw new ArgumentNullException(nameof(list)); - Contract.Ensures(Contract.Result<ArrayList>() != null); - Contract.EndContractBlock(); - return new ReadOnlyArrayList(list); - } // Removes the element at the given index. The size of the list is // decreased by one. @@ -600,159 +368,6 @@ namespace System.Collections { _version++; } - // Removes a range of elements from this list. - // - public virtual void RemoveRange(int index, int count) { - if (index < 0) - throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (count < 0) - throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_size - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.Ensures(Count >= 0); - //Contract.Ensures(Count == Contract.OldValue(Count) - count); - Contract.EndContractBlock(); - - if (count > 0) { - int i = _size; - _size -= count; - if (index < _size) { - Array.Copy(_items, index + count, _items, index, _size - index); - } - while (i > _size) _items[--i] = null; - _version++; - } - } - - // Returns an IList that contains count copies of value. - // - public static ArrayList Repeat(Object value, int count) { - if (count < 0) - throw new ArgumentOutOfRangeException(nameof(count),Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - Contract.Ensures(Contract.Result<ArrayList>() != null); - Contract.EndContractBlock(); - - ArrayList list = new ArrayList((count>_defaultCapacity)?count:_defaultCapacity); - for(int i=0; i<count; i++) - list.Add(value); - return list; - } - - // Reverses the elements in this list. - public virtual void Reverse() { - Reverse(0, Count); - } - - // Reverses the elements in a range of this list. Following a call to this - // method, an element in the range given by index and count - // which was previously located at index i will now be located at - // index index + (index + count - i - 1). - // - // This method uses the Array.Reverse method to reverse the - // elements. - // - public virtual void Reverse(int index, int count) { - if (index < 0) - throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (count < 0) - throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_size - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - Array.Reverse(_items, index, count); - _version++; - } - - // Sets the elements starting at the given index to the elements of the - // given collection. - // - public virtual void SetRange(int index, ICollection c) { - if (c==null) throw new ArgumentNullException(nameof(c), Environment.GetResourceString("ArgumentNull_Collection")); - Contract.EndContractBlock(); - int count = c.Count; - if (index < 0 || index > _size - count) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - - if (count > 0) { - c.CopyTo(_items, index); - _version++; - } - } - - public virtual ArrayList GetRange(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_size - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.Ensures(Contract.Result<ArrayList>() != null); - Contract.EndContractBlock(); - return new Range(this,index, count); - } - - // Sorts the elements in this list. Uses the default comparer and - // Array.Sort. - public virtual void Sort() - { - Sort(0, Count, Comparer.Default); - } - - // Sorts the elements in this list. Uses Array.Sort with the - // provided comparer. - public virtual void Sort(IComparer comparer) - { - Sort(0, Count, comparer); - } - - // Sorts the elements in a section of this list. The sort compares the - // elements to each other using the given IComparer interface. If - // comparer is null, the elements are compared to each other using - // the IComparable interface, which in that case must be implemented by all - // elements of the list. - // - // This method uses the Array.Sort method to sort the elements. - // - public virtual void Sort(int index, int count, IComparer comparer) { - if (index < 0) - throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (count < 0) - throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_size - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - Array.Sort(_items, index, count, comparer); - _version++; - } - - // Returns a thread-safe wrapper around an IList. - // - public static IList Synchronized(IList list) { - if (list==null) - throw new ArgumentNullException(nameof(list)); - Contract.Ensures(Contract.Result<IList>() != null); - Contract.EndContractBlock(); - return new SyncIList(list); - } - - // Returns a thread-safe wrapper around a ArrayList. - // - public static ArrayList Synchronized(ArrayList list) { - if (list==null) - throw new ArgumentNullException(nameof(list)); - Contract.Ensures(Contract.Result<ArrayList>() != null); - Contract.EndContractBlock(); - return new SyncArrayList(list); - } - - // ToArray returns a new Object array containing the contents of the ArrayList. - // This requires copying the ArrayList, which is an O(n) operation. - public virtual Object[] ToArray() { - Contract.Ensures(Contract.Result<Object[]>() != null); - - Object[] array = new Object[_size]; - Array.Copy(_items, 0, array, 0, _size); - return array; - } - // ToArray returns a new array of a particular type containing the contents // of the ArrayList. This requires copying the ArrayList and potentially // downcasting all elements. This copy may fail and is an O(n) operation. @@ -768,1070 +383,6 @@ namespace System.Collections { return array; } - // Sets the capacity of this list to the size of the list. This method can - // be used to minimize a list's memory overhead once it is known that no - // new elements will be added to the list. To completely clear a list and - // release all memory referenced by the list, execute the following - // statements: - // - // list.Clear(); - // list.TrimToSize(); - // - public virtual void TrimToSize() { - Capacity = _size; - } - - - // This class wraps an IList, exposing it as a ArrayList - // Note this requires reimplementing half of ArrayList... - [Serializable] - private class IListWrapper : ArrayList - { - private IList _list; - - internal IListWrapper(IList list) { - _list = list; - _version = 0; // list doesn't not contain a version number - } - - public override int Capacity { - get { return _list.Count; } - set { - if (value < Count) throw new ArgumentOutOfRangeException(nameof(value), Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity")); - Contract.EndContractBlock(); - } - } - - public override int Count { - get { return _list.Count; } - } - - public override bool IsReadOnly { - get { return _list.IsReadOnly; } - } - - public override bool IsFixedSize { - get { return _list.IsFixedSize; } - } - - - public override bool IsSynchronized { - get { return _list.IsSynchronized; } - } - - public override Object this[int index] { - get { - return _list[index]; - } - set { - _list[index] = value; - _version++; - } - } - - public override Object SyncRoot { - get { return _list.SyncRoot; } - } - - public override int Add(Object obj) { - int i = _list.Add(obj); - _version++; - return i; - } - - public override void AddRange(ICollection c) { - InsertRange(Count, c); - } - - // Other overloads with automatically work - public override int BinarySearch(int index, int count, Object value, IComparer comparer) - { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (this.Count - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - if (comparer == null) - comparer = Comparer.Default; - - int lo = index; - int hi = index + count - 1; - int mid; - while (lo <= hi) { - mid = (lo+hi)/2; - int r = comparer.Compare(value, _list[mid]); - if (r == 0) - return mid; - if (r < 0) - hi = mid-1; - else - lo = mid+1; - } - // return bitwise complement of the first element greater than value. - // Since hi is less than lo now, ~lo is the correct item. - return ~lo; - } - - public override void Clear() { - // If _list is an array, it will support Clear method. - // We shouldn't allow clear operation on a FixedSized ArrayList - if(_list.IsFixedSize) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - _list.Clear(); - _version++; - } - - public override Object Clone() { - // This does not do a shallow copy of _list into a ArrayList! - // This clones the IListWrapper, creating another wrapper class! - return new IListWrapper(_list); - } - - public override bool Contains(Object obj) { - return _list.Contains(obj); - } - - public override void CopyTo(Array array, int index) { - _list.CopyTo(array, index); - } - - public override void CopyTo(int index, Array array, int arrayIndex, int count) { - if (array==null) - throw new ArgumentNullException(nameof(array)); - if (index < 0 || arrayIndex < 0) - throw new ArgumentOutOfRangeException((index < 0) ? nameof(index) : nameof(arrayIndex), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if( count < 0) - throw new ArgumentOutOfRangeException( nameof(count) , Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (array.Length - arrayIndex < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - if (array.Rank != 1) - throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); - Contract.EndContractBlock(); - - if (_list.Count - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - - for(int i=index; i<index+count; i++) - array.SetValue(_list[i], arrayIndex++); - } - - public override IEnumerator GetEnumerator() { - return _list.GetEnumerator(); - } - - public override IEnumerator GetEnumerator(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - Contract.EndContractBlock(); - if (_list.Count - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - - return new IListWrapperEnumWrapper(this, index, count); - } - - public override int IndexOf(Object value) { - return _list.IndexOf(value); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int IndexOf(Object value, int startIndex) { - return IndexOf(value, startIndex, _list.Count - startIndex); - } - - public override int IndexOf(Object value, int startIndex, int count) { - if (startIndex < 0 || startIndex > this.Count) throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_Index")); - if (count < 0 || startIndex > this.Count - count) throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_Count")); - Contract.EndContractBlock(); - - int endIndex = startIndex + count; - if (value == null) { - for(int i=startIndex; i<endIndex; i++) - if (_list[i] == null) - return i; - return -1; - } else { - for(int i=startIndex; i<endIndex; i++) - if (_list[i] != null && _list[i].Equals(value)) - return i; - return -1; - } - } - - public override void Insert(int index, Object obj) { - _list.Insert(index, obj); - _version++; - } - - public override void InsertRange(int index, ICollection c) { - if (c==null) - throw new ArgumentNullException(nameof(c), Environment.GetResourceString("ArgumentNull_Collection")); - if (index < 0 || index > this.Count) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - Contract.EndContractBlock(); - - if( c.Count > 0) { - ArrayList al = _list as ArrayList; - if( al != null) { - // We need to special case ArrayList. - // When c is a range of _list, we need to handle this in a special way. - // See ArrayList.InsertRange for details. - al.InsertRange(index, c); - } - else { - IEnumerator en = c.GetEnumerator(); - while(en.MoveNext()) { - _list.Insert(index++, en.Current); - } - } - _version++; - } - } - - public override int LastIndexOf(Object value) { - return LastIndexOf(value,_list.Count - 1, _list.Count); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int LastIndexOf(Object value, int startIndex) { - return LastIndexOf(value, startIndex, startIndex + 1); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int LastIndexOf(Object value, int startIndex, int count) { - if (_list.Count == 0) - return -1; - - if (startIndex < 0 || startIndex >= _list.Count) throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_Index")); - if (count < 0 || count > startIndex + 1) throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_Count")); - - int endIndex = startIndex - count + 1; - if (value == null) { - for(int i=startIndex; i >= endIndex; i--) - if (_list[i] == null) - return i; - return -1; - } else { - for(int i=startIndex; i >= endIndex; i--) - if (_list[i] != null && _list[i].Equals(value)) - return i; - return -1; - } - } - - public override void Remove(Object value) { - int index = IndexOf(value); - if (index >=0) - RemoveAt(index); - } - - public override void RemoveAt(int index) { - _list.RemoveAt(index); - _version++; - } - - public override void RemoveRange(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - Contract.EndContractBlock(); - if (_list.Count - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - - if( count > 0) // be consistent with ArrayList - _version++; - - while(count > 0) { - _list.RemoveAt(index); - count--; - } - } - - public override void Reverse(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - Contract.EndContractBlock(); - if (_list.Count - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - - int i = index; - int j = index + count - 1; - while (i < j) - { - Object tmp = _list[i]; - _list[i++] = _list[j]; - _list[j--] = tmp; - } - _version++; - } - - public override void SetRange(int index, ICollection c) { - if (c==null) { - throw new ArgumentNullException(nameof(c), Environment.GetResourceString("ArgumentNull_Collection")); - } - Contract.EndContractBlock(); - - if (index < 0 || index > _list.Count - c.Count) { - throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - } - - if( c.Count > 0) { - IEnumerator en = c.GetEnumerator(); - while(en.MoveNext()) { - _list[index++] = en.Current; - } - _version++; - } - } - - public override ArrayList GetRange(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - Contract.EndContractBlock(); - if (_list.Count - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - return new Range(this,index, count); - } - - public override void Sort(int index, int count, IComparer comparer) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - Contract.EndContractBlock(); - if (_list.Count - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - - Object [] array = new Object[count]; - CopyTo(index, array, 0, count); - Array.Sort(array, 0, count, comparer); - for(int i=0; i<count; i++) - _list[i+index] = array[i]; - - _version++; - } - - - public override Object[] ToArray() { - Object[] array = new Object[Count]; - _list.CopyTo(array, 0); - return array; - } - - public override Array ToArray(Type type) - { - if (type==null) - throw new ArgumentNullException(nameof(type)); - Contract.EndContractBlock(); - Array array = Array.UnsafeCreateInstance(type, _list.Count); - _list.CopyTo(array, 0); - return array; - } - - public override void TrimToSize() - { - // Can't really do much here... - } - - // This is the enumerator for an IList that's been wrapped in another - // class that implements all of ArrayList's methods. - [Serializable] - private sealed class IListWrapperEnumWrapper : IEnumerator, ICloneable - { - private IEnumerator _en; - private int _remaining; - private int _initialStartIndex; // for reset - private int _initialCount; // for reset - private bool _firstCall; // firstCall to MoveNext - - private IListWrapperEnumWrapper() - { - } - - internal IListWrapperEnumWrapper(IListWrapper listWrapper, int startIndex, int count) - { - _en = listWrapper.GetEnumerator(); - _initialStartIndex = startIndex; - _initialCount = count; - while(startIndex-- > 0 && _en.MoveNext()); - _remaining = count; - _firstCall = true; - } - - public Object Clone() { - // We must clone the underlying enumerator, I think. - IListWrapperEnumWrapper clone = new IListWrapperEnumWrapper(); - clone._en = (IEnumerator) ((ICloneable)_en).Clone(); - clone._initialStartIndex = _initialStartIndex; - clone._initialCount = _initialCount; - clone._remaining = _remaining; - clone._firstCall = _firstCall; - return clone; - } - - public bool MoveNext() { - if (_firstCall) { - _firstCall = false; - return _remaining-- > 0 && _en.MoveNext(); - } - if (_remaining < 0) - return false; - bool r = _en.MoveNext(); - return r && _remaining-- > 0; - } - - public Object Current { - get { - if (_firstCall) - throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted)); - if (_remaining < 0) - throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded)); - return _en.Current; - } - } - - public void Reset() { - _en.Reset(); - int startIndex = _initialStartIndex; - while(startIndex-- > 0 && _en.MoveNext()); - _remaining = _initialCount; - _firstCall = true; - } - } - } - - - [Serializable] - private class SyncArrayList : ArrayList - { - private ArrayList _list; - private Object _root; - - internal SyncArrayList(ArrayList list) - : base( false ) - { - _list = list; - _root = list.SyncRoot; - } - - public override int Capacity { - get { - lock(_root) { - return _list.Capacity; - } - } - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - set { - lock(_root) { - _list.Capacity = value; - } - } - } - - public override int Count { - get { lock(_root) { return _list.Count; } } - } - - public override bool IsReadOnly { - get { return _list.IsReadOnly; } - } - - public override bool IsFixedSize { - get { return _list.IsFixedSize; } - } - - - public override bool IsSynchronized { - get { return true; } - } - - public override Object this[int index] { - get { - lock(_root) { - return _list[index]; - } - } - set { - lock(_root) { - _list[index] = value; - } - } - } - - public override Object SyncRoot { - get { return _root; } - } - - public override int Add(Object value) { - lock(_root) { - return _list.Add(value); - } - } - - public override void AddRange(ICollection c) { - lock(_root) { - _list.AddRange(c); - } - } - - public override int BinarySearch(Object value) { - lock(_root) { - return _list.BinarySearch(value); - } - } - - public override int BinarySearch(Object value, IComparer comparer) { - lock(_root) { - return _list.BinarySearch(value, comparer); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int BinarySearch(int index, int count, Object value, IComparer comparer) { - lock(_root) { - return _list.BinarySearch(index, count, value, comparer); - } - } - - public override void Clear() { - lock(_root) { - _list.Clear(); - } - } - - public override Object Clone() { - lock(_root) { - return new SyncArrayList((ArrayList)_list.Clone()); - } - } - - public override bool Contains(Object item) { - lock(_root) { - return _list.Contains(item); - } - } - - public override void CopyTo(Array array) { - lock(_root) { - _list.CopyTo(array); - } - } - - public override void CopyTo(Array array, int index) { - lock(_root) { - _list.CopyTo(array, index); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void CopyTo(int index, Array array, int arrayIndex, int count) { - lock(_root) { - _list.CopyTo(index, array, arrayIndex, count); - } - } - - public override IEnumerator GetEnumerator() { - lock(_root) { - return _list.GetEnumerator(); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override IEnumerator GetEnumerator(int index, int count) { - lock(_root) { - return _list.GetEnumerator(index, count); - } - } - - public override int IndexOf(Object value) { - lock(_root) { - return _list.IndexOf(value); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int IndexOf(Object value, int startIndex) { - lock(_root) { - return _list.IndexOf(value, startIndex); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int IndexOf(Object value, int startIndex, int count) { - lock(_root) { - return _list.IndexOf(value, startIndex, count); - } - } - - public override void Insert(int index, Object value) { - lock(_root) { - _list.Insert(index, value); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void InsertRange(int index, ICollection c) { - lock(_root) { - _list.InsertRange(index, c); - } - } - - public override int LastIndexOf(Object value) { - lock(_root) { - return _list.LastIndexOf(value); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int LastIndexOf(Object value, int startIndex) { - lock(_root) { - return _list.LastIndexOf(value, startIndex); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int LastIndexOf(Object value, int startIndex, int count) { - lock(_root) { - return _list.LastIndexOf(value, startIndex, count); - } - } - - public override void Remove(Object value) { - lock(_root) { - _list.Remove(value); - } - } - - public override void RemoveAt(int index) { - lock(_root) { - _list.RemoveAt(index); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void RemoveRange(int index, int count) { - lock(_root) { - _list.RemoveRange(index, count); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void Reverse(int index, int count) { - lock(_root) { - _list.Reverse(index, count); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void SetRange(int index, ICollection c) { - lock(_root) { - _list.SetRange(index, c); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override ArrayList GetRange(int index, int count) { - lock(_root) { - return _list.GetRange(index, count); - } - } - - public override void Sort() { - lock(_root) { - _list.Sort(); - } - } - - public override void Sort(IComparer comparer) { - lock(_root) { - _list.Sort(comparer); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void Sort(int index, int count, IComparer comparer) { - lock(_root) { - _list.Sort(index, count, comparer); - } - } - - public override Object[] ToArray() { - lock(_root) { - return _list.ToArray(); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override Array ToArray(Type type) { - lock(_root) { - return _list.ToArray(type); - } - } - - public override void TrimToSize() { - lock(_root) { - _list.TrimToSize(); - } - } - } - - - [Serializable] - private class SyncIList : IList - { - private IList _list; - private Object _root; - - internal SyncIList(IList list) { - _list = list; - _root = list.SyncRoot; - } - - public virtual int Count { - get { lock(_root) { return _list.Count; } } - } - - public virtual bool IsReadOnly { - get { return _list.IsReadOnly; } - } - - public virtual bool IsFixedSize { - get { return _list.IsFixedSize; } - } - - - public virtual bool IsSynchronized { - get { return true; } - } - - public virtual Object this[int index] { - get { - lock(_root) { - return _list[index]; - } - } - set { - lock(_root) { - _list[index] = value; - } - } - } - - public virtual Object SyncRoot { - get { return _root; } - } - - public virtual int Add(Object value) { - lock(_root) { - return _list.Add(value); - } - } - - - public virtual void Clear() { - lock(_root) { - _list.Clear(); - } - } - - public virtual bool Contains(Object item) { - lock(_root) { - return _list.Contains(item); - } - } - - public virtual void CopyTo(Array array, int index) { - lock(_root) { - _list.CopyTo(array, index); - } - } - - public virtual IEnumerator GetEnumerator() { - lock(_root) { - return _list.GetEnumerator(); - } - } - - public virtual int IndexOf(Object value) { - lock(_root) { - return _list.IndexOf(value); - } - } - - public virtual void Insert(int index, Object value) { - lock(_root) { - _list.Insert(index, value); - } - } - - public virtual void Remove(Object value) { - lock(_root) { - _list.Remove(value); - } - } - - public virtual void RemoveAt(int index) { - lock(_root) { - _list.RemoveAt(index); - } - } - } - - [Serializable] - private class FixedSizeList : IList - { - private IList _list; - - internal FixedSizeList(IList l) { - _list = l; - } - - public virtual int Count { - get { return _list.Count; } - } - - public virtual bool IsReadOnly { - get { return _list.IsReadOnly; } - } - - public virtual bool IsFixedSize { - get { return true; } - } - - public virtual bool IsSynchronized { - get { return _list.IsSynchronized; } - } - - public virtual Object this[int index] { - get { - return _list[index]; - } - set { - _list[index] = value; - } - } - - public virtual Object SyncRoot { - get { return _list.SyncRoot; } - } - - public virtual int Add(Object obj) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - public virtual void Clear() { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - public virtual bool Contains(Object obj) { - return _list.Contains(obj); - } - - public virtual void CopyTo(Array array, int index) { - _list.CopyTo(array, index); - } - - public virtual IEnumerator GetEnumerator() { - return _list.GetEnumerator(); - } - - public virtual int IndexOf(Object value) { - return _list.IndexOf(value); - } - - public virtual void Insert(int index, Object obj) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - public virtual void Remove(Object value) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - public virtual void RemoveAt(int index) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - } - - [Serializable] - private class FixedSizeArrayList : ArrayList - { - private ArrayList _list; - - internal FixedSizeArrayList(ArrayList l) { - _list = l; - _version = _list._version; - } - - public override int Count { - get { return _list.Count; } - } - - public override bool IsReadOnly { - get { return _list.IsReadOnly; } - } - - public override bool IsFixedSize { - get { return true; } - } - - public override bool IsSynchronized { - get { return _list.IsSynchronized; } - } - - public override Object this[int index] { - get { - return _list[index]; - } - set { - _list[index] = value; - _version = _list._version; - } - } - - public override Object SyncRoot { - get { return _list.SyncRoot; } - } - - public override int Add(Object obj) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - public override void AddRange(ICollection c) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int BinarySearch(int index, int count, Object value, IComparer comparer) { - return _list.BinarySearch(index, count, value, comparer); - } - - public override int Capacity { - get { return _list.Capacity; } - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - set { throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); } - } - - public override void Clear() { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - public override Object Clone() { - FixedSizeArrayList arrayList = new FixedSizeArrayList(_list); - arrayList._list = (ArrayList)_list.Clone(); - return arrayList; - } - - public override bool Contains(Object obj) { - return _list.Contains(obj); - } - - public override void CopyTo(Array array, int index) { - _list.CopyTo(array, index); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void CopyTo(int index, Array array, int arrayIndex, int count) { - _list.CopyTo(index, array, arrayIndex, count); - } - - public override IEnumerator GetEnumerator() { - return _list.GetEnumerator(); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override IEnumerator GetEnumerator(int index, int count) { - return _list.GetEnumerator(index, count); - } - - public override int IndexOf(Object value) { - return _list.IndexOf(value); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int IndexOf(Object value, int startIndex) { - return _list.IndexOf(value, startIndex); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int IndexOf(Object value, int startIndex, int count) { - return _list.IndexOf(value, startIndex, count); - } - - public override void Insert(int index, Object obj) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void InsertRange(int index, ICollection c) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - public override int LastIndexOf(Object value) { - return _list.LastIndexOf(value); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int LastIndexOf(Object value, int startIndex) { - return _list.LastIndexOf(value, startIndex); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int LastIndexOf(Object value, int startIndex, int count) { - return _list.LastIndexOf(value, startIndex, count); - } - - public override void Remove(Object value) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - public override void RemoveAt(int index) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void RemoveRange(int index, int count) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void SetRange(int index, ICollection c) { - _list.SetRange(index, c); - _version = _list._version; - } - - public override ArrayList GetRange(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (Count - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - return new Range(this,index, count); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void Reverse(int index, int count) { - _list.Reverse(index, count); - _version = _list._version; - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void Sort(int index, int count, IComparer comparer) { - _list.Sort(index, count, comparer); - _version = _list._version; - } - - public override Object[] ToArray() { - return _list.ToArray(); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override Array ToArray(Type type) { - return _list.ToArray(type); - } - - public override void TrimToSize() { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection")); - } - } - [Serializable] private class ReadOnlyList : IList { @@ -1908,626 +459,6 @@ namespace System.Collections { } [Serializable] - private class ReadOnlyArrayList : ArrayList - { - private ArrayList _list; - - internal ReadOnlyArrayList(ArrayList l) { - _list = l; - } - - public override int Count { - get { return _list.Count; } - } - - public override bool IsReadOnly { - get { return true; } - } - - public override bool IsFixedSize { - get { return true; } - } - - public override bool IsSynchronized { - get { return _list.IsSynchronized; } - } - - public override Object this[int index] { - get { - return _list[index]; - } - set { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - } - - public override Object SyncRoot { - get { return _list.SyncRoot; } - } - - public override int Add(Object obj) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - public override void AddRange(ICollection c) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int BinarySearch(int index, int count, Object value, IComparer comparer) { - return _list.BinarySearch(index, count, value, comparer); - } - - - public override int Capacity { - get { return _list.Capacity; } - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - set { throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); } - } - - public override void Clear() { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - public override Object Clone() { - ReadOnlyArrayList arrayList = new ReadOnlyArrayList(_list); - arrayList._list = (ArrayList)_list.Clone(); - return arrayList; - } - - public override bool Contains(Object obj) { - return _list.Contains(obj); - } - - public override void CopyTo(Array array, int index) { - _list.CopyTo(array, index); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void CopyTo(int index, Array array, int arrayIndex, int count) { - _list.CopyTo(index, array, arrayIndex, count); - } - - public override IEnumerator GetEnumerator() { - return _list.GetEnumerator(); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override IEnumerator GetEnumerator(int index, int count) { - return _list.GetEnumerator(index, count); - } - - public override int IndexOf(Object value) { - return _list.IndexOf(value); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int IndexOf(Object value, int startIndex) { - return _list.IndexOf(value, startIndex); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int IndexOf(Object value, int startIndex, int count) { - return _list.IndexOf(value, startIndex, count); - } - - public override void Insert(int index, Object obj) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void InsertRange(int index, ICollection c) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - public override int LastIndexOf(Object value) { - return _list.LastIndexOf(value); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int LastIndexOf(Object value, int startIndex) { - return _list.LastIndexOf(value, startIndex); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int LastIndexOf(Object value, int startIndex, int count) { - return _list.LastIndexOf(value, startIndex, count); - } - - public override void Remove(Object value) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - public override void RemoveAt(int index) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void RemoveRange(int index, int count) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void SetRange(int index, ICollection c) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - public override ArrayList GetRange(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (Count - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - return new Range(this,index, count); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void Reverse(int index, int count) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void Sort(int index, int count, IComparer comparer) { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - - public override Object[] ToArray() { - return _list.ToArray(); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override Array ToArray(Type type) { - return _list.ToArray(type); - } - - public override void TrimToSize() { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection")); - } - } - - - // Implements an enumerator for a ArrayList. The enumerator uses the - // internal version number of the list to ensure that no modifications are - // made to the list while an enumeration is in progress. - [Serializable] - private sealed class ArrayListEnumerator : IEnumerator, ICloneable - { - private ArrayList list; - private int index; - private int endIndex; // Where to stop. - private int version; - private Object currentElement; - private int startIndex; // Save this for Reset. - - internal ArrayListEnumerator(ArrayList list, int index, int count) { - this.list = list; - startIndex = index; - this.index = index - 1; - endIndex = this.index + count; // last valid index - version = list._version; - currentElement = null; - } - - public Object Clone() { - return MemberwiseClone(); - } - - public bool MoveNext() { - if (version != list._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); - if (index < endIndex) { - currentElement = list[++index]; - return true; - } - else { - index = endIndex + 1; - } - - return false; - } - - public Object Current { - get { - if (index < startIndex) - throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted)); - else if (index > endIndex) { - throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded)); - } - return currentElement; - } - } - - public void Reset() { - if (version != list._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); - index = startIndex - 1; - } - } - - // Implementation of a generic list subrange. An instance of this class - // is returned by the default implementation of List.GetRange. - [Serializable] - private class Range: ArrayList - { - private ArrayList _baseList; - private int _baseIndex; - [ContractPublicPropertyName("Count")] - private int _baseSize; - private int _baseVersion; - - internal Range(ArrayList list, int index, int count) : base(false) { - _baseList = list; - _baseIndex = index; - _baseSize = count; - _baseVersion = list._version; - // we also need to update _version field to make Range of Range work - _version = list._version; - } - - private void InternalUpdateRange() - { - if (_baseVersion != _baseList._version) - throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_UnderlyingArrayListChanged")); - } - - private void InternalUpdateVersion() { - _baseVersion++; - _version++; - } - - public override int Add(Object value) { - InternalUpdateRange(); - _baseList.Insert(_baseIndex + _baseSize, value); - InternalUpdateVersion(); - return _baseSize++; - } - - public override void AddRange(ICollection c) { - if( c == null ) { - throw new ArgumentNullException(nameof(c)); - } - Contract.EndContractBlock(); - - InternalUpdateRange(); - int count = c.Count; - if( count > 0) { - _baseList.InsertRange(_baseIndex + _baseSize, c); - InternalUpdateVersion(); - _baseSize += count; - } - } - - // Other overloads with automatically work - public override int BinarySearch(int index, int count, Object value, IComparer comparer) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_baseSize - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - InternalUpdateRange(); - - int i = _baseList.BinarySearch(_baseIndex + index, count, value, comparer); - if (i >= 0) return i - _baseIndex; - return i + _baseIndex; - } - - public override int Capacity { - get { - return _baseList.Capacity; - } - - set { - if (value < Count) throw new ArgumentOutOfRangeException(nameof(value), Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity")); - Contract.EndContractBlock(); - } - } - - - public override void Clear() { - InternalUpdateRange(); - if (_baseSize != 0) - { - _baseList.RemoveRange(_baseIndex, _baseSize); - InternalUpdateVersion(); - _baseSize = 0; - } - } - - public override Object Clone() { - InternalUpdateRange(); - Range arrayList = new Range(_baseList,_baseIndex,_baseSize); - arrayList._baseList = (ArrayList)_baseList.Clone(); - return arrayList; - } - - public override bool Contains(Object item) { - InternalUpdateRange(); - if (item==null) { - for(int i=0; i<_baseSize; i++) - if (_baseList[_baseIndex + i]==null) - return true; - return false; - } - else { - for(int i=0; i<_baseSize; i++) - if (_baseList[_baseIndex + i] != null && _baseList[_baseIndex + i].Equals(item)) - return true; - return false; - } - } - - public override void CopyTo(Array array, int index) { - if (array==null) - throw new ArgumentNullException(nameof(array)); - if (array.Rank != 1) - throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); - if (index < 0) - throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (array.Length - index < _baseSize) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - _baseList.CopyTo(_baseIndex, array, index, _baseSize); - } - - public override void CopyTo(int index, Array array, int arrayIndex, int count) { - if (array==null) - throw new ArgumentNullException(nameof(array)); - if (array.Rank != 1) - throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (array.Length - arrayIndex < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - if (_baseSize - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - _baseList.CopyTo(_baseIndex + index, array, arrayIndex, count); - } - - public override int Count { - get { - InternalUpdateRange(); - return _baseSize; - } - } - - public override bool IsReadOnly { - get { return _baseList.IsReadOnly; } - } - - public override bool IsFixedSize { - get { return _baseList.IsFixedSize; } - } - - public override bool IsSynchronized { - get { return _baseList.IsSynchronized; } - } - - public override IEnumerator GetEnumerator() { - return GetEnumerator(0,_baseSize); - } - - public override IEnumerator GetEnumerator(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_baseSize - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - return _baseList.GetEnumerator(_baseIndex + index, count); - } - - public override ArrayList GetRange(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_baseSize - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - return new Range(this, index, count); - } - - public override Object SyncRoot { - get { - return _baseList.SyncRoot; - } - } - - - public override int IndexOf(Object value) { - InternalUpdateRange(); - int i = _baseList.IndexOf(value, _baseIndex, _baseSize); - if (i >= 0) return i - _baseIndex; - return -1; - } - - public override int IndexOf(Object value, int startIndex) { - if (startIndex < 0) - throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (startIndex > _baseSize) - throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_Index")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - int i = _baseList.IndexOf(value, _baseIndex + startIndex, _baseSize - startIndex); - if (i >= 0) return i - _baseIndex; - return -1; - } - - public override int IndexOf(Object value, int startIndex, int count) { - if (startIndex < 0 || startIndex > _baseSize) - throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_Index")); - - if (count < 0 || (startIndex > _baseSize - count)) - throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_Count")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - int i = _baseList.IndexOf(value, _baseIndex + startIndex, count); - if (i >= 0) return i - _baseIndex; - return -1; - } - - public override void Insert(int index, Object value) { - if (index < 0 || index > _baseSize) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - _baseList.Insert(_baseIndex + index, value); - InternalUpdateVersion(); - _baseSize++; - } - - public override void InsertRange(int index, ICollection c) { - if (index < 0 || index > _baseSize) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - if( c == null) { - throw new ArgumentNullException(nameof(c)); - } - Contract.EndContractBlock(); - - InternalUpdateRange(); - int count = c.Count; - if( count > 0) { - _baseList.InsertRange(_baseIndex + index, c); - _baseSize += count; - InternalUpdateVersion(); - } - } - - public override int LastIndexOf(Object value) { - InternalUpdateRange(); - int i = _baseList.LastIndexOf(value, _baseIndex + _baseSize - 1, _baseSize); - if (i >= 0) return i - _baseIndex; - return -1; - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int LastIndexOf(Object value, int startIndex) { - return LastIndexOf(value, startIndex, startIndex + 1); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int LastIndexOf(Object value, int startIndex, int count) { - InternalUpdateRange(); - if (_baseSize == 0) - return -1; - - if (startIndex >= _baseSize) - throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_Index")); - if (startIndex < 0) - throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - - int i = _baseList.LastIndexOf(value, _baseIndex + startIndex, count); - if (i >= 0) return i - _baseIndex; - return -1; - } - - // Don't need to override Remove - - public override void RemoveAt(int index) { - if (index < 0 || index >= _baseSize) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - _baseList.RemoveAt(_baseIndex + index); - InternalUpdateVersion(); - _baseSize--; - } - - public override void RemoveRange(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_baseSize - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - // No need to call _bastList.RemoveRange if count is 0. - // In addition, _baseList won't change the vresion number if count is 0. - if( count > 0) { - _baseList.RemoveRange(_baseIndex + index, count); - InternalUpdateVersion(); - _baseSize -= count; - } - } - - public override void Reverse(int index, int count) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_baseSize - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - _baseList.Reverse(_baseIndex + index, count); - InternalUpdateVersion(); - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void SetRange(int index, ICollection c) { - InternalUpdateRange(); - if (index < 0 || index >= _baseSize) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - _baseList.SetRange(_baseIndex + index, c); - if( c.Count > 0) { - InternalUpdateVersion(); - } - } - - public override void Sort(int index, int count, IComparer comparer) { - if (index < 0 || count < 0) - throw new ArgumentOutOfRangeException((index<0 ? nameof(index) : nameof(count)), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (_baseSize - index < count) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - InternalUpdateRange(); - _baseList.Sort(_baseIndex + index, count, comparer); - InternalUpdateVersion(); - } - - public override Object this[int index] { - get { - InternalUpdateRange(); - if (index < 0 || index >= _baseSize) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - return _baseList[_baseIndex + index]; - } - set { - InternalUpdateRange(); - if (index < 0 || index >= _baseSize) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - _baseList[_baseIndex + index] = value; - InternalUpdateVersion(); - } - } - - public override Object[] ToArray() { - InternalUpdateRange(); - Object[] array = new Object[_baseSize]; - Array.Copy(_baseList._items, _baseIndex, array, 0, _baseSize); - return array; - } - - public override Array ToArray(Type type) { - if (type==null) - throw new ArgumentNullException(nameof(type)); - Contract.EndContractBlock(); - - InternalUpdateRange(); - Array array = Array.UnsafeCreateInstance(type, _baseSize); - _baseList.CopyTo(_baseIndex, array, 0, _baseSize); - return array; - } - - public override void TrimToSize() { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_RangeCollection")); - } - } - - [Serializable] private sealed class ArrayListEnumeratorSimple : IEnumerator, ICloneable { private ArrayList list; private int index; @@ -2607,20 +538,6 @@ namespace System.Collections { internal class ArrayListDebugView { private ArrayList arrayList; - - public ArrayListDebugView( ArrayList arrayList) { - if( arrayList == null) - throw new ArgumentNullException(nameof(arrayList)); - - this.arrayList = arrayList; - } - - [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] - public Object[] Items { - get { - return arrayList.ToArray(); - } - } } } } diff --git a/src/mscorlib/src/System/Collections/CollectionBase.cs b/src/mscorlib/src/System/Collections/CollectionBase.cs index ae0c0d302d..a3dd88a7b3 100644 --- a/src/mscorlib/src/System/Collections/CollectionBase.cs +++ b/src/mscorlib/src/System/Collections/CollectionBase.cs @@ -12,20 +12,14 @@ namespace System.Collections { // Useful base class for typed read/write collections where items derive from object [Serializable] -[System.Runtime.InteropServices.ComVisible(true)] public abstract class CollectionBase : IList { - ArrayList list; + private ArrayList list; protected CollectionBase() { list = new ArrayList(); } - - protected CollectionBase(int capacity) { - list = new ArrayList(capacity); - } - - protected ArrayList InnerList { + internal ArrayList InnerList { get { if (list == null) list = new ArrayList(); @@ -37,16 +31,6 @@ namespace System.Collections { get { return (IList)this; } } - [System.Runtime.InteropServices.ComVisible(false)] - public int Capacity { - get { - return InnerList.Capacity; - } - set { - InnerList.Capacity = value; - } - } - public int Count { get { diff --git a/src/mscorlib/src/System/Collections/Comparer.cs b/src/mscorlib/src/System/Collections/Comparer.cs index 0e3c78b529..928b0f9f9a 100644 --- a/src/mscorlib/src/System/Collections/Comparer.cs +++ b/src/mscorlib/src/System/Collections/Comparer.cs @@ -17,12 +17,10 @@ namespace System.Collections { using System; using System.Globalization; using System.Runtime.Serialization; - using System.Security.Permissions; using System.Diagnostics.Contracts; [Serializable] - [System.Runtime.InteropServices.ComVisible(true)] - public sealed class Comparer : IComparer , ISerializable + internal sealed class Comparer : IComparer , ISerializable { private CompareInfo m_compareInfo; public static readonly Comparer Default = new Comparer(CultureInfo.CurrentCulture); diff --git a/src/mscorlib/src/System/Collections/Concurrent/ConcurrentDictionary.cs b/src/mscorlib/src/System/Collections/Concurrent/ConcurrentDictionary.cs index c1a6f7564c..8b9014a103 100644 --- a/src/mscorlib/src/System/Collections/Concurrent/ConcurrentDictionary.cs +++ b/src/mscorlib/src/System/Collections/Concurrent/ConcurrentDictionary.cs @@ -24,7 +24,6 @@ using System.Runtime.Serialization; using System.Text; using System.Threading; using System.Security; -using System.Security.Permissions; namespace System.Collections.Concurrent { @@ -37,10 +36,9 @@ namespace System.Collections.Concurrent /// All public and protected members of <see cref="ConcurrentDictionary{TKey,TValue}"/> are thread-safe and may be used /// concurrently from multiple threads. /// </remarks> - [ComVisible(false)] [DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))] [DebuggerDisplay("Count = {Count}")] - public class ConcurrentDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue> + internal class ConcurrentDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue> { /// <summary> /// Tables that hold the internal state of the ConcurrentDictionary @@ -139,149 +137,6 @@ namespace System.Collections.Concurrent /// </summary> public ConcurrentDictionary() : this(DefaultConcurrencyLevel, DEFAULT_CAPACITY, true, EqualityComparer<TKey>.Default) { } - /// <summary> - /// Initializes a new instance of the <see - /// cref="ConcurrentDictionary{TKey,TValue}"/> - /// class that is empty, has the specified concurrency level and capacity, and uses the default - /// comparer for the key type. - /// </summary> - /// <param name="concurrencyLevel">The estimated number of threads that will update the - /// <see cref="ConcurrentDictionary{TKey,TValue}"/> concurrently.</param> - /// <param name="capacity">The initial number of elements that the <see - /// cref="ConcurrentDictionary{TKey,TValue}"/> - /// can contain.</param> - /// <exception cref="T:System.ArgumentOutOfRangeException"><paramref name="concurrencyLevel"/> is - /// less than 1.</exception> - /// <exception cref="T:System.ArgumentOutOfRangeException"> <paramref name="capacity"/> is less than - /// 0.</exception> - public ConcurrentDictionary(int concurrencyLevel, int capacity) : this(concurrencyLevel, capacity, false, EqualityComparer<TKey>.Default) { } - - /// <summary> - /// Initializes a new instance of the <see cref="ConcurrentDictionary{TKey,TValue}"/> - /// class that contains elements copied from the specified <see - /// cref="T:System.Collections.IEnumerable{KeyValuePair{TKey,TValue}}"/>, has the default concurrency - /// level, has the default initial capacity, and uses the default comparer for the key type. - /// </summary> - /// <param name="collection">The <see - /// cref="T:System.Collections.IEnumerable{KeyValuePair{TKey,TValue}}"/> whose elements are copied to - /// the new - /// <see cref="ConcurrentDictionary{TKey,TValue}"/>.</param> - /// <exception cref="T:System.ArgumentNullException"><paramref name="collection"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="T:System.ArgumentException"><paramref name="collection"/> contains one or more - /// duplicate keys.</exception> - public ConcurrentDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection) : this(collection, EqualityComparer<TKey>.Default) { } - - /// <summary> - /// Initializes a new instance of the <see cref="ConcurrentDictionary{TKey,TValue}"/> - /// class that is empty, has the specified concurrency level and capacity, and uses the specified - /// <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/>. - /// </summary> - /// <param name="comparer">The <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/> - /// implementation to use when comparing keys.</param> - /// <exception cref="T:System.ArgumentNullException"><paramref name="comparer"/> is a null reference - /// (Nothing in Visual Basic).</exception> - public ConcurrentDictionary(IEqualityComparer<TKey> comparer) : this(DefaultConcurrencyLevel, DEFAULT_CAPACITY, true, comparer) { } - - /// <summary> - /// Initializes a new instance of the <see cref="ConcurrentDictionary{TKey,TValue}"/> - /// class that contains elements copied from the specified <see - /// cref="T:System.Collections.IEnumerable"/>, has the default concurrency level, has the default - /// initial capacity, and uses the specified - /// <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/>. - /// </summary> - /// <param name="collection">The <see - /// cref="T:System.Collections.IEnumerable{KeyValuePair{TKey,TValue}}"/> whose elements are copied to - /// the new - /// <see cref="ConcurrentDictionary{TKey,TValue}"/>.</param> - /// <param name="comparer">The <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/> - /// implementation to use when comparing keys.</param> - /// <exception cref="T:System.ArgumentNullException"><paramref name="collection"/> is a null reference - /// (Nothing in Visual Basic). -or- - /// <paramref name="comparer"/> is a null reference (Nothing in Visual Basic). - /// </exception> - public ConcurrentDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer) - : this(comparer) - { - if (collection == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); - - InitializeFromCollection(collection); - } - - /// <summary> - /// Initializes a new instance of the <see cref="ConcurrentDictionary{TKey,TValue}"/> - /// class that contains elements copied from the specified <see cref="T:System.Collections.IEnumerable"/>, - /// has the specified concurrency level, has the specified initial capacity, and uses the specified - /// <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/>. - /// </summary> - /// <param name="concurrencyLevel">The estimated number of threads that will update the - /// <see cref="ConcurrentDictionary{TKey,TValue}"/> concurrently.</param> - /// <param name="collection">The <see cref="T:System.Collections.IEnumerable{KeyValuePair{TKey,TValue}}"/> whose elements are copied to the new - /// <see cref="ConcurrentDictionary{TKey,TValue}"/>.</param> - /// <param name="comparer">The <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/> implementation to use - /// when comparing keys.</param> - /// <exception cref="T:System.ArgumentNullException"> - /// <paramref name="collection"/> is a null reference (Nothing in Visual Basic). - /// -or- - /// <paramref name="comparer"/> is a null reference (Nothing in Visual Basic). - /// </exception> - /// <exception cref="T:System.ArgumentOutOfRangeException"> - /// <paramref name="concurrencyLevel"/> is less than 1. - /// </exception> - /// <exception cref="T:System.ArgumentException"><paramref name="collection"/> contains one or more duplicate keys.</exception> - public ConcurrentDictionary( - int concurrencyLevel, IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer) - : this(concurrencyLevel, DEFAULT_CAPACITY, false, comparer) - { - if (collection == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); - if (comparer == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparer); - - InitializeFromCollection(collection); - } - - private void InitializeFromCollection(IEnumerable<KeyValuePair<TKey, TValue>> collection) - { - TValue dummy; - foreach (KeyValuePair<TKey, TValue> pair in collection) - { - if (pair.Key == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); - - if (!TryAddInternal(pair.Key, pair.Value, false, false, out dummy)) - { - ThrowHelper.ThrowArgumentException(ExceptionResource.ConcurrentDictionary_SourceContainsDuplicateKeys); - } - } - - if (m_budget == 0) - { - m_budget = m_tables.m_buckets.Length / m_tables.m_locks.Length; - } - - } - - /// <summary> - /// Initializes a new instance of the <see cref="ConcurrentDictionary{TKey,TValue}"/> - /// class that is empty, has the specified concurrency level, has the specified initial capacity, and - /// uses the specified <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/>. - /// </summary> - /// <param name="concurrencyLevel">The estimated number of threads that will update the - /// <see cref="ConcurrentDictionary{TKey,TValue}"/> concurrently.</param> - /// <param name="capacity">The initial number of elements that the <see - /// cref="ConcurrentDictionary{TKey,TValue}"/> - /// can contain.</param> - /// <param name="comparer">The <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/> - /// implementation to use when comparing keys.</param> - /// <exception cref="T:System.ArgumentOutOfRangeException"> - /// <paramref name="concurrencyLevel"/> is less than 1. -or- - /// <paramref name="capacity"/> is less than 0. - /// </exception> - /// <exception cref="T:System.ArgumentNullException"><paramref name="comparer"/> is a null reference - /// (Nothing in Visual Basic).</exception> - public ConcurrentDictionary(int concurrencyLevel, int capacity, IEqualityComparer<TKey> comparer) - : this(concurrencyLevel, capacity, false, comparer) - { - } - internal ConcurrentDictionary(int concurrencyLevel, int capacity, bool growLockArray, IEqualityComparer<TKey> comparer) { if (concurrencyLevel < 1) @@ -488,91 +343,6 @@ namespace System.Collections.Concurrent } /// <summary> - /// Compares the existing value for the specified key with a specified value, and if they're equal, - /// updates the key with a third value. - /// </summary> - /// <param name="key">The key whose value is compared with <paramref name="comparisonValue"/> and - /// possibly replaced.</param> - /// <param name="newValue">The value that replaces the value of the element with <paramref - /// name="key"/> if the comparison results in equality.</param> - /// <param name="comparisonValue">The value that is compared to the value of the element with - /// <paramref name="key"/>.</param> - /// <returns>true if the value with <paramref name="key"/> was equal to <paramref - /// name="comparisonValue"/> and replaced with <paramref name="newValue"/>; otherwise, - /// false.</returns> - /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null - /// reference.</exception> - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "Reviewed for thread safety")] - public bool TryUpdate(TKey key, TValue newValue, TValue comparisonValue) - { - if (key == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); - - IEqualityComparer<TValue> valueComparer = EqualityComparer<TValue>.Default; - - while (true) - { - int bucketNo; - int lockNo; - int hashcode; - - Tables tables = m_tables; - IEqualityComparer<TKey> comparer = tables.m_comparer; - - hashcode = comparer.GetHashCode(key); - GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, tables.m_buckets.Length, tables.m_locks.Length); - - lock (tables.m_locks[lockNo]) - { - // If the table just got resized, we may not be holding the right lock, and must retry. - // This should be a rare occurence. - if (tables != m_tables) - { - continue; - } - - // Try to find this key in the bucket - Node prev = null; - for (Node node = tables.m_buckets[bucketNo]; node != null; node = node.m_next) - { - Assert((prev == null && node == tables.m_buckets[bucketNo]) || prev.m_next == node); - if (comparer.Equals(node.m_key, key)) - { - if (valueComparer.Equals(node.m_value, comparisonValue)) - { - if (s_isValueWriteAtomic) - { - node.m_value = newValue; - } - else - { - Node newNode = new Node(node.m_key, newValue, hashcode, node.m_next); - - if (prev == null) - { - tables.m_buckets[bucketNo] = newNode; - } - else - { - prev.m_next = newNode; - } - } - - return true; - } - - return false; - } - - prev = node; - } - - //didn't find the key - return false; - } - } - } - - /// <summary> /// Removes all keys and values from the <see cref="ConcurrentDictionary{TKey,TValue}"/>. /// </summary> public void Clear() @@ -947,149 +717,6 @@ namespace System.Collections.Concurrent } } - /// <summary> - /// Adds a key/value pair to the <see cref="ConcurrentDictionary{TKey,TValue}"/> - /// if the key does not already exist. - /// </summary> - /// <param name="key">The key of the element to add.</param> - /// <param name="valueFactory">The function used to generate a value for the key</param> - /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="T:System.ArgumentNullException"><paramref name="valueFactory"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="T:System.OverflowException">The dictionary contains too many - /// elements.</exception> - /// <returns>The value for the key. This will be either the existing value for the key if the - /// key is already in the dictionary, or the new value for the key as returned by valueFactory - /// if the key was not in the dictionary.</returns> - public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory) - { - if (key == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); - if (valueFactory == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.valueFactory); - - TValue resultingValue; - if (TryGetValue(key, out resultingValue)) - { - return resultingValue; - } - TryAddInternal(key, valueFactory(key), false, true, out resultingValue); - return resultingValue; - } - - /// <summary> - /// Adds a key/value pair to the <see cref="ConcurrentDictionary{TKey,TValue}"/> - /// 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> - /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="T:System.OverflowException">The dictionary contains too many - /// elements.</exception> - /// <returns>The value for the key. This will be either the existing value for the key if the - /// key is already in the dictionary, or the new value if the key was not in the dictionary.</returns> - public TValue GetOrAdd(TKey key, TValue value) - { - if (key == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); - - TValue resultingValue; - TryAddInternal(key, value, false, true, out resultingValue); - return resultingValue; - } - - /// <summary> - /// Adds a key/value pair to the <see cref="ConcurrentDictionary{TKey,TValue}"/> if the key does not already - /// exist, or updates a key/value pair in the <see cref="ConcurrentDictionary{TKey,TValue}"/> if the key - /// already exists. - /// </summary> - /// <param name="key">The key to be added or whose value should be updated</param> - /// <param name="addValueFactory">The function used to generate a value for an absent key</param> - /// <param name="updateValueFactory">The function used to generate a new value for an existing key - /// based on the key's existing value</param> - /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="T:System.ArgumentNullException"><paramref name="addValueFactory"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="T:System.ArgumentNullException"><paramref name="updateValueFactory"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="T:System.OverflowException">The dictionary contains too many - /// elements.</exception> - /// <returns>The new value for the key. This will be either be the result of addValueFactory (if the key was - /// absent) or the result of updateValueFactory (if the key was present).</returns> - public TValue AddOrUpdate(TKey key, Func<TKey, TValue> addValueFactory, Func<TKey, TValue, TValue> updateValueFactory) - { - if (key == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); - if (addValueFactory == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.addValueFactory); - if (updateValueFactory == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.updateValueFactory); - - TValue newValue, resultingValue; - while (true) - { - TValue oldValue; - if (TryGetValue(key, out oldValue)) - //key exists, try to update - { - newValue = updateValueFactory(key, oldValue); - if (TryUpdate(key, newValue, oldValue)) - { - return newValue; - } - } - else //try add - { - newValue = addValueFactory(key); - if (TryAddInternal(key, newValue, false, true, out resultingValue)) - { - return resultingValue; - } - } - } - } - - /// <summary> - /// Adds a key/value pair to the <see cref="ConcurrentDictionary{TKey,TValue}"/> if the key does not already - /// exist, or updates a key/value pair in the <see cref="ConcurrentDictionary{TKey,TValue}"/> if the key - /// already exists. - /// </summary> - /// <param name="key">The key to be added or whose value should be updated</param> - /// <param name="addValue">The value to be added for an absent key</param> - /// <param name="updateValueFactory">The function used to generate a new value for an existing key based on - /// the key's existing value</param> - /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="T:System.ArgumentNullException"><paramref name="updateValueFactory"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="T:System.OverflowException">The dictionary contains too many - /// elements.</exception> - /// <returns>The new value for the key. This will be either be the result of addValueFactory (if the key was - /// absent) or the result of updateValueFactory (if the key was present).</returns> - public TValue AddOrUpdate(TKey key, TValue addValue, Func<TKey, TValue, TValue> updateValueFactory) - { - if (key == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); - if (updateValueFactory == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.updateValueFactory); - TValue newValue, resultingValue; - while (true) - { - TValue oldValue; - if (TryGetValue(key, out oldValue)) - //key exists, try to update - { - newValue = updateValueFactory(key, oldValue); - if (TryUpdate(key, newValue, oldValue)) - { - return newValue; - } - } - else //try add - { - if (TryAddInternal(key, addValue, false, true, out resultingValue)) - { - return resultingValue; - } - } - } - } - /// <summary> diff --git a/src/mscorlib/src/System/Collections/Concurrent/ConcurrentQueue.cs b/src/mscorlib/src/System/Collections/Concurrent/ConcurrentQueue.cs index 7aa5971690..90ada007dd 100644 --- a/src/mscorlib/src/System/Collections/Concurrent/ConcurrentQueue.cs +++ b/src/mscorlib/src/System/Collections/Concurrent/ConcurrentQueue.cs @@ -1,67 +1,100 @@ // Licensed to the .NET Foundation under one or more agreements. // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. -#pragma warning disable 0420 - -// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ -// -// -// -// A lock-free, concurrent queue primitive, and its associated debugger view type. -// -// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- - -using System; -using System.Collections; using System.Collections.Generic; using System.Diagnostics; -using System.Diagnostics.Contracts; -using System.Runtime.ConstrainedExecution; using System.Runtime.InteropServices; using System.Runtime.Serialization; -using System.Security; -using System.Security.Permissions; using System.Threading; namespace System.Collections.Concurrent { - /// <summary> /// Represents a thread-safe first-in, first-out collection of objects. /// </summary> /// <typeparam name="T">Specifies the type of elements in the queue.</typeparam> /// <remarks> - /// All public and protected members of <see cref="ConcurrentQueue{T}"/> are thread-safe and may be used + /// All public and protected members of <see cref="ConcurrentQueue{T}"/> are thread-safe and may be used /// concurrently from multiple threads. /// </remarks> - [ComVisible(false)] [DebuggerDisplay("Count = {Count}")] [DebuggerTypeProxy(typeof(SystemCollectionsConcurrent_ProducerConsumerCollectionDebugView<>))] [Serializable] - public class ConcurrentQueue<T> : IProducerConsumerCollection<T>, IReadOnlyCollection<T> + internal class ConcurrentQueue<T> : IProducerConsumerCollection<T>, IReadOnlyCollection<T> { - //fields of ConcurrentQueue - [NonSerialized] - private volatile Segment m_head; + // This implementation provides an unbounded, multi-producer multi-consumer queue + // that supports the standard Enqueue/TryDequeue operations, as well as support for + // snapshot enumeration (GetEnumerator, ToArray, CopyTo), peeking, and Count/IsEmpty. + // It is composed of a linked list of bounded ring buffers, each of which has a head + // and a tail index, isolated from each other to minimize false sharing. As long as + // the number of elements in the queue remains less than the size of the current + // buffer (Segment), no additional allocations are required for enqueued items. When + // the number of items exceeds the size of the current segment, the current segment is + // "frozen" to prevent further enqueues, and a new segment is linked from it and set + // as the new tail segment for subsequent enqueues. As old segments are consumed by + // dequeues, the head reference is updated to point to the segment that dequeuers should + // try next. To support snapshot enumeration, segments also support the notion of + // preserving for observation, whereby they avoid overwriting state as part of dequeues. + // Any operation that requires a snapshot results in all current segments being + // both frozen for enqueues and preserved for observation: any new enqueues will go + // to new segments, and dequeuers will consume from the existing segments but without + // overwriting the existing data. + + /// <summary>Initial length of the segments used in the queue.</summary> + private const int InitialSegmentLength = 32; + /// <summary> + /// Maximum length of the segments used in the queue. This is a somewhat arbitrary limit: + /// larger means that as long as we don't exceed the size, we avoid allocating more segments, + /// but if we do exceed it, then the segment becomes garbage. + /// </summary> + private const int MaxSegmentLength = 1024 * 1024; + /// <summary> + /// Lock used to protect cross-segment operations, including any updates to <see cref="_tail"/> or <see cref="_head"/> + /// and any operations that need to get a consistent view of them. + /// </summary> [NonSerialized] - private volatile Segment m_tail; - - private T[] m_serializationArray; // Used for custom serialization. - - private const int SEGMENT_SIZE = 32; - - //number of snapshot takers, GetEnumerator(), ToList() and ToArray() operations take snapshot. + private object _crossSegmentLock; + /// <summary>The current tail segment.</summary> [NonSerialized] - internal volatile int m_numSnapshotTakers = 0; + private volatile Segment _tail; + /// <summary>The current head segment.</summary> + [NonSerialized] + private volatile Segment _head; + /// <summary>Field used to temporarily store the contents of the queue for serialization.</summary> + private T[] _serializationArray; /// <summary> /// Initializes a new instance of the <see cref="ConcurrentQueue{T}"/> class. /// </summary> public ConcurrentQueue() { - m_head = m_tail = new Segment(0, this); + _crossSegmentLock = new object(); + _tail = _head = new Segment(InitialSegmentLength); + } + + /// <summary>Set the data array to be serialized.</summary> + [OnSerializing] + private void OnSerializing(StreamingContext context) + { + _serializationArray = ToArray(); + } + + /// <summary>Clear the data array that was serialized.</summary> + [OnSerialized] + private void OnSerialized(StreamingContext context) + { + _serializationArray = null; + } + + /// <summary>Construct the queue from the deserialized <see cref="_serializationArray"/>.</summary> + [OnDeserialized] + private void OnDeserialized(StreamingContext context) + { + Debug.Assert(_serializationArray != null); + InitializeFromCollection(_serializationArray); + _serializationArray = null; } /// <summary> @@ -70,34 +103,39 @@ namespace System.Collections.Concurrent /// <param name="collection">A collection from which to copy elements.</param> private void InitializeFromCollection(IEnumerable<T> collection) { - Segment localTail = new Segment(0, this);//use this local variable to avoid the extra volatile read/write. this is safe because it is only called from ctor - m_head = localTail; - - int index = 0; - foreach (T element in collection) + _crossSegmentLock = new object(); + + // Determine the initial segment size. We'll use the default, + // unless the collection is known to be larger than than, in which + // case we round its length up to a power of 2, as all segments must + // be a power of 2 in length. + int length = InitialSegmentLength; + var c = collection as ICollection<T>; + if (c != null) { - Debug.Assert(index >= 0 && index < SEGMENT_SIZE); - localTail.UnsafeAdd(element); - index++; - - if (index >= SEGMENT_SIZE) + int count = c.Count; + if (count > length) { - localTail = localTail.UnsafeGrow(); - index = 0; + length = RoundUpToPowerOf2(count); } } - m_tail = localTail; + // Initialize the segment and add all of the data to it. + _tail = _head = new Segment(length); + foreach (T item in collection) + { + Enqueue(item); + } } /// <summary> - /// Initializes a new instance of the <see cref="ConcurrentQueue{T}"/> - /// class that contains elements copied from the specified collection + /// Initializes a new instance of the <see cref="ConcurrentQueue{T}"/> class that contains elements copied + /// from the specified collection. /// </summary> - /// <param name="collection">The collection whose elements are copied to the new <see - /// cref="ConcurrentQueue{T}"/>.</param> - /// <exception cref="T:System.ArgumentNullException">The <paramref name="collection"/> argument is - /// null.</exception> + /// <param name="collection"> + /// The collection whose elements are copied to the new <see cref="ConcurrentQueue{T}"/>. + /// </param> + /// <exception cref="System.ArgumentNullException">The <paramref name="collection"/> argument is null.</exception> public ConcurrentQueue(IEnumerable<T> collection) { if (collection == null) @@ -109,37 +147,15 @@ namespace System.Collections.Concurrent } /// <summary> - /// Get the data array to be serialized - /// </summary> - [OnSerializing] - private void OnSerializing(StreamingContext context) - { - // save the data into the serialization array to be saved - m_serializationArray = ToArray(); - } - - /// <summary> - /// Construct the queue from a previously seiralized one - /// </summary> - [OnDeserialized] - private void OnDeserialized(StreamingContext context) - { - Debug.Assert(m_serializationArray != null); - InitializeFromCollection(m_serializationArray); - m_serializationArray = null; - } - - /// <summary> - /// Copies the elements of the <see cref="T:System.Collections.ICollection"/> to an <see - /// cref="T:System.Array"/>, starting at a particular - /// <see cref="T:System.Array"/> index. + /// Copies the elements of the <see cref="ICollection"/> to an <see + /// cref="Array"/>, starting at a particular <see cref="Array"/> index. /// </summary> - /// <param name="array">The one-dimensional <see cref="T:System.Array">Array</see> that is the - /// destination of the elements copied from the - /// <see cref="T:System.Collections.Concurrent.ConcurrentBag"/>. The <see - /// cref="T:System.Array">Array</see> must have zero-based indexing.</param> - /// <param name="index">The zero-based index in <paramref name="array"/> at which copying - /// begins.</param> + /// <param name="array"> + /// The one-dimensional <see cref="Array">Array</see> that is the destination of the + /// elements copied from the <see cref="ConcurrentQueue{T}"/>. <paramref name="array"/> must have + /// zero-based indexing. + /// </param> + /// <param name="index">The zero-based index in <paramref name="array"/> at which copying begins.</param> /// <exception cref="ArgumentNullException"><paramref name="array"/> is a null reference (Nothing in /// Visual Basic).</exception> /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is less than @@ -148,100 +164,52 @@ namespace System.Collections.Concurrent /// <paramref name="array"/> is multidimensional. -or- /// <paramref name="array"/> does not have zero-based indexing. -or- /// <paramref name="index"/> is equal to or greater than the length of the <paramref name="array"/> - /// -or- The number of elements in the source <see cref="T:System.Collections.ICollection"/> is + /// -or- The number of elements in the source <see cref="ICollection"/> is /// greater than the available space from <paramref name="index"/> to the end of the destination /// <paramref name="array"/>. -or- The type of the source <see - /// cref="T:System.Collections.ICollection"/> cannot be cast automatically to the type of the + /// cref="ICollection"/> cannot be cast automatically to the type of the /// destination <paramref name="array"/>. /// </exception> void ICollection.CopyTo(Array array, int index) { + // Special-case when the Array is actually a T[], taking a faster path + T[] szArray = array as T[]; + if (szArray != null) + { + CopyTo(szArray, index); + return; + } + // Validate arguments. if (array == null) { throw new ArgumentNullException(nameof(array)); } - // We must be careful not to corrupt the array, so we will first accumulate an - // internal list of elements that we will then copy to the array. This requires - // some extra allocation, but is necessary since we don't know up front whether - // the array is sufficiently large to hold the stack's contents. - ((ICollection)ToList()).CopyTo(array, index); + // Otherwise, fall back to the slower path that first copies the contents + // to an array, and then uses that array's non-generic CopyTo to do the copy. + ToArray().CopyTo(array, index); } /// <summary> - /// Gets a value indicating whether access to the <see cref="T:System.Collections.ICollection"/> is + /// Gets a value indicating whether access to the <see cref="ICollection"/> is /// synchronized with the SyncRoot. /// </summary> - /// <value>true if access to the <see cref="T:System.Collections.ICollection"/> is synchronized + /// <value>true if access to the <see cref="ICollection"/> is synchronized /// with the SyncRoot; otherwise, false. For <see cref="ConcurrentQueue{T}"/>, this property always /// returns false.</value> - bool ICollection.IsSynchronized - { - // Gets a value indicating whether access to this collection is synchronized. Always returns - // false. The reason is subtle. While access is in face thread safe, it's not the case that - // locking on the SyncRoot would have prevented concurrent pushes and pops, as this property - // would typically indicate; that's because we internally use CAS operations vs. true locks. - get { return false; } - } - + bool ICollection.IsSynchronized => false; // always false, as true implies synchronization via SyncRoot /// <summary> /// Gets an object that can be used to synchronize access to the <see - /// cref="T:System.Collections.ICollection"/>. This property is not supported. - /// </summary> - /// <exception cref="T:System.NotSupportedException">The SyncRoot property is not supported.</exception> - object ICollection.SyncRoot - { - get - { - throw new NotSupportedException(Environment.GetResourceString("ConcurrentCollection_SyncRoot_NotSupported")); - } - } - - /// <summary> - /// Returns an enumerator that iterates through a collection. - /// </summary> - /// <returns>An <see cref="T:System.Collections.IEnumerator"/> that can be used to iterate through the collection.</returns> - IEnumerator IEnumerable.GetEnumerator() - { - return ((IEnumerable<T>)this).GetEnumerator(); - } - - /// <summary> - /// Attempts to add an object to the <see - /// cref="T:System.Collections.Concurrent.IProducerConsumerCollection{T}"/>. + /// cref="ICollection"/>. This property is not supported. /// </summary> - /// <param name="item">The object to add to the <see - /// cref="T:System.Collections.Concurrent.IProducerConsumerCollection{T}"/>. The value can be a null - /// reference (Nothing in Visual Basic) for reference types. - /// </param> - /// <returns>true if the object was added successfully; otherwise, false.</returns> - /// <remarks>For <see cref="ConcurrentQueue{T}"/>, this operation will always add the object to the - /// end of the <see cref="ConcurrentQueue{T}"/> - /// and return true.</remarks> - bool IProducerConsumerCollection<T>.TryAdd(T item) - { - Enqueue(item); - return true; - } + /// <exception cref="NotSupportedException">The SyncRoot property is not supported.</exception> + object ICollection.SyncRoot { get { throw new NotSupportedException(Environment.GetResourceString("ConcurrentCollection_SyncRoot_NotSupported")); } } - /// <summary> - /// Attempts to remove and return an object from the <see - /// cref="T:System.Collections.Concurrent.IProducerConsumerCollection{T}"/>. - /// </summary> - /// <param name="item"> - /// When this method returns, if the operation was successful, <paramref name="item"/> contains the - /// object removed. If no object was available to be removed, the value is unspecified. - /// </param> - /// <returns>true if an element was removed and returned succesfully; otherwise, false.</returns> - /// <remarks>For <see cref="ConcurrentQueue{T}"/>, this operation will attempt to remove the object - /// from the beginning of the <see cref="ConcurrentQueue{T}"/>. - /// </remarks> - bool IProducerConsumerCollection<T>.TryTake(out T item) - { - return TryDequeue(out item); - } + /// <summary>Returns an enumerator that iterates through a collection.</summary> + /// <returns>An <see cref="IEnumerator"/> that can be used to iterate through the collection.</returns> + IEnumerator IEnumerable.GetEnumerator() => ((IEnumerable<T>)this).GetEnumerator(); /// <summary> /// Gets a value that indicates whether the <see cref="ConcurrentQueue{T}"/> is empty. @@ -258,126 +226,43 @@ namespace System.Collections.Concurrent { get { - Segment head = m_head; - if (!head.IsEmpty) - //fast route 1: - //if current head is not empty, then queue is not empty - return false; - else if (head.Next == null) - //fast route 2: - //if current head is empty and it's the last segment - //then queue is empty - return true; - else - //slow route: - //current head is empty and it is NOT the last segment, - //it means another thread is growing new segment - { - SpinWait spin = new SpinWait(); - while (head.IsEmpty) - { - if (head.Next == null) - return true; - - spin.SpinOnce(); - head = m_head; - } - return false; - } + // IsEmpty == !TryPeek. We use a "resultUsed:false" peek in order to avoid marking + // segments as preserved for observation, making IsEmpty a cheaper way than either + // TryPeek(out T) or Count == 0 to check whether any elements are in the queue. + T ignoredResult; + return !TryPeek(out ignoredResult, resultUsed: false); } } - /// <summary> - /// Copies the elements stored in the <see cref="ConcurrentQueue{T}"/> to a new array. - /// </summary> - /// <returns>A new array containing a snapshot of elements copied from the <see - /// cref="ConcurrentQueue{T}"/>.</returns> + /// <summary>Copies the elements stored in the <see cref="ConcurrentQueue{T}"/> to a new array.</summary> + /// <returns>A new array containing a snapshot of elements copied from the <see cref="ConcurrentQueue{T}"/>.</returns> public T[] ToArray() { - return ToList().ToArray(); - } + // Snap the current contents for enumeration. + Segment head, tail; + int headHead, tailTail; + SnapForObservation(out head, out headHead, out tail, out tailTail); - /// <summary> - /// Copies the <see cref="ConcurrentQueue{T}"/> elements to a new <see - /// cref="T:System.Collections.Generic.List{T}"/>. - /// </summary> - /// <returns>A new <see cref="T:System.Collections.Generic.List{T}"/> containing a snapshot of - /// elements copied from the <see cref="ConcurrentQueue{T}"/>.</returns> - private List<T> ToList() - { - // Increments the number of active snapshot takers. This increment must happen before the snapshot is - // taken. At the same time, Decrement must happen after list copying is over. Only in this way, can it - // eliminate race condition when Segment.TryRemove() checks whether m_numSnapshotTakers == 0. - Interlocked.Increment(ref m_numSnapshotTakers); + // Count the number of items in that snapped set, and use it to allocate an + // array of the right size. + long count = GetCount(head, headHead, tail, tailTail); + T[] arr = new T[count]; - List<T> list = new List<T>(); - try + // Now enumerate the contents, copying each element into the array. + using (IEnumerator<T> e = Enumerate(head, headHead, tail, tailTail)) { - //store head and tail positions in buffer, - Segment head, tail; - int headLow, tailHigh; - GetHeadTailPositions(out head, out tail, out headLow, out tailHigh); - - if (head == tail) - { - head.AddToList(list, headLow, tailHigh); - } - else + int i = 0; + while (e.MoveNext()) { - head.AddToList(list, headLow, SEGMENT_SIZE - 1); - Segment curr = head.Next; - while (curr != tail) - { - curr.AddToList(list, 0, SEGMENT_SIZE - 1); - curr = curr.Next; - } - //Add tail segment - tail.AddToList(list, 0, tailHigh); + arr[i++] = e.Current; } + Debug.Assert(count == i); } - finally - { - // This Decrement must happen after copying is over. - Interlocked.Decrement(ref m_numSnapshotTakers); - } - return list; - } - /// <summary> - /// Store the position of the current head and tail positions. - /// </summary> - /// <param name="head">return the head segment</param> - /// <param name="tail">return the tail segment</param> - /// <param name="headLow">return the head offset, value range [0, SEGMENT_SIZE]</param> - /// <param name="tailHigh">return the tail offset, value range [-1, SEGMENT_SIZE-1]</param> - private void GetHeadTailPositions(out Segment head, out Segment tail, - out int headLow, out int tailHigh) - { - head = m_head; - tail = m_tail; - headLow = head.Low; - tailHigh = tail.High; - SpinWait spin = new SpinWait(); - - //we loop until the observed values are stable and sensible. - //This ensures that any update order by other methods can be tolerated. - while ( - //if head and tail changed, retry - head != m_head || tail != m_tail - //if low and high pointers, retry - || headLow != head.Low || tailHigh != tail.High - //if head jumps ahead of tail because of concurrent grow and dequeue, retry - || head.m_index > tail.m_index) - { - spin.SpinOnce(); - head = m_head; - tail = m_tail; - headLow = head.Low; - tailHigh = tail.High; - } + // And return it. + return arr; } - /// <summary> /// Gets the number of elements contained in the <see cref="ConcurrentQueue{T}"/>. /// </summary> @@ -391,38 +276,140 @@ namespace System.Collections.Concurrent { get { - //store head and tail positions in buffer, Segment head, tail; - int headLow, tailHigh; - GetHeadTailPositions(out head, out tail, out headLow, out tailHigh); - - if (head == tail) + int headHead, headTail, tailHead, tailTail; + var spinner = new SpinWait(); + while (true) { - return tailHigh - headLow + 1; + // Capture the head and tail, as well as the head's head and tail. + head = _head; + tail = _tail; + headHead = Volatile.Read(ref head._headAndTail.Head); + headTail = Volatile.Read(ref head._headAndTail.Tail); + + if (head == tail) + { + // There was a single segment in the queue. If the captured + // values still (or again) represent reality, return the segment's + // count. A single segment should be the most common case once the + // queue's size has stabilized after segments have grown to + // the point where growing is no longer needed. + if (head == _head && + head == _tail && + headHead == Volatile.Read(ref head._headAndTail.Head) && + headTail == Volatile.Read(ref head._headAndTail.Tail)) + { + return GetCount(head, headHead, headTail); + } + } + else if (head._nextSegment == tail) + { + // There were two segments in the queue. Get the positions + // from the tail, and if the captured values still (or again) match + // reality, return the sum of the counts from both segments. + tailHead = Volatile.Read(ref tail._headAndTail.Head); + tailTail = Volatile.Read(ref tail._headAndTail.Tail); + if (head == _head && + tail == _tail && + headHead == Volatile.Read(ref head._headAndTail.Head) && + headTail == Volatile.Read(ref head._headAndTail.Tail) && + tailHead == Volatile.Read(ref tail._headAndTail.Head) && + tailTail == Volatile.Read(ref tail._headAndTail.Tail)) + { + // We got stable values, so we can just compute the sizes based on those + // values and return the sum of the counts of the segments. + return GetCount(head, headHead, headTail) + GetCount(tail, tailHead, tailTail); + } + } + else + { + // There were more than two segments. Take the slower path, where we freeze the + // queue and then count the now stable segments. + SnapForObservation(out head, out headHead, out tail, out tailTail); + return unchecked((int)GetCount(head, headHead, tail, tailTail)); + } + + // We raced with enqueues/dequeues and captured an inconsistent picture of the queue. + // Spin and try again. + spinner.SpinOnce(); } + } + } - //head segment - int count = SEGMENT_SIZE - headLow; + /// <summary>Computes the number of items in a segment based on a fixed head and tail in that segment.</summary> + private static int GetCount(Segment s, int head, int tail) + { + if (head != tail && head != tail - s.FreezeOffset) + { + head &= s._slotsMask; + tail &= s._slotsMask; + return head < tail ? tail - head : s._slots.Length - head + tail; + } + return 0; + } - //middle segment(s), if any, are full. - //We don't deal with overflow to be consistent with the behavior of generic types in CLR. - count += SEGMENT_SIZE * ((int)(tail.m_index - head.m_index - 1)); + /// <summary>Gets the number of items in snapped region.</summary> + private static long GetCount(Segment head, int headHead, Segment tail, int tailTail) + { + // All of the segments should have been both frozen for enqueues and preserved for observation. + // Validate that here for head and tail; we'll validate it for intermediate segments later. + Debug.Assert(head._preservedForObservation); + Debug.Assert(head._frozenForEnqueues); + Debug.Assert(tail._preservedForObservation); + Debug.Assert(tail._frozenForEnqueues); + + long count = 0; + + // Head segment. We've already marked it as frozen for enqueues, so its tail position is fixed, + // and we've already marked it as preserved for observation (before we grabbed the head), so we + // can safely enumerate from its head to its tail and access its elements. + int headTail = (head == tail ? tailTail : Volatile.Read(ref head._headAndTail.Tail)) - head.FreezeOffset; + if (headHead < headTail) + { + // Mask the head and tail for the head segment + headHead &= head._slotsMask; + headTail &= head._slotsMask; + + // Increase the count by either the one or two regions, based on whether tail + // has wrapped to be less than head. + count += headHead < headTail ? + headTail - headHead : + head._slots.Length - headHead + headTail; + } - //tail segment - count += tailHigh + 1; + // We've enumerated the head. If the tail is different from the head, we need to + // enumerate the remaining segments. + if (head != tail) + { + // Count the contents of each segment between head and tail, not including head and tail. + // Since there were segments before these, for our purposes we consider them to start at + // the 0th element, and since there is at least one segment after each, each was frozen + // by the time we snapped it, so we can iterate until each's frozen tail. + for (Segment s = head._nextSegment; s != tail; s = s._nextSegment) + { + Debug.Assert(s._preservedForObservation); + Debug.Assert(s._frozenForEnqueues); + count += s._headAndTail.Tail - s.FreezeOffset; + } - return count; + // Finally, enumerate the tail. As with the intermediate segments, there were segments + // before this in the snapped region, so we can start counting from the beginning. Unlike + // the intermediate segments, we can't just go until the Tail, as that could still be changing; + // instead we need to go until the tail we snapped for observation. + count += tailTail - tail.FreezeOffset; } - } + // Return the computed count. + return count; + } /// <summary> /// Copies the <see cref="ConcurrentQueue{T}"/> elements to an existing one-dimensional <see - /// cref="T:System.Array">Array</see>, starting at the specified array index. + /// cref="Array">Array</see>, starting at the specified array index. /// </summary> - /// <param name="array">The one-dimensional <see cref="T:System.Array">Array</see> that is the + /// <param name="array">The one-dimensional <see cref="Array">Array</see> that is the /// destination of the elements copied from the - /// <see cref="ConcurrentQueue{T}"/>. The <see cref="T:System.Array">Array</see> must have zero-based + /// <see cref="ConcurrentQueue{T}"/>. The <see cref="Array">Array</see> must have zero-based /// indexing.</param> /// <param name="index">The zero-based index in <paramref name="array"/> at which copying /// begins.</param> @@ -442,19 +429,36 @@ namespace System.Collections.Concurrent { throw new ArgumentNullException(nameof(array)); } + if (index < 0) + { + throw new ArgumentOutOfRangeException(nameof(index)); + } - // We must be careful not to corrupt the array, so we will first accumulate an - // internal list of elements that we will then copy to the array. This requires - // some extra allocation, but is necessary since we don't know up front whether - // the array is sufficiently large to hold the stack's contents. - ToList().CopyTo(array, index); - } + // Snap for enumeration + Segment head, tail; + int headHead, tailTail; + SnapForObservation(out head, out headHead, out tail, out tailTail); + // Get the number of items to be enumerated + long count = GetCount(head, headHead, tail, tailTail); + if (index > array.Length - count) + { + throw new ArgumentException(Environment.GetResourceString("Arg_ArrayPlusOffTooSmall")); + } - /// <summary> - /// Returns an enumerator that iterates through the <see - /// cref="ConcurrentQueue{T}"/>. - /// </summary> + // Copy the items to the target array + int i = index; + using (IEnumerator<T> e = Enumerate(head, headHead, tail, tailTail)) + { + while (e.MoveNext()) + { + array[i++] = e.Current; + } + } + Debug.Assert(count == i - index); + } + + /// <summary>Returns an enumerator that iterates through the <see cref="ConcurrentQueue{T}"/>.</summary> /// <returns>An enumerator for the contents of the <see /// cref="ConcurrentQueue{T}"/>.</returns> /// <remarks> @@ -465,124 +469,195 @@ namespace System.Collections.Concurrent /// </remarks> public IEnumerator<T> GetEnumerator() { - // Increments the number of active snapshot takers. This increment must happen before the snapshot is - // taken. At the same time, Decrement must happen after the enumeration is over. Only in this way, can it - // eliminate race condition when Segment.TryRemove() checks whether m_numSnapshotTakers == 0. - Interlocked.Increment(ref m_numSnapshotTakers); - - // Takes a snapshot of the queue. - // A design flaw here: if a Thread.Abort() happens, we cannot decrement m_numSnapshotTakers. But we cannot - // wrap the following with a try/finally block, otherwise the decrement will happen before the yield return - // statements in the GetEnumerator (head, tail, headLow, tailHigh) method. Segment head, tail; - int headLow, tailHigh; - GetHeadTailPositions(out head, out tail, out headLow, out tailHigh); - - //If we put yield-return here, the iterator will be lazily evaluated. As a result a snapshot of - // the queue is not taken when GetEnumerator is initialized but when MoveNext() is first called. - // This is inconsistent with existing generic collections. In order to prevent it, we capture the - // value of m_head in a buffer and call out to a helper method. - //The old way of doing this was to return the ToList().GetEnumerator(), but ToList() was an - // unnecessary perfomance hit. - return GetEnumerator(head, tail, headLow, tailHigh); + int headHead, tailTail; + SnapForObservation(out head, out headHead, out tail, out tailTail); + return Enumerate(head, headHead, tail, tailTail); } /// <summary> - /// Helper method of GetEnumerator to seperate out yield return statement, and prevent lazy evaluation. + /// Gets the head and tail information of the current contents of the queue. + /// After this call returns, the specified region can be enumerated any number + /// of times and will not change. /// </summary> - private IEnumerator<T> GetEnumerator(Segment head, Segment tail, int headLow, int tailHigh) + private void SnapForObservation(out Segment head, out int headHead, out Segment tail, out int tailTail) { - try + lock (_crossSegmentLock) // _head and _tail may only change while the lock is held. { - SpinWait spin = new SpinWait(); + // Snap the head and tail + head = _head; + tail = _tail; + Debug.Assert(head != null); + Debug.Assert(tail != null); + Debug.Assert(tail._nextSegment == null); + + // Mark them and all segments in between as preserving, and ensure no additional items + // can be added to the tail. + for (Segment s = head; ; s = s._nextSegment) + { + s._preservedForObservation = true; + if (s == tail) break; + Debug.Assert(s._frozenForEnqueues); // any non-tail should already be marked + } + tail.EnsureFrozenForEnqueues(); // we want to prevent the tailTail from moving - if (head == tail) + // At this point, any dequeues from any segment won't overwrite the value, and + // none of the existing segments can have new items enqueued. + + headHead = Volatile.Read(ref head._headAndTail.Head); + tailTail = Volatile.Read(ref tail._headAndTail.Tail); + } + } + + /// <summary>Gets the item stored in the <paramref name="i"/>th entry in <paramref name="segment"/>.</summary> + private T GetItemWhenAvailable(Segment segment, int i) + { + Debug.Assert(segment._preservedForObservation); + + // Get the expected value for the sequence number + int expectedSequenceNumberAndMask = (i + 1) & segment._slotsMask; + + // If the expected sequence number is not yet written, we're still waiting for + // an enqueuer to finish storing it. Spin until it's there. + if ((segment._slots[i].SequenceNumber & segment._slotsMask) != expectedSequenceNumberAndMask) + { + var spinner = new SpinWait(); + while ((Volatile.Read(ref segment._slots[i].SequenceNumber) & segment._slotsMask) != expectedSequenceNumberAndMask) { - for (int i = headLow; i <= tailHigh; i++) - { - // If the position is reserved by an Enqueue operation, but the value is not written into, - // spin until the value is available. - spin.Reset(); - while (!head.m_state[i].m_value) - { - spin.SpinOnce(); - } - yield return head.m_array[i]; - } + spinner.SpinOnce(); + } + } + + // Return the value from the slot. + return segment._slots[i].Item; + } + + private IEnumerator<T> Enumerate(Segment head, int headHead, Segment tail, int tailTail) + { + Debug.Assert(head._preservedForObservation); + Debug.Assert(head._frozenForEnqueues); + Debug.Assert(tail._preservedForObservation); + Debug.Assert(tail._frozenForEnqueues); + + // Head segment. We've already marked it as not accepting any more enqueues, + // so its tail position is fixed, and we've already marked it as preserved for + // enumeration (before we grabbed its head), so we can safely enumerate from + // its head to its tail. + int headTail = (head == tail ? tailTail : Volatile.Read(ref head._headAndTail.Tail)) - head.FreezeOffset; + if (headHead < headTail) + { + headHead &= head._slotsMask; + headTail &= head._slotsMask; + + if (headHead < headTail) + { + for (int i = headHead; i < headTail; i++) yield return GetItemWhenAvailable(head, i); } else { - //iterate on head segment - for (int i = headLow; i < SEGMENT_SIZE; i++) - { - // If the position is reserved by an Enqueue operation, but the value is not written into, - // spin until the value is available. - spin.Reset(); - while (!head.m_state[i].m_value) - { - spin.SpinOnce(); - } - yield return head.m_array[i]; - } - //iterate on middle segments - Segment curr = head.Next; - while (curr != tail) - { - for (int i = 0; i < SEGMENT_SIZE; i++) - { - // If the position is reserved by an Enqueue operation, but the value is not written into, - // spin until the value is available. - spin.Reset(); - while (!curr.m_state[i].m_value) - { - spin.SpinOnce(); - } - yield return curr.m_array[i]; - } - curr = curr.Next; - } + for (int i = headHead; i < head._slots.Length; i++) yield return GetItemWhenAvailable(head, i); + for (int i = 0; i < headTail; i++) yield return GetItemWhenAvailable(head, i); + } + } - //iterate on tail segment - for (int i = 0; i <= tailHigh; i++) + // We've enumerated the head. If the tail is the same, we're done. + if (head != tail) + { + // Each segment between head and tail, not including head and tail. Since there were + // segments before these, for our purposes we consider it to start at the 0th element. + for (Segment s = head._nextSegment; s != tail; s = s._nextSegment) + { + Debug.Assert(s._preservedForObservation, "Would have had to been preserved as a segment part of enumeration"); + Debug.Assert(s._frozenForEnqueues, "Would have had to be frozen for enqueues as it's intermediate"); + + int sTail = s._headAndTail.Tail - s.FreezeOffset; + for (int i = 0; i < sTail; i++) { - // If the position is reserved by an Enqueue operation, but the value is not written into, - // spin until the value is available. - spin.Reset(); - while (!tail.m_state[i].m_value) - { - spin.SpinOnce(); - } - yield return tail.m_array[i]; + yield return GetItemWhenAvailable(s, i); } } - } - finally - { - // This Decrement must happen after the enumeration is over. - Interlocked.Decrement(ref m_numSnapshotTakers); + + // Enumerate the tail. Since there were segments before this, we can just start at + // its beginning, and iterate until the tail we already grabbed. + tailTail -= tail.FreezeOffset; + for (int i = 0; i < tailTail; i++) + { + yield return GetItemWhenAvailable(tail, i); + } } } - /// <summary> - /// Adds an object to the end of the <see cref="ConcurrentQueue{T}"/>. - /// </summary> - /// <param name="item">The object to add to the end of the <see - /// cref="ConcurrentQueue{T}"/>. The value can be a null reference - /// (Nothing in Visual Basic) for reference types. + /// <summary>Round the specified value up to the next power of 2, if it isn't one already.</summary> + private static int RoundUpToPowerOf2(int i) + { + --i; + i |= i >> 1; + i |= i >> 2; + i |= i >> 4; + i |= i >> 8; + i |= i >> 16; + return i + 1; + } + + /// <summary>Adds an object to the end of the <see cref="ConcurrentQueue{T}"/>.</summary> + /// <param name="item"> + /// The object to add to the end of the <see cref="ConcurrentQueue{T}"/>. + /// The value can be a null reference (Nothing in Visual Basic) for reference types. /// </param> public void Enqueue(T item) { - SpinWait spin = new SpinWait(); + // Try to enqueue to the current tail. + if (!_tail.TryEnqueue(item)) + { + // If we're unable to, we need to take a slow path that will + // try to add a new tail segment. + EnqueueSlow(item); + } + } + + /// <summary>Adds to the end of the queue, adding a new segment if necessary.</summary> + private void EnqueueSlow(T item) + { while (true) { - Segment tail = m_tail; - if (tail.TryAppend(item)) + Segment tail = _tail; + + // Try to append to the existing tail. + if (tail.TryEnqueue(item)) + { return; - spin.SpinOnce(); + } + + // If we were unsuccessful, take the lock so that we can compare and manipulate + // the tail. Assuming another enqueuer hasn't already added a new segment, + // do so, then loop around to try enqueueing again. + lock (_crossSegmentLock) + { + if (tail == _tail) + { + // Make sure no one else can enqueue to this segment. + tail.EnsureFrozenForEnqueues(); + + // We determine the new segment's length based on the old length. + // In general, we double the size of the segment, to make it less likely + // that we'll need to grow again. However, if the tail segment is marked + // as preserved for observation, something caused us to avoid reusing this + // segment, and if that happens a lot and we grow, we'll end up allocating + // lots of wasted space. As such, in such situations we reset back to the + // initial segment length; if these observations are happening frequently, + // this will help to avoid wasted memory, and if they're not, we'll + // relatively quickly grow again to a larger size. + int nextSize = tail._preservedForObservation ? InitialSegmentLength : tail.Capacity * 2; + var newTail = new Segment(nextSize); + + // Hook up the new tail. + tail._nextSegment = newTail; + _tail = newTail; + } + } } } - /// <summary> /// Attempts to remove and return the object at the beginning of the <see /// cref="ConcurrentQueue{T}"/>. @@ -591,369 +666,456 @@ namespace System.Collections.Concurrent /// When this method returns, if the operation was successful, <paramref name="result"/> contains the /// object removed. If no object was available to be removed, the value is unspecified. /// </param> - /// <returns>true if an element was removed and returned from the beggining of the <see - /// cref="ConcurrentQueue{T}"/> - /// succesfully; otherwise, false.</returns> - public bool TryDequeue(out T result) + /// <returns> + /// true if an element was removed and returned from the beginning of the + /// <see cref="ConcurrentQueue{T}"/> successfully; otherwise, false. + /// </returns> + public bool TryDequeue(out T result) => + _head.TryDequeue(out result) || // fast-path that operates just on the head segment + TryDequeueSlow(out result); // slow path that needs to fix up segments + + /// <summary>Tries to dequeue an item, removing empty segments as needed.</summary> + private bool TryDequeueSlow(out T item) { - while (!IsEmpty) + while (true) { - Segment head = m_head; - if (head.TryRemove(out result)) + // Get the current head + Segment head = _head; + + // Try to take. If we're successful, we're done. + if (head.TryDequeue(out item)) + { + return true; + } + + // Check to see whether this segment is the last. If it is, we can consider + // this to be a moment-in-time empty condition (even though between the TryDequeue + // check and this check, another item could have arrived). + if (head._nextSegment == null) + { + item = default(T); + return false; + } + + // At this point we know that head.Next != null, which means + // this segment has been frozen for additional enqueues. But between + // the time that we ran TryDequeue and checked for a next segment, + // another item could have been added. Try to dequeue one more time + // to confirm that the segment is indeed empty. + Debug.Assert(head._frozenForEnqueues); + if (head.TryDequeue(out item)) + { return true; - //since method IsEmpty spins, we don't need to spin in the while loop + } + + // This segment is frozen (nothing more can be added) and empty (nothing is in it). + // Update head to point to the next segment in the list, assuming no one's beat us to it. + lock (_crossSegmentLock) + { + if (head == _head) + { + _head = head._nextSegment; + } + } } - result = default(T); - return false; } /// <summary> /// Attempts to return an object from the beginning of the <see cref="ConcurrentQueue{T}"/> /// without removing it. /// </summary> - /// <param name="result">When this method returns, <paramref name="result"/> contains an object from - /// the beginning of the <see cref="T:System.Collections.Concurrent.ConccurrentQueue{T}"/> or an - /// unspecified value if the operation failed.</param> + /// <param name="result"> + /// When this method returns, <paramref name="result"/> contains an object from + /// the beginning of the <see cref="Concurrent.ConcurrentQueue{T}"/> or default(T) + /// if the operation failed. + /// </param> /// <returns>true if and object was returned successfully; otherwise, false.</returns> - public bool TryPeek(out T result) - { - Interlocked.Increment(ref m_numSnapshotTakers); + /// <remarks> + /// For determining whether the collection contains any items, use of the <see cref="IsEmpty"/> + /// property is recommended rather than peeking. + /// </remarks> + public bool TryPeek(out T result) => TryPeek(out result, resultUsed: true); - while (!IsEmpty) + /// <summary>Attempts to retrieve the value for the first element in the queue.</summary> + /// <param name="result">The value of the first element, if found.</param> + /// <param name="resultUsed">true if the result is neede; otherwise false if only the true/false outcome is needed.</param> + /// <returns>true if an element was found; otherwise, false.</returns> + private bool TryPeek(out T result, bool resultUsed) + { + // Starting with the head segment, look through all of the segments + // for the first one we can find that's not empty. + Segment s = _head; + while (true) { - Segment head = m_head; - if (head.TryPeek(out result)) + // Grab the next segment from this one, before we peek. + // This is to be able to see whether the value has changed + // during the peek operation. + Segment next = Volatile.Read(ref s._nextSegment); + + // Peek at the segment. If we find an element, we're done. + if (s.TryPeek(out result, resultUsed)) { - Interlocked.Decrement(ref m_numSnapshotTakers); return true; } - //since method IsEmpty spins, we don't need to spin in the while loop + + // The current segment was empty at the moment we checked. + + if (next != null) + { + // If prior to the peek there was already a next segment, then + // during the peek no additional items could have been enqueued + // to it and we can just move on to check the next segment. + Debug.Assert(next == s._nextSegment); + s = next; + } + else if (Volatile.Read(ref s._nextSegment) == null) + { + // The next segment is null. Nothing more to peek at. + break; + } + + // The next segment was null before we peeked but non-null after. + // That means either when we peeked the first segment had + // already been frozen but the new segment not yet added, + // or that the first segment was empty and between the time + // that we peeked and then checked _nextSegment, so many items + // were enqueued that we filled the first segment and went + // into the next. Since we need to peek in order, we simply + // loop around again to peek on the same segment. The next + // time around on this segment we'll then either successfully + // peek or we'll find that next was non-null before peeking, + // and we'll traverse to that segment. } + result = default(T); - Interlocked.Decrement(ref m_numSnapshotTakers); return false; } - /// <summary> - /// private class for ConcurrentQueue. - /// a queue is a linked list of small arrays, each node is called a segment. - /// A segment contains an array, a pointer to the next segment, and m_low, m_high indices recording - /// the first and last valid elements of the array. + /// Removes all objects from the <see cref="ConcurrentQueue{T}"/>. /// </summary> - private class Segment + public void Clear() { - //we define two volatile arrays: m_array and m_state. Note that the accesses to the array items - //do not get volatile treatment. But we don't need to worry about loading adjacent elements or - //store/load on adjacent elements would suffer reordering. - // - Two stores: these are at risk, but CLRv2 memory model guarantees store-release hence we are safe. - // - Two loads: because one item from two volatile arrays are accessed, the loads of the array references - // are sufficient to prevent reordering of the loads of the elements. - internal volatile T[] m_array; - - // For each entry in m_array, the corresponding entry in m_state indicates whether this position contains - // a valid value. m_state is initially all false. - internal volatile VolatileBool[] m_state; - - //pointer to the next segment. null if the current segment is the last segment - private volatile Segment m_next; - - //We use this zero based index to track how many segments have been created for the queue, and - //to compute how many active segments are there currently. - // * The number of currently active segments is : m_tail.m_index - m_head.m_index + 1; - // * m_index is incremented with every Segment.Grow operation. We use Int64 type, and we can safely - // assume that it never overflows. To overflow, we need to do 2^63 increments, even at a rate of 4 - // billion (2^32) increments per second, it takes 2^31 seconds, which is about 64 years. - internal readonly long m_index; - - //indices of where the first and last valid values - // - m_low points to the position of the next element to pop from this segment, range [0, infinity) - // m_low >= SEGMENT_SIZE implies the segment is disposable - // - m_high points to the position of the latest pushed element, range [-1, infinity) - // m_high == -1 implies the segment is new and empty - // m_high >= SEGMENT_SIZE-1 means this segment is ready to grow. - // and the thread who sets m_high to SEGMENT_SIZE-1 is responsible to grow the segment - // - Math.Min(m_low, SEGMENT_SIZE) > Math.Min(m_high, SEGMENT_SIZE-1) implies segment is empty - // - initially m_low =0 and m_high=-1; - private volatile int m_low; - private volatile int m_high; - - private volatile ConcurrentQueue<T> m_source; - - /// <summary> - /// Create and initialize a segment with the specified index. - /// </summary> - internal Segment(long index, ConcurrentQueue<T> source) + lock (_crossSegmentLock) { - m_array = new T[SEGMENT_SIZE]; - m_state = new VolatileBool[SEGMENT_SIZE]; //all initialized to false - m_high = -1; - Debug.Assert(index >= 0); - m_index = index; - m_source = source; - } - - /// <summary> - /// return the next segment - /// </summary> - internal Segment Next - { - get { return m_next; } - } - - - /// <summary> - /// return true if the current segment is empty (doesn't have any element available to dequeue, - /// false otherwise - /// </summary> - internal bool IsEmpty - { - get { return (Low > High); } - } - - /// <summary> - /// Add an element to the tail of the current segment - /// exclusively called by ConcurrentQueue.InitializedFromCollection - /// InitializeFromCollection is responsible to guaratee that there is no index overflow, - /// and there is no contention - /// </summary> - /// <param name="value"></param> - internal void UnsafeAdd(T value) - { - Debug.Assert(m_high < SEGMENT_SIZE - 1); - m_high++; - m_array[m_high] = value; - m_state[m_high].m_value = true; + // Simply substitute a new segment for the existing head/tail, + // as is done in the constructor. Operations currently in flight + // may still read from or write to an existing segment that's + // getting dropped, meaning that in flight operations may not be + // linear with regards to this clear operation. To help mitigate + // in-flight operations enqueuing onto the tail that's about to + // be dropped, we first freeze it; that'll force enqueuers to take + // this lock to synchronize and see the new tail. + _tail.EnsureFrozenForEnqueues(); + _tail = _head = new Segment(InitialSegmentLength); } + } - /// <summary> - /// Create a new segment and append to the current one - /// Does not update the m_tail pointer - /// exclusively called by ConcurrentQueue.InitializedFromCollection - /// InitializeFromCollection is responsible to guaratee that there is no index overflow, - /// and there is no contention - /// </summary> - /// <returns>the reference to the new Segment</returns> - internal Segment UnsafeGrow() + /// <summary> + /// Provides a multi-producer, multi-consumer thread-safe bounded segment. When the queue is full, + /// enqueues fail and return false. When the queue is empty, dequeues fail and return null. + /// These segments are linked together to form the unbounded <see cref="ConcurrentQueue{T}"/>. + /// </summary> + [DebuggerDisplay("Capacity = {Capacity}")] + private sealed class Segment + { + // Segment design is inspired by the algorithm outlined at: + // http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue + + /// <summary>The array of items in this queue. Each slot contains the item in that slot and its "sequence number".</summary> + internal readonly Slot[] _slots; + /// <summary>Mask for quickly accessing a position within the queue's array.</summary> + internal readonly int _slotsMask; + /// <summary>The head and tail positions, with padding to help avoid false sharing contention.</summary> + /// <remarks>Dequeueing happens from the head, enqueueing happens at the tail.</remarks> + internal PaddedHeadAndTail _headAndTail; // mutable struct: do not make this readonly + + /// <summary>Indicates whether the segment has been marked such that dequeues don't overwrite the removed data.</summary> + internal bool _preservedForObservation; + /// <summary>Indicates whether the segment has been marked such that no additional items may be enqueued.</summary> + internal bool _frozenForEnqueues; + /// <summary>The segment following this one in the queue, or null if this segment is the last in the queue.</summary> + internal Segment _nextSegment; + + /// <summary>Creates the segment.</summary> + /// <param name="boundedLength"> + /// The maximum number of elements the segment can contain. Must be a power of 2. + /// </param> + public Segment(int boundedLength) { - Debug.Assert(m_high >= SEGMENT_SIZE - 1); - Segment newSegment = new Segment(m_index + 1, m_source); //m_index is Int64, we don't need to worry about overflow - m_next = newSegment; - return newSegment; + // Validate the length + Debug.Assert(boundedLength >= 2, $"Must be >= 2, got {boundedLength}"); + Debug.Assert((boundedLength & (boundedLength - 1)) == 0, $"Must be a power of 2, got {boundedLength}"); + + // Initialize the slots and the mask. The mask is used as a way of quickly doing "% _slots.Length", + // instead letting us do "& _slotsMask". + _slots = new Slot[boundedLength]; + _slotsMask = boundedLength - 1; + + // Initialize the sequence number for each slot. The sequence number provides a ticket that + // allows dequeuers to know whether they can dequeue and enqueuers to know whether they can + // enqueue. An enqueuer at position N can enqueue when the sequence number is N, and a dequeuer + // for position N can dequeue when the sequence number is N + 1. When an enqueuer is done writing + // at position N, it sets the sequence number to N so that a dequeuer will be able to dequeue, + // and when a dequeuer is done dequeueing at position N, it sets the sequence number to N + _slots.Length, + // so that when an enqueuer loops around the slots, it'll find that the sequence number at + // position N is N. This also means that when an enqueuer finds that at position N the sequence + // number is < N, there is still a value in that slot, i.e. the segment is full, and when a + // dequeuer finds that the value in a slot is < N + 1, there is nothing currently available to + // dequeue. (It is possible for multiple enqueuers to enqueue concurrently, writing into + // subsequent slots, and to have the first enqueuer take longer, so that the slots for 1, 2, 3, etc. + // may have values, but the 0th slot may still be being filled... in that case, TryDequeue will + // return false.) + for (int i = 0; i < _slots.Length; i++) + { + _slots[i].SequenceNumber = i; + } } - /// <summary> - /// Create a new segment and append to the current one - /// Update the m_tail pointer - /// This method is called when there is no contention - /// </summary> - internal void Grow() - { - //no CAS is needed, since there is no contention (other threads are blocked, busy waiting) - Segment newSegment = new Segment(m_index + 1, m_source); //m_index is Int64, we don't need to worry about overflow - m_next = newSegment; - Debug.Assert(m_source.m_tail == this); - m_source.m_tail = m_next; - } + /// <summary>Gets the number of elements this segment can store.</summary> + internal int Capacity => _slots.Length; + /// <summary>Gets the "freeze offset" for this segment.</summary> + internal int FreezeOffset => _slots.Length * 2; /// <summary> - /// Try to append an element at the end of this segment. + /// Ensures that the segment will not accept any subsequent enqueues that aren't already underway. /// </summary> - /// <param name="value">the element to append</param> - /// <param name="tail">The tail.</param> - /// <returns>true if the element is appended, false if the current segment is full</returns> - /// <remarks>if appending the specified element succeeds, and after which the segment is full, - /// then grow the segment</remarks> - internal bool TryAppend(T value) + /// <remarks> + /// When we mark a segment as being frozen for additional enqueues, + /// we set the <see cref="_frozenForEnqueues"/> bool, but that's mostly + /// as a small helper to avoid marking it twice. The real marking comes + /// by modifying the Tail for the segment, increasing it by this + /// <see cref="FreezeOffset"/>. This effectively knocks it off the + /// sequence expected by future enqueuers, such that any additional enqueuer + /// will be unable to enqueue due to it not lining up with the expected + /// sequence numbers. This value is chosen specially so that Tail will grow + /// to a value that maps to the same slot but that won't be confused with + /// any other enqueue/dequeue sequence number. + /// </remarks> + internal void EnsureFrozenForEnqueues() // must only be called while queue's segment lock is held { - //quickly check if m_high is already over the boundary, if so, bail out - if (m_high >= SEGMENT_SIZE - 1) + if (!_frozenForEnqueues) // flag used to ensure we don't increase the Tail more than once if frozen more than once { - return false; - } + _frozenForEnqueues = true; - //Now we will use a CAS to increment m_high, and store the result in newhigh. - //Depending on how many free spots left in this segment and how many threads are doing this Increment - //at this time, the returning "newhigh" can be - // 1) < SEGMENT_SIZE - 1 : we took a spot in this segment, and not the last one, just insert the value - // 2) == SEGMENT_SIZE - 1 : we took the last spot, insert the value AND grow the segment - // 3) > SEGMENT_SIZE - 1 : we failed to reserve a spot in this segment, we return false to - // Queue.Enqueue method, telling it to try again in the next segment. - - int newhigh = SEGMENT_SIZE; //initial value set to be over the boundary - - //We need do Interlocked.Increment and value/state update in a finally block to ensure that they run - //without interuption. This is to prevent anything from happening between them, and another dequeue - //thread maybe spinning forever to wait for m_state[] to be true; - try - { } - finally - { - newhigh = Interlocked.Increment(ref m_high); - if (newhigh <= SEGMENT_SIZE - 1) + // Increase the tail by FreezeOffset, spinning until we're successful in doing so. + var spinner = new SpinWait(); + while (true) { - m_array[newhigh] = value; - m_state[newhigh].m_value = true; - } - - //if this thread takes up the last slot in the segment, then this thread is responsible - //to grow a new segment. Calling Grow must be in the finally block too for reliability reason: - //if thread abort during Grow, other threads will be left busy spinning forever. - if (newhigh == SEGMENT_SIZE - 1) - { - Grow(); + int tail = Volatile.Read(ref _headAndTail.Tail); + if (Interlocked.CompareExchange(ref _headAndTail.Tail, tail + FreezeOffset, tail) == tail) + { + break; + } + spinner.SpinOnce(); } } - - //if newhigh <= SEGMENT_SIZE-1, it means the current thread successfully takes up a spot - return newhigh <= SEGMENT_SIZE - 1; } - - /// <summary> - /// try to remove an element from the head of current segment - /// </summary> - /// <param name="result">The result.</param> - /// <param name="head">The head.</param> - /// <returns>return false only if the current segment is empty</returns> - internal bool TryRemove(out T result) + /// <summary>Tries to dequeue an element from the queue.</summary> + public bool TryDequeue(out T item) { - SpinWait spin = new SpinWait(); - int lowLocal = Low, highLocal = High; - while (lowLocal <= highLocal) + // Loop in case of contention... + var spinner = new SpinWait(); + while (true) { - //try to update m_low - if (Interlocked.CompareExchange(ref m_low, lowLocal + 1, lowLocal) == lowLocal) - { - //if the specified value is not available (this spot is taken by a push operation, - // but the value is not written into yet), then spin - SpinWait spinLocal = new SpinWait(); - while (!m_state[lowLocal].m_value) - { - spinLocal.SpinOnce(); - } - result = m_array[lowLocal]; + // Get the head at which to try to dequeue. + int currentHead = Volatile.Read(ref _headAndTail.Head); + int slotsIndex = currentHead & _slotsMask; - // If there is no other thread taking snapshot (GetEnumerator(), ToList(), etc), reset the deleted entry to null. - // It is ok if after this conditional check m_numSnapshotTakers becomes > 0, because new snapshots won't include - // the deleted entry at m_array[lowLocal]. - if (m_source.m_numSnapshotTakers <= 0) - { - m_array[lowLocal] = default(T); //release the reference to the object. - } + // Read the sequence number for the head position. + int sequenceNumber = Volatile.Read(ref _slots[slotsIndex].SequenceNumber); - //if the current thread sets m_low to SEGMENT_SIZE, which means the current segment becomes - //disposable, then this thread is responsible to dispose this segment, and reset m_head - if (lowLocal + 1 >= SEGMENT_SIZE) + // We can dequeue from this slot if it's been filled by an enqueuer, which + // would have left the sequence number at pos+1. + int diff = sequenceNumber - (currentHead + 1); + if (diff == 0) + { + // We may be racing with other dequeuers. Try to reserve the slot by incrementing + // the head. Once we've done that, no one else will be able to read from this slot, + // and no enqueuer will be able to read from this slot until we've written the new + // sequence number. WARNING: The next few lines are not reliable on a runtime that + // supports thread aborts. If a thread abort were to sneak in after the CompareExchange + // but before the Volatile.Write, enqueuers trying to enqueue into this slot would + // spin indefinitely. If this implementation is ever used on such a platform, this + // if block should be wrapped in a finally / prepared region. + if (Interlocked.CompareExchange(ref _headAndTail.Head, currentHead + 1, currentHead) == currentHead) { - // Invariant: we only dispose the current m_head, not any other segment - // In usual situation, disposing a segment is simply seting m_head to m_head.m_next - // But there is one special case, where m_head and m_tail points to the same and ONLY - //segment of the queue: Another thread A is doing Enqueue and finds that it needs to grow, - //while the *current* thread is doing *this* Dequeue operation, and finds that it needs to - //dispose the current (and ONLY) segment. Then we need to wait till thread A finishes its - //Grow operation, this is the reason of having the following while loop - spinLocal = new SpinWait(); - while (m_next == null) + // Successfully reserved the slot. Note that after the above CompareExchange, other threads + // trying to dequeue from this slot will end up spinning until we do the subsequent Write. + item = _slots[slotsIndex].Item; + if (!Volatile.Read(ref _preservedForObservation)) { - spinLocal.SpinOnce(); + // If we're preserving, though, we don't zero out the slot, as we need it for + // enumerations, peeking, ToArray, etc. And we don't update the sequence number, + // so that an enqueuer will see it as full and be forced to move to a new segment. + _slots[slotsIndex].Item = default(T); + Volatile.Write(ref _slots[slotsIndex].SequenceNumber, currentHead + _slots.Length); } - Debug.Assert(m_source.m_head == this); - m_source.m_head = m_next; + return true; } - return true; } - else + else if (diff < 0) { - //CAS failed due to contention: spin briefly and retry - spin.SpinOnce(); - lowLocal = Low; highLocal = High; + // The sequence number was less than what we needed, which means this slot doesn't + // yet contain a value we can dequeue, i.e. the segment is empty. Technically it's + // possible that multiple enqueuers could have written concurrently, with those + // getting later slots actually finishing first, so there could be elements after + // this one that are available, but we need to dequeue in order. So before declaring + // failure and that the segment is empty, we check the tail to see if we're actually + // empty or if we're just waiting for items in flight or after this one to become available. + bool frozen = _frozenForEnqueues; + int currentTail = Volatile.Read(ref _headAndTail.Tail); + if (currentTail - currentHead <= 0 || (frozen && (currentTail - FreezeOffset - currentHead <= 0))) + { + item = default(T); + return false; + } + + // It's possible it could have become frozen after we checked _frozenForEnqueues + // and before reading the tail. That's ok: in that rare race condition, we just + // loop around again. } - }//end of while - result = default(T); - return false; + + // Lost a race. Spin a bit, then try again. + spinner.SpinOnce(); + } } - /// <summary> - /// try to peek the current segment - /// </summary> - /// <param name="result">holds the return value of the element at the head position, - /// value set to default(T) if there is no such an element</param> - /// <returns>true if there are elements in the current segment, false otherwise</returns> - internal bool TryPeek(out T result) + /// <summary>Tries to peek at an element from the queue, without removing it.</summary> + public bool TryPeek(out T result, bool resultUsed) { - result = default(T); - int lowLocal = Low; - if (lowLocal > High) - return false; - SpinWait spin = new SpinWait(); - while (!m_state[lowLocal].m_value) + if (resultUsed) { - spin.SpinOnce(); + // In order to ensure we don't get a torn read on the value, we mark the segment + // as preserving for observation. Additional items can still be enqueued to this + // segment, but no space will be freed during dequeues, such that the segment will + // no longer be reusable. + _preservedForObservation = true; + Interlocked.MemoryBarrier(); } - result = m_array[lowLocal]; - return true; - } - /// <summary> - /// Adds part or all of the current segment into a List. - /// </summary> - /// <param name="list">the list to which to add</param> - /// <param name="start">the start position</param> - /// <param name="end">the end position</param> - internal void AddToList(List<T> list, int start, int end) - { - for (int i = start; i <= end; i++) + // Loop in case of contention... + var spinner = new SpinWait(); + while (true) { - SpinWait spin = new SpinWait(); - while (!m_state[i].m_value) + // Get the head at which to try to peek. + int currentHead = Volatile.Read(ref _headAndTail.Head); + int slotsIndex = currentHead & _slotsMask; + + // Read the sequence number for the head position. + int sequenceNumber = Volatile.Read(ref _slots[slotsIndex].SequenceNumber); + + // We can peek from this slot if it's been filled by an enqueuer, which + // would have left the sequence number at pos+1. + int diff = sequenceNumber - (currentHead + 1); + if (diff == 0) { - spin.SpinOnce(); + result = resultUsed ? _slots[slotsIndex].Item : default(T); + return true; + } + else if (diff < 0) + { + // The sequence number was less than what we needed, which means this slot doesn't + // yet contain a value we can peek, i.e. the segment is empty. Technically it's + // possible that multiple enqueuers could have written concurrently, with those + // getting later slots actually finishing first, so there could be elements after + // this one that are available, but we need to peek in order. So before declaring + // failure and that the segment is empty, we check the tail to see if we're actually + // empty or if we're just waiting for items in flight or after this one to become available. + bool frozen = _frozenForEnqueues; + int currentTail = Volatile.Read(ref _headAndTail.Tail); + if (currentTail - currentHead <= 0 || (frozen && (currentTail - FreezeOffset - currentHead <= 0))) + { + result = default(T); + return false; + } + + // It's possible it could have become frozen after we checked _frozenForEnqueues + // and before reading the tail. That's ok: in that rare race condition, we just + // loop around again. } - list.Add(m_array[i]); + + // Lost a race. Spin a bit, then try again. + spinner.SpinOnce(); } } /// <summary> - /// return the position of the head of the current segment - /// Value range [0, SEGMENT_SIZE], if it's SEGMENT_SIZE, it means this segment is exhausted and thus empty + /// Attempts to enqueue the item. If successful, the item will be stored + /// in the queue and true will be returned; otherwise, the item won't be stored, and false + /// will be returned. /// </summary> - internal int Low + public bool TryEnqueue(T item) { - get + // Loop in case of contention... + var spinner = new SpinWait(); + while (true) { - return Math.Min(m_low, SEGMENT_SIZE); + // Get the tail at which to try to return. + int currentTail = Volatile.Read(ref _headAndTail.Tail); + int slotsIndex = currentTail & _slotsMask; + + // Read the sequence number for the tail position. + int sequenceNumber = Volatile.Read(ref _slots[slotsIndex].SequenceNumber); + + // The slot is empty and ready for us to enqueue into it if its sequence + // number matches the slot. + int diff = sequenceNumber - currentTail; + if (diff == 0) + { + // We may be racing with other enqueuers. Try to reserve the slot by incrementing + // the tail. Once we've done that, no one else will be able to write to this slot, + // and no dequeuer will be able to read from this slot until we've written the new + // sequence number. WARNING: The next few lines are not reliable on a runtime that + // supports thread aborts. If a thread abort were to sneak in after the CompareExchange + // but before the Volatile.Write, other threads will spin trying to access this slot. + // If this implementation is ever used on such a platform, this if block should be + // wrapped in a finally / prepared region. + if (Interlocked.CompareExchange(ref _headAndTail.Tail, currentTail + 1, currentTail) == currentTail) + { + // Successfully reserved the slot. Note that after the above CompareExchange, other threads + // trying to return will end up spinning until we do the subsequent Write. + _slots[slotsIndex].Item = item; + Volatile.Write(ref _slots[slotsIndex].SequenceNumber, currentTail + 1); + return true; + } + } + else if (diff < 0) + { + // The sequence number was less than what we needed, which means this slot still + // contains a value, i.e. the segment is full. Technically it's possible that multiple + // dequeuers could have read concurrently, with those getting later slots actually + // finishing first, so there could be spaces after this one that are available, but + // we need to enqueue in order. + return false; + } + + // Lost a race. Spin a bit, then try again. + spinner.SpinOnce(); } } - /// <summary> - /// return the logical position of the tail of the current segment - /// Value range [-1, SEGMENT_SIZE-1]. When it's -1, it means this is a new segment and has no elemnet yet - /// </summary> - internal int High + /// <summary>Represents a slot in the queue.</summary> + [StructLayout(LayoutKind.Auto)] + [DebuggerDisplay("Item = {Item}, SequenceNumber = {SequenceNumber}")] + internal struct Slot { - get - { - //if m_high > SEGMENT_SIZE, it means it's out of range, we should return - //SEGMENT_SIZE-1 as the logical position - return Math.Min(m_high, SEGMENT_SIZE - 1); - } + /// <summary>The item.</summary> + public T Item; + /// <summary>The sequence number for this slot, used to synchronize between enqueuers and dequeuers.</summary> + public int SequenceNumber; } - } - }//end of class Segment + } - /// <summary> - /// A wrapper struct for volatile bool, please note the copy of the struct it self will not be volatile - /// for example this statement will not include in volatilness operation volatileBool1 = volatileBool2 the jit will copy the struct and will ignore the volatile - /// </summary> - struct VolatileBool + /// <summary>Padded head and tail indices, to avoid false sharing between producers and consumers.</summary> + [DebuggerDisplay("Head = {Head}, Tail = {Tail}")] + [StructLayout(LayoutKind.Explicit, Size = 192)] // padding before/between/after fields based on typical cache line size of 64 + internal struct PaddedHeadAndTail { - public VolatileBool(bool value) - { - m_value = value; - } - public volatile bool m_value; + [FieldOffset(64)] public int Head; + [FieldOffset(128)] public int Tail; } } diff --git a/src/mscorlib/src/System/Collections/Concurrent/ConcurrentStack.cs b/src/mscorlib/src/System/Collections/Concurrent/ConcurrentStack.cs index c36d96c26c..10a5201f6c 100644 --- a/src/mscorlib/src/System/Collections/Concurrent/ConcurrentStack.cs +++ b/src/mscorlib/src/System/Collections/Concurrent/ConcurrentStack.cs @@ -20,7 +20,6 @@ using System.Diagnostics.Contracts; using System.Runtime.ConstrainedExecution; using System.Runtime.Serialization; using System.Security; -using System.Security.Permissions; using System.Threading; namespace System.Collections.Concurrent @@ -45,7 +44,7 @@ namespace System.Collections.Concurrent /// </remarks> [DebuggerDisplay("Count = {Count}")] [DebuggerTypeProxy(typeof(SystemCollectionsConcurrent_ProducerConsumerCollectionDebugView<>))] - public class ConcurrentStack<T> : IProducerConsumerCollection<T>, IReadOnlyCollection<T> + internal class ConcurrentStack<T> : IProducerConsumerCollection<T>, IReadOnlyCollection<T> { /// <summary> /// A simple (internal) node type used to store elements of concurrent stacks and queues. @@ -79,61 +78,6 @@ namespace System.Collections.Concurrent } /// <summary> - /// Initializes a new instance of the <see cref="ConcurrentStack{T}"/> - /// class that contains elements copied from the specified collection - /// </summary> - /// <param name="collection">The collection whose elements are copied to the new <see - /// cref="ConcurrentStack{T}"/>.</param> - /// <exception cref="T:System.ArgumentNullException">The <paramref name="collection"/> argument is - /// null.</exception> - public ConcurrentStack(IEnumerable<T> collection) - { - if (collection == null) - { - throw new ArgumentNullException(nameof(collection)); - } - InitializeFromCollection(collection); - } - - /// <summary> - /// Initializes the contents of the stack from an existing collection. - /// </summary> - /// <param name="collection">A collection from which to copy elements.</param> - private void InitializeFromCollection(IEnumerable<T> collection) - { - // We just copy the contents of the collection to our stack. - Node lastNode = null; - foreach (T element in collection) - { - Node newNode = new Node(element); - newNode.m_next = lastNode; - lastNode = newNode; - } - - m_head = lastNode; - } - - /// <summary> - /// Gets a value that indicates whether the <see cref="ConcurrentStack{T}"/> is empty. - /// </summary> - /// <value>true if the <see cref="ConcurrentStack{T}"/> is empty; otherwise, false.</value> - /// <remarks> - /// For determining whether the collection contains any items, use of this property is recommended - /// rather than retrieving the number of items from the <see cref="Count"/> property and comparing it - /// to 0. However, as this collection is intended to be accessed concurrently, it may be the case - /// that another thread will modify the collection after <see cref="IsEmpty"/> returns, thus invalidating - /// the result. - /// </remarks> - public bool IsEmpty - { - // Checks whether the stack is empty. Clearly the answer may be out of date even prior to - // the function returning (i.e. if another thread concurrently adds to the stack). It does - // guarantee, however, that, if another thread does not mutate the stack, a subsequent call - // to TryPop will return true -- i.e. it will also read the stack as non-empty. - get { return m_head == null; } - } - - /// <summary> /// Gets the number of elements contained in the <see cref="ConcurrentStack{T}"/>. /// </summary> /// <value>The number of elements contained in the <see cref="ConcurrentStack{T}"/>.</value> @@ -196,18 +140,6 @@ namespace System.Collections.Concurrent } /// <summary> - /// Removes all objects from the <see cref="ConcurrentStack{T}"/>. - /// </summary> - public void Clear() - { - // Clear the list by setting the head to null. We don't need to use an atomic - // operation for this: anybody who is mutating the head by pushing or popping - // will need to use an atomic operation to guarantee they serialize and don't - // overwrite our setting of the head to null. - m_head = null; - } - - /// <summary> /// Copies the elements of the <see cref="T:System.Collections.ICollection"/> to an <see /// cref="T:System.Array"/>, starting at a particular /// <see cref="T:System.Array"/> index. @@ -306,79 +238,6 @@ namespace System.Collections.Concurrent PushCore(newNode, newNode); } - /// <summary> - /// Inserts multiple objects at the top of the <see cref="ConcurrentStack{T}"/> atomically. - /// </summary> - /// <param name="items">The objects to push onto the <see cref="ConcurrentStack{T}"/>.</param> - /// <exception cref="ArgumentNullException"><paramref name="items"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <remarks> - /// When adding multiple items to the stack, using PushRange is a more efficient - /// mechanism than using <see cref="Push"/> one item at a time. Additionally, PushRange - /// guarantees that all of the elements will be added atomically, meaning that no other threads will - /// be able to inject elements between the elements being pushed. Items at lower indices in - /// the <paramref name="items"/> array will be pushed before items at higher indices. - /// </remarks> - public void PushRange(T[] items) - { - if (items == null) - { - throw new ArgumentNullException(nameof(items)); - } - PushRange(items, 0, items.Length); - } - - /// <summary> - /// Inserts multiple objects at the top of the <see cref="ConcurrentStack{T}"/> atomically. - /// </summary> - /// <param name="items">The objects to push onto the <see cref="ConcurrentStack{T}"/>.</param> - /// <param name="startIndex">The zero-based offset in <paramref name="items"/> at which to begin - /// inserting elements onto the top of the <see cref="ConcurrentStack{T}"/>.</param> - /// <param name="count">The number of elements to be inserted onto the top of the <see - /// cref="ConcurrentStack{T}"/>.</param> - /// <exception cref="ArgumentNullException"><paramref name="items"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="ArgumentOutOfRangeException"><paramref name="startIndex"/> or <paramref - /// name="count"/> is negative. Or <paramref name="startIndex"/> is greater than or equal to the length - /// of <paramref name="items"/>.</exception> - /// <exception cref="ArgumentException"><paramref name="startIndex"/> + <paramref name="count"/> is - /// greater than the length of <paramref name="items"/>.</exception> - /// <remarks> - /// When adding multiple items to the stack, using PushRange is a more efficient - /// mechanism than using <see cref="Push"/> one item at a time. Additionally, PushRange - /// guarantees that all of the elements will be added atomically, meaning that no other threads will - /// be able to inject elements between the elements being pushed. Items at lower indices in the - /// <paramref name="items"/> array will be pushed before items at higher indices. - /// </remarks> - public void PushRange(T[] items, int startIndex, int count) - { - ValidatePushPopRangeInput(items, startIndex, count); - - // No op if the count is zero - if (count == 0) - return; - - - Node head, tail; - head = tail = new Node(items[startIndex]); - for (int i = startIndex + 1; i < startIndex + count; i++) - { - Node node = new Node(items[i]); - node.m_next = head; - head = node; - } - - tail.m_next = m_head; - if (Interlocked.CompareExchange(ref m_head, head, tail.m_next) == tail.m_next) - { - return; - } - - // If we failed, go to the slow path and loop around until we succeed. - PushCore(head, tail); - - } - /// <summary> /// Push one or many nodes into the stack, if head and tails are equal then push one node to the stack other wise push the list between head @@ -402,73 +261,6 @@ namespace System.Collections.Concurrent } /// <summary> - /// Local helper function to validate the Pop Push range methods input - /// </summary> - private void ValidatePushPopRangeInput(T[] items, int startIndex, int count) - { - if (items == null) - { - throw new ArgumentNullException(nameof(items)); - } - if (count < 0) - { - throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ConcurrentStack_PushPopRange_CountOutOfRange")); - } - int length = items.Length; - if (startIndex >= length || startIndex < 0) - { - throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ConcurrentStack_PushPopRange_StartOutOfRange")); - } - if (length - count < startIndex) //instead of (startIndex + count > items.Length) to prevent overflow - { - throw new ArgumentException(Environment.GetResourceString("ConcurrentStack_PushPopRange_InvalidCount")); - } - } - - /// <summary> - /// Attempts to add an object to the <see - /// cref="T:System.Collections.Concurrent.IProducerConsumerCollection{T}"/>. - /// </summary> - /// <param name="item">The object to add to the <see - /// cref="T:System.Collections.Concurrent.IProducerConsumerCollection{T}"/>. The value can be a null - /// reference (Nothing in Visual Basic) for reference types. - /// </param> - /// <returns>true if the object was added successfully; otherwise, false.</returns> - /// <remarks>For <see cref="ConcurrentStack{T}"/>, this operation - /// will always insert the object onto the top of the <see cref="ConcurrentStack{T}"/> - /// and return true.</remarks> - bool IProducerConsumerCollection<T>.TryAdd(T item) - { - Push(item); - return true; - } - - /// <summary> - /// Attempts to return an object from the top of the <see cref="ConcurrentStack{T}"/> - /// without removing it. - /// </summary> - /// <param name="result">When this method returns, <paramref name="result"/> contains an object from - /// the top of the <see cref="T:System.Collections.Concurrent.ConccurrentStack{T}"/> or an - /// unspecified value if the operation failed.</param> - /// <returns>true if and object was returned successfully; otherwise, false.</returns> - public bool TryPeek(out T result) - { - Node head = m_head; - - // If the stack is empty, return false; else return the element and true. - if (head == null) - { - result = default(T); - return false; - } - else - { - result = head.m_value; - return true; - } - } - - /// <summary> /// Attempts to pop and return the object at the top of the <see cref="ConcurrentStack{T}"/>. /// </summary> /// <param name="result"> @@ -498,83 +290,6 @@ namespace System.Collections.Concurrent } /// <summary> - /// Attempts to pop and return multiple objects from the top of the <see cref="ConcurrentStack{T}"/> - /// atomically. - /// </summary> - /// <param name="items"> - /// The <see cref="T:System.Array"/> to which objects popped from the top of the <see - /// cref="ConcurrentStack{T}"/> will be added. - /// </param> - /// <returns>The number of objects successfully popped from the top of the <see - /// cref="ConcurrentStack{T}"/> and inserted in - /// <paramref name="items"/>.</returns> - /// <exception cref="ArgumentNullException"><paramref name="items"/> is a null argument (Nothing - /// in Visual Basic).</exception> - /// <remarks> - /// When popping multiple items, if there is little contention on the stack, using - /// TryPopRange can be more efficient than using <see cref="TryPop"/> - /// once per item to be removed. Nodes fill the <paramref name="items"/> - /// with the first node to be popped at the startIndex, the second node to be popped - /// at startIndex + 1, and so on. - /// </remarks> - public int TryPopRange(T[] items) - { - if (items == null) - { - throw new ArgumentNullException(nameof(items)); - } - - return TryPopRange(items, 0, items.Length); - } - - /// <summary> - /// Attempts to pop and return multiple objects from the top of the <see cref="ConcurrentStack{T}"/> - /// atomically. - /// </summary> - /// <param name="items"> - /// The <see cref="T:System.Array"/> to which objects popped from the top of the <see - /// cref="ConcurrentStack{T}"/> will be added. - /// </param> - /// <param name="startIndex">The zero-based offset in <paramref name="items"/> at which to begin - /// inserting elements from the top of the <see cref="ConcurrentStack{T}"/>.</param> - /// <param name="count">The number of elements to be popped from top of the <see - /// cref="ConcurrentStack{T}"/> and inserted into <paramref name="items"/>.</param> - /// <returns>The number of objects successfully popped from the top of - /// the <see cref="ConcurrentStack{T}"/> and inserted in <paramref name="items"/>.</returns> - /// <exception cref="ArgumentNullException"><paramref name="items"/> is a null reference - /// (Nothing in Visual Basic).</exception> - /// <exception cref="ArgumentOutOfRangeException"><paramref name="startIndex"/> or <paramref - /// name="count"/> is negative. Or <paramref name="startIndex"/> is greater than or equal to the length - /// of <paramref name="items"/>.</exception> - /// <exception cref="ArgumentException"><paramref name="startIndex"/> + <paramref name="count"/> is - /// greater than the length of <paramref name="items"/>.</exception> - /// <remarks> - /// When popping multiple items, if there is little contention on the stack, using - /// TryPopRange can be more efficient than using <see cref="TryPop"/> - /// once per item to be removed. Nodes fill the <paramref name="items"/> - /// with the first node to be popped at the startIndex, the second node to be popped - /// at startIndex + 1, and so on. - /// </remarks> - public int TryPopRange(T[] items, int startIndex, int count) - { - ValidatePushPopRangeInput(items, startIndex, count); - - // No op if the count is zero - if (count == 0) - return 0; - - Node poppedHead; - int nodesCount = TryPopCore(count, out poppedHead); - if (nodesCount > 0) - { - CopyRemovedItems(poppedHead, items, startIndex, nodesCount); - - } - return nodesCount; - - } - - /// <summary> /// Local helper function to Pop an item from the stack, slow path /// </summary> /// <param name="result">The popped item</param> @@ -648,42 +363,6 @@ namespace System.Collections.Concurrent } } - - /// <summary> - /// Local helper function to copy the poped elements into a given collection - /// </summary> - /// <param name="head">The head of the list to be copied</param> - /// <param name="collection">The collection to place the popped items in</param> - /// <param name="startIndex">the beginning of index of where to place the popped items</param> - /// <param name="nodesCount">The number of nodes.</param> - private void CopyRemovedItems(Node head, T[] collection, int startIndex, int nodesCount) - { - Node current = head; - for (int i = startIndex; i < startIndex + nodesCount; i++) - { - collection[i] = current.m_value; - current = current.m_next; - } - - } - - /// <summary> - /// Attempts to remove and return an object from the <see - /// cref="T:System.Collections.Concurrent.IProducerConsumerCollection{T}"/>. - /// </summary> - /// <param name="item"> - /// When this method returns, if the operation was successful, <paramref name="item"/> contains the - /// object removed. If no object was available to be removed, the value is unspecified. - /// </param> - /// <returns>true if an element was removed and returned succesfully; otherwise, false.</returns> - /// <remarks>For <see cref="ConcurrentStack{T}"/>, this operation will attempt to pope the object at - /// the top of the <see cref="ConcurrentStack{T}"/>. - /// </remarks> - bool IProducerConsumerCollection<T>.TryTake(out T item) - { - return TryPop(out item); - } - /// <summary> /// Copies the items stored in the <see cref="ConcurrentStack{T}"/> to a new array. /// </summary> diff --git a/src/mscorlib/src/System/Collections/Concurrent/IProducerConsumerCollection.cs b/src/mscorlib/src/System/Collections/Concurrent/IProducerConsumerCollection.cs index 56be7759c9..0347ece0ec 100644 --- a/src/mscorlib/src/System/Collections/Concurrent/IProducerConsumerCollection.cs +++ b/src/mscorlib/src/System/Collections/Concurrent/IProducerConsumerCollection.cs @@ -25,9 +25,8 @@ namespace System.Collections.Concurrent /// All implementations of this interface must enable all members of this interface /// to be used concurrently from multiple threads. /// </remarks> - public interface IProducerConsumerCollection<T> : IEnumerable<T>, ICollection + internal interface IProducerConsumerCollection<T> : IEnumerable<T>, ICollection { - /// <summary> /// Copies the elements of the <see cref="IProducerConsumerCollection{T}"/> to /// an @@ -51,35 +50,12 @@ namespace System.Collections.Concurrent void CopyTo(T[] array, int index); /// <summary> - /// Attempts to add an object to the <see - /// cref="IProducerConsumerCollection{T}"/>. - /// </summary> - /// <param name="item">The object to add to the <see - /// cref="IProducerConsumerCollection{T}"/>.</param> - /// <returns>true if the object was added successfully; otherwise, false.</returns> - /// <exception cref="T:System.ArgumentException">The <paramref name="item"/> was invalid for this collection.</exception> - bool TryAdd(T item); - - /// <summary> - /// Attempts to remove and return an object from the <see cref="IProducerConsumerCollection{T}"/>. - /// </summary> - /// <param name="item"> - /// When this method returns, if the object was removed and returned successfully, <paramref - /// name="item"/> contains the removed object. If no object was available to be removed, the value is - /// unspecified. - /// </param> - /// <returns>true if an object was removed and returned successfully; otherwise, false.</returns> - bool TryTake(out T item); - - /// <summary> /// Copies the elements contained in the <see cref="IProducerConsumerCollection{T}"/> to a new array. /// </summary> /// <returns>A new array containing the elements copied from the <see cref="IProducerConsumerCollection{T}"/>.</returns> T[] ToArray(); - } - /// <summary> /// A debugger view of the IProducerConsumerCollection that makes it simple to browse the /// collection's contents at a point in time. @@ -89,28 +65,5 @@ namespace System.Collections.Concurrent { private IProducerConsumerCollection<T> m_collection; // The collection being viewed. - /// <summary> - /// Constructs a new debugger view object for the provided collection object. - /// </summary> - /// <param name="collection">A collection to browse in the debugger.</param> - public SystemCollectionsConcurrent_ProducerConsumerCollectionDebugView(IProducerConsumerCollection<T> collection) - { - if (collection == null) - { - throw new ArgumentNullException(nameof(collection)); - } - - m_collection = collection; - } - - /// <summary> - /// Returns a snapshot of the underlying collection's elements. - /// </summary> - [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] - public T[] Items - { - get { return m_collection.ToArray(); } - } - } } diff --git a/src/mscorlib/src/System/Collections/Concurrent/OrderablePartitioner.cs b/src/mscorlib/src/System/Collections/Concurrent/OrderablePartitioner.cs deleted file mode 100644 index 33e3c88e9a..0000000000 --- a/src/mscorlib/src/System/Collections/Concurrent/OrderablePartitioner.cs +++ /dev/null @@ -1,280 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ -// -// -// -// -// -// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- - -using System; -using System.Collections.Generic; -using System.Security.Permissions; -using System.Threading; - -namespace System.Collections.Concurrent -{ - - /// <summary> - /// Represents a particular manner of splitting an orderable data source into multiple partitions. - /// </summary> - /// <typeparam name="TSource">Type of the elements in the collection.</typeparam> - /// <remarks> - /// <para> - /// Each element in each partition has an integer index associated with it, which determines the relative - /// order of that element against elements in other partitions. - /// </para> - /// <para> - /// Inheritors of <see cref="OrderablePartitioner{TSource}"/> must adhere to the following rules: - /// <ol> - /// <li>All indices must be unique, such that there may not be duplicate indices. If all indices are not - /// unique, the output ordering may be scrambled.</li> - /// <li>All indices must be non-negative. If any indices are negative, consumers of the implementation - /// may throw exceptions.</li> - /// <li><see cref="GetPartitions"/> and <see cref="GetOrderablePartitions"/> should throw a - /// <see cref="T:System.ArgumentOutOfRangeException"/> if the requested partition count is less than or - /// equal to zero.</li> - /// <li><see cref="GetPartitions"/> and <see cref="GetOrderablePartitions"/> should always return a number - /// of enumerables equal to the requested partition count. If the partitioner runs out of data and cannot - /// create as many partitions as requested, an empty enumerator should be returned for each of the - /// remaining partitions. If this rule is not followed, consumers of the implementation may throw a <see - /// cref="T:System.InvalidOperationException"/>.</li> - /// <li><see cref="GetPartitions"/>, <see cref="GetOrderablePartitions"/>, - /// <see cref="GetDynamicPartitions"/>, and <see cref="GetOrderableDynamicPartitions"/> - /// should never return null. If null is returned, a consumer of the implementation may throw a - /// <see cref="T:System.InvalidOperationException"/>.</li> - /// <li><see cref="GetPartitions"/>, <see cref="GetOrderablePartitions"/>, - /// <see cref="GetDynamicPartitions"/>, and <see cref="GetOrderableDynamicPartitions"/> - /// should always return partitions that can fully and uniquely enumerate the input data source. All of - /// the data and only the data contained in the input source should be enumerated, with no duplication - /// that was not already in the input, unless specifically required by the particular partitioner's - /// design. If this is not followed, the output ordering may be scrambled.</li> - /// <li>If <see cref="KeysOrderedInEachPartition"/> returns true, each partition must return elements - /// with increasing key indices.</li> - /// <li>If <see cref="KeysOrderedAcrossPartitions"/> returns true, all the keys in partition numbered N - /// must be larger than all the keys in partition numbered N-1.</li> - /// <li>If <see cref="KeysNormalized"/> returns true, all indices must be monotonically increasing from - /// 0, though not necessarily within a single partition.</li> - /// </ol> - /// </para> - /// </remarks> - public abstract class OrderablePartitioner<TSource> : Partitioner<TSource> - { - /// <summary> - /// Initializes a new instance of the <see cref="OrderablePartitioner{TSource}"/> class with the - /// specified constraints on the index keys. - /// </summary> - /// <param name="keysOrderedInEachPartition"> - /// Indicates whether the elements in each partition are yielded in the order of - /// increasing keys. - /// </param> - /// <param name="keysOrderedAcrossPartitions"> - /// Indicates whether elements in an earlier partition always come before - /// elements in a later partition. If true, each element in partition 0 has a smaller order key than - /// any element in partition 1, each element in partition 1 has a smaller order key than any element - /// in partition 2, and so on. - /// </param> - /// <param name="keysNormalized"> - /// Indicates whether keys are normalized. If true, all order keys are distinct - /// integers in the range [0 .. numberOfElements-1]. If false, order keys must still be dictinct, but - /// only their relative order is considered, not their absolute values. - /// </param> - protected OrderablePartitioner(bool keysOrderedInEachPartition, bool keysOrderedAcrossPartitions, bool keysNormalized) - { - KeysOrderedInEachPartition = keysOrderedInEachPartition; - KeysOrderedAcrossPartitions = keysOrderedAcrossPartitions; - KeysNormalized = keysNormalized; - } - - /// <summary> - /// Partitions the underlying collection into the specified number of orderable partitions. - /// </summary> - /// <remarks> - /// Each partition is represented as an enumerator over key-value pairs. - /// The value of the pair is the element itself, and the key is an integer which determines - /// the relative ordering of this element against other elements in the data source. - /// </remarks> - /// <param name="partitionCount">The number of partitions to create.</param> - /// <returns>A list containing <paramref name="partitionCount"/> enumerators.</returns> - public abstract IList<IEnumerator<KeyValuePair<long, TSource>>> GetOrderablePartitions(int partitionCount); - - /// <summary> - /// Creates an object that can partition the underlying collection into a variable number of - /// partitions. - /// </summary> - /// <remarks> - /// <para> - /// The returned object implements the <see - /// cref="T:System.Collections.Generic.IEnumerable{TSource}"/> interface. Calling <see - /// cref="System.Collections.Generic.IEnumerable{TSource}.GetEnumerator">GetEnumerator</see> on the - /// object creates another partition over the sequence. - /// </para> - /// <para> - /// Each partition is represented as an enumerator over key-value pairs. The value in the pair is the element - /// itself, and the key is an integer which determines the relative ordering of this element against - /// other elements. - /// </para> - /// <para> - /// The <see cref="GetOrderableDynamicPartitions"/> method is only supported if the <see - /// cref="System.Collections.Concurrent.Partitioner{TSource}.SupportsDynamicPartitions">SupportsDynamicPartitions</see> - /// property returns true. - /// </para> - /// </remarks> - /// <returns>An object that can create partitions over the underlying data source.</returns> - /// <exception cref="NotSupportedException">Dynamic partitioning is not supported by this - /// partitioner.</exception> - public virtual IEnumerable<KeyValuePair<long, TSource>> GetOrderableDynamicPartitions() - { - throw new NotSupportedException(Environment.GetResourceString("Partitioner_DynamicPartitionsNotSupported")); - } - - /// <summary> - /// Gets whether elements in each partition are yielded in the order of increasing keys. - /// </summary> - public bool KeysOrderedInEachPartition { get; private set; } - - /// <summary> - /// Gets whether elements in an earlier partition always come before elements in a later partition. - /// </summary> - /// <remarks> - /// If <see cref="KeysOrderedAcrossPartitions"/> returns true, each element in partition 0 has a - /// smaller order key than any element in partition 1, each element in partition 1 has a smaller - /// order key than any element in partition 2, and so on. - /// </remarks> - public bool KeysOrderedAcrossPartitions { get; private set; } - - /// <summary> - /// Gets whether order keys are normalized. - /// </summary> - /// <remarks> - /// If <see cref="KeysNormalized"/> returns true, all order keys are distinct integers in the range - /// [0 .. numberOfElements-1]. If the property returns false, order keys must still be dictinct, but - /// only their relative order is considered, not their absolute values. - /// </remarks> - public bool KeysNormalized { get; private set; } - - /// <summary> - /// Partitions the underlying collection into the given number of ordered partitions. - /// </summary> - /// <remarks> - /// The default implementation provides the same behavior as <see cref="GetOrderablePartitions"/> except - /// that the returned set of partitions does not provide the keys for the elements. - /// </remarks> - /// <param name="partitionCount">The number of partitions to create.</param> - /// <returns>A list containing <paramref name="partitionCount"/> enumerators.</returns> - public override IList<IEnumerator<TSource>> GetPartitions(int partitionCount) - { - IList<IEnumerator<KeyValuePair<long, TSource>>> orderablePartitions = GetOrderablePartitions(partitionCount); - - if (orderablePartitions.Count != partitionCount) - { - throw new InvalidOperationException("OrderablePartitioner_GetPartitions_WrongNumberOfPartitions"); - } - - IEnumerator<TSource>[] partitions = new IEnumerator<TSource>[partitionCount]; - for (int i = 0; i < partitionCount; i++) - { - partitions[i] = new EnumeratorDropIndices(orderablePartitions[i]); - } - return partitions; - } - - /// <summary> - /// Creates an object that can partition the underlying collection into a variable number of - /// partitions. - /// </summary> - /// <remarks> - /// <para> - /// The returned object implements the <see - /// cref="T:System.Collections.Generic.IEnumerable{TSource}"/> interface. Calling <see - /// cref="System.Collections.Generic.IEnumerable{TSource}.GetEnumerator">GetEnumerator</see> on the - /// object creates another partition over the sequence. - /// </para> - /// <para> - /// The default implementation provides the same behavior as <see cref="GetOrderableDynamicPartitions"/> except - /// that the returned set of partitions does not provide the keys for the elements. - /// </para> - /// <para> - /// The <see cref="GetDynamicPartitions"/> method is only supported if the <see - /// cref="System.Collections.Concurrent.Partitioner{TSource}.SupportsDynamicPartitions"/> - /// property returns true. - /// </para> - /// </remarks> - /// <returns>An object that can create partitions over the underlying data source.</returns> - /// <exception cref="NotSupportedException">Dynamic partitioning is not supported by this - /// partitioner.</exception> - public override IEnumerable<TSource> GetDynamicPartitions() - { - IEnumerable<KeyValuePair<long, TSource>> orderablePartitions = GetOrderableDynamicPartitions(); - return new EnumerableDropIndices(orderablePartitions); - } - - /// <summary> - /// Converts an enumerable over key-value pairs to an enumerable over values. - /// </summary> - private class EnumerableDropIndices : IEnumerable<TSource>, IDisposable - { - private readonly IEnumerable<KeyValuePair<long, TSource>> m_source; - public EnumerableDropIndices(IEnumerable<KeyValuePair<long, TSource>> source) - { - m_source = source; - } - public IEnumerator<TSource> GetEnumerator() - { - return new EnumeratorDropIndices(m_source.GetEnumerator()); - } - IEnumerator IEnumerable.GetEnumerator() - { - return ((EnumerableDropIndices)this).GetEnumerator(); - } - public void Dispose() - { - IDisposable d = m_source as IDisposable; - if (d != null) - { - d.Dispose(); - } - } - } - - private class EnumeratorDropIndices : IEnumerator<TSource> - { - private readonly IEnumerator<KeyValuePair<long, TSource>> m_source; - public EnumeratorDropIndices(IEnumerator<KeyValuePair<long, TSource>> source) - { - m_source = source; - } - public bool MoveNext() - { - return m_source.MoveNext(); - } - public TSource Current - { - get - { - return m_source.Current.Value; - } - } - Object IEnumerator.Current - { - get - { - return ((EnumeratorDropIndices)this).Current; - } - } - public void Dispose() - { - m_source.Dispose(); - } - public void Reset() - { - m_source.Reset(); - } - } - - } - -} diff --git a/src/mscorlib/src/System/Collections/Concurrent/Partitioner.cs b/src/mscorlib/src/System/Collections/Concurrent/Partitioner.cs deleted file mode 100644 index 0192b1942c..0000000000 --- a/src/mscorlib/src/System/Collections/Concurrent/Partitioner.cs +++ /dev/null @@ -1,101 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ -// -// -// -// Represents a particular way of splitting a collection into multiple partitions. -// -// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- - -using System; -using System.Collections.Generic; -using System.Security.Permissions; -using System.Threading; - -namespace System.Collections.Concurrent -{ - /// <summary> - /// Represents a particular manner of splitting a data source into multiple partitions. - /// </summary> - /// <typeparam name="TSource">Type of the elements in the collection.</typeparam> - /// <remarks> - /// <para> - /// Inheritors of <see cref="Partitioner{TSource}"/> must adhere to the following rules: - /// <ol> - /// <li><see cref="GetPartitions"/> should throw a - /// <see cref="T:System.ArgumentOutOfRangeException"/> if the requested partition count is less than or - /// equal to zero.</li> - /// <li><see cref="GetPartitions"/> should always return a number of enumerables equal to the requested - /// partition count. If the partitioner runs out of data and cannot create as many partitions as - /// requested, an empty enumerator should be returned for each of the remaining partitions. If this rule - /// is not followed, consumers of the implementation may throw a <see - /// cref="T:System.InvalidOperationException"/>.</li> - /// <li><see cref="GetPartitions"/> and <see cref="GetDynamicPartitions"/> - /// should never return null. If null is returned, a consumer of the implementation may throw a - /// <see cref="T:System.InvalidOperationException"/>.</li> - /// <li><see cref="GetPartitions"/> and <see cref="GetDynamicPartitions"/> should always return - /// partitions that can fully and uniquely enumerate the input data source. All of the data and only the - /// data contained in the input source should be enumerated, with no duplication that was not already in - /// the input, unless specifically required by the particular partitioner's design. If this is not - /// followed, the output ordering may be scrambled.</li> - /// </ol> - /// </para> - /// </remarks> - public abstract class Partitioner<TSource> - { - /// <summary> - /// Partitions the underlying collection into the given number of partitions. - /// </summary> - /// <param name="partitionCount">The number of partitions to create.</param> - /// <returns>A list containing <paramref name="partitionCount"/> enumerators.</returns> - public abstract IList<IEnumerator<TSource>> GetPartitions(int partitionCount); - - /// <summary> - /// Gets whether additional partitions can be created dynamically. - /// </summary> - /// <returns> - /// true if the <see cref="Partitioner{TSource}"/> can create partitions dynamically as they are - /// requested; false if the <see cref="Partitioner{TSource}"/> can only allocate - /// partitions statically. - /// </returns> - /// <remarks> - /// <para> - /// If a derived class does not override and implement <see cref="GetDynamicPartitions"/>, - /// <see cref="SupportsDynamicPartitions"/> should return false. The value of <see - /// cref="SupportsDynamicPartitions"/> should not vary over the lifetime of this instance. - /// </para> - /// </remarks> - public virtual bool SupportsDynamicPartitions - { - get { return false; } - } - - /// <summary> - /// Creates an object that can partition the underlying collection into a variable number of - /// partitions. - /// </summary> - /// <remarks> - /// <para> - /// The returned object implements the <see - /// cref="T:System.Collections.Generic.IEnumerable{TSource}"/> interface. Calling <see - /// cref="System.Collections.Generic.IEnumerable{TSource}.GetEnumerator">GetEnumerator</see> on the - /// object creates another partition over the sequence. - /// </para> - /// <para> - /// The <see cref="GetDynamicPartitions"/> method is only supported if the <see - /// cref="SupportsDynamicPartitions"/> - /// property returns true. - /// </para> - /// </remarks> - /// <returns>An object that can create partitions over the underlying data source.</returns> - /// <exception cref="NotSupportedException">Dynamic partitioning is not supported by this - /// partitioner.</exception> - public virtual IEnumerable<TSource> GetDynamicPartitions() - { - throw new NotSupportedException(Environment.GetResourceString("Partitioner_DynamicPartitionsNotSupported")); - } - } -} diff --git a/src/mscorlib/src/System/Collections/Concurrent/PartitionerStatic.cs b/src/mscorlib/src/System/Collections/Concurrent/PartitionerStatic.cs deleted file mode 100644 index 9b36c053ad..0000000000 --- a/src/mscorlib/src/System/Collections/Concurrent/PartitionerStatic.cs +++ /dev/null @@ -1,1715 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. -#pragma warning disable 0420 - -// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ -// -// -// -// A class of default partitioners for Partitioner<TSource> -// -// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- - -using System.Collections.Generic; -using System.Security.Permissions; -using System.Threading; -using System.Diagnostics; -using System.Diagnostics.Contracts; -using System.Runtime.InteropServices; - -namespace System.Collections.Concurrent -{ - /// <summary> - /// Out-of-the-box partitioners are created with a set of default behaviors. - /// For example, by default, some form of buffering and chunking will be employed to achieve - /// optimal performance in the common scenario where an IEnumerable<> implementation is fast and - /// non-blocking. These behaviors can be overridden via this enumeration. - /// </summary> - [Flags] - public enum EnumerablePartitionerOptions - { - /// <summary> - /// Use the default behavior (i.e., use buffering to achieve optimal performance) - /// </summary> - None = 0x0, - - /// <summary> - /// Creates a partitioner that will take items from the source enumerable one at a time - /// and will not use intermediate storage that can be accessed more efficiently by multiple threads. - /// This option provides support for low latency (items will be processed as soon as they are available from - /// the source) and partial support for dependencies between items (a thread cannot deadlock waiting for an item - /// that it, itself, is responsible for processing). - /// </summary> - NoBuffering = 0x1 - } - - // The static class Partitioners implements 3 default partitioning strategies: - // 1. dynamic load balance partitioning for indexable data source (IList and arrays) - // 2. static partitioning for indexable data source (IList and arrays) - // 3. dynamic load balance partitioning for enumerables. Enumerables have indexes, which are the natural order - // of elements, but enuemrators are not indexable - // - data source of type IList/arrays have both dynamic and static partitioning, as 1 and 3. - // We assume that the source data of IList/Array is not changing concurrently. - // - data source of type IEnumerable can only be partitioned dynamically (load-balance) - // - Dynamic partitioning methods 1 and 3 are same, both being dynamic and load-balance. But the - // implementation is different for data source of IList/Array vs. IEnumerable: - // * When the source collection is IList/Arrays, we use Interlocked on the shared index; - // * When the source collection is IEnumerable, we use Monitor to wrap around the access to the source - // enumerator. - - /// <summary> - /// Provides common partitioning strategies for arrays, lists, and enumerables. - /// </summary> - /// <remarks> - /// <para> - /// The static methods on <see cref="Partitioner"/> are all thread-safe and may be used concurrently - /// from multiple threads. However, while a created partitioner is in use, the underlying data source - /// should not be modified, whether from the same thread that's using a partitioner or from a separate - /// thread. - /// </para> - /// </remarks> - public static class Partitioner - { - /// <summary> - /// Creates an orderable partitioner from an <see cref="System.Collections.Generic.IList{T}"/> - /// instance. - /// </summary> - /// <typeparam name="TSource">Type of the elements in source list.</typeparam> - /// <param name="list">The list to be partitioned.</param> - /// <param name="loadBalance"> - /// A Boolean value that indicates whether the created partitioner should dynamically - /// load balance between partitions rather than statically partition. - /// </param> - /// <returns> - /// An orderable partitioner based on the input list. - /// </returns> - public static OrderablePartitioner<TSource> Create<TSource>(IList<TSource> list, bool loadBalance) - { - if (list == null) - { - throw new ArgumentNullException(nameof(list)); - } - if (loadBalance) - { - return (new DynamicPartitionerForIList<TSource>(list)); - } - else - { - return (new StaticIndexRangePartitionerForIList<TSource>(list)); - } - } - - /// <summary> - /// Creates an orderable partitioner from a <see cref="System.Array"/> instance. - /// </summary> - /// <typeparam name="TSource">Type of the elements in source array.</typeparam> - /// <param name="array">The array to be partitioned.</param> - /// <param name="loadBalance"> - /// A Boolean value that indicates whether the created partitioner should dynamically load balance - /// between partitions rather than statically partition. - /// </param> - /// <returns> - /// An orderable partitioner based on the input array. - /// </returns> - public static OrderablePartitioner<TSource> Create<TSource>(TSource[] array, bool loadBalance) - { - // This implementation uses 'ldelem' instructions for element retrieval, rather than using a - // method call. - - if (array == null) - { - throw new ArgumentNullException(nameof(array)); - } - if (loadBalance) - { - return (new DynamicPartitionerForArray<TSource>(array)); - } - else - { - return (new StaticIndexRangePartitionerForArray<TSource>(array)); - } - } - - /// <summary> - /// Creates an orderable partitioner from a <see cref="System.Collections.Generic.IEnumerable{TSource}"/> instance. - /// </summary> - /// <typeparam name="TSource">Type of the elements in source enumerable.</typeparam> - /// <param name="source">The enumerable to be partitioned.</param> - /// <returns> - /// An orderable partitioner based on the input array. - /// </returns> - /// <remarks> - /// The ordering used in the created partitioner is determined by the natural order of the elements - /// as retrieved from the source enumerable. - /// </remarks> - public static OrderablePartitioner<TSource> Create<TSource>(IEnumerable<TSource> source) - { - return Create<TSource>(source, EnumerablePartitionerOptions.None); - } - - /// <summary> - /// Creates an orderable partitioner from a <see cref="System.Collections.Generic.IEnumerable{TSource}"/> instance. - /// </summary> - /// <typeparam name="TSource">Type of the elements in source enumerable.</typeparam> - /// <param name="source">The enumerable to be partitioned.</param> - /// <param name="partitionerOptions">Options to control the buffering behavior of the partitioner.</param> - /// <exception cref="T:System.ArgumentOutOfRangeException"> - /// The <paramref name="partitionerOptions"/> argument specifies an invalid value for <see - /// cref="T:System.Collections.Concurrent.EnumerablePartitionerOptions"/>. - /// </exception> - /// <returns> - /// An orderable partitioner based on the input array. - /// </returns> - /// <remarks> - /// The ordering used in the created partitioner is determined by the natural order of the elements - /// as retrieved from the source enumerable. - /// </remarks> - public static OrderablePartitioner<TSource> Create<TSource>(IEnumerable<TSource> source, EnumerablePartitionerOptions partitionerOptions) - { - if (source == null) - { - throw new ArgumentNullException(nameof(source)); - } - - if ((partitionerOptions & (~EnumerablePartitionerOptions.NoBuffering)) != 0) - throw new ArgumentOutOfRangeException(nameof(partitionerOptions)); - - return (new DynamicPartitionerForIEnumerable<TSource>(source, partitionerOptions)); - } - - /// <summary>Creates a partitioner that chunks the user-specified range.</summary> - /// <param name="fromInclusive">The lower, inclusive bound of the range.</param> - /// <param name="toExclusive">The upper, exclusive bound of the range.</param> - /// <returns>A partitioner.</returns> - /// <exception cref="T:System.ArgumentOutOfRangeException"> The <paramref name="toExclusive"/> argument is - /// less than or equal to the <paramref name="fromInclusive"/> argument.</exception> - public static OrderablePartitioner<Tuple<long, long>> Create(long fromInclusive, long toExclusive) - { - // How many chunks do we want to divide the range into? If this is 1, then the - // answer is "one chunk per core". Generally, though, you'll achieve better - // load balancing on a busy system if you make it higher than 1. - int coreOversubscriptionRate = 3; - - if (toExclusive <= fromInclusive) throw new ArgumentOutOfRangeException(nameof(toExclusive)); - long rangeSize = (toExclusive - fromInclusive) / - (PlatformHelper.ProcessorCount * coreOversubscriptionRate); - if (rangeSize == 0) rangeSize = 1; - return Partitioner.Create(CreateRanges(fromInclusive, toExclusive, rangeSize), EnumerablePartitionerOptions.NoBuffering); // chunk one range at a time - } - - /// <summary>Creates a partitioner that chunks the user-specified range.</summary> - /// <param name="fromInclusive">The lower, inclusive bound of the range.</param> - /// <param name="toExclusive">The upper, exclusive bound of the range.</param> - /// <param name="rangeSize">The size of each subrange.</param> - /// <returns>A partitioner.</returns> - /// <exception cref="T:System.ArgumentOutOfRangeException"> The <paramref name="toExclusive"/> argument is - /// less than or equal to the <paramref name="fromInclusive"/> argument.</exception> - /// <exception cref="T:System.ArgumentOutOfRangeException"> The <paramref name="rangeSize"/> argument is - /// less than or equal to 0.</exception> - public static OrderablePartitioner<Tuple<long, long>> Create(long fromInclusive, long toExclusive, long rangeSize) - { - if (toExclusive <= fromInclusive) throw new ArgumentOutOfRangeException(nameof(toExclusive)); - if (rangeSize <= 0) throw new ArgumentOutOfRangeException(nameof(rangeSize)); - return Partitioner.Create(CreateRanges(fromInclusive, toExclusive, rangeSize), EnumerablePartitionerOptions.NoBuffering); // chunk one range at a time - } - - // Private method to parcel out range tuples. - private static IEnumerable<Tuple<long, long>> CreateRanges(long fromInclusive, long toExclusive, long rangeSize) - { - // Enumerate all of the ranges - long from, to; - bool shouldQuit = false; - - for (long i = fromInclusive; (i < toExclusive) && !shouldQuit; i += rangeSize) - { - from = i; - try { checked { to = i + rangeSize; } } - catch (OverflowException) - { - to = toExclusive; - shouldQuit = true; - } - if (to > toExclusive) to = toExclusive; - yield return new Tuple<long, long>(from, to); - } - } - - /// <summary>Creates a partitioner that chunks the user-specified range.</summary> - /// <param name="fromInclusive">The lower, inclusive bound of the range.</param> - /// <param name="toExclusive">The upper, exclusive bound of the range.</param> - /// <returns>A partitioner.</returns> - /// <exception cref="T:System.ArgumentOutOfRangeException"> The <paramref name="toExclusive"/> argument is - /// less than or equal to the <paramref name="fromInclusive"/> argument.</exception> - public static OrderablePartitioner<Tuple<int, int>> Create(int fromInclusive, int toExclusive) - { - // How many chunks do we want to divide the range into? If this is 1, then the - // answer is "one chunk per core". Generally, though, you'll achieve better - // load balancing on a busy system if you make it higher than 1. - int coreOversubscriptionRate = 3; - - if (toExclusive <= fromInclusive) throw new ArgumentOutOfRangeException(nameof(toExclusive)); - int rangeSize = (toExclusive - fromInclusive) / - (PlatformHelper.ProcessorCount * coreOversubscriptionRate); - if (rangeSize == 0) rangeSize = 1; - return Partitioner.Create(CreateRanges(fromInclusive, toExclusive, rangeSize), EnumerablePartitionerOptions.NoBuffering); // chunk one range at a time - } - - /// <summary>Creates a partitioner that chunks the user-specified range.</summary> - /// <param name="fromInclusive">The lower, inclusive bound of the range.</param> - /// <param name="toExclusive">The upper, exclusive bound of the range.</param> - /// <param name="rangeSize">The size of each subrange.</param> - /// <returns>A partitioner.</returns> - /// <exception cref="T:System.ArgumentOutOfRangeException"> The <paramref name="toExclusive"/> argument is - /// less than or equal to the <paramref name="fromInclusive"/> argument.</exception> - /// <exception cref="T:System.ArgumentOutOfRangeException"> The <paramref name="rangeSize"/> argument is - /// less than or equal to 0.</exception> - public static OrderablePartitioner<Tuple<int, int>> Create(int fromInclusive, int toExclusive, int rangeSize) - { - if (toExclusive <= fromInclusive) throw new ArgumentOutOfRangeException(nameof(toExclusive)); - if (rangeSize <= 0) throw new ArgumentOutOfRangeException(nameof(rangeSize)); - return Partitioner.Create(CreateRanges(fromInclusive, toExclusive, rangeSize), EnumerablePartitionerOptions.NoBuffering); // chunk one range at a time - } - - // Private method to parcel out range tuples. - private static IEnumerable<Tuple<int, int>> CreateRanges(int fromInclusive, int toExclusive, int rangeSize) - { - // Enumerate all of the ranges - int from, to; - bool shouldQuit = false; - - for (int i = fromInclusive; (i < toExclusive) && !shouldQuit; i += rangeSize) - { - from = i; - try { checked { to = i + rangeSize; } } - catch (OverflowException) - { - to = toExclusive; - shouldQuit = true; - } - if (to > toExclusive) to = toExclusive; - yield return new Tuple<int, int>(from, to); - } - } - - #region DynamicPartitionEnumerator_Abstract class - /// <summary> - /// DynamicPartitionEnumerator_Abstract defines the enumerator for each partition for the dynamic load-balance - /// partitioning algorithm. - /// - Partition is an enumerator of KeyValuePairs, each corresponding to an item in the data source: - /// the key is the index in the source collection; the value is the item itself. - /// - a set of such partitions share a reader over data source. The type of the reader is specified by - /// TSourceReader. - /// - each partition requests a contiguous chunk of elements at a time from the source data. The chunk - /// size is initially 1, and doubles every time until it reaches the maximum chunk size. - /// The implementation for GrabNextChunk() method has two versions: one for data source of IndexRange - /// types (IList and the array), one for data source of IEnumerable. - /// - The method "Reset" is not supported for any partitioning algorithm. - /// - The implementation for MoveNext() method is same for all dynanmic partitioners, so we provide it - /// in this abstract class. - /// </summary> - /// <typeparam name="TSource">Type of the elements in the data source</typeparam> - /// <typeparam name="TSourceReader">Type of the reader on the data source</typeparam> - //TSourceReader is - // - IList<TSource>, when source data is IList<TSource>, the shared reader is source data itself - // - TSource[], when source data is TSource[], the shared reader is source data itself - // - IEnumerator<TSource>, when source data is IEnumerable<TSource>, and the shared reader is an - // enumerator of the source data - private abstract class DynamicPartitionEnumerator_Abstract<TSource, TSourceReader> : IEnumerator<KeyValuePair<long, TSource>> - { - //----------------- common fields and constructor for all dynamic partitioners ----------------- - //--- shared by all dervied class with souce data type: IList, Array, and IEnumerator - protected readonly TSourceReader m_sharedReader; - - protected static int s_defaultMaxChunkSize = GetDefaultChunkSize<TSource>(); - - //deferred allocating in MoveNext() with initial value 0, to avoid false sharing - //we also use the fact that: (m_currentChunkSize==null) means MoveNext is never called on this enumerator - protected SharedInt m_currentChunkSize; - - //deferring allocation in MoveNext() with initial value -1, to avoid false sharing - protected SharedInt m_localOffset; - - private const int CHUNK_DOUBLING_RATE = 3; // Double the chunk size every this many grabs - private int m_doublingCountdown; // Number of grabs remaining until chunk size doubles - protected readonly int m_maxChunkSize; // s_defaultMaxChunkSize unless single-chunking is requested by the caller - - // m_sharedIndex shared by this set of partitions, and particularly when m_sharedReader is IEnuerable - // it serves as tracking of the natual order of elements in m_sharedReader - // the value of this field is passed in from outside (already initialized) by the constructor, - protected readonly SharedLong m_sharedIndex; - - protected DynamicPartitionEnumerator_Abstract(TSourceReader sharedReader, SharedLong sharedIndex) - : this(sharedReader, sharedIndex, false) - { - } - - protected DynamicPartitionEnumerator_Abstract(TSourceReader sharedReader, SharedLong sharedIndex, bool useSingleChunking) - { - m_sharedReader = sharedReader; - m_sharedIndex = sharedIndex; - m_maxChunkSize = useSingleChunking ? 1 : s_defaultMaxChunkSize; - } - - // ---------------- abstract method declarations -------------- - - /// <summary> - /// Abstract method to request a contiguous chunk of elements from the source collection - /// </summary> - /// <param name="requestedChunkSize">specified number of elements requested</param> - /// <returns> - /// true if we successfully reserved at least one element (up to #=requestedChunkSize) - /// false if all elements in the source collection have been reserved. - /// </returns> - //GrabNextChunk does the following: - // - grab # of requestedChunkSize elements from source data through shared reader, - // - at the time of function returns, m_currentChunkSize is updated with the number of - // elements actually got assigned (<=requestedChunkSize). - // - GrabNextChunk returns true if at least one element is assigned to this partition; - // false if the shared reader already hits the last element of the source data before - // we call GrabNextChunk - protected abstract bool GrabNextChunk(int requestedChunkSize); - - /// <summary> - /// Abstract property, returns whether or not the shared reader has already read the last - /// element of the source data - /// </summary> - protected abstract bool HasNoElementsLeft { get; set; } - - /// <summary> - /// Get the current element in the current partition. Property required by IEnumerator interface - /// This property is abstract because the implementation is different depending on the type - /// of the source data: IList, Array or IEnumerable - /// </summary> - public abstract KeyValuePair<long, TSource> Current { get; } - - /// <summary> - /// Dispose is abstract, and depends on the type of the source data: - /// - For source data type IList and Array, the type of the shared reader is just the dataitself. - /// We don't do anything in Dispose method for IList and Array. - /// - For source data type IEnumerable, the type of the shared reader is an enumerator we created. - /// Thus we need to dispose this shared reader enumerator, when there is no more active partitions - /// left. - /// </summary> - public abstract void Dispose(); - - /// <summary> - /// Reset on partitions is not supported - /// </summary> - public void Reset() - { - throw new NotSupportedException(); - } - - - /// <summary> - /// Get the current element in the current partition. Property required by IEnumerator interface - /// </summary> - Object IEnumerator.Current - { - get - { - return ((DynamicPartitionEnumerator_Abstract<TSource, TSourceReader>)this).Current; - } - } - - /// <summary> - /// Moves to the next element if any. - /// Try current chunk first, if the current chunk do not have any elements left, then we - /// attempt to grab a chunk from the source collection. - /// </summary> - /// <returns> - /// true if successfully moving to the next position; - /// false otherwise, if and only if there is no more elements left in the current chunk - /// AND the source collection is exhausted. - /// </returns> - public bool MoveNext() - { - //perform deferred allocating of the local variables. - if (m_localOffset == null) - { - Debug.Assert(m_currentChunkSize == null); - m_localOffset = new SharedInt(-1); - m_currentChunkSize = new SharedInt(0); - m_doublingCountdown = CHUNK_DOUBLING_RATE; - } - - if (m_localOffset.Value < m_currentChunkSize.Value - 1) - //attempt to grab the next element from the local chunk - { - m_localOffset.Value++; - return true; - } - else - //otherwise it means we exhausted the local chunk - //grab a new chunk from the source enumerator - { - // The second part of the || condition is necessary to handle the case when MoveNext() is called - // after a previous MoveNext call returned false. - Debug.Assert(m_localOffset.Value == m_currentChunkSize.Value - 1 || m_currentChunkSize.Value == 0); - - //set the requested chunk size to a proper value - int requestedChunkSize; - if (m_currentChunkSize.Value == 0) //first time grabbing from source enumerator - { - requestedChunkSize = 1; - } - else if (m_doublingCountdown > 0) - { - requestedChunkSize = m_currentChunkSize.Value; - } - else - { - requestedChunkSize = Math.Min(m_currentChunkSize.Value * 2, m_maxChunkSize); - m_doublingCountdown = CHUNK_DOUBLING_RATE; // reset - } - - // Decrement your doubling countdown - m_doublingCountdown--; - - Debug.Assert(requestedChunkSize > 0 && requestedChunkSize <= m_maxChunkSize); - //GrabNextChunk will update the value of m_currentChunkSize - if (GrabNextChunk(requestedChunkSize)) - { - Debug.Assert(m_currentChunkSize.Value <= requestedChunkSize && m_currentChunkSize.Value > 0); - m_localOffset.Value = 0; - return true; - } - else - { - return false; - } - } - } - } - #endregion - - #region Dynamic Partitioner for source data of IEnuemrable<> type - /// <summary> - /// Inherits from DynamicPartitioners - /// Provides customized implementation of GetOrderableDynamicPartitions_Factory method, to return an instance - /// of EnumerableOfPartitionsForIEnumerator defined internally - /// </summary> - /// <typeparam name="TSource">Type of elements in the source data</typeparam> - private class DynamicPartitionerForIEnumerable<TSource> : OrderablePartitioner<TSource> - { - IEnumerable<TSource> m_source; - readonly bool m_useSingleChunking; - - //constructor - internal DynamicPartitionerForIEnumerable(IEnumerable<TSource> source, EnumerablePartitionerOptions partitionerOptions) - : base(true, false, true) - { - m_source = source; - m_useSingleChunking = ((partitionerOptions & EnumerablePartitionerOptions.NoBuffering) != 0); - } - - /// <summary> - /// Overrides OrderablePartitioner.GetOrderablePartitions. - /// Partitions the underlying collection into the given number of orderable partitions. - /// </summary> - /// <param name="partitionCount">number of partitions requested</param> - /// <returns>A list containing <paramref name="partitionCount"/> enumerators.</returns> - override public IList<IEnumerator<KeyValuePair<long, TSource>>> GetOrderablePartitions(int partitionCount) - { - if (partitionCount <= 0) - { - throw new ArgumentOutOfRangeException(nameof(partitionCount)); - } - IEnumerator<KeyValuePair<long, TSource>>[] partitions - = new IEnumerator<KeyValuePair<long, TSource>>[partitionCount]; - - IEnumerable<KeyValuePair<long, TSource>> partitionEnumerable = new InternalPartitionEnumerable(m_source.GetEnumerator(), m_useSingleChunking, true); - for (int i = 0; i < partitionCount; i++) - { - partitions[i] = partitionEnumerable.GetEnumerator(); - } - return partitions; - } - - /// <summary> - /// Overrides OrderablePartitioner.GetOrderableDyanmicPartitions - /// </summary> - /// <returns>a enumerable collection of orderable partitions</returns> - override public IEnumerable<KeyValuePair<long, TSource>> GetOrderableDynamicPartitions() - { - return new InternalPartitionEnumerable(m_source.GetEnumerator(), m_useSingleChunking, false); - } - - /// <summary> - /// Whether additional partitions can be created dynamically. - /// </summary> - override public bool SupportsDynamicPartitions - { - get { return true; } - } - - #region Internal classes: InternalPartitionEnumerable, InternalPartitionEnumerator - /// <summary> - /// Provides customized implementation for source data of IEnumerable - /// Different from the counterpart for IList/Array, this enumerable maintains several additional fields - /// shared by the partitions it owns, including a boolean "m_hasNoElementsLef", a shared lock, and a - /// shared count "m_activePartitionCount" used to track active partitions when they were created statically - /// </summary> - private class InternalPartitionEnumerable : IEnumerable<KeyValuePair<long, TSource>>, IDisposable - { - //reader through which we access the source data - private readonly IEnumerator<TSource> m_sharedReader; - private SharedLong m_sharedIndex;//initial value -1 - - private volatile KeyValuePair<long, TSource>[] m_FillBuffer; // intermediate buffer to reduce locking - private volatile int m_FillBufferSize; // actual number of elements in m_FillBuffer. Will start - // at m_FillBuffer.Length, and might be reduced during the last refill - private volatile int m_FillBufferCurrentPosition; //shared value to be accessed by Interlock.Increment only - private volatile int m_activeCopiers; //number of active copiers - - //fields shared by all partitions that this Enumerable owns, their allocation is deferred - private SharedBool m_hasNoElementsLeft; // no elements left at all. - private SharedBool m_sourceDepleted; // no elements left in the enumerator, but there may be elements in the Fill Buffer - - //shared synchronization lock, created by this Enumerable - private object m_sharedLock;//deferring allocation by enumerator - - private bool m_disposed; - - // If dynamic partitioning, then m_activePartitionCount == null - // If static partitioning, then it keeps track of active partition count - private SharedInt m_activePartitionCount; - - // records whether or not the user has requested single-chunking behavior - private readonly bool m_useSingleChunking; - - internal InternalPartitionEnumerable(IEnumerator<TSource> sharedReader, bool useSingleChunking, bool isStaticPartitioning) - { - m_sharedReader = sharedReader; - m_sharedIndex = new SharedLong(-1); - m_hasNoElementsLeft = new SharedBool(false); - m_sourceDepleted = new SharedBool(false); - m_sharedLock = new object(); - m_useSingleChunking = useSingleChunking; - - // Only allocate the fill-buffer if single-chunking is not in effect - if (!m_useSingleChunking) - { - // Time to allocate the fill buffer which is used to reduce the contention on the shared lock. - // First pick the buffer size multiplier. We use 4 for when there are more than 4 cores, and just 1 for below. This is based on empirical evidence. - int fillBufferMultiplier = (PlatformHelper.ProcessorCount > 4) ? 4 : 1; - - // and allocate the fill buffer using these two numbers - m_FillBuffer = new KeyValuePair<long, TSource>[fillBufferMultiplier * Partitioner.GetDefaultChunkSize<TSource>()]; - } - - if (isStaticPartitioning) - { - // If this object is created for static partitioning (ie. via GetPartitions(int partitionCount), - // GetOrderablePartitions(int partitionCount)), we track the active partitions, in order to dispose - // this object when all the partitions have been disposed. - m_activePartitionCount = new SharedInt(0); - } - else - { - // Otherwise this object is created for dynamic partitioning (ie, via GetDynamicPartitions(), - // GetOrderableDynamicPartitions()), we do not need tracking. This object must be disposed - // explicitly - m_activePartitionCount = null; - } - } - - public IEnumerator<KeyValuePair<long, TSource>> GetEnumerator() - { - if (m_disposed) - { - throw new ObjectDisposedException(Environment.GetResourceString("PartitionerStatic_CanNotCallGetEnumeratorAfterSourceHasBeenDisposed")); - } - else - { - return new InternalPartitionEnumerator(m_sharedReader, m_sharedIndex, - m_hasNoElementsLeft, m_sharedLock, m_activePartitionCount, this, m_useSingleChunking); - } - } - - - IEnumerator IEnumerable.GetEnumerator() - { - return ((InternalPartitionEnumerable)this).GetEnumerator(); - } - - - /////////////////// - // - // Used by GrabChunk_Buffered() - private void TryCopyFromFillBuffer(KeyValuePair<long, TSource>[] destArray, - int requestedChunkSize, - ref int actualNumElementsGrabbed) - { - actualNumElementsGrabbed = 0; - - - // making a local defensive copy of the fill buffer reference, just in case it gets nulled out - KeyValuePair<long, TSource>[] fillBufferLocalRef = m_FillBuffer; - if (fillBufferLocalRef == null) return; - - // first do a quick check, and give up if the current position is at the end - // so that we don't do an unncessary pair of Interlocked.Increment / Decrement calls - if (m_FillBufferCurrentPosition >= m_FillBufferSize) - { - return; // no elements in the buffer to copy from - } - - // We might have a chance to grab elements from the buffer. We will know for sure - // when we do the Interlocked.Add below. - // But first we must register as a potential copier in order to make sure - // the elements we're copying from don't get overwritten by another thread - // that starts refilling the buffer right after our Interlocked.Add. - Interlocked.Increment(ref m_activeCopiers); - - int endPos = Interlocked.Add(ref m_FillBufferCurrentPosition, requestedChunkSize); - int beginPos = endPos - requestedChunkSize; - - if (beginPos < m_FillBufferSize) - { - // adjust index and do the actual copy - actualNumElementsGrabbed = (endPos < m_FillBufferSize) ? endPos : m_FillBufferSize - beginPos; - Array.Copy(fillBufferLocalRef, beginPos, destArray, 0, actualNumElementsGrabbed); - } - - // let the record show we are no longer accessing the buffer - Interlocked.Decrement(ref m_activeCopiers); - } - - /// <summary> - /// This is the common entry point for consuming items from the source enumerable - /// </summary> - /// <returns> - /// true if we successfully reserved at least one element - /// false if all elements in the source collection have been reserved. - /// </returns> - internal bool GrabChunk(KeyValuePair<long, TSource>[] destArray, int requestedChunkSize, ref int actualNumElementsGrabbed) - { - actualNumElementsGrabbed = 0; - - if (m_hasNoElementsLeft.Value) - { - return false; - } - - if (m_useSingleChunking) - { - return GrabChunk_Single(destArray, requestedChunkSize, ref actualNumElementsGrabbed); - } - else - { - return GrabChunk_Buffered(destArray, requestedChunkSize, ref actualNumElementsGrabbed); - } - } - - /// <summary> - /// Version of GrabChunk that grabs a single element at a time from the source enumerable - /// </summary> - /// <returns> - /// true if we successfully reserved an element - /// false if all elements in the source collection have been reserved. - /// </returns> - internal bool GrabChunk_Single(KeyValuePair<long,TSource>[] destArray, int requestedChunkSize, ref int actualNumElementsGrabbed) - { - Debug.Assert(m_useSingleChunking, "Expected m_useSingleChecking to be true"); - Debug.Assert(requestedChunkSize == 1, "Got requested chunk size of " + requestedChunkSize + " when single-chunking was on"); - Debug.Assert(actualNumElementsGrabbed == 0, "Expected actualNumElementsGrabbed == 0, instead it is " + actualNumElementsGrabbed); - Debug.Assert(destArray.Length == 1, "Expected destArray to be of length 1, instead its length is " + destArray.Length); - - lock (m_sharedLock) - { - if (m_hasNoElementsLeft.Value) return false; - - try - { - if (m_sharedReader.MoveNext()) - { - m_sharedIndex.Value = checked(m_sharedIndex.Value + 1); - destArray[0] - = new KeyValuePair<long, TSource>(m_sharedIndex.Value, - m_sharedReader.Current); - actualNumElementsGrabbed = 1; - return true; - } - else - { - //if MoveNext() return false, we set the flag to inform other partitions - m_sourceDepleted.Value = true; - m_hasNoElementsLeft.Value = true; - return false; - } - } - catch - { - // On an exception, make sure that no additional items are hereafter enumerated - m_sourceDepleted.Value = true; - m_hasNoElementsLeft.Value = true; - throw; - } - } - } - - - - /// <summary> - /// Version of GrabChunk that uses buffering scheme to grab items out of source enumerable - /// </summary> - /// <returns> - /// true if we successfully reserved at least one element (up to #=requestedChunkSize) - /// false if all elements in the source collection have been reserved. - /// </returns> - internal bool GrabChunk_Buffered(KeyValuePair<long,TSource>[] destArray, int requestedChunkSize, ref int actualNumElementsGrabbed) - { - Debug.Assert(requestedChunkSize > 0); - Debug.Assert(!m_useSingleChunking, "Did not expect to be in single-chunking mode"); - - TryCopyFromFillBuffer(destArray, requestedChunkSize, ref actualNumElementsGrabbed); - - if (actualNumElementsGrabbed == requestedChunkSize) - { - // that was easy. - return true; - } - else if (m_sourceDepleted.Value) - { - // looks like we both reached the end of the fill buffer, and the source was depleted previously - // this means no more work to do for any other worker - m_hasNoElementsLeft.Value = true; - m_FillBuffer = null; - return (actualNumElementsGrabbed > 0); - } - - - // - // now's the time to take the shared lock and enumerate - // - lock (m_sharedLock) - { - if (m_sourceDepleted.Value) - { - return (actualNumElementsGrabbed > 0); - } - - try - { - // we need to make sure all array copiers are finished - if (m_activeCopiers > 0) - { - SpinWait sw = new SpinWait(); - while( m_activeCopiers > 0) sw.SpinOnce(); - } - - Debug.Assert(m_sharedIndex != null); //already been allocated in MoveNext() before calling GrabNextChunk - - // Now's the time to actually enumerate the source - - // We first fill up the requested # of elements in the caller's array - // continue from the where TryCopyFromFillBuffer() left off - for (; actualNumElementsGrabbed < requestedChunkSize; actualNumElementsGrabbed++) - { - if (m_sharedReader.MoveNext()) - { - m_sharedIndex.Value = checked(m_sharedIndex.Value + 1); - destArray[actualNumElementsGrabbed] - = new KeyValuePair<long, TSource>(m_sharedIndex.Value, - m_sharedReader.Current); - } - else - { - //if MoveNext() return false, we set the flag to inform other partitions - m_sourceDepleted.Value = true; - break; - } - } - - // taking a local snapshot of m_FillBuffer in case some other thread decides to null out m_FillBuffer - // in the entry of this method after observing m_sourceCompleted = true - var localFillBufferRef = m_FillBuffer; - - // If the big buffer seems to be depleted, we will also fill that up while we are under the lock - // Note that this is the only place that m_FillBufferCurrentPosition can be reset - if (m_sourceDepleted.Value == false && localFillBufferRef != null && - m_FillBufferCurrentPosition >= localFillBufferRef.Length) - { - for (int i = 0; i < localFillBufferRef.Length; i++) - { - if( m_sharedReader.MoveNext()) - { - m_sharedIndex.Value = checked(m_sharedIndex.Value + 1); - localFillBufferRef[i] - = new KeyValuePair<long, TSource>(m_sharedIndex.Value, - m_sharedReader.Current); - } - else - { - // No more elements left in the enumerator. - // Record this, so that the next request can skip the lock - m_sourceDepleted.Value = true; - - // also record the current count in m_FillBufferSize - m_FillBufferSize = i; - - // and exit the for loop so that we don't keep incrementing m_FillBufferSize - break; - } - - } - - m_FillBufferCurrentPosition = 0; - } - - - } - catch - { - // If an exception occurs, don't let the other enumerators try to enumerate. - // NOTE: this could instead throw an InvalidOperationException, but that would be unexpected - // and not helpful to the end user. We know the root cause is being communicated already.) - m_sourceDepleted.Value = true; - m_hasNoElementsLeft.Value = true; - throw; - } - } - - return (actualNumElementsGrabbed > 0); - } - - public void Dispose() - { - if (!m_disposed) - { - m_disposed = true; - m_sharedReader.Dispose(); - } - } - } - - /// <summary> - /// Inherits from DynamicPartitionEnumerator_Abstract directly - /// Provides customized implementation for: GrabNextChunk, HasNoElementsLeft, Current, Dispose - /// </summary> - private class InternalPartitionEnumerator : DynamicPartitionEnumerator_Abstract<TSource, IEnumerator<TSource>> - { - //---- fields ---- - //cached local copy of the current chunk - private KeyValuePair<long, TSource>[] m_localList; //defer allocating to avoid false sharing - - // the values of the following two fields are passed in from - // outside(already initialized) by the constructor, - private readonly SharedBool m_hasNoElementsLeft; - private readonly object m_sharedLock; - private readonly SharedInt m_activePartitionCount; - private InternalPartitionEnumerable m_enumerable; - - //constructor - internal InternalPartitionEnumerator( - IEnumerator<TSource> sharedReader, - SharedLong sharedIndex, - SharedBool hasNoElementsLeft, - object sharedLock, - SharedInt activePartitionCount, - InternalPartitionEnumerable enumerable, - bool useSingleChunking) - : base(sharedReader, sharedIndex, useSingleChunking) - { - m_hasNoElementsLeft = hasNoElementsLeft; - m_sharedLock = sharedLock; - m_enumerable = enumerable; - m_activePartitionCount = activePartitionCount; - - if (m_activePartitionCount != null) - { - // If static partitioning, we need to increase the active partition count. - Interlocked.Increment(ref m_activePartitionCount.Value); - } - } - - //overriding methods - - /// <summary> - /// Reserves a contiguous range of elements from source data - /// </summary> - /// <param name="requestedChunkSize">specified number of elements requested</param> - /// <returns> - /// true if we successfully reserved at least one element (up to #=requestedChunkSize) - /// false if all elements in the source collection have been reserved. - /// </returns> - override protected bool GrabNextChunk(int requestedChunkSize) - { - Debug.Assert(requestedChunkSize > 0); - - if (HasNoElementsLeft) - { - return false; - } - - // defer allocation to avoid false sharing - if (m_localList == null) - { - m_localList = new KeyValuePair<long, TSource>[m_maxChunkSize]; - } - - // make the actual call to the enumerable that grabs a chunk - return m_enumerable.GrabChunk(m_localList, requestedChunkSize, ref m_currentChunkSize.Value); - } - - /// <summary> - /// Returns whether or not the shared reader has already read the last - /// element of the source data - /// </summary> - /// <remarks> - /// We cannot call m_sharedReader.MoveNext(), to see if it hits the last element - /// or not, because we can't undo MoveNext(). Thus we need to maintain a shared - /// boolean value m_hasNoElementsLeft across all partitions - /// </remarks> - override protected bool HasNoElementsLeft - { - get { return m_hasNoElementsLeft.Value; } - set - { - //we only set it from false to true once - //we should never set it back in any circumstances - Debug.Assert(value); - Debug.Assert(!m_hasNoElementsLeft.Value); - m_hasNoElementsLeft.Value = true; - } - } - - override public KeyValuePair<long, TSource> Current - { - get - { - //verify that MoveNext is at least called once before Current is called - if (m_currentChunkSize == null) - { - throw new InvalidOperationException(Environment.GetResourceString("PartitionerStatic_CurrentCalledBeforeMoveNext")); - } - Debug.Assert(m_localList != null); - Debug.Assert(m_localOffset.Value >= 0 && m_localOffset.Value < m_currentChunkSize.Value); - return (m_localList[m_localOffset.Value]); - } - } - - override public void Dispose() - { - // If this is static partitioning, ie. m_activePartitionCount != null, since the current partition - // is disposed, we decrement the number of active partitions for the shared reader. - if (m_activePartitionCount != null && Interlocked.Decrement(ref m_activePartitionCount.Value) == 0) - { - // If the number of active partitions becomes 0, we need to dispose the shared - // reader we created in the m_enumerable object. - m_enumerable.Dispose(); - } - // If this is dynamic partitioning, ie. m_activePartitionCount != null, then m_enumerable needs to - // be disposed explicitly by the user, and we do not need to anything here - } - } - #endregion - - } - #endregion - - #region Dynamic Partitioner for source data of IndexRange types (IList<> and Array<>) - /// <summary> - /// Dynamic load-balance partitioner. This class is abstract and to be derived from by - /// the customized partitioner classes for IList, Array, and IEnumerable - /// </summary> - /// <typeparam name="TSource">Type of the elements in the source data</typeparam> - /// <typeparam name="TCollection"> Type of the source data collection</typeparam> - private abstract class DynamicPartitionerForIndexRange_Abstract<TSource, TCollection> : OrderablePartitioner<TSource> - { - // TCollection can be: IList<TSource>, TSource[] and IEnumerable<TSource> - // Derived classes specify TCollection, and implement the abstract method GetOrderableDynamicPartitions_Factory accordingly - TCollection m_data; - - /// <summary> - /// Constructs a new orderable partitioner - /// </summary> - /// <param name="data">source data collection</param> - protected DynamicPartitionerForIndexRange_Abstract(TCollection data) - : base(true, false, true) - { - m_data = data; - } - - /// <summary> - /// Partition the source data and create an enumerable over the resulting partitions. - /// </summary> - /// <param name="data">the source data collection</param> - /// <returns>an enumerable of partitions of </returns> - protected abstract IEnumerable<KeyValuePair<long, TSource>> GetOrderableDynamicPartitions_Factory(TCollection data); - - /// <summary> - /// Overrides OrderablePartitioner.GetOrderablePartitions. - /// Partitions the underlying collection into the given number of orderable partitions. - /// </summary> - /// <param name="partitionCount">number of partitions requested</param> - /// <returns>A list containing <paramref name="partitionCount"/> enumerators.</returns> - override public IList<IEnumerator<KeyValuePair<long, TSource>>> GetOrderablePartitions(int partitionCount) - { - if (partitionCount <= 0) - { - throw new ArgumentOutOfRangeException(nameof(partitionCount)); - } - IEnumerator<KeyValuePair<long, TSource>>[] partitions - = new IEnumerator<KeyValuePair<long, TSource>>[partitionCount]; - IEnumerable<KeyValuePair<long, TSource>> partitionEnumerable = GetOrderableDynamicPartitions_Factory(m_data); - for (int i = 0; i < partitionCount; i++) - { - partitions[i] = partitionEnumerable.GetEnumerator(); - } - return partitions; - } - - /// <summary> - /// Overrides OrderablePartitioner.GetOrderableDyanmicPartitions - /// </summary> - /// <returns>a enumerable collection of orderable partitions</returns> - override public IEnumerable<KeyValuePair<long, TSource>> GetOrderableDynamicPartitions() - { - return GetOrderableDynamicPartitions_Factory(m_data); - } - - /// <summary> - /// Whether additional partitions can be created dynamically. - /// </summary> - override public bool SupportsDynamicPartitions - { - get { return true; } - } - - } - - /// <summary> - /// Defines dynamic partition for source data of IList and Array. - /// This class inherits DynamicPartitionEnumerator_Abstract - /// - implements GrabNextChunk, HasNoElementsLeft, and Dispose methods for IList and Array - /// - Current property still remains abstract, implementation is different for IList and Array - /// - introduces another abstract method SourceCount, which returns the number of elements in - /// the source data. Implementation differs for IList and Array - /// </summary> - /// <typeparam name="TSource">Type of the elements in the data source</typeparam> - /// <typeparam name="TSourceReader">Type of the reader on the source data</typeparam> - private abstract class DynamicPartitionEnumeratorForIndexRange_Abstract<TSource, TSourceReader> : DynamicPartitionEnumerator_Abstract<TSource, TSourceReader> - { - //fields - protected int m_startIndex; //initially zero - - //constructor - protected DynamicPartitionEnumeratorForIndexRange_Abstract(TSourceReader sharedReader, SharedLong sharedIndex) - : base(sharedReader, sharedIndex) - { - } - - //abstract methods - //the Current property is still abstract, and will be implemented by derived classes - //we add another abstract method SourceCount to get the number of elements from the source reader - - /// <summary> - /// Get the number of elements from the source reader. - /// It calls IList.Count or Array.Length - /// </summary> - protected abstract int SourceCount { get; } - - //overriding methods - - /// <summary> - /// Reserves a contiguous range of elements from source data - /// </summary> - /// <param name="requestedChunkSize">specified number of elements requested</param> - /// <returns> - /// true if we successfully reserved at least one element (up to #=requestedChunkSize) - /// false if all elements in the source collection have been reserved. - /// </returns> - override protected bool GrabNextChunk(int requestedChunkSize) - { - Debug.Assert(requestedChunkSize > 0); - - while (!HasNoElementsLeft) - { - Debug.Assert(m_sharedIndex != null); - // use the new Volatile.Read method because it is cheaper than Interlocked.Read on AMD64 architecture - long oldSharedIndex = Volatile.Read(ref m_sharedIndex.Value); - - if (HasNoElementsLeft) - { - //HasNoElementsLeft situation changed from false to true immediately - //and oldSharedIndex becomes stale - return false; - } - - //there won't be overflow, because the index of IList/array is int, and we - //have casted it to long. - long newSharedIndex = Math.Min(SourceCount - 1, oldSharedIndex + requestedChunkSize); - - - //the following CAS, if successful, reserves a chunk of elements [oldSharedIndex+1, newSharedIndex] - //inclusive in the source collection - if (Interlocked.CompareExchange(ref m_sharedIndex.Value, newSharedIndex, oldSharedIndex) - == oldSharedIndex) - { - //set up local indexes. - //m_currentChunkSize is always set to requestedChunkSize when source data had - //enough elements of what we requested - m_currentChunkSize.Value = (int)(newSharedIndex - oldSharedIndex); - m_localOffset.Value = -1; - m_startIndex = (int)(oldSharedIndex + 1); - return true; - } - } - //didn't get any element, return false; - return false; - } - - /// <summary> - /// Returns whether or not the shared reader has already read the last - /// element of the source data - /// </summary> - override protected bool HasNoElementsLeft - { - get - { - Debug.Assert(m_sharedIndex != null); - // use the new Volatile.Read method because it is cheaper than Interlocked.Read on AMD64 architecture - return Volatile.Read(ref m_sharedIndex.Value) >= SourceCount - 1; - } - set - { - Debug.Assert(false); - } - } - - /// <summary> - /// For source data type IList and Array, the type of the shared reader is just the data itself. - /// We don't do anything in Dispose method for IList and Array. - /// </summary> - override public void Dispose() - { } - } - - - /// <summary> - /// Inherits from DynamicPartitioners - /// Provides customized implementation of GetOrderableDynamicPartitions_Factory method, to return an instance - /// of EnumerableOfPartitionsForIList defined internally - /// </summary> - /// <typeparam name="TSource">Type of elements in the source data</typeparam> - private class DynamicPartitionerForIList<TSource> : DynamicPartitionerForIndexRange_Abstract<TSource, IList<TSource>> - { - //constructor - internal DynamicPartitionerForIList(IList<TSource> source) - : base(source) - { } - - //override methods - override protected IEnumerable<KeyValuePair<long, TSource>> GetOrderableDynamicPartitions_Factory(IList<TSource> m_data) - { - //m_data itself serves as shared reader - return new InternalPartitionEnumerable(m_data); - } - - /// <summary> - /// Inherits from PartitionList_Abstract - /// Provides customized implementation for source data of IList - /// </summary> - private class InternalPartitionEnumerable : IEnumerable<KeyValuePair<long, TSource>> - { - //reader through which we access the source data - private readonly IList<TSource> m_sharedReader; - private SharedLong m_sharedIndex; - - internal InternalPartitionEnumerable(IList<TSource> sharedReader) - { - m_sharedReader = sharedReader; - m_sharedIndex = new SharedLong(-1); - } - - public IEnumerator<KeyValuePair<long, TSource>> GetEnumerator() - { - return new InternalPartitionEnumerator(m_sharedReader, m_sharedIndex); - } - - IEnumerator IEnumerable.GetEnumerator() - { - return ((InternalPartitionEnumerable)this).GetEnumerator(); - } - } - - /// <summary> - /// Inherits from DynamicPartitionEnumeratorForIndexRange_Abstract - /// Provides customized implementation of SourceCount property and Current property for IList - /// </summary> - private class InternalPartitionEnumerator : DynamicPartitionEnumeratorForIndexRange_Abstract<TSource, IList<TSource>> - { - //constructor - internal InternalPartitionEnumerator(IList<TSource> sharedReader, SharedLong sharedIndex) - : base(sharedReader, sharedIndex) - { } - - //overriding methods - override protected int SourceCount - { - get { return m_sharedReader.Count; } - } - /// <summary> - /// return a KeyValuePair of the current element and its key - /// </summary> - override public KeyValuePair<long, TSource> Current - { - get - { - //verify that MoveNext is at least called once before Current is called - if (m_currentChunkSize == null) - { - throw new InvalidOperationException(Environment.GetResourceString("PartitionerStatic_CurrentCalledBeforeMoveNext")); - } - - Debug.Assert(m_localOffset.Value >= 0 && m_localOffset.Value < m_currentChunkSize.Value); - return new KeyValuePair<long, TSource>(m_startIndex + m_localOffset.Value, - m_sharedReader[m_startIndex + m_localOffset.Value]); - } - } - } - } - - - - /// <summary> - /// Inherits from DynamicPartitioners - /// Provides customized implementation of GetOrderableDynamicPartitions_Factory method, to return an instance - /// of EnumerableOfPartitionsForArray defined internally - /// </summary> - /// <typeparam name="TSource">Type of elements in the source data</typeparam> - private class DynamicPartitionerForArray<TSource> : DynamicPartitionerForIndexRange_Abstract<TSource, TSource[]> - { - //constructor - internal DynamicPartitionerForArray(TSource[] source) - : base(source) - { } - - //override methods - override protected IEnumerable<KeyValuePair<long, TSource>> GetOrderableDynamicPartitions_Factory(TSource[] m_data) - { - return new InternalPartitionEnumerable(m_data); - } - - /// <summary> - /// Inherits from PartitionList_Abstract - /// Provides customized implementation for source data of Array - /// </summary> - private class InternalPartitionEnumerable : IEnumerable<KeyValuePair<long, TSource>> - { - //reader through which we access the source data - private readonly TSource[] m_sharedReader; - private SharedLong m_sharedIndex; - - internal InternalPartitionEnumerable(TSource[] sharedReader) - { - m_sharedReader = sharedReader; - m_sharedIndex = new SharedLong(-1); - } - - IEnumerator IEnumerable.GetEnumerator() - { - return ((InternalPartitionEnumerable)this).GetEnumerator(); - } - - - public IEnumerator<KeyValuePair<long, TSource>> GetEnumerator() - { - return new InternalPartitionEnumerator(m_sharedReader, m_sharedIndex); - } - } - - /// <summary> - /// Inherits from DynamicPartitionEnumeratorForIndexRange_Abstract - /// Provides customized implementation of SourceCount property and Current property for Array - /// </summary> - private class InternalPartitionEnumerator : DynamicPartitionEnumeratorForIndexRange_Abstract<TSource, TSource[]> - { - //constructor - internal InternalPartitionEnumerator(TSource[] sharedReader, SharedLong sharedIndex) - : base(sharedReader, sharedIndex) - { } - - //overriding methods - override protected int SourceCount - { - get { return m_sharedReader.Length; } - } - - override public KeyValuePair<long, TSource> Current - { - get - { - //verify that MoveNext is at least called once before Current is called - if (m_currentChunkSize == null) - { - throw new InvalidOperationException(Environment.GetResourceString("PartitionerStatic_CurrentCalledBeforeMoveNext")); - } - - Debug.Assert(m_localOffset.Value >= 0 && m_localOffset.Value < m_currentChunkSize.Value); - return new KeyValuePair<long, TSource>(m_startIndex + m_localOffset.Value, - m_sharedReader[m_startIndex + m_localOffset.Value]); - } - } - } - } - #endregion - - - #region Static partitioning for IList and Array, abstract classes - /// <summary> - /// Static partitioning over IList. - /// - dynamic and load-balance - /// - Keys are ordered within each partition - /// - Keys are ordered across partitions - /// - Keys are normalized - /// - Number of partitions is fixed once specified, and the elements of the source data are - /// distributed to each partition as evenly as possible. - /// </summary> - /// <typeparam name="TSource">type of the elements</typeparam> - /// <typeparam name="TCollection">Type of the source data collection</typeparam> - private abstract class StaticIndexRangePartitioner<TSource, TCollection> : OrderablePartitioner<TSource> - { - protected StaticIndexRangePartitioner() - : base(true, true, true) - { } - - /// <summary> - /// Abstract method to return the number of elements in the source data - /// </summary> - protected abstract int SourceCount { get; } - - /// <summary> - /// Abstract method to create a partition that covers a range over source data, - /// starting from "startIndex", ending at "endIndex" - /// </summary> - /// <param name="startIndex">start index of the current partition on the source data</param> - /// <param name="endIndex">end index of the current partition on the source data</param> - /// <returns>a partition enumerator over the specified range</returns> - // The partitioning algorithm is implemented in GetOrderablePartitions method - // This method delegates according to source data type IList/Array - protected abstract IEnumerator<KeyValuePair<long, TSource>> CreatePartition(int startIndex, int endIndex); - - /// <summary> - /// Overrides OrderablePartitioner.GetOrderablePartitions - /// Return a list of partitions, each of which enumerate a fixed part of the source data - /// The elements of the source data are distributed to each partition as evenly as possible. - /// Specifically, if the total number of elements is N, and number of partitions is x, and N = a*x +b, - /// where a is the quotient, and b is the remainder. Then the first b partitions each has a + 1 elements, - /// and the last x-b partitions each has a elements. - /// For example, if N=10, x =3, then - /// partition 0 ranges [0,3], - /// partition 1 ranges [4,6], - /// partition 2 ranges [7,9]. - /// This also takes care of the situation of (x>N), the last x-N partitions are empty enumerators. - /// An empty enumerator is indicated by - /// (m_startIndex == list.Count && m_endIndex == list.Count -1) - /// </summary> - /// <param name="partitionCount">specified number of partitions</param> - /// <returns>a list of partitions</returns> - override public IList<IEnumerator<KeyValuePair<long, TSource>>> GetOrderablePartitions(int partitionCount) - { - if (partitionCount <= 0) - { - throw new ArgumentOutOfRangeException(nameof(partitionCount)); - } - - int quotient, remainder; - quotient = Math.DivRem(SourceCount, partitionCount, out remainder); - - IEnumerator<KeyValuePair<long, TSource>>[] partitions = new IEnumerator<KeyValuePair<long, TSource>>[partitionCount]; - int lastEndIndex = -1; - for (int i = 0; i < partitionCount; i++) - { - int startIndex = lastEndIndex + 1; - - if (i < remainder) - { - lastEndIndex = startIndex + quotient; - } - else - { - lastEndIndex = startIndex + quotient - 1; - } - partitions[i] = CreatePartition(startIndex, lastEndIndex); - } - return partitions; - } - } - - /// <summary> - /// Static Partition for IList/Array. - /// This class implements all methods required by IEnumerator interface, except for the Current property. - /// Current Property is different for IList and Array. Arrays calls 'ldelem' instructions for faster element - /// retrieval. - /// </summary> - //We assume the source collection is not being updated concurrently. Otherwise it will break the - //static partitioning, since each partition operates on the source collection directly, it does - //not have a local cache of the elements assigned to them. - private abstract class StaticIndexRangePartition<TSource> : IEnumerator<KeyValuePair<long, TSource>> - { - //the start and end position in the source collection for the current partition - //the partition is empty if and only if - // (m_startIndex == m_data.Count && m_endIndex == m_data.Count-1) - protected readonly int m_startIndex; - protected readonly int m_endIndex; - - //the current index of the current partition while enumerating on the source collection - protected volatile int m_offset; - - /// <summary> - /// Constructs an instance of StaticIndexRangePartition - /// </summary> - /// <param name="startIndex">the start index in the source collection for the current partition </param> - /// <param name="endIndex">the end index in the source collection for the current partition</param> - protected StaticIndexRangePartition(int startIndex, int endIndex) - { - m_startIndex = startIndex; - m_endIndex = endIndex; - m_offset = startIndex - 1; - } - - /// <summary> - /// Current Property is different for IList and Array. Arrays calls 'ldelem' instructions for faster - /// element retrieval. - /// </summary> - public abstract KeyValuePair<long, TSource> Current { get; } - - /// <summary> - /// We don't dispose the source for IList and array - /// </summary> - public void Dispose() - { } - - public void Reset() - { - throw new NotSupportedException(); - } - - /// <summary> - /// Moves to the next item - /// Before the first MoveNext is called: m_offset == m_startIndex-1; - /// </summary> - /// <returns>true if successful, false if there is no item left</returns> - public bool MoveNext() - { - if (m_offset < m_endIndex) - { - m_offset++; - return true; - } - else - { - //After we have enumerated over all elements, we set m_offset to m_endIndex +1. - //The reason we do this is, for an empty enumerator, we need to tell the Current - //property whether MoveNext has been called or not. - //For an empty enumerator, it starts with (m_offset == m_startIndex-1 == m_endIndex), - //and we don't set a new value to m_offset, then the above condition will always be - //true, and the Current property will mistakenly assume MoveNext is never called. - m_offset = m_endIndex + 1; - return false; - } - } - - Object IEnumerator.Current - { - get - { - return ((StaticIndexRangePartition<TSource>)this).Current; - } - } - } - #endregion - - #region Static partitioning for IList - /// <summary> - /// Inherits from StaticIndexRangePartitioner - /// Provides customized implementation of SourceCount and CreatePartition - /// </summary> - /// <typeparam name="TSource"></typeparam> - private class StaticIndexRangePartitionerForIList<TSource> : StaticIndexRangePartitioner<TSource, IList<TSource>> - { - IList<TSource> m_list; - internal StaticIndexRangePartitionerForIList(IList<TSource> list) - : base() - { - Debug.Assert(list != null); - m_list = list; - } - override protected int SourceCount - { - get { return m_list.Count; } - } - override protected IEnumerator<KeyValuePair<long, TSource>> CreatePartition(int startIndex, int endIndex) - { - return new StaticIndexRangePartitionForIList<TSource>(m_list, startIndex, endIndex); - } - } - - /// <summary> - /// Inherits from StaticIndexRangePartition - /// Provides customized implementation of Current property - /// </summary> - /// <typeparam name="TSource"></typeparam> - private class StaticIndexRangePartitionForIList<TSource> : StaticIndexRangePartition<TSource> - { - //the source collection shared by all partitions - private volatile IList<TSource> m_list; - - internal StaticIndexRangePartitionForIList(IList<TSource> list, int startIndex, int endIndex) - : base(startIndex, endIndex) - { - Debug.Assert(startIndex >= 0 && endIndex <= list.Count - 1); - m_list = list; - } - - override public KeyValuePair<long, TSource> Current - { - get - { - //verify that MoveNext is at least called once before Current is called - if (m_offset < m_startIndex) - { - throw new InvalidOperationException(Environment.GetResourceString("PartitionerStatic_CurrentCalledBeforeMoveNext")); - } - - Debug.Assert(m_offset >= m_startIndex && m_offset <= m_endIndex); - return (new KeyValuePair<long, TSource>(m_offset, m_list[m_offset])); - } - } - } - #endregion - - #region static partitioning for Arrays - /// <summary> - /// Inherits from StaticIndexRangePartitioner - /// Provides customized implementation of SourceCount and CreatePartition for Array - /// </summary> - private class StaticIndexRangePartitionerForArray<TSource> : StaticIndexRangePartitioner<TSource, TSource[]> - { - TSource[] m_array; - internal StaticIndexRangePartitionerForArray(TSource[] array) - : base() - { - Debug.Assert(array != null); - m_array = array; - } - override protected int SourceCount - { - get { return m_array.Length; } - } - override protected IEnumerator<KeyValuePair<long, TSource>> CreatePartition(int startIndex, int endIndex) - { - return new StaticIndexRangePartitionForArray<TSource>(m_array, startIndex, endIndex); - } - } - - /// <summary> - /// Inherits from StaticIndexRangePartitioner - /// Provides customized implementation of SourceCount and CreatePartition - /// </summary> - private class StaticIndexRangePartitionForArray<TSource> : StaticIndexRangePartition<TSource> - { - //the source collection shared by all partitions - private volatile TSource[] m_array; - - internal StaticIndexRangePartitionForArray(TSource[] array, int startIndex, int endIndex) - : base(startIndex, endIndex) - { - Debug.Assert(startIndex >= 0 && endIndex <= array.Length - 1); - m_array = array; - } - - override public KeyValuePair<long, TSource> Current - { - get - { - //verify that MoveNext is at least called once before Current is called - if (m_offset < m_startIndex) - { - throw new InvalidOperationException(Environment.GetResourceString("PartitionerStatic_CurrentCalledBeforeMoveNext")); - } - - Debug.Assert(m_offset >= m_startIndex && m_offset <= m_endIndex); - return (new KeyValuePair<long, TSource>(m_offset, m_array[m_offset])); - } - } - } - #endregion - - - #region Utility functions - /// <summary> - /// A very simple primitive that allows us to share a value across multiple threads. - /// </summary> - /// <typeparam name="TSource"></typeparam> - private class SharedInt - { - internal volatile int Value; - - internal SharedInt(int value) - { - this.Value = value; - } - - } - - /// <summary> - /// A very simple primitive that allows us to share a value across multiple threads. - /// </summary> - private class SharedBool - { - internal volatile bool Value; - - internal SharedBool(bool value) - { - this.Value = value; - } - - } - - /// <summary> - /// A very simple primitive that allows us to share a value across multiple threads. - /// </summary> - private class SharedLong - { - internal long Value; - internal SharedLong(long value) - { - this.Value = value; - } - - } - - //-------------------- - // The following part calculates the default chunk size. It is copied from System.Linq.Parallel.Scheduling, - // because mscorlib.dll cannot access System.Linq.Parallel.Scheduling - //-------------------- - - // The number of bytes we want "chunks" to be, when partitioning, etc. We choose 4 cache - // lines worth, assuming 128b cache line. Most (popular) architectures use 64b cache lines, - // but choosing 128b works for 64b too whereas a multiple of 64b isn't necessarily sufficient - // for 128b cache systems. So 128b it is. - private const int DEFAULT_BYTES_PER_CHUNK = 128 * 4; - - private static int GetDefaultChunkSize<TSource>() - { - int chunkSize; - - if (typeof(TSource).IsValueType) - { - chunkSize = 128; - } - else - { - Debug.Assert((DEFAULT_BYTES_PER_CHUNK % IntPtr.Size) == 0, "bytes per chunk should be a multiple of pointer size"); - chunkSize = (DEFAULT_BYTES_PER_CHUNK / IntPtr.Size); - } - return chunkSize; - } - #endregion - } -} diff --git a/src/mscorlib/src/System/Collections/DictionaryEntry.cs b/src/mscorlib/src/System/Collections/DictionaryEntry.cs index 3ee392bb0d..0c5d8b2387 100644 --- a/src/mscorlib/src/System/Collections/DictionaryEntry.cs +++ b/src/mscorlib/src/System/Collections/DictionaryEntry.cs @@ -16,9 +16,9 @@ namespace System.Collections { using System; + using System.ComponentModel; // A DictionaryEntry holds a key and a value from a dictionary. // It is returned by IDictionaryEnumerator::GetEntry(). -[System.Runtime.InteropServices.ComVisible(true)] [Serializable] public struct DictionaryEntry { @@ -52,7 +52,7 @@ namespace System.Collections { } } - // BLOCKED (do not add now): [EditorBrowsable(EditorBrowsableState.Never)] + [EditorBrowsable(EditorBrowsableState.Never)] public void Deconstruct(out object key, out object value) { key = Key; diff --git a/src/mscorlib/src/System/Collections/Generic/Comparer.cs b/src/mscorlib/src/System/Collections/Generic/Comparer.cs index 4f06b0af69..056843a606 100644 --- a/src/mscorlib/src/System/Collections/Generic/Comparer.cs +++ b/src/mscorlib/src/System/Collections/Generic/Comparer.cs @@ -265,9 +265,6 @@ namespace System.Collections.Generic Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); } - // Used by the serialization engine. - private Int64EnumComparer(SerializationInfo info, StreamingContext context) { } - public override int Compare(T x, T y) { long lx = JitHelpers.UnsafeEnumCastLong(x); diff --git a/src/mscorlib/src/System/Collections/Generic/DebugView.cs b/src/mscorlib/src/System/Collections/Generic/DebugView.cs index d0711e551e..27c5011147 100644 --- a/src/mscorlib/src/System/Collections/Generic/DebugView.cs +++ b/src/mscorlib/src/System/Collections/Generic/DebugView.cs @@ -16,7 +16,6 @@ namespace System.Collections.Generic { using System; using System.Collections.ObjectModel; - using System.Security.Permissions; using System.Diagnostics; using System.Diagnostics.Contracts; diff --git a/src/mscorlib/src/System/Collections/Generic/Dictionary.cs b/src/mscorlib/src/System/Collections/Generic/Dictionary.cs index c2b2da9ad2..7b60e31031 100644 --- a/src/mscorlib/src/System/Collections/Generic/Dictionary.cs +++ b/src/mscorlib/src/System/Collections/Generic/Dictionary.cs @@ -48,12 +48,10 @@ namespace System.Collections.Generic { using System.Diagnostics; using System.Diagnostics.Contracts; using System.Runtime.Serialization; - using System.Security.Permissions; [DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))] [DebuggerDisplay("Count = {Count}")] [Serializable] - [System.Runtime.InteropServices.ComVisible(false)] public class Dictionary<TKey,TValue>: IDictionary<TKey,TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback { private struct Entry { diff --git a/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs b/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs index 3731114119..0f9259d2f3 100644 --- a/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs +++ b/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs @@ -6,7 +6,6 @@ using System; using System.Collections; using System.Collections.Generic; using System.Security; -using System.Runtime.Serialization; namespace System.Collections.Generic { @@ -367,7 +366,7 @@ namespace System.Collections.Generic } [Serializable] - internal class EnumEqualityComparer<T> : EqualityComparer<T>, ISerializable where T : struct + internal class EnumEqualityComparer<T> : EqualityComparer<T> where T : struct { [Pure] public override bool Equals(T x, T y) { @@ -384,16 +383,6 @@ namespace System.Collections.Generic public EnumEqualityComparer() { } - // This is used by the serialization engine. - protected EnumEqualityComparer(SerializationInfo information, StreamingContext context) { } - - public void GetObjectData(SerializationInfo info, StreamingContext context) { - // For back-compat we need to serialize the comparers for enums with underlying types other than int as ObjectEqualityComparer - if (Type.GetTypeCode(Enum.GetUnderlyingType(typeof(T))) != TypeCode.Int32) { - info.SetType(typeof(ObjectEqualityComparer<T>)); - } - } - // Equals method for the comparer itself. public override bool Equals(Object obj) => obj != null && GetType() == obj.GetType(); @@ -427,13 +416,10 @@ namespace System.Collections.Generic } [Serializable] - internal sealed class SByteEnumEqualityComparer<T> : EnumEqualityComparer<T>, ISerializable where T : struct + internal sealed class SByteEnumEqualityComparer<T> : EnumEqualityComparer<T> where T : struct { public SByteEnumEqualityComparer() { } - // This is used by the serialization engine. - public SByteEnumEqualityComparer(SerializationInfo information, StreamingContext context) { } - [Pure] public override int GetHashCode(T obj) { int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(obj); @@ -442,13 +428,10 @@ namespace System.Collections.Generic } [Serializable] - internal sealed class ShortEnumEqualityComparer<T> : EnumEqualityComparer<T>, ISerializable where T : struct + internal sealed class ShortEnumEqualityComparer<T> : EnumEqualityComparer<T> where T : struct { public ShortEnumEqualityComparer() { } - // This is used by the serialization engine. - public ShortEnumEqualityComparer(SerializationInfo information, StreamingContext context) { } - [Pure] public override int GetHashCode(T obj) { int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(obj); @@ -457,7 +440,7 @@ namespace System.Collections.Generic } [Serializable] - internal sealed class LongEnumEqualityComparer<T> : EqualityComparer<T>, ISerializable where T : struct + internal sealed class LongEnumEqualityComparer<T> : EqualityComparer<T> where T : struct { [Pure] public override bool Equals(T x, T y) { @@ -481,16 +464,6 @@ namespace System.Collections.Generic public LongEnumEqualityComparer() { } - // This is used by the serialization engine. - public LongEnumEqualityComparer(SerializationInfo information, StreamingContext context) { } - - public void GetObjectData(SerializationInfo info, StreamingContext context) - { - // The LongEnumEqualityComparer does not exist on 4.0 so we need to serialize this comparer as ObjectEqualityComparer - // to allow for roundtrip between 4.0 and 4.5. - info.SetType(typeof(ObjectEqualityComparer<T>)); - } - internal override int IndexOf(T[] array, T value, int startIndex, int count) { long toFind = JitHelpers.UnsafeEnumCastLong(value); @@ -515,122 +488,4 @@ namespace System.Collections.Generic return -1; } } - -#if FEATURE_RANDOMIZED_STRING_HASHING - // This type is not serializeable by design. It does not exist in previous versions and will be removed - // Once we move the framework to using secure hashing by default. - internal sealed class RandomizedStringEqualityComparer : IEqualityComparer<String>, IEqualityComparer, IWellKnownStringEqualityComparer - { - private long _entropy; - - public RandomizedStringEqualityComparer() { - _entropy = HashHelpers.GetEntropy(); - } - - public new bool Equals(object x, object y) { - if (x == y) return true; - if (x == null || y == null) return false; - if ((x is string) && (y is string)) return Equals((string)x, (string)y); - ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArgumentForComparison); - return false; - } - - [Pure] - public bool Equals(string x, string y) { - if (x != null) { - if (y != null) return x.Equals(y); - return false; - } - if (y != null) return false; - return true; - } - - [Pure] - public int GetHashCode(String obj) { - if(obj == null) return 0; - return String.InternalMarvin32HashString(obj, obj.Length, _entropy); - } - - [Pure] - public int GetHashCode(Object obj) { - if(obj == null) return 0; - - string sObj = obj as string; - if(sObj != null) return String.InternalMarvin32HashString(sObj, sObj.Length, _entropy); - - return obj.GetHashCode(); - } - - // Equals method for the comparer itself. - public override bool Equals(Object obj) { - RandomizedStringEqualityComparer comparer = obj as RandomizedStringEqualityComparer; - return (comparer != null) && (this._entropy == comparer._entropy); - } - - public override int GetHashCode() { - return (this.GetType().GetHashCode() ^ ((int) (_entropy & 0x7FFFFFFF))); - } - - - IEqualityComparer IWellKnownStringEqualityComparer.GetRandomizedEqualityComparer() { - return new RandomizedStringEqualityComparer(); - } - - // We want to serialize the old comparer. - IEqualityComparer IWellKnownStringEqualityComparer.GetEqualityComparerForSerialization() { - return EqualityComparer<string>.Default; - } - } - - // This type is not serializeable by design. It does not exist in previous versions and will be removed - // Once we move the framework to using secure hashing by default. - internal sealed class RandomizedObjectEqualityComparer : IEqualityComparer, IWellKnownStringEqualityComparer - { - private long _entropy; - - public RandomizedObjectEqualityComparer() { - _entropy = HashHelpers.GetEntropy(); - } - - [Pure] - public new bool Equals(Object x, Object y) { - if (x != null) { - if (y != null) return x.Equals(y); - return false; - } - if (y != null) return false; - return true; - } - - [Pure] - public int GetHashCode(Object obj) { - if(obj == null) return 0; - - string sObj = obj as string; - if(sObj != null) return String.InternalMarvin32HashString(sObj, sObj.Length, _entropy); - - return obj.GetHashCode(); - } - - // Equals method for the comparer itself. - public override bool Equals(Object obj){ - RandomizedObjectEqualityComparer comparer = obj as RandomizedObjectEqualityComparer; - return (comparer != null) && (this._entropy == comparer._entropy); - } - - public override int GetHashCode() { - return (this.GetType().GetHashCode() ^ ((int) (_entropy & 0x7FFFFFFF))); - } - - IEqualityComparer IWellKnownStringEqualityComparer.GetRandomizedEqualityComparer() { - return new RandomizedObjectEqualityComparer(); - } - - // We want to serialize the old comparer, which in this case was null. - IEqualityComparer IWellKnownStringEqualityComparer.GetEqualityComparerForSerialization() { - return null; - } - } -#endif } - diff --git a/src/mscorlib/src/System/Collections/Generic/KeyNotFoundException.cs b/src/mscorlib/src/System/Collections/Generic/KeyNotFoundException.cs index ffcd0405fd..1cd18cf808 100644 --- a/src/mscorlib/src/System/Collections/Generic/KeyNotFoundException.cs +++ b/src/mscorlib/src/System/Collections/Generic/KeyNotFoundException.cs @@ -20,7 +20,6 @@ namespace System.Collections.Generic { using System.Runtime.Serialization; [Serializable] - [System.Runtime.InteropServices.ComVisible(true)] public class KeyNotFoundException : SystemException, ISerializable { public KeyNotFoundException () diff --git a/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs b/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs index ad9f7472aa..ba98adad7d 100644 --- a/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs +++ b/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs @@ -16,6 +16,7 @@ namespace System.Collections.Generic { using System; + using System.ComponentModel; using System.Text; // Provides the Create factory method for KeyValuePair<TKey, TValue>. @@ -63,7 +64,7 @@ namespace System.Collections.Generic { return StringBuilderCache.GetStringAndRelease(s); } - // BLOCKED (do not add now): [EditorBrowsable(EditorBrowsableState.Never)] + [EditorBrowsable(EditorBrowsableState.Never)] public void Deconstruct(out TKey key, out TValue value) { key = Key; diff --git a/src/mscorlib/src/System/Collections/Generic/List.cs b/src/mscorlib/src/System/Collections/Generic/List.cs index 3e2947f5f9..362e26599d 100644 --- a/src/mscorlib/src/System/Collections/Generic/List.cs +++ b/src/mscorlib/src/System/Collections/Generic/List.cs @@ -20,7 +20,6 @@ namespace System.Collections.Generic { using System.Diagnostics; using System.Diagnostics.Contracts; using System.Collections.ObjectModel; - using System.Security.Permissions; // Implements a variable-size List that uses an array of objects to store the // elements. A List has a capacity, which is the allocated length @@ -927,7 +926,9 @@ namespace System.Collections.Generic { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); Contract.EndContractBlock(); - Array.Reverse(_items, index, count); + if (count > 1) { + Array.Reverse(_items, index, count); + } _version++; } @@ -966,7 +967,9 @@ namespace System.Collections.Generic { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); Contract.EndContractBlock(); - Array.Sort<T>(_items, index, count, comparer); + if (count > 1) { + Array.Sort<T>(_items, index, count, comparer); + } _version++; } @@ -976,9 +979,10 @@ namespace System.Collections.Generic { } Contract.EndContractBlock(); - if( _size > 0) { + if (_size > 1) { ArraySortHelper<T>.Sort(_items, 0, _size, comparison); } + _version++; } // ToArray returns an array containing the contents of the List. diff --git a/src/mscorlib/src/System/Collections/Hashtable.cs b/src/mscorlib/src/System/Collections/Hashtable.cs index d4c7d8d673..d1831dd97d 100644 --- a/src/mscorlib/src/System/Collections/Hashtable.cs +++ b/src/mscorlib/src/System/Collections/Hashtable.cs @@ -17,7 +17,6 @@ namespace System.Collections { using System; using System.Runtime; using System.Runtime.Serialization; - using System.Security.Permissions; using System.Diagnostics; using System.Threading; using System.Runtime.CompilerServices; @@ -66,9 +65,8 @@ namespace System.Collections { // [DebuggerTypeProxy(typeof(System.Collections.Hashtable.HashtableDebugView))] [DebuggerDisplay("Count = {Count}")] - [System.Runtime.InteropServices.ComVisible(true)] [Serializable] - public class Hashtable : IDictionary, ISerializable, IDeserializationCallback, ICloneable { + internal class Hashtable : IDictionary, ISerializable, IDeserializationCallback, ICloneable { /* Implementation Notes: The generic Dictionary was copied from Hashtable's source - any bug @@ -165,75 +163,6 @@ namespace System.Collections { private IEqualityComparer _keycomparer; private Object _syncRoot; - [Obsolete("Please use EqualityComparer property.")] - protected IHashCodeProvider hcp - { - get - { - if( _keycomparer is CompatibleComparer) { - return ((CompatibleComparer)_keycomparer).HashCodeProvider; - } - else if( _keycomparer == null) { - return null; - } - else { - throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure")); - } - } - set - { - if (_keycomparer is CompatibleComparer) { - CompatibleComparer keyComparer = (CompatibleComparer)_keycomparer; - _keycomparer = new CompatibleComparer(keyComparer.Comparer, value); - } - else if( _keycomparer == null) { - _keycomparer = new CompatibleComparer((IComparer)null, value); - } - else { - throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure")); - } - } - } - - - [Obsolete("Please use KeyComparer properties.")] - protected IComparer comparer - { - get - { - if( _keycomparer is CompatibleComparer) { - return ((CompatibleComparer)_keycomparer).Comparer; - } - else if( _keycomparer == null) { - return null; - } - else { - throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure")); - } - } - set - { - if (_keycomparer is CompatibleComparer) { - CompatibleComparer keyComparer = (CompatibleComparer)_keycomparer; - _keycomparer = new CompatibleComparer(value, keyComparer.HashCodeProvider); - } - else if( _keycomparer == null) { - _keycomparer = new CompatibleComparer(value, (IHashCodeProvider)null); - } - else { - throw new ArgumentException(Environment.GetResourceString("Arg_CannotMixComparisonInfrastructure")); - } - } - } - - protected IEqualityComparer EqualityComparer - { - get - { - return _keycomparer; - } - } - // Note: this constructor is a bogus constructor that does nothing // and is for use only with SyncHashtable. internal Hashtable( bool trash ) @@ -290,126 +219,31 @@ namespace System.Collections { Debug.Assert( loadsize < hashsize, "Invalid hashtable loadsize!"); } - // Constructs a new hashtable with the given initial capacity and load - // factor. The capacity argument serves as an indication of the - // number of entries the hashtable will contain. When this number (or an - // approximation) is known, specifying it in the constructor can eliminate - // a number of resizing operations that would otherwise be performed when - // elements are added to the hashtable. The loadFactor argument - // indicates the maximum ratio of hashtable entries to hashtable buckets. - // Smaller load factors cause faster average lookup times at the cost of - // increased memory consumption. A load factor of 1.0 generally provides - // the best balance between speed and size. The hcp argument - // is used to specify an Object that will provide hash codes for all - // the Objects in the table. Using this, you can in effect override - // GetHashCode() on each Object using your own hash function. The - // comparer argument will let you specify a custom function for - // comparing keys. By specifying user-defined objects for hcp - // and comparer, users could make a hash table using strings - // as keys do case-insensitive lookups. - // - [Obsolete("Please use Hashtable(int, float, IEqualityComparer) instead.")] - public Hashtable(int capacity, float loadFactor, IHashCodeProvider hcp, IComparer comparer) : this(capacity, loadFactor) { - if (hcp == null && comparer == null) { - this._keycomparer = null; - } - else { - this._keycomparer = new CompatibleComparer(comparer,hcp); - } - } - public Hashtable(int capacity, float loadFactor, IEqualityComparer equalityComparer) : this(capacity, loadFactor) { this._keycomparer = equalityComparer; } - - // Constructs a new hashtable using a custom hash function - // and a custom comparison function for keys. This will enable scenarios - // such as doing lookups with case-insensitive strings. - // - [Obsolete("Please use Hashtable(IEqualityComparer) instead.")] - public Hashtable(IHashCodeProvider hcp, IComparer comparer) : this(0, 1.0f, hcp, comparer) { - } public Hashtable(IEqualityComparer equalityComparer) : this(0, 1.0f, equalityComparer) { } - - // Constructs a new hashtable using a custom hash function - // and a custom comparison function for keys. This will enable scenarios - // such as doing lookups with case-insensitive strings. - // - [Obsolete("Please use Hashtable(int, IEqualityComparer) instead.")] - public Hashtable(int capacity, IHashCodeProvider hcp, IComparer comparer) - : this(capacity, 1.0f, hcp, comparer) { - } public Hashtable(int capacity, IEqualityComparer equalityComparer) : this(capacity, 1.0f, equalityComparer) { } - - // Constructs a new hashtable containing a copy of the entries in the given - // dictionary. The hashtable is created with a load factor of 1.0. - // - public Hashtable(IDictionary d) : this(d, 1.0f) { - } - - // Constructs a new hashtable containing a copy of the entries in the given - // dictionary. The hashtable is created with the given load factor. - // - public Hashtable(IDictionary d, float loadFactor) - : this(d, loadFactor, (IEqualityComparer)null) { - } - - [Obsolete("Please use Hashtable(IDictionary, IEqualityComparer) instead.")] - public Hashtable(IDictionary d, IHashCodeProvider hcp, IComparer comparer) - : this(d, 1.0f, hcp, comparer) { - } - - public Hashtable(IDictionary d, IEqualityComparer equalityComparer) - : this(d, 1.0f, equalityComparer) { - } - [Obsolete("Please use Hashtable(IDictionary, float, IEqualityComparer) instead.")] - public Hashtable(IDictionary d, float loadFactor, IHashCodeProvider hcp, IComparer comparer) - : this((d != null ? d.Count : 0), loadFactor, hcp, comparer) { - if (d==null) - throw new ArgumentNullException(nameof(d), Environment.GetResourceString("ArgumentNull_Dictionary")); - Contract.EndContractBlock(); - - IDictionaryEnumerator e = d.GetEnumerator(); - while (e.MoveNext()) Add(e.Key, e.Value); - } - - public Hashtable(IDictionary d, float loadFactor, IEqualityComparer equalityComparer) - : this((d != null ? d.Count : 0), loadFactor, equalityComparer) { - if (d==null) - throw new ArgumentNullException(nameof(d), Environment.GetResourceString("ArgumentNull_Dictionary")); - Contract.EndContractBlock(); - - IDictionaryEnumerator e = d.GetEnumerator(); - while (e.MoveNext()) Add(e.Key, e.Value); - } - - protected Hashtable(SerializationInfo info, StreamingContext context) { - //We can't do anything with the keys and values until the entire graph has been deserialized - //and we have a reasonable estimate that GetHashCode is not going to fail. For the time being, - //we'll just cache this. The graph is not valid until OnDeserialization has been called. - HashHelpers.SerializationInfoTable.Add(this, info); - } - - // ‘InitHash’ is basically an implementation of classic DoubleHashing (see http://en.wikipedia.org/wiki/Double_hashing) + // InitHash is basically an implementation of classic DoubleHashing (see http://en.wikipedia.org/wiki/Double_hashing) // - // 1) The only ‘correctness’ requirement is that the ‘increment’ used to probe + // 1) The only correctness requirement is that the increment used to probe // a. Be non-zero - // b. Be relatively prime to the table size ‘hashSize’. (This is needed to insure you probe all entries in the table before you ‘wrap’ and visit entries already probed) + // b. Be relatively prime to the table size hashSize. (This is needed to insure you probe all entries in the table before you wrap and visit entries already probed) // 2) Because we choose table sizes to be primes, we just need to insure that the increment is 0 < incr < hashSize // // Thus this function would work: Incr = 1 + (seed % (hashSize-1)) // - // While this works well for ‘uniformly distributed’ keys, in practice, non-uniformity is common. - // In particular in practice we can see ‘mostly sequential’ where you get long clusters of keys that ‘pack’. - // To avoid bad behavior you want it to be the case that the increment is ‘large’ even for ‘small’ values (because small - // values tend to happen more in practice). Thus we multiply ‘seed’ by a number that will make these small values - // bigger (and not hurt large values). We picked HashPrime (101) because it was prime, and if ‘hashSize-1’ is not a multiple of HashPrime + // While this works well for uniformly distributed keys, in practice, non-uniformity is common. + // In particular in practice we can see mostly sequential where you get long clusters of keys that pack. + // To avoid bad behavior you want it to be the case that the increment is large even for small values (because small + // values tend to happen more in practice). Thus we multiply seed by a number that will make these small values + // bigger (and not hurt large values). We picked HashPrime (101) because it was prime, and if hashSize-1 is not a multiple of HashPrime // (enforced in GetPrime), then incr has the potential of being every value from 1 to hashSize-1. The choice was largely arbitrary. // // Computes the hash function: H(key, i) = h1(key) + i*h2(key, hashSize). @@ -439,7 +273,6 @@ namespace System.Collections { } // Removes all entries from this hashtable. - [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)] public virtual void Clear() { Debug.Assert(!isWriterInProgress, "Race condition detected in usages of Hashtable - multiple threads appear to be writing to a Hashtable instance simultaneously! Don't do that - use Hashtable.Synchronized."); @@ -517,29 +350,6 @@ namespace System.Collections { } while (b.hash_coll < 0 && ++ntry < lbuckets.Length); return false; } - - // Checks if this hashtable contains an entry with the given value. The - // values of the entries of the hashtable are compared to the given value - // using the Object.Equals method. This method performs a linear - // search and is thus be substantially slower than the ContainsKey - // method. - // - public virtual bool ContainsValue(Object value) { - - if (value == null) { - for (int i = buckets.Length; --i >= 0;) { - if (buckets[i].key != null && buckets[i].key != buckets && buckets[i].val == null) - return true; - } - } - else { - for (int i = buckets.Length; --i >= 0;) { - Object val = buckets[i].val; - if (val!=null && val.Equals(value)) return true; - } - } - return false; - } // Copies the keys of this hashtable to a given array starting at a given // index. This method is used by the implementation of the CopyTo method in @@ -590,25 +400,6 @@ namespace System.Collections { CopyEntries(array, arrayIndex); } - // Copies the values in this Hashtable to an KeyValuePairs array. - // KeyValuePairs is different from Dictionary Entry in that it has special - // debugger attributes on its fields. - - internal virtual KeyValuePairs[] ToKeyValuePairsArray() { - - KeyValuePairs[] array = new KeyValuePairs[count]; - int index = 0; - bucket[] lbuckets = buckets; - for (int i = lbuckets.Length; --i >= 0;) { - Object keyv = lbuckets[i].key; - if ((keyv != null) && (keyv != buckets)){ - array[index++] = new KeyValuePairs(keyv,lbuckets[i].val); - } - } - - return array; - } - // Copies the values of this hashtable to a given array starting at a given // index. This method is used by the implementation of the CopyTo method in @@ -720,7 +511,6 @@ namespace System.Collections { version++; } - [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)] private void rehash( int newsize, bool forceNewHashCode ) { // reset occupancy @@ -853,7 +643,6 @@ namespace System.Collections { // Inserts an entry into this hashtable. This method is called from the Set // and Add methods. If the add parameter is true and the given key already // exists in the hashtable, an exception is thrown. - [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)] private void Insert (Object key, Object nvalue, bool add) { if (key == null) { throw new ArgumentNullException(nameof(key), Environment.GetResourceString("ArgumentNull_Key")); @@ -987,7 +776,6 @@ namespace System.Collections { // key exists in the hashtable, it is removed. An ArgumentException is // thrown if the key is null. // - [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)] public virtual void Remove(Object key) { if (key == null) { throw new ArgumentNullException(nameof(key), Environment.GetResourceString("ArgumentNull_Key")); @@ -1293,13 +1081,6 @@ namespace System.Collections { internal SyncHashtable(Hashtable table) : base(false) { _table = table; } - - internal SyncHashtable(SerializationInfo info, StreamingContext context) : base (info, context) { - _table = (Hashtable)info.GetValue("ParentTable", typeof(Hashtable)); - if (_table==null) { - throw new SerializationException(Environment.GetResourceString("Serialization_InsufficientState")); - } - } /*================================GetObjectData================================= @@ -1379,12 +1160,6 @@ namespace System.Collections { return _table.ContainsKey(key); } - public override bool ContainsValue(Object key) { - lock(_table.SyncRoot) { - return _table.ContainsValue(key); - } - } - public override void CopyTo(Array array, int arrayIndex) { lock (_table.SyncRoot) { _table.CopyTo(array, arrayIndex); @@ -1438,10 +1213,6 @@ namespace System.Collections { public override void OnDeserialization(Object sender) { return; } - - internal override KeyValuePairs[] ToKeyValuePairsArray() { - return _table.ToKeyValuePairsArray(); - } } @@ -1539,23 +1310,6 @@ namespace System.Collections { // internal debug view class for hashtable internal class HashtableDebugView { private Hashtable hashtable; - - public HashtableDebugView( Hashtable hashtable) { - if( hashtable == null) { - throw new ArgumentNullException(nameof(hashtable)); - } - Contract.EndContractBlock(); - - this.hashtable = hashtable; - } - - - [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] - public KeyValuePairs[] Items { - get { - return hashtable.ToKeyValuePairsArray(); - } - } } } @@ -1605,7 +1359,6 @@ namespace System.Collections { } - [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)] public static bool IsPrime(int candidate) { if ((candidate & 1) != 0) @@ -1621,7 +1374,6 @@ namespace System.Collections { return (candidate == 2); } - [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)] public static int GetPrime(int min) { if (min < 0) @@ -1644,11 +1396,6 @@ namespace System.Collections { return min; } - public static int GetMinPrime() - { - return primes[0]; - } - // Returns size of hashtable to grow to. public static int ExpandPrime(int oldSize) { @@ -1670,33 +1417,6 @@ namespace System.Collections { public const int MaxPrimeArrayLength = 0x7FEFFFFD; #if FEATURE_RANDOMIZED_STRING_HASHING - public static bool IsWellKnownEqualityComparer(object comparer) - { - return (comparer == null || comparer == System.Collections.Generic.EqualityComparer<string>.Default || comparer is IWellKnownStringEqualityComparer); - } - - public static IEqualityComparer GetRandomizedEqualityComparer(object comparer) - { - Debug.Assert(comparer == null || comparer == System.Collections.Generic.EqualityComparer<string>.Default || comparer is IWellKnownStringEqualityComparer); - - if(comparer == null) { - return new System.Collections.Generic.RandomizedObjectEqualityComparer(); - } - - if(comparer == System.Collections.Generic.EqualityComparer<string>.Default) { - return new System.Collections.Generic.RandomizedStringEqualityComparer(); - } - - IWellKnownStringEqualityComparer cmp = comparer as IWellKnownStringEqualityComparer; - - if(cmp != null) { - return cmp.GetRandomizedEqualityComparer(); - } - - Debug.Assert(false, "Missing case in GetRandomizedEqualityComparer!"); - - return null; - } public static object GetEqualityComparerForSerialization(object comparer) { @@ -1716,33 +1436,8 @@ namespace System.Collections { } private const int bufferSize = 1024; - private static byte[] data; private static int currentIndex = bufferSize; private static readonly object lockObj = new Object(); - - internal static long GetEntropy() - { - lock(lockObj) { - long ret; - - if(currentIndex == bufferSize) - { - if(data == null) - { - data = new byte[bufferSize]; - Debug.Assert(bufferSize % 8 == 0, "We increment our current index by 8, so our buffer size must be a multiple of 8"); - } - - Microsoft.Win32.Win32Native.Random(true, data, data.Length); - currentIndex = 0; - } - - ret = BitConverter.ToInt64(data, currentIndex); - currentIndex += 8; - - return ret; - } - } #endif // FEATURE_RANDOMIZED_STRING_HASHING } } diff --git a/src/mscorlib/src/System/Collections/ICollection.cs b/src/mscorlib/src/System/Collections/ICollection.cs index 6d4d6e1a93..088928a0ef 100644 --- a/src/mscorlib/src/System/Collections/ICollection.cs +++ b/src/mscorlib/src/System/Collections/ICollection.cs @@ -19,7 +19,6 @@ namespace System.Collections { // Base interface for all collections, defining enumerators, size, and // synchronization methods. - [System.Runtime.InteropServices.ComVisible(true)] public interface ICollection : IEnumerable { // Interfaces are not serialable diff --git a/src/mscorlib/src/System/Collections/IComparer.cs b/src/mscorlib/src/System/Collections/IComparer.cs index d5a3448934..574af1a768 100644 --- a/src/mscorlib/src/System/Collections/IComparer.cs +++ b/src/mscorlib/src/System/Collections/IComparer.cs @@ -21,7 +21,6 @@ namespace System.Collections { // the Array and List classes. // // Interfaces are not serializable - [System.Runtime.InteropServices.ComVisible(true)] public interface IComparer { // Compares two objects. An implementation of this method must return a // value less than zero if x is less than y, zero if x is equal to y, or a diff --git a/src/mscorlib/src/System/Collections/IDictionary.cs b/src/mscorlib/src/System/Collections/IDictionary.cs index 4da89d6983..519d53ed55 100644 --- a/src/mscorlib/src/System/Collections/IDictionary.cs +++ b/src/mscorlib/src/System/Collections/IDictionary.cs @@ -21,7 +21,6 @@ namespace System.Collections { // Keys can be any non-null object. Values can be any object. // You can look up a value in an IDictionary via the default indexed // property, Items. - [System.Runtime.InteropServices.ComVisible(true)] public interface IDictionary : ICollection { // Interfaces are not serializable diff --git a/src/mscorlib/src/System/Collections/IDictionaryEnumerator.cs b/src/mscorlib/src/System/Collections/IDictionaryEnumerator.cs index b995a04a0e..2f1add682c 100644 --- a/src/mscorlib/src/System/Collections/IDictionaryEnumerator.cs +++ b/src/mscorlib/src/System/Collections/IDictionaryEnumerator.cs @@ -44,7 +44,6 @@ namespace System.Collections { // return the same DictionaryEntry and avoids boxing the DictionaryEntry (boxing // is somewhat expensive). // -[System.Runtime.InteropServices.ComVisible(true)] public interface IDictionaryEnumerator : IEnumerator { // Returns the key of the current element of the enumeration. The returned diff --git a/src/mscorlib/src/System/Collections/IEnumerable.cs b/src/mscorlib/src/System/Collections/IEnumerable.cs index 5fa63f15d0..1d8e71cf07 100644 --- a/src/mscorlib/src/System/Collections/IEnumerable.cs +++ b/src/mscorlib/src/System/Collections/IEnumerable.cs @@ -21,7 +21,6 @@ namespace System.Collections { // Implement this interface if you need to support VB's foreach semantics. // Also, COM classes that support an enumerator will also implement this interface. [Guid("496B0ABE-CDEE-11d3-88E8-00902754C43A")] - [System.Runtime.InteropServices.ComVisible(true)] public interface IEnumerable { // Interfaces are not serializable diff --git a/src/mscorlib/src/System/Collections/IEnumerator.cs b/src/mscorlib/src/System/Collections/IEnumerator.cs index 99509d15ea..4c4fc085e8 100644 --- a/src/mscorlib/src/System/Collections/IEnumerator.cs +++ b/src/mscorlib/src/System/Collections/IEnumerator.cs @@ -20,7 +20,6 @@ namespace System.Collections { // Base interface for all enumerators, providing a simple approach // to iterating over a collection. [Guid("496B0ABF-CDEE-11d3-88E8-00902754C43A")] - [System.Runtime.InteropServices.ComVisible(true)] public interface IEnumerator { // Interfaces are not serializable diff --git a/src/mscorlib/src/System/Collections/IEqualityComparer.cs b/src/mscorlib/src/System/Collections/IEqualityComparer.cs index 50c732f47c..f591b11152 100644 --- a/src/mscorlib/src/System/Collections/IEqualityComparer.cs +++ b/src/mscorlib/src/System/Collections/IEqualityComparer.cs @@ -19,7 +19,6 @@ namespace System.Collections { using System; // An IEqualityComparer is a mechanism to consume custom performant comparison infrastructure // that can be consumed by some of the common collections. - [System.Runtime.InteropServices.ComVisible(true)] public interface IEqualityComparer { bool Equals(Object x, Object y); int GetHashCode(Object obj); diff --git a/src/mscorlib/src/System/Collections/IHashCodeProvider.cs b/src/mscorlib/src/System/Collections/IHashCodeProvider.cs index aefa15e1e5..0ae1e3295b 100644 --- a/src/mscorlib/src/System/Collections/IHashCodeProvider.cs +++ b/src/mscorlib/src/System/Collections/IHashCodeProvider.cs @@ -19,8 +19,7 @@ namespace System.Collections { // Provides a mechanism for a hash table user to override the default // GetHashCode() function on Objects, providing their own hash function. [Obsolete("Please use IEqualityComparer instead.")] - [System.Runtime.InteropServices.ComVisible(true)] - public interface IHashCodeProvider + internal interface IHashCodeProvider { // Interfaces are not serializable // Returns a hash code for the given object. diff --git a/src/mscorlib/src/System/Collections/IList.cs b/src/mscorlib/src/System/Collections/IList.cs index 8bdfe4c1d0..8b63400852 100644 --- a/src/mscorlib/src/System/Collections/IList.cs +++ b/src/mscorlib/src/System/Collections/IList.cs @@ -21,7 +21,6 @@ namespace System.Collections { // An IList is an ordered collection of objects. The exact ordering // is up to the implementation of the list, ranging from a sorted // order to insertion order. - [System.Runtime.InteropServices.ComVisible(true)] public interface IList : ICollection { // The Item property provides methods to read and edit entries in the List. diff --git a/src/mscorlib/src/System/Collections/KeyValuePairs.cs b/src/mscorlib/src/System/Collections/KeyValuePairs.cs deleted file mode 100644 index 22bf92c456..0000000000 --- a/src/mscorlib/src/System/Collections/KeyValuePairs.cs +++ /dev/null @@ -1,40 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** -** -** -** -** Purpose: KeyValuePairs to display items in collection class under debugger -** -** -===========================================================*/ - -namespace System.Collections { - using System.Diagnostics; - - [DebuggerDisplay("{value}", Name = "[{key}]", Type = "" )] - internal class KeyValuePairs { - [DebuggerBrowsable(DebuggerBrowsableState.Never)] - private object key; - - [DebuggerBrowsable(DebuggerBrowsableState.Never)] - private object value; - - public KeyValuePairs(object key, object value) { - this.value = value; - this.key = key; - } - - public object Key { - get { return key; } - } - - public object Value { - get { return value; } - } - } -} diff --git a/src/mscorlib/src/System/Collections/ListDictionaryInternal.cs b/src/mscorlib/src/System/Collections/ListDictionaryInternal.cs index be5490b194..617c33707a 100644 --- a/src/mscorlib/src/System/Collections/ListDictionaryInternal.cs +++ b/src/mscorlib/src/System/Collections/ListDictionaryInternal.cs @@ -49,13 +49,6 @@ namespace System.Collections { } Contract.EndContractBlock(); -#if FEATURE_SERIALIZATION - if (!key.GetType().IsSerializable) - throw new ArgumentException(Environment.GetResourceString("Argument_NotSerializable"), nameof(key)); - - if( (value != null) && (!value.GetType().IsSerializable ) ) - throw new ArgumentException(Environment.GetResourceString("Argument_NotSerializable"), nameof(value)); -#endif version++; DictionaryNode last = null; @@ -136,13 +129,6 @@ namespace System.Collections { } Contract.EndContractBlock(); -#if FEATURE_SERIALIZATION - if (!key.GetType().IsSerializable) - throw new ArgumentException(Environment.GetResourceString("Argument_NotSerializable"), nameof(key) ); - - if( (value != null) && (!value.GetType().IsSerializable) ) - throw new ArgumentException(Environment.GetResourceString("Argument_NotSerializable"), nameof(value)); -#endif version++; DictionaryNode last = null; diff --git a/src/mscorlib/src/System/Collections/ObjectModel/Collection.cs b/src/mscorlib/src/System/Collections/ObjectModel/Collection.cs index a3804ad7ab..b3b19fb616 100644 --- a/src/mscorlib/src/System/Collections/ObjectModel/Collection.cs +++ b/src/mscorlib/src/System/Collections/ObjectModel/Collection.cs @@ -13,7 +13,6 @@ namespace System.Collections.ObjectModel using System.Runtime; [Serializable] - [System.Runtime.InteropServices.ComVisible(false)] [DebuggerTypeProxy(typeof(Mscorlib_CollectionDebugView<>))] [DebuggerDisplay("Count = {Count}")] public class Collection<T>: IList<T>, IList, IReadOnlyList<T> diff --git a/src/mscorlib/src/System/Collections/ObjectModel/KeyedCollection.cs b/src/mscorlib/src/System/Collections/ObjectModel/KeyedCollection.cs index b6fe6ded29..3fe7716203 100644 --- a/src/mscorlib/src/System/Collections/ObjectModel/KeyedCollection.cs +++ b/src/mscorlib/src/System/Collections/ObjectModel/KeyedCollection.cs @@ -12,7 +12,6 @@ namespace System.Collections.ObjectModel using System.Diagnostics.Contracts; [Serializable] - [System.Runtime.InteropServices.ComVisible(false)] [DebuggerTypeProxy(typeof(Mscorlib_KeyedCollectionDebugView<,>))] [DebuggerDisplay("Count = {Count}")] public abstract class KeyedCollection<TKey,TItem>: Collection<TItem> diff --git a/src/mscorlib/src/System/Collections/ObjectModel/ReadOnlyCollection.cs b/src/mscorlib/src/System/Collections/ObjectModel/ReadOnlyCollection.cs index a0b8b3b459..10c48cf76d 100644 --- a/src/mscorlib/src/System/Collections/ObjectModel/ReadOnlyCollection.cs +++ b/src/mscorlib/src/System/Collections/ObjectModel/ReadOnlyCollection.cs @@ -13,7 +13,6 @@ namespace System.Collections.ObjectModel using System.Runtime; [Serializable] - [System.Runtime.InteropServices.ComVisible(false)] [DebuggerTypeProxy(typeof(Mscorlib_CollectionDebugView<>))] [DebuggerDisplay("Count = {Count}")] public class ReadOnlyCollection<T>: IList<T>, IList, IReadOnlyList<T> diff --git a/src/mscorlib/src/System/Collections/SortedList.cs b/src/mscorlib/src/System/Collections/SortedList.cs deleted file mode 100644 index 4a480a2c37..0000000000 --- a/src/mscorlib/src/System/Collections/SortedList.cs +++ /dev/null @@ -1,1008 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** -** -** -** Purpose: A sorted dictionary. -** -** -===========================================================*/ -namespace System.Collections { - using System; - using System.Security.Permissions; - using System.Diagnostics; - using System.Diagnostics.CodeAnalysis; - using System.Diagnostics.Contracts; - using System.Globalization; - - // The SortedList class implements a sorted list of keys and values. Entries in - // a sorted list are sorted by their keys and are accessible both by key and by - // index. The keys of a sorted list can be ordered either according to a - // specific IComparer implementation given when the sorted list is - // instantiated, or according to the IComparable implementation provided - // by the keys themselves. In either case, a sorted list does not allow entries - // with duplicate keys. - // - // A sorted list internally maintains two arrays that store the keys and - // values of the entries. The capacity of a sorted list is the allocated - // length of these internal arrays. As elements are added to a sorted list, the - // capacity of the sorted list is automatically increased as required by - // reallocating the internal arrays. The capacity is never automatically - // decreased, but users can call either TrimToSize or - // Capacity explicitly. - // - // The GetKeyList and GetValueList methods of a sorted list - // provides access to the keys and values of the sorted list in the form of - // List implementations. The List objects returned by these - // methods are aliases for the underlying sorted list, so modifications - // made to those lists are directly reflected in the sorted list, and vice - // versa. - // - // The SortedList class provides a convenient way to create a sorted - // copy of another dictionary, such as a Hashtable. For example: - // - // Hashtable h = new Hashtable(); - // h.Add(...); - // h.Add(...); - // ... - // SortedList s = new SortedList(h); - // - // The last line above creates a sorted list that contains a copy of the keys - // and values stored in the hashtable. In this particular example, the keys - // will be ordered according to the IComparable interface, which they - // all must implement. To impose a different ordering, SortedList also - // has a constructor that allows a specific IComparer implementation to - // be specified. - // - [DebuggerTypeProxy(typeof(System.Collections.SortedList.SortedListDebugView))] - [DebuggerDisplay("Count = {Count}")] - [System.Runtime.InteropServices.ComVisible(true)] - [Obsolete("Non-generic collections have been deprecated. Please use collections in System.Collections.Generic.")] - [Serializable] - public class SortedList : IDictionary, ICloneable - { - private Object[] keys; - private Object[] values; - private int _size; - private int version; - private IComparer comparer; - private KeyList keyList; - private ValueList valueList; - [NonSerialized] - private Object _syncRoot; - - private const int _defaultCapacity = 16; - - private static Object[] emptyArray = EmptyArray<Object>.Value; - - // Constructs a new sorted list. The sorted list is initially empty and has - // a capacity of zero. Upon adding the first element to the sorted list the - // capacity is increased to 16, and then increased in multiples of two as - // required. The elements of the sorted list are ordered according to the - // IComparable interface, which must be implemented by the keys of - // all entries added to the sorted list. - public SortedList() { - Init(); - } - private void Init() - { - keys = emptyArray; - values = emptyArray; - _size = 0; - comparer = new Comparer(CultureInfo.CurrentCulture); - } - - // Constructs a new sorted list. The sorted list is initially empty and has - // a capacity of zero. Upon adding the first element to the sorted list the - // capacity is increased to 16, and then increased in multiples of two as - // required. The elements of the sorted list are ordered according to the - // IComparable interface, which must be implemented by the keys of - // all entries added to the sorted list. - // - public SortedList(int initialCapacity) { - if (initialCapacity < 0) - throw new ArgumentOutOfRangeException(nameof(initialCapacity), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - Contract.EndContractBlock(); - keys = new Object[initialCapacity]; - values = new Object[initialCapacity]; - comparer = new Comparer(CultureInfo.CurrentCulture); - } - - // Constructs a new sorted list with a given IComparer - // implementation. The sorted list is initially empty and has a capacity of - // zero. Upon adding the first element to the sorted list the capacity is - // increased to 16, and then increased in multiples of two as required. The - // elements of the sorted list are ordered according to the given - // IComparer implementation. If comparer is null, the - // elements are compared to each other using the IComparable - // interface, which in that case must be implemented by the keys of all - // entries added to the sorted list. - // - public SortedList(IComparer comparer) - : this() { - if (comparer != null) this.comparer = comparer; - } - - // Constructs a new sorted list with a given IComparer - // implementation and a given initial capacity. The sorted list is - // initially empty, but will have room for the given number of elements - // before any reallocations are required. The elements of the sorted list - // are ordered according to the given IComparer implementation. If - // comparer is null, the elements are compared to each other using - // the IComparable interface, which in that case must be implemented - // by the keys of all entries added to the sorted list. - // - public SortedList(IComparer comparer, int capacity) - : this(comparer) { - Capacity = capacity; - } - - // Constructs a new sorted list containing a copy of the entries in the - // given dictionary. The elements of the sorted list are ordered according - // to the IComparable interface, which must be implemented by the - // keys of all entries in the the given dictionary as well as keys - // subsequently added to the sorted list. - // - public SortedList(IDictionary d) - : this(d, null) { - } - - // Constructs a new sorted list containing a copy of the entries in the - // given dictionary. The elements of the sorted list are ordered according - // to the given IComparer implementation. If comparer is - // null, the elements are compared to each other using the - // IComparable interface, which in that case must be implemented - // by the keys of all entries in the the given dictionary as well as keys - // subsequently added to the sorted list. - // - public SortedList(IDictionary d, IComparer comparer) - : this(comparer, (d != null ? d.Count : 0)) { - if (d==null) - throw new ArgumentNullException(nameof(d), Environment.GetResourceString("ArgumentNull_Dictionary")); - Contract.EndContractBlock(); - d.Keys.CopyTo(keys, 0); - d.Values.CopyTo(values, 0); - Array.Sort(keys, values, comparer); - _size = d.Count; - } - - // Adds an entry with the given key and value to this sorted list. An - // ArgumentException is thrown if the key is already present in the sorted list. - // - public virtual void Add(Object key, Object value) { - if (key == null) throw new ArgumentNullException(nameof(key), Environment.GetResourceString("ArgumentNull_Key")); - Contract.EndContractBlock(); - int i = Array.BinarySearch(keys, 0, _size, key, comparer); - if (i >= 0) - throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", GetKey(i), key)); - Insert(~i, key, value); - } - - // Returns the capacity of this sorted list. The capacity of a sorted list - // represents the allocated length of the internal arrays used to store the - // keys and values of the list, and thus also indicates the maximum number - // of entries the list can contain before a reallocation of the internal - // arrays is required. - // - public virtual int Capacity { - get { - return keys.Length; - } - set { - if (value < Count) { - throw new ArgumentOutOfRangeException(nameof(value), Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity")); - } - Contract.EndContractBlock(); - - if (value != keys.Length) { - if (value > 0) { - Object[] newKeys = new Object[value]; - Object[] newValues = new Object[value]; - if (_size > 0) { - Array.Copy(keys, 0, newKeys, 0, _size); - Array.Copy(values, 0, newValues, 0, _size); - } - keys = newKeys; - values = newValues; - } - else { - // size can only be zero here. - Debug.Assert( _size == 0, "Size is not zero"); - keys = emptyArray; - values = emptyArray; - } - } - } - } - - // Returns the number of entries in this sorted list. - // - public virtual int Count { - get { - return _size; - } - } - - // Returns a collection representing the keys of this sorted list. This - // method returns the same object as GetKeyList, but typed as an - // ICollection instead of an IList. - // - public virtual ICollection Keys { - get { - return GetKeyList(); - } - } - - // Returns a collection representing the values of this sorted list. This - // method returns the same object as GetValueList, but typed as an - // ICollection instead of an IList. - // - public virtual ICollection Values { - get { - return GetValueList(); - } - } - - // Is this SortedList read-only? - public virtual bool IsReadOnly { - get { return false; } - } - - public virtual bool IsFixedSize { - get { return false; } - } - - // Is this SortedList synchronized (thread-safe)? - public virtual bool IsSynchronized { - get { return false; } - } - - // Synchronization root for this object. - public virtual Object SyncRoot { - get { - if( _syncRoot == null) { - System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null); - } - return _syncRoot; - } - } - - // Removes all entries from this sorted list. - public virtual void Clear() { - // clear does not change the capacity - version++; - Array.Clear(keys, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references. - Array.Clear(values, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references. - _size = 0; - - } - - // Makes a virtually identical copy of this SortedList. This is a shallow - // copy. IE, the Objects in the SortedList are not cloned - we copy the - // references to those objects. - public virtual Object Clone() - { - SortedList sl = new SortedList(_size); - Array.Copy(keys, 0, sl.keys, 0, _size); - Array.Copy(values, 0, sl.values, 0, _size); - sl._size = _size; - sl.version = version; - sl.comparer = comparer; - // Don't copy keyList nor valueList. - return sl; - } - - - // Checks if this sorted list contains an entry with the given key. - // - public virtual bool Contains(Object key) { - return IndexOfKey(key) >= 0; - } - - // Checks if this sorted list contains an entry with the given key. - // - public virtual bool ContainsKey(Object key) { - // Yes, this is a SPEC'ed duplicate of Contains(). - return IndexOfKey(key) >= 0; - } - - // Checks if this sorted list contains an entry with the given value. The - // values of the entries of the sorted list are compared to the given value - // using the Object.Equals method. This method performs a linear - // search and is substantially slower than the Contains - // method. - // - public virtual bool ContainsValue(Object value) { - return IndexOfValue(value) >= 0; - } - - // Copies the values in this SortedList to an array. - public virtual void CopyTo(Array array, int arrayIndex) { - if (array == null) - throw new ArgumentNullException(nameof(array), Environment.GetResourceString("ArgumentNull_Array")); - if (array.Rank != 1) - throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); - if (arrayIndex < 0) - throw new ArgumentOutOfRangeException(nameof(arrayIndex), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (array.Length - arrayIndex < Count) - throw new ArgumentException(Environment.GetResourceString("Arg_ArrayPlusOffTooSmall")); - Contract.EndContractBlock(); - for (int i = 0; i<Count; i++) { - DictionaryEntry entry = new DictionaryEntry(keys[i],values[i]); - array.SetValue(entry, i + arrayIndex); - } - } - - // Copies the values in this SortedList to an KeyValuePairs array. - // KeyValuePairs is different from Dictionary Entry in that it has special - // debugger attributes on its fields. - - internal virtual KeyValuePairs[] ToKeyValuePairsArray() { - KeyValuePairs[] array = new KeyValuePairs[Count]; - for (int i = 0; i < Count; i++) { - array[i] = new KeyValuePairs(keys[i],values[i]); - } - return array; - } - - // Ensures that the capacity of this sorted list is at least the given - // minimum value. If the currect capacity of the list is less than - // min, the capacity is increased to twice the current capacity or - // to min, whichever is larger. - private void EnsureCapacity(int min) { - int newCapacity = keys.Length == 0? 16: keys.Length * 2; - // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow. - // Note that this check works even when _items.Length overflowed thanks to the (uint) cast - if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength; - if (newCapacity < min) newCapacity = min; - Capacity = newCapacity; - } - - // Returns the value of the entry at the given index. - // - public virtual Object GetByIndex(int index) { - if (index < 0 || index >= Count) - throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - Contract.EndContractBlock(); - return values[index]; - } - - // Returns an IEnumerator for this sorted list. If modifications - // made to the sorted list while an enumeration is in progress, - // the MoveNext and Remove methods - // of the enumerator will throw an exception. - // - IEnumerator IEnumerable.GetEnumerator() { - return new SortedListEnumerator(this, 0, _size, SortedListEnumerator.DictEntry); - } - - // Returns an IDictionaryEnumerator for this sorted list. If modifications - // made to the sorted list while an enumeration is in progress, - // the MoveNext and Remove methods - // of the enumerator will throw an exception. - // - public virtual IDictionaryEnumerator GetEnumerator() { - return new SortedListEnumerator(this, 0, _size, SortedListEnumerator.DictEntry); - } - - // Returns the key of the entry at the given index. - // - public virtual Object GetKey(int index) { - if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - Contract.EndContractBlock(); - return keys[index]; - } - - // Returns an IList representing the keys of this sorted list. The - // returned list is an alias for the keys of this sorted list, so - // modifications made to the returned list are directly reflected in the - // underlying sorted list, and vice versa. The elements of the returned - // list are ordered in the same way as the elements of the sorted list. The - // returned list does not support adding, inserting, or modifying elements - // (the Add, AddRange, Insert, InsertRange, - // Reverse, Set, SetRange, and Sort methods - // throw exceptions), but it does allow removal of elements (through the - // Remove and RemoveRange methods or through an enumerator). - // Null is an invalid key value. - // - public virtual IList GetKeyList() { - if (keyList == null) keyList = new KeyList(this); - return keyList; - } - - // Returns an IList representing the values of this sorted list. The - // returned list is an alias for the values of this sorted list, so - // modifications made to the returned list are directly reflected in the - // underlying sorted list, and vice versa. The elements of the returned - // list are ordered in the same way as the elements of the sorted list. The - // returned list does not support adding or inserting elements (the - // Add, AddRange, Insert and InsertRange - // methods throw exceptions), but it does allow modification and removal of - // elements (through the Remove, RemoveRange, Set and - // SetRange methods or through an enumerator). - // - public virtual IList GetValueList() { - if (valueList == null) valueList = new ValueList(this); - return valueList; - } - - // Returns the value associated with the given key. If an entry with the - // given key is not found, the returned value is null. - // - public virtual Object this[Object key] { - get { - int i = IndexOfKey(key); - if (i >= 0) return values[i]; - return null; - } - set { - if (key == null) throw new ArgumentNullException(nameof(key), Environment.GetResourceString("ArgumentNull_Key")); - Contract.EndContractBlock(); - int i = Array.BinarySearch(keys, 0, _size, key, comparer); - if (i >= 0) { - values[i] = value; - version++; - return; - } - Insert(~i, key, value); - } - } - - // Returns the index of the entry with a given key in this sorted list. The - // key is located through a binary search, and thus the average execution - // time of this method is proportional to Log2(size), where - // size is the size of this sorted list. The returned value is -1 if - // the given key does not occur in this sorted list. Null is an invalid - // key value. - // - public virtual int IndexOfKey(Object key) { - if (key == null) - throw new ArgumentNullException(nameof(key), Environment.GetResourceString("ArgumentNull_Key")); - Contract.EndContractBlock(); - int ret = Array.BinarySearch(keys, 0, _size, key, comparer); - return ret >=0 ? ret : -1; - } - - // Returns the index of the first occurrence of an entry with a given value - // in this sorted list. The entry is located through a linear search, and - // thus the average execution time of this method is proportional to the - // size of this sorted list. The elements of the list are compared to the - // given value using the Object.Equals method. - // - public virtual int IndexOfValue(Object value) { - return Array.IndexOf(values, value, 0, _size); - } - - // Inserts an entry with a given key and value at a given index. - private void Insert(int index, Object key, Object value) { - if (_size == keys.Length) EnsureCapacity(_size + 1); - if (index < _size) { - Array.Copy(keys, index, keys, index + 1, _size - index); - Array.Copy(values, index, values, index + 1, _size - index); - } - keys[index] = key; - values[index] = value; - _size++; - version++; - } - - // Removes the entry at the given index. The size of the sorted list is - // decreased by one. - // - public virtual void RemoveAt(int index) { - if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - Contract.EndContractBlock(); - _size--; - if (index < _size) { - Array.Copy(keys, index + 1, keys, index, _size - index); - Array.Copy(values, index + 1, values, index, _size - index); - } - keys[_size] = null; - values[_size] = null; - version++; - } - - // Removes an entry from this sorted list. If an entry with the specified - // key exists in the sorted list, it is removed. An ArgumentException is - // thrown if the key is null. - // - public virtual void Remove(Object key) { - int i = IndexOfKey(key); - if (i >= 0) - RemoveAt(i); - } - - // Sets the value at an index to a given value. The previous value of - // the given entry is overwritten. - // - public virtual void SetByIndex(int index, Object value) { - if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_Index")); - Contract.EndContractBlock(); - values[index] = value; - version++; - } - - // Returns a thread-safe SortedList. - // - public static SortedList Synchronized(SortedList list) { - if (list==null) - throw new ArgumentNullException(nameof(list)); - Contract.EndContractBlock(); - return new SyncSortedList(list); - } - - // Sets the capacity of this sorted list to the size of the sorted list. - // This method can be used to minimize a sorted list's memory overhead once - // it is known that no new elements will be added to the sorted list. To - // completely clear a sorted list and release all memory referenced by the - // sorted list, execute the following statements: - // - // sortedList.Clear(); - // sortedList.TrimToSize(); - // - public virtual void TrimToSize() { - Capacity = _size; - } - - [Serializable] - private class SyncSortedList : SortedList - { - private SortedList _list; - private Object _root; - - - internal SyncSortedList(SortedList list) { - _list = list; - _root = list.SyncRoot; - } - - public override int Count { - get { lock(_root) { return _list.Count; } } - } - - public override Object SyncRoot { - get { return _root; } - } - - public override bool IsReadOnly { - get { return _list.IsReadOnly; } - } - - public override bool IsFixedSize { - get { return _list.IsFixedSize; } - } - - - public override bool IsSynchronized { - get { return true; } - } - - public override Object this[Object key] { - get { - lock(_root) { - return _list[key]; - } - } - set { - lock(_root) { - _list[key] = value; - } - } - } - - public override void Add(Object key, Object value) { - lock(_root) { - _list.Add(key, value); - } - } - - public override int Capacity { - get{ lock(_root) { return _list.Capacity; } } - } - - public override void Clear() { - lock(_root) { - _list.Clear(); - } - } - - public override Object Clone() { - lock(_root) { - return _list.Clone(); - } - } - - public override bool Contains(Object key) { - lock(_root) { - return _list.Contains(key); - } - } - - public override bool ContainsKey(Object key) { - lock(_root) { - return _list.ContainsKey(key); - } - } - - public override bool ContainsValue(Object key) { - lock(_root) { - return _list.ContainsValue(key); - } - } - - public override void CopyTo(Array array, int index) { - lock(_root) { - _list.CopyTo(array, index); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override Object GetByIndex(int index) { - lock(_root) { - return _list.GetByIndex(index); - } - } - - public override IDictionaryEnumerator GetEnumerator() { - lock(_root) { - return _list.GetEnumerator(); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override Object GetKey(int index) { - lock(_root) { - return _list.GetKey(index); - } - } - - public override IList GetKeyList() { - lock(_root) { - return _list.GetKeyList(); - } - } - - public override IList GetValueList() { - lock(_root) { - return _list.GetValueList(); - } - } - - public override int IndexOfKey(Object key) { - if (key == null) - throw new ArgumentNullException(nameof(key), Environment.GetResourceString("ArgumentNull_Key")); - Contract.EndContractBlock(); - - lock(_root) { - return _list.IndexOfKey(key); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override int IndexOfValue(Object value) { - lock(_root) { - return _list.IndexOfValue(value); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void RemoveAt(int index) { - lock(_root) { - _list.RemoveAt(index); - } - } - - public override void Remove(Object key) { - lock(_root) { - _list.Remove(key); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Skip extra error checking to avoid *potential* AppCompat problems. - public override void SetByIndex(int index, Object value) { - lock(_root) { - _list.SetByIndex(index, value); - } - } - - internal override KeyValuePairs[] ToKeyValuePairsArray() { - return _list.ToKeyValuePairsArray(); - } - - public override void TrimToSize() { - lock(_root) { - _list.TrimToSize(); - } - } - } - - - [Serializable] - private class SortedListEnumerator : IDictionaryEnumerator, ICloneable - { - private SortedList sortedList; - private Object key; - private Object value; - private int index; - private int startIndex; // Store for Reset. - private int endIndex; - private int version; - private bool current; // Is the current element valid? - private int getObjectRetType; // What should GetObject return? - - internal const int Keys = 1; - internal const int Values = 2; - internal const int DictEntry = 3; - - internal SortedListEnumerator(SortedList sortedList, int index, int count, - int getObjRetType) { - this.sortedList = sortedList; - this.index = index; - startIndex = index; - endIndex = index + count; - version = sortedList.version; - getObjectRetType = getObjRetType; - current = false; - } - - public Object Clone() - { - return MemberwiseClone(); - } - - public virtual Object Key { - get { - if (version != sortedList.version) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion")); - if (current == false) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumOpCantHappen")); - return key; - } - } - - public virtual bool MoveNext() { - if (version != sortedList.version) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion")); - if (index < endIndex) { - key = sortedList.keys[index]; - value = sortedList.values[index]; - index++; - current = true; - return true; - } - key = null; - value = null; - current = false; - return false; - } - - public virtual DictionaryEntry Entry { - get { - if (version != sortedList.version) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion")); - if (current == false) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumOpCantHappen")); - return new DictionaryEntry(key, value); - } - } - - public virtual Object Current { - get { - if (current == false) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumOpCantHappen")); - - if (getObjectRetType==Keys) - return key; - else if (getObjectRetType==Values) - return value; - else - return new DictionaryEntry(key, value); - } - } - - public virtual Object Value { - get { - if (version != sortedList.version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); - if (current == false) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumOpCantHappen")); - return value; - } - } - - public virtual void Reset() { - if (version != sortedList.version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); - index = startIndex; - current = false; - key = null; - value = null; - } - } - - [Serializable] - private class KeyList : IList - { - private SortedList sortedList; - - internal KeyList(SortedList sortedList) { - this.sortedList = sortedList; - } - - public virtual int Count { - get { return sortedList._size; } - } - - public virtual bool IsReadOnly { - get { return true; } - } - - public virtual bool IsFixedSize { - get { return true; } - } - - public virtual bool IsSynchronized { - get { return sortedList.IsSynchronized; } - } - - public virtual Object SyncRoot { - get { return sortedList.SyncRoot; } - } - - public virtual int Add(Object key) { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - // return 0; // suppress compiler warning - } - - public virtual void Clear() { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - } - - public virtual bool Contains(Object key) { - return sortedList.Contains(key); - } - - public virtual void CopyTo(Array array, int arrayIndex) { - if (array != null && array.Rank != 1) - throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); - Contract.EndContractBlock(); - - // defer error checking to Array.Copy - Array.Copy(sortedList.keys, 0, array, arrayIndex, sortedList.Count); - } - - public virtual void Insert(int index, Object value) { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - } - - public virtual Object this[int index] { - get { - return sortedList.GetKey(index); - } - set { - throw new NotSupportedException(Environment.GetResourceString("NotSupported_KeyCollectionSet")); - } - } - - public virtual IEnumerator GetEnumerator() { - return new SortedListEnumerator(sortedList, 0, sortedList.Count, SortedListEnumerator.Keys); - } - - public virtual int IndexOf(Object key) { - if (key==null) - throw new ArgumentNullException(nameof(key), Environment.GetResourceString("ArgumentNull_Key")); - Contract.EndContractBlock(); - - int i = Array.BinarySearch(sortedList.keys, 0, - sortedList.Count, key, sortedList.comparer); - if (i >= 0) return i; - return -1; - } - - public virtual void Remove(Object key) { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - } - - public virtual void RemoveAt(int index) { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - } - } - - [Serializable] - private class ValueList : IList - { - private SortedList sortedList; - - internal ValueList(SortedList sortedList) { - this.sortedList = sortedList; - } - - public virtual int Count { - get { return sortedList._size; } - } - - public virtual bool IsReadOnly { - get { return true; } - } - - public virtual bool IsFixedSize { - get { return true; } - } - - public virtual bool IsSynchronized { - get { return sortedList.IsSynchronized; } - } - - public virtual Object SyncRoot { - get { return sortedList.SyncRoot; } - } - - public virtual int Add(Object key) { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - } - - public virtual void Clear() { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - } - - public virtual bool Contains(Object value) { - return sortedList.ContainsValue(value); - } - - public virtual void CopyTo(Array array, int arrayIndex) { - if (array != null && array.Rank != 1) - throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); - Contract.EndContractBlock(); - - // defer error checking to Array.Copy - Array.Copy(sortedList.values, 0, array, arrayIndex, sortedList.Count); - } - - public virtual void Insert(int index, Object value) { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - } - - public virtual Object this[int index] { - get { - return sortedList.GetByIndex(index); - } - set { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - } - } - - public virtual IEnumerator GetEnumerator() { - return new SortedListEnumerator(sortedList, 0, sortedList.Count, SortedListEnumerator.Values); - } - - public virtual int IndexOf(Object value) { - return Array.IndexOf(sortedList.values, value, 0, sortedList.Count); - } - - public virtual void Remove(Object value) { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - } - - public virtual void RemoveAt(int index) { - throw new NotSupportedException(Environment.GetResourceString(ResId.NotSupported_SortedListNestedWrite)); - } - - } - - // internal debug view class for sorted list - internal class SortedListDebugView { - private SortedList sortedList; - - public SortedListDebugView( SortedList sortedList) { - if( sortedList == null) { - throw new ArgumentNullException(nameof(sortedList)); - } - Contract.EndContractBlock(); - - this.sortedList = sortedList; - } - - [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] - public KeyValuePairs[] Items { - get { - return sortedList.ToKeyValuePairsArray(); - } - } - } - } -} diff --git a/src/mscorlib/src/System/Collections/Stack.cs b/src/mscorlib/src/System/Collections/Stack.cs deleted file mode 100644 index c3ad15abd8..0000000000 --- a/src/mscorlib/src/System/Collections/Stack.cs +++ /dev/null @@ -1,379 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================================= -** -** -** -** -** Purpose: An array implementation of a stack. -** -** -=============================================================================*/ -namespace System.Collections { - using System; - using System.Security.Permissions; - using System.Diagnostics; - using System.Diagnostics.CodeAnalysis; - using System.Diagnostics.Contracts; - - // A simple stack of objects. Internally it is implemented as an array, - // so Push can be O(n). Pop is O(1). - [DebuggerTypeProxy(typeof(System.Collections.Stack.StackDebugView))] - [DebuggerDisplay("Count = {Count}")] -[System.Runtime.InteropServices.ComVisible(true)] - [Serializable] - public class Stack : ICollection, ICloneable { - private Object[] _array; // Storage for stack elements - [ContractPublicPropertyName("Count")] - private int _size; // Number of items in the stack. - private int _version; // Used to keep enumerator in sync w/ collection. - [NonSerialized] - private Object _syncRoot; - - private const int _defaultCapacity = 10; - - public Stack() { - _array = new Object[_defaultCapacity]; - _size = 0; - _version = 0; - } - - // Create a stack with a specific initial capacity. The initial capacity - // must be a non-negative number. - public Stack(int initialCapacity) { - if (initialCapacity < 0) - throw new ArgumentOutOfRangeException(nameof(initialCapacity), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - Contract.EndContractBlock(); - if (initialCapacity < _defaultCapacity) - initialCapacity = _defaultCapacity; // Simplify doubling logic in Push. - _array = new Object[initialCapacity]; - _size = 0; - _version = 0; - } - - // Fills a Stack with the contents of a particular collection. The items are - // pushed onto the stack in the same order they are read by the enumerator. - // - public Stack(ICollection col) : this((col==null ? 32 : col.Count)) - { - if (col==null) - throw new ArgumentNullException(nameof(col)); - Contract.EndContractBlock(); - IEnumerator en = col.GetEnumerator(); - while(en.MoveNext()) - Push(en.Current); - } - - public virtual int Count { - get { - Contract.Ensures(Contract.Result<int>() >= 0); - return _size; - } - } - - public virtual bool IsSynchronized { - get { return false; } - } - - public virtual Object SyncRoot { - get { - if( _syncRoot == null) { - System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null); - } - return _syncRoot; - } - } - - // Removes all Objects from the Stack. - public virtual void Clear() { - Array.Clear(_array, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references. - _size = 0; - _version++; - } - - public virtual Object Clone() { - Contract.Ensures(Contract.Result<Object>() != null); - - Stack s = new Stack(_size); - s._size = _size; - Array.Copy(_array, 0, s._array, 0, _size); - s._version = _version; - return s; - } - - public virtual bool Contains(Object obj) { - int count = _size; - - while (count-- > 0) { - if (obj == null) { - if (_array[count] == null) - return true; - } - else if (_array[count] != null && _array[count].Equals(obj)) { - return true; - } - } - return false; - } - - // Copies the stack into an array. - public virtual void CopyTo(Array array, int index) { - if (array==null) - throw new ArgumentNullException(nameof(array)); - if (array.Rank != 1) - throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); - if (index < 0) - throw new ArgumentOutOfRangeException(nameof(index), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); - if (array.Length - index < _size) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); - Contract.EndContractBlock(); - - int i = 0; - if (array is Object[]) { - Object[] objArray = (Object[]) array; - while(i < _size) { - objArray[i+index] = _array[_size-i-1]; - i++; - } - } - else { - while(i < _size) { - array.SetValue(_array[_size-i-1], i+index); - i++; - } - } - } - - // Returns an IEnumerator for this Stack. - public virtual IEnumerator GetEnumerator() { - Contract.Ensures(Contract.Result<IEnumerator>() != null); - return new StackEnumerator(this); - } - - // Returns the top object on the stack without removing it. If the stack - // is empty, Peek throws an InvalidOperationException. - public virtual Object Peek() { - if (_size==0) - throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack")); - Contract.EndContractBlock(); - return _array[_size-1]; - } - - // Pops an item from the top of the stack. If the stack is empty, Pop - // throws an InvalidOperationException. - public virtual Object Pop() { - if (_size == 0) - throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack")); - //Contract.Ensures(Count == Contract.OldValue(Count) - 1); - Contract.EndContractBlock(); - _version++; - Object obj = _array[--_size]; - _array[_size] = null; // Free memory quicker. - return obj; - } - - // Pushes an item to the top of the stack. - // - public virtual void Push(Object obj) { - //Contract.Ensures(Count == Contract.OldValue(Count) + 1); - if (_size == _array.Length) { - Object[] newArray = new Object[2*_array.Length]; - Array.Copy(_array, 0, newArray, 0, _size); - _array = newArray; - } - _array[_size++] = obj; - _version++; - } - - // Returns a synchronized Stack. - // - public static Stack Synchronized(Stack stack) { - if (stack==null) - throw new ArgumentNullException(nameof(stack)); - Contract.Ensures(Contract.Result<Stack>() != null); - Contract.EndContractBlock(); - return new SyncStack(stack); - } - - - // Copies the Stack to an array, in the same order Pop would return the items. - public virtual Object[] ToArray() - { - Contract.Ensures(Contract.Result<Object[]>() != null); - - Object[] objArray = new Object[_size]; - int i = 0; - while(i < _size) { - objArray[i] = _array[_size-i-1]; - i++; - } - return objArray; - } - - [Serializable] - private class SyncStack : Stack - { - private Stack _s; - private Object _root; - - internal SyncStack(Stack stack) { - _s = stack; - _root = stack.SyncRoot; - } - - public override bool IsSynchronized { - get { return true; } - } - - public override Object SyncRoot { - get { - return _root; - } - } - - public override int Count { - get { - lock (_root) { - return _s.Count; - } - } - } - - public override bool Contains(Object obj) { - lock (_root) { - return _s.Contains(obj); - } - } - - public override Object Clone() - { - lock (_root) { - return new SyncStack((Stack)_s.Clone()); - } - } - - public override void Clear() { - lock (_root) { - _s.Clear(); - } - } - - public override void CopyTo(Array array, int arrayIndex) { - lock (_root) { - _s.CopyTo(array, arrayIndex); - } - } - - public override void Push(Object value) { - lock (_root) { - _s.Push(value); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Thread safety problems with precondition - can't express the precondition as of Dev10. - public override Object Pop() { - lock (_root) { - return _s.Pop(); - } - } - - public override IEnumerator GetEnumerator() { - lock (_root) { - return _s.GetEnumerator(); - } - } - - [SuppressMessage("Microsoft.Contracts", "CC1055")] // Thread safety problems with precondition - can't express the precondition as of Dev10. - public override Object Peek() { - lock (_root) { - return _s.Peek(); - } - } - - public override Object[] ToArray() { - lock (_root) { - return _s.ToArray(); - } - } - } - - - [Serializable] - private class StackEnumerator : IEnumerator, ICloneable - { - private Stack _stack; - private int _index; - private int _version; - private Object currentElement; - - internal StackEnumerator(Stack stack) { - _stack = stack; - _version = _stack._version; - _index = -2; - currentElement = null; - } - - public Object Clone() - { - return MemberwiseClone(); - } - - public virtual bool MoveNext() { - bool retval; - if (_version != _stack._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); - if (_index == -2) { // First call to enumerator. - _index = _stack._size-1; - retval = ( _index >= 0); - if (retval) - currentElement = _stack._array[_index]; - return retval; - } - if (_index == -1) { // End of enumeration. - return false; - } - - retval = (--_index >= 0); - if (retval) - currentElement = _stack._array[_index]; - else - currentElement = null; - return retval; - } - - public virtual Object Current { - get { - if (_index == -2) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted)); - if (_index == -1) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded)); - return currentElement; - } - } - - public virtual void Reset() { - if (_version != _stack._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); - _index = -2; - currentElement = null; - } - } - - internal class StackDebugView { - private Stack stack; - - public StackDebugView( Stack stack) { - if( stack == null) - throw new ArgumentNullException(nameof(stack)); - Contract.EndContractBlock(); - - this.stack = stack; - } - - [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] - public Object[] Items { - get { - return stack.ToArray(); - } - } - } - } -} |