From 04e49e09dcfac29e7e90b5546672a9b42d0b935a Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Sat, 29 Sep 2007 18:18:47 +0000 Subject: 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. --- ares_destroy.c | 43 +++++++++++++++++++++++++++++++------------ 1 file changed, 31 insertions(+), 12 deletions(-) (limited to 'ares_destroy.c') diff --git a/ares_destroy.c b/ares_destroy.c index d1f82bd..1dc2d95 100644 --- a/ares_destroy.c +++ b/ares_destroy.c @@ -16,6 +16,7 @@ */ #include "setup.h" +#include #include #include "ares.h" #include "ares_private.h" @@ -37,13 +38,42 @@ void ares_destroy(ares_channel channel) { int i; struct query *query; + struct list_node* list_head; + struct list_node* list_node; + + list_head = &(channel->all_queries); + for (list_node = list_head->next; list_node != list_head; ) + { + query = list_node->data; + list_node = list_node->next; /* since we're deleting the query */ + query->callback(query->arg, ARES_EDESTRUCTION, 0, NULL, 0); + ares__free_query(query); + } +#ifndef NDEBUG + /* Freeing the query should remove it from all the lists in which it sits, + * so all query lists should be empty now. + */ + assert(ares__is_list_empty(&(channel->all_queries))); + for (i = 0; i < ARES_QID_TABLE_SIZE; i++) + { + assert(ares__is_list_empty(&(channel->queries_by_qid[i]))); + } + for (i = 0; i < ARES_TIMEOUT_TABLE_SIZE; i++) + { + assert(ares__is_list_empty(&(channel->queries_by_timeout[i]))); + } +#endif if (!channel) return; if (channel->servers) { for (i = 0; i < channel->nservers; i++) - ares__close_sockets(channel, &channel->servers[i]); + { + struct server_state *server = &channel->servers[i]; + ares__close_sockets(channel, server); + assert(ares__is_list_empty(&(server->queries_to_server))); + } free(channel->servers); } @@ -59,16 +89,5 @@ void ares_destroy(ares_channel channel) if (channel->lookups) free(channel->lookups); - while (channel->queries) { - query = channel->queries; - channel->queries = query->next; - query->callback(query->arg, ARES_EDESTRUCTION, 0, NULL, 0); - if (query->tcpbuf) - free(query->tcpbuf); - if (query->server_info) - free(query->server_info); - free(query); - } - free(channel); } -- cgit v1.2.3