use crate::{
error::{PRes, PersyError},
id::{PersyId, RecRef},
index::{
config::{ByteVec, IndexType, IndexTypeId},
keeper::Container,
tree::{Leaf, LeafEntry, Node, NodeRef, Nodes, Value},
},
};
use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
use std::io::{Cursor, Read, Write};
macro_rules! impl_index_type {
($t:ty, $v:expr,$v1:ident,$w:ty) => {
impl IndexType for $t {
type Wrapper = Container<Self>;
fn get_id() -> u8 {
$v
}
fn get_type_id() -> IndexTypeId {
IndexTypeId::$v1
}
}
};
}
impl_index_type!(u8, 1, U8, u8);
impl_index_type!(u16, 2, U16, u16);
impl_index_type!(u32, 3, U32, u32);
impl_index_type!(u64, 4, U64, u64);
impl_index_type!(u128, 14, U128, u128);
impl_index_type!(i8, 5, I8, i8);
impl_index_type!(i16, 6, I16, i16);
impl_index_type!(i32, 7, I32, i32);
impl_index_type!(i64, 8, I64, i64);
impl_index_type!(i128, 15, I128, i128);
impl_index_type!(f32, 9, F32W, F32W);
impl_index_type!(f64, 10, F64W, F64W);
impl_index_type!(String, 12, STRING, String);
impl_index_type!(PersyId, 13, PERSYID, PersyId);
impl_index_type!(ByteVec, 16, BYTEVEC, ByteVec);
pub trait IndexSerialization: Sized {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()>;
fn deserialize(value: &mut dyn Read) -> PRes<Self>;
}
pub fn deserialize<K: IndexType, V: IndexType>(value: &[u8]) -> PRes<Node<K, V>> {
let mut reader = Cursor::new(value);
let t = reader.read_u8()?;
match t {
1 => {
let prev = if reader.read_u8()? == 1 {
Some(K::deserialize(&mut reader)?)
} else {
None
};
let size = reader.read_u32::<BigEndian>()?;
let mut entries = Vec::with_capacity(size as usize);
for _ in 0..size {
let key = K::deserialize(&mut reader)?;
let value_type = reader.read_u8()?;
if value_type == 1 {
let val_size = reader.read_u32::<BigEndian>()?;
let mut value = Vec::with_capacity(val_size as usize);
for _ in 0..val_size {
value.push(V::deserialize(&mut reader)?);
}
entries.push(LeafEntry {
key,
value: Value::CLUSTER(value),
});
} else {
let value = V::deserialize(&mut reader)?;
entries.push(LeafEntry {
key,
value: Value::SINGLE(value),
});
}
}
let next = if reader.read_u8()? == 1 {
Some(K::deserialize(&mut reader)?)
} else {
None
};
Ok(Node::LEAF(Leaf { entries, prev, next }))
}
2 => {
let prev = if reader.read_u8()? == 1 {
Some(K::deserialize(&mut reader)?)
} else {
None
};
let size = reader.read_u32::<BigEndian>()?;
let mut keys = Vec::with_capacity(size as usize);
for _ in 0..size {
let key = K::deserialize(&mut reader)?;
keys.push(key);
}
let size = reader.read_u32::<BigEndian>()?;
let mut pointers = Vec::with_capacity(size as usize);
for _ in 0..size {
let page = reader.read_u64::<BigEndian>()?;
let pos = reader.read_u32::<BigEndian>()?;
pointers.push(RecRef::new(page, pos));
}
let next = if reader.read_u8()? == 1 {
Some(K::deserialize(&mut reader)?)
} else {
None
};
Ok(Node::NODE(Nodes {
keys,
pointers,
prev,
next,
}))
}
_ => panic!("error on index node deserialization"),
}
}
pub fn serialize<K: IndexType, V: IndexType>(node: &Node<K, V>) -> PRes<Vec<u8>> {
let mut dest = Vec::new();
let write_page_and_pos = |dest: &mut Vec<u8>, page, pos| -> PRes<()> {
dest.write_u64::<BigEndian>(page)?;
dest.write_u32::<BigEndian>(pos)?;
Ok(())
};
let write_opt_leafptr = |dest: &mut Vec<u8>, x: Option<&NodeRef>| -> PRes<()> {
if let Some(y) = x {
write_page_and_pos(dest, y.page, y.pos)?;
} else {
write_page_and_pos(dest, 0, 0)?;
}
Ok(())
};
match node {
Node::LEAF(leaf) => {
dest.write_u8(1)?;
if let Some(pk) = &leaf.prev {
dest.write_u8(1)?;
pk.serialize(&mut dest)?;
} else {
dest.write_u8(0)?;
}
dest.write_u32::<BigEndian>(leaf.entries.len() as u32)?;
for entry in &leaf.entries {
entry.key.serialize(&mut dest)?;
match &entry.value {
Value::CLUSTER(cluster) => {
dest.write_u8(1)?;
dest.write_u32::<BigEndian>(cluster.len() as u32)?;
for val in cluster {
val.serialize(&mut dest)?;
}
}
Value::SINGLE(val) => {
dest.write_u8(2)?;
val.serialize(&mut dest)?;
}
}
}
if let Some(pk) = &leaf.next {
dest.write_u8(1)?;
pk.serialize(&mut dest)?;
} else {
dest.write_u8(0)?;
}
}
Node::NODE(node) => {
dest.write_u8(2)?;
if let Some(pk) = &node.prev {
dest.write_u8(1)?;
pk.serialize(&mut dest)?;
} else {
dest.write_u8(0)?;
}
dest.write_u32::<BigEndian>(node.keys.len() as u32)?;
for k in &node.keys {
k.serialize(&mut dest)?;
}
dest.write_u32::<BigEndian>(node.pointers.len() as u32)?;
for p in &node.pointers {
write_opt_leafptr(&mut dest, Some(p))?;
}
if let Some(pk) = &node.next {
dest.write_u8(1)?;
pk.serialize(&mut dest)?;
} else {
dest.write_u8(0)?;
}
}
}
Ok(dest)
}
impl IndexSerialization for u8 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_u8(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_u8().map_err(PersyError::from)
}
}
impl IndexSerialization for u16 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_u16::<BigEndian>(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_u16::<BigEndian>().map_err(PersyError::from)
}
}
impl IndexSerialization for u32 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_u32::<BigEndian>(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_u32::<BigEndian>().map_err(PersyError::from)
}
}
impl IndexSerialization for u64 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_u64::<BigEndian>(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_u64::<BigEndian>().map_err(PersyError::from)
}
}
impl IndexSerialization for u128 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_u128::<BigEndian>(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_u128::<BigEndian>().map_err(PersyError::from)
}
}
impl IndexSerialization for i8 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_i8(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_i8().map_err(PersyError::from)
}
}
impl IndexSerialization for i16 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_i16::<BigEndian>(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_i16::<BigEndian>().map_err(PersyError::from)
}
}
impl IndexSerialization for i32 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_i32::<BigEndian>(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_i32::<BigEndian>().map_err(PersyError::from)
}
}
impl IndexSerialization for i64 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_i64::<BigEndian>(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_i64::<BigEndian>().map_err(PersyError::from)
}
}
impl IndexSerialization for i128 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_i128::<BigEndian>(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_i128::<BigEndian>().map_err(PersyError::from)
}
}
impl IndexSerialization for f32 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_f32::<BigEndian>(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_f32::<BigEndian>().map_err(PersyError::from)
}
}
impl IndexSerialization for f64 {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_f64::<BigEndian>(*self).map_err(PersyError::from)
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
value.read_f64::<BigEndian>().map_err(PersyError::from)
}
}
impl IndexSerialization for PersyId {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_u64::<BigEndian>(self.0.page)?;
buffer.write_u32::<BigEndian>(self.0.pos)?;
Ok(())
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
let page = value.read_u64::<BigEndian>()?;
let pos = value.read_u32::<BigEndian>()?;
Ok(PersyId(RecRef::new(page, pos)))
}
}
impl IndexSerialization for String {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_u16::<BigEndian>(self.len() as u16)?;
buffer.write_all(self.as_bytes())?;
Ok(())
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
let string_size = value.read_u16::<BigEndian>()?;
let mut string = String::with_capacity(string_size as usize);
value.take(u64::from(string_size)).read_to_string(&mut string)?;
Ok(string)
}
}
impl IndexSerialization for ByteVec {
fn serialize(&self, buffer: &mut dyn Write) -> PRes<()> {
buffer.write_u16::<BigEndian>(self.0.len() as u16)?;
buffer.write_all(self.0.as_slice())?;
Ok(())
}
fn deserialize(value: &mut dyn Read) -> PRes<Self> {
let vec_size = value.read_u16::<BigEndian>()?;
let mut slice: Vec<u8> = Vec::new();
value.take(u64::from(vec_size)).read_to_end(&mut slice)?;
Ok(ByteVec(slice))
}
}
#[cfg(test)]
mod tests {
use super::{deserialize, serialize};
use crate::id::{PersyId, RecRef};
use crate::index::{
config::{ByteVec, IndexType, ValueMode},
tree::{compare, Leaf, Node, NodeRef, Nodes, Value},
};
use rand::random;
use std::{cmp::Ordering, fmt::Debug};
fn random_pointer() -> NodeRef {
RecRef::new(random::<u64>(), random::<u32>())
}
#[test]
fn test_serialization_deserialization_nodes() {
let val1 = random_pointer();
let val2 = random_pointer();
let val3 = random_pointer();
let mut node = Nodes::new_from_split(val1, &[(0, val2)]);
let pos = node.find(&2).pos;
node.add(pos, &2, val3.clone());
let value = serialize::<u8, u8>(&Node::NODE(node)).expect("serialization works");
let read = deserialize::<u8, u8>(&value).expect("deserialzie successfully");
match read {
Node::NODE(n) => {
assert_eq!(n.keys.len(), 2);
assert_eq!(n.pointers.len(), 3);
}
_ => panic!("expected a node"),
}
}
fn single_type_leaf_test<K: IndexType + Debug, V: IndexType + Debug>(key: K, value: V, value1: V) {
let mut leaf = Leaf::new();
leaf.insert_or_update(&key, &value, ValueMode::REPLACE, "deserialization error")
.expect("insert work");
let binary = serialize::<K, V>(&Node::LEAF(leaf)).expect("serialization works");
let read = deserialize::<K, V>(&binary).expect("deserialize successfully");
match read {
Node::LEAF(n) => {
assert_eq!(n.entries.len(), 1);
match n.entries[0].value {
Value::SINGLE(ref iv) => assert_eq!(compare(iv, &value), Ordering::Equal),
_ => panic!("expected SINGLE"),
}
}
_ => panic!("expected a leaf"),
}
let mut leaf_many = Leaf::new();
leaf_many
.insert_or_update(&key, &value, ValueMode::CLUSTER, "deserialization error")
.expect("insert work");
leaf_many
.insert_or_update(&key, &value1, ValueMode::CLUSTER, "deserialization error")
.expect("insert work");
let binary = serialize::<K, V>(&Node::LEAF(leaf_many)).expect("serialization works");
let read = deserialize::<K, V>(&binary).expect("deserialize successfully");
match read {
Node::LEAF(n) => {
assert_eq!(n.entries.len(), 1);
match n.entries[0].value {
Value::CLUSTER(ref iv) => {
assert_eq!(compare(&iv[0], &value), Ordering::Equal);
assert_eq!(compare(&iv[1], &value1), Ordering::Equal);
}
_ => panic!("expected CLUSTER"),
}
}
_ => panic!("expected a leaf"),
}
}
#[test]
fn test_serialization_deserialization_leafs() {
single_type_leaf_test::<u8, u8>(20, 10, 20);
single_type_leaf_test::<u16, u16>(20, 10, 20);
single_type_leaf_test::<u32, u32>(20, 10, 20);
single_type_leaf_test::<u64, u64>(20, 10, 20);
single_type_leaf_test::<u128, u128>(20, 10, 20);
single_type_leaf_test::<i8, i8>(20, 10, 20);
single_type_leaf_test::<i16, i16>(20, 10, 20);
single_type_leaf_test::<i32, i32>(20, 10, 20);
single_type_leaf_test::<i64, i64>(20, 10, 20);
single_type_leaf_test::<i128, i128>(20, 10, 20);
single_type_leaf_test::<f32, f32>(20.0, 10.0, 20.0);
single_type_leaf_test::<f64, f64>(20.0, 10.0, 20.0);
single_type_leaf_test::<String, String>("o".to_string(), "a".to_string(), "b".to_string());
single_type_leaf_test::<i32, String>(10, "a".to_string(), "b".to_string());
single_type_leaf_test::<String, i32>("a".to_string(), 10, 20);
single_type_leaf_test::<String, ByteVec>("a".to_string(), vec![0, 1].into(), vec![2, 10].into());
let id = PersyId(RecRef::new(10, 20));
let id1 = PersyId(RecRef::new(20, 20));
let id2 = PersyId(RecRef::new(30, 20));
single_type_leaf_test::<PersyId, PersyId>(id, id1, id2);
}
}