shm_list.cpp

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

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

#include <stdlib.h>
#include <stdio.h>
#include "shm_list.h"

/*****************************************************************
// 
// Based on the current node, get the next node in a dlist 
// 
******************************************************************/ 

ShmListIter& ShmListIter::operator ++ ()
{   
    _prev = _node;
    
    if (_node->_nextOffset == 0)
    {
        _node = (ShmOListElem*) 0;
    }
    else
    {
        _node = (ShmOListElem*) MAKE_SHM_PTR(_node->_nextOffset);
    }
    
    return *this;
}
    
/*****************************************************************
// 
// Calculate the size of memory which a ShmList needed.
// 
******************************************************************/ 
    
int ShmList::BaseSpace()
{
    return sizeof(ShmListHead);
}

/*****************************************************************
// 
// Attach to a shared memory
// 
******************************************************************/ 

void ShmList::Attach(char* mem_addr, int flag)
{
    // ------------------------------------------------------------
    //  size (int) | list head (including prevOffset and nextOffset)
    // ------------------------------------------------------------
    ShmListHead*    list_head = NULL;
    
    _location = mem_addr;
    list_head = (ShmListHead*) _location;
    
    _size     = &(list_head->_size);
    _listHead = &(list_head->_listHead);
    _listTail = &(list_head->_listTail);
    
    if (flag == 1)
    {
        Init();
    } 
}
    
/*****************************************************************
// 
// 这个函数只能被执行一次。
// 
******************************************************************/     
void ShmList::Init()
{                
    _listHead->_nextOffset = 0;
    _listTail->_nextOffset = 0;
    *_size                 = 0;
}

/*****************************************************************
// 
// 将一个节点从链表的“头”插入一个节点
// 
******************************************************************/ 

void ShmList::push_back(ShmOListElem* node)
{
    ShmOListElem*   tail = 0;
    
    node->_nextOffset = 0;
    
    if (_listTail->_nextOffset == 0)
    {
        _listHead->_nextOffset = _listTail->_nextOffset = MAKE_SHM_OFF(node);
    }        
    else
    {
        tail = (ShmOListElem*) MAKE_SHM_PTR (_listTail->_nextOffset);
        _listTail->_nextOffset = tail->_nextOffset = MAKE_SHM_OFF(node);            
    }
    
    (*_size)++;
}

/*****************************************************************
// 
// 将一个节点从链表的“尾”插入一个节点
// 
******************************************************************/

void ShmList::push_front(ShmOListElem* node)
{
    ShmOListElem*   head = 0;

    node->_nextOffset = 0;
    
    if (_listHead->_nextOffset == 0)
    {
        _listHead->_nextOffset = _listTail->_nextOffset = MAKE_SHM_OFF(node);
    }        
    else
    {
        head = (ShmOListElem*) MAKE_SHM_PTR (_listHead->_nextOffset);
        node->_nextOffset = _listHead->_nextOffset;
        _listHead->_nextOffset = MAKE_SHM_OFF(node);            
    }
    
    (*_size)++;
}

/*****************************************************************
// 
// 将一个节点从链表的“头”插入一个子链表所有节点
// 
******************************************************************/ 

void ShmList::push_back(ShmList& input_list)
{
    ShmOListElem*   tail = 0;
        
    if (input_list.size() == 0)
    {
        return;
    }
        
    if (_listTail->_nextOffset == 0)
    {
        _listHead->_nextOffset = input_list._listHead->_nextOffset;
        _listTail->_nextOffset = input_list._listTail->_nextOffset;
    }        
    else
    {
        tail = (ShmOListElem*) MAKE_SHM_PTR (_listTail->_nextOffset);
        tail->_nextOffset = input_list._listHead->_nextOffset;
        _listTail->_nextOffset = input_list._listTail->_nextOffset;      
    }
    
    (*_size) += input_list.size();
}

/*****************************************************************
// 
// 将一个节点从链表的“尾”插入一个子链表的所有节点
// 
******************************************************************/
void ShmList::push_front(ShmList& input_list)
{
    ShmOListElem*   head = 0;
    ShmOListElem*   tail = 0;
    
    if (input_list.size() == 0)
    {
        return;
    }
    
    if (_listHead->_nextOffset == 0)
    {
        _listHead->_nextOffset = input_list._listHead->_nextOffset;
        _listTail->_nextOffset = input_list._listTail->_nextOffset;
    }        
    else
    {
        tail = (ShmOListElem*) (input_list._listTail->_nextOffset);
        tail->_nextOffset = _listHead->_nextOffset;         
        _listHead->_nextOffset = input_list._listHead->_nextOffset;            
    }
    
    (*_size) += input_list.size();
}

/*****************************************************************
// 
// 将一个节点从链表的“尾”插入一个子链表的所有节点, 并清空子链表
// 
******************************************************************/

void ShmList::transfer_back(ShmList& input_list)
{
    push_back(input_list);
    input_list.Init();    
}

/*****************************************************************
// 
// 将一个节点从链表的“头”插入一个子链表的所有节点, 并清空子链表
// 
******************************************************************/

void ShmList::transfer_front(ShmList& input_list)
{
    push_front(input_list);
    input_list.Init();    
}

/*****************************************************************
// 
// Delete a node from ShmDList
// 
******************************************************************/ 

ShmListIter ShmList::erase(ShmListIter& it)
{
    ShmOListElem*   node     = NULL;
    int             node_off = MAKE_SHM_OFF(it._node);

    if (it._node == 0)
    {
        return iterator();
    }
    
    (*_size)--;

    if (*_size == 0)
    {
        _listHead->_nextOffset = _listTail->_nextOffset = 0;
        
        return iterator();
    }

    if (node_off == _listHead->_nextOffset)
    {
        _listHead->_nextOffset = it._node->_nextOffset;
        it._node->_nextOffset = 0;
        
        return iterator((ShmOListElem*) MAKE_SHM_PTR(_listHead->_nextOffset)); 
    }
    else if (node_off == _listTail->_nextOffset)
    {
        _listTail->_nextOffset = MAKE_SHM_OFF(it._prev);
        it._prev->_nextOffset = 0;
        return iterator();
    }
    else
    {
        it._prev->_nextOffset = it._node->_nextOffset;
        node = (ShmOListElem*) MAKE_SHM_PTR(it._node->_nextOffset);
        it._node->_nextOffset = 0;
        return iterator(it._prev, node); 
    }    
    
    return iterator();
}

/*****************************************************************
// 
// As its name, it is used to delete all the nodes from a ShmDList
// 
******************************************************************/ 

void ShmList::clear()
{
    for (iterator it = begin(); it != end(); )
    {
        it = erase(it);
    }
}

/*****************************************************************
// 
// 从链表的头取出一个节点，并将节点和链表断开
// 
******************************************************************/ 

ShmOListElem* ShmList::pop_front()
{
    iterator        it   = NULL;
    ShmOListElem*   elem = NULL;

    if (size() == 0)
    {
        return NULL;
    }
    
    it   = begin();
    elem = (ShmOListElem*) (*it);
    
    erase(it);
    
    return elem;
}