@Test public void sortSRVdistributeOverWeights() { int weight50 = 0, weight20one = 0, weight20two = 0, weight10 = 0; for (int i = 0; i < 1000; i++) { List<SRV> sortedRecords = SrvUtil.sortSrvRecords(createSRVRecords()); String host = sortedRecords.get(1).target.ace; if (host.equals("5.20.one.foo.bar")) { weight20one++; } else if (host.equals("5.20.two.foo.bar")) { weight20two++; } else if (host.equals("5.10.foo.bar")) { weight10++; } else if (host.equals("5.50.foo.bar")) { weight50++; } else { fail("Wrong host after SRVRecord sorting"); } } assertTrue(weight50 > 400 && weight50 < 600); assertTrue(weight20one > 100 && weight20one < 300); assertTrue(weight20two > 100 && weight20two < 300); assertTrue(weight10 > 0 && weight10 < 200); }
public static List<SRV> sortSrvRecords(Collection<SRV> srvRecords) { if (srvRecords.size() == 1 && srvRecords.iterator().next().target.equals(DnsName.ROOT)) { return Collections.emptyList(); } SortedMap<Integer, List<SRV>> buckets = new TreeMap<>(); for (SRV srvRecord : srvRecords) { Integer priority = srvRecord.priority; List<SRV> bucket = buckets.get(priority); if (bucket == null) { bucket = new LinkedList<>(); buckets.put(priority, bucket); } bucket.add(srvRecord); } List<SRV> sortedSrvRecords = new ArrayList<>(srvRecords.size()); for (List<SRV> bucket : buckets.values()) { int bucketSize; while ((bucketSize = bucket.size()) > 0) { int[] totals = new int[bucketSize]; int zeroWeight = 1; for (SRV srv : bucket) { if (srv.weight > 0) { zeroWeight = 0; break; } } int bucketWeightSum = 0, count = 0; for (SRV srv : bucket) { bucketWeightSum += srv.weight + zeroWeight; totals[count++] = bucketWeightSum; } int selectedPosition; if (bucketWeightSum == 0) { selectedPosition = (int) (Math.random() * bucketSize); } else { double rnd = Math.random() * bucketWeightSum; selectedPosition = bisect(totals, rnd); } SRV choosenSrvRecord = bucket.remove(selectedPosition); sortedSrvRecords.add(choosenSrvRecord); } } return sortedSrvRecords; }
SrvUtil { public static List<SRV> sortSrvRecords(Collection<SRV> srvRecords) { if (srvRecords.size() == 1 && srvRecords.iterator().next().target.equals(DnsName.ROOT)) { return Collections.emptyList(); } SortedMap<Integer, List<SRV>> buckets = new TreeMap<>(); for (SRV srvRecord : srvRecords) { Integer priority = srvRecord.priority; List<SRV> bucket = buckets.get(priority); if (bucket == null) { bucket = new LinkedList<>(); buckets.put(priority, bucket); } bucket.add(srvRecord); } List<SRV> sortedSrvRecords = new ArrayList<>(srvRecords.size()); for (List<SRV> bucket : buckets.values()) { int bucketSize; while ((bucketSize = bucket.size()) > 0) { int[] totals = new int[bucketSize]; int zeroWeight = 1; for (SRV srv : bucket) { if (srv.weight > 0) { zeroWeight = 0; break; } } int bucketWeightSum = 0, count = 0; for (SRV srv : bucket) { bucketWeightSum += srv.weight + zeroWeight; totals[count++] = bucketWeightSum; } int selectedPosition; if (bucketWeightSum == 0) { selectedPosition = (int) (Math.random() * bucketSize); } else { double rnd = Math.random() * bucketWeightSum; selectedPosition = bisect(totals, rnd); } SRV choosenSrvRecord = bucket.remove(selectedPosition); sortedSrvRecords.add(choosenSrvRecord); } } return sortedSrvRecords; } }
SrvUtil { public static List<SRV> sortSrvRecords(Collection<SRV> srvRecords) { if (srvRecords.size() == 1 && srvRecords.iterator().next().target.equals(DnsName.ROOT)) { return Collections.emptyList(); } SortedMap<Integer, List<SRV>> buckets = new TreeMap<>(); for (SRV srvRecord : srvRecords) { Integer priority = srvRecord.priority; List<SRV> bucket = buckets.get(priority); if (bucket == null) { bucket = new LinkedList<>(); buckets.put(priority, bucket); } bucket.add(srvRecord); } List<SRV> sortedSrvRecords = new ArrayList<>(srvRecords.size()); for (List<SRV> bucket : buckets.values()) { int bucketSize; while ((bucketSize = bucket.size()) > 0) { int[] totals = new int[bucketSize]; int zeroWeight = 1; for (SRV srv : bucket) { if (srv.weight > 0) { zeroWeight = 0; break; } } int bucketWeightSum = 0, count = 0; for (SRV srv : bucket) { bucketWeightSum += srv.weight + zeroWeight; totals[count++] = bucketWeightSum; } int selectedPosition; if (bucketWeightSum == 0) { selectedPosition = (int) (Math.random() * bucketSize); } else { double rnd = Math.random() * bucketWeightSum; selectedPosition = bisect(totals, rnd); } SRV choosenSrvRecord = bucket.remove(selectedPosition); sortedSrvRecords.add(choosenSrvRecord); } } return sortedSrvRecords; }  }
SrvUtil { public static List<SRV> sortSrvRecords(Collection<SRV> srvRecords) { if (srvRecords.size() == 1 && srvRecords.iterator().next().target.equals(DnsName.ROOT)) { return Collections.emptyList(); } SortedMap<Integer, List<SRV>> buckets = new TreeMap<>(); for (SRV srvRecord : srvRecords) { Integer priority = srvRecord.priority; List<SRV> bucket = buckets.get(priority); if (bucket == null) { bucket = new LinkedList<>(); buckets.put(priority, bucket); } bucket.add(srvRecord); } List<SRV> sortedSrvRecords = new ArrayList<>(srvRecords.size()); for (List<SRV> bucket : buckets.values()) { int bucketSize; while ((bucketSize = bucket.size()) > 0) { int[] totals = new int[bucketSize]; int zeroWeight = 1; for (SRV srv : bucket) { if (srv.weight > 0) { zeroWeight = 0; break; } } int bucketWeightSum = 0, count = 0; for (SRV srv : bucket) { bucketWeightSum += srv.weight + zeroWeight; totals[count++] = bucketWeightSum; } int selectedPosition; if (bucketWeightSum == 0) { selectedPosition = (int) (Math.random() * bucketSize); } else { double rnd = Math.random() * bucketWeightSum; selectedPosition = bisect(totals, rnd); } SRV choosenSrvRecord = bucket.remove(selectedPosition); sortedSrvRecords.add(choosenSrvRecord); } } return sortedSrvRecords; }  static List<SRV> sortSrvRecords(Collection<SRV> srvRecords); }
SrvUtil { public static List<SRV> sortSrvRecords(Collection<SRV> srvRecords) { if (srvRecords.size() == 1 && srvRecords.iterator().next().target.equals(DnsName.ROOT)) { return Collections.emptyList(); } SortedMap<Integer, List<SRV>> buckets = new TreeMap<>(); for (SRV srvRecord : srvRecords) { Integer priority = srvRecord.priority; List<SRV> bucket = buckets.get(priority); if (bucket == null) { bucket = new LinkedList<>(); buckets.put(priority, bucket); } bucket.add(srvRecord); } List<SRV> sortedSrvRecords = new ArrayList<>(srvRecords.size()); for (List<SRV> bucket : buckets.values()) { int bucketSize; while ((bucketSize = bucket.size()) > 0) { int[] totals = new int[bucketSize]; int zeroWeight = 1; for (SRV srv : bucket) { if (srv.weight > 0) { zeroWeight = 0; break; } } int bucketWeightSum = 0, count = 0; for (SRV srv : bucket) { bucketWeightSum += srv.weight + zeroWeight; totals[count++] = bucketWeightSum; } int selectedPosition; if (bucketWeightSum == 0) { selectedPosition = (int) (Math.random() * bucketSize); } else { double rnd = Math.random() * bucketWeightSum; selectedPosition = bisect(totals, rnd); } SRV choosenSrvRecord = bucket.remove(selectedPosition); sortedSrvRecords.add(choosenSrvRecord); } } return sortedSrvRecords; }  static List<SRV> sortSrvRecords(Collection<SRV> srvRecords);  }