稀疏数组实现（2008.12.10最新修改）

利用Windows SDK提供的虚存技术和SEH实现的稀疏数组。
类SparseArray是在《Windows核心编程（第5版）》P678页上的VMArray基础上修改而得，并提供了线程安全特性。

/**
* SparseArray.h
* @Author   Tu Yongce
* @Created  2008-11-27
* @Modified 2008-12-10
* @Version  0.2
* @Note: SparseArray类是在《Windows核心编程（第5版）》P678页上的VMArray基础上修改而得
*/

#ifndef SPARSE_ARRAY_H_INCLUDED
#define SPARSE_ARRAY_H_INCLUDED

#ifdef _MSC_VER
#pragma once
#endif

#include
#include
#include
#include "Noncopyable.h"
#include "LightWeightLock.h"

/**
* 稀疏数组，利用虚拟内存和SEH实现
* Note: 该类是线程安全的，但最好在构造第一个SparseArray对象之前（一般在主线程中进行）调用类的
*           静态函数EnsureThreadSecurity来确保内部锁被构造；
*           如果不调用，则在极小概率下可能会出现线程不安全问题，详见EnsureThreadSecurity函数说明
*/
template
class SparseArray: private Noncopyable
{
private:
    // 前一个未处理异常过滤函数指针
    static PTOP_LEVEL_EXCEPTION_FILTER sm_preFilter;

    static SparseArray *sm_head;    // SparseArray对象链表头指针
    SparseArray *m_next;            // 下一个SparseArray对象指针

    ElemType *m_array;    // 稀疏数组
    SIZE_T m_reserved;    // 数组预订区域大小（字节）

    // 获取用于在多线程中进行数据保护的锁
    static LightWeightLock& GetLock();

public:
    // 确保SparseArray类的线程安全
    static void EnsureThreadSecurity();

public:
    /**
    * 构造稀疏数组
    * @param size: 数组大小（元素个数）
    * @param failedThrow: 如果为true，则构造函数会在预定区域失败时抛出异常；
    *                                       否则需要用户自己检测SparseArray对象是否为NULL（是否失败）
    */
    explicit SparseArray(SIZE_T size, BOOL failedThrow = false);
    virtual ~SparseArray();

    // 使SparseArray可以像普通数组一样使用
    operator ElemType* ();
    operator const ElemType* () const;

    // SparseArray对象的异常过滤函数
    LONG ExceptionFilter(PEXCEPTION_POINTERS pep,
        BOOL bRetryUntilSuccessful = FALSE);

protected:
    // 访问异常的默认处理函数（派生类可重载此函数）
    virtual LONG OnAccessViolation(PVOID addr, BOOL read,
        PEXCEPTION_POINTERS pep, BOOL retryUntilSuccessful);

private:
    // SparseArray类的未处理异常过滤函数
    static LONG WINAPI MyUnhandledExceptionFilter(PEXCEPTION_POINTERS pep);
};

template
PTOP_LEVEL_EXCEPTION_FILTER SparseArray::sm_preFilter = NULL;

template
SparseArray* SparseArray::sm_head = NULL;

template
LightWeightLock& SparseArray::GetLock()
{
    // 用于在多线程中进行数据保护的锁
    static LightWeightLock lock;
    return lock;
}

/**
* 确保SparseArray类的线程安全
* 在构造SparseArray类对象之前，最好先调用此函数对类的内部锁进行构造（一般在主线程中进行）
* @Note: 如果不调用此函数，则在第一次构造SparseArray对象时可能出现线程安全问题（极小概率）：
*               如果此时有多个SparseArray对象被同时构造，那么有可能内部锁在构造好之前被使用或被多次构造
*               但如果已经有SparseArray对象被成功构造后，则不再会有线程安全问题
* @Note: 不需要调用此函数的情况：
*              （1）有非局部静态对象的SparseArray静态对象（此时内部锁会被正确构造）
*              （2）能够确保第一个SparseArray对象被正确构造
*/
template
void SparseArray::EnsureThreadSecurity()
{
    // 保证内部锁被构造
    GetLock();
}

/**
* 构造稀疏数组
* @param size: 数组大小（元素个数）
* @param failedThrow: 如果为true，则构造函数会在预定区域失败时抛出异常；
*                                       否则需要用户自己检测SparseArray对象是否为NULL（是否失败）
*/
template
SparseArray::SparseArray(SIZE_T size, BOOL failedThrow)
{
    // 预订一块虚拟内存区域
    m_reserved = sizeof(ElemType) * size;
    m_array = (ElemType*) ::VirtualAlloc(NULL, m_reserved,
        MEM_RESERVE | MEM_TOP_DOWN, PAGE_READWRITE);

    if (m_array == NULL) {
        // 预订区域失败
        if (failedThrow)
            throw std::bad_alloc("SparseArray failed to reserve the virtual memory");
        return ;
    }

    // 把该SparseArray对象加入到链表中
    GetLock().Lock();  // 互斥访问SparseArray对象链表
    if (sm_head == NULL) {
        // 设置SparseArray使用的未处理异常过滤函数
        sm_preFilter = ::SetUnhandledExceptionFilter(MyUnhandledExceptionFilter);
    }
    m_next = sm_head;
    sm_head = this;
    GetLock().Unlock();
}

