1
use crate::{
2
    error::{PRes, PersyError},
3
    id::{PersyId, RecRef},
4
    index::{
5
        config::{ByteVec, IndexType, IndexTypeId},
6
        keeper::Container,
7
        tree::nodes::{Leaf, LeafEntry, Node, NodeRef, Nodes, Value},
8
    },
9
    io::{
10
        InfallibleRead, InfallibleReadFormat, InfallibleReadVarInt, InfallibleWrite, InfallibleWriteFormat,
11
        InfallibleWriteVarInt,
12
    },
13
};
14
use std::io::Cursor;
15

16
macro_rules! impl_index_type {
17
    ($t:ty, $v:expr,$v1:ident,$w:ty) => {
18
        impl IndexType for $t {
19
            type Wrapper = Container<Self>;
20 0
            fn get_id() -> u8 {
21
                $v
22 1
            }
23
            fn get_type_id() -> IndexTypeId {
24
                IndexTypeId::$v1
25
            }
26
        }
27
    };
28
}
29

30
impl_index_type!(u8, 1, U8, u8);
31
impl_index_type!(u16, 2, U16, u16);
32
impl_index_type!(u32, 3, U32, u32);
33
impl_index_type!(u64, 4, U64, u64);
34
impl_index_type!(u128, 14, U128, u128);
35
impl_index_type!(i8, 5, I8, i8);
36
impl_index_type!(i16, 6, I16, i16);
37
impl_index_type!(i32, 7, I32, i32);
38
impl_index_type!(i64, 8, I64, i64);
39
impl_index_type!(i128, 15, I128, i128);
40
impl_index_type!(f32, 9, F32W, F32W);
41
impl_index_type!(f64, 10, F64W, F64W);
42
impl_index_type!(String, 12, STRING, String);
43
impl_index_type!(PersyId, 13, PERSYID, PersyId);
44
impl_index_type!(ByteVec, 16, BYTEVEC, ByteVec);
45

46
pub trait IndexSerialization: Sized {
47
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()>;
48
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self>;
49
}
50

51 1
pub fn deserialize<K: IndexType, V: IndexType>(value: &[u8]) -> PRes<Node<K, V>> {
52 1
    let version = value[0];
53
    match version {
54 1
        0u8 => deserialize_v0(&value[1..]),
55 0
        _ => panic!("not compatible disc version"),
56
    }
57 1
}
58

59 1
pub fn deserialize_v0<K: IndexType, V: IndexType>(value: &[u8]) -> PRes<Node<K, V>> {
60 1
    let mut reader = Cursor::new(value);
61 1
    let t = reader.read_varint_u8();
62 1
    match t {
63 1
        1 => {
64 1
            let prev = if reader.read_varint_u8() == 1 {
65 1
                Some(K::deserialize(&mut reader)?)
66 0
            } else {
67 1
                None
68
            };
69 1
            let size = reader.read_varint_u32();
70 1
            let mut entries = Vec::with_capacity(size as usize);
71 1
            for _ in 0..size {
72 1
                let key = K::deserialize(&mut reader)?;
73 1
                let value_type = reader.read_varint_u8();
74 1
                if value_type == 1 {
75 1
                    let val_size = reader.read_varint_u32();
76 1
                    let mut value = Vec::with_capacity(val_size as usize);
77 1
                    for _ in 0..val_size {
78 1
                        value.push(V::deserialize(&mut reader)?);
79
                    }
80 1
                    entries.push(LeafEntry {
81 1
                        key,
82 1
                        value: Value::CLUSTER(value),
83
                    });
84 1
                } else {
85 1
                    let value = V::deserialize(&mut reader)?;
86 1
                    entries.push(LeafEntry {
87 1
                        key,
88 1
                        value: Value::SINGLE(value),
89
                    });
90 0
                }
91 1
            }
92 1
            let next = if reader.read_varint_u8() == 1 {
93 1
                Some(K::deserialize(&mut reader)?)
94 0
            } else {
95 1
                None
96
            };
97 1
            Ok(Node::LEAF(Leaf { entries, prev, next }))
98 0
        }
99
        2 => {
100 1
            let prev = if reader.read_varint_u8() == 1 {
101 0
                Some(K::deserialize(&mut reader)?)
102 0
            } else {
103 1
                None
104
            };
105 1
            let size = reader.read_varint_u32();
106 1
            let mut keys = Vec::with_capacity(size as usize);
107 1
            for _ in 0..size {
108 1
                let key = K::deserialize(&mut reader)?;
109 1
                keys.push(key);
110 0
            }
111 1
            let size = reader.read_varint_u32();
112 1
            let mut pointers = Vec::with_capacity(size as usize);
113 1
            for _ in 0..size {
114 1
                let page = reader.read_varint_u64();
115 1
                let pos = reader.read_varint_u32();
116 1
                pointers.push(RecRef::new(page, pos));
117
            }
118 1
            let next = if reader.read_varint_u8() == 1 {
119 0
                Some(K::deserialize(&mut reader)?)
120 0
            } else {
121 1
                None
122
            };
123 1
            Ok(Node::NODE(Nodes {
124 1
                keys,
125 1
                pointers,
126 1
                prev,
127 1
                next,
128
            }))
129 0
        }
130 0
        _ => panic!("error on index node deserialization"),
131
    }
132 1
}
133

