1 files changed, 107 insertions, 5 deletions

diff --git a/ares/ares_private.h b/ares/ares_private.h
index e6ecaa251..34e4692c4 100644
--- a/ares/ares_private.h
+++ b/ares/ares_private.h
@@ -84,6 +84,15 @@
 
 #include "ares_ipv6.h"
 
+struct query;
+
+/* Node definition for circular, doubly-linked list */
+struct list_node {
+  struct list_node *prev;
+  struct list_node *next;
+  void* data;
+};
+
 struct send_request {
   /* Remaining data to send */
   const unsigned char *data;
@@ -122,17 +131,35 @@ struct server_state {
    * re-send. */
   int tcp_connection_generation;
 
+  /* Circular, doubly-linked list of outstanding queries to this server */
+  struct list_node queries_to_server;
+
+  /* Link back to owning channel */
+  ares_channel channel;
+
   /* Is this server broken? We mark connections as broken when a
    * request that is queued for sending times out.
    */
   int is_broken;
 };
 
+/* State to represent a DNS query */
 struct query {
   /* Query ID from qbuf, for faster lookup, and current timeout */
   unsigned short qid;
   time_t timeout;
 
+  /*
+   * Links for the doubly-linked lists in which we insert a query.
+   * These circular, doubly-linked lists that are hash-bucketed based
+   * the attributes we care about, help making most important
+   * operations O(1).
+   */
+  struct list_node queries_by_qid;    /* hopefully in same cache line as qid */
+  struct list_node queries_by_timeout;
+  struct list_node queries_to_server;
+  struct list_node all_queries;
+
   /* Query buf with length at beginning, for TCP transmission */
   unsigned char *tcpbuf;
   int tcplen;
@@ -149,9 +176,6 @@ struct query {
   struct query_server_info *server_info;   /* per-server state */
   int using_tcp;
   int error_status;
-
-  /* Next query in chain */
-  struct query *next;
   int timeouts; /* number of timeouts we saw for this request */
 };
 
@@ -216,8 +240,18 @@ struct ares_channeldata {
   /* Generation number to use for the next TCP socket open/close */
   int tcp_connection_generation;
 
-  /* Active queries */
-  struct query *queries;
+  /* The time at which we last called process_timeouts() */
+  time_t last_timeout_processed;
+
+  /* Circular, doubly-linked list of queries, bucketed various ways.... */
+  /* All active queries in a single list: */
+  struct list_node all_queries;
+  /* Queries bucketed by qid, for quickly dispatching DNS responses: */
+#define ARES_QID_TABLE_SIZE 2048
+  struct list_node queries_by_qid[ARES_QID_TABLE_SIZE];
+  /* Queries bucketed by timeout, for quickly handling timeouts: */
+#define ARES_TIMEOUT_TABLE_SIZE 1024
+  struct list_node queries_by_timeout[ARES_TIMEOUT_TABLE_SIZE];
 
   ares_sock_state_cb sock_state_cb;
   void *sock_state_cb_data;
@@ -228,8 +262,76 @@ void ares__send_query(ares_channel channel, struct query *query, time_t now);
 void ares__close_sockets(ares_channel channel, struct server_state *server);
 int ares__get_hostent(FILE *fp, int family, struct hostent **host);
 int ares__read_line(FILE *fp, char **buf, int *bufsize);
+void ares__free_query(struct query *query);
 short ares__generate_new_id(rc4_key* key);
 
+
+/* Routines for managing doubly-linked circular linked lists with a
+ * dummy head.
+ */
+
+/* Initialize a new head node */
+static inline void ares__init_list_head(struct list_node* head) {
+  head->prev = head;
+  head->next = head;
+  head->data = NULL;
+}
+
+/* Initialize a list node */
+static inline void ares__init_list_node(struct list_node* node, void* d) {
+  node->prev = NULL;
+  node->next = NULL;
+  node->data = d;
+}
+
+/* Returns true iff the given list is empty */
+static inline int ares__is_list_empty(struct list_node* head) {
+  return ((head->next == head) && (head->prev == head));
+}
+
+/* Inserts new_node before old_node */
+static inline void ares__insert_in_list(struct list_node* new_node,
+                                        struct list_node* old_node) {
+  new_node->next = old_node;
+  new_node->prev = old_node->prev;
+  old_node->prev->next = new_node;
+  old_node->prev = new_node;
+}
+
+/* Removes the node from the list it's in, if any */
+static inline void ares__remove_from_list(struct list_node* node) {
+  if (node->next != NULL) {
+    node->prev->next = node->next;
+    node->next->prev = node->prev;
+    node->prev = NULL;
+    node->next = NULL;
+  }
+}
+
+/* Swap the contents of two lists */
+static inline void ares__swap_lists(struct list_node* head_a,
+                                    struct list_node* head_b) {
+  int is_a_empty = ares__is_list_empty(head_a);
+  int is_b_empty = ares__is_list_empty(head_b);
+  struct list_node old_a = *head_a;
+  struct list_node old_b = *head_b;
+
+  if (is_a_empty) {
+    ares__init_list_head(head_b);
+  } else {
+    *head_b = old_a;
+    old_a.next->prev = head_b;
+    old_a.prev->next = head_b;
+  }
+  if (is_b_empty) {
+    ares__init_list_head(head_a);
+  } else {
+    *head_a = old_b;
+    old_b.next->prev = head_a;
+    old_b.prev->next = head_a;
+  }
+}
+
 #define ARES_SWAP_BYTE(a,b) \
   { unsigned char swapByte = *(a);  *(a) = *(b);  *(b) = swapByte; }