TraversalState
The pure candidate bookkeeping of an iterative Kademlia lookup. This is the network-free core of libtorrent's traversal_algorithm (src/kademlia/traversal_algorithm.cpp). DhtNode.getPeers drives one of these: it seeds the state with the routing table's closest nodes, then repeatedly asks the state for the next batch to query (next), fires the actual get_peers/find_node RPCs, and feeds the returned closer nodes back in (add).
The structure (faithful): m_results is the list of every node we've heard of for this target, kept sorted by XOR distance to the target and de-duplicated by node id (traversal_algorithm::add_entry inserts with std::lower_bound under compare_ref and drops duplicates). Each entry tracks the three observer states that matter: not yet queried, queried and in flight, and responded and alive. Those are the flag_queried and flag_alive bits in observer. The lookup stops (isDone) once the closest resultsTarget entries have all responded with nothing closer to add, exactly add_requests's completion test ("results_target completed results without finding any still in flight closer ones").
Branch factor. next hands out at most enough ids to keep branchFactor (libtorrent's α = 3, m_branch_factor) requests outstanding among the closest unqueried nodes, never reaching past the resultsTarget-th closest. That is the "keep the top-k queried" variation libtorrent documents in add_requests (it bounds good outstanding requests rather than raw outstanding requests).
Deliberate simplifications (the live-network nuances DhtNode doesn't need):
No short-timeout / branch-factor inflation. libtorrent escalates a slow node to a 1-second timeout and temporarily widens α; here a node either responds (→ alive) or is marked failed by the caller (fail) when its RPC returns null. The flat per- query timeout lives in DhtRpc.
No per-IP/CIDR spread or
restrict_routing_ipsfiltering of candidates. Those guard the routing table; the in-flight result list takes any node it's told about.No address-family split. Candidates carry a CompactNode (which already knows its v4/v6 endpoint); the caller decides which family to query.
This class is intentionally synchronous and allocation-light so it can be unit-tested without a socket: drive it with hand-built CompactNodes and assert the ordering / completion exactly as the routing-table tests do.
Parameters
the lookup target id (an info-hash for get_peers, our own id for a bootstrap find_node).
how many of the closest nodes must respond before the lookup is done. This is Kademlia's k (libtorrent uses m_table.bucket_size(), default 8).
the maximum number of concurrent in-flight queries among the top candidates. This is Kademlia's α (libtorrent's m_branch_factor, default 3).
Types
Properties
Functions
Insert node into the result list if its id is new, preserving the nearest-first ordering by XOR distance to target. Port of traversal_algorithm::add_entry's lower_bound+insert (sans the no-id/random-id path, since our candidates always carry a real id from a compact-nodes reply). Returns true if it was added.
Bulk add, for seeding from a find_node or nodes reply.
Mark c as having responded (flag_alive).
The count closest nodes that responded. This is the lookup's usable output.
Mark c as failed/timed-out (flag_failed) so it stops blocking completion.
true once the lookup has converged: among the closest resultsTarget live candidates there is nothing still in flight and nothing left unqueried that is closer than them. Port of add_requests's completion condition. Either we have found results_target alive nodes with no closer in-flight or unqueried work, or the whole result list is exhausted.
The next batch of candidates to query: the unqueried nodes nearest the target, enough to bring the number of in-flight queries (among the closest resultsTarget) up to branchFactor. Port of the request-issuing loop in add_requests: it walks the sorted results, counts alive nodes against results_target, counts in-flight ones against branch_factor, and stops as soon as either budget is spent.