Differential D6772 Diff 21864 src/avalanche/peermanager.cpp

Changeset View

Standalone View

src/avalanche/peermanager.cpp

This file was added.

				// Copyright (c) 2020 The Bitcoin developers
				// Distributed under the MIT software license, see the accompanying
				// file COPYING or http://www.opensource.org/licenses/mit-license.php.

				#include <avalanche/peermanager.h>

				#include <random.h>

				void PeerManager::addPeer(uint64_t score) {
				const uint64_t start = slotCount;
				const uint64_t stop = start + score;
				slots.emplace_back(start, stop);
				slotCount = stop;
				}

				size_t PeerManager::selectPeer() const {
				if (slots.empty()) {
				return NO_PEER;
				}

				const uint64_t max = slotCount;
				while (true) {
				size_t i = selectPeerImpl(slots, GetRand(max), max);
				if (i != NO_PEER) {
				return i;
				}
				}
				}

				size_t selectPeerImpl(const std::vector<Slot> &slots, const uint64_t slot,
				const uint64_t max) {
				assert(slot <= max);

				size_t begin = 0, end = slots.size();
				uint64_t bottom = 0, top = max;

				// Try to find the slot using dichotomic search.
				while ((end - begin) > 8) {
				// The slot we picked in not allocated.
				if (slot < bottom \|\| slot >= top) {
				return NO_PEER;
				}

				// Guesstimate the position of the slot.
				size_t i = begin + ((slot - bottom) * (end - begin) / (top - bottom));

				// We have a match.
				if (slots[i].start <= slot && slot < slots[i].stop) {
				return i;
				}

				// We undershooted.
				if (slot >= slots[i].stop) {
				begin = i + 1;
				bottom = slots[begin].start;
				continue;
				}

				// We overshooted.
				if (slots[i].start > slot) {
				end = i;
				top = slots[end].start;
				continue;
				}

				// We have an unalocated slot.
				return NO_PEER;
				}

				// Enough of that nonsense, let fallback to linear search.
				for (size_t i = begin; i < end; i++) {
				// We have a match.
				if (slots[i].start <= slot && slot < slots[i].stop) {
				return i;
				}
				}

				// We failed to find a slot, retry.
				return NO_PEER;
				}