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(FrugalListBase newList);
///
/// 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(FrugalListBase newList);
///
/// 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
- ThreadInterruptedException.cs
- SemanticKeyElement.cs
- SoapElementAttribute.cs
- MachineKeySection.cs
- DummyDataSource.cs
- XmlIterators.cs
- WebResponse.cs
- ConfigDefinitionUpdates.cs
- CommonDialog.cs
- SqlRemoveConstantOrderBy.cs
- SystemWebSectionGroup.cs
- Menu.cs
- PropertyRef.cs
- AspCompat.cs
- DataGridViewColumnTypePicker.cs
- PenThreadPool.cs
- DataGridViewSortCompareEventArgs.cs
- UIElementParaClient.cs
- SqlProviderServices.cs
- KeyboardDevice.cs
- XmlTextReaderImplHelpers.cs
- SqlDataSourceEnumerator.cs
- WindowsButton.cs
- SecurityPermission.cs
- ThreadAbortException.cs
- TreeNodeStyle.cs
- StreamWriter.cs
- ImplicitInputBrush.cs
- Rectangle.cs
- XpsS0ValidatingLoader.cs
- ACL.cs
- BindingsSection.cs
- TextDecoration.cs
- UnhandledExceptionEventArgs.cs
- HwndSourceParameters.cs
- SerializationTrace.cs
- SessionPageStateSection.cs
- SiteMapNodeCollection.cs
- SqlParameter.cs
- Matrix3DStack.cs
- CookieProtection.cs
- SymLanguageVendor.cs
- ValidationRule.cs
- DropSource.cs
- Timer.cs
- SQLInt64.cs
- SiteMapNode.cs
- Size.cs
- EqualityComparer.cs
- InvalidCastException.cs
- DataBoundControlAdapter.cs
- PriorityBinding.cs
- FilteredXmlReader.cs
- AssemblyAttributes.cs
- Drawing.cs
- TimelineClockCollection.cs
- TextTreeFixupNode.cs
- Matrix3DConverter.cs
- EventRoute.cs
- BitmapEncoder.cs
- ClassImporter.cs
- Helper.cs
- Formatter.cs
- OrderedDictionary.cs
- DefaultPropertyAttribute.cs
- DatagridviewDisplayedBandsData.cs
- CharEntityEncoderFallback.cs
- ObjectContext.cs
- _ShellExpression.cs
- SqlInternalConnectionTds.cs
- ColumnPropertiesGroup.cs
- WindowHideOrCloseTracker.cs
- WebPartConnectionCollection.cs
- IPipelineRuntime.cs
- Properties.cs
- AspCompat.cs
- VersionPair.cs
- WindowsFont.cs
- sitestring.cs
- DataObjectCopyingEventArgs.cs
- TraceUtility.cs
- AuthenticationSection.cs
- ScrollBar.cs
- MgmtConfigurationRecord.cs
- MetadataPropertyCollection.cs
- DecimalStorage.cs
- CompilerState.cs
- DateTimeOffset.cs
- RtfToken.cs
- PointCollection.cs
- MailWebEventProvider.cs
- RefreshPropertiesAttribute.cs
- ArraySortHelper.cs
- Rect3DConverter.cs
- DynamicDataManager.cs
- QilInvokeLateBound.cs
- propertytag.cs
- UrlMappingCollection.cs
- SqlDependencyListener.cs
- NameObjectCollectionBase.cs