template
SparseArray::~SparseArray()
{
    if (m_array == NULL) {
        // 构造时没有成功预订区域
        return;
    }

    // 释放预订的虚拟内存区域
    ::VirtualFree(m_array, 0, MEM_RELEASE);

    // 从链表中移除该SparseArray对象
    GetLock().Lock();  // 互斥访问SparseArray对象链表
    SparseArray *p = sm_head;
    if (p == this) {
        sm_head = p->m_next;
    } else {
        for (; p->m_next != NULL; p = p->m_next) {
            if (p->m_next == this) {
                p->m_next = p->m_next->m_next;
                break;
            }
        }
    }
    GetLock().Unlock();
}

template
SparseArray::operator ElemType* ()
{
    return m_array;
}

template
SparseArray::operator const ElemType* () const
{
    return m_array;
}

// SparseArray类的未处理异常过滤函数
template
LONG WINAPI SparseArray::MyUnhandledExceptionFilter(PEXCEPTION_POINTERS pep)
{
    // 只处理访问异常
    if (pep->ExceptionRecord->ExceptionCode != EXCEPTION_ACCESS_VIOLATION)
        return EXCEPTION_CONTINUE_SEARCH;

    // 遍历SparseArray对象链表，尝试用每一个SparseArray对象来处理访问异常
    GetLock().Lock();  // 互斥访问SparseArray对象链表
    for (SparseArray* p = sm_head; p != NULL; p = p->m_next) {
        LONG retCode = p->ExceptionFilter(pep, TRUE);
        if (retCode != EXCEPTION_CONTINUE_SEARCH) {
            // 当前SparseArray对象对访问异常进行了处理
            return retCode;
        }
    }
    GetLock().Unlock();

    // 没有SparseArray对象对此访问异常进行处理，尝试用先前的未处理异常过滤程序
    return sm_preFilter(pep);
}

// SparseArray对象的异常过滤函数
template
LONG SparseArray::ExceptionFilter(PEXCEPTION_POINTERS pep, BOOL retry)
{
    // 只处理访问异常
    if (pep->ExceptionRecord->ExceptionCode != EXCEPTION_ACCESS_VIOLATION)
        return EXCEPTION_CONTINUE_SEARCH;

    // 获得访问异常发生位置和是否为“读”操作
    PVOID addr = (PVOID) pep->ExceptionRecord->ExceptionInformation[1];
    BOOL read = (pep->ExceptionRecord->ExceptionInformation[0] == 0);

    // 如果发生非法访问的内存地址在数组范围内，则尝试对其进行处理
    LONG retCode = EXCEPTION_CONTINUE_SEARCH;

    if (m_array <= addr && addr < (PBYTE)m_array + m_reserved) {
        retCode = OnAccessViolation(addr, read, pep, retry);
    }

    return retCode;
}

// 访问异常的默认处理函数（派生类可重载此函数）
template
LONG SparseArray::OnAccessViolation(PVOID addr, BOOL /*read*/,
                                              PEXCEPTION_POINTERS /*pep*/, BOOL retry)
{
    BOOL ok;
    do {
        // 尝试调拨内存
        ok = (::VirtualAlloc(addr, sizeof(ElemType), MEM_COMMIT,
            PAGE_READWRITE) != NULL);

        // 如果调拨内存失败且需要重试，则显示对话框提示用户释放内存
        if (!ok && retry) {
            ::MessageBox(NULL,
                _T("Please close some other applications and Press OK."),
                _T("Insufficient Memory Available"),
                MB_ICONWARNING | MB_OK);
        }
    } while (!ok && retry);

    // 如果内存调拨成功，则回到发生访问异常的地方重新执行；
    // 否则，返回EXCEPTION_EXECUTE_HANDLER让异常处理程序得到以执行
    return (ok ? EXCEPTION_CONTINUE_EXECUTION : EXCEPTION_EXECUTE_HANDLER);
}

#endif // SPARSE_ARRAY_H_INCLUDED

/**
* LightWeightLock.h
* @Author   Tu Yongce
* @Created  2008-11-28
* @Modified 2008-11-28
* @Version  0.1
*/

#ifndef LIGHT_WEIGHT_LOCK_H_INCLUDED
#define LIGHT_WEIGHT_LOCK_H_INCLUDED

#ifdef _MSC_VER
#pragma once
#endif

#include
#include "Noncopyable.h"

// 轻量级互斥锁（功能等同于MFC中的CCriticalSection）
class LightWeightLock: private Noncopyable
{
private:
    CRITICAL_SECTION m_cs;

public:
    LightWeightLock()
    {
        ::InitializeCriticalSection(&m_cs);
    }

    ~LightWeightLock()
    {
        ::DeleteCriticalSection(&m_cs);
    }

    void Lock()
    {
        ::EnterCriticalSection(&m_cs);
    }

    void Unlock()
    {
        ::LeaveCriticalSection(&m_cs);
    }
};

#endif // LIGHT_WEIGHT_LOCK_H_INCLUDED