sh_hash.h

rsa算法打的一个包

// SH_Hash.h: interface for the SH_Hash class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_SH_HASH_H__80D8F99D_28F7_4711_839A_A8A4EB304719__INCLUDED_)
#define AFX_SH_HASH_H__80D8F99D_28F7_4711_839A_A8A4EB304719__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "SH_Object.h"
#include "SH_List.h"
#include "SH_Array.h"

 
template<class KEY_ARG,class ARG> 
class AFX_EXT_CLASS SH_Hash : public SH_Object  
{
public: 
    
    typedef struct _SH_HashNode
    {
        ARG     data;
        KEY_ARG key;
    }SH_HashNode;

    typedef struct _SH_HashPosition
    {
        SH_Position pos;
        int         value;
    }SH_HashPosition;

    SH_Hash();
	virtual ~SH_Hash();

    //Function decl
    BOOL         Create(int nBulkSize);
    int          GetBulkSize()  const;
    int          GetCount() const;
    BOOL         Add(KEY_ARG key,ARG val,BOOL bOverWrite=TRUE);
    BOOL         Remove(KEY_ARG key);
    BOOL         Search(KEY_ARG key,ARG & val);
    VOID         RemoveAll();
    SH_Position  GetStartPosition();
    SH_Position  GetEndPosition();
    BOOL         GetNextAssoc(SH_Position & pos,KEY_ARG & key,ARG & data);
    BOOL         GetPrevAssoc(SH_Position & pos,KEY_ARG & key,ARG & data);
    ARG          operator [](KEY_ARG key);

    virtual VOID Destroy(KEY_ARG key,ARG data){}
    virtual int  KeyValue(KEY_ARG key);
    virtual int  KeyCompare(KEY_ARG a,KEY_ARG b);
 
protected:
    SH_HashNode* SearchNode(KEY_ARG key);

private:
    SH_Array<LPVOID>        m_HashBulk;
    int                     m_nBulkSize;
    SH_HashPosition         m_HashPos;
    int                     m_nCount;
};
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
template<class KEY_ARG,class ARG>
SH_Hash<KEY_ARG,ARG>::SH_Hash()
{
    m_nBulkSize   = 0;
    m_nCount      = 0;
}

template<class KEY_ARG,class ARG>
VOID SH_Hash<KEY_ARG,ARG>::RemoveAll()
{
    int i =0;
    SH_HashNode * pNode;
    SH_List<SH_HashNode *> * pHashNodeList;
    for(i=0;i< m_nBulkSize ;i++)
    {
        pHashNodeList = (SH_List<SH_HashNode *>*)m_HashBulk[i];

        if(pHashNodeList)
        {
            while(!pHashNodeList->IsEmpty())
            {
                pNode = pHashNodeList->RemoveHead();
                if(pNode) 
                {
                    Destroy(pNode->key,pNode->data);
                    SAFE_DELETE(pNode);
                }
            }

            SAFE_DELETE(pHashNodeList);

            m_HashBulk.Store(i,NULL);
        }
    }
}

template<class KEY_ARG,class ARG>
SH_Hash<KEY_ARG,ARG>::~SH_Hash()
{
    RemoveAll();

    m_nBulkSize = 0;
}

template<class KEY_ARG,class ARG>
BOOL SH_Hash<KEY_ARG,ARG>::Create(int nBulkSize)
{
    
    if(m_nBulkSize > 0)
        return FALSE;

    m_nBulkSize = nBulkSize;
    
    if(!m_HashBulk.Create(m_nBulkSize))
    {
        m_nBulkSize = 0;
    }
    return TRUE;
}

