Previously, processing a large batch of timeouts was O(n^2) in the number of

outstanding queries, and processing a DNS response packet was O(n) in the
number of outstanding queries. To speed things up in Google, we added a few circular,
doubly-linked lists of queries that are hash-bucketed based on
the attributes we care about, so most important operations are now O(1).

It might be that the number of buckets are higher than most people would need,
but on a quick calculation it should only be 100kB or so even on a 64-bit
system, so I've let it stay as-is.

1 files changed, 13 insertions, 2 deletions

diff --git a/ares_timeout.c b/ares_timeout.c
index 496db84..12b93b0 100644
--- a/ares_timeout.c
+++ b/ares_timeout.c
@@ -26,23 +26,34 @@
 #include "ares.h"
 #include "ares_private.h"
 
+/* WARNING: Beware that this is linear in the number of outstanding
+ * requests! You are probably far better off just calling ares_process()
+ * once per second, rather than calling ares_timeout() to figure out
+ * when to next call ares_process().
+ */
 struct timeval *ares_timeout(ares_channel channel, struct timeval *maxtv,
                              struct timeval *tvbuf)
 {
   struct query *query;
+  struct list_node* list_head;
+  struct list_node* list_node;
   time_t now;
   time_t offset, min_offset; /* these use time_t since some 32 bit systems
                                 still use 64 bit time_t! (like VS2005) */
 
   /* No queries, no timeout (and no fetch of the current time). */
-  if (!channel->queries)
+  if (ares__is_list_empty(&(channel->all_queries)))
     return maxtv;
 
   /* Find the minimum timeout for the current set of queries. */
   time(&now);
   min_offset = -1;
-  for (query = channel->queries; query; query = query->next)
+
+  list_head = &(channel->all_queries);
+  for (list_node = list_head->next; list_node != list_head;
+       list_node = list_node->next)
     {
+      query = list_node->data;
       if (query->timeout == 0)
         continue;
       offset = query->timeout - now;