OFINGD26ZWCRDVVDI2ZIBLMHXKEMJA6MRNLANJYUHQPIJLPA7J2AC
T7QB6QEPWBXAU3RL7LE4GRDWWNQ65ZU2YNNTWBYLORJOABAQFEZQC
EYNN7RLSFVBWDLRTLNNFUAF46Q6OX3BR5SUEJIOOHBSNP7FVBXGAC
OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC
W26CFMAQOXMUK4ZOJMAN4SMBXMWFQHO7HCTEVW73FQSRMJZFGJIQC
ONES3V466GLO5CXKRF5ENK7VFOQPWM3YXLVRGWB56V5SH3W7XNBQC
UUUVNC4DWEEL7WV5IRPKPZ6HZMYCPA53XM7LJWICUD4E6GN37IRQC
FMN7X4J24EYPOJNBUWM4NKGWSJTRV2DHCIBMPV2AXLZVVAMNOBKQC
WS4ZQM4RMIHZ6XZKSDQJGHN5SSSWFL4H236USOPUA33S6RC53RFAC
H3FVSQIQGFCFKCPXVOSFHP4OSUOBBURJESCZNGQTNDAAD3WQSBEQC
6UVFCERMGSGNRWCVC3GWO5HWV6MSWE433DXBJVC7KRPP6LLJLCSQC
KX3WVNZW5KHVEH6EOQTZ4RBEFFJ3SGF5I467X3JWZ74PURRK4HVAC
QEUTVAZ4F4EJXRDMWDMYXF6XEDMX7YPVG4IIXEKPIR3K54E5W5OAC
EHJFNMB2R4MYG6ZSHHEENRFCSPFVWKVHLD5DXAE5HXUGXP5ZVHKQC
EAAYH6BQWDK52EC5RG3BEZQU3FJPN5RRRN4U5KDKDVPKXBVJMNDAC
DV4A2LR7Q5LAEGAQHLO34PZCHGJUHPAMRZFGT7GUFNKVQKPJNOYQC
OTWDDJE7TTE73D6BGF4ZN6BH2NFUFLPME2VJ3CPALH463UGWLEIQC
APPY2E7M5NHNC6MFYXSVEKJVAILK7YAZVTVE3W75EK2JNFVS3XBQC
YWFYZNLZ5JHLIFVBRKZK4TSWVPROUPRG77ZB5M7UHT2OKPL4ZSRQC
G4JEQLLX6Q7VVFVAEJZAVQXX33MQ36CSCYSMJ5NQM5VZ76DXKU6QC
KMT3MF5NLEQIPZLHCRYDGQ5EA46HJCG3C2ANEPMZGKGHDK77ADPAC
X3QVVQIS7B7L3XYZAWL3OOBUXOJ6RMOKQ45YMLLGAHYPEEKZ45ZAC
PXF3R6SVXJXN2NMLMWNY5OFV5QYVE2VZTLGIZDZVK5ZVLFTVSSWQC
UAQX27N4PI4LHEW6LSHJETIE5MV7JTEMPLTJFYUBMYVPC43H7VOAC
6DMPXOAT5GQ3BQQOMUZN2GMBQPRA4IB7CCPHTQTIFGO3KWWAKF3QC
S4V4QZ5CF5LUDYWNR2UMWH6CHJDJ5FPGAZCQYM5GY7FJMJV4NN4QC
6DCQHIFPEH4GZKSRRS32GMKDRPZH4MTCGOUEI7YEUVKWENBF3JWAC
AOX2XQISHGWNNAFBYRN44Q6AWG7H5DPBK5YMFHK42HQNZ2TMHEJQC
) -> (&'a K, &'a V, u64) {
if c.is_leaf {
let off =
{ u16::from_le(*(page.data.as_ptr().add(HDR + c.cur * 2) as *const u16)) as usize };
let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off as usize));
(
K::from_raw_ptr(txn, k as *const u8),
V::from_raw_ptr(txn, v as *const u8),
0,
)
) -> Option<(&'a K, &'a V, u64)> {
if c.cur < 0 || c.cur >= c.total as isize {
None
} else if c.is_leaf {
unsafe {
let off =
{ u16::from_le(*(page.data.as_ptr().add(HDR + c.cur as usize * 2) as *const u16)) as usize };
let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off));
Some((
K::from_raw_ptr(txn, k as *const u8),
V::from_raw_ptr(txn, v as *const u8),
0,
))
}
let off = u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur));
let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add((off & 0xfff) as usize));
(
K::from_raw_ptr(txn, k as *const u8),
V::from_raw_ptr(txn, v as *const u8),
off & !0xfff,
)
unsafe {
let off = u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).offset(c.cur));
let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add((off & 0xfff) as usize));
Some((
K::from_raw_ptr(txn, k as *const u8),
V::from_raw_ptr(txn, v as *const u8),
off & !0xfff,
))
}
cur: usize,
total: usize,
is_leaf: bool,
pub(in super) cur: isize,
pub(in super) total: usize,
pub(in super) is_leaf: bool,
}
impl Cursor {
pub(in super) fn new(p: crate::Page, cur: isize) -> Cursor {
let hdr = header(p);
assert!(cur < hdr.n() as isize);
Cursor {
cur,
total: hdr.n() as usize,
is_leaf: hdr.is_leaf(),
}
}
pub(in super) fn after(p: crate::Page) -> Cursor {
let hdr = header(p);
let total = hdr.n();
Cursor {
cur: total as isize,
total: total as usize,
is_leaf: hdr.is_leaf(),
}
}
pub(in super) fn last(p: crate::Page) -> Cursor {
let hdr = header(p);
let total = hdr.n();
Cursor {
cur: (total - 1) as isize,
total: total as usize,
is_leaf: hdr.is_leaf(),
}
}
let lc = <Page<K, V>>::last_cursor(m.other.as_page());
let (k0, v0, r0) = unsafe { <Page<K, V>>::unchecked_current(txn, m.other.as_page(), &lc) };
let lc = super::Cursor::last(m.other.as_page());
let (k0, v0, r0) = <Page<K, V>>::current(txn, m.other.as_page(), &lc).unwrap();
let ptr = p.add(HDR + c.cur * 8) as *mut u64;
core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - c.cur);
let ptr = p.add(HDR + c.cur as usize * 8) as *mut u64;
core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - c.cur as usize);
fn first_cursor(p: crate::Page) -> Self::Cursor {
let hdr = header(p);
Cursor {
cur: 0,
total: hdr.n() as usize,
is_leaf: hdr.is_leaf(),
}
fn cursor_before(p: crate::Page) -> Self::Cursor {
Cursor::new(p, -1)
fn last_cursor(p: crate::Page) -> Self::Cursor {
let hdr = header(p);
let total = hdr.n() as usize;
Cursor {
cur: total - 1,
total,
is_leaf: hdr.is_leaf(),
}
fn cursor_after(p: crate::Page) -> Self::Cursor {
Cursor::after(p)
let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off as usize));
(
K::from_raw_ptr(txn, k as *const u8),
V::from_raw_ptr(txn, v as *const u8),
0,
)
debug!("current {:?}", off);
unsafe {
let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off as usize));
debug!("k {:?}", K::from_raw_ptr(txn, k as *const u8));
Some((
K::from_raw_ptr(txn, k as *const u8),
V::from_raw_ptr(txn, v as *const u8),
0,
))
}
let off = u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur));
let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add((off & 0xfff) as usize));
(
K::from_raw_ptr(txn, k as *const u8),
V::from_raw_ptr(txn, v as *const u8),
off & !0xfff,
)
unsafe {
let off = u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur as usize));
let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add((off & 0xfff) as usize));
Some((
K::from_raw_ptr(txn, k as *const u8),
V::from_raw_ptr(txn, v as *const u8),
off & !0xfff,
))
}
let lc = <Page<K, V>>::last_cursor(m.other.as_page());
let (k0, v0, r0) = unsafe { <Page<K, V>>::unchecked_current(txn, m.other.as_page(), &lc) };
let lc = Cursor::last(m.other.as_page());
let (k0, v0, r0) = <Page<K, V>>::current(txn, m.other.as_page(), &lc).unwrap();
fn first_cursor(p: Page) -> Self::Cursor;
fn last_cursor(p: Page) -> Self::Cursor;
/// Returns a cursor set before the first element of the page
/// (i.e. set to -1).
fn cursor_before(p: Page) -> Self::Cursor;
fn cursor_first(p: Page) -> Self::Cursor {
let mut c = Self::cursor_before(p);
debug!("cursor_first {:?}", c);
Self::move_next(p, &mut c);
debug!("cursor_first {:?}", c);
c
}
/// Returns a cursor set after the last element of the page
/// (i.e. to element n)
fn cursor_after(p: Page) -> Self::Cursor;
fn cursor_last(p: Page) -> Self::Cursor {
let mut c = Self::cursor_after(p);
Self::move_prev(p, &mut c);
c
}
) -> Option<(&'a K, &'a V, u64)> {
if Self::is_empty(p, c) {
None
} else {
unsafe { Some(Self::unchecked_current(txn, p, c)) }
}
}
) -> Option<(&'a K, &'a V, u64)>;
let (k, v, _) = P::prev(txn, curs.page.as_page(), c).unwrap();
let l = P::left_child(curs.page.as_page(), c);
let (k, v, _) = P::prev(txn, curs.page.as_page(), &mut curs.cursor).unwrap();
let l = P::left_child(curs.page.as_page(), &curs.cursor);
if current.cursor.is_none() {
current.cursor = Some(P::last_cursor(current.page.as_page()));
}
let cursor = current.cursor.as_mut().unwrap();
let (k, v, r) = unsafe { P::unchecked_current(txn, current.page.as_page(), cursor) };
debug!("cursor = {:?}", current.cursor);
let (k, v, r) = P::current(txn, current.page.as_page(), &mut current.cursor).unwrap();
if let Some(ref mut c) = current.cursor {
// We're inside the page, and have already
// processed the left child of the current page
// cursor.
if let Some((k, v, r)) = P::next(txn, current.page.as_page(), c) {
if r > 0 {
self.push(PageCursor {
page: txn.load_page(r)?,
cursor: None,
})
}
return Ok(Some((&*k, &*v)));
} else if self.pointer > 0 {
self.pop();
} else {
return Ok(None);
if P::is_init(current.page.as_page(), ¤t.cursor) {
P::move_next(current.page.as_page(), &mut current.cursor);
let left = P::left_child(current.page.as_page(), ¤t.cursor);
// Then visit the right child (if any), i.e. push.
if left != 0 {
let page = txn.load_page(left)?;
self.push(PageCursor {
page,
cursor: P::cursor_before(page.as_page()),
})
}
} else if let Some((k, v, r)) = P::current(txn, current.page.as_page(), ¤t.cursor) {
P::move_next(current.page.as_page(), &mut current.cursor);
if r > 0 {
let page = txn.load_page(r)?;
self.push(PageCursor {
page,
cursor: P::cursor_before(page.as_page()),
})
current.cursor = Some(P::first_cursor(current.page.as_page()));
// First element of a page (not a binding).
let cursor = current.cursor.as_ref().unwrap();
let left = P::left_child(current.page.as_page(), cursor);
// Then visit the right child (if any), i.e. push.
if left != 0 {
return Ok(None);
}
}
}
pub fn prev<T: LoadPage>(&mut self, txn: &T) -> Result<Option<(&'a K, &'a V)>, T::Error> {
loop {
let current = unsafe { &mut *self.stack[self.pointer].as_mut_ptr() };
if P::is_empty(current.page.as_page(), ¤t.cursor) {
P::move_prev(current.page.as_page(), &mut current.cursor);
let right = P::right_child(current.page.as_page(), ¤t.cursor);
if right != 0 {
let page = txn.load_page(right)?;
page: txn.load_page(left)?,
cursor: None,
page,
cursor: P::cursor_after(page.as_page()),
})
}
} else if let Some((k, v, _)) = P::current(txn, current.page.as_page(), ¤t.cursor) {
P::move_prev(current.page.as_page(), &mut current.cursor);
let l = P::right_child(current.page.as_page(), ¤t.cursor);
if l > 0 {
let page = txn.load_page(l)?;
self.push(PageCursor {
page,
cursor: P::cursor_after(page.as_page()),
pub trait RootDb: Sized + sanakirja_core::LoadPage {
fn root_db<K: Representable, V: Representable>(
pub trait RootDb {
fn root_db<
K: Representable + ?Sized,
V: Representable + ?Sized,
P: crate::btree::BTreePage<K, V>,
>(
&self,
n: usize,
) -> Option<sanakirja_core::btree::Db_<K, V, P>>;
}
impl<E: Borrow<Env>> RootDb for Txn<E> {
fn root_db<
K: Representable + ?Sized,
V: Representable + ?Sized,
P: crate::btree::BTreePage<K, V>,
>(
) -> Result<Option<sanakirja_core::btree::Db<K, V>>, Self::Error>;
) -> Option<sanakirja_core::btree::Db_<K, V, P>> {
unsafe {
let env = self.env.borrow();
let db = {
let maps = env.mmaps.lock();
*(maps[0]
.ptr
.add(self.root * PAGE_SIZE + GLOBAL_HEADER_SIZE + 8 * n)
as *mut u64)
};
if db != 0 {
Some(sanakirja_core::btree::Db_ {
db,
k: std::marker::PhantomData,
v: std::marker::PhantomData,
p: std::marker::PhantomData,
})
} else {
None
}
}
}