template<class KEY_ARG,class ARG>
BOOL     SH_Hash<KEY_ARG,ARG>::Add(KEY_ARG key,ARG val,BOOL bOverWrite)
{
    int value;
    SH_HashNode           * pNode;
    SH_List<SH_HashNode*> * pHashNodeList;

    value = KeyValue(key) % m_nBulkSize;

    pHashNodeList = (SH_List<SH_HashNode*>*)m_HashBulk[value];

    if(pHashNodeList == NULL)
    {
        pHashNodeList = new SH_List<SH_HashNode*>;
        m_HashBulk.Store(value,pHashNodeList);
    }
    
    pNode = SearchNode(key);

    if(pNode)
    {
        if(bOverWrite)
        {
            Destroy(pNode->key,pNode->data);
            pNode->data = val;
            pNode->key  = key;
            return TRUE;
        }
        else
            return FALSE;
    }

    pNode = new SH_HashNode;
    pNode->data = val;
    pNode->key  = key;

    pHashNodeList->AddTail(pNode);
    
    return TRUE;
}
template<class KEY_ARG,class ARG>
BOOL     SH_Hash<KEY_ARG,ARG>::Remove(KEY_ARG key)
{
    int value;
    SH_Position             pos,oldpos;
    SH_HashNode           * pNode;
    SH_List<SH_HashNode*> * pHashNodeList;

    value = KeyValue(key) % m_nBulkSize;

    pHashNodeList = (SH_List<SH_HashNode*>*)m_HashBulk[value];

    if(!pHashNodeList)
        return FALSE;

    pos = pHashNodeList->GetHeadPosition();

    while(pos)
    {
        oldpos = pos;
        pNode = pHashNodeList->GetNext(pos);

        if(pNode && KeyCompare(pNode->key,key) == 0)
        {
            Destroy(pNode->key,pNode->data);
            pHashNodeList->RemoveAt(oldpos);
            
            SAFE_DELETE(pNode);
            
            return TRUE;
        }
    }
    return FALSE;
}

template<class KEY_ARG,class ARG>
BOOL     SH_Hash<KEY_ARG,ARG>::Search(KEY_ARG key,ARG & val)
{
    int value;
    SH_Position       pos;
    SH_HashNode     * pNode;
    SH_List<SH_HashNode*> *  pHashNodeList;

    value = KeyValue(key) % m_nBulkSize;

    pHashNodeList = (SH_List<SH_HashNode*>*)m_HashBulk[value];

    if(!pHashNodeList)
        return FALSE;

    pos = pHashNodeList->GetHeadPosition();

    while(pos)
    {
        pNode = pHashNodeList->GetNext(pos);

        if(pNode && KeyCompare(pNode->key,key) == 0)
        {
            val = pNode->data;
            return TRUE;
        }
    }
    return FALSE;
}

template<class KEY_ARG,class ARG>
SH_Hash<KEY_ARG,ARG>::SH_HashNode * SH_Hash<KEY_ARG,ARG>::SearchNode(KEY_ARG key)
{
    int value;
    SH_Position       pos;
    SH_HashNode     * pNode;
    SH_List<SH_HashNode*> *  pHashNodeList;

    value = KeyValue(key) % m_nBulkSize;

    pHashNodeList = (SH_List<SH_HashNode*>*)m_HashBulk[value];

    if(!pHashNodeList)
        return NULL;

    pos = pHashNodeList->GetHeadPosition();

    while(pos)
    {
        pNode = pHashNodeList->GetNext(pos);

        if(pNode && KeyCompare(pNode->key,key) == 0)
        {
            return pNode;
        }
    }
    return NULL;
}

template<class KEY_ARG,class ARG>
int SH_Hash<KEY_ARG,ARG>::KeyValue(KEY_ARG key)
{
    int    value = 0;

    value = (int)key;

    return value;
}
template<class KEY_ARG,class ARG>
SH_Position SH_Hash<KEY_ARG,ARG>::GetStartPosition()
{
    int i = 0;
    SH_HashNode * pNode = NULL;
    SH_List<SH_HashNode *> * pHashNodeList;

    for(i = 0; i < m_HashBulk.GetSize();i++)
    {
        pHashNodeList = (SH_List<SH_HashNode *>*)m_HashBulk[i];

        if(pHashNodeList)
        {
            if(pHashNodeList->GetHead(pNode))
            {
                if(pNode) 
                {
                    m_HashPos.pos   = pHashNodeList->GetHeadPosition();
                    m_HashPos.value = i;

                    return (SH_Position)&m_HashPos;
                }
            }
        }
    }
    return NULL;
}

