SecondaryIndex.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ WCF / WCF / 3.5.30729.1 / untmp / Orcas / SP / ndp / cdf / src / WCF / infocard / Service / managed / Microsoft / InfoCards / SecondaryIndex.cs / 1 / SecondaryIndex.cs

                            //------------------------------------------------------------------------------ 
// Copyright (c) Microsoft Corporation.  All rights reserved.
//-----------------------------------------------------------------------------
namespace Microsoft.InfoCards
{ 
    using System;
    using System.Collections; 
    using System.Collections.Generic; 
    using System.Runtime.InteropServices;
    using IDT = Microsoft.InfoCards.Diagnostics.InfoCardTrace; 


    //
    // Summary: 
    //  Manages data, sorting, and searching of an index buffer
    // 
    // Remarks: 
    //  This class if for internal file store use only.
    // 
    internal unsafe class SecondaryIndex
    {
        byte[] m_buffer;
        Int32 m_lastIndex; 
        IComparer m_searchComparer;
        IComparer m_sortComparer; 
        SecondaryIndexDefinition m_definition; 
        bool m_isOpen;
 

        //
        // Summary:
        //  Creates an instance of a SecondaryIndex 
        //
        // Remarks: 
        //  The sort and search comparers are very tightly bound, the sort 
        //  must be at least equiviant to search, but may also be more restrictive.
        // 
        //  See SecondaryIndexList::SearchComparer and SecondaryIndexList::SortComparer for examples.
        //
        // Parameters:
        //  definition:     the definition to draw rules from 
        //  search:         The IComparer to use for search routines.
        //  sort:           The IComparer to use for sort routines. 
        // 
        public SecondaryIndex( SecondaryIndexDefinition definition, IComparer search, IComparer sort )
        { 
            if( null == definition )
            {
                throw IDT.ThrowHelperArgumentNull( "definition" );
            } 
            if( null == search )
            { 
                throw IDT.ThrowHelperArgumentNull( "search" ); 
            }
            if( null == sort ) 
            {
                throw IDT.ThrowHelperArgumentNull( "sort" );
            }
 
            m_definition = definition;
            m_searchComparer = search; 
            m_sortComparer = sort; 
            Clear( );
            m_isOpen = true; 
        }

        //
        // Summary: 
        //  Gets the definition this index uses for its rules.
        // 
        public SecondaryIndexDefinition Definition 
        {
            get 
            {
                ThrowIfNotOpen( );
                return m_definition;
            } 
        }
 
        // 
        // Summary:
        //  Gets the last used index in the buffer. 
        //
        public Int32 LastIndex
        {
            get 
            {
                ThrowIfNotOpen( ); 
                return m_lastIndex; 
            }
        } 

        //
        // Summary:
        //  Gets the Raw buffer. 
        //
        public byte[] GetBuffer() 
        { 
            ThrowIfNotOpen( );
            return m_buffer; 
        }


