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, 14 insertions, 3 deletions

diff --git a/ares_send.c b/ares_send.c
index c801580..2007321 100644
--- a/ares_send.c
+++ b/ares_send.c
@@ -102,9 +102,20 @@ void ares_send(ares_channel channel, const unsigned char *qbuf, int qlen,
   query->error_status = ARES_ECONNREFUSED;
   query->timeouts = 0;
 
-  /* Chain the query into this channel's query list. */
-  query->next = channel->queries;
-  channel->queries = query;
+  /* Initialize our list nodes. */
+  ares__init_list_node(&(query->queries_by_qid),     query);
+  ares__init_list_node(&(query->queries_by_timeout), query);
+  ares__init_list_node(&(query->queries_to_server),  query);
+  ares__init_list_node(&(query->all_queries),        query);
+       
+  /* Chain the query into the list of all queries. */
+  ares__insert_in_list(&(query->all_queries), &(channel->all_queries));
+  /* Keep track of queries bucketed by qid, so we can process DNS
+   * responses quickly.
+   */
+  ares__insert_in_list(
+      &(query->queries_by_qid),
+      &(channel->queries_by_qid[query->qid % ARES_QID_TABLE_SIZE]));
 
   /* Perform the first query action. */
   time(&now);