primitivemap/
bucket.rs

1use kv::{Key, Value};
2use smallvec::SmallVec;
3
4pub const BUCKET_SIZE: usize = 2;
5pub const BUCKET_LIST_SIZE: usize = 2048;
6
7pub trait Bucket<K: Key, V: Value>: Sized {
8    fn new() -> Self;
9    fn push(&mut self, key: K, value: V);
10    fn get(&self, key: K) -> Option<V>;
11}
12
13#[derive(Clone)]
14pub struct SmallVecBucket<K: Key, V> {
15    members: SmallVec<[(K, V); BUCKET_SIZE]>,
16}
17
18impl<K: Key, V: Value> Bucket<K, V> for SmallVecBucket<K, V> {
19    fn new() -> Self {
20        SmallVecBucket {
21            members: SmallVec::new(),
22        }
23    }
24
25    #[inline]
26    fn push(&mut self, key: K, value: V) {
27        self.members.push((key, value))
28    }
29
30    #[inline]
31    fn get(&self, key: K) -> Option<V> {
32        self.members
33            .iter()
34            .find(|&&(k, _)| k == key)
35            .map(|&(_, v)| v)
36    }
37}
38
39#[derive(Copy, Clone)]
40pub struct ArrayBucket<K: Key, V> {
41    members: [(K, V); BUCKET_SIZE],
42    len: usize,
43}
44
45impl<K: Key, V: Value> Bucket<K, V> for ArrayBucket<K, V> {
46    fn new() -> Self {
47        ArrayBucket {
48            members: [(K::default(), V::default()); BUCKET_SIZE],
49            len: 0,
50        }
51    }
52
53    #[inline]
54    fn push(&mut self, key: K, value: V) {
55        let idx = self.len;
56        self.members[idx] = (key, value);
57        self.len += 1;
58    }
59
60    #[inline]
61    fn get(&self, key: K) -> Option<V> {
62        let len = self.len;
63        self.members[..len]
64            .iter()
65            .find(|&&(k, _)| k == key)
66            .map(|&(_, v)| v)
67    }
68}
69
70pub type SmallVecBucketList<K, V> = SmallVec<[SmallVecBucket<K, V>; BUCKET_LIST_SIZE]>;
71pub type ArrayBucketList<K, V> = [ArrayBucket<K, V>; BUCKET_LIST_SIZE];
72
73pub trait BucketList<K: Key, V: Value> {
74    type Bucket: Bucket<K, V>;
75
76    fn empty() -> Self;
77    fn len(&self) -> usize;
78    fn get(&self, idx: usize) -> &Self::Bucket;
79    fn get_mut(&mut self, idx: usize) -> &mut Self::Bucket;
80}
81
82impl<K: Key, V: Value> BucketList<K, V> for SmallVecBucketList<K, V> {
83    type Bucket = SmallVecBucket<K, V>;
84
85    fn empty() -> Self {
86        let mut vec = SmallVec::new();
87        // pre-polulate vec
88        for _ in 0..BUCKET_LIST_SIZE {
89            vec.push(SmallVecBucket::new())
90        }
91        vec
92    }
93
94    #[inline]
95    fn len(&self) -> usize {
96        self.as_ref().len()
97    }
98
99    #[inline]
100    fn get(&self, idx: usize) -> &Self::Bucket {
101        &self[idx]
102    }
103
104    #[inline]
105    fn get_mut(&mut self, idx: usize) -> &mut Self::Bucket {
106        &mut self[idx]
107    }
108}
109
110impl<K: Key, V: Value> BucketList<K, V> for ArrayBucketList<K, V> {
111    type Bucket = ArrayBucket<K, V>;
112
113    fn empty() -> Self {
114        [ArrayBucket::new(); BUCKET_LIST_SIZE]
115    }
116
117    #[inline]
118    fn len(&self) -> usize {
119        self.as_ref().len()
120    }
121
122    #[inline]
123    fn get(&self, idx: usize) -> &Self::Bucket {
124        &self[idx]
125    }
126
127    #[inline]
128    fn get_mut(&mut self, idx: usize) -> &mut Self::Bucket {
129        &mut self[idx]
130    }
131}
primitivemap/bucket.rs

primitivemap/
bucket.rs