134 1
pub fn serialize<K: IndexType, V: IndexType>(node: &Node<K, V>) -> PRes<Vec<u8>> {
135 1
    let mut dest = Vec::new();
136 1
    dest.push(0u8);
137 1
    serialize_v0(node, &mut dest)?;
138 1
    Ok(dest)
139 1
}
140 1
pub fn serialize_v0<K: IndexType, V: IndexType>(node: &Node<K, V>, dest: &mut dyn InfallibleWrite) -> PRes<()> {
141 1
    let write_page_and_pos = |dest: &mut dyn InfallibleWrite, page, pos| -> PRes<()> {
142 1
        dest.write_varint_u64(page);
143 1
        dest.write_varint_u32(pos);
144 1
        Ok(())
145 1
    };
146

147 1
    let write_opt_leafptr = |dest: &mut dyn InfallibleWrite, x: Option<&NodeRef>| -> PRes<()> {
148 1
        if let Some(y) = x {
149 1
            write_page_and_pos(dest, y.page, y.pos)?;
150
        } else {
151 0
            write_page_and_pos(dest, 0, 0)?;
152
        }
153 1
        Ok(())
154 1
    };
155

156 1
    match node {
157 1
        Node::LEAF(leaf) => {
158 1
            dest.write_varint_u8(1);
159 1
            if let Some(pk) = &leaf.prev {
160 1
                dest.write_varint_u8(1);
161 1
                pk.serialize(dest)?;
162
            } else {
163 1
                dest.write_varint_u8(0);
164
            }
165 1
            dest.write_varint_u32(leaf.entries.len() as u32);
166 1
            for entry in &leaf.entries {
167 1
                entry.key.serialize(dest)?;
168 1
                match &entry.value {
169 1
                    Value::CLUSTER(cluster) => {
170 1
                        dest.write_varint_u8(1);
171 1
                        dest.write_varint_u32(cluster.len() as u32);
172 1
                        for val in cluster {
173 1
                            val.serialize(dest)?;
174
                        }
175
                    }
176 1
                    Value::SINGLE(val) => {
177 1
                        dest.write_varint_u8(2);
178 1
                        val.serialize(dest)?;
179
                    }
180
                }
181
            }
182 1
            if let Some(pk) = &leaf.next {
183 1
                dest.write_varint_u8(1);
184 1
                pk.serialize(dest)?;
185
            } else {
186 1
                dest.write_varint_u8(0);
187
            }
188
        }
189 1
        Node::NODE(node) => {
190 1
            dest.write_varint_u8(2);
191 1
            if let Some(pk) = &node.prev {
192 0
                dest.write_varint_u8(1);
193 0
                pk.serialize(dest)?;
194
            } else {
195 1
                dest.write_varint_u8(0);
196
            }
197 1
            dest.write_varint_u32(node.keys.len() as u32);
198 1
            for k in &node.keys {
199 1
                k.serialize(dest)?;
200
            }
201 1
            dest.write_varint_u32(node.pointers.len() as u32);
202 1
            for p in &node.pointers {
203 1
                write_opt_leafptr(dest, Some(p))?;
204
            }
205 1
            if let Some(pk) = &node.next {
206 0
                dest.write_varint_u8(1);
207 0
                pk.serialize(dest)?;
208
            } else {
209 1
                dest.write_varint_u8(0);
210
            }
211
        }
212
    }
213 1
    Ok(())
214 1
}
215

216
impl IndexSerialization for u8 {
217 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
218 1
        buffer.write_varint_u8(*self);
219 1
        Ok(())
220 1
    }
221 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
222 1
        Ok(value.read_varint_u8())
223 1
    }
224
}
225

226
impl IndexSerialization for u16 {
227 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
228 1
        buffer.write_varint_u16(*self);
229 1
        Ok(())
230 1
    }
231 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
232 1
        Ok(value.read_varint_u16())
233 1
    }
234
}
235

236
impl IndexSerialization for u32 {
237 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
238 1
        buffer.write_varint_u32(*self);
239 1
        Ok(())
240 1
    }
