hash_rings/consistent.rs
1//! Hashing ring implemented using consistent hashing.
2
3use crate::util;
4use std::collections::hash_map::RandomState;
5use std::collections::{BTreeMap, HashMap, HashSet};
6use std::hash::{BuildHasher, Hash};
7use std::iter::Iterator;
8use std::vec::Vec;
9
10/// A hashing ring implemented using consistent hashing.
11///
12/// Consistent hashing is based on mapping each node to a pseudorandom value. In this
13/// implementation the pseudorandom is a combination of the hash of the node and the hash of the
14/// replica number. A point is also represented as a pseudorandom value and it is mapped to the
15/// node with the smallest value that is greater than or equal to the point's value. If such a
16/// node does not exist, then the point maps to the node with the smallest value.
17///
18/// # Examples
19/// ```
20/// use hash_rings::consistent::Ring;
21/// use std::collections::hash_map::DefaultHasher;
22/// use std::hash::BuildHasherDefault;
23///
24/// type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
25///
26/// let mut ring = Ring::with_hasher(DefaultBuildHasher::default());
27///
28/// ring.insert_node(&"node-1", 1);
29/// ring.insert_node(&"node-2", 3);
30///
31/// ring.remove_node(&"node-1");
32///
33/// assert_eq!(ring.get_node(&"point-1"), &"node-2");
34/// assert_eq!(ring.len(), 1);
35///
36/// let mut iterator = ring.iter();
37/// assert_eq!(iterator.next(), Some((&"node-2", 3)));
38/// assert_eq!(iterator.next(), None);
39/// ```
40pub struct Ring<'a, T, H = RandomState> {
41 nodes: BTreeMap<u64, &'a T>,
42 replicas: HashMap<&'a T, usize>,
43 hash_builder: H,
44}
45
46impl<'a, T> Ring<'a, T, RandomState> {
47 /// Constructs a new, empty `Ring<T>`.
48 ///
49 /// # Examples
50 ///
51 /// ```
52 /// use hash_rings::consistent::Ring;
53 ///
54 /// let mut ring: Ring<&str> = Ring::new();
55 /// ```
56 pub fn new() -> Self
57 where
58 T: Hash + Eq,
59 {
60 Self::default()
61 }
62}
63
64impl<'a, T, H> Ring<'a, T, H> {
65 /// Constructs a new, empty `Ring<T>` with a specified hash builder.
66 ///
67 /// # Examples
68 ///
69 /// ```
70 /// use hash_rings::consistent::Ring;
71 /// use std::collections::hash_map::DefaultHasher;
72 /// use std::hash::BuildHasherDefault;
73 ///
74 /// type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
75 ///
76 /// let mut ring: Ring<&str, _> = Ring::with_hasher(DefaultBuildHasher::default());
77 /// ```
78 pub fn with_hasher(hash_builder: H) -> Self
79 where
80 T: Hash + Eq,
81 H: BuildHasher + Default,
82 {
83 Self {
84 nodes: BTreeMap::new(),
85 replicas: HashMap::new(),
86 hash_builder,
87 }
88 }
89
90 fn get_next_node(&self, hash: u64) -> Option<&T> {
91 self.nodes
92 .range(hash..)
93 .next()
94 .or_else(|| self.nodes.iter().next())
95 .map(|entry| *entry.1)
96 }
97
98 /// Inserts a node into the ring with a number of replicas.
99 ///
100 /// Increasing the number of replicas will increase the number of expected points mapped to the
101 /// node. For example, a node with three replicas will receive approximately three times more
102 /// points than a node with one replica.
103 ///
104 /// # Examples
105 ///
106 /// ```
107 /// use hash_rings::consistent::Ring;
108 ///
109 /// let mut ring: Ring<&str> = Ring::new();
110 ///
111 /// // "node-2" will receive three times more points than "node-1"
112 /// ring.insert_node(&"node-1", 1);
113 /// ring.insert_node(&"node-2", 3);
114 /// ```
115 pub fn insert_node(&mut self, id: &'a T, replicas: usize)
116 where
117 T: Hash + Eq,
118 H: BuildHasher,
119 {
120 for i in 0..replicas {
121 let hash = util::combine_hash(
122 &self.hash_builder,
123 util::gen_hash(&self.hash_builder, id),
124 util::gen_hash(&self.hash_builder, &i),
125 );
126 self.nodes.insert(hash, id);
127 }
128 self.replicas.insert(id, replicas);
129 }
130
131 /// Removes a node and all its replicas from the ring.
132 ///
133 /// # Examples
134 ///
135 /// ```
136 /// use hash_rings::consistent::Ring;
137 ///
138 /// let mut ring: Ring<&str> = Ring::new();
139 ///
140 /// ring.insert_node(&"node-1", 1);
141 /// ring.insert_node(&"node-2", 1);
142 /// ring.remove_node(&"node-2");
143 /// ```
144 pub fn remove_node(&mut self, id: &T)
145 where
146 T: Hash + Eq,
147 H: BuildHasher,
148 {
149 for i in 0..self.replicas[id] {
150 let hash = util::combine_hash(
151 &self.hash_builder,
152 util::gen_hash(&self.hash_builder, id),
153 util::gen_hash(&self.hash_builder, &i),
154 );
155 let should_remove = {
156 if let Some(existing_id) = self.nodes.get(&hash) {
157 *existing_id == id
158 } else {
159 false
160 }
161 };
162
163 if should_remove {
164 self.nodes.remove(&hash);
165 }
166 }
167 self.replicas.remove(id);
168 }
169
170 /// Returns the node associated with a point.
171 ///
172 /// # Panics
173 ///
174 /// Panics if the ring is empty.
175 ///
176 /// # Examples
177 ///
178 /// ```
179 /// use hash_rings::consistent::Ring;
180 ///
181 /// let mut ring: Ring<&str> = Ring::new();
182 ///
183 /// ring.insert_node(&"node-1", 1);
184 /// assert_eq!(ring.get_node(&"point-1"), &"node-1");
185 /// ```
186 pub fn get_node<U>(&self, point: &U) -> &T
187 where
188 U: Hash,
189 H: BuildHasher,
190 {
191 let hash = util::gen_hash(&self.hash_builder, point);
192 match self.get_next_node(hash) {
193 Some(node) => &*node,
194 None => panic!("Error: empty ring."),
195 }
196 }
197
198 fn contains_node(&self, index: u64) -> bool {
199 self.nodes.contains_key(&index)
200 }
201
202 fn get_replica_count(&self, id: &T) -> usize
203 where
204 T: Hash + Eq,
205 {
206 self.replicas[id]
207 }
208
209 /// Returns the number of nodes in the ring.
210 ///
211 /// # Examples
212 ///
213 /// ```
214 /// use hash_rings::consistent::Ring;
215 ///
216 /// let mut ring: Ring<&str> = Ring::new();
217 ///
218 /// ring.insert_node(&"node-1", 3);
219 /// assert_eq!(ring.len(), 1);
220 /// ```
221 pub fn len(&self) -> usize
222 where
223 T: Hash + Eq,
224 {
225 self.replicas.len()
226 }
227
228 /// Returns `true` if the ring is empty.
229 ///
230 /// # Examples
231 ///
232 /// ```
233 /// use hash_rings::consistent::Ring;
234 ///
235 /// let mut ring: Ring<&str> = Ring::new();
236 ///
237 /// assert!(ring.is_empty());
238 /// ring.insert_node(&"node-1", 3);
239 /// assert!(!ring.is_empty());
240 /// ```
241 pub fn is_empty(&self) -> bool
242 where
243 T: Hash + Eq,
244 {
245 self.replicas.is_empty()
246 }
247
248 /// Returns an iterator over the ring. The iterator will yield nodes and the replica count in
249 /// no particular order.
250 ///
251 /// # Examples
252 ///
253 /// ```
254 /// use hash_rings::consistent::Ring;
255 ///
256 /// let mut ring = Ring::new();
257 /// ring.insert_node(&"node-1", 1);
258 ///
259 /// let mut iterator = ring.iter();
260 /// assert_eq!(iterator.next(), Some((&"node-1", 1)));
261 /// assert_eq!(iterator.next(), None);
262 /// ```
263 pub fn iter(&'a self) -> impl Iterator<Item = (&'a T, usize)>
264 where
265 T: Hash + Eq,
266 {
267 self.replicas.iter().map(|replica| {
268 let (id, replica_count) = replica;
269 (&**id, *replica_count)
270 })
271 }
272}
273
274impl<'a, T, H> IntoIterator for &'a Ring<'a, T, H>
275where
276 T: Hash + Eq,
277{
278 type IntoIter = Box<dyn Iterator<Item = (&'a T, usize)> + 'a>;
279 type Item = (&'a T, usize);
280
281 fn into_iter(self) -> Self::IntoIter {
282 Box::new(self.iter())
283 }
284}
285
286impl<'a, T, H> Default for Ring<'a, T, H>
287where
288 T: Hash + Eq,
289 H: BuildHasher + Default,
290{
291 fn default() -> Self {
292 Self::with_hasher(Default::default())
293 }
294}
295
296/// A client that uses `Ring<T>`.
297///
298/// # Examples
299/// ```
300/// use hash_rings::consistent::Client;
301///
302/// let mut client = Client::new();
303/// client.insert_node(&"node-1", 3);
304/// client.insert_point(&"point-1");
305/// client.insert_point(&"point-2");
306///
307/// assert_eq!(client.len(), 1);
308/// assert_eq!(client.get_node(&"point-1"), &"node-1");
309///
310/// client.remove_point(&"point-2");
311/// assert_eq!(client.get_points(&"node-1"), [&"point-1"]);
312/// ```
313pub struct Client<'a, T, U, H = RandomState> {
314 ring: Ring<'a, T, H>,
315 data: BTreeMap<u64, HashSet<&'a U>>,
316}
317
318impl<'a, T, U> Client<'a, T, U, RandomState> {
319 /// Constructs a new, empty `Client<T, U>`.
320 ///
321 /// # Examples
322 ///
323 /// ```
324 /// use hash_rings::consistent::Client;
325 ///
326 /// let mut client: Client<&str, &str> = Client::new();
327 /// ```
328 pub fn new() -> Self
329 where
330 T: Hash + Eq,
331 U: Hash + Eq,
332 {
333 Self::default()
334 }
335}
336
337impl<'a, T, U, H> Client<'a, T, U, H> {
338 /// Constructs a new, empty `Client<T, U>` with a specified hash builder.
339 ///
340 /// # Examples
341 ///
342 /// ```
343 /// use hash_rings::consistent::Client;
344 /// use std::collections::hash_map::DefaultHasher;
345 /// use std::hash::BuildHasherDefault;
346 ///
347 /// type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
348 ///
349 /// let mut client: Client<&str, &str, _> = Client::with_hasher(DefaultBuildHasher::default());
350 /// ```
351 pub fn with_hasher(hash_builder: H) -> Self
352 where
353 T: Hash + Eq,
354 U: Hash + Eq,
355 H: BuildHasher + Default,
356 {
357 Self {
358 ring: Ring::with_hasher(hash_builder),
359 data: BTreeMap::new(),
360 }
361 }
362
363 fn get_next_node(&mut self, hash: u64) -> Option<(u64, &mut HashSet<&'a U>)> {
364 if self.data.range_mut(hash..).next().is_some() {
365 self.data
366 .range_mut(hash..)
367 .next()
368 .map(|entry| (*entry.0, entry.1))
369 } else if self.data.iter_mut().next().is_some() {
370 self.data.iter_mut().next().map(|entry| (*entry.0, entry.1))
371 } else {
372 None
373 }
374 }
375
376 /// Inserts a node into the ring with a number of replicas.
377 ///
378 /// Increasing the number of replicas will increase the number of expected points mapped to the
379 /// node. For example, a node with three replicas will receive approximately three times more
380 /// points than a node with one replica.
381 ///
382 /// # Examples
383 ///
384 /// ```
385 /// use hash_rings::consistent::Client;
386 ///
387 /// let mut client: Client<&str, &str> = Client::new();
388 ///
389 /// // "node-2" will receive three times more points than "node-1"
390 /// client.insert_node(&"node-1", 1);
391 /// client.insert_node(&"node-2", 3);
392 /// ```
393 pub fn insert_node(&mut self, id: &'a T, replicas: usize)
394 where
395 T: Hash + Eq,
396 U: Hash + Eq,
397 H: BuildHasher,
398 {
399 let new_hashes = (0..replicas)
400 .map(|replica| {
401 util::combine_hash(
402 &self.ring.hash_builder,
403 util::gen_hash(&self.ring.hash_builder, &id),
404 util::gen_hash(&self.ring.hash_builder, &replica),
405 )
406 })
407 .collect::<Vec<u64>>();
408 self.ring.insert_node(id, replicas);
409 for new_hash in new_hashes {
410 // If hash already exists, then no additional work is needed to be done.
411 if self.data.contains_key(&new_hash) {
412 continue;
413 }
414 let hash = match self.get_next_node(new_hash) {
415 Some((hash, _)) => hash,
416 None => {
417 self.data.insert(new_hash, HashSet::new());
418 continue;
419 }
420 };
421 let Client { ring, data } = self;
422 let (old_set, new_set) = data
423 .get_mut(&hash)
424 .expect("Expected node to exist.")
425 .drain()
426 .partition(|point| {
427 let point_hash = util::gen_hash(&ring.hash_builder, point);
428 if new_hash < hash {
429 new_hash < point_hash && point_hash <= hash
430 } else {
431 new_hash < point_hash || point_hash <= hash
432 }
433 });
434 self.data.insert(hash, old_set);
435 self.data.insert(new_hash, new_set);
436 }
437 }
438
439 /// Removes a node and all its replicas from the ring.
440 ///
441 /// # Panics
442 ///
443 /// Panics if the ring is empty after removal of a node or if the node does not exist.
444 ///
445 /// # Examples
446 ///
447 /// ```
448 /// use hash_rings::consistent::Client;
449 ///
450 /// let mut client: Client<&str, &str> = Client::new();
451 ///
452 /// client.insert_node(&"node-1", 1);
453 /// client.insert_node(&"node-2", 1);
454 /// client.remove_node(&"node-2");
455 /// ```
456 pub fn remove_node(&mut self, id: &T)
457 where
458 T: Hash + Eq,
459 U: Hash + Eq,
460 H: BuildHasher,
461 {
462 let replicas = self.ring.get_replica_count(id);
463 self.ring.remove_node(id);
464 for i in 0..replicas {
465 let hash = util::combine_hash(
466 &self.ring.hash_builder,
467 util::gen_hash(&self.ring.hash_builder, id),
468 util::gen_hash(&self.ring.hash_builder, &i),
469 );
470 if !self.ring.contains_node(hash) {
471 if let Some(points) = self.data.remove(&hash) {
472 if let Some((_, next_points)) = self.get_next_node(hash) {
473 next_points.extend(points);
474 } else {
475 panic!("Error: empty ring after deletion.");
476 }
477 }
478 }
479 }
480 }
481
482 /// Returns the points associated with a node and its replicas.
483 ///
484 /// # Panics
485 ///
486 /// Panics if the node does not exist.
487 ///
488 /// # Examples
489 ///
490 /// ```
491 /// use hash_rings::consistent::Client;
492 ///
493 /// let mut client: Client<&str, &str> = Client::new();
494 ///
495 /// client.insert_node(&"node-1", 1);
496 /// client.insert_point(&"point-1");
497 /// assert_eq!(client.get_points(&"node-1"), [&"point-1"]);
498 /// ```
499 pub fn get_points(&self, id: &T) -> Vec<&U>
500 where
501 T: Hash + Eq,
502 U: Hash + Eq,
503 H: BuildHasher,
504 {
505 let mut ret: Vec<&U> = Vec::new();
506 for i in 0..self.ring.get_replica_count(id) {
507 let hash = util::combine_hash(
508 &self.ring.hash_builder,
509 util::gen_hash(&self.ring.hash_builder, id),
510 util::gen_hash(&self.ring.hash_builder, &i),
511 );
512 if let Some(points) = self.data.get(&hash) {
513 ret.extend(points.iter());
514 }
515 }
516 ret
517 }
518
519 /// Returns the node associated with a point.
520 ///
521 /// # Panics
522 ///
523 /// Panics if the ring is empty.
524 ///
525 /// # Examples
526 ///
527 /// ```
528 /// use hash_rings::consistent::Client;
529 ///
530 /// let mut client: Client<&str, &str> = Client::new();
531 ///
532 /// client.insert_node(&"node-1", 1);
533 /// client.insert_point(&"point-1");
534 /// assert_eq!(client.get_node(&"point-1"), &"node-1");
535 /// ```
536 pub fn get_node(&self, point: &U) -> &T
537 where
538 U: Hash + Eq,
539 H: BuildHasher,
540 {
541 self.ring.get_node(point)
542 }
543
544 /// Inserts a point into the ring and returns the node associated with the inserted point.
545 ///
546 /// # Panics
547 ///
548 /// Panics if the ring is empty.
549 ///
550 /// # Examples
551 ///
552 /// ```
553 /// use hash_rings::consistent::Client;
554 ///
555 /// let mut client = Client::new();
556 /// client.insert_node(&"node-1", 1);
557 /// client.insert_point(&"point-1");
558 /// ```
559 pub fn insert_point(&mut self, point: &'a U) -> &T
560 where
561 U: Hash + Eq,
562 H: BuildHasher,
563 {
564 let hash = util::gen_hash(&self.ring.hash_builder, point);
565 if let Some((_, points)) = self.get_next_node(hash) {
566 points.insert(point);
567 self.ring.get_node(point)
568 } else {
569 panic!("Error: empty ring.");
570 }
571 }
572
573 /// Removes a point from the ring.
574 ///
575 /// # Panics
576 ///
577 /// Panics if the ring is empty.
578 ///
579 /// # Examples
580 ///
581 /// ```
582 /// use hash_rings::consistent::Client;
583 ///
584 /// let mut client = Client::new();
585 /// client.insert_node(&"node-1", 1);
586 /// client.insert_point(&"point-1");
587 /// client.remove_point(&"point-1");
588 /// ```
589 pub fn remove_point(&mut self, point: &U)
590 where
591 U: Hash + Eq,
592 H: BuildHasher,
593 {
594 let hash = util::gen_hash(&self.ring.hash_builder, &point);
595 if let Some((_, points)) = self.get_next_node(hash) {
596 points.remove(point);
597 } else {
598 panic!("Error: empty ring.");
599 }
600 }
601
602 /// Returns the number of nodes in the ring.
603 ///
604 /// # Examples
605 ///
606 /// ```
607 /// use hash_rings::consistent::Client;
608 ///
609 /// let mut client: Client<&str, &str> = Client::new();
610 ///
611 /// client.insert_node(&"node-1", 3);
612 /// assert_eq!(client.len(), 1);
613 /// ```
614 pub fn len(&self) -> usize
615 where
616 T: Hash + Eq,
617 {
618 self.ring.len()
619 }
620
621 /// Returns `true` if the ring is empty.
622 ///
623 /// # Examples
624 ///
625 /// ```
626 /// use hash_rings::consistent::Client;
627 ///
628 /// let mut client: Client<&str, &str> = Client::new();
629 ///
630 /// assert!(client.is_empty());
631 /// client.insert_node(&"node-1", 3);
632 /// assert!(!client.is_empty());
633 /// ```
634 pub fn is_empty(&self) -> bool
635 where
636 T: Hash + Eq,
637 {
638 self.ring.is_empty()
639 }
640
641 /// Returns an iterator over the ring. The iterator will yield nodes and points in no
642 /// particular order.
643 ///
644 /// # Examples
645 ///
646 /// ```
647 /// use hash_rings::consistent::Client;
648 ///
649 /// let mut client = Client::new();
650 /// client.insert_node(&"node-1", 1);
651 /// client.insert_point(&"point-1");
652 ///
653 /// let mut iterator = client.iter();
654 /// assert_eq!(iterator.next(), Some((&"node-1", vec![&"point-1"])));
655 /// assert_eq!(iterator.next(), None);
656 /// ```
657 pub fn iter(&'a self) -> impl Iterator<Item = (&'a T, Vec<&'a U>)>
658 where
659 T: Hash + Eq,
660 U: Hash + Eq,
661 H: BuildHasher,
662 {
663 self.ring.iter().map(move |replica| {
664 let mut points = Vec::new();
665 for i in 0..replica.1 {
666 let hash = util::combine_hash(
667 &self.ring.hash_builder,
668 util::gen_hash(&self.ring.hash_builder, &*replica.0),
669 util::gen_hash(&self.ring.hash_builder, &i),
670 );
671 points.extend(&self.data[&hash])
672 }
673 (replica.0, points)
674 })
675 }
676}
677
678impl<'a, T, U, H> IntoIterator for &'a Client<'a, T, U, H>
679where
680 T: Hash + Eq,
681 U: Hash + Eq,
682 H: BuildHasher,
683{
684 type IntoIter = Box<dyn Iterator<Item = (&'a T, Vec<&'a U>)> + 'a>;
685 type Item = (&'a T, Vec<&'a U>);
686
687 fn into_iter(self) -> Self::IntoIter {
688 Box::new(self.iter())
689 }
690}
691
692impl<'a, T, U, H> Default for Client<'a, T, U, H>
693where
694 T: Hash + Eq,
695 U: Hash + Eq,
696 H: BuildHasher + Default,
697{
698 fn default() -> Self {
699 Self::with_hasher(Default::default())
700 }
701}
702
703#[cfg(test)]
704mod tests {
705 use super::Client;
706 use crate::test_util::{BuildAddHasher, BuildDefaultHasher};
707 use std::hash::{Hash, Hasher};
708
709 #[test]
710 fn test_size_empty() {
711 let client: Client<'_, u32, u32> = Client::new();
712 assert!(client.is_empty());
713 assert_eq!(client.len(), 0);
714 }
715
716 #[test]
717 #[should_panic]
718 fn test_panic_remove_node_empty_client() {
719 let mut client: Client<'_, u32, u32> = Client::new();
720 client.insert_node(&0, 1);
721 client.remove_node(&0);
722 }
723
724 #[test]
725 #[should_panic]
726 fn test_panic_remove_node_non_existent_node() {
727 let mut client: Client<'_, u32, u32> = Client::new();
728 client.remove_node(&0);
729 }
730
731 #[test]
732 #[should_panic]
733 fn test_panic_get_node_empty_client() {
734 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
735 client.get_node(&0);
736 }
737
738 #[test]
739 #[should_panic]
740 fn test_panic_insert_point_empty_client() {
741 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
742 client.insert_point(&0);
743 }
744
745 #[test]
746 #[should_panic]
747 fn test_panic_remove_point_empty_client() {
748 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
749 client.remove_point(&0);
750 }
751
752 pub struct Key(pub u32);
753 impl Hash for Key {
754 fn hash<H>(&self, state: &mut H)
755 where
756 H: Hasher,
757 {
758 state.write_u32(self.0 / 2);
759 }
760 }
761
762 impl PartialEq for Key {
763 fn eq(&self, other: &Key) -> bool {
764 self.0 == other.0
765 }
766 }
767
768 impl Eq for Key {}
769
770 #[test]
771 fn test_insert_node_same_node() {
772 let mut client: Client<'_, Key, u32, BuildAddHasher> = Client::default();
773 client.insert_node(&Key(0), 1);
774 client.insert_point(&0);
775 client.insert_node(&Key(1), 1);
776 assert_eq!(client.get_points(&Key(0)), [&0u32]);
777 assert_eq!(client.get_points(&Key(1)), [&0u32]);
778 }
779
780 #[test]
781 fn test_insert_node_share_node() {
782 let mut client: Client<'_, Key, u32, BuildAddHasher> = Client::default();
783 client.insert_node(&Key(0), 1);
784 client.insert_point(&0);
785 client.insert_point(&1);
786 let mut actual: Vec<&u32> = client.get_points(&Key(0));
787 actual.sort();
788 assert_eq!(actual, [&0u32, &1u32]);
789 client.insert_node(&Key(2), 1);
790 assert_eq!(client.get_points(&Key(0)), [&0u32]);
791 assert_eq!(client.get_points(&Key(2)), [&1u32]);
792 }
793
794 #[test]
795 fn test_remove_node() {
796 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
797 client.insert_node(&0, 1);
798 client.insert_point(&0);
799 client.insert_node(&1, 1);
800 client.remove_node(&1);
801 assert_eq!(client.get_points(&0), [&0]);
802 }
803
804 #[test]
805 fn test_get_node() {
806 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
807 client.insert_node(&0, 3);
808 assert_eq!(client.get_node(&0), &0);
809 }
810
811 #[test]
812 fn test_insert_point() {
813 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
814 client.insert_node(&0, 3);
815 client.insert_point(&0);
816 assert_eq!(client.get_points(&0), [&0u32]);
817 }
818
819 #[test]
820 fn test_remove_point() {
821 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
822 client.insert_node(&0, 3);
823 client.insert_point(&0);
824 client.remove_point(&0);
825 let expected: [&u32; 0] = [];
826 assert_eq!(client.get_points(&0), expected);
827 }
828
829 #[test]
830 fn test_iter() {
831 let mut client: Client<'_, u32, u32, BuildDefaultHasher> = Client::default();
832 client.insert_node(&0, 3);
833 client.insert_point(&1);
834 client.insert_point(&2);
835 client.insert_point(&3);
836 client.insert_point(&4);
837 client.insert_point(&5);
838 let mut actual: Vec<(&u32, Vec<&u32>)> = client.iter().collect();
839 actual[0].1.sort();
840 assert_eq!(actual[0].0, &0);
841 assert_eq!(actual[0].1, [&1, &2, &3, &4, &5]);
842 }
843}