+/*
+ * Copyright (C) 2008 Thadeu Lima de Souza Cascardo <cascardo@holoscopio.com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include <udns.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <assert.h>
+
+/*
+ * Our own implementation of random integer numbers in a range.
+ */
+static int random_int_range (int start, int end)
+{
+ long long r;
+ int range = end - start;
+ r = random () * range;
+ r = r / RAND_MAX;
+ return start + r;
+}
+
+/*
+ * Since we implement the proposed algorithm from RFC 2782, entries
+ * with weight 0 should come before those with non-zero weight.
+ */
+static int dns_srv_compare (const void* a, const void* b)
+{
+ struct dns_srv* addr_a = (struct dns_srv*) a;
+ struct dns_srv* addr_b = (struct dns_srv*) b;
+ if (addr_a->priority != addr_b->priority)
+ return addr_a->priority - addr_b->priority;
+ if (addr_b->weight == 0)
+ return 1;
+ else if (addr_a->weight == 0)
+ return -1;
+ return 0;
+}
+
+/*
+ * Order a vector of addresses with priorities and weights by priority
+ * putting those with weight 0 at the start of those with the same
+ * priority.
+ */
+static void dns_srv_sort_priority (void* srvaddr, int n)
+{
+ qsort (srvaddr, n, sizeof (struct dns_srv), dns_srv_compare);
+}
+
+/*
+ * Move entries between j and i one position forward and move i to j
+ * position.
+ */
+static void dns_srv_switch (struct dns_srv* srvaddr, int j, int i)
+{
+ struct dns_srv entry;
+ memcpy (&entry, &(srvaddr[i]), sizeof (struct dns_srv));
+ memmove (&(srvaddr[j+1]), &(srvaddr[j]), sizeof (struct dns_srv) * (i - j));
+ memcpy (&(srvaddr[j]), &entry, sizeof (struct dns_srv));
+}
+
+/*
+ * Given a vector of addresses with priorities and weights, sort them
+ * according to RFC 2782..
+ */
+
+void dns_srv_sort (struct dns_srv* srvaddr, int n)
+{
+ int i;
+ int j;
+ int prio;
+ int sum;
+ int wrand;
+ dns_srv_sort_priority (srvaddr, n);
+ prio = 0;
+ for (j = 0; j < n;)
+ {
+ sum = 0;
+ /* Compute the sum of weights for the priority prio */
+ for (i = j; i < n && srvaddr[i].priority == prio; i++)
+ {
+ sum += srvaddr[i].weight;
+ }
+ /* If there is no more nodes with priority prio, get next prio */
+ if (i == j && srvaddr[i].priority > prio)
+ {
+ prio = srvaddr[i].priority;
+ }
+ else
+ {
+ while (sum > 0)
+ {
+ wrand = random_int_range (0, sum + 1);
+ for (i = j; i < n && srvaddr[i].weight < wrand; i++)
+ {
+ wrand -= srvaddr[i].weight;
+ }
+ assert (i < n);
+ assert (srvaddr[i].priority == prio);
+ dns_srv_switch (srvaddr, j, i);
+ sum -= srvaddr[j].weight;
+ j++;
+ }
+ /* Those remaining addresses with weight 0 */
+ for (i = j; i < n && srvaddr[i].priority == prio; i++, j++);
+ }
+ }
+}
+
+#ifdef TEST
+/*
+ * A test, should be put on another file and built and run with make
+ * tests. One issue is that verifying full correctness is not
+ * possible, since this should be random. However, addresses with
+ * different priorities have an order that should be respected and are
+ * possible to test.
+ */
+int main (int argc, char** argv)
+{
+ int i;
+ struct dns_rr_srv* rr;
+ struct dns_srv* srv;
+ char* domain = "holoscopio.com.";
+ if (argc > 1)
+ domain = argv[1];
+ dns_init (1);
+ rr = dns_resolve_srv (NULL, domain, "xmpp-client", "tcp", 0);
+ if (rr == NULL)
+ {
+ printf ("No results.\n");
+ exit (0);
+ }
+ printf ("Before sorting:\n");
+ for (i = 0; i < rr->dnssrv_nrr; i++)
+ {
+ srv = &(rr->dnssrv_srv[i]);
+ printf ("%s %d %d %d\n", srv->name, srv->port, srv->priority, srv->weight);
+ }
+ srandom (time (0));
+ dns_srv_sort (rr->dnssrv_srv, rr->dnssrv_nrr);
+ printf ("\nAfter sorting:\n");
+ for (i = 0; i < rr->dnssrv_nrr; i++)
+ {
+ srv = &(rr->dnssrv_srv[i]);
+ printf ("%s %d %d %d\n", srv->name, srv->port, srv->priority, srv->weight);
+ }
+ free (rr);
+ return 0;
+}
+#endif