FrugalMap.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / wpf / src / Shared / MS / Utility / FrugalMap.cs / 1 / FrugalMap.cs

                            //---------------------------------------------------------------------------- 
//
// Copyright (C) Microsoft Corporation.  All rights reserved.
//
//--------------------------------------------------------------------------- 

using System; 
using System.Diagnostics; 
using System.Collections;
using System.Windows; 

#if WINDOWS_BASE
    using MS.Internal.WindowsBase;
#elif PRESENTATION_CORE 
    using MS.Internal.PresentationCore;
#elif PRESENTATIONFRAMEWORK 
    using MS.Internal.PresentationFramework; 
#elif DRT
    using MS.Internal.Drt; 
#else
#error Attempt to use FriendAccessAllowedAttribute from an unknown assembly.
using MS.Internal.YourAssemblyName;
#endif 

namespace MS.Utility 
{ 
    // These classes implement a frugal storage model for key/value pair data
    // structures. The keys are integers, and the values objects. 
    // Performance measurements show that Avalon has many maps that contain a
    // single key/value pair. Therefore these classes are structured to prefer
    // a map that contains a single key/value pair and uses a conservative
    // growth strategy to minimize the steady state memory footprint. To enforce 
    // the slow growth the map does not allow the user to set the capacity.
    // Also note that the map uses one fewer objects than the BCL HashTable and 
    // does no allocations at all until an item is inserted into the map. 
    //
    // The code is also structured to perform well from a CPU standpoint. Perf 
    // analysis of DependencyObject showed that we used a single entry 63% of
    // the time and growth tailed off quickly. Average access times are 8 to 16
    // times faster than a BCL Hashtable.
    // 
    // FrugalMap is appropriate for small maps or maps that grow slowly. Its
    // primary focus is for maps that contain fewer than 64 entries and that 
    // usually start with no entries, or a single entry. If you know your map 
    // will always have a minimum of 64 or more entires FrugalMap *may* not
    // be the best choice. Choose your collections wisely and pay particular 
    // attention to the growth patterns and search methods.

    // This enum controls the growth to successively more complex storage models
    internal enum FrugalMapStoreState 
    {
        Success, 
        ThreeObjectMap, 
        SixObjectMap,
        Array, 
        SortedArray,
        Hashtable
    }
 
    abstract class FrugalMapBase
    { 
        public abstract FrugalMapStoreState InsertEntry(int key, Object value); 

        public abstract void RemoveEntry(int key); 

        /// 
        /// Looks for an entry that contains the given key, null is returned if the
        /// key is not found. 
        /// 
        public abstract Object Search(int key); 
 

        ///  
        /// A routine used by enumerators that need a sorted map
        /// 
        public abstract void Sort();
 
        /// 
        /// A routine used by enumerators to iterate through the map 
        ///  
        public abstract void GetKeyValuePair(int index, out int key, out Object value);
 
        /// 
        /// A routine used to iterate through all the entries in the map
        /// 
        public abstract void Iterate(ArrayList list, FrugalMapIterationCallback callback); 

        ///  
        /// Promotes the key/value pairs in the current collection to the next larger 
        /// and more complex storage model.
        ///  
        public abstract void Promote(FrugalMapBase newMap);

        /// 
        /// Size of this data store 
        /// 
        public abstract int Count 
        { 
            get;
        } 

        protected const int INVALIDKEY = 0x7FFFFFFF;

        internal struct Entry 
        {
            public int Key; 
            public Object Value; 
        }
    } 

    /// 
    /// A simple class to handle a single key/value pair
    ///  
    internal sealed class SingleObjectMap : FrugalMapBase
    { 
        public SingleObjectMap() 
        {
            _loneEntry.Key = INVALIDKEY; 
            _loneEntry.Value = DependencyProperty.UnsetValue;
        }

        public override FrugalMapStoreState InsertEntry(int key, Object value) 
        {
            // If we don't have any entries or the existing entry is being overwritten, 
            // then we can use this map.  Otherwise we have to promote. 
            if ((INVALIDKEY == _loneEntry.Key) || (key == _loneEntry.Key))
            { 
                Debug.Assert(INVALIDKEY != key);

                _loneEntry.Key = key;
                _loneEntry.Value = value; 
                return FrugalMapStoreState.Success;
            } 
            else 
            {
                // Entry already used, move to an ThreeObjectMap 
                return FrugalMapStoreState.ThreeObjectMap;
            }
        }
 
        public override void RemoveEntry(int key)
        { 
            // Wipe out the info in the only entry if it matches the key. 
            if (key == _loneEntry.Key)
            { 
                _loneEntry.Key = INVALIDKEY;
                _loneEntry.Value = DependencyProperty.UnsetValue;
            }
        } 

        public override Object Search(int key) 
        { 
            if (key == _loneEntry.Key)
            { 
                return _loneEntry.Value;
            }
            return DependencyProperty.UnsetValue;
        } 

        public override void Sort() 
        { 
            // Single items are already sorted.
        } 

        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (0 == index) 
            {
                value = _loneEntry.Value; 
                key = _loneEntry.Key; 
            }
            else 
            {
                value = DependencyProperty.UnsetValue;
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index"); 
            }
        } 
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        { 
            if (Count == 1)
            {
                callback(list, _loneEntry.Key, _loneEntry.Value);
            } 
        }
 
        public override void Promote(FrugalMapBase newMap) 
        {
            if (FrugalMapStoreState.Success == newMap.InsertEntry(_loneEntry.Key, _loneEntry.Value)) 
            {
            }
            else
            { 
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            } 
        }
 
        // Size of this data store
        public override int Count
        {
            get 
            {
                if (INVALIDKEY != _loneEntry.Key) 
                { 
                    return 1;
                } 
                else
                {
                    return 0;
                } 
            }
        } 
 
