Code:
/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / wpf / src / Shared / MS / Utility / FrugalList.cs / 1 / FrugalList.cs
//---------------------------------------------------------------------------- // // Copyright (C) Microsoft Corporation. All rights reserved. // //--------------------------------------------------------------------------- using System; using System.Diagnostics; using System.Collections; using System.Collections.Generic; using System.Windows; using System.Diagnostics.CodeAnalysis; using MS.Internal.WindowsBase; //using MS.Internal.PresentationCore; //using SR=MS.Internal.WindowsBase.SR; //using SRID=MS.Internal.WindowsBase.SRID; // These classes implement a frugal storage model for lists of type. // Performance measurements show that Avalon has many lists that contain // a limited number of entries, and frequently zero or a single entry. // Therefore these classes are structured to prefer a storage model that // starts at zero, and employs a conservative growth strategy to minimize // the steady state memory footprint. Also note that the list uses one // fewer objects than ArrayList and List and does no allocations at all // until an item is inserted into the list. // // The code is also structured to perform well from a CPU standpoint. Perf // analysis shows that the reduced number of processor cache misses makes // FrugalList faster than ArrayList or List , especially for lists of 6 // or fewer items. Timing differ with the size of . // // FrugalList is appropriate for small lists or lists that grow slowly. // Due to the slow growth, if you use it for a list with more than 6 initial // entires is best to set the capacity of the list at construction time or // soon after. If you must grow the list by a large amount, set the capacity // or use Insert() method to force list growth to the final size. Choose // your collections wisely and pay particular attention to the growth // patterns and search methods. // FrugalList has all of the methods of the Ilist interface, but implements // them as virtual methods of the class and not as Interface methods. This // is to avoid the virtual stub dispatch CPU costs associated with Interfaces. // We suppress two FxCop warnings in this module because not all usages // of FrugalList will instantiate all the storage classes and not all class instances // will use every method. // CA1811:AvoidUncalledPrivateCode // CA1812:AvoidUninstantiatedInternalClasses // namespace MS.Utility { // These classes implement a frugal storage model for lists of . // Performance measurements show that many lists contain a single item. // Therefore this list is structured to prefer a list that contains a single // item, and does conservative growth to minimize the memory footprint. // This enum controls the growth to successively more complex storage models internal enum FrugalListStoreState { Success, SingleItemList, ThreeItemList, SixItemList, Array } abstract class FrugalListBase { /// /// Number of entries in this store /// // Number of entries in this store public int Count { get { return _count; } } ////// Capacity of this store /// public abstract int Capacity { get; } // Increase size if needed, insert item into the store public abstract FrugalListStoreState Add(T value); ////// Removes all values from the store /// public abstract void Clear(); ////// Returns true if the store contains the entry. /// public abstract bool Contains(T value); ////// Returns the index into the store that contains the item. /// -1 is returned if the item is not in the store. /// public abstract int IndexOf(T value); ////// Insert item into the store at index, grows if needed /// public abstract void Insert(int index, T value); // Place item into the store at index public abstract void SetAt(int index, T value); ////// Removes the item from the store. If the item was not /// in the store false is returned. /// public abstract bool Remove(T value); ////// Removes the item from the store /// public abstract void RemoveAt(int index); ////// Return the item at index in the store /// public abstract T EntryAt(int index); ////// Promotes the values in the current store to the next larger /// and more complex storage model. /// public abstract void Promote(FrugalListBasenewList); /// /// Returns the entries as an array /// public abstract T[] ToArray(); ////// Copies the entries to the given array starting at the /// specified index /// public abstract void CopyTo(T[] array, int index); ////// Creates a shallow copy of the list /// public abstract object Clone(); // The number of items in the list. protected int _count; } ////// A simple class to handle a single item /// internal sealed class SingleItemList: FrugalListBase { // Capacity of this store public override int Capacity { get { return SIZE; } } public override FrugalListStoreState Add(T value) { // If we don't have any entries or the existing entry is being overwritten, // then we can use this store. Otherwise we have to promote. if (0 == _count) { _loneEntry = value; ++_count; return FrugalListStoreState.Success; } else { // Entry already used, move to an ThreeItemList return FrugalListStoreState.ThreeItemList; } } public override void Clear() { // Wipe out the info _loneEntry = default(T); _count = 0; } public override bool Contains(T value) { return _loneEntry.Equals(value); } public override int IndexOf(T value) { if (_loneEntry.Equals(value)) { return 0; } return -1; } public override void Insert(int index, T value) { // Should only get here if count and index are 0 if ((_count < SIZE) && (index < SIZE)) { _loneEntry = value; ++_count; return; } throw new ArgumentOutOfRangeException("index"); } public override void SetAt(int index, T value) { // Overwrite item at index _loneEntry = value; } public override bool Remove(T value) { // Wipe out the info in the only entry if it matches the item. if (_loneEntry.Equals(value)) { _loneEntry = default(T); --_count; return true; } return false; } public override void RemoveAt(int index) { // Wipe out the info at index if (0 == index) { _loneEntry = default(T); --_count; } else { throw new ArgumentOutOfRangeException("index"); } } public override T EntryAt(int index) { return _loneEntry; } public override void Promote(FrugalListBase oldList) { if (SIZE == oldList.Count) { SetCount(SIZE); SetAt(0, oldList.EntryAt(0)); } else { // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(SingleItemList oldList) { SetCount(oldList.Count); SetAt(0, oldList.EntryAt(0)); } public override T[] ToArray() { T[] array = new T[1]; array[0] = _loneEntry; return array; } public override void CopyTo(T[] array, int index) { array[index] = _loneEntry; } public override object Clone() { SingleItemList newList = new SingleItemList (); newList.Promote(this); return newList; } private void SetCount(int value) { if ((value >= 0) && (value <= SIZE)) { _count = value; } else { throw new ArgumentOutOfRangeException("Count"); } } private const int SIZE = 1; private T _loneEntry; } /// /// A simple class to handle a list with 3 items. Perf analysis showed /// that this yielded better memory locality and perf than an object and an array. /// internal sealed class ThreeItemList: FrugalListBase { // Capacity of this store public override int Capacity { get { return SIZE; } } public override FrugalListStoreState Add(T value) { switch (_count) { case 0: _entry0 = value; break; case 1: _entry1 = value; break; case 2: _entry2 = value; break; default: // We have to promote return FrugalListStoreState.SixItemList; } ++_count; return FrugalListStoreState.Success; } public override void Clear() { // Wipe out the info. _entry0 = default(T); _entry1 = default(T); _entry2 = default(T); _count = 0; } public override bool Contains(T value) { return (-1 != IndexOf(value)); } public override int IndexOf(T value) { if (_entry0.Equals(value)) { return 0; } if (_count > 1) { if (_entry1.Equals(value)) { return 1; } if ((3 == _count) && (_entry2.Equals(value))) { return 2; } } return -1; } public override void Insert(int index, T value) { // Should only get here if count < SIZE if (_count < SIZE) { switch (index) { case 0: _entry2 = _entry1; _entry1 = _entry0; _entry0 = value; break; case 1: _entry2 = _entry1; _entry1 = value; break; case 2: _entry2 = value; break; default: throw new ArgumentOutOfRangeException("index"); } ++_count; return; } throw new ArgumentOutOfRangeException("index"); } public override void SetAt(int index, T value) { // Overwrite item at index switch (index) { case 0: _entry0 = value; break; case 1: _entry1 = value; break; case 2: _entry2 = value; break; default: throw new ArgumentOutOfRangeException("index"); } } public override bool Remove(T value) { // If the item matches an existing entry, wipe out the last // entry and move all the other entries up. Because we only // have three entries we can just unravel all the cases. if (_entry0.Equals(value)) { RemoveAt(0); return true; } else if ( _count > 1) { if (_entry1.Equals(value)) { RemoveAt(1); return true; } else if ((3 == _count) && (_entry2.Equals(value))) { RemoveAt(2); return true; } } return false; } public override void RemoveAt(int index) { // Remove entry at index, wipe out the last entry and move // all the other entries up. Because we only have three // entries we can just unravel all the cases. switch (index) { case 0: _entry0 = _entry1; _entry1 = _entry2; break; case 1: _entry1 = _entry2; break; case 2: break; default: throw new ArgumentOutOfRangeException("index"); } _entry2 = default(T); --_count; } public override T EntryAt(int index) { switch (index) { case 0: return _entry0; case 1: return _entry1; case 2: return _entry2; default: throw new ArgumentOutOfRangeException("index"); } } public override void Promote(FrugalListBase oldList) { int oldCount = oldList.Count; if (SIZE >= oldCount) { SetCount(oldList.Count); switch (oldCount) { case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } else { // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(SingleItemList oldList) { SetCount(oldList.Count); SetAt(0, oldList.EntryAt(0)); } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(ThreeItemList oldList) { int oldCount = oldList.Count; SetCount(oldList.Count); switch (oldCount) { case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } public override T[] ToArray() { T[] array = new T[_count]; array[0] = _entry0; if (_count >= 2) { array[1] = _entry1; if (_count == 3) { array[2] = _entry2; } } return array; } public override void CopyTo(T[] array, int index) { array[index] = _entry0; if (_count >= 2) { array[index+1] = _entry1; if (_count == 3) { array[index+2] = _entry2; } } } public override object Clone() { ThreeItemList newList = new ThreeItemList (); newList.Promote(this); return newList; } private void SetCount(int value) { if ((value >= 0) && (value <= SIZE)) { _count = value; } else { throw new ArgumentOutOfRangeException("Count"); } } private const int SIZE = 3; private T _entry0; private T _entry1; private T _entry2; } /// /// A simple class to handle a list with 6 items. /// internal sealed class SixItemList: FrugalListBase { // Capacity of this store public override int Capacity { get { return SIZE; } } public override FrugalListStoreState Add(T value) { switch (_count) { case 0: _entry0 = value; break; case 1: _entry1 = value; break; case 2: _entry2 = value; break; case 3: _entry3 = value; break; case 4: _entry4 = value; break; case 5: _entry5 = value; break; default: // We have to promote return FrugalListStoreState.Array; } ++_count; return FrugalListStoreState.Success; } public override void Clear() { // Wipe out the info. _entry0 = default(T); _entry1 = default(T); _entry2 = default(T); _entry3 = default(T); _entry4 = default(T); _entry5 = default(T); _count = 0; } public override bool Contains(T value) { return (-1 != IndexOf(value)); } public override int IndexOf(T value) { if (_entry0.Equals(value)) { return 0; } if (_count > 1) { if (_entry1.Equals(value)) { return 1; } if (_count > 2) { if (_entry2.Equals(value)) { return 2; } if (_count > 3) { if (_entry3.Equals(value)) { return 3; } if (_count > 4) { if (_entry4.Equals(value)) { return 4; } if ((6 == _count) && (_entry5.Equals(value))) { return 5; } } } } } return -1; } public override void Insert(int index, T value) { // Should only get here if count is less than SIZE if (_count < SIZE) { switch (index) { case 0: _entry5 = _entry4; _entry4 = _entry3; _entry3 = _entry2; _entry2 = _entry1; _entry1 = _entry0; _entry0 = value; break; case 1: _entry5 = _entry4; _entry4 = _entry3; _entry3 = _entry2; _entry2 = _entry1; _entry1 = value; break; case 2: _entry5 = _entry4; _entry4 = _entry3; _entry3 = _entry2; _entry2 = value; break; case 3: _entry5 = _entry4; _entry4 = _entry3; _entry3 = value; break; case 4: _entry5 = _entry4; _entry4 = value; break; case 5: _entry5 = value; break; default: throw new ArgumentOutOfRangeException("index"); } ++_count; return; } throw new ArgumentOutOfRangeException("index"); } public override void SetAt(int index, T value) { // Overwrite item at index switch (index) { case 0: _entry0 = value; break; case 1: _entry1 = value; break; case 2: _entry2 = value; break; case 3: _entry3 = value; break; case 4: _entry4 = value; break; case 5: _entry5 = value; break; default: throw new ArgumentOutOfRangeException("index"); } } public override bool Remove(T value) { // If the item matches an existing entry, wipe out the last // entry and move all the other entries up. Because we only // have six entries we can just unravel all the cases. if (_entry0.Equals(value)) { RemoveAt(0); return true; } else if (_count > 1) { if (_entry1.Equals(value)) { RemoveAt(1); return true; } else if (_count > 2) { if (_entry2.Equals(value)) { RemoveAt(2); return true; } else if (_count > 3) { if (_entry3.Equals(value)) { RemoveAt(3); return true; } else if (_count > 4) { if (_entry4.Equals(value)) { RemoveAt(4); return true; } else if ((6 == _count) && (_entry5.Equals(value))) { RemoveAt(5); return true; } } } } } return false; } public override void RemoveAt(int index) { // Remove entry at index, wipe out the last entry and move // all the other entries up. Because we only have six // entries we can just unravel all the cases. switch (index) { case 0: _entry0 = _entry1; _entry1 = _entry2; _entry2 = _entry3; _entry3 = _entry4; _entry4 = _entry5; break; case 1: _entry1 = _entry2; _entry2 = _entry3; _entry3 = _entry4; _entry4 = _entry5; break; case 2: _entry2 = _entry3; _entry3 = _entry4; _entry4 = _entry5; break; case 3: _entry3 = _entry4; _entry4 = _entry5; break; case 4: _entry4 = _entry5; break; case 5: break; default: throw new ArgumentOutOfRangeException("index"); } _entry5 = default(T); --_count; } public override T EntryAt(int index) { switch (index) { case 0: return _entry0; case 1: return _entry1; case 2: return _entry2; case 3: return _entry3; case 4: return _entry4; case 5: return _entry5; default: throw new ArgumentOutOfRangeException("index"); } } public override void Promote(FrugalListBase oldList) { int oldCount = oldList.Count; if (SIZE >= oldCount) { SetCount(oldList.Count); switch (oldCount) { case 6: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); SetAt(5, oldList.EntryAt(5)); break; case 5: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); break; case 4: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); break; case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } else { // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(ThreeItemList oldList) { int oldCount = oldList.Count; if (SIZE <= oldCount) { SetCount(oldList.Count); switch (oldCount) { case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } else { // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(SixItemList oldList) { int oldCount = oldList.Count; SetCount(oldList.Count); switch (oldCount) { case 6: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); SetAt(5, oldList.EntryAt(5)); break; case 5: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); break; case 4: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); break; case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } public override T[] ToArray() { T[] array = new T[_count]; if (_count >= 1) { array[0] = _entry0; if (_count >= 2) { array[1] = _entry1; if (_count >= 3) { array[2] = _entry2; if (_count >= 4) { array[3] = _entry3; if (_count >= 5) { array[4] = _entry4; if (_count == 6) { array[5] = _entry5; } } } } } } return array; } public override void CopyTo(T[] array, int index) { if (_count >= 1) { array[index] = _entry0; if (_count >= 2) { array[index+1] = _entry1; if (_count >= 3) { array[index+2] = _entry2; if (_count >= 4) { array[index+3] = _entry3; if (_count >= 5) { array[index+4] = _entry4; if (_count == 6) { array[index+5] = _entry5; } } } } } } } public override object Clone() { SixItemList newList = new SixItemList (); newList.Promote(this); return newList; } private void SetCount(int value) { if ((value >= 0) && (value <= SIZE)) { _count = value; } else { throw new ArgumentOutOfRangeException("Count"); } } private const int SIZE = 6; private T _entry0; private T _entry1; private T _entry2; private T _entry3; private T _entry4; private T _entry5; } /// /// A simple class to handle an array of 7 or more items. It is unsorted and uses /// a linear search. /// internal sealed class ArrayItemList: FrugalListBase { public ArrayItemList() { } public ArrayItemList(int size) { // Make size a multiple of GROWTH size += (GROWTH - 1); size -= (size % GROWTH); _entries = new T[size]; } public ArrayItemList(ICollection collection) { if (collection != null) { _count = collection.Count; _entries = new T[_count]; collection.CopyTo(_entries, 0); } } public ArrayItemList(ICollection collection) { if (collection != null) { _count = collection.Count; _entries = new T[_count]; collection.CopyTo(_entries, 0); } } // Capacity of this store public override int Capacity { get { if (_entries != null) { return _entries.Length; } return 0; } } public override FrugalListStoreState Add(T value) { // If we don't have any entries or the existing entry is being overwritten, // then we can use this store. Otherwise we have to promote. if ((null != _entries) && (_count < _entries.Length)) { _entries[_count] = value; ++_count; } else { if (null != _entries) { int size = _entries.Length; // Grow the list slowly while it is small but // faster once it reaches the LARGEGROWTH size if (size < LARGEGROWTH) { size += GROWTH; } else { size += size >> 2; } T[] destEntries = new T[size]; // Copy old array Array.Copy(_entries, 0, destEntries, 0, _entries.Length); _entries = destEntries; } else { _entries = new T[MINSIZE]; } // Insert into new array _entries[_count] = value; ++_count; } return FrugalListStoreState.Success; } public override void Clear() { // Wipe out the info. for (int i = 0; i < _count; ++i) { _entries[i] = default(T); } _count = 0; } public override bool Contains(T value) { return (-1 != IndexOf(value)); } public override int IndexOf(T value) { for (int index = 0; index < _count; ++index) { if (_entries[index].Equals(value)) { return index; } } return -1; } public override void Insert(int index, T value) { if ((null != _entries) && (_count < _entries.Length)) { // Move down the required number of items Array.Copy(_entries, index, _entries, index + 1, _count - index); // Put in the new item at the specified index _entries[index] = value; ++_count; return; } throw new ArgumentOutOfRangeException("index"); } public override void SetAt(int index, T value) { // Overwrite item at index _entries[index] = value; } public override bool Remove(T value) { for (int index = 0; index < _count; ++index) { if (_entries[index].Equals(value)) { RemoveAt(index); return true; } } return false; } public override void RemoveAt(int index) { // Shift entries down int numToCopy = (_count - index) - 1; if (numToCopy > 0) { Array.Copy(_entries, index + 1, _entries, index, numToCopy); } // Wipe out the last entry _entries[_count - 1] = default(T); --_count; return; } public override T EntryAt(int index) { return _entries[index]; } public override void Promote(FrugalListBase oldList) { for (int index = 0; index < oldList.Count; ++index) { if (FrugalListStoreState.Success == Add(oldList.EntryAt(index))) { continue; } // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(SixItemList oldList) { int oldCount = oldList.Count; SetCount(oldList.Count); switch (oldCount) { case 6: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); SetAt(5, oldList.EntryAt(5)); break; case 5: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); break; case 4: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); break; case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(ArrayItemList oldList) { int oldCount = oldList.Count; if (_entries.Length >= oldCount) { SetCount(oldList.Count); for (int index = 0; index < oldCount; ++index) { SetAt(index, oldList.EntryAt(index)); } } else { // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } public override T[] ToArray() { T[] array = new T[_count]; for (int i = 0; i < _count; ++i) { array[i] = _entries[i]; } return array; } public override void CopyTo(T[] array, int index) { for (int i = 0; i < _count; ++i) { array[index+i] = _entries[i]; } } public override object Clone() { ArrayItemList newList = new ArrayItemList (this.Capacity); newList.Promote(this); return newList; } private void SetCount(int value) { if ((value >= 0) && (value <= _entries.Length)) { _count = value; } else { throw new ArgumentOutOfRangeException("Count"); } } // MINSIZE and GROWTH chosen to minimize memory footprint private const int MINSIZE = 9; private const int GROWTH = 3; private const int LARGEGROWTH = 18; private T[] _entries; } // Use FrugalObjectList when more than one reference to the list is needed. // The "object" in FrugalObjectLIst refers to the list itself, not what the list contains. [FriendAccessAllowed] // Built into Core, also used by Framework. internal class FrugalObjectList { public FrugalObjectList() { } public FrugalObjectList(int size) { Capacity = size; } public int Capacity { get { if (null != _listStore) { return _listStore.Capacity; } return 0; } set { int capacity = 0; if (null != _listStore) { capacity = _listStore.Capacity; } if (capacity < value) { // Need to move to a more complex storage FrugalListBase newStore; if (value == 1) { newStore = new SingleItemList (); } else if (value <= 3) { newStore = new ThreeItemList (); } else if (value <= 6) { newStore = new SixItemList (); } else { newStore = new ArrayItemList (value); } if (null != _listStore) { // Move entries in the old store to the new one newStore.Promote(_listStore); } _listStore = newStore; } } } public int Count { get { if (null != _listStore) { return _listStore.Count; } return 0; } } public T this[int index] { get { // If no entry, default(T) is returned if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { return _listStore.EntryAt(index); } throw new ArgumentOutOfRangeException("index"); } set { // Ensure write success if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { _listStore.SetAt(index, value); return; } throw new ArgumentOutOfRangeException("index"); } } public int Add(T value) { if (null != _listStore) { // This is done because forward branches // default prediction is not to be taken // making this a CPU win because Add is // a common operation. } else { _listStore = new SingleItemList (); } FrugalListStoreState myState = _listStore.Add(value); if (FrugalListStoreState.Success == myState) { } else { // Need to move to a more complex storage // Allocate the store, promote, and add using the derived classes // to avoid virtual method calls if (FrugalListStoreState.ThreeItemList == myState) { ThreeItemList newStore = new ThreeItemList (); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); // Insert the new item newStore.Add(value); _listStore = newStore; } else if (FrugalListStoreState.SixItemList == myState) { SixItemList newStore = new SixItemList (); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); _listStore = newStore; // Insert the new item newStore.Add(value); _listStore = newStore; } else if (FrugalListStoreState.Array == myState) { ArrayItemList newStore = new ArrayItemList (_listStore.Count + 1); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); _listStore = newStore; // Insert the new item newStore.Add(value); _listStore = newStore; } else { throw new InvalidOperationException(SR.Get(SRID.FrugalList_CannotPromoteBeyondArray)); } } return _listStore.Count - 1; } public void Clear() { if (null != _listStore) { _listStore.Clear(); } } public bool Contains(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.Contains(value); } return false; } public int IndexOf(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.IndexOf(value); } return -1; } public void Insert(int index, T value) { if ((index == 0) || ((null != _listStore) && ((index <= _listStore.Count) && (index >= 0)))) { // Make sure we have a place to put the item int minCapacity = 1; if ((null != _listStore) && (_listStore.Count == _listStore.Capacity)) { // Store is full minCapacity = Capacity + 1; } // Make the Capacity at *least* this big Capacity = minCapacity; _listStore.Insert(index, value); return; } throw new ArgumentOutOfRangeException("index"); } public bool Remove(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.Remove(value); } return false; } public void RemoveAt(int index) { if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { _listStore.RemoveAt(index); return; } throw new ArgumentOutOfRangeException("index"); } public void EnsureIndex(int index) { if (index >= 0) { int delta = (index + 1) - Count; if (delta > 0) { // Grow the store Capacity = index + 1; T filler = default(T); // Insert filler structs or objects for (int i = 0; i < delta; ++i) { _listStore.Add(filler); } } return; } throw new ArgumentOutOfRangeException("index"); } public T[] ToArray() { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.ToArray(); } return null; } public void CopyTo(T[] array, int index) { if ((null != _listStore) && (_listStore.Count > 0)) { _listStore.CopyTo(array, index); } } public FrugalObjectList Clone() { FrugalObjectList myClone = new FrugalObjectList (); if (null != _listStore) { myClone._listStore = (FrugalListBase )_listStore.Clone(); } return myClone; } internal FrugalListBase _listStore; } // Use FrugalStructList when only one reference to the list is needed. // The "struct" in FrugalStructList refers to the list itself, not what the list contains. [FriendAccessAllowed] // Built into Core, also used by Framework. internal struct FrugalStructList { public FrugalStructList(int size) { _listStore = null; Capacity = size; } public FrugalStructList(ICollection collection) { if (collection.Count > 6) { _listStore = new ArrayItemList (collection); } else { _listStore = null; Capacity = collection.Count; foreach (T item in collection) { Add(item); } } } public FrugalStructList(ICollection collection) { if (collection.Count > 6) { _listStore = new ArrayItemList (collection); } else { _listStore = null; Capacity = collection.Count; foreach (T item in collection) { Add(item); } } } public int Capacity { get { if (null != _listStore) { return _listStore.Capacity; } return 0; } set { int capacity = 0; if (null != _listStore) { capacity = _listStore.Capacity; } if (capacity < value) { // Need to move to a more complex storage FrugalListBase newStore; if (value == 1) { newStore = new SingleItemList (); } else if (value <= 3) { newStore = new ThreeItemList (); } else if (value <= 6) { newStore = new SixItemList (); } else { newStore = new ArrayItemList (value); } if (null != _listStore) { // Move entries in the old store to the new one newStore.Promote(_listStore); } _listStore = newStore; } } } public int Count { get { if (null != _listStore) { return _listStore.Count; } return 0; } } public T this[int index] { get { // If no entry, default(T) is returned if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { return _listStore.EntryAt(index); } throw new ArgumentOutOfRangeException("index"); } set { // Ensure write success if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { _listStore.SetAt(index, value); return; } throw new ArgumentOutOfRangeException("index"); } } public int Add(T value) { if (null != _listStore) { // This is done because forward branches // default prediction is not to be taken // making this a CPU win because Add is // a common operation. } else { _listStore = new SingleItemList (); } FrugalListStoreState myState = _listStore.Add(value); if (FrugalListStoreState.Success == myState) { } else { // Need to move to a more complex storage // Allocate the store, promote, and add using the derived classes // to avoid virtual method calls if (FrugalListStoreState.ThreeItemList == myState) { ThreeItemList newStore = new ThreeItemList (); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); // Insert the new item newStore.Add(value); _listStore = newStore; } else if (FrugalListStoreState.SixItemList == myState) { SixItemList newStore = new SixItemList (); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); _listStore = newStore; // Insert the new item newStore.Add(value); _listStore = newStore; } else if (FrugalListStoreState.Array == myState) { ArrayItemList newStore = new ArrayItemList (_listStore.Count + 1); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); _listStore = newStore; // Insert the new item newStore.Add(value); _listStore = newStore; } else { throw new InvalidOperationException(SR.Get(SRID.FrugalList_CannotPromoteBeyondArray)); } } return _listStore.Count - 1; } public void Clear() { if (null != _listStore) { _listStore.Clear(); } } public bool Contains(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.Contains(value); } return false; } public int IndexOf(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.IndexOf(value); } return -1; } public void Insert(int index, T value) { if ((index == 0) || ((null != _listStore) && ((index <= _listStore.Count) && (index >= 0)))) { // Make sure we have a place to put the item int minCapacity = 1; if ((null != _listStore) && (_listStore.Count == _listStore.Capacity)) { // Store is full minCapacity = Capacity + 1; } // Make the Capacity at *least* this big Capacity = minCapacity; _listStore.Insert(index, value); return; } throw new ArgumentOutOfRangeException("index"); } public bool Remove(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.Remove(value); } return false; } public void RemoveAt(int index) { if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { _listStore.RemoveAt(index); return; } throw new ArgumentOutOfRangeException("index"); } public void EnsureIndex(int index) { if (index >= 0) { int delta = (index + 1) - Count; if (delta > 0) { // Grow the store Capacity = index + 1; T filler = default(T); // Insert filler structs or objects for (int i = 0; i < delta; ++i) { _listStore.Add(filler); } } return; } throw new ArgumentOutOfRangeException("index"); } public T[] ToArray() { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.ToArray(); } return null; } public void CopyTo(T[] array, int index) { if ((null != _listStore) && (_listStore.Count > 0)) { _listStore.CopyTo(array, index); } } public FrugalStructList Clone() { FrugalStructList myClone = new FrugalStructList (); if (null != _listStore) { myClone._listStore = (FrugalListBase )_listStore.Clone(); } return myClone; } internal FrugalListBase _listStore; } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // Copyright (c) Microsoft Corporation. All rights reserved. //---------------------------------------------------------------------------- // // Copyright (C) Microsoft Corporation. All rights reserved. // //--------------------------------------------------------------------------- using System; using System.Diagnostics; using System.Collections; using System.Collections.Generic; using System.Windows; using System.Diagnostics.CodeAnalysis; using MS.Internal.WindowsBase; //using MS.Internal.PresentationCore; //using SR=MS.Internal.WindowsBase.SR; //using SRID=MS.Internal.WindowsBase.SRID; // These classes implement a frugal storage model for lists of type . // Performance measurements show that Avalon has many lists that contain // a limited number of entries, and frequently zero or a single entry. // Therefore these classes are structured to prefer a storage model that // starts at zero, and employs a conservative growth strategy to minimize // the steady state memory footprint. Also note that the list uses one // fewer objects than ArrayList and List and does no allocations at all // until an item is inserted into the list. // // The code is also structured to perform well from a CPU standpoint. Perf // analysis shows that the reduced number of processor cache misses makes // FrugalList faster than ArrayList or List , especially for lists of 6 // or fewer items. Timing differ with the size of . // // FrugalList is appropriate for small lists or lists that grow slowly. // Due to the slow growth, if you use it for a list with more than 6 initial // entires is best to set the capacity of the list at construction time or // soon after. If you must grow the list by a large amount, set the capacity // or use Insert() method to force list growth to the final size. Choose // your collections wisely and pay particular attention to the growth // patterns and search methods. // FrugalList has all of the methods of the Ilist interface, but implements // them as virtual methods of the class and not as Interface methods. This // is to avoid the virtual stub dispatch CPU costs associated with Interfaces. // We suppress two FxCop warnings in this module because not all usages // of FrugalList will instantiate all the storage classes and not all class instances // will use every method. // CA1811:AvoidUncalledPrivateCode // CA1812:AvoidUninstantiatedInternalClasses // namespace MS.Utility { // These classes implement a frugal storage model for lists of . // Performance measurements show that many lists contain a single item. // Therefore this list is structured to prefer a list that contains a single // item, and does conservative growth to minimize the memory footprint. // This enum controls the growth to successively more complex storage models internal enum FrugalListStoreState { Success, SingleItemList, ThreeItemList, SixItemList, Array } abstract class FrugalListBase { /// /// Number of entries in this store /// // Number of entries in this store public int Count { get { return _count; } } ////// Capacity of this store /// public abstract int Capacity { get; } // Increase size if needed, insert item into the store public abstract FrugalListStoreState Add(T value); ////// Removes all values from the store /// public abstract void Clear(); ////// Returns true if the store contains the entry. /// public abstract bool Contains(T value); ////// Returns the index into the store that contains the item. /// -1 is returned if the item is not in the store. /// public abstract int IndexOf(T value); ////// Insert item into the store at index, grows if needed /// public abstract void Insert(int index, T value); // Place item into the store at index public abstract void SetAt(int index, T value); ////// Removes the item from the store. If the item was not /// in the store false is returned. /// public abstract bool Remove(T value); ////// Removes the item from the store /// public abstract void RemoveAt(int index); ////// Return the item at index in the store /// public abstract T EntryAt(int index); ////// Promotes the values in the current store to the next larger /// and more complex storage model. /// public abstract void Promote(FrugalListBasenewList); /// /// Returns the entries as an array /// public abstract T[] ToArray(); ////// Copies the entries to the given array starting at the /// specified index /// public abstract void CopyTo(T[] array, int index); ////// Creates a shallow copy of the list /// public abstract object Clone(); // The number of items in the list. protected int _count; } ////// A simple class to handle a single item /// internal sealed class SingleItemList: FrugalListBase { // Capacity of this store public override int Capacity { get { return SIZE; } } public override FrugalListStoreState Add(T value) { // If we don't have any entries or the existing entry is being overwritten, // then we can use this store. Otherwise we have to promote. if (0 == _count) { _loneEntry = value; ++_count; return FrugalListStoreState.Success; } else { // Entry already used, move to an ThreeItemList return FrugalListStoreState.ThreeItemList; } } public override void Clear() { // Wipe out the info _loneEntry = default(T); _count = 0; } public override bool Contains(T value) { return _loneEntry.Equals(value); } public override int IndexOf(T value) { if (_loneEntry.Equals(value)) { return 0; } return -1; } public override void Insert(int index, T value) { // Should only get here if count and index are 0 if ((_count < SIZE) && (index < SIZE)) { _loneEntry = value; ++_count; return; } throw new ArgumentOutOfRangeException("index"); } public override void SetAt(int index, T value) { // Overwrite item at index _loneEntry = value; } public override bool Remove(T value) { // Wipe out the info in the only entry if it matches the item. if (_loneEntry.Equals(value)) { _loneEntry = default(T); --_count; return true; } return false; } public override void RemoveAt(int index) { // Wipe out the info at index if (0 == index) { _loneEntry = default(T); --_count; } else { throw new ArgumentOutOfRangeException("index"); } } public override T EntryAt(int index) { return _loneEntry; } public override void Promote(FrugalListBase oldList) { if (SIZE == oldList.Count) { SetCount(SIZE); SetAt(0, oldList.EntryAt(0)); } else { // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(SingleItemList oldList) { SetCount(oldList.Count); SetAt(0, oldList.EntryAt(0)); } public override T[] ToArray() { T[] array = new T[1]; array[0] = _loneEntry; return array; } public override void CopyTo(T[] array, int index) { array[index] = _loneEntry; } public override object Clone() { SingleItemList newList = new SingleItemList (); newList.Promote(this); return newList; } private void SetCount(int value) { if ((value >= 0) && (value <= SIZE)) { _count = value; } else { throw new ArgumentOutOfRangeException("Count"); } } private const int SIZE = 1; private T _loneEntry; } /// /// A simple class to handle a list with 3 items. Perf analysis showed /// that this yielded better memory locality and perf than an object and an array. /// internal sealed class ThreeItemList: FrugalListBase { // Capacity of this store public override int Capacity { get { return SIZE; } } public override FrugalListStoreState Add(T value) { switch (_count) { case 0: _entry0 = value; break; case 1: _entry1 = value; break; case 2: _entry2 = value; break; default: // We have to promote return FrugalListStoreState.SixItemList; } ++_count; return FrugalListStoreState.Success; } public override void Clear() { // Wipe out the info. _entry0 = default(T); _entry1 = default(T); _entry2 = default(T); _count = 0; } public override bool Contains(T value) { return (-1 != IndexOf(value)); } public override int IndexOf(T value) { if (_entry0.Equals(value)) { return 0; } if (_count > 1) { if (_entry1.Equals(value)) { return 1; } if ((3 == _count) && (_entry2.Equals(value))) { return 2; } } return -1; } public override void Insert(int index, T value) { // Should only get here if count < SIZE if (_count < SIZE) { switch (index) { case 0: _entry2 = _entry1; _entry1 = _entry0; _entry0 = value; break; case 1: _entry2 = _entry1; _entry1 = value; break; case 2: _entry2 = value; break; default: throw new ArgumentOutOfRangeException("index"); } ++_count; return; } throw new ArgumentOutOfRangeException("index"); } public override void SetAt(int index, T value) { // Overwrite item at index switch (index) { case 0: _entry0 = value; break; case 1: _entry1 = value; break; case 2: _entry2 = value; break; default: throw new ArgumentOutOfRangeException("index"); } } public override bool Remove(T value) { // If the item matches an existing entry, wipe out the last // entry and move all the other entries up. Because we only // have three entries we can just unravel all the cases. if (_entry0.Equals(value)) { RemoveAt(0); return true; } else if ( _count > 1) { if (_entry1.Equals(value)) { RemoveAt(1); return true; } else if ((3 == _count) && (_entry2.Equals(value))) { RemoveAt(2); return true; } } return false; } public override void RemoveAt(int index) { // Remove entry at index, wipe out the last entry and move // all the other entries up. Because we only have three // entries we can just unravel all the cases. switch (index) { case 0: _entry0 = _entry1; _entry1 = _entry2; break; case 1: _entry1 = _entry2; break; case 2: break; default: throw new ArgumentOutOfRangeException("index"); } _entry2 = default(T); --_count; } public override T EntryAt(int index) { switch (index) { case 0: return _entry0; case 1: return _entry1; case 2: return _entry2; default: throw new ArgumentOutOfRangeException("index"); } } public override void Promote(FrugalListBase oldList) { int oldCount = oldList.Count; if (SIZE >= oldCount) { SetCount(oldList.Count); switch (oldCount) { case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } else { // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(SingleItemList oldList) { SetCount(oldList.Count); SetAt(0, oldList.EntryAt(0)); } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(ThreeItemList oldList) { int oldCount = oldList.Count; SetCount(oldList.Count); switch (oldCount) { case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } public override T[] ToArray() { T[] array = new T[_count]; array[0] = _entry0; if (_count >= 2) { array[1] = _entry1; if (_count == 3) { array[2] = _entry2; } } return array; } public override void CopyTo(T[] array, int index) { array[index] = _entry0; if (_count >= 2) { array[index+1] = _entry1; if (_count == 3) { array[index+2] = _entry2; } } } public override object Clone() { ThreeItemList newList = new ThreeItemList (); newList.Promote(this); return newList; } private void SetCount(int value) { if ((value >= 0) && (value <= SIZE)) { _count = value; } else { throw new ArgumentOutOfRangeException("Count"); } } private const int SIZE = 3; private T _entry0; private T _entry1; private T _entry2; } /// /// A simple class to handle a list with 6 items. /// internal sealed class SixItemList: FrugalListBase { // Capacity of this store public override int Capacity { get { return SIZE; } } public override FrugalListStoreState Add(T value) { switch (_count) { case 0: _entry0 = value; break; case 1: _entry1 = value; break; case 2: _entry2 = value; break; case 3: _entry3 = value; break; case 4: _entry4 = value; break; case 5: _entry5 = value; break; default: // We have to promote return FrugalListStoreState.Array; } ++_count; return FrugalListStoreState.Success; } public override void Clear() { // Wipe out the info. _entry0 = default(T); _entry1 = default(T); _entry2 = default(T); _entry3 = default(T); _entry4 = default(T); _entry5 = default(T); _count = 0; } public override bool Contains(T value) { return (-1 != IndexOf(value)); } public override int IndexOf(T value) { if (_entry0.Equals(value)) { return 0; } if (_count > 1) { if (_entry1.Equals(value)) { return 1; } if (_count > 2) { if (_entry2.Equals(value)) { return 2; } if (_count > 3) { if (_entry3.Equals(value)) { return 3; } if (_count > 4) { if (_entry4.Equals(value)) { return 4; } if ((6 == _count) && (_entry5.Equals(value))) { return 5; } } } } } return -1; } public override void Insert(int index, T value) { // Should only get here if count is less than SIZE if (_count < SIZE) { switch (index) { case 0: _entry5 = _entry4; _entry4 = _entry3; _entry3 = _entry2; _entry2 = _entry1; _entry1 = _entry0; _entry0 = value; break; case 1: _entry5 = _entry4; _entry4 = _entry3; _entry3 = _entry2; _entry2 = _entry1; _entry1 = value; break; case 2: _entry5 = _entry4; _entry4 = _entry3; _entry3 = _entry2; _entry2 = value; break; case 3: _entry5 = _entry4; _entry4 = _entry3; _entry3 = value; break; case 4: _entry5 = _entry4; _entry4 = value; break; case 5: _entry5 = value; break; default: throw new ArgumentOutOfRangeException("index"); } ++_count; return; } throw new ArgumentOutOfRangeException("index"); } public override void SetAt(int index, T value) { // Overwrite item at index switch (index) { case 0: _entry0 = value; break; case 1: _entry1 = value; break; case 2: _entry2 = value; break; case 3: _entry3 = value; break; case 4: _entry4 = value; break; case 5: _entry5 = value; break; default: throw new ArgumentOutOfRangeException("index"); } } public override bool Remove(T value) { // If the item matches an existing entry, wipe out the last // entry and move all the other entries up. Because we only // have six entries we can just unravel all the cases. if (_entry0.Equals(value)) { RemoveAt(0); return true; } else if (_count > 1) { if (_entry1.Equals(value)) { RemoveAt(1); return true; } else if (_count > 2) { if (_entry2.Equals(value)) { RemoveAt(2); return true; } else if (_count > 3) { if (_entry3.Equals(value)) { RemoveAt(3); return true; } else if (_count > 4) { if (_entry4.Equals(value)) { RemoveAt(4); return true; } else if ((6 == _count) && (_entry5.Equals(value))) { RemoveAt(5); return true; } } } } } return false; } public override void RemoveAt(int index) { // Remove entry at index, wipe out the last entry and move // all the other entries up. Because we only have six // entries we can just unravel all the cases. switch (index) { case 0: _entry0 = _entry1; _entry1 = _entry2; _entry2 = _entry3; _entry3 = _entry4; _entry4 = _entry5; break; case 1: _entry1 = _entry2; _entry2 = _entry3; _entry3 = _entry4; _entry4 = _entry5; break; case 2: _entry2 = _entry3; _entry3 = _entry4; _entry4 = _entry5; break; case 3: _entry3 = _entry4; _entry4 = _entry5; break; case 4: _entry4 = _entry5; break; case 5: break; default: throw new ArgumentOutOfRangeException("index"); } _entry5 = default(T); --_count; } public override T EntryAt(int index) { switch (index) { case 0: return _entry0; case 1: return _entry1; case 2: return _entry2; case 3: return _entry3; case 4: return _entry4; case 5: return _entry5; default: throw new ArgumentOutOfRangeException("index"); } } public override void Promote(FrugalListBase oldList) { int oldCount = oldList.Count; if (SIZE >= oldCount) { SetCount(oldList.Count); switch (oldCount) { case 6: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); SetAt(5, oldList.EntryAt(5)); break; case 5: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); break; case 4: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); break; case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } else { // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(ThreeItemList oldList) { int oldCount = oldList.Count; if (SIZE <= oldCount) { SetCount(oldList.Count); switch (oldCount) { case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } else { // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(SixItemList oldList) { int oldCount = oldList.Count; SetCount(oldList.Count); switch (oldCount) { case 6: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); SetAt(5, oldList.EntryAt(5)); break; case 5: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); break; case 4: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); break; case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } public override T[] ToArray() { T[] array = new T[_count]; if (_count >= 1) { array[0] = _entry0; if (_count >= 2) { array[1] = _entry1; if (_count >= 3) { array[2] = _entry2; if (_count >= 4) { array[3] = _entry3; if (_count >= 5) { array[4] = _entry4; if (_count == 6) { array[5] = _entry5; } } } } } } return array; } public override void CopyTo(T[] array, int index) { if (_count >= 1) { array[index] = _entry0; if (_count >= 2) { array[index+1] = _entry1; if (_count >= 3) { array[index+2] = _entry2; if (_count >= 4) { array[index+3] = _entry3; if (_count >= 5) { array[index+4] = _entry4; if (_count == 6) { array[index+5] = _entry5; } } } } } } } public override object Clone() { SixItemList newList = new SixItemList (); newList.Promote(this); return newList; } private void SetCount(int value) { if ((value >= 0) && (value <= SIZE)) { _count = value; } else { throw new ArgumentOutOfRangeException("Count"); } } private const int SIZE = 6; private T _entry0; private T _entry1; private T _entry2; private T _entry3; private T _entry4; private T _entry5; } /// /// A simple class to handle an array of 7 or more items. It is unsorted and uses /// a linear search. /// internal sealed class ArrayItemList: FrugalListBase { public ArrayItemList() { } public ArrayItemList(int size) { // Make size a multiple of GROWTH size += (GROWTH - 1); size -= (size % GROWTH); _entries = new T[size]; } public ArrayItemList(ICollection collection) { if (collection != null) { _count = collection.Count; _entries = new T[_count]; collection.CopyTo(_entries, 0); } } public ArrayItemList(ICollection collection) { if (collection != null) { _count = collection.Count; _entries = new T[_count]; collection.CopyTo(_entries, 0); } } // Capacity of this store public override int Capacity { get { if (_entries != null) { return _entries.Length; } return 0; } } public override FrugalListStoreState Add(T value) { // If we don't have any entries or the existing entry is being overwritten, // then we can use this store. Otherwise we have to promote. if ((null != _entries) && (_count < _entries.Length)) { _entries[_count] = value; ++_count; } else { if (null != _entries) { int size = _entries.Length; // Grow the list slowly while it is small but // faster once it reaches the LARGEGROWTH size if (size < LARGEGROWTH) { size += GROWTH; } else { size += size >> 2; } T[] destEntries = new T[size]; // Copy old array Array.Copy(_entries, 0, destEntries, 0, _entries.Length); _entries = destEntries; } else { _entries = new T[MINSIZE]; } // Insert into new array _entries[_count] = value; ++_count; } return FrugalListStoreState.Success; } public override void Clear() { // Wipe out the info. for (int i = 0; i < _count; ++i) { _entries[i] = default(T); } _count = 0; } public override bool Contains(T value) { return (-1 != IndexOf(value)); } public override int IndexOf(T value) { for (int index = 0; index < _count; ++index) { if (_entries[index].Equals(value)) { return index; } } return -1; } public override void Insert(int index, T value) { if ((null != _entries) && (_count < _entries.Length)) { // Move down the required number of items Array.Copy(_entries, index, _entries, index + 1, _count - index); // Put in the new item at the specified index _entries[index] = value; ++_count; return; } throw new ArgumentOutOfRangeException("index"); } public override void SetAt(int index, T value) { // Overwrite item at index _entries[index] = value; } public override bool Remove(T value) { for (int index = 0; index < _count; ++index) { if (_entries[index].Equals(value)) { RemoveAt(index); return true; } } return false; } public override void RemoveAt(int index) { // Shift entries down int numToCopy = (_count - index) - 1; if (numToCopy > 0) { Array.Copy(_entries, index + 1, _entries, index, numToCopy); } // Wipe out the last entry _entries[_count - 1] = default(T); --_count; return; } public override T EntryAt(int index) { return _entries[index]; } public override void Promote(FrugalListBase oldList) { for (int index = 0; index < oldList.Count; ++index) { if (FrugalListStoreState.Success == Add(oldList.EntryAt(index))) { continue; } // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(SixItemList oldList) { int oldCount = oldList.Count; SetCount(oldList.Count); switch (oldCount) { case 6: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); SetAt(5, oldList.EntryAt(5)); break; case 5: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); SetAt(4, oldList.EntryAt(4)); break; case 4: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); SetAt(3, oldList.EntryAt(3)); break; case 3: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); SetAt(2, oldList.EntryAt(2)); break; case 2: SetAt(0, oldList.EntryAt(0)); SetAt(1, oldList.EntryAt(1)); break; case 1: SetAt(0, oldList.EntryAt(0)); break; case 0: break; default: throw new ArgumentOutOfRangeException("index"); } } // Class specific implementation to avoid virtual method calls and additional logic public void Promote(ArrayItemList oldList) { int oldCount = oldList.Count; if (_entries.Length >= oldCount) { SetCount(oldList.Count); for (int index = 0; index < oldCount; ++index) { SetAt(index, oldList.EntryAt(index)); } } else { // this list is smaller than oldList throw new ArgumentException(SR.Get(SRID.FrugalList_TargetMapCannotHoldAllData, oldList.ToString(), this.ToString()), "oldList"); } } public override T[] ToArray() { T[] array = new T[_count]; for (int i = 0; i < _count; ++i) { array[i] = _entries[i]; } return array; } public override void CopyTo(T[] array, int index) { for (int i = 0; i < _count; ++i) { array[index+i] = _entries[i]; } } public override object Clone() { ArrayItemList newList = new ArrayItemList (this.Capacity); newList.Promote(this); return newList; } private void SetCount(int value) { if ((value >= 0) && (value <= _entries.Length)) { _count = value; } else { throw new ArgumentOutOfRangeException("Count"); } } // MINSIZE and GROWTH chosen to minimize memory footprint private const int MINSIZE = 9; private const int GROWTH = 3; private const int LARGEGROWTH = 18; private T[] _entries; } // Use FrugalObjectList when more than one reference to the list is needed. // The "object" in FrugalObjectLIst refers to the list itself, not what the list contains. [FriendAccessAllowed] // Built into Core, also used by Framework. internal class FrugalObjectList { public FrugalObjectList() { } public FrugalObjectList(int size) { Capacity = size; } public int Capacity { get { if (null != _listStore) { return _listStore.Capacity; } return 0; } set { int capacity = 0; if (null != _listStore) { capacity = _listStore.Capacity; } if (capacity < value) { // Need to move to a more complex storage FrugalListBase newStore; if (value == 1) { newStore = new SingleItemList (); } else if (value <= 3) { newStore = new ThreeItemList (); } else if (value <= 6) { newStore = new SixItemList (); } else { newStore = new ArrayItemList (value); } if (null != _listStore) { // Move entries in the old store to the new one newStore.Promote(_listStore); } _listStore = newStore; } } } public int Count { get { if (null != _listStore) { return _listStore.Count; } return 0; } } public T this[int index] { get { // If no entry, default(T) is returned if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { return _listStore.EntryAt(index); } throw new ArgumentOutOfRangeException("index"); } set { // Ensure write success if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { _listStore.SetAt(index, value); return; } throw new ArgumentOutOfRangeException("index"); } } public int Add(T value) { if (null != _listStore) { // This is done because forward branches // default prediction is not to be taken // making this a CPU win because Add is // a common operation. } else { _listStore = new SingleItemList (); } FrugalListStoreState myState = _listStore.Add(value); if (FrugalListStoreState.Success == myState) { } else { // Need to move to a more complex storage // Allocate the store, promote, and add using the derived classes // to avoid virtual method calls if (FrugalListStoreState.ThreeItemList == myState) { ThreeItemList newStore = new ThreeItemList (); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); // Insert the new item newStore.Add(value); _listStore = newStore; } else if (FrugalListStoreState.SixItemList == myState) { SixItemList newStore = new SixItemList (); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); _listStore = newStore; // Insert the new item newStore.Add(value); _listStore = newStore; } else if (FrugalListStoreState.Array == myState) { ArrayItemList newStore = new ArrayItemList (_listStore.Count + 1); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); _listStore = newStore; // Insert the new item newStore.Add(value); _listStore = newStore; } else { throw new InvalidOperationException(SR.Get(SRID.FrugalList_CannotPromoteBeyondArray)); } } return _listStore.Count - 1; } public void Clear() { if (null != _listStore) { _listStore.Clear(); } } public bool Contains(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.Contains(value); } return false; } public int IndexOf(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.IndexOf(value); } return -1; } public void Insert(int index, T value) { if ((index == 0) || ((null != _listStore) && ((index <= _listStore.Count) && (index >= 0)))) { // Make sure we have a place to put the item int minCapacity = 1; if ((null != _listStore) && (_listStore.Count == _listStore.Capacity)) { // Store is full minCapacity = Capacity + 1; } // Make the Capacity at *least* this big Capacity = minCapacity; _listStore.Insert(index, value); return; } throw new ArgumentOutOfRangeException("index"); } public bool Remove(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.Remove(value); } return false; } public void RemoveAt(int index) { if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { _listStore.RemoveAt(index); return; } throw new ArgumentOutOfRangeException("index"); } public void EnsureIndex(int index) { if (index >= 0) { int delta = (index + 1) - Count; if (delta > 0) { // Grow the store Capacity = index + 1; T filler = default(T); // Insert filler structs or objects for (int i = 0; i < delta; ++i) { _listStore.Add(filler); } } return; } throw new ArgumentOutOfRangeException("index"); } public T[] ToArray() { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.ToArray(); } return null; } public void CopyTo(T[] array, int index) { if ((null != _listStore) && (_listStore.Count > 0)) { _listStore.CopyTo(array, index); } } public FrugalObjectList Clone() { FrugalObjectList myClone = new FrugalObjectList (); if (null != _listStore) { myClone._listStore = (FrugalListBase )_listStore.Clone(); } return myClone; } internal FrugalListBase _listStore; } // Use FrugalStructList when only one reference to the list is needed. // The "struct" in FrugalStructList refers to the list itself, not what the list contains. [FriendAccessAllowed] // Built into Core, also used by Framework. internal struct FrugalStructList { public FrugalStructList(int size) { _listStore = null; Capacity = size; } public FrugalStructList(ICollection collection) { if (collection.Count > 6) { _listStore = new ArrayItemList (collection); } else { _listStore = null; Capacity = collection.Count; foreach (T item in collection) { Add(item); } } } public FrugalStructList(ICollection collection) { if (collection.Count > 6) { _listStore = new ArrayItemList (collection); } else { _listStore = null; Capacity = collection.Count; foreach (T item in collection) { Add(item); } } } public int Capacity { get { if (null != _listStore) { return _listStore.Capacity; } return 0; } set { int capacity = 0; if (null != _listStore) { capacity = _listStore.Capacity; } if (capacity < value) { // Need to move to a more complex storage FrugalListBase newStore; if (value == 1) { newStore = new SingleItemList (); } else if (value <= 3) { newStore = new ThreeItemList (); } else if (value <= 6) { newStore = new SixItemList (); } else { newStore = new ArrayItemList (value); } if (null != _listStore) { // Move entries in the old store to the new one newStore.Promote(_listStore); } _listStore = newStore; } } } public int Count { get { if (null != _listStore) { return _listStore.Count; } return 0; } } public T this[int index] { get { // If no entry, default(T) is returned if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { return _listStore.EntryAt(index); } throw new ArgumentOutOfRangeException("index"); } set { // Ensure write success if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { _listStore.SetAt(index, value); return; } throw new ArgumentOutOfRangeException("index"); } } public int Add(T value) { if (null != _listStore) { // This is done because forward branches // default prediction is not to be taken // making this a CPU win because Add is // a common operation. } else { _listStore = new SingleItemList (); } FrugalListStoreState myState = _listStore.Add(value); if (FrugalListStoreState.Success == myState) { } else { // Need to move to a more complex storage // Allocate the store, promote, and add using the derived classes // to avoid virtual method calls if (FrugalListStoreState.ThreeItemList == myState) { ThreeItemList newStore = new ThreeItemList (); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); // Insert the new item newStore.Add(value); _listStore = newStore; } else if (FrugalListStoreState.SixItemList == myState) { SixItemList newStore = new SixItemList (); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); _listStore = newStore; // Insert the new item newStore.Add(value); _listStore = newStore; } else if (FrugalListStoreState.Array == myState) { ArrayItemList newStore = new ArrayItemList (_listStore.Count + 1); // Extract the values from the old store and insert them into the new store newStore.Promote(_listStore); _listStore = newStore; // Insert the new item newStore.Add(value); _listStore = newStore; } else { throw new InvalidOperationException(SR.Get(SRID.FrugalList_CannotPromoteBeyondArray)); } } return _listStore.Count - 1; } public void Clear() { if (null != _listStore) { _listStore.Clear(); } } public bool Contains(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.Contains(value); } return false; } public int IndexOf(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.IndexOf(value); } return -1; } public void Insert(int index, T value) { if ((index == 0) || ((null != _listStore) && ((index <= _listStore.Count) && (index >= 0)))) { // Make sure we have a place to put the item int minCapacity = 1; if ((null != _listStore) && (_listStore.Count == _listStore.Capacity)) { // Store is full minCapacity = Capacity + 1; } // Make the Capacity at *least* this big Capacity = minCapacity; _listStore.Insert(index, value); return; } throw new ArgumentOutOfRangeException("index"); } public bool Remove(T value) { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.Remove(value); } return false; } public void RemoveAt(int index) { if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0))) { _listStore.RemoveAt(index); return; } throw new ArgumentOutOfRangeException("index"); } public void EnsureIndex(int index) { if (index >= 0) { int delta = (index + 1) - Count; if (delta > 0) { // Grow the store Capacity = index + 1; T filler = default(T); // Insert filler structs or objects for (int i = 0; i < delta; ++i) { _listStore.Add(filler); } } return; } throw new ArgumentOutOfRangeException("index"); } public T[] ToArray() { if ((null != _listStore) && (_listStore.Count > 0)) { return _listStore.ToArray(); } return null; } public void CopyTo(T[] array, int index) { if ((null != _listStore) && (_listStore.Count > 0)) { _listStore.CopyTo(array, index); } } public FrugalStructList Clone() { FrugalStructList myClone = new FrugalStructList (); if (null != _listStore) { myClone._listStore = (FrugalListBase )_listStore.Clone(); } return myClone; } internal FrugalListBase _listStore; } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // Copyright (c) Microsoft Corporation. All rights reserved.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- RawKeyboardInputReport.cs
- AuthenticationService.cs
- TimeSpanOrInfiniteValidator.cs
- TableLayout.cs
- AppliedDeviceFiltersEditor.cs
- EntityDataSourceContextCreatingEventArgs.cs
- XamlReader.cs
- HttpCacheVary.cs
- PartialTrustVisibleAssemblyCollection.cs
- InvalidOperationException.cs
- COM2DataTypeToManagedDataTypeConverter.cs
- BindingNavigator.cs
- CompilerCollection.cs
- ReadWriteObjectLock.cs
- EncoderFallback.cs
- ContentValidator.cs
- XmlSerializerNamespaces.cs
- ScriptReference.cs
- COMException.cs
- GenerateTemporaryAssemblyTask.cs
- NameObjectCollectionBase.cs
- HttpPostedFile.cs
- ObjectListItemCollection.cs
- WindowsToolbarItemAsMenuItem.cs
- WebBrowserUriTypeConverter.cs
- KeyedHashAlgorithm.cs
- UseAttributeSetsAction.cs
- SqlTypeSystemProvider.cs
- CellTreeNodeVisitors.cs
- WorkflowHostingResponseContext.cs
- DesignBindingPropertyDescriptor.cs
- MapPathBasedVirtualPathProvider.cs
- ExecutionEngineException.cs
- XmlSchemaSimpleType.cs
- ScriptRegistrationManager.cs
- DeobfuscatingStream.cs
- HtmlTextBoxAdapter.cs
- FixedSOMPage.cs
- OSFeature.cs
- UserControlAutomationPeer.cs
- DbDataReader.cs
- SelfIssuedAuthRSACryptoProvider.cs
- PerCallInstanceContextProvider.cs
- MsmqSecureHashAlgorithm.cs
- CodeExpressionCollection.cs
- VariableElement.cs
- ServiceOperationParameter.cs
- XmlTextReader.cs
- XmlQueryOutput.cs
- _Events.cs
- HtmlInputControl.cs
- _ConnectOverlappedAsyncResult.cs
- FontWeight.cs
- HtmlLink.cs
- SecurityKeyType.cs
- PrimaryKeyTypeConverter.cs
- ScrollBar.cs
- BitmapDecoder.cs
- ListBox.cs
- SafeIUnknown.cs
- WebService.cs
- XmlSerializerVersionAttribute.cs
- BuildManagerHost.cs
- EventLogEntryCollection.cs
- DataGridViewColumnCollection.cs
- CapacityStreamGeometryContext.cs
- ISAPIWorkerRequest.cs
- LinqToSqlWrapper.cs
- MaskedTextProvider.cs
- DesignUtil.cs
- PersonalizationProviderHelper.cs
- MeasureItemEvent.cs
- AccessText.cs
- ChangeNode.cs
- RewritingProcessor.cs
- FileIOPermission.cs
- DelegatedStream.cs
- HandlerBase.cs
- FtpWebRequest.cs
- Stopwatch.cs
- WsdlInspector.cs
- NullableConverter.cs
- UniqueIdentifierService.cs
- HtmlMeta.cs
- ElementProxy.cs
- FormViewDeletedEventArgs.cs
- SpecularMaterial.cs
- ToolStripSeparator.cs
- SqlUdtInfo.cs
- UICuesEvent.cs
- Walker.cs
- Pkcs7Recipient.cs
- ModifiableIteratorCollection.cs
- Line.cs
- GroupBoxAutomationPeer.cs
- DomainUpDown.cs
- DataContractSerializerOperationFormatter.cs
- Transform.cs
- JapaneseLunisolarCalendar.cs
- AssociationTypeEmitter.cs