hash.rs

#[feature(managed_boxes)];
#[feature(macro_rules)];
#[feature(macro_registrar, macro_rules)];

extern mod extra;

use std::cast;
use std::hash::{Streaming, SipState};
use std::rc::Rc;
use std::rand;
use std::rand::Rng;

pub trait Hasher {
    fn result_u64(&mut self) -> u64;
}

pub trait StreamHasher: Hasher {
    fn input(&mut self, bytes: &[u8]);
}

//////////////////////////////////////////////////////////////////////////////

pub struct SipHasher {
    priv state: SipState,
}

impl SipHasher {
    #[inline]
    pub fn new() -> SipHasher {
        let mut r = rand::task_rng();
        SipHasher::new_with_keys(r.gen(), r.gen())
    }

    #[inline]
    pub fn new_with_keys(k0: u64, k1: u64) -> SipHasher {
        SipHasher {
            state: SipState::new(k0, k1)
        }
    }
}

impl Hasher for SipHasher {
    #[inline]
    fn result_u64(&mut self) -> u64 {
        self.state.result_u64()
    }
}

impl StreamHasher for SipHasher {
    #[inline]
    fn input(&mut self, bytes: &[u8]) {
        self.state.input(bytes);
    }
}

//////////////////////////////////////////////////////////////////////////////

pub struct FixedHasher {
    priv hash: Option<u64>,
}

impl FixedHasher {
    pub fn new() -> FixedHasher {
        FixedHasher { hash: None }
    }

    pub fn input_hash(&mut self, hash: u64) {
        assert!(self.hash.is_none());
        self.hash = Some(hash);
    }
}

impl Hasher for FixedHasher {
    fn result_u64(&mut self) -> u64 {
        assert!(self.hash.is_some());
        match self.hash {
            Some(hash) => hash,
            None => { fail!("hash was not set"); }
        }
    }
}

//////////////////////////////////////////////////////////////////////////////

pub trait Hashable<H: Hasher> {
    fn hash2(&self, h: &mut H);
}

impl<H: StreamHasher> Hashable<H> for bool {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as u8).hash2(hasher)
    }
}

impl<H: StreamHasher> Hashable<H> for u8 {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        hasher.input([*self])
    }
}

impl<H: StreamHasher> Hashable<H> for u16 {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        hasher.input([
            *self as u8,
            (*self >> 8) as u8,
        ])
    }
}

impl<H: StreamHasher> Hashable<H> for u32 {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        hasher.input([
            *self as u8,
            (*self >> 8) as u8,
            (*self >> 16) as u8,
            (*self >> 24) as u8,
        ])
    }
}

impl<H: StreamHasher> Hashable<H> for u64 {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        hasher.input([
            *self as u8,
            (*self >> 8) as u8,
            (*self >> 16) as u8,
            (*self >> 24) as u8,
            (*self >> 32) as u8,
            (*self >> 40) as u8,
            (*self >> 48) as u8,
            (*self >> 56) as u8,
        ])
    }
}

#[cfg(target_word_size = "32")]
impl<H: StreamHasher> Hashable<H> for uint {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as u32).hash2(hasher)
    }
}

#[cfg(target_word_size = "64")]
impl<H: StreamHasher> Hashable<H> for uint {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as u64).hash2(hasher)
    }
}

impl<H: StreamHasher> Hashable<H> for i8 {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as u8).hash2(hasher)
    }
}

impl<H: StreamHasher> Hashable<H> for i16 {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as u8).hash2(hasher)
    }
}

impl<H: StreamHasher> Hashable<H> for i32 {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as u8).hash2(hasher)
    }
}

impl<H: StreamHasher> Hashable<H> for i64 {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as u8).hash2(hasher)
    }
}

impl<H: StreamHasher> Hashable<H> for int {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as uint).hash2(hasher)
    }
}

impl<H: StreamHasher> Hashable<H> for char {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as u32).hash2(hasher)
    }
}

impl<H: StreamHasher> Hashable<H> for f32 {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        let i: u32 = unsafe {
            // 0.0 == -0.0 so they should also have the same hashcode
            cast::transmute(if *self == -0.0 { 0.0 } else { *self })
        };
        i.hash2(hasher)
    }
}

impl<H: StreamHasher> Hashable<H> for f64 {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        let i: u64 = unsafe {
            // 0.0 == -0.0 so they should also have the same hashcode
            cast::transmute(if *self == -0.0 { 0.0 } else { *self })
        };
        i.hash2(hasher)
    }
}

impl<'a, H: StreamHasher, A: Hashable<H>> Hashable<H> for &'a [A] {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        self.len().hash2(hasher);
        for elt in self.iter() {
            elt.hash2(hasher);
        }
    }
}

impl<H: StreamHasher, A: Hashable<H>> Hashable<H> for ~[A] {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        self.as_slice().hash2(hasher)
    }
}

impl<H: StreamHasher, A: Hashable<H>> Hashable<H> for @[A] {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        self.as_slice().hash2(hasher)
    }
}