        private Entry _loneEntry;
    } 


    /// 
    /// A simple class to handle a single object with 3 key/value pairs.  The pairs are stored unsorted 
    /// and uses a linear search.  Perf analysis showed that this yielded better memory locality and
    /// perf than an object and an array. 
    ///  
    /// 
    /// This map inserts at the last position.  Any time we add to the map we set _sorted to false. If you need 
    /// to iterate through the map in sorted order you must call Sort before using GetKeyValuePair.
    /// 
    internal sealed class ThreeObjectMap : FrugalMapBase
    { 
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        { 
            // Check to see if we are updating an existing entry 
            Debug.Assert(INVALIDKEY != key);
 
            // First check if the key matches the key of one of the existing entries.
            // If it does, overwrite the existing value and return success.
            switch (_count)
            { 
                case 1:
                    if (_entry0.Key == key) 
                    { 
                        _entry0.Value = value;
                        return FrugalMapStoreState.Success; 
                    }
                    break;

                case 2: 
                    if (_entry0.Key == key)
                    { 
                        _entry0.Value = value; 
                        return FrugalMapStoreState.Success;
                    } 
                    if (_entry1.Key == key)
                    {
                        _entry1.Value = value;
                        return FrugalMapStoreState.Success; 
                    }
                    break; 
 
                case 3:
                    if (_entry0.Key == key) 
                    {
                        _entry0.Value = value;
                        return FrugalMapStoreState.Success;
                    } 
                    if (_entry1.Key == key)
                    { 
                        _entry1.Value = value; 
                        return FrugalMapStoreState.Success;
                    } 
                    if (_entry2.Key == key)
                    {
                        _entry2.Value = value;
                        return FrugalMapStoreState.Success; 
                    }
                    break; 
 
                default:
                    break; 
            }

            // If we got past the above switch, that means this key
            // doesn't exist in the map already so we should add it. 
            // Only add it if we're not at the size limit; otherwise
            // we have to promote. 
            if (SIZE > _count) 
            {
                // Space still available to store the value. Insert 
                // into the entry at _count (the next available slot).
                switch (_count)
                {
                    case 0: 
                        _entry0.Key = key;
                        _entry0.Value = value; 
                        _sorted = true; 
                        break;
 
                    case 1:
                        _entry1.Key = key;
                        _entry1.Value = value;
                        // We have added an entry to the array, so we may not be sorted any longer 
                        _sorted = false;
                        break; 
 
                    case 2:
                        _entry2.Key = key; 
                        _entry2.Value = value;
                        // We have added an entry to the array, so we may not be sorted any longer
                        _sorted = false;
                        break; 
                }
                ++_count; 
 
                return FrugalMapStoreState.Success;
            } 
            else
            {
                // Array is full, move to a SixObjectMap
                return FrugalMapStoreState.SixObjectMap; 
            }
        } 
 
        public override void RemoveEntry(int key)
        { 
            // If the key 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.
            switch (_count) 
            {
                case 1: 
                    if (_entry0.Key == key) 
                    {
                        _entry0.Key = INVALIDKEY; 
                        _entry0.Value = DependencyProperty.UnsetValue;
                        --_count;
                        return;
                    } 
                    break;
 
                case 2: 
                    if (_entry0.Key == key)
                    { 
                        _entry0 = _entry1;
                        _entry1.Key = INVALIDKEY;
                        _entry1.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    } 
                    if (_entry1.Key == key) 
                    {
                        _entry1.Key = INVALIDKEY; 
                        _entry1.Value = DependencyProperty.UnsetValue;
                        --_count;
                    }
                    break; 

                case 3: 
                    if (_entry0.Key == key) 
                    {
                        _entry0 = _entry1; 
                        _entry1 = _entry2;
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    } 
                    if (_entry1.Key == key) 
                    {
                        _entry1 = _entry2; 
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break; 
                    }
                    if (_entry2.Key == key) 
                    { 
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break;
                    }
                    break; 

                default: 
                    break; 
            }
        } 

        public override Object Search(int key)
        {
            Debug.Assert(INVALIDKEY != key); 
            if (_count > 0)
            { 
                if (_entry0.Key == key) 
                {
                    return _entry0.Value; 
                }
                if (_count > 1)
                {
                    if (_entry1.Key == key) 
                    {
                        return _entry1.Value; 
                    } 
                    if ((_count > 2) && (_entry2.Key == key))
                    { 
                        return _entry2.Value;
                    }
                }
            } 
            return DependencyProperty.UnsetValue;
        } 
 
        public override void Sort()
        { 
            // If we're unsorted and we have entries to sort, do a simple
            // sort.  Sort the pairs (0,1), (1,2) and then (0,1) again.
            if ((false == _sorted) && (_count > 1))
            { 
                Entry temp;
                if (_entry0.Key > _entry1.Key) 
                { 
                    temp = _entry0;
                    _entry0 = _entry1; 
                    _entry1 = temp;
                }
                if (_count > 2)
                { 
                    if (_entry1.Key > _entry2.Key)
                    { 
                        temp = _entry1; 
                        _entry1 = _entry2;
                        _entry2 = temp; 

                        if (_entry0.Key > _entry1.Key)
                        {
                            temp = _entry0; 
                            _entry0 = _entry1;
                            _entry1 = temp; 
                        } 
                    }
                } 
                _sorted = true;
            }
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        { 
            if (index < _count) 
            {
                switch (index) 
                {
                    case 0:
                        key = _entry0.Key;
                        value = _entry0.Value; 
                        break;
 
                    case 1: 
                        key = _entry1.Key;
                        value = _entry1.Value; 
                        break;

                    case 2:
                        key = _entry2.Key; 
                        value = _entry2.Value;
                        break; 
 
                    default:
                        key = INVALIDKEY; 
                        value = DependencyProperty.UnsetValue;
                        break;
                }
            } 
            else
            { 
                key = INVALIDKEY; 
                value = DependencyProperty.UnsetValue;
                throw new ArgumentOutOfRangeException("index"); 
            }
        }

        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback) 
        {
            if (_count > 0) 
            { 
                if (_count >= 1)
                { 
                    callback(list, _entry0.Key, _entry0.Value);
                }
                if (_count >= 2)
                { 
                    callback(list, _entry1.Key, _entry1.Value);
                } 
                if (_count == 3) 
                {
                    callback(list, _entry2.Key, _entry2.Value); 
                }
            }
        }
 
        public override void Promote(FrugalMapBase newMap)
        { 
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry0.Key, _entry0.Value)) 
            {
                // newMap is smaller than previous map 
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry1.Key, _entry1.Value))
            { 
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            } 
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry2.Key, _entry2.Value))
            { 
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
        } 

        // Size of this data store 
        public override int Count 
        {
            get 
            {
                return _count;
            }
        } 

        private const int SIZE = 3; 
 
        // The number of items in the map.
        private UInt16 _count; 

        private bool _sorted;
        private Entry _entry0;
        private Entry _entry1; 
        private Entry _entry2;
    } 
 
    /// 
    /// A simple class to handle a single object with 6 key/value pairs.  The pairs are stored unsorted 
    /// and uses a linear search.  Perf analysis showed that this yielded better memory locality and
    /// perf than an object and an array.
    /// 
    ///  
    /// This map inserts at the last position.  Any time we add to the map we set _sorted to false. If you need
    /// to iterate through the map in sorted order you must call Sort before using GetKeyValuePair. 
    ///  
    internal sealed class SixObjectMap : FrugalMapBase
    { 
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        {
            // Check to see if we are updating an existing entry
            Debug.Assert(INVALIDKEY != key); 

            // First check if the key matches the key of one of the existing entries. 
            // If it does, overwrite the existing value and return success. 
            if (_count > 0)
            { 
                if (_entry0.Key == key)
                {
                    _entry0.Value = value;
                    return FrugalMapStoreState.Success; 
                }
                if (_count > 1) 
                { 
                    if (_entry1.Key == key)
                    { 
                        _entry1.Value = value;
                        return FrugalMapStoreState.Success;
                    }
                    if (_count > 2) 
                    {
                        if (_entry2.Key == key) 
                        { 
                            _entry2.Value = value;
                            return FrugalMapStoreState.Success; 
                        }
                        if (_count > 3)
                        {
                            if (_entry3.Key == key) 
                            {
                                _entry3.Value = value; 
                                return FrugalMapStoreState.Success; 
                            }
                            if (_count > 4) 
                            {
                                if (_entry4.Key == key)
                                {
                                    _entry4.Value = value; 
                                    return FrugalMapStoreState.Success;
                                } 
                                if ((_count > 5) && (_entry5.Key == key)) 
                                {
                                    _entry5.Value = value; 
                                    return FrugalMapStoreState.Success;
                                }
                            }
                        } 
                    }
                } 
            } 

            // If we got past the above switch, that means this key 
            // doesn't exist in the map already so we should add it.
            // Only add it if we're not at the size limit; otherwise
            // we have to promote.
            if (SIZE > _count) 
            {
                // We are adding an entry to the array, so we may not be sorted any longer 
                _sorted = false; 

                // Space still available to store the value. Insert 
                // into the entry at _count (the next available slot).
                switch (_count)
                {
                    case 0: 
                        _entry0.Key = key;
                        _entry0.Value = value; 
 
                        // Single entries are always sorted
                        _sorted = true; 
                        break;

                    case 1:
                        _entry1.Key = key; 
                        _entry1.Value = value;
                        break; 
 
                    case 2:
                        _entry2.Key = key; 
                        _entry2.Value = value;
                        break;

                    case 3: 
                        _entry3.Key = key;
                        _entry3.Value = value; 
                        break; 

                    case 4: 
                        _entry4.Key = key;
                        _entry4.Value = value;
                        break;
 
                    case 5:
                        _entry5.Key = key; 
                        _entry5.Value = value; 
                        break;
                } 
                ++_count;

                return FrugalMapStoreState.Success;
            } 
            else
            { 
                // Array is full, move to a Array 
                return FrugalMapStoreState.Array;
            } 
        }

        public override void RemoveEntry(int key)
        { 
            // If the key 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. 
            switch (_count)
            { 
                case 1:
                    if (_entry0.Key == key)
                    {
                        _entry0.Key = INVALIDKEY; 
                        _entry0.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        return; 
                    }
                    break; 

                case 2:
                    if (_entry0.Key == key)
                    { 
                        _entry0 = _entry1;
                        _entry1.Key = INVALIDKEY; 
                        _entry1.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1.Key = INVALIDKEY; 
                        _entry1.Value = DependencyProperty.UnsetValue;
                        --_count; 
                    } 
                    break;
 
                case 3:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1; 
                        _entry1 = _entry2;
                        _entry2.Key = INVALIDKEY; 
                        _entry2.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1 = _entry2; 
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue; 
                        --_count; 
                        break;
                    } 
                    if (_entry2.Key == key)
                    {
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    } 
                    break;
 
                case 4:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1; 
                        _entry1 = _entry2;
                        _entry2 = _entry3; 
                        _entry3.Key = INVALIDKEY; 
                        _entry3.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    }
                    if (_entry1.Key == key)
                    { 
                        _entry1 = _entry2;
                        _entry2 = _entry3; 
                        _entry3.Key = INVALIDKEY; 
                        _entry3.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    }
                    if (_entry2.Key == key)
                    { 
                        _entry2 = _entry3;
                        _entry3.Key = INVALIDKEY; 
                        _entry3.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    }
                    if (_entry3.Key == key)
                    {
                        _entry3.Key = INVALIDKEY; 
                        _entry3.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break; 
                    }
                    break; 

                case 5:
                    if (_entry0.Key == key)
                    { 
                        _entry0 = _entry1;
                        _entry1 = _entry2; 
                        _entry2 = _entry3; 
                        _entry3 = _entry4;
                        _entry4.Key = INVALIDKEY; 
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    } 
                    if (_entry1.Key == key)
                    { 
                        _entry1 = _entry2; 
                        _entry2 = _entry3;
                        _entry3 = _entry4; 
                        _entry4.Key = INVALIDKEY;
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break; 
                    }
                    if (_entry2.Key == key) 
                    { 
                        _entry2 = _entry3;
                        _entry3 = _entry4; 
                        _entry4.Key = INVALIDKEY;
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break; 
                    }
                    if (_entry3.Key == key) 
                    { 
                        _entry3 = _entry4;
                        _entry4.Key = INVALIDKEY; 
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    } 
                    if (_entry4.Key == key)
                    { 
                        _entry4.Key = INVALIDKEY; 
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    }
                    break;
 
                case 6:
                    if (_entry0.Key == key) 
                    { 
                        _entry0 = _entry1;
                        _entry1 = _entry2; 
                        _entry2 = _entry3;
                        _entry3 = _entry4;
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break; 
                    }
                    if (_entry1.Key == key) 
                    {
                        _entry1 = _entry2;
                        _entry2 = _entry3;
                        _entry3 = _entry4; 
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    }
                    if (_entry2.Key == key)
                    {
                        _entry2 = _entry3; 
                        _entry3 = _entry4;
                        _entry4 = _entry5; 
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    }
                    if (_entry3.Key == key)
                    { 
                        _entry3 = _entry4;
                        _entry4 = _entry5; 
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    }
                    if (_entry4.Key == key)
                    { 
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    }
                    if (_entry5.Key == key)
                    {
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break; 
                    }
                    break; 

                default:
                    break;
            } 
        }
 
        public override Object Search(int key) 
        {
            Debug.Assert(INVALIDKEY != key); 
            if (_count > 0)
            {
                if (_entry0.Key == key)
                { 
                    return _entry0.Value;
                } 
                if (_count > 1) 
                {
                    if (_entry1.Key == key) 
                    {
                        return _entry1.Value;
                    }
                    if (_count > 2) 
                    {
                        if (_entry2.Key == key) 
                        { 
                            return _entry2.Value;
                        } 
                        if (_count > 3)
                        {
                            if (_entry3.Key == key)
                            { 
                                return _entry3.Value;
                            } 
                            if (_count > 4) 
                            {
                                if (_entry4.Key == key) 
                                {
                                    return _entry4.Value;
                                }
                                if ((_count > 5) && (_entry5.Key == key)) 
                                {
                                    return _entry5.Value; 
                                } 
                            }
                        } 
                    }
                }
            }
            return DependencyProperty.UnsetValue; 
        }
 
        public override void Sort() 
        {
            // If we're unsorted and we have entries to sort, do a simple 
            // bubble sort. Sort the pairs, 0..5, and then again until we no
            // longer do any swapping.
            if ((false == _sorted) && (_count > 1))
            { 
                bool swapped;
 
                do 
                {
                    swapped = false; 

                    Entry temp;
                    if (_entry0.Key > _entry1.Key)
                    { 
                        temp = _entry0;
                        _entry0 = _entry1; 
                        _entry1 = temp; 
                        swapped = true;
                    } 
                    if (_count > 2)
                    {
                        if (_entry1.Key > _entry2.Key)
                        { 
                            temp = _entry1;
                            _entry1 = _entry2; 
                            _entry2 = temp; 
                            swapped = true;
                        } 
                        if (_count > 3)
                        {
                            if (_entry2.Key > _entry3.Key)
                            { 
                                temp = _entry2;
                                _entry2 = _entry3; 
                                _entry3 = temp; 
                                swapped = true;
                            } 
                            if (_count > 4)
                            {
                                if (_entry3.Key > _entry4.Key)
                                { 
                                    temp = _entry3;
                                    _entry3 = _entry4; 
                                    _entry4 = temp; 
                                    swapped = true;
                                } 
                                if (_count > 5)
                                {
                                    if (_entry4.Key > _entry5.Key)
                                    { 
                                        temp = _entry4;
                                        _entry4 = _entry5; 
                                        _entry5 = temp; 
                                        swapped = true;
                                    } 
                                }
                            }
                        }
                    } 
                }
                while (swapped); 
                _sorted = true; 
            }
        } 

        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (index < _count) 
            {
                switch (index) 
                { 
                    case 0:
                        key = _entry0.Key; 
                        value = _entry0.Value;
                        break;

                    case 1: 
                        key = _entry1.Key;
                        value = _entry1.Value; 
                        break; 

                    case 2: 
                        key = _entry2.Key;
                        value = _entry2.Value;
                        break;
 
                    case 3:
                        key = _entry3.Key; 
                        value = _entry3.Value; 
                        break;
 
                    case 4:
                        key = _entry4.Key;
                        value = _entry4.Value;
                        break; 

                    case 5: 
                        key = _entry5.Key; 
                        value = _entry5.Value;
                        break; 

                    default:
                        key = INVALIDKEY;
                        value = DependencyProperty.UnsetValue; 
                        break;
                } 
            } 
            else
            { 
                key = INVALIDKEY;
                value = DependencyProperty.UnsetValue;
                throw new ArgumentOutOfRangeException("index");
            } 
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback) 
        {
            if (_count > 0) 
            {
                if (_count >= 1)
                {
                    callback(list, _entry0.Key, _entry0.Value); 
                }
                if (_count >= 2) 
                { 
                    callback(list, _entry1.Key, _entry1.Value);
                } 
                if (_count >= 3)
                {
                    callback(list, _entry2.Key, _entry2.Value);
                } 
                if (_count >= 4)
                { 
                    callback(list, _entry3.Key, _entry3.Value); 
                }
                if (_count >= 5) 
                {
                    callback(list, _entry4.Key, _entry4.Value);
                }
                if (_count == 6) 
                {
                    callback(list, _entry5.Key, _entry5.Value); 
                } 
            }
        } 

        public override void Promote(FrugalMapBase newMap)
        {
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry0.Key, _entry0.Value)) 
            {
                // newMap is smaller than previous map 
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry1.Key, _entry1.Value)) 
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            } 
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry2.Key, _entry2.Value))
            { 
                // newMap is smaller than previous map 
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            } 
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry3.Key, _entry3.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry4.Key, _entry4.Value)) 
            { 
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry5.Key, _entry5.Value))
            {
                // newMap is smaller than previous map 
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            } 
        } 

        // Size of this data store 
        public override int Count
        {
            get
            { 
                return _count;
            } 
        } 

        private const int SIZE = 6; 

        // The number of items in the map.
        private UInt16 _count;
 
        private bool _sorted;
        private Entry _entry0; 
        private Entry _entry1; 
        private Entry _entry2;
        private Entry _entry3; 
        private Entry _entry4;
        private Entry _entry5;
    }
 
    /// 
    /// A simple class to handle an array of between 6 and 12 key/value pairs.  It is unsorted 
    /// and uses a linear search.  Perf analysis showed that this was the optimal size for both 
    /// memory and perf.  The values may need to be adjusted as the CLR and Avalon evolve.
    ///  
    internal sealed class ArrayObjectMap : FrugalMapBase
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        { 
            // Check to see if we are updating an existing entry
            for (int index = 0; index < _count; ++index) 
            { 
                Debug.Assert(INVALIDKEY != key);
 
                if (_entries[index].Key == key)
                {
                    _entries[index].Value = value;
                    return FrugalMapStoreState.Success; 
                }
            } 
 
            // New key/value pair
            if (MAXSIZE > _count) 
            {
                // Space still available to store the value
                if (null != _entries)
                { 
                    // We are adding an entry to the array, so we may not be sorted any longer
                    _sorted = false; 
 
                    if (_entries.Length > _count)
                    { 
                        // Have empty entries, just set the first available
                    }
                    else
                    { 
                        Entry[] destEntries = new Entry[_entries.Length + GROWTH];
 
                        // Copy old array 
                        Array.Copy(_entries, 0, destEntries, 0, _entries.Length);
                        _entries = destEntries; 
                    }
                }
                else
                { 
                    _entries = new Entry[MINSIZE];
 
                    // No entries, must be sorted 
                    _sorted = true;
                } 

                // Stuff in the new key/value pair
                _entries[_count].Key = key;
                _entries[_count].Value = value; 

                // Bump the count for the entry just added. 
                ++_count; 

                return FrugalMapStoreState.Success; 
            }
            else
            {
                // Array is full, move to a SortedArray 
                return FrugalMapStoreState.SortedArray;
            } 
        } 

        public override void RemoveEntry(int key) 
        {
            for (int index = 0; index < _count; ++index)
            {
                if (_entries[index].Key == key) 
                {
                    // 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].Key = INVALIDKEY;
                    _entries[_count - 1].Value = DependencyProperty.UnsetValue; 
                    --_count; 
                    break;
                } 
            }
        }

        public override Object Search(int key) 
        {
            for (int index = 0; index < _count; ++index) 
            { 
                if (key == _entries[index].Key)
                { 
                    return _entries[index].Value;
                }
            }
            return DependencyProperty.UnsetValue; 
        }
 
        public override void Sort() 
        {
            if ((false == _sorted) && (_count > 1)) 
            {
                QSort(0, (_count - 1));
                _sorted = true;
            } 
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value) 
        {
            if (index < _count) 
            {
                value = _entries[index].Value;
                key = _entries[index].Key;
            } 
            else
            { 
                value = DependencyProperty.UnsetValue; 
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index"); 
            }
        }

        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback) 
        {
            if (_count > 0) 
            { 
                for (int i=0; i< _count; i++)
                { 
                    callback(list, _entries[i].Key, _entries[i].Value);
                }
            }
        } 

        public override void Promote(FrugalMapBase newMap) 
        { 
            for (int index = 0; index < _entries.Length; ++index)
            { 
                if (FrugalMapStoreState.Success == newMap.InsertEntry(_entries[index].Key, _entries[index].Value))
                {
                    continue;
                } 
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            } 
        }
 
        // Size of this data store
        public override int Count
        {
            get 
            {
                return _count; 
            } 
        }
 
        // Compare two Entry nodes in the _entries array
        private int Compare(int left, int right)
        {
            return (_entries[left].Key - _entries[right].Key); 
        }
 
        // Partition the _entries array for QuickSort 
        private int Partition(int left, int right)
        { 
            int pivot = right;
            int i = left - 1;
            int j = right;
            Entry temp; 

            for (;;) 
            { 
                while (Compare(++i, pivot) < 0);
                while (Compare(pivot, --j) < 0) 
                {
                    if (j == left)
                    {
                        break; 
                    }
                } 
                if (i >= j) 
                {
                    break; 
                }
                temp = _entries[j];
                _entries[j] = _entries[i];
                _entries[i] = temp; 
            }
            temp = _entries[right]; 
            _entries[right] = _entries[i]; 
            _entries[i] = temp;
            return i; 
        }

        // Sort the _entries array using an index based QuickSort
        private void QSort(int left, int right) 
        {
            if (left < right) 
            { 
                int pivot = Partition(left, right);
                QSort(left, pivot - 1); 
                QSort(pivot + 1, right);
            }
        }
 
        // MINSIZE and GROWTH chosen to minimize memory footprint
        private const int MINSIZE = 9; 
        private const int MAXSIZE = 15; 
        private const int GROWTH = 3;
 
        // The number of items in the map.
        private UInt16 _count;

        private bool _sorted; 
        private Entry[] _entries;
    } 
 
    // A sorted array of key/value pairs. A binary search is used to minimize the cost of insert/search.
 
    internal sealed class SortedObjectMap : FrugalMapBase
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        { 
            bool found;
 
            Debug.Assert(INVALIDKEY != key); 

            // Check to see if we are updating an existing entry 
            int index = FindInsertIndex(key, out found);
            if (found)
            {
                _entries[index].Value = value; 
                return FrugalMapStoreState.Success;
            } 
            else 
            {
                // New key/value pair 
                if (MAXSIZE > _count)
                {
                    // Less than the maximum array size
                    if (null != _entries) 
                    {
                        if (_entries.Length > _count) 
                        { 
                            // Have empty entries, just set the first available
                        } 
                        else
                        {
                            Entry[] destEntries = new Entry[_entries.Length + GROWTH];
 
                            // Copy old array
                            Array.Copy(_entries, 0, destEntries, 0, _entries.Length); 
                            _entries = destEntries; 
                        }
                    } 
                    else
                    {
                        _entries = new Entry[MINSIZE];
                    } 

                    // Inserting into the middle of the existing entries? 
                    if (index < _count) 
                    {
                        // Move higher valued keys to make room for the new key 
                        Array.Copy(_entries, index, _entries, index + 1, (_count - index));
                    }
                    else
                    { 
                        _lastKey = key;
                    } 
 
                    // Stuff in the new key/value pair
                    _entries[index].Key = key; 
                    _entries[index].Value = value;
                    ++_count;
                    return FrugalMapStoreState.Success;
                } 
                else
                { 
                    // SortedArray is full, move to a hashtable 
                    return FrugalMapStoreState.Hashtable;
                } 
            }
        }

        public override void RemoveEntry(int key) 
        {
            bool found; 
 
            Debug.Assert(INVALIDKEY != key);
 
            int index = FindInsertIndex(key, out found);

            if (found)
            { 
                // Shift entries down
                int numToCopy = (_count - index) - 1; 
                if (numToCopy > 0) 
                {
                    Array.Copy(_entries, index + 1, _entries, index, numToCopy); 
                }
                else
                {
                    // If we're not copying anything, then it means we are 
                    //  going to remove the last entry.  Update _lastKey so
                    //  that it reflects the key of the new "last entry" 
                    if( _count > 1 ) 
                    {
                        // Next-to-last entry will be the new last entry 
                        _lastKey = _entries[_count - 2].Key;
                    }
                    else
                    { 
                        // Unless there isn't a next-to-last entry, in which
                        //  case the key is reset to INVALIDKEY. 
                        _lastKey = INVALIDKEY; 
                    }
                } 

                // Wipe out the last entry
                _entries[_count - 1].Key = INVALIDKEY;
                _entries[_count - 1].Value = DependencyProperty.UnsetValue; 

                --_count; 
            } 
        }
 
        public override Object Search(int key)
        {
            bool found;
 
            int index = FindInsertIndex(key, out found);
            if (found) 
            { 
                return _entries[index].Value;
            } 
            return DependencyProperty.UnsetValue;
        }

        public override void Sort() 
        {
            // Always sorted. 
        } 

        public override void GetKeyValuePair(int index, out int key, out Object value) 
        {
            if (index < _count)
            {
                value = _entries[index].Value; 
                key = _entries[index].Key;
            } 
            else 
            {
                value = DependencyProperty.UnsetValue; 
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index");
            }
        } 

        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback) 
        { 
            if (_count > 0)
            { 
                for (int i=0; i< _count; i++)
                {
                    callback(list, _entries[i].Key, _entries[i].Value);
                } 
            }
        } 
 
        public override void Promote(FrugalMapBase newMap)
        { 
            for (int index = 0; index < _entries.Length; ++index)
            {
                if (FrugalMapStoreState.Success == newMap.InsertEntry(_entries[index].Key, _entries[index].Value))
                { 
                    continue;
                } 
                // newMap is smaller than previous map 
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            } 
        }

        private int FindInsertIndex(int key, out bool found)
        { 
            int iLo = 0;
 
            // Only do the binary search if there is a chance of finding the key 
            // This also speeds insertion because we tend to insert at the end.
            if ((_count > 0) && (key <= _lastKey)) 
            {
                // The array index used for insertion is somewhere between 0
                //  and _count-1 inclusive
                int iHi = _count-1; 

                // Do a binary search to find the insertion point 
                do 
                {
                    int iPv = (iHi + iLo) / 2; 
                    if (key <= _entries[iPv].Key)
                    {
                        iHi = iPv;
                    } 
                    else
                    { 
                        iLo = iPv + 1; 
                    }
                } 
                while (iLo < iHi);
                found = (key == _entries[iLo].Key);
            }
            else 
            {
                // Insert point is at the end 
                iLo = _count; 
                found = false;
            } 
            return iLo;
        }

        public override int Count 
        {
            get 
            { 
                return _count;
            } 
        }

        // MINSIZE chosen to be larger than MAXSIZE of the ArrayObjectMap with some extra space for new values
        // The MAXSIZE and GROWTH are chosen to minimize memory usage as we grow the array 
        private const int MINSIZE = 16;
        private const int MAXSIZE = 128; 
        private const int GROWTH = 8; 

        // The number of items in the map. 
        internal int _count;

        private int _lastKey = INVALIDKEY;
        private Entry[] _entries; 
    }
 
    internal sealed class HashObjectMap : FrugalMapBase 
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value) 
        {
            Debug.Assert(INVALIDKEY != key);

            if (null != _entries) 
            {
                // This is done because forward branches 
                // default prediction is not to be taken 
                // making this a CPU win because insert
                // is a common operation. 
            }
            else
            {
                _entries = new Hashtable(MINSIZE); 
            }
 
            _entries[key] = ((value != NullValue) && (value != null)) ? value : NullValue; 
            return FrugalMapStoreState.Success;
        } 

        public override void RemoveEntry(int key)
        {
            _entries.Remove(key); 
        }
 
        public override Object Search(int key) 
        {
            object value = _entries[key]; 

            return ((value != NullValue) && (value != null)) ? value : DependencyProperty.UnsetValue;
        }
 
        public override void Sort()
        { 
            // Always sorted. 
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (index < _entries.Count)
            { 
                IDictionaryEnumerator myEnumerator = _entries.GetEnumerator();
 
                // Move to first valid value 
                myEnumerator.MoveNext();
 
                for (int i = 0; i < index; ++i)
                {
                    myEnumerator.MoveNext();
                } 
                key = (int)myEnumerator.Key;
                if ((myEnumerator.Value != NullValue) && (myEnumerator.Value != null)) 
                { 
                    value = myEnumerator.Value;
                } 
                else
                {
                    value = DependencyProperty.UnsetValue;
                } 
            }
            else 
            { 
                value = DependencyProperty.UnsetValue;
                key = INVALIDKEY; 
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        { 
            IDictionaryEnumerator myEnumerator = _entries.GetEnumerator(); 

            while (myEnumerator.MoveNext()) 
            {
                int key = (int)myEnumerator.Key;
                object value;
                if ((myEnumerator.Value != NullValue) && (myEnumerator.Value != null)) 
                {
                    value = myEnumerator.Value; 
                } 
                else
                { 
                    value = DependencyProperty.UnsetValue;
                }

                callback(list, key, value); 
            }
        } 
 
        public override void Promote(FrugalMapBase newMap)
        { 
            // Should never get here
            throw new InvalidOperationException(SR.Get(SRID.FrugalMap_CannotPromoteBeyondHashtable));
        }
 
        // Size of this data store
        public override int Count 
        { 
            get
            { 
                return _entries.Count;
            }
        }
 
        // 163 is chosen because it is the first prime larger than 128, the MAXSIZE of SortedObjectMap
        internal const int MINSIZE = 163; 
 
        // Hashtable will return null from its indexer if the key is not
        // found OR if the value is null.  To distinguish between these 
        // two cases we insert NullValue instead of null.
        private static object NullValue = new object();

        internal Hashtable _entries; 
    }
 
    [FriendAccessAllowed] 
    internal struct FrugalMap
    { 
        public object this[int key]
        {
            get
            { 
                // If no entry, DependencyProperty.UnsetValue is returned
                if (null != _mapStore) 
                { 
                    return _mapStore.Search(key);
                } 
                return DependencyProperty.UnsetValue;
            }

            set 
            {
                if (value != DependencyProperty.UnsetValue) 
                { 
                    // If not unset value, ensure write success
                    if (null != _mapStore) 
                    {
                        // This is done because forward branches
                        // default prediction is not to be taken
                        // making this a CPU win because set is 
                        // a common operation.
                    } 
                    else 
                    {
                        _mapStore = new SingleObjectMap(); 
                    }

                    FrugalMapStoreState myState = _mapStore.InsertEntry(key, value);
                    if (FrugalMapStoreState.Success == myState) 
                    {
                        return; 
                    } 
                    else
                    { 
                        // Need to move to a more complex storage
                        FrugalMapBase newStore;

                        if (FrugalMapStoreState.ThreeObjectMap == myState) 
                        {
                            newStore = new ThreeObjectMap(); 
                        } 
                        else if (FrugalMapStoreState.SixObjectMap == myState)
                        { 
                            newStore = new SixObjectMap();
                        }
                        else if (FrugalMapStoreState.Array == myState)
                        { 
                            newStore = new ArrayObjectMap();
                        } 
                        else if (FrugalMapStoreState.SortedArray == myState) 
                        {
                            newStore = new SortedObjectMap(); 
                        }
                        else if (FrugalMapStoreState.Hashtable == myState)
                        {
                            newStore = new HashObjectMap(); 
                        }
                        else 
                        { 
                            throw new InvalidOperationException(SR.Get(SRID.FrugalMap_CannotPromoteBeyondHashtable));
                        } 

                        // Extract the values from the old store and insert them into the new store
                        _mapStore.Promote(newStore);
 
                        // Insert the new value
                        _mapStore = newStore; 
                        _mapStore.InsertEntry(key, value); 
                    }
                } 
                else
                {
                    // DependencyProperty.UnsetValue means remove the value
                    if (null != _mapStore) 
                    {
                        _mapStore.RemoveEntry(key); 
                        if (_mapStore.Count == 0) 
                        {
                            // Map Store is now empty ... throw it away 
                            _mapStore = null;
                        }
                    }
                } 
            }
        } 
 
        public void Sort()
        { 
            if (null != _mapStore)
            {
                _mapStore.Sort();
            } 
        }
 
        public void GetKeyValuePair(int index, out int key, out Object value) 
        {
            if (null != _mapStore) 
            {
                _mapStore.GetKeyValuePair(index, out key, out value);
            }
            else 
            {
                throw new ArgumentOutOfRangeException("index"); 
            } 
        }
 
        public void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (null != callback)
            { 
                if (null != list)
                { 
                    if (_mapStore != null) 
                    {
                        _mapStore.Iterate(list, callback); 
                    }
                }
                else
                { 
                    throw new ArgumentNullException("list");
                } 
            } 
            else
            { 
                throw new ArgumentNullException("callback");
            }
        }
 
        public int Count
        { 
            get 
            {
                if (null != _mapStore) 
                {
                    return _mapStore.Count;
                }
                return 0; 
            }
        } 
 
        internal FrugalMapBase _mapStore;
    } 

    // A sorted array of key/value pairs. A binary search is used to minimize the cost of insert/search.

    internal sealed class LargeSortedObjectMap : FrugalMapBase 
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value) 
        { 
            bool found;
 
            Debug.Assert(INVALIDKEY != key);

            // Check to see if we are updating an existing entry
            int index = FindInsertIndex(key, out found); 
            if (found)
            { 
                _entries[index].Value = value; 
                return FrugalMapStoreState.Success;
            } 
            else
            {
                // New key/value pair
                if (null != _entries) 
                {
                    if (_entries.Length > _count) 
                    { 
                        // Have empty entries, just set the first available
                    } 
                    else
                    {
                        int size = _entries.Length;
                        Entry[] destEntries = new Entry[size + (size >> 1)]; 

                        // Copy old array 
                        Array.Copy(_entries, 0, destEntries, 0, _entries.Length); 
                        _entries = destEntries;
                    } 
                }
                else
                {
                    _entries = new Entry[MINSIZE]; 
                }
 
                // Inserting into the middle of the existing entries? 
                if (index < _count)
                { 
                    // Move higher valued keys to make room for the new key
                    Array.Copy(_entries, index, _entries, index + 1, (_count - index));
                }
                else 
                {
                    _lastKey = key; 
                } 

                // Stuff in the new key/value pair 
                _entries[index].Key = key;
                _entries[index].Value = value;
                ++_count;
                return FrugalMapStoreState.Success; 
            }
        } 
 
        public override void RemoveEntry(int key)
        { 
            bool found;

            Debug.Assert(INVALIDKEY != key);
 
            int index = FindInsertIndex(key, out found);
 
            if (found) 
            {
                // Shift entries down 
                int numToCopy = (_count - index) - 1;
                if (numToCopy > 0)
                {
                    Array.Copy(_entries, index + 1, _entries, index, numToCopy); 
                }
                else 
                { 
                    // If we're not copying anything, then it means we are
                    //  going to remove the last entry.  Update _lastKey so 
                    //  that it reflects the key of the new "last entry"
                    if( _count > 1 )
                    {
                        // Next-to-last entry will be the new last entry 
                        _lastKey = _entries[_count - 2].Key;
                    } 
                    else 
                    {
                        // Unless there isn't a next-to-last entry, in which 
                        //  case the key is reset to INVALIDKEY.
                        _lastKey = INVALIDKEY;
                    }
                } 

                // Wipe out the last entry 
                _entries[_count - 1].Key = INVALIDKEY; 
                _entries[_count - 1].Value = DependencyProperty.UnsetValue;
 
                --_count;
            }
        }
 
        public override Object Search(int key)
        { 
            bool found; 

            int index = FindInsertIndex(key, out found); 
            if (found)
            {
                return _entries[index].Value;
            } 
            return DependencyProperty.UnsetValue;
        } 
 
        public override void Sort()
        { 
            // Always sorted.
        }

        public override void GetKeyValuePair(int index, out int key, out Object value) 
        {
            if (index < _count) 
            { 
                value = _entries[index].Value;
                key = _entries[index].Key; 
            }
            else
            {
                value = DependencyProperty.UnsetValue; 
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index"); 
            } 
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (_count > 0)
            { 
                for (int i=0; i< _count; i++)
                { 
                    callback(list, _entries[i].Key, _entries[i].Value); 
                }
            } 
        }

        public override void Promote(FrugalMapBase newMap)
        { 
            for (int index = 0; index < _entries.Length; ++index)
            { 
                if (FrugalMapStoreState.Success == newMap.InsertEntry(_entries[index].Key, _entries[index].Value)) 
                {
                    continue; 
                }
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            } 
        }
 
        private int FindInsertIndex(int key, out bool found) 
        {
            int iLo = 0; 

            // Only do the binary search if there is a chance of finding the key
            // This also speeds insertion because we tend to insert at the end.
            if ((_count > 0) && (key <= _lastKey)) 
            {
                // The array index used for insertion is somewhere between 0 
                //  and _count-1 inclusive 
                int iHi = _count-1;
 
                // Do a binary search to find the insertion point
                do
                {
                    int iPv = (iHi + iLo) / 2; 
                    if (key <= _entries[iPv].Key)
                    { 
                        iHi = iPv; 
                    }
                    else 
                    {
                        iLo = iPv + 1;
                    }
                } 
                while (iLo < iHi);
                found = (key == _entries[iLo].Key); 
            } 
            else
            { 
                // Insert point is at the end
                iLo = _count;
                found = false;
            } 
            return iLo;
        } 
 
        public override int Count
        { 
            get
            {
                return _count;
            } 
        }
 
        // MINSIZE chosen to be small, growth rate of 1.5 is slow at small sizes, but increasingly agressive as 
        // the array grows
        private const int MINSIZE = 2; 

        // The number of items in the map.
        internal int _count;
 
        private int _lastKey = INVALIDKEY;
        private Entry[] _entries; 
    } 

    // This is a variant of FrugalMap that always uses an array as the underlying store. 
    // This avoids the virtual method calls that are present when the store morphs through
    // the size efficient store classes normally used. It is appropriate only when we know the
    // store will always be populated and individual elements will be accessed in a tight loop.
    internal struct InsertionSortMap 
    {
        public object this[int key] 
        { 
            get
            { 
                // If no entry, DependencyProperty.UnsetValue is returned
                if (null != _mapStore)
                {
                    return _mapStore.Search(key); 
                }
                return DependencyProperty.UnsetValue; 
            } 

            set 
            {
                if (value != DependencyProperty.UnsetValue)
                {
                    // If not unset value, ensure write success 
                    if (null != _mapStore)
                    { 
                        // This is done because forward branches 
                        // default prediction is not to be taken
                        // making this a CPU win because set is 
                        // a common operation.
                    }
                    else
                    { 
                        _mapStore = new LargeSortedObjectMap();
                    } 
 
                    FrugalMapStoreState myState = _mapStore.InsertEntry(key, value);
                    if (FrugalMapStoreState.Success == myState) 
                    {
                        return;
                    }
                    else 
                    {
                        // Need to move to a more complex storage 
                        LargeSortedObjectMap newStore; 

                        if (FrugalMapStoreState.SortedArray == myState) 
                        {
                            newStore = new LargeSortedObjectMap();
                        }
                        else 
                        {
                            throw new InvalidOperationException(SR.Get(SRID.FrugalMap_CannotPromoteBeyondHashtable)); 
                        } 

                        // Extract the values from the old store and insert them into the new store 
                        _mapStore.Promote(newStore);

                        // Insert the new value
                        _mapStore = newStore; 
                        _mapStore.InsertEntry(key, value);
                    } 
                } 
                else
                { 
                    // DependencyProperty.UnsetValue means remove the value
                    if (null != _mapStore)
                    {
                        _mapStore.RemoveEntry(key); 
                        if (_mapStore.Count == 0)
                        { 
                            // Map Store is now empty ... throw it away 
                            _mapStore = null;
                        } 
                    }
                }
            }
        } 

        public void Sort() 
        { 
            if (null != _mapStore)
            { 
                _mapStore.Sort();
            }
        }
 
        public void GetKeyValuePair(int index, out int key, out Object value)
        { 
            if (null != _mapStore) 
            {
                _mapStore.GetKeyValuePair(index, out key, out value); 
            }
            else
            {
                throw new ArgumentOutOfRangeException("index"); 
            }
        } 
 
        public void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        { 
            if (null != callback)
            {
                if (null != list)
                { 
                    if (_mapStore != null)
                    { 
                        _mapStore.Iterate(list, callback); 
                    }
                } 
                else
                {
                    throw new ArgumentNullException("list");
                } 
            }
            else 
            { 
                throw new ArgumentNullException("callback");
            } 
        }

        public int Count
        { 
            get
            { 
                if (null != _mapStore) 
                {
                    return _mapStore.Count; 
                }
                return 0;
            }
        } 

        internal LargeSortedObjectMap _mapStore; 
    } 

    ///  
    ///     FrugalMapIterationCallback
    /// 
    internal delegate void FrugalMapIterationCallback(ArrayList list, int key, object value);
} 


