libp2p_kad/kbucket/bucket.rs
1// Copyright 2019 Parity Technologies (UK) Ltd.
2//
3// Permission is hereby granted, free of charge, to any person obtaining a
4// copy of this software and associated documentation files (the "Software"),
5// to deal in the Software without restriction, including without limitation
6// the rights to use, copy, modify, merge, publish, distribute, sublicense,
7// and/or sell copies of the Software, and to permit persons to whom the
8// Software is furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in
11// all copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
14// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
18// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
19// DEALINGS IN THE SOFTWARE.
20
21//! The internal API for a single `KBucket` in a `KBucketsTable`.
22//!
23//! > **Note**: Uniqueness of entries w.r.t. a `Key` in a `KBucket` is not
24//! > checked in this module. This is an invariant that must hold across all
25//! > buckets in a `KBucketsTable` and hence is enforced by the public API
26//! > of the `KBucketsTable` and in particular the public `Entry` API.
27
28use super::*;
29pub(crate) use crate::K_VALUE;
30/// A `PendingNode` is a `Node` that is pending insertion into a `KBucket`.
31#[derive(Debug, Clone)]
32pub(crate) struct PendingNode<TKey, TVal> {
33 /// The pending node to insert.
34 node: Node<TKey, TVal>,
35
36 /// The status of the pending node.
37 status: NodeStatus,
38
39 /// The instant at which the pending node is eligible for insertion into a bucket.
40 replace: Instant,
41}
42
43/// The status of a node in a bucket.
44///
45/// The status of a node in a bucket together with the time of the
46/// last status change determines the position of the node in a
47/// bucket.
48#[derive(PartialEq, Eq, Debug, Copy, Clone)]
49pub enum NodeStatus {
50 /// The node is considered connected.
51 Connected,
52 /// The node is considered disconnected.
53 Disconnected,
54}
55
56impl<TKey, TVal> PendingNode<TKey, TVal> {
57 pub(crate) fn status(&self) -> NodeStatus {
58 self.status
59 }
60
61 pub(crate) fn value_mut(&mut self) -> &mut TVal {
62 &mut self.node.value
63 }
64
65 pub(crate) fn is_ready(&self) -> bool {
66 Instant::now() >= self.replace
67 }
68
69 #[cfg(test)]
70 pub(crate) fn set_ready_at(&mut self, t: Instant) {
71 self.replace = t;
72 }
73
74 pub(crate) fn into_node(self) -> Node<TKey, TVal> {
75 self.node
76 }
77}
78
79/// A `Node` in a bucket, representing a peer participating
80/// in the Kademlia DHT together with an associated value (e.g. contact
81/// information).
82#[derive(Debug, Clone, PartialEq, Eq)]
83pub struct Node<TKey, TVal> {
84 /// The key of the node, identifying the peer.
85 pub key: TKey,
86 /// The associated value.
87 pub value: TVal,
88}
89
90/// The position of a node in a `KBucket`, i.e. a non-negative integer
91/// in the range `[0, K_VALUE)`.
92#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
93pub(crate) struct Position(usize);
94/// A `KBucket` is a list of up to `K_VALUE` keys and associated values,
95/// ordered from least-recently connected to most-recently connected.
96#[derive(Debug, Clone)]
97pub(crate) struct KBucket<TKey, TVal> {
98 /// The nodes contained in the bucket.
99 nodes: ArrayVec<Node<TKey, TVal>, { K_VALUE.get() }>,
100
101 /// The position (index) in `nodes` that marks the first connected node.
102 ///
103 /// Since the entries in `nodes` are ordered from least-recently connected to
104 /// most-recently connected, all entries above this index are also considered
105 /// connected, i.e. the range `[0, first_connected_pos)` marks the sub-list of entries
106 /// that are considered disconnected and the range
107 /// `[first_connected_pos, K_VALUE)` marks sub-list of entries that are
108 /// considered connected.
109 ///
110 /// `None` indicates that there are no connected entries in the bucket, i.e.
111 /// the bucket is either empty, or contains only entries for peers that are
112 /// considered disconnected.
113 first_connected_pos: Option<usize>,
114
115 /// A node that is pending to be inserted into a full bucket, should the
116 /// least-recently connected (and currently disconnected) node not be
117 /// marked as connected within `unresponsive_timeout`.
118 pending: Option<PendingNode<TKey, TVal>>,
119
120 /// The timeout window before a new pending node is eligible for insertion,
121 /// if the least-recently connected node is not updated as being connected
122 /// in the meantime.
123 pending_timeout: Duration,
124}
125
126/// The result of inserting an entry into a bucket.
127#[must_use]
128#[derive(Debug, Clone, PartialEq, Eq)]
129pub(crate) enum InsertResult<TKey> {
130 /// The entry has been successfully inserted.
131 Inserted,
132 /// The entry is pending insertion because the relevant bucket is currently full.
133 /// The entry is inserted after a timeout elapsed, if the status of the
134 /// least-recently connected (and currently disconnected) node in the bucket
135 /// is not updated before the timeout expires.
136 Pending {
137 /// The key of the least-recently connected entry that is currently considered
138 /// disconnected and whose corresponding peer should be checked for connectivity
139 /// in order to prevent it from being evicted. If connectivity to the peer is
140 /// re-established, the corresponding entry should be updated with
141 /// [`NodeStatus::Connected`].
142 disconnected: TKey,
143 },
144 /// The entry was not inserted because the relevant bucket is full.
145 Full,
146}
147
148/// The result of applying a pending node to a bucket, possibly
149/// replacing an existing node.
150#[derive(Debug, Clone, PartialEq, Eq)]
151pub(crate) struct AppliedPending<TKey, TVal> {
152 /// The key of the inserted pending node.
153 pub(crate) inserted: Node<TKey, TVal>,
154 /// The node that has been evicted from the bucket to make room for the
155 /// pending node, if any.
156 pub(crate) evicted: Option<Node<TKey, TVal>>,
157}
158
159impl<TKey, TVal> KBucket<TKey, TVal>
160where
161 TKey: Clone + AsRef<KeyBytes>,
162 TVal: Clone,
163{
164 /// Creates a new `KBucket` with the given timeout for pending entries.
165 pub(crate) fn new(pending_timeout: Duration) -> Self {
166 KBucket {
167 nodes: ArrayVec::new(),
168 first_connected_pos: None,
169 pending: None,
170 pending_timeout,
171 }
172 }
173
174 /// Returns a reference to the pending node of the bucket, if there is any.
175 pub(crate) fn pending(&self) -> Option<&PendingNode<TKey, TVal>> {
176 self.pending.as_ref()
177 }
178
179 /// Returns a mutable reference to the pending node of the bucket, if there is any.
180 pub(crate) fn pending_mut(&mut self) -> Option<&mut PendingNode<TKey, TVal>> {
181 self.pending.as_mut()
182 }
183
184 /// Returns a reference to the pending node of the bucket, if there is any
185 /// with a matching key.
186 pub(crate) fn as_pending(&self, key: &TKey) -> Option<&PendingNode<TKey, TVal>> {
187 self.pending()
188 .filter(|p| p.node.key.as_ref() == key.as_ref())
189 }
190
191 /// Returns an iterator over the nodes in the bucket, together with their status.
192 pub(crate) fn iter(&self) -> impl Iterator<Item = (&Node<TKey, TVal>, NodeStatus)> {
193 self.nodes
194 .iter()
195 .enumerate()
196 .map(move |(p, n)| (n, self.status(Position(p))))
197 }
198
199 /// Inserts the pending node into the bucket, if its timeout has elapsed,
200 /// replacing the least-recently connected node.
201 ///
202 /// If a pending node has been inserted, its key is returned together with
203 /// the node that was replaced. `None` indicates that the nodes in the
204 /// bucket remained unchanged.
205 pub(crate) fn apply_pending(&mut self) -> Option<AppliedPending<TKey, TVal>> {
206 if let Some(pending) = self.pending.take() {
207 if pending.replace <= Instant::now() {
208 if self.nodes.is_full() {
209 if self.status(Position(0)) == NodeStatus::Connected {
210 // The bucket is full with connected nodes. Drop the pending node.
211 return None;
212 }
213 debug_assert!(self.first_connected_pos.map_or(true, |p| p > 0)); // (*)
214 // The pending node will be inserted.
215 let inserted = pending.node.clone();
216 // A connected pending node goes at the end of the list for
217 // the connected peers, removing the least-recently connected.
218 if pending.status == NodeStatus::Connected {
219 let evicted = Some(self.nodes.remove(0));
220 self.first_connected_pos = self
221 .first_connected_pos
222 .map_or_else(|| Some(self.nodes.len()), |p| p.checked_sub(1));
223 self.nodes.push(pending.node);
224 return Some(AppliedPending { inserted, evicted });
225 }
226 // A disconnected pending node goes at the end of the list
227 // for the disconnected peers.
228 else if let Some(p) = self.first_connected_pos {
229 let insert_pos = p.checked_sub(1).expect("by (*)");
230 let evicted = Some(self.nodes.remove(0));
231 self.nodes.insert(insert_pos, pending.node);
232 return Some(AppliedPending { inserted, evicted });
233 } else {
234 // All nodes are disconnected. Insert the new node as the most
235 // recently disconnected, removing the least-recently disconnected.
236 let evicted = Some(self.nodes.remove(0));
237 self.nodes.push(pending.node);
238 return Some(AppliedPending { inserted, evicted });
239 }
240 } else {
241 // There is room in the bucket, so just insert the pending node.
242 let inserted = pending.node.clone();
243 match self.insert(pending.node, pending.status) {
244 InsertResult::Inserted => {
245 return Some(AppliedPending {
246 inserted,
247 evicted: None,
248 })
249 }
250 _ => unreachable!("Bucket is not full."),
251 }
252 }
253 } else {
254 self.pending = Some(pending);
255 }
256 }
257
258 None
259 }
260
261 /// Updates the status of the pending node, if any.
262 pub(crate) fn update_pending(&mut self, status: NodeStatus) {
263 if let Some(pending) = &mut self.pending {
264 pending.status = status
265 }
266 }
267
268 /// Removes the pending node from the bucket, if any.
269 pub(crate) fn remove_pending(&mut self) -> Option<PendingNode<TKey, TVal>> {
270 self.pending.take()
271 }
272
273 /// Updates the status of the node referred to by the given key, if it is
274 /// in the bucket.
275 pub(crate) fn update(&mut self, key: &TKey, status: NodeStatus) {
276 // Remove the node from its current position and then reinsert it
277 // with the desired status, which puts it at the end of either the
278 // prefix list of disconnected nodes or the suffix list of connected
279 // nodes (i.e. most-recently disconnected or most-recently connected,
280 // respectively).
281 if let Some((node, _status, pos)) = self.remove(key) {
282 // If the least-recently connected node re-establishes its
283 // connected status, drop the pending node.
284 if pos == Position(0) && status == NodeStatus::Connected {
285 self.pending = None
286 }
287 // Reinsert the node with the desired status.
288 match self.insert(node, status) {
289 InsertResult::Inserted => {}
290 _ => unreachable!("The node is removed before being (re)inserted."),
291 }
292 }
293 }
294
295 /// Inserts a new node into the bucket with the given status.
296 ///
297 /// The status of the node to insert determines the result as follows:
298 ///
299 /// * `NodeStatus::Connected`: If the bucket is full and either all nodes are connected
300 /// or there is already a pending node, insertion fails with `InsertResult::Full`.
301 /// If the bucket is full but at least one node is disconnected and there is no pending
302 /// node, the new node is inserted as pending, yielding `InsertResult::Pending`.
303 /// Otherwise the bucket has free slots and the new node is added to the end of the
304 /// bucket as the most-recently connected node.
305 ///
306 /// * `NodeStatus::Disconnected`: If the bucket is full, insertion fails with
307 /// `InsertResult::Full`. Otherwise the bucket has free slots and the new node
308 /// is inserted at the position preceding the first connected node,
309 /// i.e. as the most-recently disconnected node. If there are no connected nodes,
310 /// the new node is added as the last element of the bucket.
311 ///
312 pub(crate) fn insert(
313 &mut self,
314 node: Node<TKey, TVal>,
315 status: NodeStatus,
316 ) -> InsertResult<TKey> {
317 match status {
318 NodeStatus::Connected => {
319 if self.nodes.is_full() {
320 if self.first_connected_pos == Some(0) || self.pending.is_some() {
321 return InsertResult::Full;
322 } else {
323 self.pending = Some(PendingNode {
324 node,
325 status: NodeStatus::Connected,
326 replace: Instant::now() + self.pending_timeout,
327 });
328 return InsertResult::Pending {
329 disconnected: self.nodes[0].key.clone(),
330 };
331 }
332 }
333 let pos = self.nodes.len();
334 self.first_connected_pos = self.first_connected_pos.or(Some(pos));
335 self.nodes.push(node);
336 InsertResult::Inserted
337 }
338 NodeStatus::Disconnected => {
339 if self.nodes.is_full() {
340 return InsertResult::Full;
341 }
342 if let Some(ref mut p) = self.first_connected_pos {
343 self.nodes.insert(*p, node);
344 *p += 1;
345 } else {
346 self.nodes.push(node);
347 }
348 InsertResult::Inserted
349 }
350 }
351 }
352
353 /// Removes the node with the given key from the bucket, if it exists.
354 pub(crate) fn remove(
355 &mut self,
356 key: &TKey,
357 ) -> Option<(Node<TKey, TVal>, NodeStatus, Position)> {
358 if let Some(pos) = self.position(key) {
359 // Remove the node from its current position.
360 let status = self.status(pos);
361 let node = self.nodes.remove(pos.0);
362 // Adjust `first_connected_pos` accordingly.
363 match status {
364 NodeStatus::Connected => {
365 if self.first_connected_pos.map_or(false, |p| p == pos.0)
366 && pos.0 == self.nodes.len()
367 {
368 // It was the last connected node.
369 self.first_connected_pos = None
370 }
371 }
372 NodeStatus::Disconnected => {
373 if let Some(ref mut p) = self.first_connected_pos {
374 *p -= 1;
375 }
376 }
377 }
378 Some((node, status, pos))
379 } else {
380 None
381 }
382 }
383
384 /// Returns the status of the node at the given position.
385 pub(crate) fn status(&self, pos: Position) -> NodeStatus {
386 if self.first_connected_pos.map_or(false, |i| pos.0 >= i) {
387 NodeStatus::Connected
388 } else {
389 NodeStatus::Disconnected
390 }
391 }
392
393 /// Gets the number of entries currently in the bucket.
394 pub(crate) fn num_entries(&self) -> usize {
395 self.nodes.len()
396 }
397
398 /// Gets the number of entries in the bucket that are considered connected.
399 #[cfg(test)]
400 pub(crate) fn num_connected(&self) -> usize {
401 self.first_connected_pos.map_or(0, |i| self.nodes.len() - i)
402 }
403
404 /// Gets the number of entries in the bucket that are considered disconnected.
405 #[cfg(test)]
406 pub(crate) fn num_disconnected(&self) -> usize {
407 self.nodes.len() - self.num_connected()
408 }
409
410 /// Gets the position of an node in the bucket.
411 pub(crate) fn position(&self, key: &TKey) -> Option<Position> {
412 self.nodes
413 .iter()
414 .position(|p| p.key.as_ref() == key.as_ref())
415 .map(Position)
416 }
417
418 /// Gets a mutable reference to the node identified by the given key.
419 ///
420 /// Returns `None` if the given key does not refer to a node in the
421 /// bucket.
422 pub(crate) fn get_mut(&mut self, key: &TKey) -> Option<&mut Node<TKey, TVal>> {
423 self.nodes
424 .iter_mut()
425 .find(move |p| p.key.as_ref() == key.as_ref())
426 }
427}
428
429#[cfg(test)]
430mod tests {
431 use super::*;
432 use libp2p_identity::PeerId;
433 use quickcheck::*;
434 use std::collections::VecDeque;
435
436 impl Arbitrary for KBucket<Key<PeerId>, ()> {
437 fn arbitrary(g: &mut Gen) -> KBucket<Key<PeerId>, ()> {
438 let timeout = Duration::from_secs(g.gen_range(1..g.size()) as u64);
439 let mut bucket = KBucket::<Key<PeerId>, ()>::new(timeout);
440 let num_nodes = g.gen_range(1..K_VALUE.get() + 1);
441 for _ in 0..num_nodes {
442 let key = Key::from(PeerId::random());
443 let node = Node {
444 key: key.clone(),
445 value: (),
446 };
447 let status = NodeStatus::arbitrary(g);
448 match bucket.insert(node, status) {
449 InsertResult::Inserted => {}
450 _ => panic!(),
451 }
452 }
453 bucket
454 }
455 }
456
457 impl Arbitrary for NodeStatus {
458 fn arbitrary(g: &mut Gen) -> NodeStatus {
459 if bool::arbitrary(g) {
460 NodeStatus::Connected
461 } else {
462 NodeStatus::Disconnected
463 }
464 }
465 }
466
467 impl Arbitrary for Position {
468 fn arbitrary(g: &mut Gen) -> Position {
469 Position(g.gen_range(0..K_VALUE.get()))
470 }
471 }
472
473 // Fill a bucket with random nodes with the given status.
474 fn fill_bucket(bucket: &mut KBucket<Key<PeerId>, ()>, status: NodeStatus) {
475 let num_entries_start = bucket.num_entries();
476 for i in 0..K_VALUE.get() - num_entries_start {
477 let key = Key::from(PeerId::random());
478 let node = Node { key, value: () };
479 assert_eq!(InsertResult::Inserted, bucket.insert(node, status));
480 assert_eq!(bucket.num_entries(), num_entries_start + i + 1);
481 }
482 }
483
484 #[test]
485 fn ordering() {
486 fn prop(status: Vec<NodeStatus>) -> bool {
487 let mut bucket = KBucket::<Key<PeerId>, ()>::new(Duration::from_secs(1));
488
489 // The expected lists of connected and disconnected nodes.
490 let mut connected = VecDeque::new();
491 let mut disconnected = VecDeque::new();
492
493 // Fill the bucket, thereby populating the expected lists in insertion order.
494 for status in status {
495 let key = Key::from(PeerId::random());
496 let node = Node {
497 key: key.clone(),
498 value: (),
499 };
500 let full = bucket.num_entries() == K_VALUE.get();
501 if let InsertResult::Inserted = bucket.insert(node, status) {
502 let vec = match status {
503 NodeStatus::Connected => &mut connected,
504 NodeStatus::Disconnected => &mut disconnected,
505 };
506 if full {
507 vec.pop_front();
508 }
509 vec.push_back((status, key.clone()));
510 }
511 }
512
513 // Get all nodes from the bucket, together with their status.
514 let mut nodes = bucket
515 .iter()
516 .map(|(n, s)| (s, n.key.clone()))
517 .collect::<Vec<_>>();
518
519 // Split the list of nodes at the first connected node.
520 let first_connected_pos = nodes.iter().position(|(s, _)| *s == NodeStatus::Connected);
521 assert_eq!(bucket.first_connected_pos, first_connected_pos);
522 let tail = first_connected_pos.map_or(Vec::new(), |p| nodes.split_off(p));
523
524 // All nodes before the first connected node must be disconnected and
525 // in insertion order. Similarly, all remaining nodes must be connected
526 // and in insertion order.
527 disconnected == nodes && connected == tail
528 }
529
530 quickcheck(prop as fn(_) -> _);
531 }
532
533 #[test]
534 fn full_bucket() {
535 let mut bucket = KBucket::<Key<PeerId>, ()>::new(Duration::from_secs(1));
536
537 // Fill the bucket with disconnected nodes.
538 fill_bucket(&mut bucket, NodeStatus::Disconnected);
539
540 // Trying to insert another disconnected node fails.
541 let key = Key::from(PeerId::random());
542 let node = Node { key, value: () };
543 match bucket.insert(node, NodeStatus::Disconnected) {
544 InsertResult::Full => {}
545 x => panic!("{x:?}"),
546 }
547
548 // One-by-one fill the bucket with connected nodes, replacing the disconnected ones.
549 for i in 0..K_VALUE.get() {
550 let (first, first_status) = bucket.iter().next().unwrap();
551 let first_disconnected = first.clone();
552 assert_eq!(first_status, NodeStatus::Disconnected);
553
554 // Add a connected node, which is expected to be pending, scheduled to
555 // replace the first (i.e. least-recently connected) node.
556 let key = Key::from(PeerId::random());
557 let node = Node {
558 key: key.clone(),
559 value: (),
560 };
561 match bucket.insert(node.clone(), NodeStatus::Connected) {
562 InsertResult::Pending { disconnected } => {
563 assert_eq!(disconnected, first_disconnected.key)
564 }
565 x => panic!("{x:?}"),
566 }
567
568 // Trying to insert another connected node fails.
569 match bucket.insert(node.clone(), NodeStatus::Connected) {
570 InsertResult::Full => {}
571 x => panic!("{x:?}"),
572 }
573
574 assert!(bucket.pending().is_some());
575
576 // Apply the pending node.
577 let pending = bucket.pending_mut().expect("No pending node.");
578 pending.set_ready_at(Instant::now().checked_sub(Duration::from_secs(1)).unwrap());
579 let result = bucket.apply_pending();
580 assert_eq!(
581 result,
582 Some(AppliedPending {
583 inserted: node.clone(),
584 evicted: Some(first_disconnected)
585 })
586 );
587 assert_eq!(Some((&node, NodeStatus::Connected)), bucket.iter().last());
588 assert!(bucket.pending().is_none());
589 assert_eq!(Some(K_VALUE.get() - (i + 1)), bucket.first_connected_pos);
590 }
591
592 assert!(bucket.pending().is_none());
593 assert_eq!(K_VALUE.get(), bucket.num_entries());
594
595 // Trying to insert another connected node fails.
596 let key = Key::from(PeerId::random());
597 let node = Node { key, value: () };
598 match bucket.insert(node, NodeStatus::Connected) {
599 InsertResult::Full => {}
600 x => panic!("{x:?}"),
601 }
602 }
603
604 #[test]
605 fn full_bucket_discard_pending() {
606 let mut bucket = KBucket::<Key<PeerId>, ()>::new(Duration::from_secs(1));
607 fill_bucket(&mut bucket, NodeStatus::Disconnected);
608 let (first, _) = bucket.iter().next().unwrap();
609 let first_disconnected = first.clone();
610
611 // Add a connected pending node.
612 let key = Key::from(PeerId::random());
613 let node = Node {
614 key: key.clone(),
615 value: (),
616 };
617 if let InsertResult::Pending { disconnected } = bucket.insert(node, NodeStatus::Connected) {
618 assert_eq!(&disconnected, &first_disconnected.key);
619 } else {
620 panic!()
621 }
622 assert!(bucket.pending().is_some());
623
624 // Update the status of the first disconnected node to be connected.
625 bucket.update(&first_disconnected.key, NodeStatus::Connected);
626
627 // The pending node has been discarded.
628 assert!(bucket.pending().is_none());
629 assert!(bucket.iter().all(|(n, _)| n.key != key));
630
631 // The initially disconnected node is now the most-recently connected.
632 assert_eq!(
633 Some((&first_disconnected, NodeStatus::Connected)),
634 bucket.iter().last()
635 );
636 assert_eq!(
637 bucket.position(&first_disconnected.key).map(|p| p.0),
638 bucket.first_connected_pos
639 );
640 assert_eq!(1, bucket.num_connected());
641 assert_eq!(K_VALUE.get() - 1, bucket.num_disconnected());
642 }
643
644 #[test]
645 fn bucket_update() {
646 fn prop(mut bucket: KBucket<Key<PeerId>, ()>, pos: Position, status: NodeStatus) -> bool {
647 let num_nodes = bucket.num_entries();
648
649 // Capture position and key of the random node to update.
650 let pos = pos.0 % num_nodes;
651 let key = bucket.nodes[pos].key.clone();
652
653 // Record the (ordered) list of status of all nodes in the bucket.
654 let mut expected = bucket
655 .iter()
656 .map(|(n, s)| (n.key.clone(), s))
657 .collect::<Vec<_>>();
658
659 // Update the node in the bucket.
660 bucket.update(&key, status);
661
662 // Check that the bucket now contains the node with the new status,
663 // preserving the status and relative order of all other nodes.
664 let expected_pos = match status {
665 NodeStatus::Connected => num_nodes - 1,
666 NodeStatus::Disconnected => bucket.first_connected_pos.unwrap_or(num_nodes) - 1,
667 };
668 expected.remove(pos);
669 expected.insert(expected_pos, (key.clone(), status));
670 let actual = bucket
671 .iter()
672 .map(|(n, s)| (n.key.clone(), s))
673 .collect::<Vec<_>>();
674 expected == actual
675 }
676
677 quickcheck(prop as fn(_, _, _) -> _);
678 }
679}