use super::MutPage;
const N_LEVELS: usize = 7;
pub const SKIPLIST_ROOT: u16 = 8;
const RIGHT_CHILD_OFFSET_U64: isize = 1;
pub const FIRST_BINDING_SIZE: u16 = SKIPLIST_ROOT + 16;
#[derive(Debug, Copy, Clone)]
pub struct SkipCursor {
pub levels: [u16; N_LEVELS],
pub started: bool,
}
impl SkipCursor {
pub fn new() -> Self {
SkipCursor {
levels: [SKIPLIST_ROOT; N_LEVELS],
started: false,
}
}
pub fn reset(&mut self) {
for i in self.levels.iter_mut() {
*i = SKIPLIST_ROOT
}
self.started = false
}
}
pub(crate) fn set_cursor(
page: &MutPage,
curs: &mut SkipCursor,
key: u64,
) -> Option<u64> {
let mut level = N_LEVELS - 1;
loop {
let result = set_cursor_at_level(page, &mut curs.levels[level], level, key);
if level == 0 {
return result;
}
level -= 1;
curs.levels[level] = curs.levels[level + 1]
}
}
fn set_cursor_at_level(
page: &MutPage,
position: &mut u16,
level: usize,
key: u64,
) -> Option<u64> {
loop {
let next_position = next_at_level(page, *position, level);
if next_position == 0 {
return None;
}
let (k, v) = unsafe { read_key_value(page, next_position) };
if k == key {
return Some(v)
} else if k < key {
debug_assert!(*position != next_position);
*position = next_position
} else {
return None
}
}
}
unsafe fn set_level(p: *mut u8, level: usize, value: u16) {
debug_assert!(level < N_LEVELS);
debug_assert_eq!(value & 7, 0); debug_assert_eq!((p as usize) & 7, 0); let p = p as *mut u64;
let mut levels = u64::from_le(*p);
let value = (value >> 3) as u64;
levels &= !(0x1ff << (9 * level));
levels |= value << (9 * level);
*p = levels.to_le()
}
#[doc(hidden)]
pub(crate) fn skiplist_insert_after_cursor(
page: &mut MutPage,
r: &mut u8,
cursor: &mut SkipCursor,
key: u64,
value: u64,
right_child: u64,
) {
let off = page.alloc(32);
debug_assert_ne!(off, 0);
page.reset_pointers(off);
unsafe {
*(page.p.offset(off as isize + 16) as *mut u64) = key;
*(page.p.offset(off as isize + 24) as *mut u64) = value;
}
set_right_child(page, off, right_child);
let mut g = *r;
*r += 1;
for l in 0..N_LEVELS {
unsafe {
debug_assert_ne!(off, next_at_level(page, cursor.levels[l], l));
debug_assert_ne!(off, cursor.levels[l]);
set_level(
page.p.offset(off as isize),
l,
next_at_level(page, cursor.levels[l], l),
);
set_level(page.p.offset(cursor.levels[l] as isize), l, off);
}
cursor.levels[l] = off;
if g & 1 == 0 {
break;
}
g >>= 1
}
}
#[doc(hidden)]
pub(crate) fn set_right_child(page: &MutPage, off: u16, r: u64) {
if off >= 4096 {
panic!("{} < 4096", off);
}
unsafe {
*((page.offset(off as isize) as *mut u64).offset(RIGHT_CHILD_OFFSET_U64)) = r.to_le();
}
}
impl MutPage {
fn reset_pointers(&mut self, offset: u16) {
unsafe {
let p: *mut u8 = self.p.offset(offset as isize);
std::ptr::write_bytes(p, 0, 8);
}
}
}
pub(crate) fn next_at_level(p: &MutPage, off: u16, level: usize) -> u16 {
unsafe {
debug_assert!(level < N_LEVELS);
let levels = u64::from_le(*(p.offset(off as isize) as *const u64));
(((levels >> (9 * level)) & 0x1ff) as u16) << 3
}
}
pub(crate) unsafe fn read_key_value(
p: &MutPage,
off: u16,
) -> (u64, u64) {
assert!(off < 4096);
(*(p.offset(off as isize + 16) as *mut u64),
*(p.offset(off as isize + 24) as *mut u64))
}
impl MutPage {
pub fn init_skiplist_page(&mut self) {
self.reset_pointers(SKIPLIST_ROOT);
self.set_first_free(FIRST_BINDING_SIZE); self.set_size(FIRST_BINDING_SIZE); unsafe {
*((self.offset(SKIPLIST_ROOT as isize) as *mut u64).offset(RIGHT_CHILD_OFFSET_U64)) = 0;
}
}
}