use crate::core::ser::{self, Readable, Reader, Writeable, Writer};
use crate::store::Batch;
use crate::types::CommitPos;
use crate::util::secp::pedersen::Commitment;
use enum_primitive::FromPrimitive;
use grin_store as store;
use std::marker::PhantomData;
use store::{to_key, to_key_u64, Error};
enum_from_primitive! {
#[derive(Copy, Clone, Debug, PartialEq)]
enum ListWrapperVariant {
Single = 0,
Multi = 1,
}
}
impl Writeable for ListWrapperVariant {
fn write<W: Writer>(&self, writer: &mut W) -> Result<(), ser::Error> {
writer.write_u8(*self as u8)
}
}
impl Readable for ListWrapperVariant {
fn read<R: Reader>(reader: &mut R) -> Result<ListWrapperVariant, ser::Error> {
ListWrapperVariant::from_u8(reader.read_u8()?).ok_or(ser::Error::CorruptedData)
}
}
enum_from_primitive! {
#[derive(Copy, Clone, Debug, PartialEq)]
enum ListEntryVariant {
Head = 2,
Tail = 3,
Middle = 4,
}
}
impl Writeable for ListEntryVariant {
fn write<W: Writer>(&self, writer: &mut W) -> Result<(), ser::Error> {
writer.write_u8(*self as u8)
}
}
impl Readable for ListEntryVariant {
fn read<R: Reader>(reader: &mut R) -> Result<ListEntryVariant, ser::Error> {
ListEntryVariant::from_u8(reader.read_u8()?).ok_or(ser::Error::CorruptedData)
}
}
pub trait ListIndex {
type List: Readable + Writeable;
type Entry: ListIndexEntry;
fn list_key(&self, commit: Commitment) -> Vec<u8>;
fn entry_key(&self, commit: Commitment, pos: u64) -> Vec<u8>;
fn get_list(&self, batch: &Batch<'_>, commit: Commitment) -> Result<Option<Self::List>, Error> {
batch.db.get_ser(&self.list_key(commit))
}
fn get_entry(
&self,
batch: &Batch<'_>,
commit: Commitment,
pos: u64,
) -> Result<Option<Self::Entry>, Error> {
batch.db.get_ser(&self.entry_key(commit, pos))
}
fn peek_pos(
&self,
batch: &Batch<'_>,
commit: Commitment,
) -> Result<Option<<Self::Entry as ListIndexEntry>::Pos>, Error>;
fn push_pos(
&self,
batch: &Batch<'_>,
commit: Commitment,
new_pos: <Self::Entry as ListIndexEntry>::Pos,
) -> Result<(), Error>;
fn pop_pos(
&self,
batch: &Batch<'_>,
commit: Commitment,
) -> Result<Option<<Self::Entry as ListIndexEntry>::Pos>, Error>;
}
pub trait RewindableListIndex {
fn rewind(&self, batch: &Batch<'_>, commit: Commitment, rewind_pos: u64) -> Result<(), Error>;
}
pub trait PruneableListIndex: ListIndex {
fn clear(&self, batch: &Batch<'_>) -> Result<(), Error>;
fn prune(&self, batch: &Batch<'_>, commit: Commitment, cutoff_pos: u64) -> Result<(), Error>;
fn pop_pos_back(
&self,
batch: &Batch<'_>,
commit: Commitment,
) -> Result<Option<<Self::Entry as ListIndexEntry>::Pos>, Error>;
}
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum ListWrapper<T> {
Single {
pos: T,
},
Multi {
head: u64,
tail: u64,
},
}
impl<T> Writeable for ListWrapper<T>
where
T: Writeable,
{
fn write<W: Writer>(&self, writer: &mut W) -> Result<(), ser::Error> {
match self {
ListWrapper::Single { pos } => {
ListWrapperVariant::Single.write(writer)?;
pos.write(writer)?;
}
ListWrapper::Multi { head, tail } => {
ListWrapperVariant::Multi.write(writer)?;
writer.write_u64(*head)?;
writer.write_u64(*tail)?;
}
}
Ok(())
}
}
impl<T> Readable for ListWrapper<T>
where
T: Readable,
{
fn read<R: Reader>(reader: &mut R) -> Result<ListWrapper<T>, ser::Error> {
let entry = match ListWrapperVariant::read(reader)? {
ListWrapperVariant::Single => ListWrapper::Single {
pos: T::read(reader)?,
},
ListWrapperVariant::Multi => ListWrapper::Multi {
head: reader.read_u64()?,
tail: reader.read_u64()?,
},
};
Ok(entry)
}
}
pub struct MultiIndex<T> {
phantom: PhantomData<*const T>,
list_prefix: u8,
entry_prefix: u8,
}
impl<T> MultiIndex<T> {
pub fn init(list_prefix: u8, entry_prefix: u8) -> MultiIndex<T> {
MultiIndex {
phantom: PhantomData,
list_prefix,
entry_prefix,
}
}
}
impl<T> ListIndex for MultiIndex<T>
where
T: PosEntry,
{
type List = ListWrapper<T>;
type Entry = ListEntry<T>;
fn list_key(&self, commit: Commitment) -> Vec<u8> {
to_key(self.list_prefix, &mut commit.as_ref().to_vec())
}
fn entry_key(&self, commit: Commitment, pos: u64) -> Vec<u8> {
to_key_u64(self.entry_prefix, &mut commit.as_ref().to_vec(), pos)
}
fn peek_pos(&self, batch: &Batch<'_>, commit: Commitment) -> Result<Option<T>, Error> {
match self.get_list(batch, commit)? {
None => Ok(None),
Some(ListWrapper::Single { pos }) => Ok(Some(pos)),
Some(ListWrapper::Multi { head, .. }) => {
if let Some(ListEntry::Head { pos, .. }) = self.get_entry(batch, commit, head)? {
Ok(Some(pos))
} else {
Err(Error::OtherErr("expected head to be head variant".into()))
}
}
}
}
fn push_pos(&self, batch: &Batch<'_>, commit: Commitment, new_pos: T) -> Result<(), Error> {
match self.get_list(batch, commit)? {
None => {
let list = ListWrapper::Single { pos: new_pos };
batch.db.put_ser(&self.list_key(commit), &list)?;
}
Some(ListWrapper::Single { pos: current_pos }) => {
if new_pos.pos() <= current_pos.pos() {
return Err(Error::OtherErr("pos must be increasing".into()));
}
let head = ListEntry::Head {
pos: new_pos,
next: current_pos.pos(),
};
let tail = ListEntry::Tail {
pos: current_pos,
prev: new_pos.pos(),
};
let list: ListWrapper<T> = ListWrapper::Multi {
head: new_pos.pos(),
tail: current_pos.pos(),
};
batch
.db
.put_ser(&self.entry_key(commit, new_pos.pos()), &head)?;
batch
.db
.put_ser(&self.entry_key(commit, current_pos.pos()), &tail)?;
batch.db.put_ser(&self.list_key(commit), &list)?;
}
Some(ListWrapper::Multi { head, tail }) => {
if new_pos.pos() <= head {
return Err(Error::OtherErr("pos must be increasing".into()));
}
if let Some(ListEntry::Head {
pos: current_pos,
next: current_next,
}) = self.get_entry(batch, commit, head)?
{
let head = ListEntry::Head {
pos: new_pos,
next: current_pos.pos(),
};
let middle = ListEntry::Middle {
pos: current_pos,
next: current_next,
prev: new_pos.pos(),
};
let list: ListWrapper<T> = ListWrapper::Multi {
head: new_pos.pos(),
tail,
};
batch
.db
.put_ser(&self.entry_key(commit, new_pos.pos()), &head)?;
batch
.db
.put_ser(&self.entry_key(commit, current_pos.pos()), &middle)?;
batch.db.put_ser(&self.list_key(commit), &list)?;
} else {
return Err(Error::OtherErr("expected head to be head variant".into()));
}
}
}
Ok(())
}
fn pop_pos(&self, batch: &Batch<'_>, commit: Commitment) -> Result<Option<T>, Error> {
match self.get_list(batch, commit)? {
None => Ok(None),
Some(ListWrapper::Single { pos }) => {
batch.delete(&self.list_key(commit))?;
Ok(Some(pos))
}
Some(ListWrapper::Multi { head, tail }) => {
if let Some(ListEntry::Head {
pos: current_pos,
next: current_next,
}) = self.get_entry(batch, commit, head)?
{
match self.get_entry(batch, commit, current_next)? {
Some(ListEntry::Middle { pos, next, .. }) => {
let head = ListEntry::Head { pos, next };
let list: ListWrapper<T> = ListWrapper::Multi {
head: pos.pos(),
tail,
};
batch.delete(&self.entry_key(commit, current_pos.pos()))?;
batch
.db
.put_ser(&self.entry_key(commit, pos.pos()), &head)?;
batch.db.put_ser(&self.list_key(commit), &list)?;
Ok(Some(current_pos))
}
Some(ListEntry::Tail { pos, .. }) => {
let list = ListWrapper::Single { pos };
batch.delete(&self.entry_key(commit, current_pos.pos()))?;
batch.db.put_ser(&self.list_key(commit), &list)?;
Ok(Some(current_pos))
}
Some(_) => Err(Error::OtherErr("next was unexpected".into())),
None => Err(Error::OtherErr("next missing".into())),
}
} else {
Err(Error::OtherErr("expected head to be head variant".into()))
}
}
}
}
}
impl<T: PosEntry> RewindableListIndex for MultiIndex<T> {
fn rewind(&self, batch: &Batch<'_>, commit: Commitment, rewind_pos: u64) -> Result<(), Error> {
while self
.peek_pos(batch, commit)?
.map(|x| x.pos() > rewind_pos)
.unwrap_or(false)
{
self.pop_pos(batch, commit)?;
}
Ok(())
}
}
impl<T: PosEntry> PruneableListIndex for MultiIndex<T> {
fn clear(&self, batch: &Batch<'_>) -> Result<(), Error> {
let mut list_count = 0;
let mut entry_count = 0;
let prefix = to_key(self.list_prefix, "");
for (key, _) in batch.db.iter::<ListWrapper<T>>(&prefix)? {
let _ = batch.delete(&key);
list_count += 1;
}
let prefix = to_key(self.entry_prefix, "");
for (key, _) in batch.db.iter::<ListEntry<T>>(&prefix)? {
let _ = batch.delete(&key);
entry_count += 1;
}
debug!(
"clear: lists deleted: {}, entries deleted: {}",
list_count, entry_count
);
Ok(())
}
fn prune(
&self,
_batch: &Batch<'_>,
_commit: Commitment,
_cutoff_pos: u64,
) -> Result<(), Error> {
unimplemented!(
"we currently rebuild index on startup/compaction, pruning not yet implemented"
);
}
fn pop_pos_back(&self, batch: &Batch<'_>, commit: Commitment) -> Result<Option<T>, Error> {
match self.get_list(batch, commit)? {
None => Ok(None),
Some(ListWrapper::Single { pos }) => {
batch.delete(&self.list_key(commit))?;
Ok(Some(pos))
}
Some(ListWrapper::Multi { head, tail }) => {
if let Some(ListEntry::Tail {
pos: current_pos,
prev: current_prev,
}) = self.get_entry(batch, commit, tail)?
{
match self.get_entry(batch, commit, current_prev)? {
Some(ListEntry::Middle { pos, prev, .. }) => {
let tail = ListEntry::Tail { pos, prev };
let list: ListWrapper<T> = ListWrapper::Multi {
head,
tail: pos.pos(),
};
batch.delete(&self.entry_key(commit, current_pos.pos()))?;
batch
.db
.put_ser(&self.entry_key(commit, pos.pos()), &tail)?;
batch.db.put_ser(&self.list_key(commit), &list)?;
Ok(Some(current_pos))
}
Some(ListEntry::Head { pos, .. }) => {
let list = ListWrapper::Single { pos };
batch.delete(&self.entry_key(commit, current_pos.pos()))?;
batch.db.put_ser(&self.list_key(commit), &list)?;
Ok(Some(current_pos))
}
Some(_) => Err(Error::OtherErr("prev was unexpected".into())),
None => Err(Error::OtherErr("prev missing".into())),
}
} else {
Err(Error::OtherErr("expected tail to be tail variant".into()))
}
}
}
}
}
pub trait PosEntry: Readable + Writeable + Copy {
fn pos(&self) -> u64;
}
impl PosEntry for CommitPos {
fn pos(&self) -> u64 {
self.pos
}
}
pub trait ListIndexEntry: Readable + Writeable {
type Pos: PosEntry;
fn get_pos(&self) -> Self::Pos;
}
impl<T> ListIndexEntry for ListEntry<T>
where
T: PosEntry,
{
type Pos = T;
fn get_pos(&self) -> Self::Pos {
match self {
Self::Head { pos, .. } => *pos,
Self::Tail { pos, .. } => *pos,
Self::Middle { pos, .. } => *pos,
}
}
}
pub enum ListEntry<T> {
Head {
pos: T,
next: u64,
},
Tail {
pos: T,
prev: u64,
},
Middle {
pos: T,
next: u64,
prev: u64,
},
}
impl<T> Writeable for ListEntry<T>
where
T: Writeable,
{
fn write<W: Writer>(&self, writer: &mut W) -> Result<(), ser::Error> {
match self {
ListEntry::Head { pos, next } => {
ListEntryVariant::Head.write(writer)?;
pos.write(writer)?;
writer.write_u64(*next)?;
}
ListEntry::Tail { pos, prev } => {
ListEntryVariant::Tail.write(writer)?;
pos.write(writer)?;
writer.write_u64(*prev)?;
}
ListEntry::Middle { pos, next, prev } => {
ListEntryVariant::Middle.write(writer)?;
pos.write(writer)?;
writer.write_u64(*next)?;
writer.write_u64(*prev)?;
}
}
Ok(())
}
}
impl<T> Readable for ListEntry<T>
where
T: Readable,
{
fn read<R: Reader>(reader: &mut R) -> Result<ListEntry<T>, ser::Error> {
let entry = match ListEntryVariant::read(reader)? {
ListEntryVariant::Head => ListEntry::Head {
pos: T::read(reader)?,
next: reader.read_u64()?,
},
ListEntryVariant::Tail => ListEntry::Tail {
pos: T::read(reader)?,
prev: reader.read_u64()?,
},
ListEntryVariant::Middle => ListEntry::Middle {
pos: T::read(reader)?,
next: reader.read_u64()?,
prev: reader.read_u64()?,
},
};
Ok(entry)
}
}