From b21162cf8e06f40baa1f58be6a8c17435cebc34d Mon Sep 17 00:00:00 2001 From: weidai Date: Fri, 4 Oct 2002 17:31:41 +0000 Subject: Initial revision git-svn-id: svn://svn.code.sf.net/p/cryptopp/code/trunk/c5@2 57ff6487-cd31-0410-9ec3-f628ee90f5f0 --- queue.cpp | 518 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 518 insertions(+) create mode 100644 queue.cpp (limited to 'queue.cpp') diff --git a/queue.cpp b/queue.cpp new file mode 100644 index 0000000..a01e213 --- /dev/null +++ b/queue.cpp @@ -0,0 +1,518 @@ +// queue.cpp - written and placed in the public domain by Wei Dai + +#include "pch.h" +#include "queue.h" +#include "filters.h" + +NAMESPACE_BEGIN(CryptoPP) + +// this class for use by ByteQueue only +class ByteQueueNode +{ +public: + ByteQueueNode(unsigned int maxSize) + : buf(maxSize) + { + m_head = m_tail = 0; + next = 0; + } + + inline unsigned int MaxSize() const {return buf.size();} + + inline unsigned int CurrentSize() const + { + return m_tail-m_head; + } + + inline bool UsedUp() const + { + return (m_head==MaxSize()); + } + + inline void Clear() + { + m_head = m_tail = 0; + } + +/* inline unsigned int Put(byte inByte) + { + if (MaxSize()==m_tail) + return 0; + + buf[m_tail++]=inByte; + return 1; + } +*/ + inline unsigned int Put(const byte *begin, unsigned int length) + { + unsigned int l = STDMIN(length, MaxSize()-m_tail); + memcpy(buf+m_tail, begin, l); + m_tail += l; + return l; + } + + inline unsigned int Peek(byte &outByte) const + { + if (m_tail==m_head) + return 0; + + outByte=buf[m_head]; + return 1; + } + + inline unsigned int Peek(byte *target, unsigned int copyMax) const + { + unsigned int len = STDMIN(copyMax, m_tail-m_head); + memcpy(target, buf+m_head, len); + return len; + } + + inline unsigned int CopyTo(BufferedTransformation &target, const std::string &channel=BufferedTransformation::NULL_CHANNEL) const + { + unsigned int len = m_tail-m_head; + target.ChannelPut(channel, buf+m_head, len); + return len; + } + + inline unsigned int CopyTo(BufferedTransformation &target, unsigned int copyMax, const std::string &channel=BufferedTransformation::NULL_CHANNEL) const + { + unsigned int len = STDMIN(copyMax, m_tail-m_head); + target.ChannelPut(channel, buf+m_head, len); + return len; + } + + inline unsigned int Get(byte &outByte) + { + unsigned int len = Peek(outByte); + m_head += len; + return len; + } + + inline unsigned int Get(byte *outString, unsigned int getMax) + { + unsigned int len = Peek(outString, getMax); + m_head += len; + return len; + } + + inline unsigned int TransferTo(BufferedTransformation &target, const std::string &channel=BufferedTransformation::NULL_CHANNEL) + { + unsigned int len = m_tail-m_head; + target.ChannelPutModifiable(channel, buf+m_head, len); + m_head = m_tail; + return len; + } + + inline unsigned int TransferTo(BufferedTransformation &target, unsigned int transferMax, const std::string &channel=BufferedTransformation::NULL_CHANNEL) + { + unsigned int len = STDMIN(transferMax, m_tail-m_head); + target.ChannelPutModifiable(channel, buf+m_head, len); + m_head += len; + return len; + } + + inline unsigned int Skip(unsigned int skipMax) + { + unsigned int len = STDMIN(skipMax, m_tail-m_head); + m_head += len; + return len; + } + + inline byte operator[](unsigned int i) const + { + return buf[m_head+i]; + } + + ByteQueueNode *next; + + SecByteBlock buf; + unsigned int m_head, m_tail; +}; + +// ******************************************************** + +ByteQueue::ByteQueue(unsigned int m_nodeSize) + : m_nodeSize(m_nodeSize), m_lazyLength(0) +{ + m_head = m_tail = new ByteQueueNode(m_nodeSize); +} + +ByteQueue::ByteQueue(const ByteQueue ©) +{ + CopyFrom(copy); +} + +void ByteQueue::CopyFrom(const ByteQueue ©) +{ + m_lazyLength = 0; + m_nodeSize = copy.m_nodeSize; + m_head = m_tail = new ByteQueueNode(*copy.m_head); + + for (ByteQueueNode *current=copy.m_head->next; current; current=current->next) + { + m_tail->next = new ByteQueueNode(*current); + m_tail = m_tail->next; + } + + m_tail->next = NULL; + + Put(copy.m_lazyString, copy.m_lazyLength); +} + +ByteQueue::~ByteQueue() +{ + Destroy(); +} + +void ByteQueue::Destroy() +{ + ByteQueueNode *next; + + for (ByteQueueNode *current=m_head; current; current=next) + { + next=current->next; + delete current; + } +} + +void ByteQueue::IsolatedInitialize(const NameValuePairs ¶meters) +{ + m_nodeSize = parameters.GetIntValueWithDefault("NodeSize", 256); + Clear(); +} + +unsigned long ByteQueue::CurrentSize() const +{ + unsigned long size=0; + + for (ByteQueueNode *current=m_head; current; current=current->next) + size += current->CurrentSize(); + + return size + m_lazyLength; +} + +bool ByteQueue::IsEmpty() const +{ + return m_head==m_tail && m_head->CurrentSize()==0 && m_lazyLength==0; +} + +void ByteQueue::Clear() +{ + Destroy(); + m_head = m_tail = new ByteQueueNode(m_nodeSize); + m_lazyLength = 0; +} + +unsigned int ByteQueue::Put2(const byte *inString, unsigned int length, int messageEnd, bool blocking) +{ + if (m_lazyLength > 0) + FinalizeLazyPut(); + + unsigned int len; + while ((len=m_tail->Put(inString, length)) < length) + { + m_tail->next = new ByteQueueNode(m_nodeSize); + m_tail = m_tail->next; + inString += len; + length -= len; + } + + return 0; +} + +void ByteQueue::CleanupUsedNodes() +{ + while (m_head != m_tail && m_head->UsedUp()) + { + ByteQueueNode *temp=m_head; + m_head=m_head->next; + delete temp; + } + + if (m_head->CurrentSize() == 0) + m_head->Clear(); +} + +void ByteQueue::LazyPut(const byte *inString, unsigned int size) +{ + if (m_lazyLength > 0) + FinalizeLazyPut(); + m_lazyString = inString; + m_lazyLength = size; +} + +void ByteQueue::UndoLazyPut(unsigned int size) +{ + if (m_lazyLength < size) + throw InvalidArgument("ByteQueue: size specified for UndoLazyPut is too large"); + + m_lazyLength -= size; +} + +void ByteQueue::FinalizeLazyPut() +{ + unsigned int len = m_lazyLength; + m_lazyLength = 0; + if (len) + Put(m_lazyString, len); +} + +unsigned int ByteQueue::Get(byte &outByte) +{ + if (m_head->Get(outByte)) + { + if (m_head->UsedUp()) + CleanupUsedNodes(); + return 1; + } + else if (m_lazyLength > 0) + { + outByte = *m_lazyString++; + m_lazyLength--; + return 1; + } + else + return 0; +} + +unsigned int ByteQueue::Get(byte *outString, unsigned int getMax) +{ + ArraySink sink(outString, getMax); + return TransferTo(sink, getMax); +} + +unsigned int ByteQueue::Peek(byte &outByte) const +{ + if (m_head->Peek(outByte)) + return 1; + else if (m_lazyLength > 0) + { + outByte = *m_lazyString; + return 1; + } + else + return 0; +} + +unsigned int ByteQueue::Peek(byte *outString, unsigned int peekMax) const +{ + ArraySink sink(outString, peekMax); + return CopyTo(sink, peekMax); +} + +unsigned int ByteQueue::TransferTo2(BufferedTransformation &target, unsigned long &transferBytes, const std::string &channel, bool blocking) +{ + if (blocking) + { + unsigned long bytesLeft = transferBytes; + for (ByteQueueNode *current=m_head; bytesLeft && current; current=current->next) + bytesLeft -= current->TransferTo(target, bytesLeft, channel); + CleanupUsedNodes(); + + unsigned int len = (unsigned int)STDMIN(bytesLeft, (unsigned long)m_lazyLength); + if (len) + { + target.ChannelPut(channel, m_lazyString, len); + m_lazyString += len; + m_lazyLength -= len; + bytesLeft -= len; + } + transferBytes -= bytesLeft; + return 0; + } + else + { + Walker walker(*this); + unsigned int blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking); + Skip(transferBytes); + return blockedBytes; + } +} + +unsigned int ByteQueue::CopyRangeTo2(BufferedTransformation &target, unsigned long &begin, unsigned long end, const std::string &channel, bool blocking) const +{ + Walker walker(*this); + walker.Skip(begin); + unsigned long transferBytes = end-begin; + unsigned int blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking); + begin += transferBytes; + return blockedBytes; +} + +void ByteQueue::Unget(byte inByte) +{ + Unget(&inByte, 1); +} + +void ByteQueue::Unget(const byte *inString, unsigned int length) +{ + // TODO: make this more efficient + ByteQueueNode *newHead = new ByteQueueNode(length); + newHead->next = m_head; + m_head = newHead; + m_head->Put(inString, length); +} + +const byte * ByteQueue::Spy(unsigned int &contiguousSize) const +{ + contiguousSize = m_head->m_tail - m_head->m_head; + if (contiguousSize == 0 && m_lazyLength > 0) + { + contiguousSize = m_lazyLength; + return m_lazyString; + } + else + return m_head->buf + m_head->m_head; +} + +byte * ByteQueue::CreatePutSpace(unsigned int &size) +{ + if (m_lazyLength > 0) + FinalizeLazyPut(); + + if (m_tail->m_tail == m_tail->MaxSize()) + { + m_tail->next = new ByteQueueNode(size < m_nodeSize ? m_nodeSize : STDMAX(m_nodeSize, 1024U)); + m_tail = m_tail->next; + } + + size = m_tail->MaxSize() - m_tail->m_tail; + return m_tail->buf + m_tail->m_tail; +} + +ByteQueue & ByteQueue::operator=(const ByteQueue &rhs) +{ + Destroy(); + CopyFrom(rhs); + return *this; +} + +bool ByteQueue::operator==(const ByteQueue &rhs) const +{ + const unsigned long currentSize = CurrentSize(); + + if (currentSize != rhs.CurrentSize()) + return false; + + Walker walker1(*this), walker2(rhs); + byte b1, b2; + + while (walker1.Get(b1) && walker2.Get(b2)) + if (b1 != b2) + return false; + + return true; +} + +byte ByteQueue::operator[](unsigned long i) const +{ + for (ByteQueueNode *current=m_head; current; current=current->next) + { + if (i < current->CurrentSize()) + return (*current)[i]; + + i -= current->CurrentSize(); + } + + assert(i < m_lazyLength); + return m_lazyString[i]; +} + +void ByteQueue::swap(ByteQueue &rhs) +{ + std::swap(m_nodeSize, rhs.m_nodeSize); + std::swap(m_head, rhs.m_head); + std::swap(m_tail, rhs.m_tail); + std::swap(m_lazyString, rhs.m_lazyString); + std::swap(m_lazyLength, rhs.m_lazyLength); +} + +// ******************************************************** + +void ByteQueue::Walker::IsolatedInitialize(const NameValuePairs ¶meters) +{ + m_node = m_queue.m_head; + m_position = 0; + m_offset = 0; + m_lazyString = m_queue.m_lazyString; + m_lazyLength = m_queue.m_lazyLength; +} + +unsigned int ByteQueue::Walker::Get(byte &outByte) +{ + ArraySink sink(&outByte, 1); + return TransferTo(sink, 1); +} + +unsigned int ByteQueue::Walker::Get(byte *outString, unsigned int getMax) +{ + ArraySink sink(outString, getMax); + return TransferTo(sink, getMax); +} + +unsigned int ByteQueue::Walker::Peek(byte &outByte) const +{ + ArraySink sink(&outByte, 1); + return CopyTo(sink, 1); +} + +unsigned int ByteQueue::Walker::Peek(byte *outString, unsigned int peekMax) const +{ + ArraySink sink(outString, peekMax); + return CopyTo(sink, peekMax); +} + +unsigned int ByteQueue::Walker::TransferTo2(BufferedTransformation &target, unsigned long &transferBytes, const std::string &channel, bool blocking) +{ + unsigned long bytesLeft = transferBytes; + unsigned int blockedBytes = 0; + + while (m_node) + { + unsigned int len = STDMIN(bytesLeft, (unsigned long)m_node->CurrentSize()-m_offset); + blockedBytes = target.ChannelPut2(channel, m_node->buf+m_node->m_head+m_offset, len, 0, blocking); + + if (blockedBytes) + goto done; + + m_position += len; + bytesLeft -= len; + + if (!bytesLeft) + { + m_offset += len; + goto done; + } + + m_node = m_node->next; + m_offset = 0; + } + + if (bytesLeft && m_lazyLength) + { + unsigned int len = (unsigned int)STDMIN(bytesLeft, (unsigned long)m_lazyLength); + unsigned int blockedBytes = target.ChannelPut2(channel, m_lazyString, len, 0, blocking); + if (blockedBytes) + goto done; + + m_lazyString += len; + m_lazyLength -= len; + bytesLeft -= len; + } + +done: + transferBytes -= bytesLeft; + return blockedBytes; +} + +unsigned int ByteQueue::Walker::CopyRangeTo2(BufferedTransformation &target, unsigned long &begin, unsigned long end, const std::string &channel, bool blocking) const +{ + Walker walker(*this); + walker.Skip(begin); + unsigned long transferBytes = end-begin; + unsigned int blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking); + begin += transferBytes; + return blockedBytes; +} + +NAMESPACE_END -- cgit v1.2.1