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
    }
}

/// Sets the cursor to the last position strictly smaller than
/// (key, value). If the key (and possibly value) was found, the
/// corresponding value is returned.
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]
    }
}

/// Moves the cursor at level `level`, until the final position is
/// either immediately before NIL, or the largest position
/// strictly smaller than (key, value). If (key, value) was found,
/// it is returned.
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); // Check that value is multiple of 8.
    debug_assert_eq!((p as usize) & 7, 0); // Check that the conversion to *mut u64 is valid.
    let p = p as *mut u64;
    let mut levels = u64::from_le(*p);

    // All values are 8-bytes aligned, we don't need to store the 3 extra 0s.
    let value = (value >> 3) as u64;

    // Set the value at that level to 0.
    levels &= !(0x1ff << (9 * level));

    // Replace with current value.
    levels |= value << (9 * level);

    *p = levels.to_le()
}

/// This function panics if there's enough space on the page.
#[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,
) {
    // First allocate the key and value.
    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);

    // Now insert in the base list.
    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) {
        // Initialize the list pointers.
        unsafe {
            let p: *mut u8 = self.p.offset(offset as isize);
            std::ptr::write_bytes(p, 0, 8);
        }
    }
}

// All bindings are 8-bytes aligned. There are 7 layers, each
// encoding 9 bits, which are then multiplied by 8 to get the
// position on the page.
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);
        // Initialize the page metadata.
        self.set_first_free(FIRST_BINDING_SIZE); // first free spot.
        self.set_size(FIRST_BINDING_SIZE); // occupied size on page.
        unsafe {
            *((self.offset(SKIPLIST_ROOT as isize) as *mut u64).offset(RIGHT_CHILD_OFFSET_U64)) = 0;
        }
    }
}