downstream 1.23.0

downstream provides efficient, constant-space implementations of stream curation algorithms
Documentation 
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
121
122
123
124
125
126
127
128

use super::{AssignStorageSiteTrait, CircularAlgo, HasIngestCapacityTrait, SteadyAlgo};
use crate::_auxlib as aux;

/// Does this algorithm have the capacity to ingest a data item at logical time
/// T?
///
/// @template Uint Unsigned integer type for operands.
/// @param S The number of buffer sites available.
/// @param T Queried logical time.
/// @returns Whether there is capacity to ingest at time T.
#[allow(non_snake_case)]
pub fn has_ingest_capacity<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> bool {
    let _0: Uint = Uint::zero();
    let _6: Uint = Uint::from_u32(6).unwrap();
    let _7: Uint = Uint::from_u32(7).unwrap();
    let _8: Uint = Uint::from_u32(8).unwrap();
    if S < _8 || S % _8 != _0 {
        return false;
    }
    let eighth_S: Uint = S / _8;
    let seven_eighth_S: Uint = _7 * eighth_S;
    let t_div_8: Uint = T / _8;
    let t_mod_8: Uint = T % _8;
    let adj_t_mod: Uint = if t_mod_8 < _7 { t_mod_8 } else { _6 };
    let has_capacity_1st =
        CircularAlgo::has_ingest_capacity(seven_eighth_S, t_div_8 * _7 + adj_t_mod);
    let has_capacity_2nd = T < _7 || SteadyAlgo::has_ingest_capacity(eighth_S, (T - _7) / _8);

    has_capacity_1st && has_capacity_2nd
}

/// Site selection for hybrid circular/steady curation.
///
/// What buffer site should the T'th data item be stored to?
///
/// @template Uint Unsigned integer type for operands and return value.
/// @param S Buffer size.
///     Must be divisible by 8, with S/8 being a power of two.
/// @param T Current logical time.
/// @returns The selected storage site, if any.
///     Returns S if no site should be selected (i.e., discard).
#[allow(non_snake_case)]
pub fn _assign_storage_site<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> Uint {
    debug_assert!(has_ingest_capacity(S, T));

    let _7: Uint = Uint::from_u32(7).unwrap();
    let _8: Uint = Uint::from_u32(8).unwrap();
    let eighth_S: Uint = S / _8;
    let seven_eighth_S: Uint = _7 * eighth_S;
    let remainder: Uint = T % _8;
    if remainder < _7 {
        let adj_T: Uint = (T / _8) * _7 + remainder;
        let site: Uint = CircularAlgo::_assign_storage_site(seven_eighth_S, adj_T);
        if site == seven_eighth_S {
            S
        } else {
            site
        }
    } else {
        let adj_T: Uint = T / _8;
        let site: Uint = SteadyAlgo::_assign_storage_site(eighth_S, adj_T);
        if site == eighth_S {
            S
        } else {
            seven_eighth_S + site
        }
    }
}

/// Site selection for hybrid circular/steady curation.
///
/// What buffer site should the T'th data item be stored to?
///
/// @template Uint Unsigned integer type for operands and return value.
/// @param S Buffer size.
///     Must be divisible by 8, with S/8 being a power of two.
/// @param T Current logical time.
/// @returns The selected storage site, if any.
///     Returns None if no site should be selected (i.e., discard).
#[allow(non_snake_case)]
pub fn assign_storage_site<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> Option<Uint> {
    let k: Uint = _assign_storage_site(S, T);
    if k == S {
        None
    } else {
        Some(k)
    }
}

pub struct Algo;

#[allow(non_snake_case)]
impl crate::dstream::HasIngestCapacityTrait for Algo {
    fn has_ingest_capacity<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> bool {
        has_ingest_capacity::<Uint>(S, T)
    }
}

#[allow(non_snake_case)]
impl crate::dstream::AssignStorageSiteTrait for Algo {
    fn _assign_storage_site<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> Uint {
        _assign_storage_site::<Uint>(S, T)
    }

    fn assign_storage_site<Uint: aux::UnsignedTrait>(S: Uint, T: Uint) -> Option<Uint> {
        assign_storage_site::<Uint>(S, T)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_smoke_has_ingest_capacity() {
        has_ingest_capacity::<u32>(16, 5);
    }

    #[test]
    fn test_smoke_assign_storage_site() {
        assign_storage_site::<u32>(16, 5);
    }

    #[test]
    fn test_smoke_impl_assign_storage_site() {
        _assign_storage_site::<u32>(16, 5);
    }
}