chashtableex.hpp

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

    if( pstBucket->iCount<=0 )
    	return __result;

    iNode	=	pstBucket->iHead;

    n		=	0;
    while(iNode>=0 && iNode<_M_ptable->iMax && n<pstBucket->iCount )
    {
        pstItem	=	SHT_GET_ITEM(_M_ptable, iNode);
        if( pstItem->uCode ==__key)
        {
             ++__result;
        }

    	iNode	=	pstItem->iNext;
    	n++;
    }
  
    return __result;
  }

  pointer remove(const value_type& __obj)
    {
        return sht_remove(_M_ptable, __obj);
    }
  
  int erase(const unsigned int & __key)
    {
       int iBucket;
        LPSHBUCKET pstBucket;
        const _Node* pstItem;
        int iNode;
        int n;
        int __erased = 0;
        iBucket	=	(int) (__key % (unsigned int)_M_ptable->iBucket);
        pstBucket	=	SHT_GET_BUCKET(_M_ptable, iBucket);

        if( pstBucket->iCount<=0 )
        {
        	return __erased;
        }

        iNode	=	pstBucket->iHead;

        n		=	0;
        while(iNode>=0 && iNode<_M_ptable->iMax && n<pstBucket->iCount )
        {
            pstItem	=	SHT_GET_ITEM(_M_ptable, iNode);
            if( pstItem->uCode ==__key)
            {
                sht_remove_by_pos(_M_ptable, iNode );
                 ++__erased;
            }

        	iNode	=	pstItem->iNext;
        	n++;
        }
      return __erased;
    }
  void erase(const iterator& __it)
    {
        int iNode;
        LPSHITEM pstItem;
        iNode = SHT_DATA2INDEX(_M_ptable, __it._M_cur);
        if(iNode >=0 && iNode<_M_ptable->iMax )
        {
            sht_remove_by_pos(_M_ptable, iNode );
        }  
    }
  void erase(const const_iterator& __it)
    {
        int iNode;
        _Node* pvData = const_cast<_Node*>(__it._M_cur);
        LPSHITEM pstItem;
        iNode = SHT_DATA2INDEX(_M_ptable, pvData);
        if(iNode >=0 && iNode<_M_ptable->iMax )
        {
            sht_remove_by_pos(_M_ptable, iNode );
        }  
    }
  

private:
    int sht_make_free_chain_i(LPSHTABLE pstTab);
    int sht_alloc_node_i(LPSHTABLE pstTab);
    int sht_free_node_i(LPSHTABLE pstTab, int iNode);
    void sht_insert_i(LPSHTABLE pstTab, int iNode, unsigned int uCode);
    void sht_remove_i(LPSHTABLE pstTab, int iNode, unsigned int uCode);
    int sht_find_i(LPSHTABLE pstTab, const _Val& pvData, unsigned int uCode);
    LPSHTABLE sht_init(void* pvBuff, int iBuff, int iBucket, int iMax, int iUnit);
    int sht_check(void* pvBuff, int iBuff, int iBucket, int iMax, int iUnit);
    LPSHTABLE sht_attach(void* pvBuff, int iBuff, int iBucket, int iMax, int iUnit);
    _Val* sht_find(LPSHTABLE pstTab, const _Val& pvData);
    _Val* sht_find_new(LPSHTABLE pstTab, const _Val& pvData);
    _Val* sht_insert_unique(LPSHTABLE pstTab, const _Val& pvData);
    _Val* sht_insert_multi(LPSHTABLE pstTab, const _Val& pvData);
    _Val* sht_remove(LPSHTABLE pstTab, const _Val& pvData);
    _Val* sht_remove_by_pos(LPSHTABLE pstTab, int iPos);
    _Val* sht_pos(LPSHTABLE pstTab, int iPos, int* pfValid);
    int sht_rebuild(LPSHTABLE pstTab);
};

template <class _Val, class _ExK,
          class _All>
_Hashtable_iterator<_Val,_ExK,_All>&
_Hashtable_iterator<_Val,_ExK,_All>::operator++()
{
    int i;
    _Val* pvData;
    LPSHITEM pstItem;
    i = SHT_DATA2INDEX(_M_ht->_M_ptable, _M_cur);
    for(; i < _M_ht->_M_ptable->iMax; i++)
    {
    	pvData	=	sht_pos(_M_ht->_M_ptable, i, NULL);

    	pstItem	=	SHT_DATA2ITEM(pvData);

    	if( pstItem->fValid )
    	{
    	    _M_cur = pstItem;
            return *this;
    	}
    }
    _M_cur = 0;
    return *this;
}

template <class _Val, class _ExK,
          class _All>
inline _Hashtable_iterator<_Val,_ExK,_All>
_Hashtable_iterator<_Val,_ExK,_All>::operator++(int)
{
  iterator __tmp = *this;
  ++*this;
  return __tmp;
}

template <class _Val, class _ExK,
          class _All>
_Hashtable_const_iterator<_Val,_ExK,_All>&
_Hashtable_const_iterator<_Val,_ExK,_All>::operator++()
{
    int i;
    void* pvData;
    LPSHITEM pstItem;
    i = SHT_DATA2INDEX(_M_ht->_M_ptable, _M_cur);
    for(; i < _M_ht->_M_ptable->iMax; i++)
    {
    	pvData	=	sht_pos(_M_ht->_M_ptable, i, NULL);

    	pstItem	=	SHT_DATA2ITEM(pvData);

    	if( pstItem->fValid )
    	{
    	    _M_cur = pstItem;
            return *this;
    	}
    }
    _M_cur = 0;
    return *this;
}

template <class _Val, class _ExK, 
          class _All>
inline _Hashtable_const_iterator<_Val,_ExK,_All>
_Hashtable_const_iterator<_Val,_ExK,_All>::operator++(int)
{
  const_iterator __tmp = *this;
  ++*this;
  return __tmp;
}

template <class _Val, class _Ex, class _All>
int CHashTableEx<_Val,_Ex,_All>::sht_make_free_chain_i(LPSHTABLE pstTab)
{
	LPSHITEM pstItem;
	LPSHITEM pstNext;
	int i;
	int n;

	pstTab->iFreeHead	=	-1;
	n	=	0;

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

		if( pstItem->fValid )
			continue;

		n++;

		pstItem->iNext	=	pstTab->iFreeHead;
		pstItem->iPrev	=	-1;

		if( pstTab->iFreeHead<0 )
		{
			pstTab->iFreeHead	=	i;
		}
		else
		{
			pstNext	=	SHT_GET_ITEM(pstTab, pstTab->iFreeHead);
			pstNext->iPrev	=	i;
			pstTab->iFreeHead	=	i;
		}
	}

	return n;
}

template <class _Val, class _Ex, class _All>
int CHashTableEx<_Val,_Ex,_All>::sht_alloc_node_i(LPSHTABLE pstTab)
{
	int iNode;
	LPSHITEM pstItem;
	LPSHITEM pstHead;

	if( pstTab->iFreeHead<0 || pstTab->iFreeHead>=pstTab->iMax )
		return -1;

	iNode	=	pstTab->iFreeHead;
	pstItem	=	SHT_GET_ITEM(pstTab, iNode);

	pstTab->iFreeHead	=	pstItem->iNext;

	pstItem->fValid	=	1;
	pstItem->uCode	=	0;
	pstItem->iNext	=	-1;
	pstItem->iPrev	=	-1;
    pstItem->iLruNext = -1;
    pstItem->iLruPrev = -1;

	if( pstTab->iFreeHead>=0 && pstTab->iFreeHead<pstTab->iMax )
	{
		pstHead	=	SHT_GET_ITEM(pstTab, pstTab->iFreeHead);
		pstHead->iPrev	=	-1;
	}

	pstTab->iItem++;

	return iNode;
}

template <class _Val, class _Ex, class _All>
int CHashTableEx<_Val,_Ex,_All>::sht_free_node_i(LPSHTABLE pstTab, int iNode)
{
	LPSHITEM pstItem;
	LPSHITEM pstHead;

	if( iNode<0 || iNode>=pstTab->iMax )
		return -1;

	pstItem	=	SHT_GET_ITEM(pstTab, iNode);

	pstItem->fValid	=	0;
	pstItem->uCode	=	0;
	pstItem->iPrev	=	-1;
	pstItem->iNext	=	-1;
    pstItem->iLruNext = -1;
    pstItem->iLruPrev = -1;

	if( pstTab->iFreeHead>=0 && pstTab->iFreeHead<pstTab->iMax )
	{
		pstHead	=	SHT_GET_ITEM(pstTab, pstTab->iFreeHead);
		pstHead->iPrev	=	iNode;
	}

	pstItem->iNext		=	pstTab->iFreeHead;
	pstTab->iFreeHead	=	iNode;

	pstTab->iItem--;

	return iNode;
}

template <class _Val, class _Ex, class _All>
void CHashTableEx<_Val,_Ex,_All>::sht_insert_i(LPSHTABLE pstTab, int iNode, unsigned int uCode)
{
	int iBucket;
	LPSHBUCKET pstBucket;
	LPSHITEM pstItem;
	LPSHITEM pstHead;
    LPSHITEM pstLruHead;

	iBucket	=	(int) (uCode % (unsigned int)pstTab->iBucket);

	pstBucket	=	SHT_GET_BUCKET(pstTab, iBucket);

	pstItem	=	SHT_GET_ITEM(pstTab, iNode);

	pstItem->uCode	=	uCode;

	if( pstBucket->iCount>0 )
		pstItem->iNext	=	pstBucket->iHead;
	else
		pstItem->iNext	=	-1;

	pstItem->iPrev	=	-1;

	if( pstBucket->iCount>0 && pstBucket->iHead>=0 && pstBucket->iHead<pstTab->iMax )
	{
		pstHead	=	SHT_GET_ITEM(pstTab, pstBucket->iHead);
		pstHead->iPrev	=	iNode;
	}

	pstBucket->iHead	=	iNode;
	pstBucket->iCount++;

    /*add LRU chain head*/
    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;
    if ( pstTab->iLruTail <0 && pstItem->iLruNext <0) 
        pstTab->iLruTail = iNode;
}

template <class _Val, class _Ex, class _All>
void CHashTableEx<_Val,_Ex,_All>::sht_remove_i(LPSHTABLE pstTab, int iNode, unsigned int uCode)
{
	int iBucket;
	LPSHBUCKET pstBucket;
	LPSHITEM pstItem;
	LPSHITEM pstPrev;
	LPSHITEM pstNext;

	LPSHITEM pstLruPrev;
	LPSHITEM pstLruNext;

	iBucket	=	(int) (uCode % (unsigned int)pstTab->iBucket);

	pstBucket	=	SHT_GET_BUCKET(pstTab, iBucket);

	pstItem	=	SHT_GET_ITEM(pstTab, iNode);

	if( pstItem->iPrev>=0 && pstItem->iPrev<pstTab->iMax )
	{
		pstPrev	=	SHT_GET_ITEM(pstTab, pstItem->iPrev);
		pstPrev->iNext	=	pstItem->iNext;
	}

	if( pstItem->iNext>=0 && pstItem->iNext<pstTab->iMax )
	{
		pstNext	=	SHT_GET_ITEM(pstTab, pstItem->iNext);
		pstNext->iPrev	=	pstItem->iPrev;
	}

	if( pstBucket->iHead==iNode )
		pstBucket->iHead	=	pstItem->iNext;

	pstBucket->iCount--;

    /* delete Lru Chain Item */
	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;
}

template <class _Val, class _Ex, class _All>
int CHashTableEx<_Val,_Ex,_All>::sht_find_i(LPSHTABLE pstTab, const _Val& pvData, unsigned int uCode)
{
	int iBucket;
	LPSHBUCKET pstBucket;
	LPSHITEM pstItem;
	int iNode;
	int n;

	iBucket	=	(int) (uCode % (unsigned int)pstTab->iBucket);
	pstBucket	=	SHT_GET_BUCKET(pstTab, iBucket);

	if( pstBucket->iCount<=0 )
		return -1;

	iNode	=	pstBucket->iHead;
	n		=	0;

	while(iNode>=0 && iNode<pstTab->iMax && n<pstBucket->iCount )
	{
		pstItem	=	SHT_GET_ITEM(pstTab, iNode);

		if( pstItem->uCode==uCode && pvData == *(_Val*)pstItem->szData )
			return iNode;

		iNode	=	pstItem->iNext;
		n++;
	}

	return -1;
}

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

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

	memset(pvBuff, 0, sizeof(SHTABLE));

	pstTab	=	(LPSHTABLE) pvBuff;

	pstTab->cbSize		=	sizeof(SHTABLE);
	pstTab->uFlags		=	0;

	pstTab->iVersion	=	SHT_VERSION;
	pstTab->iBuff		=	iBuff;

	pstTab->iBucket		=	iBucket;
	pstTab->iMax		=	iMax;
	pstTab->iItem		=	0;
	pstTab->iHeadSize	=	SHT_HEADSIZE();

	pstTab->iFreeHead	=	-1;
  	pstTab->iLruHead    =	-1;
  	pstTab->iLruTail    =	-1;
	if( (iBuff - pstTab->iHeadSize)/(int)sizeof(SHBUCKET) < iBucket )