dxtmpl.h

希望我上传的这些东西可以对搞编程的程序员有点小小的帮助！谢谢！

    {
        _ASSERT( pOldNode == m_pNodeTail );
        m_pNodeTail = pNewNode;
    }
    pOldNode->pNext = pNewNode;
    return (DXLISTPOS) pNewNode;
}

template<class TYPE, class ARG_TYPE>
void CDXList<TYPE, ARG_TYPE>::RemoveAt(DXLISTPOS position)
{
    DXASSERT_VALID( this );

    CNode* pOldNode = (CNode*) position;
    _ASSERT( DXIsValidAddress(pOldNode, sizeof(CNode), TRUE ) );

    // remove pOldNode from list
    if (pOldNode == m_pNodeHead)
    {
        m_pNodeHead = pOldNode->pNext;
    }
    else
    {
        _ASSERT( DXIsValidAddress(pOldNode->pPrev, sizeof(CNode), TRUE ) );
        pOldNode->pPrev->pNext = pOldNode->pNext;
    }
    if (pOldNode == m_pNodeTail)
    {
        m_pNodeTail = pOldNode->pPrev;
    }
    else
    {
        _ASSERT( DXIsValidAddress(pOldNode->pNext, sizeof(CNode), TRUE ) );
        pOldNode->pNext->pPrev = pOldNode->pPrev;
    }
    FreeNode(pOldNode);
}

template<class TYPE, class ARG_TYPE>
DXLISTPOS CDXList<TYPE, ARG_TYPE>::FindIndex(int nIndex) const
{
    DXASSERT_VALID( this );
    _ASSERT( nIndex >= 0 );

    if (nIndex >= m_nCount)
        return NULL;  // went too far

    CNode* pNode = m_pNodeHead;
    while (nIndex--)
    {
        _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ));
        pNode = pNode->pNext;
    }
    return (DXLISTPOS) pNode;
}

template<class TYPE, class ARG_TYPE>
DXLISTPOS CDXList<TYPE, ARG_TYPE>::Find(ARG_TYPE searchValue, DXLISTPOS startAfter) const
{
    DXASSERT_VALID( this );

    CNode* pNode = (CNode*) startAfter;
    if (pNode == NULL)
    {
        pNode = m_pNodeHead;  // start at head
    }
    else
    {
        _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ) );
        pNode = pNode->pNext;  // start after the one specified
    }

    for (; pNode != NULL; pNode = pNode->pNext)
        if (DXCompareElements(&pNode->data, &searchValue))
            return (DXLISTPOS)pNode;
    return NULL;
}

#ifdef _DEBUG
template<class TYPE, class ARG_TYPE>
void CDXList<TYPE, ARG_TYPE>::AssertValid() const
{
    if (m_nCount == 0)
    {
        // empty list
        _ASSERT( m_pNodeHead == NULL );
        _ASSERT( m_pNodeTail == NULL );
    }
    else
    {
        // non-empty list
        _ASSERT( DXIsValidAddress(m_pNodeHead, sizeof(CNode), TRUE ));
        _ASSERT( DXIsValidAddress(m_pNodeTail, sizeof(CNode), TRUE ));
    }
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
class CDXMap
{
protected:
    // Association
    struct CAssoc
    {
        CAssoc* pNext;
        UINT nHashValue;  // needed for efficient iteration
        KEY key;
        VALUE value;
    };
public:
// Construction
    CDXMap( int nBlockSize = 10 );

// Attributes
    // number of elements
    int GetCount() const;
    BOOL IsEmpty() const;

    // Lookup
    BOOL Lookup(ARG_KEY key, VALUE& rValue) const;

// Operations
    // Lookup and add if not there
    VALUE& operator[](ARG_KEY key);

    // add a new (key, value) pair
    void SetAt(ARG_KEY key, ARG_VALUE newValue);

    // removing existing (key, ?) pair
    BOOL RemoveKey(ARG_KEY key);
    void RemoveAll();

    // iterating all (key, value) pairs
    DXLISTPOS GetStartPosition() const;
    void GetNextAssoc(DXLISTPOS& rNextPosition, KEY& rKey, VALUE& rValue) const;

    // advanced features for derived classes
    UINT GetHashTableSize() const;
    void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);

// Implementation
protected:
    CAssoc** m_pHashTable;
    UINT m_nHashTableSize;
    int m_nCount;
    CAssoc* m_pFreeList;
    struct CDXPlex* m_pBlocks;
    int m_nBlockSize;

    CAssoc* NewAssoc();
    void FreeAssoc(CAssoc*);
    CAssoc* GetAssocAt(ARG_KEY, UINT&) const;

public:
    ~CDXMap();
#ifdef _DEBUG
//  void Dump(CDumpContext&) const;
    void AssertValid() const;
#endif
};