        // 
        // Summary:
        //  Runs through the index values, and writes the new values 
        //      for the object. 
        //
        // Remarks: 
        //  if remove is true, all values with the specified localId will be removed
        //      When performing a multi-pass index set, only use true on the first call.
        //
        // Parameters: 
        //  id:             The localId you wish set values for
        //  indexBuffer:    The buffer to draw the values from. 
        //  remove:         bool to remove all existing values before inserting the new ones. 
        //
        internal void SetValuesForId( Int32 id,  DataRowIndexBuffer indexBuffer, bool remove ) 
        {
            ThrowIfNotOpen( );

            if( id <= 0 ) 
            {
                throw IDT.ThrowHelperError( new ArgumentOutOfRangeException( 
                                        "id", 
                                        SR.GetString( SR.StoreLocalIdOutOfRange ) ) );
            } 

            IndexObject[] objects = indexBuffer[ m_definition.Name ].ToArray();

            if( remove ) 
            {
                RemoveForIdAndShiftData( id ); 
            } 

            if( null == objects || 0 == objects.Length ) 
            {
                return;
            }
 
            for( int i=0;i list = new List(); 
            fixed( byte* pIndexBuffer = &m_buffer[ 0 ] )
            { 
                SecondaryIndexItem* pIndex = (SecondaryIndexItem*)pIndexBuffer;

                //
                // Loop through all of the index entries 
                //
                for( int i = 0; i < m_lastIndex + 1; i++ ) 
                { 
                    //
                    // If the index entry if for the passed in localID 
                    //    copy it to a temp buffer and save it off
                    //
                    if( pIndex[ i ].LocalId == id )
                    { 
                        byte[] entry = new byte[ SecondaryIndexItem.HashValueSize ];
 
                        Marshal.Copy( 
                                    (IntPtr)(&pIndex[ i ].HashValue),
                                    entry, 
                                    0,
                                    SecondaryIndexItem.HashValueSize );

                        list.Add( new IndexObject( entry ) ); 
                    }
                } 
 
                //
                // If we have found values, copy tose values 
                //      to the input buffer
                //
                if( list.Count > 0 )
                { 
                    buffer.SetIndexValues( m_definition.Name, list.ToArray() );
                } 
            } 

        } 

        //
        // Summary:
        //  Release and close all internal resources currently in use. 
        //
        public void Close() 
        { 
            if( m_isOpen )
            { 
                //
                // Our buffers contain sensitive information,
                // and becuase this is a managed buffer, it destruction
                // is non-deterministic.  We must clear this buffer before 
                // we close out to ensure that all sesnitive data is erased.
                // 
                Clear( ); 
                m_buffer = null;
                m_isOpen = false; 
            }
        }

 

        // 
        // Summary: 
        //  Validates a buffer that contains a single index value against the specifications
        //  in the SecondaryIndexDefinition. 
        //
        //  Only validation that does not require data scans is done here.
        //
        // Remarks: 
        //  Currently, only NULL checks are done, unique checks are done at insert time.
        // 
        // Parameters: 
        //  indexValue:     The indexValue to test.
        // 
        public void ValidateIndexValue( byte[] indexValue )
        {
            if( SecondaryIndexSettings.Nullable != ( m_definition.Settings & SecondaryIndexSettings.Nullable ) )
            { 
                if( IsBufferEmpty( indexValue ) )
                { 
                    throw IDT.ThrowHelperError( new InvalidOperationException( 
                                    SR.GetString( SR.StoreNullIndexValueNotPermitted, m_definition.Name ) ) );
                } 
            }
        }

 
        //
        // Summary: 
        //  Initialize this instance with new information. 
        //
        // Parameters: 
        //  buffer:         the index buffer to use.
        //  lastIndex:      the last used index in the buffer.
        //
        public void SetBuffer( byte[] buffer, Int32 lastIndex ) 
        {
            ThrowIfNotOpen( ); 
 
            m_buffer = buffer;
            m_lastIndex = lastIndex; 


        }
 
        //
        // Summary: 
        //  Get all matching localIds using the IndexObject as the criteria. 
        //
        // Remarks: 
        //  low and high can be used to create index ranges, and to increase the search speed.
        //      When performing a "loop" of matches, if the list you are matching sorted, you
        //      can prime the low/high with the last match found to speed searches.
        // 
        // Paramters:
        //  obj:            IndexObject to use as the search data. 
        //  collection:     location to store all the matches 
        //  low:            The start to use for the local index buffer.
        //  high:           The end to use for the local index buffer. 
        //
        public int Match( IndexObject obj, LocalIdCollection collection, Int32 low, Int32 high )
        {
            if( null == obj ) 
            {
                throw IDT.ThrowHelperArgumentNull( "obj" ); 
            } 
            if( null == collection )
            { 
                throw IDT.ThrowHelperArgumentNull( "collection" );
            }
            if( (UInt32)low > (UInt32)high )
            { 
                throw IDT.ThrowHelperError( new ArgumentOutOfRangeException(
                                    "low", 
                                    low, 
                                    SR.GetString( SR.StoreLowValueOutOfRange ) ) );
            } 
            if( (UInt32)high > (UInt32)m_lastIndex )
            {
                throw IDT.ThrowHelperError( new ArgumentOutOfRangeException(
                                "high", 
                                high,
                                 SR.GetString( SR.StoreHighValueOutOfRange ) ) ); 
            } 

 
            if( !obj.IsCompiled )
            {
                if( !obj.CanCompile )
                { 
                    throw IDT.ThrowHelperError( new InvalidOperationException(
                                    SR.GetString( SR.StoreIndexObjectCanNotBeCompiled ) ) ); 
                } 

                obj.Compile( m_definition ); 
            }


            ValidateIndexValue( obj.CompiledForm ); 

            SecondaryIndexItem indexItem; 
 
            Marshal.Copy( obj.CompiledForm, 0, (IntPtr)(&indexItem.HashValue), SecondaryIndexItem.HashValueSize );
 
            return Match( &indexItem, collection, low, high );

        }
 

        // 
        // Summary: 
        //  Clear the current data and reset the lastIndex
        // 
        public void Clear()
        {
            m_buffer = new byte[ sizeof( SecondaryIndexItem ) * m_definition.InitialSize ];
            m_lastIndex = -1; 
        }
 
 
        //
        // Summary: 
        //  Remove all data for a given LocalId, and compact all unused space.
        //
        // Remarks:
        // 
        // Parameters:
        //  id:         LocalId to clear all data for. 
        // 
        void RemoveForIdAndShiftData( Int32 id )
        { 

            if( -1 == m_lastIndex )
            {
                // 
                // If the list is empty, just return.
                // 
                return; 
            }
 
            Int32 count = m_lastIndex + 1;
            Int32 currentOffset = 0;
            Int32 index = 0;
 
            fixed( byte* pIndexBuffer = &m_buffer[ 0 ] )
            { 
                SecondaryIndexItem* pIndex = (SecondaryIndexItem*)pIndexBuffer; 

 
                do
                {
                    IDT.Assert(
                            (UInt32)currentOffset < (UInt32)m_buffer.Length , 
                            "currentOffset is invalid or has been corrupted.");
 
                    IDT.Assert( 
                            0 == ( currentOffset % sizeof( SecondaryIndexItem ) ),
                            "currentOffset is not aligned proppertly.  This can cause data corruption." ); 

                    IDT.Assert(
                            ( ( &pIndex[ index ] ) - pIndex ) <= count * sizeof( SecondaryIndexItem ),
                            "Current IndexPointer has walked beyond the total count of valid data."); 

                    // 
                    // Get the current index. 
                    //
                    index = currentOffset / sizeof( SecondaryIndexItem ); 

                    IDT.Assert(
                            ( ( &pIndex[ index ] ) - pIndex ) < m_buffer.Length,
                             "Current IndexPointer has walked beyond the allocated buffer"); 

                    // 
                    // If the current SecondaryIndexItem::get_LocalId matches 
                    //
                    if( pIndex[ index ].LocalId == id ) 
                    {


                        // 
                        // if not the last item in the list, we need to copy the trailing data.
                        // 
                        if( count != (index + 1 ) ) 
                        {
 
                            IDT.Assert(
                                    m_lastIndex >= 0,
                                    "LastIndex indicates an invalid state for the index" );
 
                            //
                            // Shift the from the next spot to the end down one slot 
                            // 
                            Array.Copy(
                                    m_buffer, 
                                    currentOffset + sizeof( SecondaryIndexItem ),
                                    m_buffer,
                                    currentOffset,
                                    ( count - ( index + 1 ) ) * sizeof( SecondaryIndexItem ) ); 

                            // 
                            // Clear the last slot. 
                            //
                            Array.Clear( m_buffer, m_lastIndex * sizeof( SecondaryIndexItem ), sizeof( SecondaryIndexItem ) ); 

                        }
                        else
                        { 
                            //
                            // just clear this slot, it is the last slot in the index, 
                            //  and is a match. 
                            //
                           Array.Clear( m_buffer, currentOffset, sizeof( SecondaryIndexItem ) ); 

                        }

                        // 
                        // decrement the counters.
                        // 
                        m_lastIndex--; 
                        count--;
                    } 
                    else
                    {
                        //
                        // This is not a match, so move the current offet to the next item. 
                        //
                        currentOffset += sizeof( SecondaryIndexItem ); 
                    } 

                } while( currentOffset / sizeof( SecondaryIndexItem ) < count ); 
            }
        }

        // 
        // Summary:
        //  Makes room, and writes the given value and id to the correct slot 
        // 
        // Remarks:
        //  indexValue.Length must equal SecondaryIndexItem.HashValueSize 
        //
        // Parameters:
        //  id:         The localId this value maps to.
        //  indexValue: The raw compiled index value to be written. 
        //
        void ShiftAndInsertValues( Int32 id,  byte[] indexValue ) 
        { 
            IDT.Assert(
                    id > 0, 
                    "Invalid LocalId" );
            IDT.Assert(
                    null != indexValue,
                    "Null indev value passed" ); 
            IDT.Assert(
                    indexValue.Length  ==  SecondaryIndexItem.HashValueSize, 
                    "Index buffer is not correct size."); 

            SecondaryIndexItem item; 

            item.LocalId = id;
            Marshal.Copy( indexValue, 0, (IntPtr)(&item.HashValue), SecondaryIndexItem.HashValueSize );
 
            AddItem( &item );
        } 
 
        //
        // Summary: 
        //  Loops through the hash value, and checks to ensure that it is not NULL (all zeros).
        //
        static bool IsBufferEmpty( byte[] hash )
        { 
            for( int i = 0; i < hash.Length; i++ )
            { 
                if( hash[ i ] != 0 ) 
                {
                    return false; 
                }
            }
            return true;
        } 

 
        // 
        // Summary:
        //  Internal BinarySearch that will ENSURE that the index returned is the first 
        //      instance in the list.
        //
        // Remarks:
        // 
        //
        // Parameters: 
        //  pMatch:         a pointer to a item to use for the match. 
        //  comp:           the comparer to use when searching
        //  lowStart:       The low range of the search. 
        //  highStart:      The high range of the search.
        //
        // Returns:
        //  if the value was found, the index of the first matching entry. 
        //  if not found, the compliment of the location where it can be found.
        // 
        int BSearch( SecondaryIndexItem* pMatch, IComparer comp, int lowStart, int highStart ) 
        {
            int high, i, low, res; 

            low = lowStart;
            high = highStart;
 
            fixed( byte* pIndexBuffer = &m_buffer[ 0 ] )
            { 
                SecondaryIndexItem* pIndex = (SecondaryIndexItem*)pIndexBuffer; 

                while( low <= high ) 
                {
                    i = ( high + low ) / 2;

                    res = comp.Compare( (IntPtr)pMatch, (IntPtr)(&pIndex[ i ]) ); 
                    if( 0 == res )
                    { 
                        high = i; 
                        if( high == low )
                        { 
                            return high;
                        }
                    }
                    else if( res < 0 ) 
                    {
                        high = i - 1; 
                    } 
                    else
                    { 
                        low = i + 1;
                    }
                }
 
            }
 
            // 
            // low now contains the place where the value should be placed.
            // ~ this value to  indicate that the item was not present, but 
            // still provide the location to the caller.  They simple need to
            // un-complement the value to get the result.
            //
            return ~low; 
        }
 
 

 
        //
        // Summary:
        //  Performs a binary search, and gathers all matching values for a given index value.
        // 
        // Remarks:
        // 
        // 
        // Parameters:
        //  pMatch:     item to match 
        //  resutls:    location to add results too
        //  lowStart:   The low range of the search.
        //  highStart:  The high range of the search.
        // 
        // Returns:
        //      Index of last matching item in the list. 
        //      if value is less than 0, the compliment of the value 
        //      will be the location to insert the value.
        // 
        int Match( SecondaryIndexItem* pMatch, LocalIdCollection results, int lowStart, int highStart )
        {
            int index = BSearch( pMatch, m_searchComparer, lowStart, highStart );
            if( index >= 0 ) 
            {
                fixed( byte* pIndexBuffer = &m_buffer[ 0 ] ) 
                { 
                    //
                    // Cast the pinned buffer to an index ptr (used as array) 
                    //
                    SecondaryIndexItem* pIndex = (SecondaryIndexItem*)pIndexBuffer;

                    IDT.Assert( 
                        index * sizeof( SecondaryIndexItem ) < m_buffer.Length,
                        "Index has moved beyond the allocated buffer." 
                    ); 

                    // 
                    // since the index will point to the first match
                    // and there could be multiples, we willl loop through
                    // untill we don't find a match.
                    // 

                    do 
                    { 

                        results.Add( pIndex[ index ].LocalId ); 
                        index++;

                    } while(    index <= m_lastIndex
                                && 0 == m_searchComparer.Compare( (IntPtr)(&pIndex[ index ]) , (IntPtr)pMatch  ) ); 

 
                } 

                // 
                // index must point to the last matching value,
                // which is now 1 behind the index value.
                //
                index = index - 1; 
            }
 
 
            return index;
        } 

        //
        // Summary:
        //  Finds the slot for an item, then makes room for that item, and copies 
        //  the data from the specified pointer to that slot.
        // 
        // Parameters: 
        //  pMatch:         A pointer to the data to copy into the index.
        // 
        void AddItem( SecondaryIndexItem* pMatch )
        {
            Int32 index = 0;
 
            IDT.Assert(
                null != pMatch, 
                "Match pointer is null"); 

            IDT.Assert( 
                pMatch->LocalId > 0,
                "Match pointer has invalid local id" );

            if( SecondaryIndexSettings.Unique == ( m_definition.Settings & SecondaryIndexSettings.Unique ) ) 
            {
                // 
                // If unique, we will use the exact same comparer we use for searching. 
                //
                index = BSearch( pMatch, m_searchComparer, 0, m_lastIndex ); 

                if( index >= 0 )
                {
                    throw IDT.ThrowHelperError( new InvalidOperationException( 
                                    SR.GetString( SR.StoreUniqueIndexConstraintBroken,m_definition.Name ) ) );
                } 
            } 
            else
            { 
                //
                // Use the normal sort comparer.
                //
                index = BSearch( pMatch, m_sortComparer, 0, m_lastIndex); 
            }
 
            if( index >= 0 ) 
            {
                // 
                // We found an exact match, so just bail, we have
                // no need to add the item.
                //
                return; 
            }
 
            index = ~index; 

            // 
            // If we are not already at the end of the list.
            //
            Int32 count = m_lastIndex + 1;
            Int32 totalCount = m_buffer.Length / sizeof( SecondaryIndexItem ); 

            // 
            // Check to see if the index 
            // is above the last used index
            // 
            //
            // do we need to grow to fit the new item.
            //
            if( ( count + 1 ) >= totalCount ) 
            {
                GrowIndex( ); 
            } 

            if( index < count ) 
            {
                Int32 totalBytesUsed    = count * sizeof( SecondaryIndexItem );
                Int32 byteOffset        = index * sizeof( SecondaryIndexItem );
                Int32 newByteOffset     = byteOffset + sizeof( SecondaryIndexItem ); 
                Int32 bytesToCopy       = totalBytesUsed - byteOffset;
 
                IDT.Assert( 
                    bytesToCopy > 0,
                    "No Bytes to copy into index."); 

                Array.Copy( m_buffer, byteOffset, m_buffer, newByteOffset, bytesToCopy );
            }
            fixed( byte* pIndexBuffer = &m_buffer[ 0 ] ) 
            {
 
                SecondaryIndexItem* pIndex = (SecondaryIndexItem*)pIndexBuffer; 
                //
                //copy the value 
                //
                IDT.Assert(
                        ( ( &pIndex[ index ] ) - pIndex ) < m_buffer.Length,
                        "IndexPointer is beyond the end of the allocated buffer" ); 

                pIndex[ index ] = *pMatch; 
            } 
            //
            // Increment the index value 
            //
            m_lastIndex++;

        } 

 
 
        //
        // Summary: 
        //  Grows the index by +-20%
        //
        void GrowIndex()
        { 
            //
            // add 20% then round up to correct size 
            // 
            int newSize = Utility.CalculateIncreaseByPercent(
                m_buffer.Length, 
                sizeof( SecondaryIndexItem ),
                5 );

            IDT.Assert( 
                    newSize > m_buffer.Length &&
                    0 == ( newSize % sizeof( SecondaryIndexItem ) ), 
                    "New size calculated for index is invalid." ); 

            int byteCount = ( m_lastIndex + 1 ) * sizeof( SecondaryIndexItem ); 

            byte[] newBuffer = new byte[ newSize ];
            Array.Copy( m_buffer, 0, newBuffer, 0, byteCount );
            Array.Clear( m_buffer, 0, byteCount ); 
            m_buffer = newBuffer;
        } 
 
        void ThrowIfNotOpen()
        { 
            if( !m_isOpen )
            {
                throw IDT.ThrowHelperError( new ObjectDisposedException( "SecondaryIndex" ) );
            } 
        }
    } 
} 

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