use dispatch queues to cut down on array crawling costs

6 files changed, 168 insertions, 81 deletions

diff --git a/host.c b/host.c
index f11ca05..8d07e80 100644
--- a/host.c
+++ b/host.c
@@ -72,13 +72,14 @@ enet_host_create (const ENetAddress * address, size_t peerCount, enet_uint32 inc
     host -> recalculateBandwidthLimits = 0;
     host -> mtu = ENET_HOST_DEFAULT_MTU;
     host -> peerCount = peerCount;
-    host -> lastServicedPeer = host -> peers;
     host -> commandCount = 0;
     host -> bufferCount = 0;
     host -> receivedAddress.host = ENET_HOST_ANY;
     host -> receivedAddress.port = 0;
     host -> receivedDataLength = 0;
      
+    enet_list_clear (& host -> dispatchQueue);
+
     for (currentPeer = host -> peers;
          currentPeer < & host -> peers [host -> peerCount];
          ++ currentPeer)
@@ -92,6 +93,7 @@ enet_host_create (const ENetAddress * address, size_t peerCount, enet_uint32 inc
        enet_list_clear (& currentPeer -> sentUnreliableCommands);
        enet_list_clear (& currentPeer -> outgoingReliableCommands);
        enet_list_clear (& currentPeer -> outgoingUnreliableCommands);
+       enet_list_clear (& currentPeer -> dispatchedCommands);
 
        enet_peer_reset (currentPeer);
     }
diff --git a/include/enet/enet.h b/include/enet/enet.h
index f6fd240..b139976 100644
--- a/include/enet/enet.h
+++ b/include/enet/enet.h
@@ -226,6 +226,7 @@ typedef struct _ENetChannel
  */
 typedef struct _ENetPeer
 { 
+   ENetListNode  dispatchList;
    struct _ENetHost * host;
    enet_uint16   outgoingPeerID;
    enet_uint16   incomingPeerID;
@@ -272,6 +273,8 @@ typedef struct _ENetPeer
    ENetList      sentUnreliableCommands;
    ENetList      outgoingReliableCommands;
    ENetList      outgoingUnreliableCommands;
+   ENetList      dispatchedCommands;
+   int           needsDispatch;
    enet_uint16   incomingUnsequencedGroup;
    enet_uint16   outgoingUnsequencedGroup;
    enet_uint32   unsequencedWindow [ENET_PEER_UNSEQUENCED_WINDOW_SIZE / 32]; 
@@ -303,7 +306,7 @@ typedef struct _ENetHost
    ENetPeer *         peers;                       /**< array of peers allocated for this host */
    size_t             peerCount;                   /**< number of peers allocated for this host */
    enet_uint32        serviceTime;
-   ENetPeer *         lastServicedPeer;
+   ENetList           dispatchQueue;
    int                continueSending;
    size_t             packetSize;
    enet_uint16        headerFlags;
@@ -469,7 +472,7 @@ ENET_API void       enet_host_bandwidth_limit (ENetHost *, enet_uint32, enet_uin
 extern   void       enet_host_bandwidth_throttle (ENetHost *);
 
 ENET_API int                 enet_peer_send (ENetPeer *, enet_uint8, ENetPacket *);
-ENET_API ENetPacket *        enet_peer_receive (ENetPeer *, enet_uint8);
+ENET_API ENetPacket *        enet_peer_receive (ENetPeer *, enet_uint8 * channelID);
 ENET_API void                enet_peer_ping (ENetPeer *);
 ENET_API void                enet_peer_reset (ENetPeer *);
 ENET_API void                enet_peer_disconnect (ENetPeer *, enet_uint32);
diff --git a/include/enet/list.h b/include/enet/list.h
index 99bc4ae..d7b2600 100644
--- a/include/enet/list.h
+++ b/include/enet/list.h
@@ -24,6 +24,7 @@ extern void enet_list_clear (ENetList *);
 
 extern ENetListIterator enet_list_insert (ENetListIterator, void *);
 extern void * enet_list_remove (ENetListIterator);
+extern ENetListIterator enet_list_move (ENetListIterator, void *, void *);
 
 extern size_t enet_list_size (ENetList *);
 
diff --git a/list.c b/list.c
index 1a4aa3a..8487200 100644
--- a/list.c
+++ b/list.c
@@ -40,6 +40,24 @@ enet_list_remove (ENetListIterator position)
    return position;
 }
 
+ENetListIterator
+enet_list_move (ENetListIterator position, void * dataFirst, void * dataLast)
+{
+   ENetListIterator first = (ENetListIterator) dataFirst,
+                    last = (ENetListIterator) dataLast;
+
+   first -> previous -> next = last -> next;
+   last -> next -> previous = first -> previous;
+
+   first -> previous = position -> previous;
+   last -> next = position;
+
+   first -> previous -> next = first;
+   position -> previous = last;
+    
+   return first;
+}
+
 size_t
 enet_list_size (ENetList * list)
 {
diff --git a/peer.c b/peer.c
index 9b4e077..90987a5 100644
--- a/peer.c
+++ b/peer.c
@@ -204,46 +204,21 @@ enet_peer_send (ENetPeer * peer, enet_uint8 channelID, ENetPacket * packet)
 
 /** Attempts to dequeue any incoming queued packet.
     @param peer peer to dequeue packets from
-    @param channelID channel on which to receive
+    @param channelID holds the channel ID of the channel the packet was received on success
     @returns a pointer to the packet, or NULL if there are no available incoming queued packets
 */
 ENetPacket *
-enet_peer_receive (ENetPeer * peer, enet_uint8 channelID)
+enet_peer_receive (ENetPeer * peer, enet_uint8 * channelID)
 {
-   ENetChannel * channel = & peer -> channels [channelID];
-   ENetIncomingCommand * incomingCommand = NULL;
+   ENetIncomingCommand * incomingCommand;
    ENetPacket * packet;
-
-   if (! enet_list_empty (& channel -> incomingUnreliableCommands))
-   {
-      incomingCommand = (ENetIncomingCommand *) enet_list_front (& channel -> incomingUnreliableCommands);
-
-      if ((incomingCommand -> command.header.command & ENET_PROTOCOL_COMMAND_MASK) == ENET_PROTOCOL_COMMAND_SEND_UNRELIABLE)
-      {
-         if (incomingCommand -> reliableSequenceNumber != channel -> incomingReliableSequenceNumber)
-           incomingCommand = NULL;
-      }
-   }
-
-   if (incomingCommand == NULL &&
-       ! enet_list_empty (& channel -> incomingReliableCommands))
-   {
-      incomingCommand = (ENetIncomingCommand *) enet_list_front (& channel -> incomingReliableCommands);
-
-      if (incomingCommand -> fragmentsRemaining > 0 ||
-          incomingCommand -> reliableSequenceNumber != (enet_uint16) (channel -> incomingReliableSequenceNumber + 1))
-        return NULL;
-
-      channel -> incomingReliableSequenceNumber = incomingCommand -> reliableSequenceNumber;
-
-      if (incomingCommand -> fragmentCount > 0)
-        channel -> incomingReliableSequenceNumber += incomingCommand -> fragmentCount - 1;
-   }
-
-   if (incomingCommand == NULL)
+   
+   if (enet_list_empty (& peer -> dispatchedCommands))
      return NULL;
 
-   enet_list_remove (& incomingCommand -> incomingCommandList);
+   incomingCommand = (ENetIncomingCommand *) enet_list_remove (enet_list_begin (& peer -> dispatchedCommands));
+
+   * channelID = incomingCommand -> command.header.channelID;
 
    packet = incomingCommand -> packet;
 
@@ -307,6 +282,13 @@ enet_peer_reset_queues (ENetPeer * peer)
 {
     ENetChannel * channel;
 
+    if (peer -> needsDispatch)
+    {
+       enet_list_remove (& peer -> dispatchList);
+
+       peer -> needsDispatch = 0;
+    }
+
     while (! enet_list_empty (& peer -> acknowledgements))
       enet_free (enet_list_remove (enet_list_begin (& peer -> acknowledgements)));
 
@@ -314,6 +296,7 @@ enet_peer_reset_queues (ENetPeer * peer)
     enet_peer_reset_outgoing_commands (& peer -> sentUnreliableCommands);
     enet_peer_reset_outgoing_commands (& peer -> outgoingReliableCommands);
     enet_peer_reset_outgoing_commands (& peer -> outgoingUnreliableCommands);
+    enet_peer_reset_incoming_commands (& peer -> dispatchedCommands);
 
     if (peer -> channels != NULL && peer -> channelCount > 0)
     {
@@ -601,6 +584,71 @@ enet_peer_queue_outgoing_command (ENetPeer * peer, const ENetProtocol * command,
     return outgoingCommand;
 }
 
+static void
+enet_peer_dispatch_incoming_unreliable_commands (ENetPeer * peer, ENetChannel * channel)
+{
+    ENetListIterator currentCommand;
+
+    for (currentCommand = enet_list_begin (& channel -> incomingUnreliableCommands);
+         currentCommand != enet_list_end (& channel -> incomingUnreliableCommands);
+         currentCommand = enet_list_next (currentCommand))
+    {
+       ENetIncomingCommand * incomingCommand = (ENetIncomingCommand *) currentCommand;
+
+       if ((incomingCommand -> command.header.command & ENET_PROTOCOL_COMMAND_MASK) == ENET_PROTOCOL_COMMAND_SEND_UNRELIABLE &&
+           incomingCommand -> reliableSequenceNumber != channel -> incomingReliableSequenceNumber)
+         break;
+    }
+
+    if (currentCommand == enet_list_begin (& channel -> incomingUnreliableCommands))
+      return;
+
+    enet_list_move (enet_list_end (& peer -> dispatchedCommands), enet_list_begin (& channel -> incomingUnreliableCommands), enet_list_previous (currentCommand));
+
+    if (! peer -> needsDispatch)
+    {
+       enet_list_insert (enet_list_end (& peer -> host -> dispatchQueue), & peer -> dispatchList);
+
+       peer -> needsDispatch = 1;
+    }
+}
+
+static void
+enet_peer_dispatch_incoming_reliable_commands (ENetPeer * peer, ENetChannel * channel)
+{
+    ENetListIterator currentCommand;
+
+    for (currentCommand = enet_list_begin (& channel -> incomingReliableCommands);
+         currentCommand != enet_list_end (& channel -> incomingReliableCommands);
+         currentCommand = enet_list_next (currentCommand))
+    {
+       ENetIncomingCommand * incomingCommand = (ENetIncomingCommand *) currentCommand;
+         
+       if (incomingCommand -> fragmentsRemaining > 0 ||
+           incomingCommand -> reliableSequenceNumber != (enet_uint16) (channel -> incomingReliableSequenceNumber + 1))
+         break;
+
+       channel -> incomingReliableSequenceNumber = incomingCommand -> reliableSequenceNumber;
+
+       if (incomingCommand -> fragmentCount > 0)
+         channel -> incomingReliableSequenceNumber += incomingCommand -> fragmentCount - 1;
+    } 
+
+    if (currentCommand == enet_list_begin (& channel -> incomingReliableCommands))
+      return;
+
+    enet_list_move (enet_list_end (& peer -> dispatchedCommands), enet_list_begin (& channel -> incomingReliableCommands), enet_list_previous (currentCommand));
+
+    if (! peer -> needsDispatch)
+    {
+       enet_list_insert (enet_list_end (& peer -> host -> dispatchQueue), & peer -> dispatchList);
+
+       peer -> needsDispatch = 1;
+    }
+
+    enet_peer_dispatch_incoming_unreliable_commands (peer, channel);
+}
+
 ENetIncomingCommand *
 enet_peer_queue_incoming_command (ENetPeer * peer, const ENetProtocol * command, ENetPacket * packet, enet_uint32 fragmentCount)
 {
@@ -734,6 +782,18 @@ enet_peer_queue_incoming_command (ENetPeer * peer, const ENetProtocol * command,
 
     enet_list_insert (enet_list_next (currentCommand), incomingCommand);
 
+    switch (command -> header.command & ENET_PROTOCOL_COMMAND_MASK)
+    {
+    case ENET_PROTOCOL_COMMAND_SEND_FRAGMENT:
+    case ENET_PROTOCOL_COMMAND_SEND_RELIABLE:
+       enet_peer_dispatch_reliable_incoming_commands (peer, channel);
+       break;
+
+    default:
+       enet_peer_dispatch_unreliable_incoming_commands (peer, channel);
+       break;
+    }
+
     return incomingCommand;
 
 freePacket:
diff --git a/protocol.c b/protocol.c
index 8518d1f..544feb2 100644
--- a/protocol.c
+++ b/protocol.c
@@ -34,24 +34,20 @@ enet_protocol_command_size (enet_uint8 commandNumber)
 static int
 enet_protocol_dispatch_incoming_commands (ENetHost * host, ENetEvent * event)
 {
-    ENetPeer * currentPeer = host -> lastServicedPeer;
-    ENetChannel * channel;
-
-    do
+    while (! enet_list_empty (& host -> dispatchQueue))
     {
-       ++ currentPeer;
-       
-       if (currentPeer >= & host -> peers [host -> peerCount])
-         currentPeer = host -> peers;
+       ENetPeer * peer = (ENetPeer *) enet_list_remove (enet_list_begin (& host -> dispatchQueue));
 
-       switch (currentPeer -> state)
+       peer -> needsDispatch = 0;
+
+       switch (peer -> state)
        {
        case ENET_PEER_STATE_CONNECTION_PENDING:
        case ENET_PEER_STATE_CONNECTION_SUCCEEDED:
-           currentPeer -> state = ENET_PEER_STATE_CONNECTED;
+           peer -> state = ENET_PEER_STATE_CONNECTED;
 
            event -> type = ENET_EVENT_TYPE_CONNECT;
-           event -> peer = currentPeer;
+           event -> peer = peer;
 
            return 1;
            
@@ -59,72 +55,77 @@ enet_protocol_dispatch_incoming_commands (ENetHost * host, ENetEvent * event)
            host -> recalculateBandwidthLimits = 1;
 
            event -> type = ENET_EVENT_TYPE_DISCONNECT;
-           event -> peer = currentPeer;
-           event -> data = currentPeer -> disconnectData;
-
-           enet_peer_reset (currentPeer);
+           event -> peer = peer;
+           event -> data = peer -> disconnectData;
 
-           host -> lastServicedPeer = currentPeer;
+           enet_peer_reset (peer);
 
            return 1;
-       }
 
-       if (currentPeer -> state != ENET_PEER_STATE_CONNECTED)
-         continue;
-
-       for (channel = currentPeer -> channels;
-            channel < & currentPeer -> channels [currentPeer -> channelCount];
-            ++ channel)
-       {
-           if (enet_list_empty (& channel -> incomingReliableCommands) &&
-               enet_list_empty (& channel -> incomingUnreliableCommands))
+       case ENET_PEER_STATE_CONNECTED:
+           if (enet_list_empty (& peer -> dispatchedCommands))
              continue;
 
-           event -> packet = enet_peer_receive (currentPeer, channel - currentPeer -> channels);
+           event -> packet = enet_peer_receive (peer, & event -> channelID);
            if (event -> packet == NULL)
              continue;
              
            event -> type = ENET_EVENT_TYPE_RECEIVE;
-           event -> peer = currentPeer;
-           event -> channelID = (enet_uint8) (channel - currentPeer -> channels);
+           event -> peer = peer;
 
-           host -> lastServicedPeer = currentPeer;
+           if (! enet_list_empty (& peer -> dispatchedCommands))
+           {
+              peer -> needsDispatch = 1;
+         
+              enet_list_insert (enet_list_end (& host -> dispatchQueue), & peer -> dispatchList);
+           }
 
            return 1;
        }
-    } while (currentPeer != host -> lastServicedPeer);
+    }
 
     return 0;
 }
 
 static void
+enet_protocol_dispatch_state (ENetHost * host, ENetPeer * peer, ENetPeerState state)
+{
+    peer -> state = state;
+
+    if (! peer -> needsDispatch)
+    {
+       enet_list_insert (enet_list_end (& host -> dispatchQueue), & peer -> dispatchList);
+
+       peer -> needsDispatch = 1;
+    }    
+}
+    
+static void
 enet_protocol_notify_connect (ENetHost * host, ENetPeer * peer, ENetEvent * event)
 {
     host -> recalculateBandwidthLimits = 1;
 
-    if (event == NULL)
-       peer -> state = (peer -> state == ENET_PEER_STATE_CONNECTING ? ENET_PEER_STATE_CONNECTION_SUCCEEDED : ENET_PEER_STATE_CONNECTION_PENDING);
-    else
+    if (event != NULL)
     {
-       peer -> state = ENET_PEER_STATE_CONNECTED;
+        peer -> state = ENET_PEER_STATE_CONNECTED;
 
-       event -> type = ENET_EVENT_TYPE_CONNECT;
-       event -> peer = peer;
+        event -> type = ENET_EVENT_TYPE_CONNECT;
+        event -> peer = peer;
     }
+    else 
+        enet_protocol_dispatch_state (host, peer, peer -> state == ENET_PEER_STATE_CONNECTING ? ENET_PEER_STATE_CONNECTION_SUCCEEDED : ENET_PEER_STATE_CONNECTION_PENDING);
 }
 
 static void
 enet_protocol_notify_disconnect (ENetHost * host, ENetPeer * peer, ENetEvent * event)
 {
     if (peer -> state >= ENET_PEER_STATE_CONNECTION_PENDING)
-        host -> recalculateBandwidthLimits = 1;
+       host -> recalculateBandwidthLimits = 1;
 
     if (peer -> state != ENET_PEER_STATE_CONNECTING && peer -> state < ENET_PEER_STATE_CONNECTION_SUCCEEDED)
         enet_peer_reset (peer);
     else
-    if (event == NULL)
-        peer -> state = ENET_PEER_STATE_ZOMBIE;
-    else
+    if (event != NULL)
     {
         event -> type = ENET_EVENT_TYPE_DISCONNECT;
         event -> peer = peer;
@@ -132,6 +133,8 @@ enet_protocol_notify_disconnect (ENetHost * host, ENetPeer * peer, ENetEvent * e
 
         enet_peer_reset (peer);
     }
+    else 
+        enet_protocol_dispatch_state (host, peer, ENET_PEER_STATE_ZOMBIE);
 }
 
 static void
@@ -636,7 +639,7 @@ enet_protocol_handle_disconnect (ENetHost * host, ENetPeer * peer, const ENetPro
     enet_peer_reset_queues (peer);
 
     if (peer -> state == ENET_PEER_STATE_CONNECTION_SUCCEEDED)
-        peer -> state = ENET_PEER_STATE_ZOMBIE;
+        enet_protocol_dispatch_state (host, peer, ENET_PEER_STATE_ZOMBIE);
     else
     if (peer -> state != ENET_PEER_STATE_CONNECTED && peer -> state != ENET_PEER_STATE_DISCONNECT_LATER)
     {
@@ -648,7 +651,7 @@ enet_protocol_handle_disconnect (ENetHost * host, ENetPeer * peer, const ENetPro
     if (command -> header.command & ENET_PROTOCOL_COMMAND_FLAG_ACKNOWLEDGE)
       peer -> state = ENET_PEER_STATE_ACKNOWLEDGING_DISCONNECT;
     else
-      peer -> state = ENET_PEER_STATE_ZOMBIE;
+      enet_protocol_dispatch_state (host, peer, ENET_PEER_STATE_ZOMBIE);
 
     peer -> disconnectData = ENET_NET_TO_HOST_32 (command -> disconnect.data);
     return 0;
@@ -751,7 +754,7 @@ enet_protocol_handle_verify_connect (ENetHost * host, ENetEvent * event, ENetPee
         ENET_NET_TO_HOST_32 (command -> verifyConnect.packetThrottleAcceleration) != peer -> packetThrottleAcceleration ||
         ENET_NET_TO_HOST_32 (command -> verifyConnect.packetThrottleDeceleration) != peer -> packetThrottleDeceleration)
     {
-        peer -> state = ENET_PEER_STATE_ZOMBIE;
+        enet_protocol_dispatch_state (host, peer, ENET_PEER_STATE_ZOMBIE);
 
         return -1;
     }
@@ -1047,7 +1050,7 @@ enet_protocol_send_acknowledgements (ENetHost * host, ENetPeer * peer)
        command -> acknowledge.receivedSentTime = ENET_HOST_TO_NET_16 (acknowledgement -> sentTime);
   
        if ((acknowledgement -> command.header.command & ENET_PROTOCOL_COMMAND_MASK) == ENET_PROTOCOL_COMMAND_DISCONNECT)
-         peer -> state = ENET_PEER_STATE_ZOMBIE;
+         enet_protocol_dispatch_state (host, peer, ENET_PEER_STATE_ZOMBIE);
 
        enet_list_remove (& acknowledgement -> acknowledgementList);
        enet_free (acknowledgement);