ItemMap.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / wpf / src / Shared / MS / Utility / ItemMap.cs / 1305600 / ItemMap.cs

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

namespace MS.Utility 
{
    // 
    // ItemStructMap 
    //
 
    // Disable warnings about fields never being assigned to
    // This struct is designed to function with its fields starting at
    // their default values and without the need of surfacing a constructor
    // other than the deafult 
    #pragma warning disable 649
 
    internal struct ItemStructMap 
    {
        public int EnsureEntry(int key) 
        {
            int index = Search(key);
            if (index < 0)
            { 
                // Not found, add Entry
 
                // Create initial capacity, if necessary 
                if (Entries == null)
                { 
                    Entries = new Entry[SearchTypeThreshold];
                }

                // Convert not-found index to insertion point 
                index = ~index;
 
                Entry[] destEntries = Entries; 

                // Increase capacity, if necessary 
                if ((Count + 1) > Entries.Length)
                {
                    destEntries = new Entry[Entries.Length * 2];
 
                    // Initialize start of new array
                    Array.Copy(Entries, 0, destEntries, 0, index); 
                } 

                // Shift entries to make room for new key at provided insertion point 
                Array.Copy(Entries, index, destEntries, index + 1, Count - index);

                // Ensure Source and Destination arrays are the same
                Entries = destEntries; 

                // Clear new entry 
                Entries[index] = EmptyEntry; 

                // Set 
                Entries[index].Key = key;

                Count++;
            } 

            return index; 
        } 

        public int Search(int key) 
        {
            int keyPv = Int32.MaxValue;
            int iPv = 0;
 
            // Use fastest search based on size
            if (Count > SearchTypeThreshold) 
            { 
                // Binary Search
                int iLo = 0; 
                int iHi = Count - 1;

                while (iLo <= iHi)
                { 
                    iPv = (iHi + iLo) / 2;
                    keyPv = Entries[iPv].Key; 
 
                    if (key == keyPv)
                    { 
                        return iPv;
                    }

                    if (key < keyPv) 
                    {
                        iHi = iPv - 1; 
                    } 
                    else
                    { 
                        iLo = iPv + 1;
                    }
                }
            } 
            else
            { 
                // Linear search 

                for (int i = 0; i < Count; i++) 
                {
                    iPv = i;
                    keyPv = Entries[iPv].Key;
 
                    if (key == keyPv)
                    { 
                        return iPv; 
                    }
 
                    if (key < keyPv)
                    {
                        break;
                    } 
                }
            } 
 
            // iPv and keyPv will match and have the last pivot check
 
            // Return a negative value whose bitwise compliment
            // is this index of the first Entry that is greater
            // than the key passed in (sorted insertion point)
 
            if (key > keyPv)
            { 
                iPv++; 
            }
 

            return ~iPv;
        }
 
        private const int SearchTypeThreshold = 4;
 
        public Entry[] Entries; 
        public int Count;
 
        public struct Entry
        {
            public int Key;
            public T Value; 
        }
 
        private static Entry EmptyEntry; 
    }
 
    #pragma warning restore 649
}

 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.
using System; 
using System.Collections;
using System.Diagnostics;

namespace MS.Utility 
{
    // 
    // ItemStructMap 
    //
 
    // Disable warnings about fields never being assigned to
    // This struct is designed to function with its fields starting at
    // their default values and without the need of surfacing a constructor
    // other than the deafult 
    #pragma warning disable 649
 
    internal struct ItemStructMap 
    {
        public int EnsureEntry(int key) 
        {
            int index = Search(key);
            if (index < 0)
            { 
                // Not found, add Entry
 
                // Create initial capacity, if necessary 
                if (Entries == null)
                { 
                    Entries = new Entry[SearchTypeThreshold];
                }

                // Convert not-found index to insertion point 
                index = ~index;
 
                Entry[] destEntries = Entries; 

                // Increase capacity, if necessary 
                if ((Count + 1) > Entries.Length)
                {
                    destEntries = new Entry[Entries.Length * 2];
 
                    // Initialize start of new array
                    Array.Copy(Entries, 0, destEntries, 0, index); 
                } 

                // Shift entries to make room for new key at provided insertion point 
                Array.Copy(Entries, index, destEntries, index + 1, Count - index);

                // Ensure Source and Destination arrays are the same
                Entries = destEntries; 

                // Clear new entry 
                Entries[index] = EmptyEntry; 

                // Set 
                Entries[index].Key = key;

                Count++;
            } 

            return index; 
        } 

        public int Search(int key) 
        {
            int keyPv = Int32.MaxValue;
            int iPv = 0;
 
            // Use fastest search based on size
            if (Count > SearchTypeThreshold) 
            { 
                // Binary Search
                int iLo = 0; 
                int iHi = Count - 1;

                while (iLo <= iHi)
                { 
                    iPv = (iHi + iLo) / 2;
                    keyPv = Entries[iPv].Key; 
 
                    if (key == keyPv)
                    { 
                        return iPv;
                    }

                    if (key < keyPv) 
                    {
                        iHi = iPv - 1; 
                    } 
                    else
                    { 
                        iLo = iPv + 1;
                    }
                }
            } 
            else
            { 
                // Linear search 

                for (int i = 0; i < Count; i++) 
                {
                    iPv = i;
                    keyPv = Entries[iPv].Key;
 
                    if (key == keyPv)
                    { 
                        return iPv; 
                    }
 
                    if (key < keyPv)
                    {
                        break;
                    } 
                }
            } 
 
            // iPv and keyPv will match and have the last pivot check
 
            // Return a negative value whose bitwise compliment
            // is this index of the first Entry that is greater
            // than the key passed in (sorted insertion point)
 
            if (key > keyPv)
            { 
                iPv++; 
            }
 

            return ~iPv;
        }
 
        private const int SearchTypeThreshold = 4;
 
        public Entry[] Entries; 
        public int Count;
 
        public struct Entry
        {
            public int Key;
            public T Value; 
        }
 
        private static Entry EmptyEntry; 
    }
 
    #pragma warning restore 649
}

 

// 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