Swiftdiff options
| author | Remko Tronçon <git@el-tramo.be> | 2012-04-23 13:32:24 (GMT) |
|---|---|---|
| committer | Remko Tronçon <git@el-tramo.be> | 2012-04-23 13:57:24 (GMT) |
| commit | 18f4f0ba13bbfe901dae44e95d869ba0425e93c7 (patch) | |
| tree | 51de477a7f2dc9aba3177e6ea50ed90dbff91f85 /Swiften/Network/DomainNameServiceQuery.cpp | |
| parent | 2f64443e7a3e427a3a38665b5aafb77c9b128cc0 (diff) | |
| download | swift-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.cpp | 55 |
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; + } +} + + } |