2 * Copyright (C) 2008 Thadeu Lima de Souza Cascardo <cascardo@holoscopio.com>
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
27 * Our own implementation of random integer numbers in a range.
29 static int random_int_range (int start, int end)
32 int range = end - start;
33 r = random () * range;
39 * Since we implement the proposed algorithm from RFC 2782, entries
40 * with weight 0 should come before those with non-zero weight.
42 static int dns_srv_compare (const void* a, const void* b)
44 struct dns_srv* addr_a = (struct dns_srv*) a;
45 struct dns_srv* addr_b = (struct dns_srv*) b;
46 if (addr_a->priority != addr_b->priority)
47 return addr_a->priority - addr_b->priority;
48 if (addr_b->weight == 0)
50 else if (addr_a->weight == 0)
56 * Order a vector of addresses with priorities and weights by priority
57 * putting those with weight 0 at the start of those with the same
60 static void dns_srv_sort_priority (void* srvaddr, int n)
62 qsort (srvaddr, n, sizeof (struct dns_srv), dns_srv_compare);
66 * Move entries between j and i one position forward and move i to j
69 static void dns_srv_switch (struct dns_srv* srvaddr, int j, int i)
72 memcpy (&entry, &(srvaddr[i]), sizeof (struct dns_srv));
73 memmove (&(srvaddr[j+1]), &(srvaddr[j]), sizeof (struct dns_srv) * (i - j));
74 memcpy (&(srvaddr[j]), &entry, sizeof (struct dns_srv));
78 * Given a vector of addresses with priorities and weights, sort them
79 * according to RFC 2782..
82 void hc_dns_srv_sort (struct dns_srv* srvaddr, int n)
89 dns_srv_sort_priority (srvaddr, n);
94 /* Compute the sum of weights for the priority prio */
95 for (i = j; i < n && srvaddr[i].priority == prio; i++)
97 sum += srvaddr[i].weight;
99 /* If there is no more nodes with priority prio, get next prio */
100 if (i == j && srvaddr[i].priority > prio)
102 prio = srvaddr[i].priority;
108 wrand = random_int_range (0, sum + 1);
109 for (i = j; i < n && srvaddr[i].weight < wrand; i++)
111 wrand -= srvaddr[i].weight;
114 assert (srvaddr[i].priority == prio);
115 dns_srv_switch (srvaddr, j, i);
116 sum -= srvaddr[j].weight;
119 /* Those remaining addresses with weight 0 */
120 for (i = j; i < n && srvaddr[i].priority == prio; i++, j++);
127 * A test, should be put on another file and built and run with make
128 * tests. One issue is that verifying full correctness is not
129 * possible, since this should be random. However, addresses with
130 * different priorities have an order that should be respected and are
133 int main (int argc, char** argv)
136 struct dns_rr_srv* rr;
138 char* domain = "holoscopio.com.";
142 rr = dns_resolve_srv (NULL, domain, "xmpp-client", "tcp", 0);
145 printf ("No results.\n");
148 printf ("Before sorting:\n");
149 for (i = 0; i < rr->dnssrv_nrr; i++)
151 srv = &(rr->dnssrv_srv[i]);
152 printf ("%s %d %d %d\n", srv->name, srv->port, srv->priority, srv->weight);
155 hc_dns_srv_sort (rr->dnssrv_srv, rr->dnssrv_nrr);
156 printf ("\nAfter sorting:\n");
157 for (i = 0; i < rr->dnssrv_nrr; i++)
159 srv = &(rr->dnssrv_srv[i]);
160 printf ("%s %d %d %d\n", srv->name, srv->port, srv->priority, srv->weight);