// 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.Windows; 

#if WINDOWS_BASE
    using MS.Internal.WindowsBase;
#elif PRESENTATION_CORE 
    using MS.Internal.PresentationCore;
#elif PRESENTATIONFRAMEWORK 
    using MS.Internal.PresentationFramework; 
#elif DRT
    using MS.Internal.Drt; 
#else
#error Attempt to use FriendAccessAllowedAttribute from an unknown assembly.
using MS.Internal.YourAssemblyName;
#endif 

namespace MS.Utility 
{ 
    // These classes implement a frugal storage model for key/value pair data
    // structures. The keys are integers, and the values objects. 
    // Performance measurements show that Avalon has many maps that contain a
    // single key/value pair. Therefore these classes are structured to prefer
    // a map that contains a single key/value pair and uses a conservative
    // growth strategy to minimize the steady state memory footprint. To enforce 
    // the slow growth the map does not allow the user to set the capacity.
    // Also note that the map uses one fewer objects than the BCL HashTable and 
    // does no allocations at all until an item is inserted into the map. 
    //
    // The code is also structured to perform well from a CPU standpoint. Perf 
    // analysis of DependencyObject showed that we used a single entry 63% of
    // the time and growth tailed off quickly. Average access times are 8 to 16
    // times faster than a BCL Hashtable.
    // 
    // FrugalMap is appropriate for small maps or maps that grow slowly. Its
    // primary focus is for maps that contain fewer than 64 entries and that 
    // usually start with no entries, or a single entry. If you know your map 
    // will always have a minimum of 64 or more entires FrugalMap *may* not
    // be the best choice. Choose your collections wisely and pay particular 
    // attention to the growth patterns and search methods.

