gqueue.cpp

一个非常有用的开源代码

/*
	Copyright (C) 2006, Mike Gashler

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	see http://www.gnu.org/copyleft/lesser.html
*/

#include "GQueue.h"
#include "GMacros.h"
#include <cassert>
#include <stdlib.h>

GQueue::GQueue(int nChunkSize)
{
	GAssert(nChunkSize > 4, "too small");
#ifdef WIN32
	GAssert(sizeof(wchar_t) == 2, "wrong size");
#else
	GAssert(sizeof(wchar_t) == 4, "wrong size");
#endif // !WIN32
	m_nDefaultChunkSize = nChunkSize;
	m_nInPos = nChunkSize;
	m_nOutPos = 0;
	m_pFirstChunk = NULL;
	m_pLastChunk = NULL;
	m_nDataSize = 0;
	m_pExtra = NULL;
}

GQueue::~GQueue()
{
	while(m_pFirstChunk)
		delete(UnlinkFirst());
	delete(m_pExtra);
}

void GQueue::Link(GQueueChunk* pChunk)
{
	GAssert(!pChunk->m_pNext, "Already linked");
	if(m_pLastChunk)
	{
		GAssert(!m_pLastChunk->m_pNext, "not really the last one");
		m_pLastChunk->m_pNext = pChunk;
		m_pLastChunk = pChunk;
	}
	else
	{
		GAssert(!m_pFirstChunk, "Linked list messed up");
		m_pFirstChunk = pChunk;
		m_pLastChunk = pChunk;
	}
}

GQueueChunk* GQueue::UnlinkFirst()
{
	GQueueChunk* pChunk = m_pFirstChunk;
	m_pFirstChunk = pChunk->m_pNext;
	if(!m_pFirstChunk)
		m_pLastChunk = NULL;
	pChunk->m_pNext = NULL;
	return pChunk;
}

void GQueue::DropFirstChunk()
{
	delete(m_pExtra);
	m_pExtra = UnlinkFirst();
	m_nOutPos = 0;
}

GQueueChunk* GQueue::MakeNewChunk(int nMinSize)
{
	if(m_pLastChunk)
		m_pLastChunk->m_nSize = m_nInPos;
	if(m_pExtra && m_pExtra->m_bDelete)
	{
		Link(m_pExtra);
		m_pExtra = NULL;
	}
	else
		Link(new GQueueChunk(MAX(nMinSize, m_nDefaultChunkSize), NULL));
	m_nInPos = 0;
	return m_pLastChunk;
}

void GQueue::Flush()
{
	while(m_pFirstChunk)
		DropFirstChunk();
	m_nInPos = 0;
	m_nOutPos = 0;
	m_nDataSize = 0;
}

void GQueue::PushStatic(const unsigned char* pBuf, int nBufSize)
{
	GQueueChunk* pCurrentChunk = m_pLastChunk;
	if(pCurrentChunk)
		pCurrentChunk->m_nSize = m_nInPos;
	if(m_pExtra && !m_pExtra->m_bDelete)
	{
		pCurrentChunk = m_pExtra;
		m_pExtra = NULL;
		pCurrentChunk->m_pData = (unsigned char*)pBuf;
		pCurrentChunk->m_nSize = nBufSize;
	}
	else
		pCurrentChunk = new GQueueChunk(nBufSize, pBuf);
	Link(pCurrentChunk);
	m_nInPos = nBufSize;
	m_nDataSize += nBufSize;
}

char* GQueue::DumpToString()
{
	int nSize = m_nDataSize;
	char* szStr = new char[nSize + 1];
	Pop((unsigned char*)szStr, nSize);
	szStr[nSize] = '\0';
	return szStr;
}

void GQueue::Poke(int nIndex, const unsigned char* pBuf, int nLen)
{
	while(m_nDataSize < nIndex)
		Push('\0');
	GQueueChunk* pCurrentChunk = m_pFirstChunk;
	while(nIndex >= pCurrentChunk->m_nSize)
	{
		nIndex -= pCurrentChunk->m_nSize;
		pCurrentChunk = pCurrentChunk->m_pNext;
	}
	while(true)
	{
		int nPart = MIN(pCurrentChunk->m_nSize - nIndex, nLen);
		memcpy(&pCurrentChunk->m_pData[nIndex], pBuf, nPart);
		nLen -= nPart;
		if(nLen <= 0)
			return;
        pBuf += nIndex;
		pCurrentChunk = pCurrentChunk->m_pNext;
		nIndex = 0;
	}
}

#ifndef NO_TEST_CODE
// static
void GQueue::Test()
{
	GQueue queue(1025);
	int nIn = 0;
	int nOut = 0;
	char c;
	for(nIn = 0; nIn < 250611; nIn++)
	{
		queue.Push((char)nIn);
		if((rand() * 8 / RAND_MAX) == 0)
		{
			queue.Pop(&c);
			if(c != (char)nOut)
				throw "wrong answer";
			nOut++;
		}
	}
	while(nOut < 250611)
	{
		queue.Pop(&c);
		if(c != (char)nOut)
			throw "wrong answer";
		nOut++;
	}
}
#endif // NO_TEST_CODE