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

// Copyright 2019 Conflux Foundation. All rights reserved.
// Conflux is free software and distributed under GNU General Public License.
// See http://www.gnu.org/licenses/

use std::{
    cmp::Ordering,
    collections::{binary_heap::PeekMut, BinaryHeap, HashMap},
    hash::Hash,
    time::{Duration, Instant},
};

pub struct TimeWindowBucket<KEY: Eq + Hash + Clone> {
    interval: Duration,
    limit: usize,
    timeouts: BinaryHeap<Item<KEY>>,
    counters: HashMap<KEY, usize>,
}

impl<KEY: Eq + Hash + Clone> TimeWindowBucket<KEY> {
    pub fn new(interval: Duration, limit: usize) -> Self {
        TimeWindowBucket {
            interval,
            limit,
            timeouts: BinaryHeap::new(),
            counters: HashMap::new(),
        }
    }

    fn refresh(&mut self) {
        while let Some(item) = self.timeouts.peek_mut() {
            if item.time.elapsed() <= self.interval {
                break;
            }

            let item = PeekMut::pop(item);
            let counter = self
                .counters
                .get_mut(&item.data)
                .expect("data inconsistent");
            if *counter <= 1 {
                self.counters.remove(&item.data);
            } else {
                *counter -= 1;
            }
        }
    }

    pub fn try_acquire(&mut self, key: KEY) -> bool {
        self.refresh();

        let counter = self.counters.entry(key.clone()).or_default();
        if *counter >= self.limit {
            return false;
        }

        *counter += 1;
        self.timeouts.push(Item::new(key));

        true
    }
}

struct Item<T> {
    time: Instant,
    data: T,
}

impl<T> Item<T> {
    fn new(data: T) -> Self {
        Item {
            time: Instant::now(),
            data,
        }
    }
}

impl<T> PartialEq for Item<T> {
    fn eq(&self, other: &Self) -> bool { self.time.eq(&other.time) }
}

impl<T> Eq for Item<T> {}

impl<T> PartialOrd for Item<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<T> Ord for Item<T> {
    fn cmp(&self, other: &Self) -> Ordering { other.time.cmp(&self.time) }
}

#[cfg(test)]
mod tests {
    use crate::time_window_bucket::TimeWindowBucket;
    use std::{thread::sleep, time::Duration};

    #[test]
    fn test_acquire() {
        let interval = Duration::from_millis(10);
        let mut bucket = TimeWindowBucket::new(interval, 2);

        assert_eq!(bucket.try_acquire(3), true);
        assert_eq!(bucket.try_acquire(3), true);
        assert_eq!(bucket.try_acquire(3), false);
        assert_eq!(bucket.try_acquire(4), true);

        sleep(interval + Duration::from_millis(1));

        assert_eq!(bucket.try_acquire(3), true);
        assert_eq!(bucket.try_acquire(3), true);
        assert_eq!(bucket.try_acquire(3), false);
    }
}