    // This enum controls the growth to successively more complex storage models
    internal enum FrugalMapStoreState 
    {
        Success, 
        ThreeObjectMap, 
        SixObjectMap,
        Array, 
        SortedArray,
        Hashtable
    }
 
    abstract class FrugalMapBase
    { 
        public abstract FrugalMapStoreState InsertEntry(int key, Object value); 

        public abstract void RemoveEntry(int key); 

        /// 
        /// Looks for an entry that contains the given key, null is returned if the
        /// key is not found. 
        /// 
        public abstract Object Search(int key); 
 

        ///  
        /// A routine used by enumerators that need a sorted map
        /// 
        public abstract void Sort();
 
        /// 
        /// A routine used by enumerators to iterate through the map 
        ///  
        public abstract void GetKeyValuePair(int index, out int key, out Object value);
 
        /// 
        /// A routine used to iterate through all the entries in the map
        /// 
        public abstract void Iterate(ArrayList list, FrugalMapIterationCallback callback); 

        ///  
        /// Promotes the key/value pairs in the current collection to the next larger 
        /// and more complex storage model.
        ///  
        public abstract void Promote(FrugalMapBase newMap);

        /// 
        /// Size of this data store 
        /// 
        public abstract int Count 
        { 
            get;
        } 

        protected const int INVALIDKEY = 0x7FFFFFFF;

