/*=================================================================** Copyright (c)2006,** All rights reserved.**** 文件名稱：ipc_hash.cpp**** 當前版本：1.1** 作    者：Like** 完成日期：2006-11-24**===================================================================*/#include <stdlib.h>#include <stdio.h>#include "shm_hash.h" /* int HashFunc(char *key, int len){    char* end = key + len;    int  hash = 0;        for (hash = 0; key < end; key++)    {        hash *= 16777619;        hash ^= (int) *(unsigned char*) key;    }        hash &= 134217727;    return (hash);} */ShmHashIter& ShmHashIter::operator ++ (){           Node*       node   = (Node*) MAKE_SHM_PTR(_nodeOffset);    Bucket*     bucket = (Bucket*) MAKE_SHM_PTR(_bucketOffset);        if (node->_nextOffset == MAKE_SHM_OFF(&(bucket->_nodeList)))    {        _bucketOffset = bucket->_bucketList._nextOffset;        bucket        = (Bucket*) MAKE_SHM_PTR(_bucketOffset);        _nodeOffset   = bucket->_nodeList._nextOffset;        return *this;    }    else    {           _nodeOffset  = node->_nextOffset;        return *this;    }}void ShmHash::Attach(char* mem_addr, int is_created){        // ------------------------------------------------------------    //  magic number | elem_size | size | bucket list | bucket entries.    // ------------------------------------------------------------    ShmHashHead*    hash_head = NULL;        _location       = mem_addr;    hash_head       = (ShmHashHead*) _location;                        _magicNumberPtr = &(hash_head->_magicNumber);    _elemSizePtr    = &(hash_head->_elemSize);    _size           = &(hash_head->_size);    _listLocation   = &(hash_head->_buffList);        _bucketList     = &(hash_head->_bucketList);    _bucketEntries  = &(hash_head->_firstEntry);       _nodeBuffList.Attach((char*) _listLocation, is_created);        if (is_created == 1)    {        Init();    }    else    {    	printf("Attached, magic = %d, elem size = %d, size = %d\n",    		*_magicNumberPtr, *_elemSizePtr, *_size);    }}void ShmHash::Init(){    int     i        = 0;    int     list_off = 0;    int     node_off = 0;        *_magicNumberPtr = _magicNumber;    *_elemSizePtr    = _elemSize;	printf("Created, magic = %d, elem size = %d, size = %d\n",		*_magicNumberPtr, *_elemSizePtr, *_size);        for (i = 0; i < *_magicNumberPtr; i++)    {        LoopBucket(&_bucketEntries[i]);    }        list_off = MAKE_SHM_OFF(_bucketList);    node_off = MAKE_SHM_OFF(&(_bucketList->_nodeList));        _bucketList->_bucketList._nextOffset =         _bucketList->_bucketList._prevOffset = list_off;        _bucketList->_nodeList._nextOffset =         _bucketList->_nodeList._prevOffset = node_off;      }void ShmHash::LoopBucket(ShmHashBucket* bucket){    ShmOffset   list_off = MAKE_SHM_OFF(&bucket->_bucketList);    ShmOffset   node_off = MAKE_SHM_OFF(&bucket->_nodeList);        bucket->_bucketList._prevOffset = list_off;    bucket->_bucketList._prevOffset = list_off;              bucket->_nodeList._prevOffset   = node_off;    bucket->_nodeList._nextOffset   = node_off;           }int ShmHash::BaseSpace(const int magic){    return sizeof(ShmHashHead) + sizeof(ShmHashBucket) * (magic - 1);}    ShmHashIter ShmHash::search(int k, int& flag){       int         offset    = 0;      Bucket*     bucket    = NULL;    Node*       head_node = NULL;    Node*       tail_node = NULL;    Node*       node      = NULL;            offset = k % (*_magicNumberPtr);    bucket = &_bucketEntries[offset];    head_node = &(bucket->_nodeList);    // Go through the node list        for (node = (Node*) MAKE_SHM_PTR (head_node->_nextOffset);         node != head_node;         node = (Node*) MAKE_SHM_PTR (node->_nextOffset))    {                if (_matchCallback(node))        {            flag = HASH_FOUND;            return iterator(MAKE_SHM_OFF(node), MAKE_SHM_OFF(bucket));        }            }    if (flag == HASH_FIND)    {        flag = HASH_NOT_FOUND;        return end();    }        if (head_node->_nextOffset == MAKE_SHM_OFF(head_node))    {        LinkBucketToList(bucket);    }        if (_nodeBuffList.size() > 0)    {        node = (Node*) _nodeBuffList.pop_front();         }    else    {        node = (Node*) _allocCallback(*_elemSizePtr);    }        offset = MAKE_SHM_OFF(node);    // Insert this new node into node list from tail        node->_nextOffset = MAKE_SHM_OFF(head_node);                          node->_prevOffset = head_node->_prevOffset;    tail_node = (Node*) MAKE_SHM_PTR(head_node->_prevOffset);    head_node->_prevOffset = offset;            tail_node->_nextOffset = offset;            flag = HASH_NEW;        return iterator(offset, MAKE_SHM_OFF(bucket));  }ShmHashIter ShmHash::erase(ShmHashIter& it){    Bucket*     bucket    = (Bucket*) MAKE_SHM_PTR(it._bucketOffset);    Node*       head_node = &(bucket->_nodeList);    Node*       node      = (Node*) MAKE_SHM_PTR(it._nodeOffset);    Node*       prev_node = (Node*) MAKE_SHM_PTR(node->_prevOffset);    Node*       next_node = (Node*) MAKE_SHM_PTR(node->_nextOffset);        prev_node->_nextOffset = node->_nextOffset;    next_node->_prevOffset = node->_prevOffset;     /*     *  If this bucket becomes empty, remove it from bucket list     */    if (head_node->_nextOffset == MAKE_SHM_OFF(head_node))    {                    bucket    = RemoveBucketFromList(bucket);               head_node = &(bucket->_nodeList);        if (_freeCallback != NULL)        {            _freeCallback(node);        }        else        {            _nodeBuffList.push_back((ShmOListElem*) node);        }                return iterator(head_node->_nextOffset, MAKE_SHM_OFF(bucket));    }    /*     *  If the removed node is the last one of this bucket,      *  return the first node of next bucket.     */        else if (next_node == head_node)    {                bucket    = (Bucket*) MAKE_SHM_PTR(bucket->_bucketList._nextOffset);        head_node = &(bucket->_nodeList);                 _freeCallback(node);        return iterator(head_node->_nextOffset, MAKE_SHM_OFF(bucket));    }                    _freeCallback(node);    return iterator(MAKE_SHM_OFF(next_node), MAKE_SHM_OFF(bucket));}void ShmHash::LinkBucketToList(ShmHashBucket* bucket){    Bucket*     prev_bucket = NULL;    Bucket*     temp_bucket = NULL;        // Insert this node into bucket list from tail        bucket->_bucketList._nextOffset = MAKE_SHM_OFF(_bucketList);    bucket->_bucketList._prevOffset = _bucketList->_bucketList._prevOffset;            prev_bucket = (Bucket*) MAKE_SHM_PTR(_bucketList->_bucketList._prevOffset);            _bucketList->_bucketList._prevOffset =         prev_bucket->_bucketList._nextOffset = MAKE_SHM_OFF(bucket);    temp_bucket = _bucketList;}ShmHashBucket* ShmHash::RemoveBucketFromList(ShmHashBucket* bucket){    Bucket*     prev_list = (Bucket*) MAKE_SHM_PTR(bucket->_bucketList._prevOffset);    Bucket*     next_list = (Bucket*) MAKE_SHM_PTR(bucket->_bucketList._nextOffset);        prev_list->_bucketList._nextOffset = bucket->_bucketList._nextOffset;    next_list->_bucketList._prevOffset = bucket->_bucketList._prevOffset;        bucket->_bucketList._nextOffset    = bucket->_bucketList._prevOffset = 0;    return next_list;}void ShmHash::clear(){    for (iterator it = begin(); it != end(); )    {        it = erase(it);    }}