shm_hash.cpp

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

/*=================================================================
** 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);
    }
}