summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRemko Tronçon <git@el-tramo.be>2012-04-23 13:32:24 (GMT)
committerRemko Tronçon <git@el-tramo.be>2012-04-23 13:57:24 (GMT)
commit18f4f0ba13bbfe901dae44e95d869ba0425e93c7 (patch)
tree51de477a7f2dc9aba3177e6ea50ed90dbff91f85 /Swiften/Network/DomainNameServiceQuery.cpp
parent2f64443e7a3e427a3a38665b5aafb77c9b128cc0 (diff)
downloadswift-contrib-18f4f0ba13bbfe901dae44e95d869ba0425e93c7.zip
swift-contrib-18f4f0ba13bbfe901dae44e95d869ba0425e93c7.tar.bz2
Select SRV randomly, taking weight into account.
Resolves: #1030
Diffstat (limited to 'Swiften/Network/DomainNameServiceQuery.cpp')
-rw-r--r--Swiften/Network/DomainNameServiceQuery.cpp55
1 files changed, 55 insertions, 0 deletions
diff --git a/Swiften/Network/DomainNameServiceQuery.cpp b/Swiften/Network/DomainNameServiceQuery.cpp
index 5713b63..eb999e0 100644
--- a/Swiften/Network/DomainNameServiceQuery.cpp
+++ b/Swiften/Network/DomainNameServiceQuery.cpp
@@ -6,9 +6,64 @@
#include <Swiften/Network/DomainNameServiceQuery.h>
+#include <numeric>
+#include <cassert>
+
+#include <Swiften/Base/RandomGenerator.h>
+#include <boost/numeric/conversion/cast.hpp>
+
+using namespace Swift;
+
+namespace {
+ struct ResultPriorityComparator {
+ bool operator()(const DomainNameServiceQuery::Result& a, const DomainNameServiceQuery::Result& b) const {
+ return a.priority < b.priority;
+ }
+ };
+
+ struct WeightAccumulator {
+ int operator()(int accumulator, const DomainNameServiceQuery::Result& result) {
+ return accumulator + result.weight;
+ }
+ };
+
+ struct WeightToProbability {
+ WeightToProbability(int total) : total(total) {}
+
+ double operator()(const DomainNameServiceQuery::Result& result) {
+ return result.weight / boost::numeric_cast<double>(total);
+ }
+ int total;
+ };
+}
+
namespace Swift {
DomainNameServiceQuery::~DomainNameServiceQuery() {
}
+void DomainNameServiceQuery::sortResults(std::vector<DomainNameServiceQuery::Result>& queries, RandomGenerator& generator) {
+ ResultPriorityComparator comparator;
+ std::sort(queries.begin(), queries.end(), comparator);
+
+ std::vector<DomainNameServiceQuery::Result>::iterator i = queries.begin();
+ while (i != queries.end()) {
+ std::vector<DomainNameServiceQuery::Result>::iterator next = std::upper_bound(i, queries.end(), *i, comparator);
+ if (std::distance(i, next) > 1) {
+ int weightSum = std::accumulate(i, next, 0, WeightAccumulator());
+ std::vector<double> probabilities;
+ std::transform(i, next, std::back_inserter(probabilities), WeightToProbability(weightSum));
+
+ // Shuffling the result array and the probabilities in parallel
+ for (size_t j = 0; j < probabilities.size(); ++j) {
+ int selectedIndex = generator.generateWeighedRandomNumber(probabilities.begin() + j, probabilities.end());
+ std::swap(i[j], i[j + selectedIndex]);
+ std::swap(probabilities.begin()[j], probabilities.begin()[j + selectedIndex]);
+ }
+ }
+ i = next;
+ }
+}
+
+
}