241 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
242 1
        Ok(value.read_varint_u32())
243 1
    }
244
}
245

246
impl IndexSerialization for u64 {
247 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
248 1
        buffer.write_varint_u64(*self);
249 1
        Ok(())
250 1
    }
251 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
252 1
        Ok(value.read_varint_u64())
253 1
    }
254
}
255

256
impl IndexSerialization for u128 {
257 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
258 1
        buffer.write_varint_u128(*self);
259 1
        Ok(())
260 1
    }
261 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
262 1
        Ok(value.read_varint_u128())
263 1
    }
264
}
265

266
impl IndexSerialization for i8 {
267 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
268 1
        buffer.write_varint_i8(*self);
269 1
        Ok(())
270 1
    }
271 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
272 1
        Ok(value.read_varint_i8())
273 1
    }
274
}
275

276
impl IndexSerialization for i16 {
277 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
278 1
        buffer.write_varint_i16(*self);
279 1
        Ok(())
280 1
    }
281 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
282 1
        Ok(value.read_varint_i16())
283 1
    }
284
}
285

286
impl IndexSerialization for i32 {
287 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
288 1
        buffer.write_varint_i32(*self);
289 1
        Ok(())
290 1
    }
291 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
292 1
        Ok(value.read_varint_i32())
293 1
    }
294
}
295

296
impl IndexSerialization for i64 {
297 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
298 1
        buffer.write_varint_i64(*self);
299 1
        Ok(())
300 1
    }
301 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
302 1
        Ok(value.read_varint_i64())
303 1
    }
304
}
305

306
impl IndexSerialization for i128 {
307 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
308 1
        buffer.write_varint_i128(*self);
309 1
        Ok(())
310 1
    }
311 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
312 1
        Ok(value.read_varint_i128())
313 1
    }
314
}
315

316
impl IndexSerialization for f32 {
317 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
318 1
        buffer.write_f32(*self);
319 1
        Ok(())
320 1
    }
321 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
322 1
        Ok(value.read_f32())
323 1
    }
324
}
325

326
impl IndexSerialization for f64 {
327 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
328 1
        buffer.write_f64(*self);
329 1
        Ok(())
330 1
    }
331 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
332 1
        Ok(value.read_f64())
333 1
    }
334
}
335

336
impl IndexSerialization for PersyId {
337 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
338 1
        buffer.write_varint_u64(self.0.page);
339 1
        buffer.write_varint_u32(self.0.pos);
340 1
        Ok(())
341 1
    }
342 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
343 1
        let page = value.read_varint_u64();
344 1
        let pos = value.read_varint_u32();
345 1
        Ok(PersyId(RecRef::new(page, pos)))
346 1
    }
347
}
348

349
impl IndexSerialization for String {
350 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
351 1
        buffer.write_varint_u32(self.len() as u32);
352 1
        buffer.write_all(self.as_bytes());
353 1
        Ok(())
354 1
    }
355 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
356 1
        let string_size = value.read_varint_u32();
357 1
        let mut buff = vec![0; string_size as usize];
358 1
        value.read_exact(&mut buff);
359 1
        let string = String::from_utf8(buff).map_err(|e| PersyError::DecodingUtf8(e.utf8_error()))?;
360 1
        Ok(string)
361 1
    }
362
}
363

364
impl IndexSerialization for ByteVec {
365 1
    fn serialize(&self, buffer: &mut dyn InfallibleWrite) -> PRes<()> {
366 1
        buffer.write_varint_u32(self.0.len() as u32);
367 1
        buffer.write_all(self.0.as_slice());
368 1
        Ok(())
369 1
    }
370 1
    fn deserialize(value: &mut dyn InfallibleRead) -> PRes<Self> {
371 1
        let vec_size = value.read_varint_u32();
372 1
        let mut slice: Vec<u8> = vec![0; vec_size as usize];
373 1
        value.read_exact(&mut slice);
374 1
        Ok(ByteVec(slice))
375 1
    }
376
}
377

