(svn r20510) -Codechange: unify packet queue handling and make insertion O(1) instead of O(n)

4 files changed, 72 insertions, 36 deletions

diff --git a/src/network/core/tcp_game.cpp b/src/network/core/tcp_game.cpp
index 8044ef138..66a1b6f81 100644
--- a/src/network/core/tcp_game.cpp
+++ b/src/network/core/tcp_game.cpp
@@ -36,12 +36,6 @@ NetworkClientSocket::NetworkClientSocket(ClientID client_id)
 
 NetworkClientSocket::~NetworkClientSocket()
 {
-	while (this->command_queue != NULL) {
-		CommandPacket *p = this->command_queue->next;
-		free(this->command_queue);
-		this->command_queue = p;
-	}
-
 	if (_redirect_console_to_client == this->client_id) _redirect_console_to_client = INVALID_CLIENT_ID;
 	this->client_id = INVALID_CLIENT_ID;
 	this->status = STATUS_INACTIVE;
diff --git a/src/network/core/tcp_game.h b/src/network/core/tcp_game.h
index 70a261d08..d6952d1bf 100644
--- a/src/network/core/tcp_game.h
+++ b/src/network/core/tcp_game.h
@@ -74,6 +74,22 @@ enum TCPPacketType {
 /** Packet that wraps a command */
 struct CommandPacket;
 
+/** A queue of CommandPackets. */
+class CommandQueue {
+	CommandPacket *first; ///< The first packet in the queue.
+	CommandPacket *last;  ///< The last packet in the queue; only valid when first != NULL.
+
+public:
+	/** Initialise the command queue. */
+	CommandQueue() : first(NULL), last(NULL) {}
+	/** Clear the command queue. */
+	~CommandQueue() { this->Free(); }
+	void Append(CommandPacket *p);
+	CommandPacket *Pop();
+	CommandPacket *Peek();
+	void Free();
+};
+
 /** Status of a client */
 enum ClientStatus {
 	STATUS_INACTIVE,     ///< The client is not connected nor active
@@ -106,7 +122,7 @@ public:
 
 	ClientStatus status;      ///< Status of this client
 
-	CommandPacket *command_queue; ///< The command-queue awaiting delivery
+	CommandQueue command_queue; ///< The command-queue awaiting delivery
 
 	NetworkRecvStatus CloseConnection(bool error = true);
 
diff --git a/src/network/network_command.cpp b/src/network/network_command.cpp
index 39eae0f94..8c550338c 100644
--- a/src/network/network_command.cpp
+++ b/src/network/network_command.cpp
@@ -52,8 +52,53 @@ static CommandCallback * const _callback_table[] = {
 	/* 0x19 */ CcStartStopVehicle,
 };
 
+/**
+ * Append a CommandPacket at the end of the queue.
+ * @param p The packet to append to the queue.
+ */
+void CommandQueue::Append(CommandPacket *p)
+{
+	assert(p != NULL);
+	if (this->first == NULL) {
+		this->first = p;
+	} else {
+		this->last->next = p;
+	}
+	this->last = p;
+}
+
+/**
+ * Return the first item in the queue and remove it from the queue.
+ * @return the first item in the queue.
+ */
+CommandPacket *CommandQueue::Pop()
+{
+	CommandPacket *ret = this->first;
+	if (ret != NULL) this->first = this->first->next;
+	return ret;
+}
+
+/**
+ * Return the first item in the queue, but don't remove it.
+ * @return the first item in the queue.
+ */
+CommandPacket *CommandQueue::Peek()
+{
+	return this->first;
+}
+
+/** Free everything that is in the queue. */
+void CommandQueue::Free()
+{
+	CommandPacket *cp;
+	while ((cp = this->Pop()) != NULL) {
+		free(cp);
+	}
+}
+
+
 /** Local queue of packets */
-static CommandPacket *_local_command_queue = NULL;
+static CommandQueue _local_command_queue;
 
 /**
  * Add a command to the local or client socket command queue,
@@ -65,16 +110,7 @@ void NetworkAddCommandQueue(CommandPacket cp, NetworkClientSocket *cs)
 {
 	CommandPacket *new_cp = MallocT<CommandPacket>(1);
 	*new_cp = cp;
-
-	CommandPacket **begin = (cs == NULL ? &_local_command_queue : &cs->command_queue);
-
-	if (*begin == NULL) {
-		*begin = new_cp;
-	} else {
-		CommandPacket *c = *begin;
-		while (c->next != NULL) c = c->next;
-		c->next = new_cp;
-	}
+	(cs == NULL ? _local_command_queue : cs->command_queue).Append(new_cp);
 }
 
 /**
@@ -141,7 +177,7 @@ void NetworkSend_Command(TileIndex tile, uint32 p1, uint32 p2, uint32 cmd, Comma
  */
 void NetworkSyncCommandQueue(NetworkClientSocket *cs)
 {
-	for (CommandPacket *p = _local_command_queue; p != NULL; p = p->next) {
+	for (CommandPacket *p = _local_command_queue.Peek(); p != NULL; p = p->next) {
 		CommandPacket c = *p;
 		c.callback = 0;
 		c.next = NULL;
@@ -156,26 +192,24 @@ void NetworkExecuteLocalCommandQueue()
 {
 	assert(IsLocalCompany());
 
-	while (_local_command_queue != NULL) {
-
+	CommandPacket *cp;
+	while ((cp = _local_command_queue.Peek()) != NULL) {
 		/* The queue is always in order, which means
 		 * that the first element will be executed first. */
-		if (_frame_counter < _local_command_queue->frame) break;
+		if (_frame_counter < cp->frame) break;
 
-		if (_frame_counter > _local_command_queue->frame) {
+		if (_frame_counter > cp->frame) {
 			/* If we reach here, it means for whatever reason, we've already executed
 			 * past the command we need to execute. */
 			error("[net] Trying to execute a packet in the past!");
 		}
 
-		CommandPacket *cp = _local_command_queue;
-
 		/* We can execute this command */
 		_current_company = cp->company;
 		cp->cmd |= CMD_NETWORK_COMMAND;
 		DoCommandP(cp, cp->my_cmd);
 
-		_local_command_queue = _local_command_queue->next;
+		_local_command_queue.Pop();
 		free(cp);
 	}
 
@@ -188,12 +222,7 @@ void NetworkExecuteLocalCommandQueue()
  */
 void NetworkFreeLocalCommandQueue()
 {
-	/* Free all queued commands */
-	while (_local_command_queue != NULL) {
-		CommandPacket *p = _local_command_queue;
-		_local_command_queue = _local_command_queue->next;
-		free(p);
-	}
+	_local_command_queue.Free();
 }
 
 /**
diff --git a/src/network/network_server.cpp b/src/network/network_server.cpp
index bd01d9300..d2f3ce3ab 100644
--- a/src/network/network_server.cpp
+++ b/src/network/network_server.cpp
@@ -1618,11 +1618,8 @@ void NetworkServer_ReadPackets(NetworkClientSocket *cs)
 static void NetworkHandleCommandQueue(NetworkClientSocket *cs)
 {
 	CommandPacket *cp;
-
-	while ( (cp = cs->command_queue) != NULL) {
+	while ((cp = cs->command_queue.Pop()) != NULL) {
 		SEND_COMMAND(PACKET_SERVER_COMMAND)(cs, cp);
-
-		cs->command_queue = cp->next;
 		free(cp);
 	}
 }