        internal struct Entry 
        {
            public int Key; 
            public Object Value; 
        }
    } 

    /// 
    /// A simple class to handle a single key/value pair
    ///  
    internal sealed class SingleObjectMap : FrugalMapBase
    { 
        public SingleObjectMap() 
        {
            _loneEntry.Key = INVALIDKEY; 
            _loneEntry.Value = DependencyProperty.UnsetValue;
        }

        public override FrugalMapStoreState InsertEntry(int key, Object value) 
        {
            // If we don't have any entries or the existing entry is being overwritten, 
            // then we can use this map.  Otherwise we have to promote. 
            if ((INVALIDKEY == _loneEntry.Key) || (key == _loneEntry.Key))
            { 
                Debug.Assert(INVALIDKEY != key);

                _loneEntry.Key = key;
                _loneEntry.Value = value; 
                return FrugalMapStoreState.Success;
            } 
            else 
            {
                // Entry already used, move to an ThreeObjectMap 
                return FrugalMapStoreState.ThreeObjectMap;
            }
        }
 
        public override void RemoveEntry(int key)
        { 
            // Wipe out the info in the only entry if it matches the key. 
            if (key == _loneEntry.Key)
            { 
                _loneEntry.Key = INVALIDKEY;
                _loneEntry.Value = DependencyProperty.UnsetValue;
            }
        } 

        public override Object Search(int key) 
        { 
            if (key == _loneEntry.Key)
            { 
                return _loneEntry.Value;
            }
            return DependencyProperty.UnsetValue;
        } 

        public override void Sort() 
        { 
            // Single items are already sorted.
        } 

        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (0 == index) 
            {
                value = _loneEntry.Value; 
                key = _loneEntry.Key; 
            }
            else 
            {
                value = DependencyProperty.UnsetValue;
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index"); 
            }
        } 
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        { 
            if (Count == 1)
            {
                callback(list, _loneEntry.Key, _loneEntry.Value);
            } 
        }
 
        public override void Promote(FrugalMapBase newMap) 
        {
            if (FrugalMapStoreState.Success == newMap.InsertEntry(_loneEntry.Key, _loneEntry.Value)) 
            {
            }
            else
            { 
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            } 
        }
 
        // Size of this data store
        public override int Count
        {
            get 
            {
                if (INVALIDKEY != _loneEntry.Key) 
                { 
                    return 1;
                } 
                else
                {
                    return 0;
                } 
            }
        } 
 