/////////////////////////////////////////////////////////////////////////////
// CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE> inline functions

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline int CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetCount() const
    { return m_nCount; }
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline BOOL CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::IsEmpty() const
    { return m_nCount == 0; }
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::SetAt(ARG_KEY key, ARG_VALUE newValue)
    { (*this)[key] = newValue; }
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline DXLISTPOS CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetStartPosition() const
    { return (m_nCount == 0) ? NULL : DX_BEFORE_START_POSITION; }
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline UINT CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetHashTableSize() const
    { return m_nHashTableSize; }

/////////////////////////////////////////////////////////////////////////////
// CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE> out-of-line functions

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CDXMap( int nBlockSize )
{
    _ASSERT( nBlockSize > 0 );

    m_pHashTable = NULL;
    m_nHashTableSize = 17;  // default size
    m_nCount = 0;
    m_pFreeList = NULL;
    m_pBlocks = NULL;
    m_nBlockSize = nBlockSize;
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::InitHashTable(
    UINT nHashSize, BOOL bAllocNow)
//
// Used to force allocation of a hash table or to override the default
//   hash table size of (which is fairly small)
{
    DXASSERT_VALID( this );
    _ASSERT( m_nCount == 0 );
    _ASSERT( nHashSize > 0 );

    if (m_pHashTable != NULL)
    {
        // free hash table
        delete[] m_pHashTable;
        m_pHashTable = NULL;
    }

    if (bAllocNow)
    {
        m_pHashTable = new CAssoc* [nHashSize];
        memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
    }
    m_nHashTableSize = nHashSize;
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveAll()
{
    DXASSERT_VALID( this );

    if (m_pHashTable != NULL)
    {
        // destroy elements (values and keys)
        for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
        {
            CAssoc* pAssoc;
            for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
              pAssoc = pAssoc->pNext)
            {
                DXDestructElements(&pAssoc->value, 1);
                DXDestructElements(&pAssoc->key, 1);
            }
        }
    }

    // free hash table
    delete[] m_pHashTable;
    m_pHashTable = NULL;

    m_nCount = 0;
    m_pFreeList = NULL;
    m_pBlocks->FreeDataChain();
    m_pBlocks = NULL;
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::~CDXMap()
{
    RemoveAll();
    _ASSERT( m_nCount == 0 );
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::NewAssoc()
{
    if (m_pFreeList == NULL)
    {
        // add another block
        CDXPlex* newBlock = CDXPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CDXMap::CAssoc));
        // chain them into free list
        CDXMap::CAssoc* pAssoc = (CDXMap::CAssoc*) newBlock->data();
        // free in reverse order to make it easier to debug
        pAssoc += m_nBlockSize - 1;
        for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--)
        {
            pAssoc->pNext = m_pFreeList;
            m_pFreeList = pAssoc;
        }
    }
    _ASSERT( m_pFreeList != NULL );  // we must have something

    CDXMap::CAssoc* pAssoc = m_pFreeList;
    m_pFreeList = m_pFreeList->pNext;
    m_nCount++;
    _ASSERT( m_nCount > 0 );  // make sure we don't overflow
    DXConstructElements(&pAssoc->key, 1);
    DXConstructElements(&pAssoc->value, 1);   // special construct values
    return pAssoc;
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::FreeAssoc(CDXMap::CAssoc* pAssoc)
{
    DXDestructElements(&pAssoc->value, 1);
    DXDestructElements(&pAssoc->key, 1);
    pAssoc->pNext = m_pFreeList;
    m_pFreeList = pAssoc;
    m_nCount--;
    _ASSERT( m_nCount >= 0 );  // make sure we don't underflow
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAssocAt(ARG_KEY key, UINT& nHash) const
// find association (or return NULL)
{
    nHash = DXHashKey(key) % m_nHashTableSize;

    if (m_pHashTable == NULL)
        return NULL;

    // see if it exists
    CAssoc* pAssoc;
    for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
    {
        if (DXCompareElements(&pAssoc->key, &key))
            return pAssoc;
    }
    return NULL;
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup(ARG_KEY key, VALUE& rValue) const
{
    DXASSERT_VALID( this );

    UINT nHash;
    CAssoc* pAssoc = GetAssocAt(key, nHash);
    if (pAssoc == NULL)
        return FALSE;  // not in map

    rValue = pAssoc->value;
    return TRUE;
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
VALUE& CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::operator[](ARG_KEY key)
{
    DXASSERT_VALID( this );

    UINT nHash;
    CAssoc* pAssoc;
    if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
    {
        if (m_pHashTable == NULL)
            InitHashTable(m_nHashTableSize);

        // it doesn't exist, add a new Association
        pAssoc = NewAssoc();
        pAssoc->nHashValue = nHash;
        pAssoc->key = key;
        // 'pAssoc->value' is a constructed object, nothing more

        // put into hash table
        pAssoc->pNext = m_pHashTable[nHash];
        m_pHashTable[nHash] = pAssoc;
    }
    return pAssoc->value;  // return new reference
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveKey(ARG_KEY key)
// remove key - return TRUE if removed
{
    DXASSERT_VALID( this );

    if (m_pHashTable == NULL)
        return FALSE;  // nothing in the table

    CAssoc** ppAssocPrev;
    ppAssocPrev = &m_pHashTable[DXHashKey(key) % m_nHashTableSize];

    CAssoc* pAssoc;
    for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
    {
        if (DXCompareElements(&pAssoc->key, &key))
        {
            // remove it
            *ppAssocPrev = pAssoc->pNext;  // remove from list
            FreeAssoc(pAssoc);
            return TRUE;
        }
        ppAssocPrev = &pAssoc->pNext;
    }
    return FALSE;  // not found
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetNextAssoc(DXLISTPOS& rNextPosition,
    KEY& rKey, VALUE& rValue) const
{
    DXASSERT_VALID( this );
    _ASSERT( m_pHashTable != NULL );  // never call on empty map

    CAssoc* pAssocRet = (CAssoc*)rNextPosition;
    _ASSERT( pAssocRet != NULL );

    if (pAssocRet == (CAssoc*) DX_BEFORE_START_POSITION)
    {
        // find the first association
        for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
            if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
                break;
        _ASSERT( pAssocRet != NULL );  // must find something
    }

    // find next association
    _ASSERT( DXIsValidAddress(pAssocRet, sizeof(CAssoc), TRUE ));
    CAssoc* pAssocNext;
    if ((pAssocNext = pAssocRet->pNext) == NULL)
    {
        // go to next bucket
        for (UINT nBucket = pAssocRet->nHashValue + 1;
          nBucket < m_nHashTableSize; nBucket++)
            if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
                break;
    }

    rNextPosition = (DXLISTPOS) pAssocNext;

    // fill in return data
    rKey = pAssocRet->key;
    rValue = pAssocRet->value;
}

#ifdef _DEBUG
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::AssertValid() const
{
    _ASSERT( m_nHashTableSize > 0 );
    _ASSERT( (m_nCount == 0 || m_pHashTable != NULL) );
        // non-empty map should have hash table
}
#endif //_DEBUG

#pragma option pop /*P_O_Pop*/
#endif //--- This must be the last line in the file