chashtableex.hpp

LRU算法的C++实现类。封装得不错

		return NULL;

	pstTab->iBucketOff	=	pstTab->iHeadSize;
	pstTab->iBucketSize	=	sizeof(SHBUCKET)*iBucket;

	pstTab->iDataOff		=	pstTab->iBucketOff + pstTab->iBucketSize;
	pstTab->iDataUnitMin	=	iUnit;
	pstTab->iDataUnitMax	=	SHT_DATAUNIT(iUnit);

	if( (iBuff - pstTab->iDataOff)/pstTab->iDataUnitMax < iMax )
		return NULL;

	pstTab->iDataSize		=	pstTab->iDataUnitMax*iMax;

	//2008.06.10 by kent, init item valid flag
	for (i = 0; i<pstTab->iMax; i++)
	{
		pstItem	=	SHT_GET_ITEM(pstTab, i);
		pstItem->fValid = 0;
	}
	//by kent end

	sht_make_free_chain_i(pstTab);

	return pstTab;
}

template <class _Val, class _Ex, class _All>
int CHashTableEx<_Val,_Ex,_All>::sht_check(void* pvBuff, int iBuff, int iBucket, int iMax, int iUnit)
{
	LPSHTABLE pstTab;
	int iSize;

	pstTab	=	(LPSHTABLE) pvBuff;

	if( iBuff<(int)SHT_HEADSIZE() || iBucket<=0 || iMax<=0 || iUnit<=0 )
		return -1;

	iSize	=	SHT_SIZE(iBucket, iMax, iUnit);
	if( iBuff<iSize )
		return -1;

	if( pstTab->iBuff!=iBuff || pstTab->iVersion!=SHT_VERSION ||
		pstTab->cbSize!=sizeof(SHTABLE) || pstTab->iBucket!=iBucket ||
		pstTab->iMax!=iMax || pstTab->iItem>pstTab->iMax ||
		pstTab->iHeadSize!=SHT_HEADSIZE() )
		return -1;

	if( pstTab->iHeadSize>pstTab->iBucketOff || 
		pstTab->iBucketSize/sizeof(SHBUCKET)!=iBucket ||
		iBuff - pstTab->iBucketOff<pstTab->iBucketSize ||
		pstTab->iBucketOff+pstTab->iBucketSize>pstTab->iDataOff || 
		pstTab->iDataUnitMin!=iUnit || 
		pstTab->iDataUnitMax!=SHT_DATAUNIT(iUnit) || 
		pstTab->iDataSize/pstTab->iDataUnitMax!=iMax ||
		iBuff - pstTab->iDataOff<pstTab->iDataSize )
		return -1;

	return 0;
}

template <class _Val, class _Ex, class _All>
LPSHTABLE CHashTableEx<_Val,_Ex,_All>::sht_attach(void* pvBuff, int iBuff, int iBucket, int iMax, int iUnit)
{
	if( sht_check(pvBuff, iBuff, iBucket, iMax, iUnit)<0 )
		return NULL;
	else
		return (LPSHTABLE)pvBuff;
}

template <class _Val, class _Ex, class _All>
_Val* CHashTableEx<_Val,_Ex,_All>::sht_find(LPSHTABLE pstTab, const _Val& pvData)
{
	unsigned int uCode;
	int iNode;
	LPSHITEM pstItem;
    LPSHITEM pstLruPrev;
    LPSHITEM pstLruNext;
    LPSHITEM pstLruHead;

	uCode = _M_get_key(pvData);
	iNode	=	sht_find_i(pstTab, pvData, uCode);

	if( iNode<0 )
		return NULL;

	pstItem	=	SHT_GET_ITEM(pstTab, iNode);

    /*  Update LRU Chain    (delete and add head)   */
    if (pstTab->iLruHead != iNode)    
    {
    	if( pstItem->iLruPrev >=0 && pstItem->iLruPrev<pstTab->iMax )
    	{
    		pstLruPrev = SHT_GET_ITEM(pstTab, pstItem->iLruPrev);
    		pstLruPrev->iLruNext = pstItem->iLruNext;
    	}

    	if( pstItem->iLruNext >=0 && pstItem->iLruNext<pstTab->iMax )
    	{
    		pstLruNext = SHT_GET_ITEM(pstTab, pstItem->iLruNext);
    		pstLruNext->iLruPrev = pstItem->iLruPrev;
    	}
        /*    
        if (pstTab->iLruHead == iNode)
            pstTab->iLruHead = pstItem->iLruNext;
        */    
        if (pstTab->iLruTail == iNode)
            pstTab->iLruTail = pstItem->iLruPrev;

        if( pstTab->iLruHead >=0 && pstTab->iLruHead< pstTab->iMax )
        {
            pstLruHead = SHT_GET_ITEM(pstTab, pstTab->iLruHead);
            pstLruHead->iLruPrev = iNode;
        }
        pstItem->iLruNext = pstTab->iLruHead ;
        pstItem->iLruPrev = -1;
        pstTab->iLruHead = iNode;
    }
    
	return (_Val*)pstItem->szData;
}

template <class _Val, class _Ex, class _All>
_Val* CHashTableEx<_Val,_Ex,_All>::sht_find_new(LPSHTABLE pstTab, const _Val& pvData)
{
	unsigned int uCode;
	int iNode;
	LPSHITEM pstItem;

    uCode = _M_get_key(pvData);
	iNode	=	sht_find_i(pstTab, pvData, uCode);

	if( iNode<0 )
		return NULL;

	pstItem	=	SHT_GET_ITEM(pstTab, iNode);

	return (_Val*)pstItem->szData;
}

template <class _Val, class _Ex, class _All>
_Val* CHashTableEx<_Val,_Ex,_All>::sht_insert_unique(LPSHTABLE pstTab, const _Val& pvData)
{
	if( sht_find(pstTab, pvData) )
		return NULL;

	return sht_insert_multi(pstTab, pvData);
}

template <class _Val, class _Ex, class _All>
_Val* CHashTableEx<_Val,_Ex,_All>::sht_insert_multi(LPSHTABLE pstTab, const _Val& pvData)
{
	unsigned int uCode;
	int iNode;
	LPSHITEM pstItem;

	iNode	=	sht_alloc_node_i(pstTab);

       //modified by jinglinma 20090510 begin
	//if( iNode<0 )
	//	return NULL;
        //try to get one of the right LRU
        if (iNode < 0)
        {
            if( pstTab->iLruTail<0 || pstTab->iLruTail > pstTab->iMax )
            {
                return NULL;
            }
            sht_remove_by_pos(pstTab, pstTab->iLruTail );
            iNode = sht_alloc_node_i(pstTab);
            if (iNode < 0)
            {
                return NULL;
            }
        }
       //modified by jinglinma 20090510 end

    uCode = _M_get_key(pvData);

    sht_insert_i(pstTab, iNode, uCode);

	pstItem	=	SHT_GET_ITEM(pstTab, iNode);

    return (_Val*)pstItem->szData;
}

template <class _Val, class _Ex, class _All>
_Val* CHashTableEx<_Val,_Ex,_All>::sht_remove(LPSHTABLE pstTab, const _Val& pvData)
{
	unsigned int uCode;
	int iNode;
	LPSHITEM pstItem;

    uCode = _M_get_key(pvData);

    iNode = sht_find_i(pstTab, pvData,  uCode);
	if( iNode<0 )
		return NULL;

	sht_remove_i(pstTab, iNode, uCode);
	sht_free_node_i(pstTab, iNode);

	pstItem	=	SHT_GET_ITEM(pstTab, iNode);

	return (_Val*)pstItem->szData;
}

template <class _Val, class _Ex, class _All>
_Val* CHashTableEx<_Val,_Ex,_All>::sht_remove_by_pos(LPSHTABLE pstTab, int iPos)
{
	LPSHITEM pstItem;

	if( iPos<0 || iPos>=pstTab->iMax )
		return NULL;

	pstItem	=	SHT_GET_ITEM(pstTab, iPos);

	sht_remove_i(pstTab, iPos, pstItem->uCode);
	sht_free_node_i(pstTab, iPos);

	return (_Val*)pstItem->szData;
}

template <class _Val, class _Ex, class _All>
_Val* CHashTableEx<_Val,_Ex,_All>::sht_pos(LPSHTABLE pstTab, int iPos, int* pfValid)
{
	LPSHITEM pstItem;

	if( iPos<0 || iPos>=pstTab->iMax )
		return NULL;

	pstItem	=	SHT_GET_ITEM(pstTab, iPos);

	if( pfValid )
		*pfValid	=	pstItem->fValid;

	return (_Val*)pstItem->szData;
}

template <class _Val, class _Ex, class _All>
int CHashTableEx<_Val,_Ex,_All>::sht_rebuild(LPSHTABLE pstTab)
{
	LPSHITEM pstItem;
	LPSHBUCKET pstBucket;
	int i;

	sht_make_free_chain_i(pstTab);

	for(i=0; i<pstTab->iBucket; i++)
	{
		pstBucket	=	SHT_GET_BUCKET(pstTab, i);
		pstBucket->iCount	=	0;
		pstBucket->iHead	=	-1;
	}

	pstTab->iItem	=	0;

	for(i=0; i<pstTab->iMax; i++)
	{
		pstItem	=	SHT_GET_ITEM(pstTab, i);

		if( !pstItem->fValid )
			continue;

		sht_insert_i(pstTab, i, pstItem->uCode);

		pstTab->iItem++;
	}

	return 0;
}


