spcollec.h

TTS语音开发示例

        pOldNode->pNext = pNewNode;
    }
    return (SPLISTPOS) pNewNode;
}

template<class TYPE, class ARG_TYPE>
void CSPList<TYPE, ARG_TYPE>::RemoveAt(SPLISTPOS position)
{
    SPASSERT_VALID( this );

    CNode* pOldNode = (CNode*) position;
    SPDBG_ASSERT( SPIsValidAddress(pOldNode, sizeof(CNode), TRUE ) );

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

template<class TYPE, class ARG_TYPE>
SPLISTPOS CSPList<TYPE, ARG_TYPE>::FindIndex(int nIndex) const
{
    SPASSERT_VALID( this );
    SPDBG_ASSERT( nIndex >= 0 );

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

    CNode* pNode = m_pNodeHead;
    while (nIndex--)
    {
        SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ));
        pNode = pNode->pNext;
    }
    return (SPLISTPOS) pNode;
}

template<class TYPE, class ARG_TYPE>
SPLISTPOS CSPList<TYPE, ARG_TYPE>::Find(ARG_TYPE searchValue, SPLISTPOS startAfter) const
{
    SPASSERT_VALID( this );

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

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

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

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

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
class CSPMap
{
protected:
    // Association
    struct CAssoc
    {
        CAssoc* pNext;
        UINT nHashValue;  // needed for efficient iteration
        KEY key;
        VALUE value;
    };
public:
// Construction
    CSPMap( 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
    SPLISTPOS GetStartPosition() const;
    void GetNextAssoc(SPLISTPOS& rNextPosition, KEY& rKey, VALUE& rValue) const;

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

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

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

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

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

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline int CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetCount() const
    { return m_nCount; }
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline BOOL CSPMap<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 CSPMap<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 SPLISTPOS CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetStartPosition() const
    { return (m_nCount == 0) ? NULL : SP_BEFORE_START_POSITION; }
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline UINT CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetHashTableSize() const
    { return m_nHashTableSize; }

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

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CSPMap( int nBlockSize )
{
    SPDBG_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>
HRESULT CSPMap<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)
{
    SPASSERT_VALID( this );
    SPDBG_ASSERT( m_nCount == 0 );
    SPDBG_ASSERT( nHashSize > 0 );
    HRESULT hr = S_OK;

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

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

    m_nHashTableSize = ( SUCCEEDED( hr ) )?(nHashSize):(0);
    return hr;
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveAll()
{
    SPASSERT_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)
            {
                SPDestructElements(&pAssoc->value, 1);
                SPDestructElements(&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>
CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::~CSPMap()
{
    RemoveAll();
    SPDBG_ASSERT( m_nCount == 0 );
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::NewAssoc()
{
    if (m_pFreeList == NULL)
    {
        // add another block
        CSPPlex* newBlock = CSPPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CSPMap::CAssoc));

        if( newBlock )
        {
            // chain them into free list
            CSPMap::CAssoc* pAssoc = (CSPMap::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;
            }
        }
    }

    CSPMap::CAssoc* pAssoc = m_pFreeList;
    if( pAssoc )
    {
        if( SUCCEEDED( SPConstructElements(&pAssoc->key, 1   ) ) )
        {
            if( SUCCEEDED( SPConstructElements(&pAssoc->value, 1 ) ) )
            {
                m_pFreeList = m_pFreeList->pNext;
                m_nCount++;
                SPDBG_ASSERT( m_nCount > 0 );  // make sure we don't overflow
            }
            else
            {
                SPDestructElements( &pAssoc->key, 1 );
            }
        }
        else
        {
            pAssoc = NULL;
        }
    }
    return pAssoc;
}

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

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAssocAt(ARG_KEY key, UINT& nHash) const
// find association (or return NULL)
{
    nHash = SPHashKey(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 (SPCompareElements(&pAssoc->key, &key))
            return pAssoc;
    }
    return NULL;
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup(ARG_KEY key, VALUE& rValue) const
{
    SPASSERT_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& CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::operator[](ARG_KEY key)
{
    SPASSERT_VALID( this );
    HRESULT hr = S_OK;
    static const CAssoc ErrAssoc = 0;

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

        if( SUCCEEDED( hr ) )
        {
            // it doesn't exist, add a new Association
            pAssoc = NewAssoc();
            if( pAssoc )
            {
                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;
            }
            else
            {
                pAssoc = &ErrAssoc;
            }
        }
    }
    return pAssoc->value;  // return new reference
}

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

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

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

    CAssoc* pAssoc;
    for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
    {
        if (SPCompareElements(&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 CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetNextAssoc(SPLISTPOS& rNextPosition,
    KEY& rKey, VALUE& rValue) const
{
    SPASSERT_VALID( this );
    SPDBG_ASSERT( m_pHashTable != NULL );  // never call on empty map

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

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

    // find next association
    SPDBG_ASSERT( SPIsValidAddress(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 = (SPLISTPOS) 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 CSPMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::AssertValid() const
{
    SPDBG_ASSERT( m_nHashTableSize > 0 );
    SPDBG_ASSERT( (m_nCount == 0 || m_pHashTable != NULL) );
        // non-empty map should have hash table
}
#endif //_DEBUG

#endif //--- This must be the last line in the file