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
110
111
112
113
114
115
116
117
118
119
120

use seahash::SeaHasher;

use std::marker::PhantomData;
use std::hash::{Hash, Hasher};

use std::borrow::Cow;

use Val;
use meta::{Meta, SubMeta, Select, Selection};

use meta::checksum::CheckSum;

/// This `T` can be viewed as a Key-Value pair.
pub trait Keyed {
    type Key: Val + Ord;
    type Value: Clone;

    fn key(&self) -> &Self::Key;
    fn value(&self) -> &Self::Value;
    fn value_mut(&mut self) -> &mut Self::Value;
}

/// A key, K is usually `T::Key` where `T: Keyed`
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Key<K>(K);
#[derive(Clone, PartialEq)]
pub struct KeySum<T>(T);
#[derive(Clone, PartialEq)]
pub struct ValSum<T>(T);

impl<T> KeySum<T> {
    fn inner(&self) -> &T {
        &self.0
    }
}

impl<T> ValSum<T> {
    fn inner(&self) -> &T {
        &self.0
    }
}

impl<K> Key<K> {
    /// Construct a new Key
    pub fn new(key: K) -> Self {
        Key(key)
    }
}

impl<T> Meta<T> for Key<T::Key>
    where T: Val + Keyed
{
    fn from_t(t: &T) -> Self {
        Key(t.key().clone())
    }
    fn merge(&mut self, other: &Self, _t: PhantomData<T>) {
        if self.0 < other.0 {
            self.0 = other.0.clone()
        }
    }
}

impl<T> Select<T> for Key<T::Key>
    where T: Val + Keyed
{
    fn select(&mut self, other: Cow<Self>) -> Selection {
        if self.0 == other.0 {
            Selection::Hit
        } else if self.0 < other.0 {
            Selection::Between
        } else {
            Selection::Miss
        }
    }
}

impl<T> Meta<T> for KeySum<u64>
    where T: Val + Keyed,
          T::Key: Hash
{
    fn from_t(t: &T) -> Self {
        let mut hasher = SeaHasher::new();
        t.key().hash(&mut hasher);
        KeySum(hasher.finish())
    }
    fn merge(&mut self, other: &Self, _t: PhantomData<T>) {
        let a = self.0;
        let b = other.0;
        self.0 = (a ^ b).wrapping_add(a);
    }
}

impl<T> Meta<T> for ValSum<u64>
    where T: Val + Keyed,
          T::Value: Hash
{
    fn from_t(t: &T) -> Self {
        let mut hasher = SeaHasher::new();
        t.value().hash(&mut hasher);
        ValSum(hasher.finish())
    }

    fn merge(&mut self, other: &Self, _t: PhantomData<T>) {
        let a = self.0;
        let b = other.0;
        self.0 = (a ^ b).wrapping_add(a);
    }
}

impl<M> SubMeta<CheckSum<u64>> for M
    where M: SubMeta<KeySum<u64>> + SubMeta<ValSum<u64>>
{
    fn submeta(&self) -> Cow<CheckSum<u64>> {
        let k: Cow<KeySum<u64>> = self.submeta();
        let v: Cow<ValSum<u64>> = self.submeta();

        let check = CheckSum::new(k.inner() ^ v.inner());
        Cow::Owned(check)
    }
}