queue.h

// queue.h - originally written and placed in the public domain by Wei Dai

/// \file
/// \brief Classes for an unlimited queue to store bytes

#ifndef CRYPTOPP_QUEUE_H
#define CRYPTOPP_QUEUE_H

#include "cryptlib.h"
#include "simple.h"

NAMESPACE_BEGIN(CryptoPP)

class ByteQueueNode;

/// \brief Data structure used to store byte strings
/// \details The queue is implemented as a linked list of byte arrays.
///  Each byte array is stored in a ByteQueueNode.
/// \sa <A HREF="https://www.cryptopp.com/wiki/ByteQueue">ByteQueue</A>
///  on the Crypto++ wiki.
/// \since Crypto++ 2.0
class CRYPTOPP_DLL ByteQueue : public Bufferless<BufferedTransformation>
{
public:
	virtual ~ByteQueue();

	/// \brief Construct a ByteQueue
	/// \param nodeSize the initial node size
	/// \details Internally, ByteQueue uses a ByteQueueNode to store bytes,
	///  and <tt>nodeSize</tt> determines the size of the ByteQueueNode. A value
	///  of 0 indicates the ByteQueueNode should be automatically sized,
	///  which means a value of 256 is used.
	ByteQueue(size_t nodeSize=0);

	/// \brief Copy construct a ByteQueue
	/// \param copy the other ByteQueue
	ByteQueue(const ByteQueue &copy);

	// BufferedTransformation
	lword MaxRetrievable() const
		{return CurrentSize();}
	bool AnyRetrievable() const
		{return !IsEmpty();}

	void IsolatedInitialize(const NameValuePairs &parameters);
	byte * CreatePutSpace(size_t &size);
	size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking);

	size_t Get(byte &outByte);
	size_t Get(byte *outString, size_t getMax);

	size_t Peek(byte &outByte) const;
	size_t Peek(byte *outString, size_t peekMax) const;

	size_t TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true);
	size_t CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true) const;

	/// \brief Set node size
	/// \param nodeSize the new node size, in bytes
	/// \details The default node size is 256.
	void SetNodeSize(size_t nodeSize);

	/// \brief Determine data size
	/// \return the data size, in bytes
	lword CurrentSize() const;

	/// \brief Determine data availability
	/// \return true if the ByteQueue has data, false otherwise
	bool IsEmpty() const;

	/// \brief Empty the queue
	void Clear();

	/// \brief Insert data in the queue
	/// \param inByte a byte to insert
	/// \details Unget() inserts a byte at the head of the queue
	void Unget(byte inByte);

	/// \brief Insert data in the queue
	/// \param inString a byte array to insert
	/// \param length the size of the byte array
	/// \details Unget() inserts a byte array at the head of the queue
	void Unget(const byte *inString, size_t length);

	/// \brief Peek data in the queue
	/// \param contiguousSize the size of the data
	/// \details Spy() peeks at data at the head of the queue. Spy() does
	///  not remove data from the queue.
	/// \details The data's size is returned in <tt>contiguousSize</tt>.
	///  Spy() returns the size of the first byte array in the list. The
	///  entire data may be larger since the queue is a linked list of
	///  byte arrays.
	const byte * Spy(size_t &contiguousSize) const;

	/// \brief Insert data in the queue
	/// \param inString a byte array to insert
	/// \param size the length of the byte array
	/// \details LazyPut() inserts a byte array at the tail of the queue.
	///  The data may not be copied at this point. Rather, the pointer
	///  and size to external data are recorded.
	/// \details Another call to Put() or LazyPut() will force the data to
	///  be copied. When lazy puts are used, the data is copied when
	///  FinalizeLazyPut() is called.
	/// \sa LazyPutter
	void LazyPut(const byte *inString, size_t size);

	/// \brief Insert data in the queue
	/// \param inString a byte array to insert
	/// \param size the length of the byte array
	/// \details LazyPut() inserts a byte array at the tail of the queue.
	///  The data may not be copied at this point. Rather, the pointer
	///  and size to external data are recorded.
	/// \details Another call to Put() or LazyPut() will force the data to
	///  be copied. When lazy puts are used, the data is copied when
	///  FinalizeLazyPut() is called.
	/// \sa LazyPutter
	void LazyPutModifiable(byte *inString, size_t size);

	/// \brief Remove data from the queue
	/// \param size the length of the data
	/// \throw InvalidArgument if there is no lazy data in the queue or if
	///  size is larger than the lazy string
	/// \details UndoLazyPut() truncates data inserted using LazyPut() by
	///  modifying size.
	/// \sa LazyPutter
	void UndoLazyPut(size_t size);

	/// \brief Insert data in the queue
	/// \details FinalizeLazyPut() copies external data inserted using
	///  LazyPut() or LazyPutModifiable() into the tail of the queue.
	/// \sa LazyPutter
	void FinalizeLazyPut();

	/// \brief Assign contents from another ByteQueue
	/// \param rhs the other ByteQueue
	/// \return reference to this ByteQueue
	ByteQueue & operator=(const ByteQueue &rhs);

	/// \brief Bitwise compare two ByteQueue
	/// \param rhs the other ByteQueue
	/// \return true if the size and bits are equal, false otherwise
	/// \details operator==() walks each ByteQueue comparing bytes in
	///  each queue. operator==() is not constant time.
	bool operator==(const ByteQueue &rhs) const;

	/// \brief Bitwise compare two ByteQueue
	/// \param rhs the other ByteQueue
	/// \return true if the size and bits are not equal, false otherwise
	/// \details operator!=() is implemented in terms of operator==().
	///  operator==() is not constant time.
	bool operator!=(const ByteQueue &rhs) const {return !operator==(rhs);}

	/// \brief Retrieve data from the queue
	/// \param index of byte to retrieve
	/// \return byte at the specified index
	/// \details operator[]() does not perform bounds checking.
	byte operator[](lword index) const;

	/// \brief Swap contents with another ByteQueue
	/// \param rhs the other ByteQueue
	void swap(ByteQueue &rhs);

	/// \brief A ByteQueue iterator
	class Walker : public InputRejecting<BufferedTransformation>
	{
	public:
		/// \brief Construct a ByteQueue Walker
		/// \param queue a ByteQueue
		Walker(const ByteQueue &queue)
			: m_queue(queue), m_node(NULLPTR), m_position(0), m_offset(0), m_lazyString(NULLPTR), m_lazyLength(0)
				{Initialize();}

		lword GetCurrentPosition() {return m_position;}

		lword MaxRetrievable() const
			{return m_queue.CurrentSize() - m_position;}

		void IsolatedInitialize(const NameValuePairs &parameters);

		size_t Get(byte &outByte);
		size_t Get(byte *outString, size_t getMax);

		size_t Peek(byte &outByte) const;
		size_t Peek(byte *outString, size_t peekMax) const;

		size_t TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true);
		size_t CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true) const;

	private:
		const ByteQueue &m_queue;
		const ByteQueueNode *m_node;
		lword m_position;
		size_t m_offset;
		const byte *m_lazyString;
		size_t m_lazyLength;
	};

	friend class Walker;

