#![deny(
missing_docs,
trivial_casts,
trivial_numeric_casts,
unused_import_braces,
unused_qualifications
)]
#[cfg(test)]
extern crate hex;
#[macro_use]
extern crate log;
#[cfg(feature = "uuid")]
extern crate uuid;
#[doc(hidden)]
pub mod skiplist;
#[doc(hidden)]
pub mod transaction;
use rand::Rng;
use skiplist::SkipCursor;
use std::borrow::Borrow;
pub use transaction::{
CRCError, Commit, Env, Error, Exclusive, LoadPage, MutTxn, Shared, Statistics, Txn, ZERO_HEADER, Page
};
use transaction::{Cow, MutPage};
#[derive(Clone, Copy, Debug)]
pub struct Db<K: Representable, V: Representable>(#[doc(hidden)] pub u64, #[doc(hidden)]pub std::marker::PhantomData<(K, V)>);
#[derive(Clone, Copy, Debug)]
pub struct UnsafeDb(u64);
pub mod value;
#[repr(u16)]
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
pub enum Alignment {
B1 = 1,
B2 = 2,
B4 = 4,
B8 = 8,
}
pub trait Representable: Copy + std::fmt::Debug {
type PageOffsets: Iterator<Item = u64>;
fn alignment() -> Alignment {
Alignment::B8
}
fn onpage_size(&self) -> u16;
unsafe fn skip(p: *mut u8) -> *mut u8 {
let r = Self::read_value(p);
p.offset(r.onpage_size() as isize)
}
unsafe fn write_value(&self, p: *mut u8);
unsafe fn read_value(p: *const u8) -> Self;
unsafe fn cmp_value<T: LoadPage>(&self, txn: &T, x: Self) -> std::cmp::Ordering;
fn drop_value<E: Borrow<Env<Exclusive>>, T, R: Rng>(
&self,
_: &mut MutTxn<E, T>,
_: &mut R,
) -> Result<(), Error> {
Ok(())
}
fn page_offsets(&self) -> Self::PageOffsets;
}
impl<A: Representable, B: Representable> Representable for (A, B) {
fn alignment() -> Alignment {
std::cmp::max(A::alignment(), B::alignment())
}
fn onpage_size(&self) -> u16 {
let a_size = self.0.onpage_size();
let b_size = self.1.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
let size = a_size + b_size + b_padding;
debug!("size: {:?}", size);
size
}
unsafe fn write_value(&self, p: *mut u8) {
self.0.write_value(p);
let a_size = self.0.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
self.1.write_value(p.offset((a_size + b_padding) as isize))
}
unsafe fn read_value(p: *const u8) -> Self {
let a = A::read_value(p);
let a_size = a.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
let a = A::read_value(p);
let b = B::read_value(p.offset((a_size + b_padding) as isize));
(a, b)
}
unsafe fn cmp_value<T: LoadPage>(&self, txn: &T, x: Self) -> std::cmp::Ordering {
let ord = self.0.cmp_value(txn, x.0);
if let std::cmp::Ordering::Equal = ord {
self.1.cmp_value(txn, x.1)
} else {
ord
}
}
type PageOffsets = std::iter::Chain<A::PageOffsets, B::PageOffsets>;
fn page_offsets(&self) -> Self::PageOffsets {
self.0.page_offsets().chain(self.1.page_offsets())
}
fn drop_value<E: Borrow<Env<Exclusive>>, T, R: Rng>(
&self,
txn: &mut MutTxn<E, T>,
rng: &mut R,
) -> Result<(), Error> {
self.0.drop_value(txn, rng)?;
self.1.drop_value(txn, rng)?;
Ok(())
}
}
impl<A: Representable, B: Representable, C: Representable> Representable for (A, B, C) {
fn alignment() -> Alignment {
std::cmp::max(
std::cmp::max(A::alignment(), B::alignment()),
C::alignment(),
)
}
fn onpage_size(&self) -> u16 {
let a_size = self.0.onpage_size();
let b_size = self.1.onpage_size();
let c_size = self.2.onpage_size();
let b_align = B::alignment() as u16;
let c_align = C::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
let a_b_size = a_size + b_size + b_padding;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
let size = a_b_size + c_size + c_padding;
debug!("size: {:?}", size);
size
}
unsafe fn write_value(&self, p: *mut u8) {
self.0.write_value(p);
let a_size = self.0.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
self.1.write_value(p.offset((a_size + b_padding) as isize));
let b_size = self.1.onpage_size();
let a_b_size = a_size + b_size + b_padding;
let c_align = C::alignment() as u16;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
self.2
.write_value(p.offset((a_b_size + c_padding) as isize))
}
unsafe fn read_value(p: *const u8) -> Self {
let a = A::read_value(p);
let a_size = a.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
let b = B::read_value(p.offset((a_size + b_padding) as isize));
let b_size = b.onpage_size();
let a_b_size = a_size + b_size + b_padding;
let c_align = C::alignment() as u16;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
let c = C::read_value(p.offset((a_b_size + c_padding) as isize));
(a, b, c)
}
unsafe fn cmp_value<T: LoadPage>(&self, txn: &T, x: Self) -> std::cmp::Ordering {
let ord = self.0.cmp_value(txn, x.0);
if let std::cmp::Ordering::Equal = ord {
let ord = self.1.cmp_value(txn, x.1);
if let std::cmp::Ordering::Equal = ord {
self.2.cmp_value(txn, x.2)
} else {
ord
}
} else {
ord
}
}
type PageOffsets =
std::iter::Chain<std::iter::Chain<A::PageOffsets, B::PageOffsets>, C::PageOffsets>;
fn page_offsets(&self) -> Self::PageOffsets {
self.0
.page_offsets()
.chain(self.1.page_offsets())
.chain(self.2.page_offsets())
}
fn drop_value<E: Borrow<Env<Exclusive>>, T, R: Rng>(
&self,
txn: &mut MutTxn<E, T>,
rng: &mut R,
) -> Result<(), Error> {
self.0.drop_value(txn, rng)?;
self.1.drop_value(txn, rng)?;
self.2.drop_value(txn, rng)?;
Ok(())
}
}
impl<A: Representable, B: Representable, C: Representable, D: Representable> Representable
for (A, B, C, D)
{
fn alignment() -> Alignment {
std::cmp::max(
std::cmp::max(A::alignment(), B::alignment()),
std::cmp::max(C::alignment(), D::alignment()),
)
}
fn onpage_size(&self) -> u16 {
let a_size = self.0.onpage_size();
let b_size = self.1.onpage_size();
let c_size = self.2.onpage_size();
let d_size = self.3.onpage_size();
let b_align = B::alignment() as u16;
let c_align = C::alignment() as u16;
let d_align = D::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
let a_b_size = a_size + b_size + b_padding;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
let a_b_c_size = a_b_size + c_size + c_padding;
let d_padding = (d_align - (a_b_c_size % d_align)) % d_align;
let a_b_c_d_size = a_b_c_size + d_size + d_padding;
info!("size = {:?}", a_b_c_d_size);
a_b_c_d_size
}
unsafe fn write_value(&self, p: *mut u8) {
self.0.write_value(p);
let a_size = self.0.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
self.1.write_value(p.offset((a_size + b_padding) as isize));
let b_size = self.1.onpage_size();
let a_b_size = a_size + b_size + b_padding;
let c_align = C::alignment() as u16;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
self.2
.write_value(p.offset((a_b_size + c_padding) as isize));
let c_size = self.2.onpage_size();
let a_b_c_size = a_b_size + c_size + c_padding;
let d_align = D::alignment() as u16;
let d_padding = (d_align - (a_b_c_size % d_align)) % d_align;
self.3
.write_value(p.offset((a_b_c_size + d_padding) as isize));
}
unsafe fn read_value(p: *const u8) -> Self {
let a = A::read_value(p);
let a_size = a.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
let b = B::read_value(p.offset((a_size + b_padding) as isize));
let b_size = b.onpage_size();
let a_b_size = a_size + b_size + b_padding;
let c_align = C::alignment() as u16;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
let c = C::read_value(p.offset((a_b_size + c_padding) as isize));
let c_size = c.onpage_size();
let a_b_c_size = a_b_size + c_size + c_padding;
let d_align = D::alignment() as u16;
let d_padding = (d_align - (a_b_c_size % d_align)) % d_align;
let d = D::read_value(p.offset((a_b_c_size + d_padding) as isize));
info!("{:?} {:?} {:?} {:?}", a, b, c, d);
(a, b, c, d)
}
unsafe fn cmp_value<T: LoadPage>(&self, txn: &T, x: Self) -> std::cmp::Ordering {
let ord = self.0.cmp_value(txn, x.0);
if let std::cmp::Ordering::Equal = ord {
let ord = self.1.cmp_value(txn, x.1);
if let std::cmp::Ordering::Equal = ord {
let ord = self.2.cmp_value(txn, x.2);
if let std::cmp::Ordering::Equal = ord {
self.3.cmp_value(txn, x.3)
} else {
ord
}
} else {
ord
}
} else {
ord
}
}
type PageOffsets = std::iter::Chain<
std::iter::Chain<A::PageOffsets, B::PageOffsets>,
std::iter::Chain<C::PageOffsets, D::PageOffsets>,
>;
fn page_offsets(&self) -> Self::PageOffsets {
self.0
.page_offsets()
.chain(self.1.page_offsets())
.chain(self.2.page_offsets().chain(self.3.page_offsets()))
}
fn drop_value<E: Borrow<Env<Exclusive>>, T, R: Rng>(
&self,
txn: &mut MutTxn<E, T>,
rng: &mut R,
) -> Result<(), Error> {
self.0.drop_value(txn, rng)?;
self.1.drop_value(txn, rng)?;
self.2.drop_value(txn, rng)?;
self.3.drop_value(txn, rng)?;
Ok(())
}
}
impl<A: Representable, B: Representable, C: Representable, D: Representable, E: Representable>
Representable for (A, B, C, D, E)
{
fn alignment() -> Alignment {
A::alignment()
.max(B::alignment())
.max(C::alignment())
.max(D::alignment())
.max(E::alignment())
}
fn onpage_size(&self) -> u16 {
let a_size = self.0.onpage_size();
let b_size = self.1.onpage_size();
let c_size = self.2.onpage_size();
let d_size = self.3.onpage_size();
let e_size = self.4.onpage_size();
let b_align = B::alignment() as u16;
let c_align = C::alignment() as u16;
let d_align = D::alignment() as u16;
let e_align = E::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
let a_b_size = a_size + b_size + b_padding;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
let a_b_c_size = a_b_size + c_size + c_padding;
let d_padding = (d_align - (a_b_c_size % d_align)) % d_align;
let a_b_c_d_size = a_b_c_size + d_size + d_padding;
let e_padding = (e_align - (a_b_c_d_size % e_align)) % e_align;
let a_b_c_d_e_size = a_b_c_d_size + e_size + e_padding;
info!("size = {:?}", a_b_c_d_e_size);
a_b_c_d_e_size
}
unsafe fn write_value(&self, p: *mut u8) {
self.0.write_value(p);
let a_size = self.0.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
self.1.write_value(p.offset((a_size + b_padding) as isize));
let b_size = self.1.onpage_size();
let a_b_size = a_size + b_size + b_padding;
let c_align = C::alignment() as u16;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
self.2
.write_value(p.offset((a_b_size + c_padding) as isize));
let c_size = self.2.onpage_size();
let a_b_c_size = a_b_size + c_size + c_padding;
let d_align = D::alignment() as u16;
let d_padding = (d_align - (a_b_c_size % d_align)) % d_align;
self.3
.write_value(p.offset((a_b_c_size + d_padding) as isize));
let d_size = self.3.onpage_size();
let a_b_c_d_size = a_b_c_size + d_size + d_padding;
let e_align = E::alignment() as u16;
let e_padding = (e_align - (a_b_c_d_size % e_align)) % e_align;
self.4
.write_value(p.offset((a_b_c_d_size + e_padding) as isize));
}
unsafe fn read_value(p: *const u8) -> Self {
let a = A::read_value(p);
let a_size = a.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
let b = B::read_value(p.offset((a_size + b_padding) as isize));
let b_size = b.onpage_size();
let a_b_size = a_size + b_size + b_padding;
let c_align = C::alignment() as u16;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
let c = C::read_value(p.offset((a_b_size + c_padding) as isize));
let c_size = c.onpage_size();
let a_b_c_size = a_b_size + c_size + c_padding;
let d_align = D::alignment() as u16;
let d_padding = (d_align - (a_b_c_size % d_align)) % d_align;
let d = D::read_value(p.offset((a_b_c_size + d_padding) as isize));
let d_size = d.onpage_size();
let a_b_c_d_size = a_b_c_size + d_size + d_padding;
let e_align = E::alignment() as u16;
let e_padding = (e_align - (a_b_c_d_size % e_align)) % e_align;
let e = E::read_value(p.offset((a_b_c_d_size + e_padding) as isize));
info!("{:?} {:?} {:?} {:?} {:?}", a, b, c, d, e);
(a, b, c, d, e)
}
unsafe fn cmp_value<T: LoadPage>(&self, txn: &T, x: Self) -> std::cmp::Ordering {
let ord = self.0.cmp_value(txn, x.0);
if let std::cmp::Ordering::Equal = ord {
let ord = self.1.cmp_value(txn, x.1);
if let std::cmp::Ordering::Equal = ord {
let ord = self.2.cmp_value(txn, x.2);
if let std::cmp::Ordering::Equal = ord {
let ord = self.3.cmp_value(txn, x.3);
if let std::cmp::Ordering::Equal = ord {
self.4.cmp_value(txn, x.4)
} else {
ord
}
} else {
ord
}
} else {
ord
}
} else {
ord
}
}
type PageOffsets = std::iter::Chain<
std::iter::Chain<
std::iter::Chain<std::iter::Chain<A::PageOffsets, B::PageOffsets>, C::PageOffsets>,
D::PageOffsets,
>,
E::PageOffsets,
>;
fn page_offsets(&self) -> Self::PageOffsets {
self.0
.page_offsets()
.chain(self.1.page_offsets())
.chain(self.2.page_offsets())
.chain(self.3.page_offsets())
.chain(self.4.page_offsets())
}
fn drop_value<Env_: Borrow<Env<Exclusive>>, T, R: Rng>(
&self,
txn: &mut MutTxn<Env_, T>,
rng: &mut R,
) -> Result<(), Error> {
self.0.drop_value(txn, rng)?;
self.1.drop_value(txn, rng)?;
self.2.drop_value(txn, rng)?;
self.3.drop_value(txn, rng)?;
self.4.drop_value(txn, rng)?;
Ok(())
}
}
impl<
A: Representable,
B: Representable,
C: Representable,
D: Representable,
E: Representable,
F: Representable,
> Representable for (A, B, C, D, E, F)
{
fn alignment() -> Alignment {
A::alignment()
.max(B::alignment())
.max(C::alignment())
.max(D::alignment())
.max(E::alignment())
.max(F::alignment())
}
fn onpage_size(&self) -> u16 {
let a_size = self.0.onpage_size();
let b_size = self.1.onpage_size();
let c_size = self.2.onpage_size();
let d_size = self.3.onpage_size();
let e_size = self.4.onpage_size();
let f_size = self.5.onpage_size();
let b_align = B::alignment() as u16;
let c_align = C::alignment() as u16;
let d_align = D::alignment() as u16;
let e_align = E::alignment() as u16;
let f_align = F::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
let a_b_size = a_size + b_size + b_padding;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
let a_b_c_size = a_b_size + c_size + c_padding;
let d_padding = (d_align - (a_b_c_size % d_align)) % d_align;
let a_b_c_d_size = a_b_c_size + d_size + d_padding;
let e_padding = (e_align - (a_b_c_d_size % e_align)) % e_align;
let a_b_c_d_e_size = a_b_c_d_size + e_size + e_padding;
let f_padding = (f_align - (a_b_c_d_e_size % f_align)) % f_align;
let a_b_c_d_e_f_size = a_b_c_d_e_size + f_size + f_padding;
info!("size = {:?}", a_b_c_d_e_f_size);
a_b_c_d_e_f_size
}
unsafe fn write_value(&self, p: *mut u8) {
self.0.write_value(p);
let a_size = self.0.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
self.1.write_value(p.offset((a_size + b_padding) as isize));
let b_size = self.1.onpage_size();
let a_b_size = a_size + b_size + b_padding;
let c_align = C::alignment() as u16;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
self.2
.write_value(p.offset((a_b_size + c_padding) as isize));
let c_size = self.2.onpage_size();
let a_b_c_size = a_b_size + c_size + c_padding;
let d_align = D::alignment() as u16;
let d_padding = (d_align - (a_b_c_size % d_align)) % d_align;
self.3
.write_value(p.offset((a_b_c_size + d_padding) as isize));
let d_size = self.3.onpage_size();
let a_b_c_d_size = a_b_c_size + d_size + d_padding;
let e_align = E::alignment() as u16;
let e_padding = (e_align - (a_b_c_d_size % e_align)) % e_align;
self.4
.write_value(p.offset((a_b_c_d_size + e_padding) as isize));
let e_size = self.4.onpage_size();
let a_b_c_d_e_size = a_b_c_d_size + e_size + e_padding;
let f_align = F::alignment() as u16;
let f_padding = (f_align - (a_b_c_d_e_size % f_align)) % f_align;
self.5
.write_value(p.offset((a_b_c_d_e_size + f_padding) as isize));
}
unsafe fn read_value(p: *const u8) -> Self {
let a = A::read_value(p);
let a_size = a.onpage_size();
let b_align = B::alignment() as u16;
let b_padding = (b_align - (a_size % b_align)) % b_align;
let b = B::read_value(p.offset((a_size + b_padding) as isize));
let b_size = b.onpage_size();
let a_b_size = a_size + b_size + b_padding;
let c_align = C::alignment() as u16;
let c_padding = (c_align - (a_b_size % c_align)) % c_align;
let c = C::read_value(p.offset((a_b_size + c_padding) as isize));
let c_size = c.onpage_size();
let a_b_c_size = a_b_size + c_size + c_padding;
let d_align = D::alignment() as u16;
let d_padding = (d_align - (a_b_c_size % d_align)) % d_align;
let d = D::read_value(p.offset((a_b_c_size + d_padding) as isize));
let d_size = d.onpage_size();
let a_b_c_d_size = a_b_c_size + d_size + d_padding;
let e_align = E::alignment() as u16;
let e_padding = (e_align - (a_b_c_d_size % e_align)) % e_align;
let e = E::read_value(p.offset((a_b_c_d_size + e_padding) as isize));
let e_size = e.onpage_size();
let a_b_c_d_e_size = a_b_c_d_size + e_size + e_padding;
let f_align = F::alignment() as u16;
let f_padding = (f_align - (a_b_c_d_e_size % f_align)) % f_align;
let f = F::read_value(p.offset((a_b_c_d_e_size + f_padding) as isize));
info!("{:?} {:?} {:?} {:?} {:?} {:?}", a, b, c, d, e, f);
(a, b, c, d, e, f)
}
unsafe fn cmp_value<T: LoadPage>(&self, txn: &T, x: Self) -> std::cmp::Ordering {
let ord = self.0.cmp_value(txn, x.0);
if let std::cmp::Ordering::Equal = ord {
let ord = self.1.cmp_value(txn, x.1);
if let std::cmp::Ordering::Equal = ord {
let ord = self.2.cmp_value(txn, x.2);
if let std::cmp::Ordering::Equal = ord {
let ord = self.3.cmp_value(txn, x.3);
if let std::cmp::Ordering::Equal = ord {
let ord = self.4.cmp_value(txn, x.4);
if let std::cmp::Ordering::Equal = ord {
self.5.cmp_value(txn, x.5)
} else {
ord
}
} else {
ord
}
} else {
ord
}
} else {
ord
}
} else {
ord
}
}
type PageOffsets = std::iter::Chain<
std::iter::Chain<
std::iter::Chain<
std::iter::Chain<std::iter::Chain<A::PageOffsets, B::PageOffsets>, C::PageOffsets>,
D::PageOffsets,
>,
E::PageOffsets,
>,
F::PageOffsets,
>;
fn page_offsets(&self) -> Self::PageOffsets {
self.0
.page_offsets()
.chain(self.1.page_offsets())
.chain(self.2.page_offsets())
.chain(self.3.page_offsets())
.chain(self.4.page_offsets())
.chain(self.5.page_offsets())
}
fn drop_value<Env_: Borrow<Env<Exclusive>>, T, R: Rng>(
&self,
txn: &mut MutTxn<Env_, T>,
rng: &mut R,
) -> Result<(), Error> {
self.0.drop_value(txn, rng)?;
self.1.drop_value(txn, rng)?;
self.2.drop_value(txn, rng)?;
self.3.drop_value(txn, rng)?;
self.4.drop_value(txn, rng)?;
self.5.drop_value(txn, rng)?;
Ok(())
}
}
impl Representable for f64 {
fn alignment() -> Alignment {
Alignment::B8
}
fn onpage_size(&self) -> u16 {
8
}
unsafe fn skip(p: *mut u8) -> *mut u8 {
p.offset(8)
}
unsafe fn write_value(&self, p: *mut u8) {
let s: u64 = std::mem::transmute(*self);
s.write_value(p)
}
unsafe fn read_value(p: *const u8) -> Self {
std::mem::transmute(u64::read_value(p))
}
unsafe fn cmp_value<T: LoadPage>(&self, _: &T, x: Self) -> std::cmp::Ordering {
(*self).partial_cmp(&x).unwrap()
}
type PageOffsets = std::iter::Empty<u64>;
fn page_offsets(&self) -> Self::PageOffsets {
std::iter::empty()
}
}
impl Representable for u64 {
fn alignment() -> Alignment {
Alignment::B8
}
fn onpage_size(&self) -> u16 {
8
}
unsafe fn skip(p: *mut u8) -> *mut u8 {
p.offset(8)
}
unsafe fn write_value(&self, p: *mut u8) {
*(p as *mut u64) = self.to_le()
}
unsafe fn read_value(p: *const u8) -> Self {
u64::from_le(*(p as *const u64))
}
unsafe fn cmp_value<T: LoadPage>(&self, _: &T, x: Self) -> std::cmp::Ordering {
self.cmp(&x)
}
type PageOffsets = std::iter::Empty<u64>;
fn page_offsets(&self) -> Self::PageOffsets {
std::iter::empty()
}
}
impl Representable for u32 {
fn alignment() -> Alignment {
Alignment::B4
}
fn onpage_size(&self) -> u16 {
4
}
unsafe fn skip(p: *mut u8) -> *mut u8 {
p.offset(4)
}
unsafe fn write_value(&self, p: *mut u8) {
*(p as *mut u32) = self.to_le()
}
unsafe fn read_value(p: *const u8) -> Self {
u32::from_le(*(p as *const u32))
}
unsafe fn cmp_value<T: LoadPage>(&self, _: &T, x: Self) -> std::cmp::Ordering {
self.cmp(&x)
}
type PageOffsets = std::iter::Empty<u64>;
fn page_offsets(&self) -> Self::PageOffsets {
std::iter::empty()
}
}
impl Representable for i64 {
fn alignment() -> Alignment {
Alignment::B8
}
fn onpage_size(&self) -> u16 {
8
}
unsafe fn skip(p: *mut u8) -> *mut u8 {
p.offset(8)
}
unsafe fn write_value(&self, p: *mut u8) {
*(p as *mut i64) = self.to_le()
}
unsafe fn read_value(p: *const u8) -> Self {
i64::from_le(*(p as *const i64))
}
unsafe fn cmp_value<T: LoadPage>(&self, _: &T, x: Self) -> std::cmp::Ordering {
self.cmp(&x)
}
type PageOffsets = std::iter::Empty<u64>;
fn page_offsets(&self) -> Self::PageOffsets {
std::iter::empty()
}
}
impl Representable for i32 {
fn alignment() -> Alignment {
Alignment::B4
}
fn onpage_size(&self) -> u16 {
4
}
unsafe fn skip(p: *mut u8) -> *mut u8 {
p.offset(8)
}
unsafe fn write_value(&self, p: *mut u8) {
debug!("write_value i64: {:?} {:?}", *self, p);
*(p as *mut i32) = self.to_le()
}
unsafe fn read_value(p: *const u8) -> Self {
i32::from_le(*(p as *const i32))
}
unsafe fn cmp_value<T: LoadPage>(&self, _: &T, x: Self) -> std::cmp::Ordering {
self.cmp(&x)
}
type PageOffsets = std::iter::Empty<u64>;
fn page_offsets(&self) -> Self::PageOffsets {
std::iter::empty()
}
}
impl Representable for () {
fn alignment() -> Alignment {
Alignment::B1
}
fn onpage_size(&self) -> u16 {
0
}
unsafe fn skip(p: *mut u8) -> *mut u8 {
p
}
unsafe fn write_value(&self, _: *mut u8) {}
unsafe fn read_value(_: *const u8) -> Self {}
unsafe fn cmp_value<T: LoadPage>(&self, _: &T, _: Self) -> std::cmp::Ordering {
std::cmp::Ordering::Equal
}
type PageOffsets = std::iter::Empty<u64>;
fn page_offsets(&self) -> Self::PageOffsets {
std::iter::empty()
}
}
impl<K: Representable, V: Representable> Representable for Db<K, V> {
fn alignment() -> Alignment {
Alignment::B8
}
fn onpage_size(&self) -> u16 {
8
}
unsafe fn skip(p: *mut u8) -> *mut u8 {
p.offset(8)
}
unsafe fn write_value(&self, p: *mut u8) {
debug!("write_value u64: {:?} {:?}", *self, p);
*(p as *mut u64) = self.0.to_le()
}
unsafe fn read_value(p: *const u8) -> Self {
Db(u64::from_le(*(p as *const u64)), std::marker::PhantomData)
}
unsafe fn cmp_value<T: LoadPage>(&self, _: &T, x: Db<K, V>) -> std::cmp::Ordering {
self.0.cmp(&x.0)
}
type PageOffsets = std::iter::Once<u64>;
fn page_offsets(&self) -> Self::PageOffsets {
std::iter::once(self.0)
}
fn drop_value<E: Borrow<Env<Exclusive>>, T, R: Rng>(
&self,
txn: &mut MutTxn<E, T>,
rng: &mut R,
) -> Result<(), Error> {
txn.drop(rng, self)
}
}
#[cfg(feature = "uuid")]
impl Representable for uuid::Uuid {
fn alignment() -> Alignment {
Alignment::B4
}
fn onpage_size(&self) -> u16 {
16
}
unsafe fn skip(p: *mut u8) -> *mut u8 {
p.offset(16)
}
unsafe fn write_value(&self, p: *mut u8) {
std::ptr::copy(self.as_bytes().as_ptr(), p, 16)
}
unsafe fn read_value(p: *const u8) -> Self {
let mut bytes = [0; 16];
std::ptr::copy(p, bytes.as_mut_ptr(), 16);
uuid::Uuid::from_bytes(bytes)
}
unsafe fn cmp_value<T: LoadPage>(&self, _: &T, x: Self) -> std::cmp::Ordering {
(*self).cmp(&x)
}
type PageOffsets = std::iter::Empty<u64>;
fn page_offsets(&self) -> Self::PageOffsets {
std::iter::empty()
}
}
#[cfg(feature = "git2")]
impl Representable for git2::Oid {
fn alignment() -> Alignment {
Alignment::B1
}
fn onpage_size(&self) -> u16 {
20
}
unsafe fn skip(p: *mut u8) -> *mut u8 {
p.offset(20)
}
unsafe fn write_value(&self, p: *mut u8) {
std::ptr::copy(self.as_bytes().as_ptr(), p, 20)
}
unsafe fn read_value(p: *const u8) -> Self {
let mut bytes = [0; 20];
std::ptr::copy(p, bytes.as_mut_ptr(), 20);
git2::Oid::from_bytes(&bytes).unwrap()
}
unsafe fn cmp_value<T: LoadPage>(&self, _: &T, x: Self) -> std::cmp::Ordering {
(*self).cmp(&x)
}
type PageOffsets = std::iter::Empty<u64>;
fn page_offsets(&self) -> Self::PageOffsets {
std::iter::empty()
}
}
#[doc(hidden)]
#[derive(Debug, Copy, Clone)]
pub struct PageCursor {
page: u64,
cursor: SkipCursor,
}
impl std::ops::Index<usize> for PageCursor {
type Output = u16;
fn index(&self, i: usize) -> &u16 {
self.cursor.levels.index(i)
}
}
impl std::ops::IndexMut<usize> for PageCursor {
fn index_mut(&mut self, i: usize) -> &mut u16 {
self.cursor.levels.index_mut(i)
}
}
impl PageCursor {
fn new() -> Self {
PageCursor {
page: 0,
cursor: SkipCursor::new(),
}
}
}
pub(crate) const N_CURSORS: usize = 30;
#[derive(Debug, Clone)]
pub struct Cursor {
stack: [PageCursor; N_CURSORS],
first_rc_level: usize,
pointer: usize,
}
impl Cursor {
pub(crate) fn new() -> Self {
Cursor {
stack: [PageCursor::new(); N_CURSORS],
first_rc_level: N_CURSORS,
pointer: 1,
}
}
}
impl std::ops::Index<usize> for Cursor {
type Output = PageCursor;
fn index(&self, i: usize) -> &PageCursor {
self.stack.index(i)
}
}
impl std::ops::IndexMut<usize> for Cursor {
fn index_mut(&mut self, i: usize) -> &mut PageCursor {
self.stack.index_mut(i)
}
}
impl Cursor {
fn current_mut(&mut self) -> &mut PageCursor {
&mut self.stack[self.pointer]
}
fn current(&self) -> &PageCursor {
&self.stack[self.pointer]
}
fn set<T: LoadPage + Transaction, K: Representable, V: Representable>(
&mut self,
txn: &T,
db: &Db<K, V>,
k: Option<(K, Option<V>)>,
) -> Result<bool, CRCError> {
debug!("Cursor::set {:?}", k);
debug!("db = {:?}", db.0);
self.stack[1].page = db.0;
self.pointer = 1;
let mut last_matching_page = 0;
loop {
debug!(
"self.stack: {:?} {:?}",
&self.stack[..self.pointer + 1],
self.pointer
);
let page = txn.load_page(self.stack[self.pointer].page)?;
if self.first_rc_level >= N_CURSORS && rc(txn, self.stack[self.pointer].page)? >= 2 {
debug!(
"first_rc_level: {:?} {:?}",
self.pointer, self.stack[self.pointer].page
);
self.first_rc_level = self.pointer
}
if let Some((k, v)) = k {
if skiplist::set_cursor(txn, &page, &mut self.stack[self.pointer].cursor, k, v)
.is_some()
{
debug!("found on page {:?}", page.page_offset());
if v.is_some() {
debug!("found v");
return Ok(true);
} else {
last_matching_page = self.pointer
}
}
}
let next_page = skiplist::right_child(&page, self.stack[self.pointer][0]);
debug!(
"next_page = {:?}, cursors: {:?}",
next_page, self.stack[self.pointer].cursor
);
if next_page > 0 {
self.pointer += 1;
self.stack[self.pointer].page = next_page;
} else {
break;
}
}
if last_matching_page > 0 {
debug!("last_matching_page: {:?}", last_matching_page);
debug!("cursors: {:?}", &self.stack[..self.pointer + 1]);
self.pointer = last_matching_page;
Ok(true)
} else {
debug!("not found");
Ok(false)
}
}
}
pub unsafe fn next<T: Transaction, K: Representable, V: Representable>(
txn: &T,
cursor: &mut Cursor,
) -> Result<Option<(K, V)>, CRCError> {
loop {
if cursor.pointer == 0 {
debug!("next, pointer = 0");
return Ok(None);
} else {
let page = cursor[cursor.pointer].page;
debug!("next(), pointer: {:?}", cursor.pointer);
debug!(target:"iter", "PAGE: {:?}", page);
let page = txn.load_page(page)?;
let pos = cursor[cursor.pointer][0];
debug!("pos = {:?} {:?}", pos, skiplist::SKIPLIST_ROOT);
if pos == skiplist::SKIPLIST_ROOT {
let right_child = skiplist::right_child(&page, pos);
debug!("right_child = {:?}", right_child);
if right_child != 0 {
cursor.pointer += 1;
let p = cursor.pointer;
cursor[p].page = right_child;
skiplist::set_cursor_root(&mut cursor[p].cursor);
} else {
let p = cursor.pointer;
if !skiplist::move_cursor_forward(&page, &mut cursor[p].cursor) {
cursor[p][0] = skiplist::NIL
}
}
} else if pos == skiplist::NIL {
debug!("POP!");
if cursor.pointer > 1 {
cursor.pointer -= 1;
} else {
return Ok(None);
}
let p = cursor.pointer;
let page = txn.load_page(cursor[p].page)?;
if !skiplist::move_cursor_forward(&page, &mut cursor[p].cursor) {
cursor[p][0] = skiplist::NIL
}
} else {
let (cur_key, cur_value) = skiplist::read_key_value::<_, K, V>(&page, pos);
debug!("key = {:?}, value = {:?}", cur_key, cur_value);
let right_child = skiplist::right_child(&page, pos);
if right_child != 0 {
cursor.pointer += 1;
let p = cursor.pointer;
cursor[p].page = right_child;
skiplist::set_cursor_root(&mut cursor[p].cursor);
} else {
let p = cursor.pointer;
if !skiplist::move_cursor_forward(&page, &mut cursor[p].cursor) {
cursor[p][0] = skiplist::NIL
}
}
return Ok(Some((cur_key, cur_value)));
}
}
}
}
pub unsafe fn cur<T: Transaction, K: Representable, V: Representable>(
txn: &T,
cursor: &Cursor,
) -> Result<Option<(K, V)>, CRCError> {
if cursor.pointer == 0 {
Ok(None)
} else {
let page = cursor[cursor.pointer].page;
debug!("cur(), pointer: {:?}", cursor.pointer);
debug!("PAGE: {:?}", page);
let page = txn.load_page(page)?;
let pos = cursor[cursor.pointer][0];
debug!("pos = {:?}", pos);
if pos == skiplist::SKIPLIST_ROOT {
Ok(None)
} else {
let (cur_key, cur_value) = skiplist::read_key_value::<_, K, V>(&page, pos);
Ok(Some((cur_key, cur_value)))
}
}
}
pub unsafe fn prev<T: Transaction, K: Representable, V: Representable>(
txn: &T,
cursor: &mut Cursor,
) -> Result<Option<(K, V)>, CRCError> {
loop {
if cursor.pointer == 0 {
return Ok(None);
} else {
let page = cursor[cursor.pointer].page;
debug!("prev(), pointer: {:?}", cursor.pointer);
debug!("PAGE: {:?}", page);
let page = txn.load_page(page)?;
let pos = cursor[cursor.pointer][0];
debug!("pos = {:?}", pos);
if pos == skiplist::SKIPLIST_ROOT {
if cursor.pointer > 1 {
cursor.pointer -= 1
} else {
return Ok(None);
}
} else {
let (cur_key, cur_value) = skiplist::read_key_value::<_, K, V>(&page, pos);
let right_child = skiplist::right_child(&page, pos);
if right_child != 0 {
let p = cursor.pointer;
skiplist::move_cursor_backward(&page, &mut cursor[p].cursor);
let mut right_child = skiplist::right_child(&page, cursor[p][0]);
while right_child != 0 {
cursor.pointer += 1;
let p = cursor.pointer;
cursor[p].page = right_child;
let page = txn.load_page(right_child)?;
skiplist::set_cursor_last(&page, &mut cursor[p].cursor);
right_child = skiplist::right_child(&page, cursor[p][0])
}
} else {
let p = cursor.pointer;
skiplist::move_cursor_backward(&page, &mut cursor[p].cursor);
}
return Ok(Some((cur_key, cur_value)));
}
}
}
}
#[derive(Clone)]
pub struct DbIterator<'a, T: Transaction + 'a, K, V> {
txn: &'a T,
stack: Cursor,
marker: std::marker::PhantomData<(K, V)>,
}
impl<'a, T: Transaction + 'a, K: Representable, V: Representable> Iterator
for DbIterator<'a, T, K, V>
{
type Item = Result<(K, V), CRCError>;
fn next(&mut self) -> Option<Self::Item> {
unsafe {
match next(self.txn, &mut self.stack) {
Ok(Some(x)) => Some(Ok(x)),
Ok(None) => None,
Err(e) => Some(Err(e)),
}
}
}
}
impl<'a, T: Transaction + 'a, K: Representable, V: Representable> DbIterator<'a, T, K, V> {
pub fn prev(&mut self) -> Option<Result<(K, V), CRCError>> {
unsafe {
match prev(self.txn, &mut self.stack) {
Ok(Some(x)) => Some(Ok(x)),
Ok(None) => None,
Err(e) => Some(Err(e)),
}
}
}
}
#[derive(Clone)]
pub struct RevDbIterator<'a, T: Transaction + 'a, K, V>(DbIterator<'a, T, K, V>);
impl<'a, T: Transaction + 'a, K: Representable, V: Representable> Iterator
for RevDbIterator<'a, T, K, V>
{
type Item = Result<(K, V), CRCError>;
fn next(&mut self) -> Option<Self::Item> {
self.0.prev()
}
}
mod put;
pub use put::*;
mod del;
pub use del::*;
const RC_ROOT: usize = 0;
#[derive(Debug)]
struct PageItem<K, V> {
ptr: *const u8,
kv: Option<(K, V)>,
right: u64,
incr_right_rc: bool,
incr_kv_rc: bool,
}
impl<E: Borrow<Env<Exclusive>>, T> MutTxn<E, T> {
pub fn create_db<K: Representable, V: Representable>(&mut self) -> Result<Db<K, V>, Error> {
debug!("create_db");
let mut db = self.alloc_page()?;
db.init_skiplist_page();
Ok(Db(db.offset, std::marker::PhantomData))
}
pub fn set_root<K: Representable, V: Representable>(&mut self, root: usize, value: Db<K, V>) {
unsafe { self.set_root_raw(root, value.0) }
}
#[doc(hidden)]
pub unsafe fn set_root_raw(&mut self, root: usize, value: u64) {
assert!(root <= (PAGE_SIZE as usize - ZERO_HEADER as usize - transaction::CRC_SIZE as usize) >> 3);
debug!("set_root {:?} {:?}", root, value);
self.set_root_(1 + root, value)
}
pub fn fork<R: Rng, K: Representable, V: Representable>(
&mut self,
rng: &mut R,
db: &Db<K, V>,
) -> Result<Db<K, V>, Error> {
debug!("FORK ! {:?}", db.0);
self.incr_rc(rng, db.0)?;
Ok(Db(db.0, std::marker::PhantomData))
}
pub fn drop<R: Rng, K: Representable, V: Representable>(
&mut self,
rng: &mut R,
db: &Db<K, V>,
) -> Result<(), Error> {
debug!(target: "sanakirja::drop", "DROP ! {:?}", db.0);
let mut stack = vec![db.0];
while let Some(page) = stack.pop() {
if page == 0 {
continue;
}
debug!(target: "sanakirja::drop", "page = {:?}", page);
let rc = rc(self, page)?;
if rc > 1 {
self.set_rc(rng, page, rc - 1)?
} else {
let page_ = self.load_cow_page(page)?;
for (_, k, r) in skiplist::iter_all::<_, K, V>(&page_) {
if let Some((k, v)) = k {
k.drop_value(self, rng)?;
v.drop_value(self, rng)?;
}
if page > 0 {
stack.push(r)
}
}
if rc == 1 {
self.remove_rc(rng, page)?;
}
debug!(target: "sanakirja::drop", "freeing {:?}", page);
unsafe { self.free_page(page) }
}
}
debug!(target: "sanakirja::drop", "/DROP {:?}", db.0);
Ok(())
}
fn spread_on_one_page<
'a,
R: Rng,
K: Representable,
V: Representable,
I: Iterator<Item = PageItem<K, V>>,
>(
&mut self,
rng: &mut R,
it: I,
) -> Result<u64, Error> {
debug!("spread_on_one_page");
let mut new_a = self.alloc_page()?;
debug!("new_a: {:?}", new_a);
new_a.init_skiplist_page();
let mut new_a_cursor = SkipCursor::new();
for item in it {
debug!("spread_on_one_page: {:?}", skiplist::occupied(&new_a));
debug!("incr_r: {:?} {:?}", item.incr_right_rc, item.right);
if item.incr_right_rc && item.right != 0 {
self.incr_rc(rng, item.right)?;
}
if let Some((k, v)) = item.kv {
if item.incr_kv_rc {
for offset in k.page_offsets().chain(v.page_offsets()) {
self.incr_rc(rng, offset)?
}
}
skiplist::skiplist_insert_after_cursor(
&mut new_a,
rng,
&mut new_a_cursor,
k,
v,
item.right,
)
} else {
skiplist::set_right_child(&mut new_a, new_a_cursor.levels[0], item.right);
}
}
Ok(new_a.page_offset())
}
fn spread_on_two_pages<
'a,
R: Rng,
K: Representable,
V: Representable,
I: Iterator<Item = PageItem<K, V>>,
>(
&mut self,
rng: &mut R,
mut it: I,
total_it_size: u16,
) -> Result<(u64, u64, K, V), Error> {
debug!("spread on two pages");
let mut new_a = self.alloc_page()?;
new_a.init_skiplist_page();
let mut new_b = self.alloc_page()?;
new_b.init_skiplist_page();
let mut new_a_cursor = SkipCursor::new();
let mut new_b_cursor = SkipCursor::new();
let mut middle = None;
{
for item in &mut it {
debug!("spread_on_two_pages: A, {:?}", item.kv);
if item.incr_right_rc && item.right != 0 {
self.incr_rc(rng, item.right)?;
}
debug!("Spread A");
if let Some((k, v)) = item.kv {
if item.incr_kv_rc {
for offset in k.page_offsets().chain(v.page_offsets()) {
self.incr_rc(rng, offset)?
}
}
let rec_size = skiplist::record_size(k, v);
debug!(
"{:?} {:?} {:?}",
skiplist::occupied(&new_a),
total_it_size,
rec_size
);
if skiplist::occupied(&new_a) >= (total_it_size - rec_size) / 2 {
skiplist::set_right_child(&mut new_b, skiplist::SKIPLIST_ROOT, item.right);
middle = Some((k, v));
break;
} else {
skiplist::skiplist_insert_after_cursor(
&mut new_a,
rng,
&mut new_a_cursor,
k,
v,
item.right,
)
}
} else {
skiplist::set_right_child(&mut new_a, new_a_cursor.levels[0], item.right)
}
}
for item in &mut it {
debug!("spread_on_two_pages: A, {:?}", item.kv);
if item.incr_right_rc && item.right != 0 {
self.incr_rc(rng, item.right)?;
}
debug!("Spread B");
if let Some((k, v)) = item.kv {
if item.incr_kv_rc {
for offset in k.page_offsets().chain(v.page_offsets()) {
self.incr_rc(rng, offset)?
}
}
skiplist::skiplist_insert_after_cursor(
&mut new_b,
rng,
&mut new_b_cursor,
k,
v,
item.right,
)
} else {
skiplist::set_right_child(&mut new_b, new_b_cursor.levels[0], item.right)
}
}
}
let (k, v) = middle.unwrap();
Ok((new_a.page_offset(), new_b.page_offset(), k, v))
}
fn split_root<R: Rng, K: Representable, V: Representable>(
&mut self,
rng: &mut R,
cursor: &mut Cursor,
left: u64,
right: u64,
key: K,
value: V,
) -> Result<u64, Error> {
debug!("split root");
let mut new_root = self.alloc_page()?;
debug!(target:"stack", "split_root {:?} -> {:?} {:?}", new_root, left, right);
new_root.init_skiplist_page();
cursor.stack[0].page = new_root.offset;
skiplist::set_right_child(&mut new_root, skiplist::SKIPLIST_ROOT, left);
skiplist::skiplist_insert_after_cursor(
&mut new_root,
rng,
&mut cursor.current_mut().cursor,
key,
value,
right,
);
Ok(new_root.page_offset())
}
fn set_rc<R: Rng>(&mut self, rng: &mut R, page: u64, rc: u64) -> Result<(), Error> {
debug!("set_rc");
let mut rc_root: Db<u64, u64> = Db(self.root_(RC_ROOT), std::marker::PhantomData);
if rc_root.0 == 0 && rc > 1 {
rc_root = self.create_db()?
};
debug!("====== BEGIN RC: RC_ROOT = {:?}", rc_root.0);
if rc_root.0 != 0 {
self.del(rng, &mut rc_root, page, None)?;
if rc > 1 {
self.put(rng, &mut rc_root, page, rc)?;
}
self.set_root_(RC_ROOT, rc_root.0);
}
debug!("====== END RC");
Ok(())
}
fn remove_rc<R: Rng>(&mut self, rng: &mut R, page: u64) -> Result<(), Error> {
let mut rc_root: Db<u64, u64> = Db(self.root_(RC_ROOT), std::marker::PhantomData);
if rc_root.0 != 0 {
debug!("====== BEGIN RC: RC_ROOT = {:?}", rc_root.0);
self.del(rng, &mut rc_root, page, None)?;
self.set_root_(RC_ROOT, rc_root.0);
debug!("====== END RC");
}
Ok(())
}
fn incr_rc<R: Rng>(&mut self, rng: &mut R, page: u64) -> Result<(), Error> {
if page > 0 {
let rc = std::cmp::max(1, rc(self, page)?);
self.set_rc(rng, page, rc + 1)
} else {
Ok(())
}
}
}
pub trait Transaction: LoadPage + Sized {
fn iter<'a, K: Representable, V: Representable>(
&'a self,
db: &'a Db<K, V>,
key: Option<(K, Option<V>)>,
) -> Result<DbIterator<'a, Self, K, V>, CRCError> {
let (stack, _) = self.set_cursors(db, key)?;
let mut c = DbIterator {
txn: self,
stack: stack,
marker: std::marker::PhantomData,
};
if key.is_some() {
let p = c.stack.pointer;
let page = self.load_page(c.stack[p].page)?;
let pos = c.stack[p][0];
c.stack[p][0] = skiplist::next_at_level(&page, pos, 0);
}
Ok(c)
}
fn rev_iter<'a, K: Representable, V: Representable>(
&'a self,
db: &'a Db<K, V>,
key: Option<(K, Option<V>)>,
) -> Result<RevDbIterator<'a, Self, K, V>, CRCError> {
let stack = if let Some(key) = key {
self.set_cursors(db, Some(key))?.0
} else {
self.set_cursors_last(db)?
};
Ok(RevDbIterator(DbIterator {
txn: self,
stack: stack,
marker: std::marker::PhantomData,
}))
}
fn set_cursors<K: Representable, V: Representable>(
&self,
root: &Db<K, V>,
key: Option<(K, Option<V>)>,
) -> Result<(Cursor, bool), CRCError> {
let mut stack = Cursor::new();
let present = stack.set(self, &root, key)?;
Ok((stack, present))
}
fn set_cursors_last<K: Representable, V: Representable>(
&self,
root: &Db<K, V>,
) -> Result<Cursor, CRCError> {
let mut stack = Cursor::new();
stack[1].page = root.0;
stack.pointer = 1;
let p = stack.pointer;
let page = self.load_page(stack[p].page)?;
skiplist::set_cursor_last(&page, &mut stack[p].cursor);
let mut right_child = skiplist::right_child(&page, stack[p][0]);
debug!("rev_iter: {:?} {:?}", stack[p].page, right_child);
while right_child != 0 {
debug!("right_child: {:?}", right_child);
stack.pointer += 1;
let p = stack.pointer;
stack[p].page = right_child;
let page = self.load_page(stack[p].page)?;
skiplist::set_cursor_last(&page, &mut stack[p].cursor);
right_child = skiplist::right_child(&page, stack[p][0])
}
Ok(stack)
}
fn root<K: Representable, V: Representable>(&self, root: usize) -> Option<Db<K, V>> {
debug!("root {:?}", root);
let db = self.root_(1 + root);
if db > 0 {
Some(Db(db, std::marker::PhantomData))
} else {
None
}
}
fn get<'a, K: Representable, V: Representable>(
&'a self,
root: &Db<K, V>,
key: K,
value: Option<V>,
) -> Result<Option<V>, CRCError> {
debug!("get from {:?}", root);
let mut page_off = root.0;
loop {
debug!("load_page {:?}", page_off);
let page = self.load_page(page_off)?;
let mut cursor = SkipCursor::new();
if let Some(val) = skiplist::set_cursor(self, &page, &mut cursor, key, value) {
return Ok(Some(val));
} else {
let next_page = skiplist::right_child(&page, cursor.levels[0]);
if next_page == 0 {
return Ok(None);
} else {
page_off = next_page
}
}
}
}
}
fn rc<T: Transaction>(t: &T, page: u64) -> Result<u64, CRCError> {
let rc_root = t.root_(RC_ROOT);
debug!("rc_root = {:?}", rc_root);
if rc_root == 0 {
Ok(0)
} else {
let db: Db<u64, u64> = Db(rc_root, std::marker::PhantomData);
Ok(t.get(&db, page, None)?.unwrap_or(0))
}
}
impl<L, E: Borrow<Env<L>>> Transaction for Txn<L, E> {}
impl<E: Borrow<Env<Exclusive>>, T> Transaction for MutTxn<E, T> {}
const PAGE_SIZE: u32 = 4096;
const PAGE_SIZE_U16: u16 = 4096;
const PAGE_SIZE_I16: i16 = 4096;
#[doc(hidden)]
pub trait PageT: Sized {
fn page_offset(&self) -> u64;
fn data(&self) -> *mut u8;
fn offset(&self, off: isize) -> *mut u8 {
unsafe {
assert!(off < 4096);
let p: *mut u8 = self.data();
p.offset(off)
}
}
}
#[doc(hidden)]
pub const INDIRECT_BIT: u16 = 0x8000;
impl PageT for MutPage {
fn page_offset(&self) -> u64 {
self.offset
}
fn data(&self) -> *mut u8 {
self.data
}
}
impl PageT for Page {
fn page_offset(&self) -> u64 {
self.offset
}
fn data(&self) -> *mut u8 {
self.data as *mut u8
}
}
impl PageT for Cow {
fn page_offset(&self) -> u64 {
match self {
&Cow::Page(ref p) => p.page_offset(),
&Cow::MutPage(ref p) => p.page_offset(),
}
}
fn data(&self) -> *mut u8 {
match self {
&Cow::Page(ref p) => p.data(),
&Cow::MutPage(ref p) => p.data(),
}
}
}
#[doc(hidden)]
pub const MAX_RECORD_SIZE: u16 = (PAGE_SIZE as u16 - BINDING_HEADER_SIZE) >> 2;
#[doc(hidden)]
pub const BINDING_HEADER_SIZE: u16 = 16;
#[cfg(test)]
mod tests;
use std::collections::HashSet;
use std::fs::File;
use std::io::{BufWriter, Write};
use std::path::Path;
pub fn debug<P: AsRef<Path>, T: LoadPage + Transaction, K: Representable, V: Representable>(
t: &T,
db: &[&Db<K, V>],
p: P,
recurse: bool,
) {
let f = File::create(p.as_ref()).unwrap();
let mut buf = BufWriter::new(f);
writeln!(&mut buf, "digraph{{").unwrap();
let mut h = HashSet::new();
for db in db {
let page = t.load_page(db.0).unwrap();
print_page::<T, K, V>(t, &mut h, &mut buf, &page, recurse);
}
writeln!(&mut buf, "}}").unwrap();
}
pub fn debug_<P: AsRef<Path>, T: LoadPage + Transaction>(
t: &T,
db: &[UnsafeDb],
p: P,
recurse: bool,
) {
let f = File::create(p.as_ref()).unwrap();
let mut buf = BufWriter::new(f);
writeln!(&mut buf, "digraph{{").unwrap();
let mut h = HashSet::new();
for db in db {
let page = t.load_page(db.0).unwrap();
print_page::<T, (), ()>(t, &mut h, &mut buf, &page, recurse);
}
writeln!(&mut buf, "}}").unwrap();
}
fn print_page<T: LoadPage + Transaction, K: Representable, V: Representable>(
txn: &T,
pages: &mut HashSet<u64>,
buf: &mut BufWriter<File>,
p: &Page,
print_children: bool,
) {
if !pages.contains(&p.offset) {
pages.insert(p.offset);
writeln!(
buf,
"subgraph cluster{} {{\nlabel=\"Page {}, first_free {}, occupied {}, rc \
{}\";\ncolor=black;",
p.offset,
p.offset,
skiplist::first_free(p),
skiplist::occupied(p),
rc(txn, p.page_offset()).unwrap()
)
.unwrap();
let mut h = Vec::new();
let mut edges = Vec::new();
let mut hh = HashSet::new();
skiplist::print_skiplist_simple::<T, K, V>(txn, &mut hh, buf, &mut edges, &mut h, p);
writeln!(buf, "}}").unwrap();
for p in edges.iter() {
writeln!(buf, "{}", p).unwrap()
}
if print_children {
for p in h.iter() {
print_page::<T, K, V>(txn, pages, buf, p, print_children)
}
}
}
}