Code to sort SRV results from udns according to RFC 2782.

diff --git a/sort_udns.c b/sort_udns.c
new file mode 100644 (file)
index 0000000..8b0336b
--- /dev/null
+++ b/sort_udns.c
@@ -0,0 +1,165 @@
+/*
+ * 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

diff --git a/sort_udns.h b/sort_udns.h
new file mode 100644 (file)
index 0000000..7db89a8
--- /dev/null
+++ b/sort_udns.h
@@ -0,0 +1,25 @@
+/*
+ * 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/>.
+ *
+ */
+
+#ifndef SORT_UDNS_H
+#define SORT_UDNS_H
+
+void dns_srv_sort (struct dns_srv* srvaddr, int n);
+
+#endif
+