hash.rs

#[feature(macro_rules)];
#[feature(default_type_params)];
#[allow(default_type_param_usage)];

use std::cast;
use std::rc::Rc;
use std::unstable::intrinsics;

trait Hash<S = SumState> {
    fn hash(&self, state: &mut S) -> u64;
}

trait Stream {
    fn result(&self) -> u64;

    fn hash_bytes(&mut self, v: &[u8]);

    #[inline]
    fn hash_nil(&mut self) { }

    #[inline]
    fn hash_u8(&mut self, v: u8) {
        unsafe {
            let bytes: [u8, .. 1] = cast::transmute(v);
            self.hash_bytes(bytes)
        }
    }

    #[inline]
    fn hash_u16(&mut self, v: u16) {
        unsafe {
            let value = intrinsics::to_le16(v as i16);
            let bytes: [u8, .. 2] = cast::transmute(value);
            self.hash_bytes(bytes)
        }
    }

    #[inline]
    fn hash_u32(&mut self, v: u32) {
        unsafe {
            let value = intrinsics::to_le32(v as i32);
            let bytes: [u8, .. 4] = cast::transmute(value);
            self.hash_bytes(bytes)
        }
    }

    #[inline]
    fn hash_u64(&mut self, v: u64) {
        unsafe {
            let value = intrinsics::to_le64(v as i64);
            let bytes: [u8, .. 8] = cast::transmute(value);
            self.hash_bytes(bytes)
        }
    }

    #[inline]
    #[cfg(target_word_size = "32")]
    fn hash_uint(&mut self, v: uint) {
        self.hash_u32(v as u32)
    }

    #[inline]
    #[cfg(target_word_size = "64")]
    fn hash_uint(&mut self, v: uint) {
        self.hash_u64(v as u64)
    }

    #[inline]
    fn hash_i8(&mut self, v: i8) {
        self.hash_u8(v as u8)
    }

    #[inline]
    fn hash_i16(&mut self, v: i16) {
        self.hash_u16(v as u16)
    }

    #[inline]
    fn hash_i32(&mut self, v: i32) {
        self.hash_u32(v as u32)
    }

    #[inline]
    fn hash_i64(&mut self, v: i64) {
        self.hash_u64(v as u64)
    }

    #[inline]
    fn hash_int(&mut self, v: int) {
        self.hash_uint(v as uint)
    }

    #[inline]
    fn hash_f32(&mut self, v: f32) {
        unsafe {
            // 0.0 == -0.0 so they should also have the same hashcode
            let v: u32 = cast::transmute(if v == -0.0 { 0.0 } else { v });
            self.hash_u32(v)
        }
    }

    #[inline]
    fn hash_f64(&mut self, v: f64) {
        unsafe {
            // 0.0 == -0.0 so they should also have the same hashcode
            let v: u64 = cast::transmute(if v == -0.0 { 0.0 } else { v });
            self.hash_u64(v)
        }
    }

    #[inline]
    fn hash_bool(&mut self, v: bool) {
        self.hash_u8(v as u8)
    }

    #[inline]
    fn hash_char(&mut self, v: char) {
        self.hash_u32(v as u32)
    }

    #[inline]
    fn hash_str(&mut self, v: &str) {
        self.hash_bytes(v.as_bytes());
        self.hash_u8(0xff);
    }

    #[inline]
    fn hash_slice<T: StreamHash<Self>>(&mut self, v: &[T]) {
        self.hash_uint(v.len());
        for elt in v.iter() {
            elt.input(self)
        }
    }

    #[inline]
    fn hash_ref<T: StreamHash<Self>>(&mut self, v: &T) {
        (*v).input(self)
    }

    // NB: raw-pointer `Hash` does _not_ dereference
    // to the target; it just gives you the pointer-bytes.
    #[inline]
    fn hash_ptr<T: StreamHash<Self>>(&mut self, v: *T) {
        self.hash_uint(v as uint)
    }

    #[inline]
    fn hash_mut_ptr<T: StreamHash<Self>>(&mut self, v: *mut T) {
        self.hash_uint(v as uint)
    }
}

trait StreamHash<S: Stream>: Hash<S> {
    fn input(&self, state: &mut S);
}

trait Hasher<S> {
    fn state(&self) -> S;

    #[inline]
    fn hash<T: Hash<S>>(&self, value: &T) -> u64 {
        let mut state = self.state();
        value.hash(&mut state)
    }
}

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

