changeset 27215:4df543f96c62

merge of '0de8339ed2206f013cb9b8105fe3c73ccc2a0f72' and '74ffbb29d8b34ca9471c654d63e54325825d13e2'

--- a/ChangeLog	Mon Jun 29 06:38:40 2009 +0000
+++ b/ChangeLog	Mon Jun 29 06:50:35 2009 +0000
@@ -18,6 +18,8 @@
 	  from you on MSN.
 	* DNS servers are re-read when DNS queries fail in case the system has
 	  moved to a new network and the old servers are not accessible.
+	* DNS SRV records with equal priority are sorted with respect to their
+	  weight as specified in RFC 2782.  (Vijay Raghunathan)
 	* GnuTLS logging (disabled by default) can be controlled through the
 	  PURPLE_GNUTLS_DEBUG environment variable, which is an integer between
 	  0 and 9 (higher is more verbose). Higher values may reveal sensitive

--- a/libpurple/dnssrv.c	Mon Jun 29 06:38:40 2009 +0000
+++ b/libpurple/dnssrv.c	Mon Jun 29 06:50:35 2009 +0000
@@ -94,6 +94,17 @@
 	char query[256];
 } PurpleSrvInternalQuery;
 
+typedef struct _PurpleSrvResponseContainer {
+	PurpleSrvResponse *response;
+	int sum;
+} PurpleSrvResponseContainer;
+
+/**
+ * Sort by priority, then by weight.  Strictly numerically--no
+ * randomness.  Technically we only need to sort by pref and then
+ * make sure any records with weight 0 are at the beginning of
+ * their group, but it's just as easy to sort by weight.
+ */
 static gint
 responsecompare(gconstpointer ar, gconstpointer br)
 {
@@ -112,6 +123,129 @@
 	return 1;
 }
 
+/**
+ * Iterate over a list of PurpleSrvResponseContainer making the sum
+ * the running total of the sums.  Select a random integer in the range
+ * (1, sum+1), then find the first element greater than or equal to the
+ * number selected.  From RFC 2782.
+ *
+ * @param list The list of PurpleSrvResponseContainer.  This function
+ *        removes a node from this list and returns the new list.
+ * @param container_ptr The PurpleSrvResponseContainer that was chosen
+ *        will be returned here.
+ */
+static GList *select_random_response(GList *list,
+		PurpleSrvResponseContainer **container_ptr)
+{
+	GList *cur;
+	size_t runningtotal;
+	int r;
+
+	runningtotal = 0;
+	cur = list;
+
+	while (cur) {
+		PurpleSrvResponseContainer *container = cur->data;
+		runningtotal += container->response->weight;
+		container->sum = runningtotal;
+		cur = cur->next;
+	}
+
+	/*
+	 * If the running total is greater than 0, pick a number between
+	 * 1 and the runningtotal inclusive. (This is not precisely what
+	 * the RFC algorithm describes, but we wish to deal with integers
+	 * and avoid floats.  This is functionally equivalent.)
+	 * If running total is 0, then choose r = 0.
+	 */
+	r = runningtotal ? g_random_int_range(1, runningtotal + 1) : 0;
+	cur = list;
+	while (r > ((PurpleSrvResponseContainer *)cur->data)->sum) {
+		cur = cur->next;
+	}
+
+	/* Set the return parameter and remove cur from the list */
+	*container_ptr =  cur->data;
+	return g_list_delete_link(list, cur);
+}
+
+/**
+ * Reorder a GList of PurpleSrvResponses that have the same priority
+ * (aka "pref").
+ */
+static void srv_reorder(GList *list, int num)
+{
+	int i;
+	GList *cur;
+	GList *container_list = NULL;
+	PurpleSrvResponseContainer *container;
+
+	if (num < 2)
+		/* Nothing to sort */
+		return;
+
+	/* First build a list of container structs */
+	for (i = 0, cur = list; i < num; i++, cur = cur->next) {
+		container = g_new(PurpleSrvResponseContainer, 1);
+		container->response = cur->data;
+		container_list = g_list_prepend(container_list, container);
+	}
+	container_list = g_list_reverse(container_list);
+
+	/*
+	 * Re-order the list that was passed in as a parameter.  We leave
+	 * the list nodes in place, but replace their data pointers.
+	 */
+	cur = list;
+	while (container_list) {
+		container_list = select_random_response(container_list, &container);
+		cur->data = container->response;
+		g_free(container);
+		cur = cur->next;
+	}
+}
+
+/**
+ * Sorts a GList of PurpleSrvResponse's according to the
+ * algorithm described in RFC 2782.
+ *
+ * @param response GList of PurpleSrvResponse's
+ * @param The original list, resorted
+ */
+static GList *purple_srv_sort(GList *list)
+{
+	GList *cur, *start;
+	int count;
+	int pref;
+
+	if (!list || !list->next)
+		/* Nothing to sort */
+		return list;
+
+	list = g_list_sort(list, responsecompare);
+
+	start = cur = list;
+	count = 1;
+	while (cur) {
+		PurpleSrvResponse *next_response;
+		pref = ((PurpleSrvResponse *)cur->data)->pref;
+		next_response = cur->next ? cur->next->data : NULL;
+		if (!next_response || next_response->pref != pref) {
+			/*
+			 * The 'count' records starting at 'start' all have the same
+			 * priority.  Sort them by weight.
+			 */
+			srv_reorder(start, count);
+			start = cur->next;
+			count = 0;
+		}
+		count++;
+		cur = cur->next;
+	}
+
+	return list;
+}
+
 #ifndef _WIN32
 
 G_GNUC_NORETURN static void
@@ -191,7 +325,7 @@
 			srvres->port = port;
 			srvres->weight = weight;
 
-			ret = g_list_insert_sorted(ret, srvres, responsecompare);
+			ret = g_list_prepend(ret, srvres);
 		} else if (query.type == T_TXT) {
 			txtres = g_new0(PurpleTxtResponse, 1);
 			txtres->content = g_strndup((gchar*)(++cp), dlen-1);
@@ -204,6 +338,10 @@
 
 end:
 	size = g_list_length(ret);
+
+	if (query.type == T_SRV)
+		ret = purple_srv_sort(ret);
+
 	/* TODO: Check return value */
 	write(out, &(query.type), sizeof(query.type));
 	write(out, &size, sizeof(size));
@@ -397,11 +535,11 @@
 				srvres->port = srv_data->wPort;
 				srvres->weight = srv_data->wWeight;
 
-				lst = g_slist_insert_sorted(lst, srvres, responsecompare);
+				lst = g_slist_prepend(lst, srvres);
 			}
 
 			MyDnsRecordListFree(dr, DnsFreeRecordList);
-			query_data->results = lst;
+			query_data->results = purple_srv_sort(lst);
 		} else if (type == DNS_TYPE_TXT) {
 			PDNS_RECORD dr_tmp;
 			GSList *lst = NULL;

--- a/libpurple/dnssrv.h	Mon Jun 29 06:38:40 2009 +0000
+++ b/libpurple/dnssrv.h	Mon Jun 29 06:50:35 2009 +0000
@@ -41,6 +41,12 @@
 	int pref;
 };
 
+/**
+ * @param resp An array of PurpleSrvResponse of size results.  The array
+ *        is sorted based on the order described in the DNS SRV RFC.
+ *        Users of this API should try each record in resp in order,
+ *        starting at the beginning.
+ */
 typedef void (*PurpleSrvCallback)(PurpleSrvResponse *resp, int results, gpointer data);
 
 /**