shm_hash.h

hash表和单向链表的实现代码,相当实用.

/*=================================================================
** Copyright (c)2006,
** All rights reserved.
**
** 文件名称：ipc_hash.h
**
** 当前版本：1.1
** 作    者：Like
** 完成日期：2006-11-24
**
===================================================================*/

#ifndef SHM_HASH_H
#define SHM_HASH_H

#include "shm_elem.h"
#include "shm_list.h"

/*
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53ul,         97ul,         193ul,       389ul,       769ul,
  1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
  49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
  1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
  50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
  1610612741ul, 3221225473ul, 4294967291ul
};
*/


class ShmHash;
class ShmHashIter;

/******************************************************************************
** Author：       Like
** Class Name：   ShmDListIter
** Created Date:  2006-11-24
** Description:   Used to go through a ShmDList
**
** Usage:         See description of ShmDList below
******************************************************************************/

class ShmHashBucket
{
    typedef ShmElem BucketList; 
    typedef ShmElem NodeList;
    
    friend class ShmHash;
    friend class ShmHashIter;
    
public:
    ShmHashBucket()
    {    
    }
    
    ~ShmHashBucket() 
    {
    } 
    
private:
    BucketList  _bucketList;
    NodeList    _nodeList;
};

/******************************************************************************
** Author：       Like
** Class Name：   ShmHashIter
** Created Date:  2006-11-24
** Description:   Used to go through a ShmHash
**
** Usage:         See description of ShmHash below
******************************************************************************/

class ShmHashIter
{
    typedef ShmElem       Node;
    typedef ShmHashBucket Bucket;
    typedef ShmHashIter   iterator;
    
    friend class ShmHash;
    
public:
    ShmHashIter() 
        : _nodeOffset(0), _bucketOffset(0)
    {
    }

    ShmHashIter(ShmOffset node_offset, ShmOffset bucket_offset)
        : _nodeOffset(node_offset), _bucketOffset(bucket_offset)
    {
    }

    ShmHashIter(const iterator& it)
        : _nodeOffset(it._nodeOffset), _bucketOffset(it._bucketOffset)
    {
    }

    Node* operator *()
    { 
        return (Node*) MAKE_SHM_PTR(_nodeOffset);
    }

    iterator& operator ++ ();
    
    iterator operator ++ (int)
    { 
        iterator    tmp = *this; 
        
        ++*this; 
        
        return tmp; 
    }

    bool operator == (const iterator& it) const
    { 
        return _nodeOffset == it._nodeOffset; 
    }
    
    bool operator != (const iterator& it) const
    { 
        return _nodeOffset != it._nodeOffset; 
    }

public:
    ShmOffset   _nodeOffset;
    ShmOffset   _bucketOffset;
};

/******************************************************************************
** Author：       Like
** Class Name：   ShmHash
** Created Date:  2006-11-24
** Description:   是一个基于共享内存的哈希表的实现。
** Note:          任何插入ShmHash的节点必须存放在共享内存上，并且和ShmHash
**                存放于同一个共享内存。使用ShmMgr可以实现这一目的. 
**                Please see shm_mgr.h for more details.           
**
** Usage:         See hash_demo.cpp for details of useage 
**        
******************************************************************************/

typedef struct ShmHashHead
{
    int             _magicNumber;
    int             _elemSize;
    int             _size;
    ShmListHead     _buffList;
    ShmHashBucket   _bucketList;
    ShmHashBucket   _firstEntry;

} ShmHashHead;

class ShmHash
{
    typedef ShmHashBucket Bucket; 
    typedef ShmElem       Node;

    typedef int   (*MatchCallback)(Node*);
    typedef char* (*AllocCallback)(int);
    typedef void  (*FreeCallback)(Node*);
        
    friend class ShmHashIter;
        
public:
    typedef ShmHashIter iterator; 

    enum { HASH_FIND, HASH_INSERT, HASH_NOT_FOUND, HASH_FOUND, HASH_NEW };
    
    ShmHash()
    {
    }
    
    ShmHash(int magic, int elem_size, 
            MatchCallback match_callback, 
            AllocCallback alloc_callback, 
            FreeCallback free_callback = NULL)
    {
        Init(magic, elem_size, match_callback, alloc_callback, free_callback);
    }
        
    ~ShmHash() 
    {
    }

    void Init(int magic, int elem_size, 
            MatchCallback match_callback, 
            AllocCallback alloc_callback, 
            FreeCallback free_callback = NULL)
    {
        _magicNumber   = magic;
        _elemSize      = elem_size;
        _matchCallback = match_callback;     
        _allocCallback = alloc_callback;    
        _freeCallback  = free_callback;
    }

    static int BaseSpace(const int magic);
    
    void Attach(char* mem_addr, int is_created);

    iterator search(int, int& flag);
    iterator erase(iterator&);
    void     clear();

    inline iterator begin()
    {
        Bucket* bucket = 
            (Bucket*) MAKE_SHM_PTR(_bucketList->_bucketList._nextOffset);              
        
        return iterator(bucket->_nodeList._nextOffset, 
                    _bucketList->_bucketList._nextOffset); 
    }
    
    inline iterator end()
    { 
        return iterator(MAKE_SHM_OFF(&(_bucketList->_nodeList)), 
                            MAKE_SHM_OFF(_bucketList));
    }

    unsigned int size() const 
    { 
        return *_size; 
    }
    
       
    bool empty() const 
    { 
        return (*_size == 0); 
    }
    
private:
    void Init();
        
    void LoopBucket(ShmHashBucket* bucket);
    inline void LinkBucketToList(Bucket*);
    inline Bucket* RemoveBucketFromList(Bucket*);

    int             _magicNumber;
    int             _elemSize;
    char*           _location;
    ShmListHead*    _listLocation;
    Bucket*         _bucketEntries;
    Bucket*         _bucketList;
    ShmList         _nodeBuffList;
    int*            _magicNumberPtr; 
    int*            _size;
    int*            _elemSizePtr;
    
    MatchCallback   _matchCallback;
    AllocCallback   _allocCallback;
    FreeCallback    _freeCallback;
};

#endif //SHM_HASH_H