chashtableex.hpp

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

#ifndef __C_HASHTABLEEX_HPP__
#define __C_HASHTABLEEX_HPP__

#include <iostream>
#include <utility>
#include "CShmManager.hpp"

using namespace std;

const int CHASH_TABLE_EX_MAX_HASH_NODE_COUNT = 50000000;
enum { _INIT_TABLE = 1,_CHECK_TABLE = 0 };

#define SHT_MIN_HEAD			0x100
#define SHT_BUCKET_ALIGN		0x100
#define SHT_MIN_ALIGN			0x08
#define SHT_VERSION				0x0101

#define SHTF_NEEDFREE			0x01

struct tagSHitem
{
	int iPrev;
	int iNext;
    int iLruPrev;
    int iLruNext;
	unsigned uCode;
	int fValid;
	char szData[1];
};

typedef struct tagSHitem		SHITEM;
typedef struct tagSHitem		*LPSHITEM;

struct tagSHbucket
{
	int iCount;
	int iHead;
};

typedef struct tagSHbucket		SHBUCKET;
typedef struct tagSHbucket		*LPSHBUCKET;

struct tagSHtable
{
	unsigned int cbSize;		/* the size of this struct. */
	unsigned int uFlags;		/* some flags. */
	int iVersion;				/* version number. */
	int iBuff;					/* the size of the buff. */

	int iBucket;				/* bucket number used. */
	int iMax;					/* maximum items can store. */
	int iItem;					/* current item number. */
	int iHeadSize;

	int iBucketOff;
	int iBucketSize;

	int iDataOff;
	int iDataSize;
	int iDataUnitMin;			/* the data-unit's real size. */
	int iDataUnitMax;			/* the data-unit's occupy size.*/

	int iFreeHead;
    int iLruHead;
    int iLruTail;
	int iRes;					/* reserved. */
};

typedef struct tagSHtable			SHTABLE;
typedef struct tagSHtable			*LPSHTABLE;

#define SHT_ROUND(size)					( ( (size) + SHT_MIN_ALIGN - 1) /SHT_MIN_ALIGN*SHT_MIN_ALIGN )

#define SHT_HEADSIZE()					( SHT_MIN_HEAD < sizeof(SHTABLE) ? sizeof(SHTABLE) : SHT_MIN_HEAD )

#define SHT_BUCKETSIZE(buck)			( (buck) * sizeof(SHBUCKET) )

#define SHT_DATAUNIT(data)				SHT_ROUND((data) + offsetof(SHITEM, szData))

#define SHT_DATASIZE(max, unit)			( (max) * SHT_DATAUNIT(unit) )

#define SHT_SIZE(buck, max, unit)		( SHT_HEADSIZE() + SHT_BUCKETSIZE(buck) + SHT_DATASIZE(max, unit) )

#define SHT_GET_BUCKET(pstTab, i)		( (LPSHBUCKET) ( ((int)(pstTab)) + pstTab->iBucketOff + i*sizeof(SHBUCKET) ) )

#define SHT_GET_ITEM(pstTab, i)			( (LPSHITEM) ( ((int)(pstTab)) + pstTab->iDataOff + i*pstTab->iDataUnitMax ) )

#define SHT_DATA2ITEM(pvData)			( (SHITEM*) ( ((int)(pvData)) - offsetof(SHITEM, szData)) )
#define SHT_ITEM2DATA(pvItem)			( (pvItem)->szData )

#define SHT_DATA2INDEX(pstTab, pvData)			(( ((int)(pstTab)) + pstTab->iDataOff -  ( ((int)(pvData)) - offsetof(SHITEM, szData)) )/pstTab->iDataUnitMax)

typedef CShmManager<SHTABLE> shmAlloc;

template <class _Val, class _ExtractKey, class _Alloc = shmAlloc >
class CHashTableEx;

template <class _Val,
          class _ExtractKey, class _Alloc>
struct _Hashtable_iterator;

template <class _Val,
          class _ExtractKey, class _Alloc>
struct _Hashtable_const_iterator;

template <class _Val,
          class _ExtractKey, class _Alloc>
struct _Hashtable_iterator {
  typedef CHashTableEx<_Val,_ExtractKey,_Alloc>
          _Hashtable;
  typedef _Hashtable_iterator<_Val,   
                              _ExtractKey,  _Alloc>
          iterator;
  typedef _Hashtable_const_iterator<_Val,   
                                    _ExtractKey,  _Alloc>
          const_iterator;
  typedef SHITEM _Node;

  typedef _Val value_type;
  typedef size_t size_type;
  typedef ptrdiff_t         difference_type;  
  typedef _Val& reference;
  typedef _Val* pointer;

  _Node* _M_cur;
  _Hashtable* _M_ht;

  _Hashtable_iterator(_Node* __n, _Hashtable* __tab) 
    : _M_cur(__n), _M_ht(__tab) {}
  _Hashtable_iterator() {}
  reference operator*() const { return *(pointer)_M_cur->szData; }
  pointer operator->() const { return &(operator*()); }
  iterator& operator++();
  iterator operator++(int);
  bool operator==(const iterator& __it) const
    { return _M_cur == __it._M_cur; }
  bool operator!=(const iterator& __it) const
    { return _M_cur != __it._M_cur; }
};


template <class _Val,
          class _ExtractKey, class _Alloc>
struct _Hashtable_const_iterator {
  typedef CHashTableEx<_Val,_ExtractKey,_Alloc>
          _Hashtable;
  typedef _Hashtable_iterator<_Val, 
                              _ExtractKey,_Alloc>
          iterator;
  typedef _Hashtable_const_iterator<_Val,   
                                    _ExtractKey,  _Alloc>
          const_iterator;
  typedef SHITEM _Node;

  typedef forward_iterator_tag iterator_category;
  typedef _Val value_type;
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;
  typedef const _Val& reference;
  typedef const _Val* pointer;

  const _Node* _M_cur;
  const _Hashtable* _M_ht;

  _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
    : _M_cur(__n), _M_ht(__tab) {}
  _Hashtable_const_iterator() {}
  _Hashtable_const_iterator(const iterator& __it) 
    : _M_cur(__it._M_cur), _M_ht(__it._M_ht) {}
  reference operator*() const { return *(pointer)_M_cur->szData;; }
  pointer operator->() const { return &(operator*()); }
  const_iterator& operator++();
  const_iterator operator++(int);
  bool operator==(const const_iterator& __it) const 
    { return _M_cur == __it._M_cur; }
  bool operator!=(const const_iterator& __it) const 
    { return _M_cur != __it._M_cur; }
};

// Forward declaration of operator==.

template <class _Val, class _Ex, class _All>
class CHashTableEx;

template <class _Val,
          class _ExtractKey, class _Alloc>
class CHashTableEx {
public:
  typedef _Val value_type;

  typedef size_t            size_type;
  typedef ptrdiff_t         difference_type;
  typedef value_type*       pointer;
  typedef const value_type* const_pointer;
  typedef value_type&       reference;
  typedef const value_type& const_reference;

private:
  typedef SHITEM _Node;

public:
  typedef _Alloc allocator_type;
private:
  allocator_type _M_table_allocator;
  LPSHTABLE _M_get_Table(long iTblSize) { return _M_table_allocator.allocate(iTblSize); }
  void _M_put_Table(LPSHTABLE pTbl) { return _M_table_allocator.deallocate(pTbl); }
    #define __HASH_ALLOC_INIT(__a) _M_table_allocator(__a),
private:
  _ExtractKey           _M_get_key;

  LPSHTABLE _M_ptable;
  size_type             _M_num_elements;  

public:
  typedef _Hashtable_iterator<_Val,_ExtractKey,_Alloc>
          iterator;
  typedef _Hashtable_const_iterator<_Val,_ExtractKey,
                                    _Alloc>
          const_iterator;

  friend struct
  _Hashtable_iterator<_Val,_ExtractKey,_Alloc>;
  friend struct
  _Hashtable_const_iterator<_Val,_ExtractKey,_Alloc>;

public:
  CHashTableEx(size_type n,
            int inittype,
            const _ExtractKey& __ext,
            const allocator_type& __a = shmAlloc())
    : __HASH_ALLOC_INIT(__a)
    _M_get_key(__ext)
  {
    _M_num_elements = n;
    Init(inittype);
    return;
  }
  ~CHashTableEx() { _M_put_Table(_M_ptable);}
    int Init(int fCreate = _CHECK_TABLE);
    int dump_all(ostream &out = cout);
    int dump_valid(ostream &out = cout);
    int dump_lru(ostream &out = cout);

  size_type size() const 
  {
      return _M_ptable->iItem; 
  }
  size_type max_size() const { return _M_ptable->iMax; }
  bool empty() const { return size() == 0; }

  //遍历方式不更新LRU
  iterator begin()
  {
    int i;
    _Val* pvData;
    LPSHITEM pstItem;
    for(i=0; i<_M_ptable->iMax; i++)
    {
    	pvData	=	sht_pos(_M_ptable, i, NULL);

    	pstItem	=	SHT_DATA2ITEM(pvData);

    	if( pstItem->fValid )
    	{
            return iterator(pstItem, this);
    	}
    }      
    return end();
  }

  iterator end() { return iterator(0, this); }

  const_iterator begin() const
  {
    int i;
    _Val* pvData;
    LPSHITEM pstItem;
    for(i=0; i<_M_ptable->iMax; i++)
    {
    	pvData	=	sht_pos(_M_ptable, i, NULL);

    	pstItem	=	SHT_DATA2ITEM(pvData);

    	if( pstItem->fValid )
    	{
            return const_iterator(pstItem, this);
    	}
    }
    return end();
  }

  const_iterator end() const { return const_iterator(0, this); }

public:

  size_type max_bucket_count() const
    { return _M_ptable->iBucket; } 

  size_type elems_in_bucket(size_type __bucket) const
  {
    LPSHBUCKET pstBucket;
    pstBucket	=	SHT_GET_BUCKET(_M_ptable, __bucket);
    return pstBucket->iCount;
  }

  pair<iterator, bool> insert_unique(const value_type& __obj)
  {
    return insert_unique_noresize(__obj);
  }

  iterator insert_equal(const value_type& __obj)
  {
    return insert_equal_noresize(__obj);
  }

  pair<iterator, bool> insert_unique_noresize(const value_type& __obj)
    {
        value_type *pdata = NULL;
        LPSHITEM pstItem;

        pdata = sht_insert_unique( _M_ptable, __obj);
        if ( NULL != pdata )
        {
            pstItem	=	SHT_DATA2ITEM(pdata);
            memcpy(pdata, &__obj, sizeof(__obj));
            return pair<iterator, bool>(iterator(pstItem, this), true);
        }
        return pair<iterator, bool>(iterator(0, this), false);
    }
  iterator insert_equal_noresize(const value_type& __obj)
{

    value_type *pdata = NULL;
    LPSHITEM pstItem;
    
    sht_insert_multi(_M_ptable, __obj);
    if ( NULL != pdata )
    {
        pstItem	=	SHT_DATA2ITEM(pdata);
        memcpy(pdata, &__obj, sizeof(__obj));
        return iterator(pstItem, this);
    }
    return iterator(0, this);
}

  pointer find_or_insert(const value_type& __obj)
    {
        value_type *pdata = sht_find(_M_ptable, __obj);
        if( pdata != NULL)
        {
        	return pdata;
        }

        return sht_insert_multi(_M_ptable, __obj);
    } 
    pointer search(const value_type& __obj)
    {
        return sht_find(_M_ptable, __obj);
    }

  iterator find(const unsigned int & __key) 
  {
    int iBucket;
    LPSHBUCKET pstBucket;
    _Node* pstItem;
    int iNode;
    int n;
    iBucket	=	(int) (__key % (unsigned int)_M_ptable->iBucket);
    pstBucket	=	SHT_GET_BUCKET(_M_ptable, iBucket);

    if( pstBucket->iCount<=0 )
    {
    	return iterator(0, this);
    }

    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)
        {
          return iterator(pstItem, this);
        }

    	iNode	=	pstItem->iNext;
    	n++;
    }
  
    return iterator(0, this);
  } 

  const_iterator find(const unsigned int & __key) const
  {
   int iBucket;
    LPSHBUCKET pstBucket;
    const _Node* pstItem;
    int iNode;
    int n;
    const _Node* __first = NULL;
    iBucket	=	(int) (__key % (unsigned int)_M_ptable->iBucket);
    pstBucket	=	SHT_GET_BUCKET(_M_ptable, iBucket);

    if( pstBucket->iCount<=0 )
    {
    	return const_iterator(__first, this);
    }

    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)
        {
          return const_iterator(pstItem, this);
        }

    	iNode	=	pstItem->iNext;
    	n++;
    }
  
    return const_iterator(__first, this);
  } 

  size_type count(const unsigned int &__key) const
  {
   int iBucket;
    LPSHBUCKET pstBucket;
    const _Node* pstItem;
    int iNode;
    int n;
    size_type __result = 0;
    iBucket	=	(int) (__key % (unsigned int)_M_ptable->iBucket);
    pstBucket	=	SHT_GET_BUCKET(_M_ptable, iBucket);