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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

use std::cmp::{Ord, Ordering::*};
use std::collections::HashMap;
use std::hash::{Hash, Hasher};

use nohash_hasher::{BuildNoHashHasher, IntMap};

macro_rules! PerfectHasher {
    ($name:ident, $size:ty) => {
        pub struct $name<C, H> {
            // Key is the Id
            alloted: IntMap<$size, C>,
            hasher: H,
        }

        impl<C, H> $name<C, H>
        where
            H: Hasher,
            C: Hash + Ord,
        {
            pub fn new(hasher: H) -> Self {
                $name {
                    alloted: IntMap::default(),
                    hasher,
                }
            }

            pub fn with_capacity(capacity: $size, hasher: H) -> Self {
                $name {
                    alloted: HashMap::with_capacity_and_hasher(
                        capacity as usize,
                        BuildNoHashHasher::default(),
                    ),
                    hasher,
                }
            }

            pub fn unique_id(&mut self, content: C) -> $size {
                content.hash(&mut self.hasher);
                let mut hash = self.hasher.finish() as $size;

                loop {
                    let mut comparison = Equal;

                    let entry = self
                        .alloted
                        .entry(hash)
                        .and_modify(|cached| comparison = content.cmp(cached));

                    match comparison {
                        Equal => {
                            entry.or_insert(content);
                            return hash;
                        }
                        Less => hash = hash.wrapping_sub(1),
                        Greater => hash = hash.wrapping_add(1),
                    }
                }
            }

            pub fn dissociate(&mut self, id: $size) {
                self.alloted.remove(&id);
            }
        }
    };
}

PerfectHasher!(PerfectHasher8, u8);
PerfectHasher!(PerfectHasher16, u16);
PerfectHasher!(PerfectHasher32, u32);
PerfectHasher!(PerfectHasher64, u64);
PerfectHasher!(PerfectHasher, usize);

mod test {
    use super::*;

    /// A Hasher that always outputs `0` for testing purposes.
    #[allow(dead_code)]
    pub struct CollideHasher;

    impl Hasher for CollideHasher {
        fn write(&mut self, _: &[u8]) {}

        fn finish(&self) -> u64 {
            0
        }
    }

    #[test]
    fn collision_resilience() {
        let mut ph: PerfectHasher<char, CollideHasher> = PerfectHasher::new(CollideHasher);
        assert_eq!(0, ph.unique_id('a'));
        assert_eq!(1, ph.unique_id('b'));
    }

    #[test]
    fn collision_wrap() {
        let mut ph: PerfectHasher<char, CollideHasher> = PerfectHasher::new(CollideHasher);
        assert_eq!(0, ph.unique_id('b'));
        assert_eq!(usize::max_value(), ph.unique_id('a'));
    }

    #[test]
    fn dissociate() {
        let mut ph: PerfectHasher<char, CollideHasher> = PerfectHasher::new(CollideHasher);
        assert_eq!(0, ph.unique_id('a'));
        ph.dissociate(0);
        assert_eq!(0, ph.unique_id('b'));
    }
}