        private Entry _loneEntry;
    } 


    /// 
    /// A simple class to handle a single object with 3 key/value pairs.  The pairs are stored unsorted 
    /// and uses a linear search.  Perf analysis showed that this yielded better memory locality and
    /// perf than an object and an array. 
    ///  
    /// 
    /// This map inserts at the last position.  Any time we add to the map we set _sorted to false. If you need 
    /// to iterate through the map in sorted order you must call Sort before using GetKeyValuePair.
    /// 
    internal sealed class ThreeObjectMap : FrugalMapBase
    { 
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        { 
            // Check to see if we are updating an existing entry 
            Debug.Assert(INVALIDKEY != key);
 
            // First check if the key matches the key of one of the existing entries.
            // If it does, overwrite the existing value and return success.
            switch (_count)
            { 
                case 1:
                    if (_entry0.Key == key) 
                    { 
                        _entry0.Value = value;
                        return FrugalMapStoreState.Success; 
                    }
                    break;

                case 2: 
                    if (_entry0.Key == key)
                    { 
                        _entry0.Value = value; 
                        return FrugalMapStoreState.Success;
                    } 
                    if (_entry1.Key == key)
                    {
                        _entry1.Value = value;
                        return FrugalMapStoreState.Success; 
                    }
                    break; 
 
                case 3:
                    if (_entry0.Key == key) 
                    {
                        _entry0.Value = value;
                        return FrugalMapStoreState.Success;
                    } 
                    if (_entry1.Key == key)
                    { 
                        _entry1.Value = value; 
                        return FrugalMapStoreState.Success;
                    } 
                    if (_entry2.Key == key)
                    {
                        _entry2.Value = value;
                        return FrugalMapStoreState.Success; 
                    }
                    break; 
 
                default:
                    break; 
            }

            // If we got past the above switch, that means this key
            // doesn't exist in the map already so we should add it. 
            // Only add it if we're not at the size limit; otherwise
            // we have to promote. 
            if (SIZE > _count) 
            {
                // Space still available to store the value. Insert 
                // into the entry at _count (the next available slot).
                switch (_count)
                {
                    case 0: 
                        _entry0.Key = key;
                        _entry0.Value = value; 
                        _sorted = true; 
                        break;
 
                    case 1:
                        _entry1.Key = key;
                        _entry1.Value = value;
                        // We have added an entry to the array, so we may not be sorted any longer 
                        _sorted = false;
                        break; 
 
                    case 2:
                        _entry2.Key = key; 
                        _entry2.Value = value;
                        // We have added an entry to the array, so we may not be sorted any longer
                        _sorted = false;
                        break; 
                }
                ++_count; 
 
                return FrugalMapStoreState.Success;
            } 
            else
            {
                // Array is full, move to a SixObjectMap
                return FrugalMapStoreState.SixObjectMap; 
            }
        } 
 
        public override void RemoveEntry(int key)
        { 
            // If the key 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.
            switch (_count) 
            {
                case 1: 
                    if (_entry0.Key == key) 
                    {
                        _entry0.Key = INVALIDKEY; 
                        _entry0.Value = DependencyProperty.UnsetValue;
                        --_count;
                        return;
                    } 
                    break;
 
                case 2: 
                    if (_entry0.Key == key)
                    { 
                        _entry0 = _entry1;
                        _entry1.Key = INVALIDKEY;
                        _entry1.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    } 
                    if (_entry1.Key == key) 
                    {
                        _entry1.Key = INVALIDKEY; 
                        _entry1.Value = DependencyProperty.UnsetValue;
                        --_count;
                    }
                    break; 

                case 3: 
                    if (_entry0.Key == key) 
                    {
                        _entry0 = _entry1; 
                        _entry1 = _entry2;
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    } 
                    if (_entry1.Key == key) 
                    {
                        _entry1 = _entry2; 
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break; 
                    }
                    if (_entry2.Key == key) 
                    { 
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break;
                    }
                    break; 

                default: 
                    break; 
            }
        } 

        public override Object Search(int key)
        {
            Debug.Assert(INVALIDKEY != key); 
            if (_count > 0)
            { 
                if (_entry0.Key == key) 
                {
                    return _entry0.Value; 
                }
                if (_count > 1)
                {
                    if (_entry1.Key == key) 
                    {
                        return _entry1.Value; 
                    } 
                    if ((_count > 2) && (_entry2.Key == key))
                    { 
                        return _entry2.Value;
                    }
                }
            } 
            return DependencyProperty.UnsetValue;
        } 
 
        public override void Sort()
        { 
            // If we're unsorted and we have entries to sort, do a simple
            // sort.  Sort the pairs (0,1), (1,2) and then (0,1) again.
            if ((false == _sorted) && (_count > 1))
            { 
                Entry temp;
                if (_entry0.Key > _entry1.Key) 
                { 
                    temp = _entry0;
                    _entry0 = _entry1; 
                    _entry1 = temp;
                }
                if (_count > 2)
                { 
                    if (_entry1.Key > _entry2.Key)
                    { 
                        temp = _entry1; 
                        _entry1 = _entry2;
                        _entry2 = temp; 

                        if (_entry0.Key > _entry1.Key)
                        {
                            temp = _entry0; 
                            _entry0 = _entry1;
                            _entry1 = temp; 
                        } 
                    }
                } 
                _sorted = true;
            }
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        { 
            if (index < _count) 
            {
                switch (index) 
                {
                    case 0:
                        key = _entry0.Key;
                        value = _entry0.Value; 
                        break;
 
                    case 1: 
                        key = _entry1.Key;
                        value = _entry1.Value; 
                        break;

                    case 2:
                        key = _entry2.Key; 
                        value = _entry2.Value;
                        break; 
 
                    default:
                        key = INVALIDKEY; 
                        value = DependencyProperty.UnsetValue;
                        break;
                }
            } 
            else
            { 
                key = INVALIDKEY; 
                value = DependencyProperty.UnsetValue;
                throw new ArgumentOutOfRangeException("index"); 
            }
        }

        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback) 
        {
            if (_count > 0) 
            { 
                if (_count >= 1)
                { 
                    callback(list, _entry0.Key, _entry0.Value);
                }
                if (_count >= 2)
                { 
                    callback(list, _entry1.Key, _entry1.Value);
                } 
                if (_count == 3) 
                {
                    callback(list, _entry2.Key, _entry2.Value); 
                }
            }
        }
 
        public override void Promote(FrugalMapBase newMap)
        { 
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry0.Key, _entry0.Value)) 
            {
                // newMap is smaller than previous map 
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry1.Key, _entry1.Value))
            { 
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            } 
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry2.Key, _entry2.Value))
            { 
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            }
        } 

        // Size of this data store 
        public override int Count 
        {
            get 
            {
                return _count;
            }
        } 

        private const int SIZE = 3; 
 
        // The number of items in the map.
        private UInt16 _count; 

        private bool _sorted;
        private Entry _entry0;
        private Entry _entry1; 
        private Entry _entry2;
    } 
 
    /// 
    /// A simple class to handle a single object with 6 key/value pairs.  The pairs are stored unsorted 
    /// and uses a linear search.  Perf analysis showed that this yielded better memory locality and
    /// perf than an object and an array.
    /// 
    ///  
    /// This map inserts at the last position.  Any time we add to the map we set _sorted to false. If you need
    /// to iterate through the map in sorted order you must call Sort before using GetKeyValuePair. 
    ///  
    internal sealed class SixObjectMap : FrugalMapBase
    { 
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        {
            // Check to see if we are updating an existing entry
            Debug.Assert(INVALIDKEY != key); 

            // First check if the key matches the key of one of the existing entries. 
            // If it does, overwrite the existing value and return success. 
            if (_count > 0)
            { 
                if (_entry0.Key == key)
                {
                    _entry0.Value = value;
                    return FrugalMapStoreState.Success; 
                }
                if (_count > 1) 
                { 
                    if (_entry1.Key == key)
                    { 
                        _entry1.Value = value;
                        return FrugalMapStoreState.Success;
                    }
                    if (_count > 2) 
                    {
                        if (_entry2.Key == key) 
                        { 
                            _entry2.Value = value;
                            return FrugalMapStoreState.Success; 
                        }
                        if (_count > 3)
                        {
                            if (_entry3.Key == key) 
                            {
                                _entry3.Value = value; 
                                return FrugalMapStoreState.Success; 
                            }
                            if (_count > 4) 
                            {
                                if (_entry4.Key == key)
                                {
                                    _entry4.Value = value; 
                                    return FrugalMapStoreState.Success;
                                } 
                                if ((_count > 5) && (_entry5.Key == key)) 
                                {
                                    _entry5.Value = value; 
                                    return FrugalMapStoreState.Success;
                                }
                            }
                        } 
                    }
                } 
            } 

            // If we got past the above switch, that means this key 
            // doesn't exist in the map already so we should add it.
            // Only add it if we're not at the size limit; otherwise
            // we have to promote.
            if (SIZE > _count) 
            {
                // We are adding an entry to the array, so we may not be sorted any longer 
                _sorted = false; 

                // Space still available to store the value. Insert 
                // into the entry at _count (the next available slot).
                switch (_count)
                {
                    case 0: 
                        _entry0.Key = key;
                        _entry0.Value = value; 
 
                        // Single entries are always sorted
                        _sorted = true; 
                        break;

                    case 1:
                        _entry1.Key = key; 
                        _entry1.Value = value;
                        break; 
 
                    case 2:
                        _entry2.Key = key; 
                        _entry2.Value = value;
                        break;

                    case 3: 
                        _entry3.Key = key;
                        _entry3.Value = value; 
                        break; 

                    case 4: 
                        _entry4.Key = key;
                        _entry4.Value = value;
                        break;
 
                    case 5:
                        _entry5.Key = key; 
                        _entry5.Value = value; 
                        break;
                } 
                ++_count;

                return FrugalMapStoreState.Success;
            } 
            else
            { 
                // Array is full, move to a Array 
                return FrugalMapStoreState.Array;
            } 
        }

        public override void RemoveEntry(int key)
        { 
            // If the key 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. 
            switch (_count)
            { 
                case 1:
                    if (_entry0.Key == key)
                    {
                        _entry0.Key = INVALIDKEY; 
                        _entry0.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        return; 
                    }
                    break; 

                case 2:
                    if (_entry0.Key == key)
                    { 
                        _entry0 = _entry1;
                        _entry1.Key = INVALIDKEY; 
                        _entry1.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1.Key = INVALIDKEY; 
                        _entry1.Value = DependencyProperty.UnsetValue;
                        --_count; 
                    } 
                    break;
 
                case 3:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1; 
                        _entry1 = _entry2;
                        _entry2.Key = INVALIDKEY; 
                        _entry2.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    }
                    if (_entry1.Key == key)
                    {
                        _entry1 = _entry2; 
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue; 
                        --_count; 
                        break;
                    } 
                    if (_entry2.Key == key)
                    {
                        _entry2.Key = INVALIDKEY;
                        _entry2.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    } 
                    break;
 
                case 4:
                    if (_entry0.Key == key)
                    {
                        _entry0 = _entry1; 
                        _entry1 = _entry2;
                        _entry2 = _entry3; 
                        _entry3.Key = INVALIDKEY; 
                        _entry3.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    }
                    if (_entry1.Key == key)
                    { 
                        _entry1 = _entry2;
                        _entry2 = _entry3; 
                        _entry3.Key = INVALIDKEY; 
                        _entry3.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    }
                    if (_entry2.Key == key)
                    { 
                        _entry2 = _entry3;
                        _entry3.Key = INVALIDKEY; 
                        _entry3.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    }
                    if (_entry3.Key == key)
                    {
                        _entry3.Key = INVALIDKEY; 
                        _entry3.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break; 
                    }
                    break; 

                case 5:
                    if (_entry0.Key == key)
                    { 
                        _entry0 = _entry1;
                        _entry1 = _entry2; 
                        _entry2 = _entry3; 
                        _entry3 = _entry4;
                        _entry4.Key = INVALIDKEY; 
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    } 
                    if (_entry1.Key == key)
                    { 
                        _entry1 = _entry2; 
                        _entry2 = _entry3;
                        _entry3 = _entry4; 
                        _entry4.Key = INVALIDKEY;
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break; 
                    }
                    if (_entry2.Key == key) 
                    { 
                        _entry2 = _entry3;
                        _entry3 = _entry4; 
                        _entry4.Key = INVALIDKEY;
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break; 
                    }
                    if (_entry3.Key == key) 
                    { 
                        _entry3 = _entry4;
                        _entry4.Key = INVALIDKEY; 
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count;
                        break;
                    } 
                    if (_entry4.Key == key)
                    { 
                        _entry4.Key = INVALIDKEY; 
                        _entry4.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    }
                    break;
 
                case 6:
                    if (_entry0.Key == key) 
                    { 
                        _entry0 = _entry1;
                        _entry1 = _entry2; 
                        _entry2 = _entry3;
                        _entry3 = _entry4;
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break; 
                    }
                    if (_entry1.Key == key) 
                    {
                        _entry1 = _entry2;
                        _entry2 = _entry3;
                        _entry3 = _entry4; 
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    }
                    if (_entry2.Key == key)
                    {
                        _entry2 = _entry3; 
                        _entry3 = _entry4;
                        _entry4 = _entry5; 
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    }
                    if (_entry3.Key == key)
                    { 
                        _entry3 = _entry4;
                        _entry4 = _entry5; 
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break;
                    }
                    if (_entry4.Key == key)
                    { 
                        _entry4 = _entry5;
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue; 
                        --_count;
                        break; 
                    }
                    if (_entry5.Key == key)
                    {
                        _entry5.Key = INVALIDKEY; 
                        _entry5.Value = DependencyProperty.UnsetValue;
                        --_count; 
                        break; 
                    }
                    break; 

                default:
                    break;
            } 
        }
 
        public override Object Search(int key) 
        {
            Debug.Assert(INVALIDKEY != key); 
            if (_count > 0)
            {
                if (_entry0.Key == key)
                { 
                    return _entry0.Value;
                } 
                if (_count > 1) 
                {
                    if (_entry1.Key == key) 
                    {
                        return _entry1.Value;
                    }
                    if (_count > 2) 
                    {
                        if (_entry2.Key == key) 
                        { 
                            return _entry2.Value;
                        } 
                        if (_count > 3)
                        {
                            if (_entry3.Key == key)
                            { 
                                return _entry3.Value;
                            } 
                            if (_count > 4) 
                            {
                                if (_entry4.Key == key) 
                                {
                                    return _entry4.Value;
                                }
                                if ((_count > 5) && (_entry5.Key == key)) 
                                {
                                    return _entry5.Value; 
                                } 
                            }
                        } 
                    }
                }
            }
            return DependencyProperty.UnsetValue; 
        }
 
        public override void Sort() 
        {
            // If we're unsorted and we have entries to sort, do a simple 
            // bubble sort. Sort the pairs, 0..5, and then again until we no
            // longer do any swapping.
            if ((false == _sorted) && (_count > 1))
            { 
                bool swapped;
 
                do 
                {
                    swapped = false; 

                    Entry temp;
                    if (_entry0.Key > _entry1.Key)
                    { 
                        temp = _entry0;
                        _entry0 = _entry1; 
                        _entry1 = temp; 
                        swapped = true;
                    } 
                    if (_count > 2)
                    {
                        if (_entry1.Key > _entry2.Key)
                        { 
                            temp = _entry1;
                            _entry1 = _entry2; 
                            _entry2 = temp; 
                            swapped = true;
                        } 
                        if (_count > 3)
                        {
                            if (_entry2.Key > _entry3.Key)
                            { 
                                temp = _entry2;
                                _entry2 = _entry3; 
                                _entry3 = temp; 
                                swapped = true;
                            } 
                            if (_count > 4)
                            {
                                if (_entry3.Key > _entry4.Key)
                                { 
                                    temp = _entry3;
                                    _entry3 = _entry4; 
                                    _entry4 = temp; 
                                    swapped = true;
                                } 
                                if (_count > 5)
                                {
                                    if (_entry4.Key > _entry5.Key)
                                    { 
                                        temp = _entry4;
                                        _entry4 = _entry5; 
                                        _entry5 = temp; 
                                        swapped = true;
                                    } 
                                }
                            }
                        }
                    } 
                }
                while (swapped); 
                _sorted = true; 
            }
        } 

        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (index < _count) 
            {
                switch (index) 
                { 
                    case 0:
                        key = _entry0.Key; 
                        value = _entry0.Value;
                        break;

                    case 1: 
                        key = _entry1.Key;
                        value = _entry1.Value; 
                        break; 

                    case 2: 
                        key = _entry2.Key;
                        value = _entry2.Value;
                        break;
 
                    case 3:
                        key = _entry3.Key; 
                        value = _entry3.Value; 
                        break;
 
                    case 4:
                        key = _entry4.Key;
                        value = _entry4.Value;
                        break; 

                    case 5: 
                        key = _entry5.Key; 
                        value = _entry5.Value;
                        break; 

                    default:
                        key = INVALIDKEY;
                        value = DependencyProperty.UnsetValue; 
                        break;
                } 
            } 
            else
            { 
                key = INVALIDKEY;
                value = DependencyProperty.UnsetValue;
                throw new ArgumentOutOfRangeException("index");
            } 
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback) 
        {
            if (_count > 0) 
            {
                if (_count >= 1)
                {
                    callback(list, _entry0.Key, _entry0.Value); 
                }
                if (_count >= 2) 
                { 
                    callback(list, _entry1.Key, _entry1.Value);
                } 
                if (_count >= 3)
                {
                    callback(list, _entry2.Key, _entry2.Value);
                } 
                if (_count >= 4)
                { 
                    callback(list, _entry3.Key, _entry3.Value); 
                }
                if (_count >= 5) 
                {
                    callback(list, _entry4.Key, _entry4.Value);
                }
                if (_count == 6) 
                {
                    callback(list, _entry5.Key, _entry5.Value); 
                } 
            }
        } 

        public override void Promote(FrugalMapBase newMap)
        {
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry0.Key, _entry0.Value)) 
            {
                // newMap is smaller than previous map 
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry1.Key, _entry1.Value)) 
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            } 
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry2.Key, _entry2.Value))
            { 
                // newMap is smaller than previous map 
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            } 
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry3.Key, _entry3.Value))
            {
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry4.Key, _entry4.Value)) 
            { 
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            }
            if (FrugalMapStoreState.Success != newMap.InsertEntry(_entry5.Key, _entry5.Value))
            {
                // newMap is smaller than previous map 
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            } 
        } 

        // Size of this data store 
        public override int Count
        {
            get
            { 
                return _count;
            } 
        } 

        private const int SIZE = 6; 

        // The number of items in the map.
        private UInt16 _count;
 
        private bool _sorted;
        private Entry _entry0; 
        private Entry _entry1; 
        private Entry _entry2;
        private Entry _entry3; 
        private Entry _entry4;
        private Entry _entry5;
    }
 
    /// 
    /// A simple class to handle an array of between 6 and 12 key/value pairs.  It is unsorted 
    /// and uses a linear search.  Perf analysis showed that this was the optimal size for both 
    /// memory and perf.  The values may need to be adjusted as the CLR and Avalon evolve.
    ///  
    internal sealed class ArrayObjectMap : FrugalMapBase
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        { 
            // Check to see if we are updating an existing entry
            for (int index = 0; index < _count; ++index) 
            { 
                Debug.Assert(INVALIDKEY != key);
 
                if (_entries[index].Key == key)
                {
                    _entries[index].Value = value;
                    return FrugalMapStoreState.Success; 
                }
            } 
 
            // New key/value pair
            if (MAXSIZE > _count) 
            {
                // Space still available to store the value
                if (null != _entries)
                { 
                    // We are adding an entry to the array, so we may not be sorted any longer
                    _sorted = false; 
 
                    if (_entries.Length > _count)
                    { 
                        // Have empty entries, just set the first available
                    }
                    else
                    { 
                        Entry[] destEntries = new Entry[_entries.Length + GROWTH];
 
                        // Copy old array 
                        Array.Copy(_entries, 0, destEntries, 0, _entries.Length);
                        _entries = destEntries; 
                    }
                }
                else
                { 
                    _entries = new Entry[MINSIZE];
 
                    // No entries, must be sorted 
                    _sorted = true;
                } 

                // Stuff in the new key/value pair
                _entries[_count].Key = key;
                _entries[_count].Value = value; 

                // Bump the count for the entry just added. 
                ++_count; 

                return FrugalMapStoreState.Success; 
            }
            else
            {
                // Array is full, move to a SortedArray 
                return FrugalMapStoreState.SortedArray;
            } 
        } 

        public override void RemoveEntry(int key) 
        {
            for (int index = 0; index < _count; ++index)
            {
                if (_entries[index].Key == key) 
                {
                    // 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].Key = INVALIDKEY;
                    _entries[_count - 1].Value = DependencyProperty.UnsetValue; 
                    --_count; 
                    break;
                } 
            }
        }

        public override Object Search(int key) 
        {
            for (int index = 0; index < _count; ++index) 
            { 
                if (key == _entries[index].Key)
                { 
                    return _entries[index].Value;
                }
            }
            return DependencyProperty.UnsetValue; 
        }
 
        public override void Sort() 
        {
            if ((false == _sorted) && (_count > 1)) 
            {
                QSort(0, (_count - 1));
                _sorted = true;
            } 
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value) 
        {
            if (index < _count) 
            {
                value = _entries[index].Value;
                key = _entries[index].Key;
            } 
            else
            { 
                value = DependencyProperty.UnsetValue; 
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index"); 
            }
        }

        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback) 
        {
            if (_count > 0) 
            { 
                for (int i=0; i< _count; i++)
                { 
                    callback(list, _entries[i].Key, _entries[i].Value);
                }
            }
        } 

        public override void Promote(FrugalMapBase newMap) 
        { 
            for (int index = 0; index < _entries.Length; ++index)
            { 
                if (FrugalMapStoreState.Success == newMap.InsertEntry(_entries[index].Key, _entries[index].Value))
                {
                    continue;
                } 
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap"); 
            } 
        }
 
        // Size of this data store
        public override int Count
        {
            get 
            {
                return _count; 
            } 
        }
 
        // Compare two Entry nodes in the _entries array
        private int Compare(int left, int right)
        {
            return (_entries[left].Key - _entries[right].Key); 
        }
 
        // Partition the _entries array for QuickSort 
        private int Partition(int left, int right)
        { 
            int pivot = right;
            int i = left - 1;
            int j = right;
            Entry temp; 

            for (;;) 
            { 
                while (Compare(++i, pivot) < 0);
                while (Compare(pivot, --j) < 0) 
                {
                    if (j == left)
                    {
                        break; 
                    }
                } 
                if (i >= j) 
                {
                    break; 
                }
                temp = _entries[j];
                _entries[j] = _entries[i];
                _entries[i] = temp; 
            }
            temp = _entries[right]; 
            _entries[right] = _entries[i]; 
            _entries[i] = temp;
            return i; 
        }

        // Sort the _entries array using an index based QuickSort
        private void QSort(int left, int right) 
        {
            if (left < right) 
            { 
                int pivot = Partition(left, right);
                QSort(left, pivot - 1); 
                QSort(pivot + 1, right);
            }
        }
 
        // MINSIZE and GROWTH chosen to minimize memory footprint
        private const int MINSIZE = 9; 
        private const int MAXSIZE = 15; 
        private const int GROWTH = 3;
 
        // The number of items in the map.
        private UInt16 _count;

        private bool _sorted; 
        private Entry[] _entries;
    } 
 
    // A sorted array of key/value pairs. A binary search is used to minimize the cost of insert/search.
 
    internal sealed class SortedObjectMap : FrugalMapBase
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value)
        { 
            bool found;
 
            Debug.Assert(INVALIDKEY != key); 

            // Check to see if we are updating an existing entry 
            int index = FindInsertIndex(key, out found);
            if (found)
            {
                _entries[index].Value = value; 
                return FrugalMapStoreState.Success;
            } 
            else 
            {
                // New key/value pair 
                if (MAXSIZE > _count)
                {
                    // Less than the maximum array size
                    if (null != _entries) 
                    {
                        if (_entries.Length > _count) 
                        { 
                            // Have empty entries, just set the first available
                        } 
                        else
                        {
                            Entry[] destEntries = new Entry[_entries.Length + GROWTH];
 
                            // Copy old array
                            Array.Copy(_entries, 0, destEntries, 0, _entries.Length); 
                            _entries = destEntries; 
                        }
                    } 
                    else
                    {
                        _entries = new Entry[MINSIZE];
                    } 

                    // Inserting into the middle of the existing entries? 
                    if (index < _count) 
                    {
                        // Move higher valued keys to make room for the new key 
                        Array.Copy(_entries, index, _entries, index + 1, (_count - index));
                    }
                    else
                    { 
                        _lastKey = key;
                    } 
 
                    // Stuff in the new key/value pair
                    _entries[index].Key = key; 
                    _entries[index].Value = value;
                    ++_count;
                    return FrugalMapStoreState.Success;
                } 
                else
                { 
                    // SortedArray is full, move to a hashtable 
                    return FrugalMapStoreState.Hashtable;
                } 
            }
        }

        public override void RemoveEntry(int key) 
        {
            bool found; 
 
            Debug.Assert(INVALIDKEY != key);
 
            int index = FindInsertIndex(key, out found);

            if (found)
            { 
                // Shift entries down
                int numToCopy = (_count - index) - 1; 
                if (numToCopy > 0) 
                {
                    Array.Copy(_entries, index + 1, _entries, index, numToCopy); 
                }
                else
                {
                    // If we're not copying anything, then it means we are 
                    //  going to remove the last entry.  Update _lastKey so
                    //  that it reflects the key of the new "last entry" 
                    if( _count > 1 ) 
                    {
                        // Next-to-last entry will be the new last entry 
                        _lastKey = _entries[_count - 2].Key;
                    }
                    else
                    { 
                        // Unless there isn't a next-to-last entry, in which
                        //  case the key is reset to INVALIDKEY. 
                        _lastKey = INVALIDKEY; 
                    }
                } 

                // Wipe out the last entry
                _entries[_count - 1].Key = INVALIDKEY;
                _entries[_count - 1].Value = DependencyProperty.UnsetValue; 

                --_count; 
            } 
        }
 
        public override Object Search(int key)
        {
            bool found;
 
            int index = FindInsertIndex(key, out found);
            if (found) 
            { 
                return _entries[index].Value;
            } 
            return DependencyProperty.UnsetValue;
        }

        public override void Sort() 
        {
            // Always sorted. 
        } 

        public override void GetKeyValuePair(int index, out int key, out Object value) 
        {
            if (index < _count)
            {
                value = _entries[index].Value; 
                key = _entries[index].Key;
            } 
            else 
            {
                value = DependencyProperty.UnsetValue; 
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index");
            }
        } 

        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback) 
        { 
            if (_count > 0)
            { 
                for (int i=0; i< _count; i++)
                {
                    callback(list, _entries[i].Key, _entries[i].Value);
                } 
            }
        } 
 
        public override void Promote(FrugalMapBase newMap)
        { 
            for (int index = 0; index < _entries.Length; ++index)
            {
                if (FrugalMapStoreState.Success == newMap.InsertEntry(_entries[index].Key, _entries[index].Value))
                { 
                    continue;
                } 
                // newMap is smaller than previous map 
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            } 
        }

        private int FindInsertIndex(int key, out bool found)
        { 
            int iLo = 0;
 
            // Only do the binary search if there is a chance of finding the key 
            // This also speeds insertion because we tend to insert at the end.
            if ((_count > 0) && (key <= _lastKey)) 
            {
                // The array index used for insertion is somewhere between 0
                //  and _count-1 inclusive
                int iHi = _count-1; 

                // Do a binary search to find the insertion point 
                do 
                {
                    int iPv = (iHi + iLo) / 2; 
                    if (key <= _entries[iPv].Key)
                    {
                        iHi = iPv;
                    } 
                    else
                    { 
                        iLo = iPv + 1; 
                    }
                } 
                while (iLo < iHi);
                found = (key == _entries[iLo].Key);
            }
            else 
            {
                // Insert point is at the end 
                iLo = _count; 
                found = false;
            } 
            return iLo;
        }

        public override int Count 
        {
            get 
            { 
                return _count;
            } 
        }

        // MINSIZE chosen to be larger than MAXSIZE of the ArrayObjectMap with some extra space for new values
        // The MAXSIZE and GROWTH are chosen to minimize memory usage as we grow the array 
        private const int MINSIZE = 16;
        private const int MAXSIZE = 128; 
        private const int GROWTH = 8; 

        // The number of items in the map. 
        internal int _count;

        private int _lastKey = INVALIDKEY;
        private Entry[] _entries; 
    }
 
    internal sealed class HashObjectMap : FrugalMapBase 
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value) 
        {
            Debug.Assert(INVALIDKEY != key);

            if (null != _entries) 
            {
                // This is done because forward branches 
                // default prediction is not to be taken 
                // making this a CPU win because insert
                // is a common operation. 
            }
            else
            {
                _entries = new Hashtable(MINSIZE); 
            }
 
            _entries[key] = ((value != NullValue) && (value != null)) ? value : NullValue; 
            return FrugalMapStoreState.Success;
        } 

        public override void RemoveEntry(int key)
        {
            _entries.Remove(key); 
        }
 
        public override Object Search(int key) 
        {
            object value = _entries[key]; 

            return ((value != NullValue) && (value != null)) ? value : DependencyProperty.UnsetValue;
        }
 
        public override void Sort()
        { 
            // Always sorted. 
        }
 
        public override void GetKeyValuePair(int index, out int key, out Object value)
        {
            if (index < _entries.Count)
            { 
                IDictionaryEnumerator myEnumerator = _entries.GetEnumerator();
 
                // Move to first valid value 
                myEnumerator.MoveNext();
 
                for (int i = 0; i < index; ++i)
                {
                    myEnumerator.MoveNext();
                } 
                key = (int)myEnumerator.Key;
                if ((myEnumerator.Value != NullValue) && (myEnumerator.Value != null)) 
                { 
                    value = myEnumerator.Value;
                } 
                else
                {
                    value = DependencyProperty.UnsetValue;
                } 
            }
            else 
            { 
                value = DependencyProperty.UnsetValue;
                key = INVALIDKEY; 
                throw new ArgumentOutOfRangeException("index");
            }
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        { 
            IDictionaryEnumerator myEnumerator = _entries.GetEnumerator(); 

            while (myEnumerator.MoveNext()) 
            {
                int key = (int)myEnumerator.Key;
                object value;
                if ((myEnumerator.Value != NullValue) && (myEnumerator.Value != null)) 
                {
                    value = myEnumerator.Value; 
                } 
                else
                { 
                    value = DependencyProperty.UnsetValue;
                }

                callback(list, key, value); 
            }
        } 
 
        public override void Promote(FrugalMapBase newMap)
        { 
            // Should never get here
            throw new InvalidOperationException(SR.Get(SRID.FrugalMap_CannotPromoteBeyondHashtable));
        }
 
        // Size of this data store
        public override int Count 
        { 
            get
            { 
                return _entries.Count;
            }
        }
 
        // 163 is chosen because it is the first prime larger than 128, the MAXSIZE of SortedObjectMap
        internal const int MINSIZE = 163; 
 
        // Hashtable will return null from its indexer if the key is not
        // found OR if the value is null.  To distinguish between these 
        // two cases we insert NullValue instead of null.
        private static object NullValue = new object();

        internal Hashtable _entries; 
    }
 
    [FriendAccessAllowed] 
    internal struct FrugalMap
    { 
        public object this[int key]
        {
            get
            { 
                // If no entry, DependencyProperty.UnsetValue is returned
                if (null != _mapStore) 
                { 
                    return _mapStore.Search(key);
                } 
                return DependencyProperty.UnsetValue;
            }

            set 
            {
                if (value != DependencyProperty.UnsetValue) 
                { 
                    // If not unset value, ensure write success
                    if (null != _mapStore) 
                    {
                        // This is done because forward branches
                        // default prediction is not to be taken
                        // making this a CPU win because set is 
                        // a common operation.
                    } 
                    else 
                    {
                        _mapStore = new SingleObjectMap(); 
                    }

                    FrugalMapStoreState myState = _mapStore.InsertEntry(key, value);
                    if (FrugalMapStoreState.Success == myState) 
                    {
                        return; 
                    } 
                    else
                    { 
                        // Need to move to a more complex storage
                        FrugalMapBase newStore;

                        if (FrugalMapStoreState.ThreeObjectMap == myState) 
                        {
                            newStore = new ThreeObjectMap(); 
                        } 
                        else if (FrugalMapStoreState.SixObjectMap == myState)
                        { 
                            newStore = new SixObjectMap();
                        }
                        else if (FrugalMapStoreState.Array == myState)
                        { 
                            newStore = new ArrayObjectMap();
                        } 
                        else if (FrugalMapStoreState.SortedArray == myState) 
                        {
                            newStore = new SortedObjectMap(); 
                        }
                        else if (FrugalMapStoreState.Hashtable == myState)
                        {
                            newStore = new HashObjectMap(); 
                        }
                        else 
                        { 
                            throw new InvalidOperationException(SR.Get(SRID.FrugalMap_CannotPromoteBeyondHashtable));
                        } 

                        // Extract the values from the old store and insert them into the new store
                        _mapStore.Promote(newStore);
 
                        // Insert the new value
                        _mapStore = newStore; 
                        _mapStore.InsertEntry(key, value); 
                    }
                } 
                else
                {
                    // DependencyProperty.UnsetValue means remove the value
                    if (null != _mapStore) 
                    {
                        _mapStore.RemoveEntry(key); 
                        if (_mapStore.Count == 0) 
                        {
                            // Map Store is now empty ... throw it away 
                            _mapStore = null;
                        }
                    }
                } 
            }
        } 
 
        public void Sort()
        { 
            if (null != _mapStore)
            {
                _mapStore.Sort();
            } 
        }
 
        public void GetKeyValuePair(int index, out int key, out Object value) 
        {
            if (null != _mapStore) 
            {
                _mapStore.GetKeyValuePair(index, out key, out value);
            }
            else 
            {
                throw new ArgumentOutOfRangeException("index"); 
            } 
        }
 
        public void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (null != callback)
            { 
                if (null != list)
                { 
                    if (_mapStore != null) 
                    {
                        _mapStore.Iterate(list, callback); 
                    }
                }
                else
                { 
                    throw new ArgumentNullException("list");
                } 
            } 
            else
            { 
                throw new ArgumentNullException("callback");
            }
        }
 
        public int Count
        { 
            get 
            {
                if (null != _mapStore) 
                {
                    return _mapStore.Count;
                }
                return 0; 
            }
        } 
 
        internal FrugalMapBase _mapStore;
    } 

    // A sorted array of key/value pairs. A binary search is used to minimize the cost of insert/search.

    internal sealed class LargeSortedObjectMap : FrugalMapBase 
    {
        public override FrugalMapStoreState InsertEntry(int key, Object value) 
        { 
            bool found;
 
            Debug.Assert(INVALIDKEY != key);

            // Check to see if we are updating an existing entry
            int index = FindInsertIndex(key, out found); 
            if (found)
            { 
                _entries[index].Value = value; 
                return FrugalMapStoreState.Success;
            } 
            else
            {
                // New key/value pair
                if (null != _entries) 
                {
                    if (_entries.Length > _count) 
                    { 
                        // Have empty entries, just set the first available
                    } 
                    else
                    {
                        int size = _entries.Length;
                        Entry[] destEntries = new Entry[size + (size >> 1)]; 

                        // Copy old array 
                        Array.Copy(_entries, 0, destEntries, 0, _entries.Length); 
                        _entries = destEntries;
                    } 
                }
                else
                {
                    _entries = new Entry[MINSIZE]; 
                }
 
                // Inserting into the middle of the existing entries? 
                if (index < _count)
                { 
                    // Move higher valued keys to make room for the new key
                    Array.Copy(_entries, index, _entries, index + 1, (_count - index));
                }
                else 
                {
                    _lastKey = key; 
                } 

                // Stuff in the new key/value pair 
                _entries[index].Key = key;
                _entries[index].Value = value;
                ++_count;
                return FrugalMapStoreState.Success; 
            }
        } 
 
        public override void RemoveEntry(int key)
        { 
            bool found;

            Debug.Assert(INVALIDKEY != key);
 
            int index = FindInsertIndex(key, out found);
 
            if (found) 
            {
                // Shift entries down 
                int numToCopy = (_count - index) - 1;
                if (numToCopy > 0)
                {
                    Array.Copy(_entries, index + 1, _entries, index, numToCopy); 
                }
                else 
                { 
                    // If we're not copying anything, then it means we are
                    //  going to remove the last entry.  Update _lastKey so 
                    //  that it reflects the key of the new "last entry"
                    if( _count > 1 )
                    {
                        // Next-to-last entry will be the new last entry 
                        _lastKey = _entries[_count - 2].Key;
                    } 
                    else 
                    {
                        // Unless there isn't a next-to-last entry, in which 
                        //  case the key is reset to INVALIDKEY.
                        _lastKey = INVALIDKEY;
                    }
                } 

                // Wipe out the last entry 
                _entries[_count - 1].Key = INVALIDKEY; 
                _entries[_count - 1].Value = DependencyProperty.UnsetValue;
 
                --_count;
            }
        }
 
        public override Object Search(int key)
        { 
            bool found; 

            int index = FindInsertIndex(key, out found); 
            if (found)
            {
                return _entries[index].Value;
            } 
            return DependencyProperty.UnsetValue;
        } 
 
        public override void Sort()
        { 
            // Always sorted.
        }

        public override void GetKeyValuePair(int index, out int key, out Object value) 
        {
            if (index < _count) 
            { 
                value = _entries[index].Value;
                key = _entries[index].Key; 
            }
            else
            {
                value = DependencyProperty.UnsetValue; 
                key = INVALIDKEY;
                throw new ArgumentOutOfRangeException("index"); 
            } 
        }
 
        public override void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        {
            if (_count > 0)
            { 
                for (int i=0; i< _count; i++)
                { 
                    callback(list, _entries[i].Key, _entries[i].Value); 
                }
            } 
        }

        public override void Promote(FrugalMapBase newMap)
        { 
            for (int index = 0; index < _entries.Length; ++index)
            { 
                if (FrugalMapStoreState.Success == newMap.InsertEntry(_entries[index].Key, _entries[index].Value)) 
                {
                    continue; 
                }
                // newMap is smaller than previous map
                throw new ArgumentException(SR.Get(SRID.FrugalMap_TargetMapCannotHoldAllData, this.ToString(), newMap.ToString()), "newMap");
            } 
        }
 
        private int FindInsertIndex(int key, out bool found) 
        {
            int iLo = 0; 

            // Only do the binary search if there is a chance of finding the key
            // This also speeds insertion because we tend to insert at the end.
            if ((_count > 0) && (key <= _lastKey)) 
            {
                // The array index used for insertion is somewhere between 0 
                //  and _count-1 inclusive 
                int iHi = _count-1;
 
                // Do a binary search to find the insertion point
                do
                {
                    int iPv = (iHi + iLo) / 2; 
                    if (key <= _entries[iPv].Key)
                    { 
                        iHi = iPv; 
                    }
                    else 
                    {
                        iLo = iPv + 1;
                    }
                } 
                while (iLo < iHi);
                found = (key == _entries[iLo].Key); 
            } 
            else
            { 
                // Insert point is at the end
                iLo = _count;
                found = false;
            } 
            return iLo;
        } 
 
        public override int Count
        { 
            get
            {
                return _count;
            } 
        }
 
        // MINSIZE chosen to be small, growth rate of 1.5 is slow at small sizes, but increasingly agressive as 
        // the array grows
        private const int MINSIZE = 2; 

        // The number of items in the map.
        internal int _count;
 
        private int _lastKey = INVALIDKEY;
        private Entry[] _entries; 
    } 

    // This is a variant of FrugalMap that always uses an array as the underlying store. 
    // This avoids the virtual method calls that are present when the store morphs through
    // the size efficient store classes normally used. It is appropriate only when we know the
    // store will always be populated and individual elements will be accessed in a tight loop.
    internal struct InsertionSortMap 
    {
        public object this[int key] 
        { 
            get
            { 
                // If no entry, DependencyProperty.UnsetValue is returned
                if (null != _mapStore)
                {
                    return _mapStore.Search(key); 
                }
                return DependencyProperty.UnsetValue; 
            } 

            set 
            {
                if (value != DependencyProperty.UnsetValue)
                {
                    // If not unset value, ensure write success 
                    if (null != _mapStore)
                    { 
                        // This is done because forward branches 
                        // default prediction is not to be taken
                        // making this a CPU win because set is 
                        // a common operation.
                    }
                    else
                    { 
                        _mapStore = new LargeSortedObjectMap();
                    } 
 
                    FrugalMapStoreState myState = _mapStore.InsertEntry(key, value);
                    if (FrugalMapStoreState.Success == myState) 
                    {
                        return;
                    }
                    else 
                    {
                        // Need to move to a more complex storage 
                        LargeSortedObjectMap newStore; 

                        if (FrugalMapStoreState.SortedArray == myState) 
                        {
                            newStore = new LargeSortedObjectMap();
                        }
                        else 
                        {
                            throw new InvalidOperationException(SR.Get(SRID.FrugalMap_CannotPromoteBeyondHashtable)); 
                        } 

                        // Extract the values from the old store and insert them into the new store 
                        _mapStore.Promote(newStore);

                        // Insert the new value
                        _mapStore = newStore; 
                        _mapStore.InsertEntry(key, value);
                    } 
                } 
                else
                { 
                    // DependencyProperty.UnsetValue means remove the value
                    if (null != _mapStore)
                    {
                        _mapStore.RemoveEntry(key); 
                        if (_mapStore.Count == 0)
                        { 
                            // Map Store is now empty ... throw it away 
                            _mapStore = null;
                        } 
                    }
                }
            }
        } 

        public void Sort() 
        { 
            if (null != _mapStore)
            { 
                _mapStore.Sort();
            }
        }
 
        public void GetKeyValuePair(int index, out int key, out Object value)
        { 
            if (null != _mapStore) 
            {
                _mapStore.GetKeyValuePair(index, out key, out value); 
            }
            else
            {
                throw new ArgumentOutOfRangeException("index"); 
            }
        } 
 
        public void Iterate(ArrayList list, FrugalMapIterationCallback callback)
        { 
            if (null != callback)
            {
                if (null != list)
                { 
                    if (_mapStore != null)
                    { 
                        _mapStore.Iterate(list, callback); 
                    }
                } 
                else
                {
                    throw new ArgumentNullException("list");
                } 
            }
            else 
            { 
                throw new ArgumentNullException("callback");
            } 
        }

        public int Count
        { 
            get
            { 
                if (null != _mapStore) 
                {
                    return _mapStore.Count; 
                }
                return 0;
            }
        } 

        internal LargeSortedObjectMap _mapStore; 
    } 

    ///  
    ///     FrugalMapIterationCallback
    /// 
    internal delegate void FrugalMapIterationCallback(ArrayList list, int key, object value);
} 


// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK