//
// FILE: SparseArray.h
//
// Copyright (c) 1997 by Aaron Michael Cohen and Mike Woodring
//
/////////////////////////////////////////////////////////////////////////

#ifndef __SPARSEARRAY_H__
#define __SPARSEARRAY_H__

#include <windows.h>
#include <stdio.h>

// CSparseArray
//
// A template class that implements an array.  The class
// parameter T specifies the type of the object that will
// be stored in each element of the array.  This implementation
// is geared for arrays that will be very large, but sparsely
// populated.  This allows efficient array indexing operations
// to be used without committing large amounts of virtual memory
// unless actually needed.
//
// Note - this implementation requires that class T provide
// an assignment operator.
//
template <class T>
class CSparseArray
{
    private:
        enum ACCESS_TYPE { READING, WRITING };

    public:
        // The constructor will reserve virtual address space
        // for the array.  An instance of the UndefinedElement 
        // parameter will be returned by the GetAt operation
        // if it's called before the page of memory containing
        // the requested index has not been committed.
        //
        CSparseArray( long lNumElements, T UndefinedElement )
        {
            // Figure out how big a page is on this platform.
            //
            SYSTEM_INFO SystemInfo;

            GetSystemInfo(&SystemInfo);
            m_dwPageSize = SystemInfo.dwPageSize;

            // Reserve a range of addresses for the array without comitting
            // any memory or paging file to back it.
            //
            m_pElements = (T *)
                VirtualAlloc(
                    NULL,
                    sizeof(T) * lNumElements,
                    MEM_RESERVE,
                    PAGE_READWRITE
                );

            // For listing brevity, we'll assume the above
            // allocation never fails.

            m_UndefinedElement  = UndefinedElement;
            m_lNumElements      = lNumElements;
            m_lCommittedPages   = 0;

            printf(
                "Array address space reserved for %d elements (%d pages)\n",
                lNumElements,
                (m_lNumElements * sizeof(T)) / m_dwPageSize
            );
        }
        
        ~CSparseArray()
        {
            if( m_pElements )
            {
                // Free the array storage back to the OS.
                //
                VirtualFree(
                    m_pElements,
                    sizeof(T) * m_lNumElements,
                    MEM_RELEASE
                );

                printf(
                    "Maximum pages = %d, committed pages = %d\n",
                    (sizeof(T) * m_lNumElements) / m_dwPageSize,
                    m_lCommittedPages
                );
            }
        }

        // GetAt
        //
        // Retrieves an element from the array at index lIndex.  If
        // the page of memory that would contain the element at
        // the given index has not been committed yet, this operation
        // returns an instance of the "undefined element" specified
        // in the class constructor.
        //
        T GetAt( long lIndex )
        {
            __try {
                return(m_pElements[lIndex]);
            }
            __except( ExceptionFilter(READING, GetExceptionInformation(), m_UndefinedElement) ) {
                printf(
                    "Access made to out of bounds or uncommitted element %d (last index = %d)\n",
                    lIndex,
                    m_lNumElements - 1
                );

                return(m_UndefinedElement);
            }
        }

        // Writes the given object to the array at the specified
        // index.  If the page of memory that contains that element
        // has not been committed, it will be.
        //
        void SetAt( long lIndex, T rhs )
        {
            __try {
                m_pElements[lIndex] = rhs;
            }
            __except( ExceptionFilter(WRITING, GetExceptionInformation(), rhs) ) {
                printf(
                    "Access made out of bounds to element %d (last index = %d)\n",
                    lIndex,
                    m_lNumElements - 1
                );
            }
        }

    private:
        int CSparseArray::ExceptionFilter
        (
            ACCESS_TYPE             AccessType,
            LPEXCEPTION_POINTERS    pExceptionPtrs,
            T&                      Object
        )
        {
            if( EXCEPTION_ACCESS_VIOLATION == pExceptionPtrs->ExceptionRecord->ExceptionCode )
            {
                DWORD dwAddressOfAccess;
                DWORD dwAddressOfFirstElement;
                DWORD dwAddressOfLastElement;

                dwAddressOfAccess = pExceptionPtrs->ExceptionRecord->ExceptionInformation[1];
                dwAddressOfFirstElement = (DWORD)m_pElements;
                dwAddressOfLastElement = dwAddressOfFirstElement + (sizeof(T) * (m_lNumElements - 1));

                if( WRITING == AccessType )
                {
                    // The following little print out exists to show what's
                    // being written into the array - for demonstration
                    // purposes only.
                    //
                    if( sizeof(T) == sizeof(BYTE) )
                    {
                        long lElementIndex = (dwAddressOfAccess - dwAddressOfFirstElement) / sizeof(T);
                        long lPageNum = (dwAddressOfAccess - dwAddressOfFirstElement) / m_dwPageSize;

                        printf(
                            "Writing %c to uncommitted page at index %d (page %d).\n",
                            (BYTE)Object,
                            lElementIndex,
                            lPageNum
                        );
                    }
                
                    if(
                        (dwAddressOfFirstElement <= dwAddressOfAccess) &&
                        (dwAddressOfAccess <= dwAddressOfLastElement)
                    )
                    {
                        printf("Committing page now.\n");

                        // An access is being made to an element within the array
                        // that hasn't been committed yet.  Commit the page containing
                        // that element and resume execution.
                        //
                        VirtualAlloc(
                            (PVOID)dwAddressOfAccess,
                            sizeof(T),
                            MEM_COMMIT,
                            PAGE_READWRITE
                        );

                        m_lCommittedPages++;
                        return(EXCEPTION_CONTINUE_EXECUTION);
                    }
                    else
                    {
                        printf("Write is out of bounds.\n");
                    }
                }
                else
                {
                    if(
                        (dwAddressOfFirstElement <= dwAddressOfAccess) &&
                        (dwAddressOfAccess <= dwAddressOfLastElement)
                    )
                    {
                        // A read operation was performed.
                        printf("Read attempted from uncomitted page.\n");
                    }
                    else
                    {
                        printf("Read attempted out of bounds.\n");
                    }
                }
            }

            // If we make it here, we couldn't handle the exception
            // gracefully.
            //
            return(EXCEPTION_EXECUTE_HANDLER);
        }

    private:
        DWORD   m_dwPageSize;
        T      *m_pElements;
        T       m_UndefinedElement;
        long    m_lNumElements;
        long    m_lCommittedPages;
};

#endif // __SPARSEARRAY_H__