impl<'a, H: StreamHasher> Hashable<H> for &'a str {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        hasher.input(self.as_bytes());
        0xFFu8.hash2(hasher);
    }
}

impl<H: StreamHasher> Hashable<H> for ~str {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        self.as_slice().hash2(hasher)
    }
}

impl<H: StreamHasher> Hashable<H> for @str {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        self.as_slice().hash2(hasher)
    }
}

impl<H: Hasher, A: Hashable<H>> Hashable<H> for (A, ) {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        match *self {
            (ref a, ) => a.hash2(hasher)
        }
    }
}

macro_rules! hash2_tuple_tuple(
    ($($A:ident),+) => (
        impl<H: Hasher, $($A: Hashable<H>),+> Hashable<H> for ($($A),+) {
            #[inline]
            fn hash2(&self, hasher: &mut H) {
                match *self {
                    ($(ref $A),+) => {
                        $(
                            $A.hash2(hasher);
                        )+
                    }
                }
            }
        }
    )
)

hash2_tuple_tuple!(A1, A2)
hash2_tuple_tuple!(A1, A2, A3)
hash2_tuple_tuple!(A1, A2, A3, A4)
hash2_tuple_tuple!(A1, A2, A3, A4, A5)
hash2_tuple_tuple!(A1, A2, A3, A4, A5, A6)
hash2_tuple_tuple!(A1, A2, A3, A4, A5, A6, A7)
hash2_tuple_tuple!(A1, A2, A3, A4, A5, A6, A7, A8)

impl<H: StreamHasher, A: Hashable<H>> Hashable<H> for Option<A> {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        match *self {
            Some(ref a) => {
                0u8.hash2(hasher);
                a.hash2(hasher);
            }
            None => {
                0u8.hash2(hasher);
            }
        }
    }
}

impl<'a, H: StreamHasher, A: Hashable<H>> Hashable<H> for &'a A {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (**self).hash2(hasher);
    }
}

impl<H: StreamHasher, A: Hashable<H>> Hashable<H> for @A {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (**self).hash2(hasher);
    }
}

impl<H: StreamHasher, A: Hashable<H>> Hashable<H> for Rc<A> {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        self.borrow().hash2(hasher);
    }
}

impl<H: StreamHasher, A: Hashable<H>> Hashable<H> for ~A {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (**self).hash2(hasher);
    }
}

// NB: raw-pointer IterBytes does _not_ dereference
// to the target; it just gives you the pointer-bytes.
impl<H: StreamHasher, A: Hashable<H>> Hashable<H> for *A {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as uint).hash2(hasher);
    }
}

impl<H: StreamHasher, A: Hashable<H>> Hashable<H> for *mut A {
    #[inline]
    fn hash2(&self, hasher: &mut H) {
        (*self as uint).hash2(hasher);
    }
}


#[cfg(test)]
mod tests {
    use extra::test::BenchHarness;
    use super::Hasher;
    use super::StreamHasher;
    use super::FixedHasher;
    use super::SipHasher;
    use super::Hashable;

    #[bench]
    fn bench_str_1(bh: &mut BenchHarness) {
        let s = "foo";
        bh.iter(|| {
            assert_eq!(s.hash(), 16262950014981195938);
        })
    }

    #[bench]
    fn bench_str_2(bh: &mut BenchHarness) {
        let s = "foo";
        bh.iter(|| {
            let mut hasher = SipHasher::new_with_keys(0, 0);
            s.hash2(&mut hasher);
            assert_eq!(hasher.result_u64(), 16262950014981195938);
        })
    }

    #[deriving(IterBytes)]
    struct Compound {
        x: u8,
        y: u16,
        z: ~str,
    }

    impl<H: StreamHasher> Hashable<H> for Compound {
        fn hash2(&self, hasher: &mut H) {
            self.x.hash2(hasher);
            self.y.hash2(hasher);
            self.z.hash2(hasher);
        }
    }

    #[bench]
    fn bench_compound_1(bh: &mut BenchHarness) {
        let compound = Compound {
            x: 1,
            y: 2,
            z: ~"foobarbaz",
        };
        bh.iter(|| {
            assert_eq!(compound.hash(), 3581836382593270478);
        })
    }

    #[bench]
    fn bench_compound_2(bh: &mut BenchHarness) {
        let compound = Compound {
            x: 1,
            y: 2,
            z: ~"foobarbaz",
        };
        bh.iter(|| {
            let mut hasher = SipHasher::new_with_keys(0, 0);
            compound.hash2(&mut hasher);
            assert_eq!(hasher.result_u64(), 3581836382593270478);
        })
    }



    struct Fixed {
        hash: u64,
    }

    impl Hashable<FixedHasher> for Fixed {
        fn hash2(&self, hasher: &mut FixedHasher) {
            hasher.input_hash(self.hash);
        }
    }

    #[bench]
    fn bench_fixed(bh: &mut BenchHarness) {
        let fixed = Fixed { hash: 5 };
        bh.iter(|| {
            let mut hasher = FixedHasher::new();
            fixed.hash2(&mut hasher);
            assert_eq!(hasher.result_u64(), 5);
        })
    }
}