| 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 |
} |