1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#![feature(btree_range, collections_bound)]
extern crate crc;
use crc::crc64::{ECMA, Digest, Hasher64};
use std::collections::BTreeMap;
use std::hash::{Hash, Hasher};
use std::collections::Bound::{Included, Excluded, Unbounded};
struct Hasher64StdHashHasher<T: Hasher64>(T);
impl<T> Hasher for Hasher64StdHashHasher<T>
where T: Hasher64
{
fn write(&mut self, bytes: &[u8]) {
self.0.write(bytes);
}
fn finish(&self) -> u64 {
self.0.sum64()
}
}
pub struct HashRing<B: Hash> {
buckets: BTreeMap<u64, B>,
}
impl<B> HashRing<B>
where B: Hash
{
pub fn new() -> HashRing<B> {
HashRing::<B> { buckets: BTreeMap::new() }
}
pub fn add_bucket(&mut self, bucket: B) {
let hash_code = HashRing::<B>::get_hash_code(&bucket);
self.buckets.insert(hash_code, bucket);
}
pub fn get_bucket<T>(&self, item: &T) -> Option<&B>
where T: Hash
{
let hash_code = HashRing::<B>::get_hash_code(item);
let back_half = self.buckets.range((Included(&hash_code), Unbounded)).next().map(|val| val.1);
let front_half = self.buckets
.range((Included(&0), Excluded(&hash_code)))
.next()
.map(|val| val.1);
back_half.or(front_half)
}
pub fn remove_bucket(&mut self, bucket: &B) -> bool {
let code = HashRing::<B>::get_hash_code(bucket);
match self.buckets.remove(&code) {
None => false,
Some(..) => true,
}
}
fn get_hash_code<H>(value: &H) -> u64
where H: Hash
{
let mut hasher = Hasher64StdHashHasher(Digest::new(ECMA));
value.hash(&mut hasher);
hasher.finish()
}
}