378
#[cfg(test)]
379
mod tests {
380
    use super::{deserialize, serialize};
381
    use crate::id::{PersyId, RecRef};
382
    use crate::index::{
383
        config::{ByteVec, IndexType, ValueMode},
384
        tree::nodes::{compare, Leaf, Node, NodeRef, Nodes, Value},
385
    };
386
    use rand::random;
387
    use std::{cmp::Ordering, fmt::Debug};
388

389 1
    fn random_pointer() -> NodeRef {
390 1
        RecRef::new(random::<u64>(), random::<u32>())
391 1
    }
392

393
    #[test]
394 1
    fn test_serialization_deserialization_nodes() {
395 1
        let val1 = random_pointer();
396 1
        let val2 = random_pointer();
397 1
        let val3 = random_pointer();
398 1
        let mut node = Nodes::new_from_split(val1, &[(0, val2)]);
399 1
        let pos = node.find(&2).pos;
400 1
        node.add(pos, &2, val3.clone());
401 1
        let value = serialize::<u8, u8>(&Node::NODE(node)).expect("serialization works");
402 1
        let read = deserialize::<u8, u8>(&value).expect("deserialzie successfully");
403
        match read {
404 1
            Node::NODE(n) => {
405 1
                assert_eq!(n.keys.len(), 2);
406 1
                assert_eq!(n.pointers.len(), 3);
407 1
            }
408 0
            _ => panic!("expected a node"),
409
        }
410 1
    }
411

412 1
    fn single_type_leaf_test<K: IndexType + Debug, V: IndexType + Debug>(key: K, value: V, value1: V) {
413 1
        let mut leaf = Leaf::new();
414 1
        leaf.insert_or_update(&key, &value, ValueMode::REPLACE, "deserialization error")
415
            .expect("insert work");
416 1
        let binary = serialize::<K, V>(&Node::LEAF(leaf)).expect("serialization works");
417 1
        let read = deserialize::<K, V>(&binary).expect("deserialize successfully");
418
        match read {
419 1
            Node::LEAF(n) => {
420 1
                assert_eq!(n.entries.len(), 1);
421 1
                match n.entries[0].value {
422 1
                    Value::SINGLE(ref iv) => assert_eq!(compare(iv, &value), Ordering::Equal),
423 0
                    _ => panic!("expected SINGLE"),
424
                }
425 1
            }
426 0
            _ => panic!("expected a leaf"),
427
        }
428 1
        let mut leaf_many = Leaf::new();
429 1
        leaf_many
430 1
            .insert_or_update(&key, &value, ValueMode::CLUSTER, "deserialization error")
431
            .expect("insert work");
432 1
        leaf_many
433 1
            .insert_or_update(&key, &value1, ValueMode::CLUSTER, "deserialization error")
434
            .expect("insert work");
435 1
        let binary = serialize::<K, V>(&Node::LEAF(leaf_many)).expect("serialization works");
436 1
        let read = deserialize::<K, V>(&binary).expect("deserialize successfully");
437
        match read {
438 1
            Node::LEAF(n) => {
439 1
                assert_eq!(n.entries.len(), 1);
440 1
                match n.entries[0].value {
441 1
                    Value::CLUSTER(ref iv) => {
442 1
                        assert_eq!(compare(&iv[0], &value), Ordering::Equal);
443 1
                        assert_eq!(compare(&iv[1], &value1), Ordering::Equal);
444
                    }
445 0
                    _ => panic!("expected CLUSTER"),
446
                }
447 1
            }
448 0
            _ => panic!("expected a leaf"),
449
        }
450 1
    }
451

452
    #[test]
453 1
    fn test_serialization_deserialization_leafs() {
454 1
        single_type_leaf_test::<u8, u8>(20, 10, 20);
455 1
        single_type_leaf_test::<u16, u16>(20, 10, 20);
456 1
        single_type_leaf_test::<u32, u32>(20, 10, 20);
457 1
        single_type_leaf_test::<u64, u64>(20, 10, 20);
458 1
        single_type_leaf_test::<u128, u128>(20, 10, 20);
459 1
        single_type_leaf_test::<i8, i8>(20, 10, 20);
460 1
        single_type_leaf_test::<i16, i16>(20, 10, 20);
461 1
        single_type_leaf_test::<i32, i32>(20, 10, 20);
462 1
        single_type_leaf_test::<i64, i64>(20, 10, 20);
463 1
        single_type_leaf_test::<i128, i128>(20, 10, 20);
464 1
        single_type_leaf_test::<f32, f32>(20.0, 10.0, 20.0);
465 1
        single_type_leaf_test::<f64, f64>(20.0, 10.0, 20.0);
466 1
        single_type_leaf_test::<String, String>("o".to_string(), "a".to_string(), "b".to_string());
467 1
        single_type_leaf_test::<i32, String>(10, "a".to_string(), "b".to_string());
468 1
        single_type_leaf_test::<String, i32>("a".to_string(), 10, 20);
469 1
        single_type_leaf_test::<String, ByteVec>("a".to_string(), vec![0, 1].into(), vec![2, 10].into());
470 1
        let id = PersyId(RecRef::new(10, 20));
471 1
        let id1 = PersyId(RecRef::new(20, 20));
472 1
        let id2 = PersyId(RecRef::new(30, 20));
473 1
        single_type_leaf_test::<PersyId, PersyId>(id, id1, id2);
474 1
    }
475
}

Read our documentation on viewing source code .

Loading