macro_rules! impl_hash(
    ($ty:ty => $e:expr) => (
        impl<'a, S: Stream> Hash<S> for $ty {
            #[inline]
            fn hash(&self, state: &mut S) -> u64 {
                self.input(state);
                state.result()
            }
        }

        impl<'a, S: Stream> StreamHash<S> for $ty {
            #[inline]
            fn input(&self, state: &mut S) {
                $e
            }
        }
    )
)

impl_hash!(u8 => state.hash_u8(*self))
impl_hash!(u16 => state.hash_u16(*self))
impl_hash!(u32 => state.hash_u32(*self))
impl_hash!(u64 => state.hash_u64(*self))
impl_hash!(uint => state.hash_uint(*self))

impl_hash!(i8 => state.hash_i8(*self))
impl_hash!(i16 => state.hash_i16(*self))
impl_hash!(i32 => state.hash_i32(*self))
impl_hash!(i64 => state.hash_i64(*self))
impl_hash!(int => state.hash_int(*self))

impl_hash!(&'a str => state.hash_str(*self))
impl_hash!(~str => state.hash_str(*self))

macro_rules! impl_hash_tuple(
    () => (
        impl<S: Stream> Hash<S> for () {
            #[inline]
            fn hash(&self, state: &mut S) -> u64 {
                self.input(state);
                state.result()
            }
        }

        impl<S: Stream> StreamHash<S> for () {
            #[inline]
            fn input(&self, state: &mut S) {
                state.hash_nil();
            }
        }
    );

    ($A:ident $($B:ident)*) => (
        impl<
            S: Stream,
            $A: StreamHash<S> $(, $B: StreamHash<S>)*
        > Hash<S> for ($A, $($B),*) {
            #[inline]
            fn hash(&self, state: &mut S) -> u64 {
                self.input(state);
                state.result()
            }
        }

        impl<
            S: Stream,
            $A: StreamHash<S> $(, $B: StreamHash<S>)*
        > StreamHash<S> for ($A, $($B),*) {
            #[inline]
            fn input(&self, state: &mut S) {
                match *self {
                    (ref $A, $(ref $B),*) => {
                        $A.hash(state);
                        $(
                            $B.hash(state);
                        )*
                    }
                }
            }
        }
    );
)

impl_hash_tuple!()
impl_hash_tuple!(A0)
impl_hash_tuple!(A0 A1)
impl_hash_tuple!(A0 A1 A2)
impl_hash_tuple!(A0 A1 A2 A3)
impl_hash_tuple!(A0 A1 A2 A3 A4)
impl_hash_tuple!(A0 A1 A2 A3 A4 A5)
impl_hash_tuple!(A0 A1 A2 A3 A4 A5 A6)
impl_hash_tuple!(A0 A1 A2 A3 A4 A5 A6 A7)

macro_rules! impl_hash_compound(
    ($ty:ty => $e:expr) => (
        impl<'a, S: Stream, T: StreamHash<S>> Hash<S> for $ty {
            #[inline]
            fn hash(&self, state: &mut S) -> u64 {
                self.input(state);
                state.result()
            }
        }

        impl<'a, S: Stream, T: StreamHash<S>> StreamHash<S> for $ty {
            #[inline]
            fn input(&self, state: &mut S) {
                $e
            }
        }
    )
)

impl_hash_compound!(&'a [T] => state.hash_slice(*self))
impl_hash_compound!(~[T] => state.hash_slice(*self))
impl_hash_compound!(&'a T => state.hash_ref(*self))
impl_hash_compound!(~T => state.hash_ref(&*self))
impl_hash_compound!(Rc<T> => state.hash_ref(self.borrow()))

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

struct SumState {
    sum: u64,
}

impl Stream for SumState {
    #[inline]
    fn result(&self) -> u64 {
        self.sum
    }

    #[inline]
    fn hash_bytes(&mut self, bytes: &[u8]) {
        for byte in bytes.iter() {
            self.sum += *byte as u64;
        }
    }
}

struct SumHasher;

impl Hasher<SumState> for SumHasher {
    #[inline]
    fn state(&self) -> SumState {
        SumState { sum: 0 }
    }
}

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

struct CustomHasher;

impl Hasher<()> for CustomHasher {
    #[inline]
    fn state(&self) -> () {
        ()
    }
}

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

struct HashMap<K, V, H = SumHasher> {
    hasher: H,
    buckets: ~[Bucket<K, V>],
}

struct Bucket<K, V> {
    hash: u64,
    key: K,
    value: V,
}

impl<K: Eq + Hash, V> HashMap<K, V> {
    pub fn new() -> HashMap<K, V> {
        HashMap::new_with_hasher(SumHasher)
    }

}

impl<
    K: Eq + Hash<S>,
    V,
    S,
    H: Hasher<S>
> HashMap<K, V, H> {
    pub fn new_with_hasher(hasher: H) -> HashMap<K, V, H> {
        HashMap {
            hasher: hasher,
            buckets: ~[],
        }
    }

    pub fn insert(&mut self, key: K, value: V) {
        let hash = self.hasher.hash(&key);

        match self.find_bucket(hash, &key) {
            Some(idx) => {
                self.buckets[idx] = Bucket {
                    hash: hash,
                    key: key,
                    value: value,
                };
            }
            None => {
                self.buckets.push(Bucket {
                    hash: hash,
                    key: key,
                    value: value,
                });
            }
        }
    }

    pub fn find<'a>(&'a self, key: &K) -> Option<&'a V> {
        let hash = self.hasher.hash(key);

        self.find_bucket(hash, key).and_then(|idx| {
            Some(&self.buckets[idx].value)
        })
    }

    pub fn find_equiv<'a, T: Equiv<K> + Hash<S>>(&'a self, key: &T) -> Option<&'a V> {
        let hash = self.hasher.hash(key);

        self.find_equiv_bucket(hash, key).and_then(|idx| {
            Some(&self.buckets[idx].value)
        })
    }

    fn find_bucket(&self, hash: u64, key: &K) -> Option<uint> {
        for (i, bucket) in self.buckets.iter().enumerate() {
            if hash == bucket.hash && *key == bucket.key {
                return Some(i);
            }
        }

        None
    }

    fn find_equiv_bucket<Q: Equiv<K>>(&self, hash: u64, key: &Q) -> Option<uint> {
        for (i, bucket) in self.buckets.iter().enumerate() {
            if hash == bucket.hash && key.equiv(&bucket.key) {
                return Some(i);
            }
        }

        None
    }
}

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

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

impl<S: Stream> Hash<S> for Compound {
    #[inline]
    fn hash(&self, hasher: &mut S) -> u64 {
        self.input(hasher);
        hasher.result()
    }
}

impl<S: Stream> StreamHash<S> for Compound {
    #[inline]
    fn input(&self, hasher: &mut S) {
        self.x.input(hasher);
        self.y.input(hasher);
    }
}

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

#[deriving(Eq)]
struct Custom {
    hash: u64,
}

impl Hash<()> for Custom {
    #[inline]
    fn hash(&self, _hasher: &mut ()) -> u64 {
        self.hash
    }
}

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

fn find<'a, K: Eq + Hash, V>(map: &'a HashMap<K, V>, key: &K) -> Option<&'a V> {
    map.find(key)
}

fn find_generic<
    'a,
    K: Eq + Hash<S>,
    V,
    S,
    H: Hasher<S>
>(map: &'a HashMap<K, V, H>, key: &K) -> Option<&'a V> {
    map.find(key)
}

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

fn main() {
    let mut map1 = HashMap::new();
    map1.insert(~"abc", 1);

    println!("map1: {:?}", map1.find(&~"abc"));
    println!("map1: {:?}", map1.find(&~"xyz"));
    println!("map1: {:?}", map1.find_equiv(& &"abc"));
    println!("map1: {:?}", map1.find_equiv(& &"xyz"));
    println!("map1: {:?}", find(&map1, &~"abc"));
    println!("map1: {:?}", find(&map1, &~"xyz"));

    let mut map2 = HashMap::new();
    map2.insert(Compound { x: ~"abc", y: 5 }, 2);

    println!("map2: {:?}", map2.find(&Compound { x: ~"abc", y: 5 }));
    println!("map2: {:?}", map2.find(&Compound { x: ~"xyz", y: 5 }));
    println!("map2: {:?}", map2.find(&Compound { x: ~"abc", y: 6 }));

    let mut map3 = HashMap::new_with_hasher(CustomHasher);
    map3.insert(Custom { hash: 5 }, 3);

    println!("map3: {:?}", map3.find(&Custom { hash: 5 }));
    println!("map3: {:?}", map3.find(&Custom { hash: 6 }));
    println!("map1: {:?}", find_generic(&map3, &Custom { hash: 5 }));
    println!("map1: {:?}", find_generic(&map3, &Custom { hash: 6 }));
}