protected:
	void CleanupUsedNodes();
	void CopyFrom(const ByteQueue &copy);
	void Destroy();

private:
	ByteQueueNode *m_head, *m_tail;
	byte *m_lazyString;
	size_t m_lazyLength;
	size_t m_nodeSize;
	bool m_lazyStringModifiable;
	bool m_autoNodeSize;
};

/// \brief Helper class to finalize Puts on ByteQueue
/// \details LazyPutter ensures LazyPut is committed to the ByteQueue
///  in event of exception. During destruction, the LazyPutter class
///  calls FinalizeLazyPut.
class CRYPTOPP_DLL LazyPutter
{
public:
	virtual ~LazyPutter() {
		try {m_bq.FinalizeLazyPut();}
		catch(const Exception&) {CRYPTOPP_ASSERT(0);}
	}

	/// \brief Construct a LazyPutter
	/// \param bq the ByteQueue
	/// \param inString a byte array to insert
	/// \param size the length of the byte array
	/// \details LazyPutter ensures LazyPut is committed to the ByteQueue
	///  in event of exception. During destruction, the LazyPutter class
	///  calls FinalizeLazyPut.
	LazyPutter(ByteQueue &bq, const byte *inString, size_t size)
		: m_bq(bq) {bq.LazyPut(inString, size);}

protected:
	LazyPutter(ByteQueue &bq) : m_bq(bq) {}

private:
	ByteQueue &m_bq;
};

/// \brief Helper class to finalize Puts on ByteQueue
/// \details LazyPutterModifiable ensures LazyPut is committed to the
///  ByteQueue in event of exception. During destruction, the
///  LazyPutterModifiable class calls FinalizeLazyPut.
class LazyPutterModifiable : public LazyPutter
{
public:
	/// \brief Construct a LazyPutterModifiable
	/// \param bq the ByteQueue
	/// \param inString a byte array to insert
	/// \param size the length of the byte array
	/// \details LazyPutterModifiable ensures LazyPut is committed to the
	///  ByteQueue in event of exception. During destruction, the
	///  LazyPutterModifiable class calls FinalizeLazyPut.
	LazyPutterModifiable(ByteQueue &bq, byte *inString, size_t size)
		: LazyPutter(bq) {bq.LazyPutModifiable(inString, size);}
};

NAMESPACE_END

#ifndef __BORLANDC__
NAMESPACE_BEGIN(std)
template<> inline void swap(CryptoPP::ByteQueue &a, CryptoPP::ByteQueue &b)
{
	a.swap(b);
}
NAMESPACE_END
#endif

#endif