simple_kbuckets/
bucket.rs

1use std::collections::VecDeque;
2
3use key::Key;
4
5/// Stores a part of values, with keys at distance between `2^k` and
6/// `2^(k+1)` of the table's main key.
7pub struct Bucket<TKey: Key, TValue> {
8    data: VecDeque<(TKey, TValue)>,
9    max_size: usize,
10}
11
12impl<TKey: Key, TValue> Bucket<TKey, TValue> {
13    /// Creates a new bucket.
14    pub fn new(max_size: usize) -> Bucket<TKey, TValue> {
15        Bucket {
16            data: VecDeque::with_capacity(max_size),
17            max_size: max_size,
18        }
19    }
20
21    /// Adds a new item to the bucket.
22    /// If the bucket is already full, pops the oldest element before
23    /// insertion, and returns it.
24    /// If there is already an element with that key, pops it before
25    /// insertion, and returns it.
26    pub fn update(&mut self, key: TKey, value: TValue) -> Option<(TKey, TValue)> {
27        // Search if there is already an element with that key.
28        let mut index_to_remove = None;
29        for (i, k) in self.data.iter().map(|&(ref k,_)| k.clone()).enumerate() {
30            if k == key {
31                index_to_remove = Some(i);
32            }
33        }
34
35        // If there is already an element with that key, pop it and
36        // get its value.
37        let res = {
38            if let Some(i) = index_to_remove {
39                self.data.remove(i)
40            }
41            else if self.data.len() == self.max_size {
42                self.data.pop_front()
43            }
44            else {
45                None
46            }
47        };
48
49        // Insert and return
50        self.data.push_back((key, value));
51        res
52    }
53
54    /// Returns the content of this bucket.
55    pub fn data(&self) -> &VecDeque<(TKey, TValue)> {
56        &self.data
57    }
58}
simple_kbuckets/bucket.rs

simple_kbuckets/
bucket.rs
