Debian Codegraph @

minidns-core/src/main/java/org/minidns/util/SrvUtil.java

raw
1 /*
2 * Copyright 2015-2020 the original author or authors
3 *
4 * This software is licensed under the Apache License, Version 2.0,
5 * the GNU Lesser General Public License version 2 or later ("LGPL")
6 * and the WTFPL.
7 * You may choose either license to govern your use of this software only
8 * upon the condition that you accept all of the terms of either
9 * the Apache License 2.0, the LGPL 2.1+ or the WTFPL.
10 */
11 package org.minidns.util;
12
13 import java.util.ArrayList;
14 import java.util.Collection;
15 import java.util.Collections;
16 import java.util.LinkedList;
17 import java.util.List;
18 import java.util.SortedMap;
19 import java.util.TreeMap;
20
21 import org.minidns.dnsname.DnsName;
22 import org.minidns.record.SRV;
23
24 public class SrvUtil {
25
26 /**
27 * Sort the given collection of {@link SRV} resource records by their priority and weight.
28 * <p>
29 * Sorting by priority is easy. Sorting the buckets of SRV records with the same priority by weight requires to choose those records
30 * randomly but taking the weight into account.
31 * </p>
32 *
33 * @param srvRecords
34 * a collection of SRV records.
35 * @return a sorted list of the given records.
36 */
37 public static List<SRV> sortSrvRecords(Collection<SRV> srvRecords) {
38 // RFC 2782, Usage rules: "If there is precisely one SRV RR, and its Target is "."
39 // (the root domain), abort."
40 if (srvRecords.size() == 1 && srvRecords.iterator().next().target.equals(DnsName.ROOT)) {
41 return Collections.emptyList();
42 }
43
44 // Create the priority buckets.
45 SortedMap<Integer, List<SRV>> buckets = new TreeMap<>();
46 for (SRV srvRecord : srvRecords) {
47 Integer priority = srvRecord.priority;
48 List<SRV> bucket = buckets.get(priority);
49 if (bucket == null) {
50 bucket = new LinkedList<>();
51 buckets.put(priority, bucket);
52 }
53 bucket.add(srvRecord);
54 }
55
56 List<SRV> sortedSrvRecords = new ArrayList<>(srvRecords.size());
57
58 for (List<SRV> bucket : buckets.values()) {
59 // The list of buckets will be sorted by priority, thanks to SortedMap. We now have determine the order of
60 // the SRV records with the same priority, i.e., within the same bucket, by their weight. This is done by
61 // creating an array 'totals' which reflects the percentage of the SRV RRs weight by the total weight of all
62 // SRV RRs in the bucket. For every entry in the bucket, we choose one using a random number and the sum of
63 // all weights left in the bucket. We then select RRs position based on the according index of the selected
64 // value in the 'total' array. This ensures that its weight is taken into account.
65 int bucketSize;
66 while ((bucketSize = bucket.size()) > 0) {
67 int[] totals = new int[bucketSize];
68
69 int zeroWeight = 1;
70 for (SRV srv : bucket) {
71 if (srv.weight > 0) {
72 zeroWeight = 0;
73 break;
74 }
75 }
76
77 int bucketWeightSum = 0, count = 0;
78 for (SRV srv : bucket) {
79 bucketWeightSum += srv.weight + zeroWeight;
80 totals[count++] = bucketWeightSum;
81 }
82
83 int selectedPosition;
84 if (bucketWeightSum == 0) {
85 // If total priority is 0, then the sum of all weights in this priority bucket is 0. So we simply
86 // select one of the weights randomly as the other algorithm performed in the else block is unable
87 // to handle this case.
88 selectedPosition = (int) (Math.random() * bucketSize);
89 } else {
90 double rnd = Math.random() * bucketWeightSum;
91 selectedPosition = bisect(totals, rnd);
92 }
93
94 SRV choosenSrvRecord = bucket.remove(selectedPosition);
95 sortedSrvRecords.add(choosenSrvRecord);
96 }
97 }
98
99 return sortedSrvRecords;
100 }
101
102 // TODO This is not yet really bisection just a stupid linear search.
103 private static int bisect(int[] array, double value) {
104 int pos = 0;
105 for (int element : array) {
106 if (value < element)
107 break;
108 pos++;
109 }
110 return pos;
111 }
112
113 }