template<class KEY_ARG,class ARG>
SH_Position SH_Hash<KEY_ARG,ARG>::GetEndPosition()
{
    int i = 0;
    SH_HashNode * pNode;
    SH_List<SH_HashNode *,SH_HashNode*> * pHashNodeList;

    for(i = m_HashBulk.GetSize(); i>0 ;i++)
    {
        pHashNodeList = (SH_List<SH_HashNode *,SH_HashNode*>*)m_HashBulk[i-1];

        if(pHashNodeList)
        {
            pNode = pHashNodeList->GetTail();
                if(pNode) 
                {
                    m_HashPos.pos   = pHashNodeList->GetTailPosition();
                    m_HashPos.value = i;

                    return (SH_Position)&m_HashPos;
                }
        }
    }
    return NULL;
}

template<class KEY_ARG,class ARG>
BOOL SH_Hash<KEY_ARG,ARG>::GetNextAssoc(SH_Position & pos,KEY_ARG & key,ARG & data)
{
    int               i     = 0;
    int               value = 0;
    SH_HashNode     * pNode;
    SH_HashPosition * pHashPos;
    SH_List<SH_HashNode *> * pHashNodeList;

    pHashPos = (SH_HashPosition*)pos;
    if(!pHashPos || !pHashPos->pos) 
        return FALSE;
    pHashNodeList = (SH_List<SH_HashNode *>*)m_HashBulk[pHashPos->value];

    pNode = pHashNodeList->GetNext(pHashPos->pos);
    ASSERT(pNode != NULL);
    data = pNode->data;
    key  = pNode->key;

    if(pHashNodeList)
    {
        if(pHashPos->pos == NULL)
        {
            for(i=pHashPos->value+1;i<m_nBulkSize;i++)
            {
                pHashNodeList = (SH_List<SH_HashNode *>*)m_HashBulk[i];

                if(pHashNodeList && pHashNodeList->GetHead(pNode))
                {
                    if(pNode)
                    {
                        m_HashPos.pos   = pHashNodeList->GetHeadPosition();
                        m_HashPos.value = i;
                        pos = (SH_Position)&m_HashPos;
                        return TRUE;
                    }
                }
            }

            pos = NULL;
        }
        return TRUE;
    }
    return FALSE;
}
template<class KEY_ARG,class ARG>
BOOL   SH_Hash<KEY_ARG,ARG>::GetPrevAssoc(SH_Position & pos,KEY_ARG & key,ARG & data)
{
    int               i     = 0;
    int               value = 0;
    SH_HashNode     * pNode;
    SH_HashPosition * pHashPos;
    SH_List<SH_HashNode *,SH_HashNode*> * pHashNodeList;

    
    pHashPos = (SH_HashPosition*)pos;
    
    if(!pHashPos || !pHashPos->pos) 
        return FALSE;
    
    pHashNodeList = (SH_List<SH_HashNode *,SH_HashNode*>*)m_HashBulk[pHashPos->value];

    pNode = pHashNodeList->GetPrev(pHashPos->pos);
    ASSERT(pNode != NULL);
    data = pNode->data;
    key  = pNode->key;

    if(pHashNodeList)
    {
        if(pHashPos->pos == NULL)
        {
            for(i=pHashPos->value-1;i>=0;i++)
            {
                pHashNodeList = (SH_List<SH_HashNode *,SH_HashNode*>*)m_HashBulk[i];

                if(pHashNodeList->GetTail(pNode))
                {
                    if(pNode)
                    {
                        m_HashPos.pos   = pHashNodeList->GetTailPosition();
                        m_HashPos.value = i;
                        pos = (SH_Position)&m_HashPos;
                        return TRUE;
                    }
                }
            }
            pos = NULL;
        }
        return TRUE;
    }
    return FALSE;
}


template<class KEY_ARG,class ARG>
int SH_Hash<KEY_ARG,ARG>::KeyCompare(KEY_ARG a,KEY_ARG b)
{
    if(a>b)
        return 1;
    else if(a==b)
        return 0;
    else
        return -1;
}

template<class KEY_ARG,class ARG>
ARG SH_Hash<KEY_ARG,ARG>::operator [](KEY_ARG key)
{
    ARG value = (ARG)0;

    if(!Search(key,value))
        ASSERT(FALSE);

    return value;
}

template<class KEY_ARG,class ARG>
AFX_INLINE  int      SH_Hash<KEY_ARG,ARG>::GetCount()  const
{
    return m_nCount;
}

#endif // !defined(AFX_SH_HASH_H__80D8F99D_28F7_4711_839A_A8A4EB304719__INCLUDED_)