template <class _Val, class _Ex, class _All>
int CHashTableEx<_Val,_Ex,_All>::dump_all(ostream &out)
{
    int i;
    _Val* pvData;
    LPSHITEM pstItem;

    out << "--------------Dump hash table(ALL) start----------------\n";
    out << "Bucket:" << _M_ptable->iBucket << ", Buff:" << _M_ptable->iBuff << "\n";
    out << "Max Items:" << _M_ptable->iMax << " Total Items:" << _M_ptable->iItem << "\n";

    for(i=0; i < _M_ptable->iMax; i++)
    {
    	pvData	=	sht_pos(_M_ptable, i, NULL);

    	pstItem	=	SHT_DATA2ITEM(pvData);

    	if( pstItem->fValid )
    		{
                    out << "\t(VALID) Item pos=" << i << " code=" << pstItem->uCode << " ";
                    out << *pvData;
                    out << endl;
    	}
    	else
    	{
                    out << "\t(FREE) Item pos=" << i << " code=" << pstItem->uCode << " \n";
    	}
    }
    out << "--------------Dump hash table(ALL) end-------------------\n";

    return 0;
}

template <class _Val, class _Ex, class _All>
int CHashTableEx<_Val,_Ex,_All>::dump_valid(ostream &out)
{
    int i;
    int n;
    LPSHBUCKET pstBucket;
    LPSHITEM pstItem;

    out << "--------------Dump hash table(VALID) start---------------\n";
    out << "Bucket:" << _M_ptable->iBucket << ", Buff:" << _M_ptable->iBuff <<"\n";
    out << "Max Items:" << _M_ptable->iMax << " Total Items:" << _M_ptable->iItem << "\n";
 
	for(i=0; i < _M_ptable->iBucket; i++)
	{
		pstBucket	=	SHT_GET_BUCKET(_M_ptable, i);

		if( pstBucket->iCount<=0 )
	    {
			continue;
		}
	    //fprintf(fp, "Bucket %4d Items:%d\n", i, pstBucket->iCount );

		if( pstBucket->iHead<0 || pstBucket->iHead>_M_ptable->iMax )
		{
                    out << "\t[ERROR] Head Pos=" << pstBucket->iHead << "\n";
			continue;
		}

		pstItem	=	SHT_GET_ITEM(_M_ptable, pstBucket->iHead);
		n =	0;

		do
		{
			//fprintf(fp, "\t(VALID) Item pos=%d code=%08x ", i, pstItem->uCode);
			//fprintf(fp, "\t Item pos=%d  ", i );
			out << "\t";
                    out << *(_Val*)pstItem->szData;
                    out << endl;

			if( pstItem->iNext<0 )
				break;
            pstItem	=	SHT_GET_ITEM(_M_ptable, pstItem->iNext);
			n++;
		}
		while( n<pstBucket->iCount );
	}

    out << "--------------Dump hash table(VALID) end-----------------\n";
	return 0;
}

template <class _Val, class _Ex, class _All>
int CHashTableEx<_Val,_Ex,_All>::dump_lru(ostream &out)
{
	int i;
	int n;
	LPSHITEM pstItem;

    out << "--------------Dump hash table(VALID) start---------------\n";
    out << "Bucket:" << _M_ptable->iBucket << ", Buff:" << _M_ptable->iBuff <<"\n";
    out << "Max Items:" << _M_ptable->iMax << " Total Items:" << _M_ptable->iItem << "\n";


    if( _M_ptable->iLruHead<0 || _M_ptable->iLruHead>_M_ptable->iMax )
        return 0;
    out << "--------------Dump LRU Chain start---------------\n";
    //pstItem = SHT_GET_ITEM(pstTab, pstTab->iLruHead);
    pstItem = SHT_GET_ITEM(_M_ptable, _M_ptable->iLruTail);
    n = 0;
    i=  _M_ptable->iLruTail;
    do
    {
        out << "\t LRU=" << n << ",  pos=" << i << " ";
        out << *(_Val*)pstItem->szData;
        out << endl;
    	if( pstItem->iLruPrev<0 )	break;
        i =  pstItem->iLruPrev;
        pstItem	= SHT_GET_ITEM(_M_ptable, pstItem->iLruPrev);
		n++;
    }while(1);
    out << "--------------Dump LRU Chain end---------------\n";
	return 0;
}

template <class _Val, class _Ex, class _All>
int CHashTableEx<_Val,_Ex,_All>::Init(int fCreate)
{
    LPSHTABLE    pTab = NULL;

    long iSize = SHT_SIZE( _M_num_elements/4, _M_num_elements, sizeof(_Val));

    if( iSize <= SHT_HEADSIZE() )
    {
        printf("invalid size:%d\n", iSize);
        return -2;
    }
    _M_ptable = _M_get_Table(iSize);

    if( NULL==_M_ptable)
    {
        return -1;
    }

    if ( fCreate )
    {
        pTab = sht_init(_M_ptable, iSize, _M_num_elements/4, _M_num_elements, sizeof(_Val));
    }
    else
    {
        pTab = sht_attach(_M_ptable, iSize, _M_num_elements/4, _M_num_elements, sizeof(_Val));
    }
    if( NULL== pTab)     
    {
        printf("initialize shared memory failed\n");
        return -3;
    }

    _M_ptable->uFlags   =   SHTF_NEEDFREE;

    return 0;
}


#endif /* __C_HASHTABLEEX_HPP__ */

// Local Variables:
// mode:C++
// End: