rusty_leveldb/
write_batch.rs

1use crate::integer_encoding::{FixedInt, VarInt, VarIntWriter};
2use crate::key_types::ValueType;
3use crate::memtable::MemTable;
4use crate::types::SequenceNumber;
5
6use std::io::Write;
7
8const SEQNUM_OFFSET: usize = 0;
9const COUNT_OFFSET: usize = 8;
10const HEADER_SIZE: usize = 12;
11
12/// A WriteBatch contains entries to be written to a MemTable (for example) in a compact form.
13///
14/// The storage format is (with the respective length in bytes)
15///
16/// [tag: 1, keylen: ~var, key: keylen, vallen: ~var, val: vallen]
17pub struct WriteBatch {
18    entries: Vec<u8>,
19}
20
21impl WriteBatch {
22    pub(crate) fn new() -> WriteBatch {
23        let mut v = Vec::with_capacity(128);
24        v.resize(HEADER_SIZE, 0);
25
26        WriteBatch { entries: v }
27    }
28
29    /// Initializes a WriteBatch with a serialized WriteBatch.
30    pub fn set_contents(&mut self, from: &[u8]) {
31        self.entries.clear();
32        self.entries.extend_from_slice(from);
33    }
34
35    /// Adds an entry to a WriteBatch, to be added to the database.
36    #[allow(unused_assignments)]
37    pub fn put(&mut self, k: &[u8], v: &[u8]) {
38        self.entries
39            .write_all(&[ValueType::TypeValue as u8])
40            .unwrap();
41        self.entries.write_varint(k.len()).unwrap();
42        self.entries.write_all(k).unwrap();
43        self.entries.write_varint(v.len()).unwrap();
44        self.entries.write_all(v).unwrap();
45
46        let c = self.count();
47        self.set_count(c + 1);
48    }
49
50    /// Marks an entry to be deleted from the database.
51    #[allow(unused_assignments)]
52    pub fn delete(&mut self, k: &[u8]) {
53        self.entries
54            .write_all(&[ValueType::TypeDeletion as u8])
55            .unwrap();
56        self.entries.write_varint(k.len()).unwrap();
57        self.entries.write_all(k).unwrap();
58
59        let c = self.count();
60        self.set_count(c + 1);
61    }
62
63    /// Clear the contents of a WriteBatch.
64    pub fn clear(&mut self) {
65        self.entries.clear()
66    }
67
68    fn byte_size(&self) -> usize {
69        self.entries.len()
70    }
71
72    fn set_count(&mut self, c: u32) {
73        c.encode_fixed(&mut self.entries[COUNT_OFFSET..COUNT_OFFSET + 4]);
74    }
75
76    /// Returns how many operations are in a batch.
77    pub fn count(&self) -> u32 {
78        u32::decode_fixed(&self.entries[COUNT_OFFSET..COUNT_OFFSET + 4])
79    }
80
81    fn set_sequence(&mut self, s: SequenceNumber) {
82        s.encode_fixed(&mut self.entries[SEQNUM_OFFSET..SEQNUM_OFFSET + 8]);
83    }
84
85    pub fn sequence(&self) -> SequenceNumber {
86        u64::decode_fixed(&self.entries[SEQNUM_OFFSET..SEQNUM_OFFSET + 8])
87    }
88
89    pub fn iter<'a>(&'a self) -> WriteBatchIter<'a> {
90        WriteBatchIter {
91            batch: self,
92            ix: HEADER_SIZE,
93        }
94    }
95
96    pub fn insert_into_memtable(&self, mut seq: SequenceNumber, mt: &mut MemTable) {
97        for (k, v) in self.iter() {
98            match v {
99                Some(v_) => mt.add(seq, ValueType::TypeValue, k, v_),
100                None => mt.add(seq, ValueType::TypeDeletion, k, b""),
101            }
102            seq += 1;
103        }
104    }
105
106    pub fn encode(mut self, seq: SequenceNumber) -> Vec<u8> {
107        self.set_sequence(seq);
108        self.entries
109    }
110}
111
112impl Default for WriteBatch {
113    fn default() -> Self {
114        Self::new()
115    }
116}
117
118pub struct WriteBatchIter<'a> {
119    batch: &'a WriteBatch,
120    ix: usize,
121}
122
123/// The iterator also plays the role of the decoder.
124impl<'a> Iterator for WriteBatchIter<'a> {
125    type Item = (&'a [u8], Option<&'a [u8]>);
126    fn next(&mut self) -> Option<Self::Item> {
127        if self.ix >= self.batch.entries.len() {
128            return None;
129        }
130
131        let tag = self.batch.entries[self.ix];
132        self.ix += 1;
133
134        let (klen, l) = usize::decode_var(&self.batch.entries[self.ix..])?;
135        self.ix += l;
136        let k = &self.batch.entries[self.ix..self.ix + klen];
137        self.ix += klen;
138
139        if tag == ValueType::TypeValue as u8 {
140            let (vlen, m) = usize::decode_var(&self.batch.entries[self.ix..])?;
141            self.ix += m;
142            let v = &self.batch.entries[self.ix..self.ix + vlen];
143            self.ix += vlen;
144
145            Some((k, Some(v)))
146        } else {
147            Some((k, None))
148        }
149    }
150}
151
152#[cfg(test)]
153mod tests {
154    use super::*;
155    use std::iter::Iterator;
156
157    #[test]
158    fn test_write_batch() {
159        let mut b = WriteBatch::new();
160        let entries: [(&[u8], &[u8]); 5] = [
161            (b"abc", b"def"),
162            (b"123", b"456"),
163            (b"xxx", b"yyy"),
164            (b"zzz", b""),
165            (b"010", b""),
166        ];
167
168        for &(k, v) in entries.iter() {
169            if !v.is_empty() {
170                b.put(k, v);
171            } else {
172                b.delete(k)
173            }
174        }
175
176        eprintln!("{:?}", b.entries);
177        assert_eq!(b.byte_size(), 49);
178        assert_eq!(b.iter().count(), 5);
179
180        let mut i = 0;
181
182        for (k, v) in b.iter() {
183            assert_eq!(k, entries[i].0);
184
185            match v {
186                None => assert!(entries[i].1.is_empty()),
187                Some(v_) => assert_eq!(v_, entries[i].1),
188            }
189
190            i += 1;
191        }
192
193        assert_eq!(i, 5);
194        assert_eq!(b.encode(1).len(), 49);
195    }
196}
rusty_leveldb/write_batch.rs

rusty_leveldb/
write_batch.rs
