--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/sources/network/packetqueue.cpp Sat Jul 23 12:28:52 2016 +0300
@@ -0,0 +1,154 @@
+/*
+ Copyright 2016 Teemu Piippo
+ All rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions
+ are met:
+
+ 1. Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+ 2. Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in the
+ documentation and/or other materials provided with the distribution.
+ 3. Neither the name of the copyright holder nor the names of its
+ contributors may be used to endorse or promote products derived from
+ this software without specific prior written permission.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER
+ OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#include <algorithm>
+#include "packetqueue.h"
+BEGIN_ZFC_NAMESPACE
+
+/*!
+ * \brief Constructs an empty packet queue.
+ */
+PacketQueue::PacketQueue() :
+ m_currentSequenceNumber(0) {}
+
+/*!
+ * \brief Inserts the packet into the queue, unless the packet is the next packet to be processed.
+ * \param sequenceNumber Sequence number of the packet.
+ * \param data Payload of the packet.
+ * \return True, if the packet was stored, false if the packet should be processed immediately.
+ */
+bool PacketQueue::addPacket(unsigned int sequenceNumber, const ByteArray& data)
+{
+ // Check whether this packet is the one we're supposed to process next.
+ if (sequenceNumber != m_currentSequenceNumber)
+ {
+ // It is not, therefore store it for later.
+ m_queue[sequenceNumber] = data;
+ return true;
+ }
+ else
+ {
+ // It is, therefore the caller processes it, and we can advance to the next packet right away.
+ m_currentSequenceNumber = getNextSequenceNumber();
+ return false;
+ }
+}
+
+/*!
+ * \returns whether there are packets in queue that cannot be processed due to missing in-between packets. If true, the
+ * \returns caller should initiate packet recovery protocol.
+ */
+bool PacketQueue::isStuck() const
+{
+ return m_queue.size() > 0 and m_queue.find(m_currentSequenceNumber) == m_queue.end();
+}
+
+/*!
+ * \returns whether or not there are packets awaiting processing.
+ */
+bool PacketQueue::hasPacketsToPop() const
+{
+ return m_queue.size() > 0 and m_queue.find(m_currentSequenceNumber) != m_queue.end();
+}
+
+/*!
+ * \brief Retrieves the next packet to be processed, and removes it from the queue.
+ * \param packet Reference to a byte array to store the packet payload into.
+ * \returns whether the next packet was successfully popped from the queue, or not.
+ */
+bool PacketQueue::popNextPacket(ByteArray& packet)
+{
+ // Find the packet matching our current sequence number.
+ auto iterator = m_queue.find(m_currentSequenceNumber);
+
+ if (iterator != m_queue.end())
+ {
+ // We found the packet we were looking for. Pass it to the caller.
+ packet = iterator->second;
+ // Remove the packet from the queue.
+ m_queue.erase(iterator);
+ // We can now advance to the next packet.
+ m_currentSequenceNumber = getNextSequenceNumber();
+ return true;
+ }
+ else
+ {
+ // We did not find the next packet.
+ return false;
+ }
+}
+
+/*!
+ * \returns the sequence number for the next packet.
+ */
+int PacketQueue::getNextSequenceNumber() const
+{
+ return (m_currentSequenceNumber + 1) % 1024;
+}
+
+/*!
+ * \returns a list of packets that have to be requested from the server.
+ */
+std::set<int> PacketQueue::getLostPackets() const
+{
+ std::set<int> packetsNeeded;
+ std::set<int> packetsInQueue;
+
+ // Build the set of packet numbers we currently have.
+ for (auto pair : m_queue)
+ packetsInQueue.insert(pair.first);
+
+ // Build the set of packets we wish to process. To do this we need the smallest and largest numbers in
+ // packetsInQueue.
+ Range<int> packetRange(min(packetsInQueue), max(packetsInQueue));
+
+ for (int i : packetRange)
+ packetsNeeded.insert(i);
+
+ // The set of lost packets is now the set of packets we want, minus the packets we have.
+ std::set<int> packetsLost;
+ std::set_difference(packetsNeeded.begin(), packetsNeeded.end(),
+ packetsInQueue.begin(), packetsInQueue.end(),
+ std::inserter(packetsLost, packetsLost.begin()));
+ return packetsLost;
+}
+
+std::set<unsigned int> PacketQueue::getWaitingPackets() const
+{
+ std::set<unsigned int> packetsInQueue;
+
+ // Build the set of packet numbers we currently have.
+ for (auto pair : m_queue)
+ packetsInQueue.insert(pair.first);
+
+ return packetsInQueue;
+}
+
+END_ZFC_NAMESPACE