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

mod skiplist;
fn main() {
    let mut page = [0u8; 4096];
    let mut total_put = std::time::Duration::from_secs(0);
    let mut total_lookup = std::time::Duration::from_secs(0);
    for _ in 0..1_000_000 {
        let mut p = MutPage {
            p: page.as_mut_ptr()
        };
        unsafe {
            p.init();
            let now = std::time::SystemTime::now();
            for i in 0..170 {
                p.put(i * i, i * i * i, 0);
            }
            total_put += now.elapsed().unwrap();
            let now = std::time::SystemTime::now();
            for i in 0..170 {
                p.lookup(i * i);
            }
            total_lookup += now.elapsed().unwrap();
        }
    }
    println!("{:?} {:?}", total_put, total_lookup);
    let mut total_put = std::time::Duration::from_secs(0);
    let mut total_lookup = std::time::Duration::from_secs(0);
    for _ in 0..1_000_000 {
        let mut p = MutPage {
            p: page.as_mut_ptr()
        };
        unsafe {
            p.init();
            for i in 0..170 {
                let now = std::time::SystemTime::now();
                p.put_ord(i * i, i * i * i, 0);
                total_put += now.elapsed().unwrap();
            }
            let now = std::time::SystemTime::now();
            for i in 0..170 {
                p.lookup_ord(i * i);
            }
            total_lookup += now.elapsed().unwrap();
        }
    }
    println!("{:?} {:?}", total_put, total_lookup);
    let mut rng = 0;
    let mut total_put = std::time::Duration::from_secs(0);
    let mut total_lookup = std::time::Duration::from_secs(0);
    for _ in 0..1_000_000 {
        let mut p = MutPage {
            p: page.as_mut_ptr()
        };
        p.init_skiplist_page();
        let mut c = skiplist::SkipCursor::new();
        let now = std::time::SystemTime::now();
        for i in 0..100 {
            c.reset();
            skiplist::set_cursor(&p, &mut c, i * i);
            skiplist::skiplist_insert_after_cursor(&mut p, &mut rng, &mut c, i*i, i*i*i, 0);
        }
        total_put += now.elapsed().unwrap();
        let now = std::time::SystemTime::now();
        for i in 0..100 {
            c.reset();
            skiplist::set_cursor(&p, &mut c, i * i);
        }
        total_lookup += now.elapsed().unwrap();
    }
    println!("{:?} {:?}", total_put, total_lookup);
}
struct MutPage {
    p: *mut u8,
}
impl MutPage {
    pub unsafe fn init(&mut self) {
        let p = self.p as *mut u64;
        *(p.offset(1)) = 0;
        self.set_size(16);
        self.set_first_free(16);
    }
    pub fn size(&self) -> u16 {
        unsafe {
            u16::from_le(*(self.p as *mut u16).offset(2))
        }
    }
    pub fn set_size(&self, n: u16) {
        unsafe {
            *(self.p as *mut u16).offset(2) = n.to_le()
        }
    }
    pub fn set_first_free(&self, n: u16) {
        unsafe {
            *(self.p as *mut u16).offset(3) = n.to_le()
        }
    }
    pub fn first_free(&self) -> u16 {
        unsafe {
            u16::from_le(*(self.p as *mut u16).offset(3))
        }
    }
    pub unsafe fn put(&mut self, k0: u64, v0: u64, rr: u64) {
        let rn0 = u64::from_le(*self.offset(8));
        let mut n0 = (rn0 & 0xfff) as isize;
        let mut i = n0;
        n0 = 8;
        while i != 0 {
            let k = u64::from_le(*self.offset(i + 8));
            if k0 < k {
                let rn = u64::from_le(*self.offset(i));
                let n = (rn & 0xfff) as isize;
                n0 = i;
                i = n
            } else if k0 == k {
                return
            } else {
                // Insérer ici.
                let off = self.alloc(24);
                let r0 = *self.offset(n0) & !0xfff;
                *self.offset(n0) = r0 | (off as u64);
                *self.offset(off as isize) = rr | (i as u64);
                *self.offset(off as isize + 8) = k0.to_le();
                *self.offset(off as isize + 16) = v0.to_le();
                return
            }
        }
        let off = self.alloc(24);
        let r0 = *self.offset(n0) & !0xfff;
        *self.offset(n0) = r0 | (off as u64);
        *self.offset(off as isize) = rr.to_le();
        *self.offset(off as isize + 8) = k0.to_le();
        *self.offset(off as isize + 16) = v0.to_le();
    }
    unsafe fn offset(&self, i: isize) -> *mut u64 {
        self.p.offset(i) as *mut u64
    }
    pub fn alloc(&mut self, n: u16) -> u16 {
        self.set_size(self.size() + n);
        let result = self.first_free();
        assert!(result + n <= 4096);
        self.set_first_free(result + n);
        result
    }
    pub unsafe fn lookup(&self, k0: u64) -> Option<u64> {
        let rn0 = u64::from_le(*self.offset(8));
        let mut i = (rn0 & 0xfff) as isize;
        while i != 0 {
            let k = u64::from_le(*self.offset(i + 8));
            if k0 < k {
                let rn = u64::from_le(*self.offset(i));
                let n = (rn & 0xfff) as isize;
                i = n
            } else if k0 == k {
                return Some(u64::from_le(*self.offset(i + 16)))
            } else {
                return None
            }
        }
        None
    }
}
impl MutPage {
    pub unsafe fn lookup_ord_(&mut self, k0: u64) -> u16 {
        let mut a = 16;
        let mut b = self.size();
        assert!(b <= 4096);
        while a < b {
            let mid = (a + b) / 2 - 16;
            let mid = 16 + mid - (mid % 24);
            let k = *(self.p.offset(mid as isize) as *mut u64);
            if k < k0 {
                if a == mid {
                    break
                }
                a = mid
            } else {
                b = mid
            }
        }
        a
    }
    pub unsafe fn lookup_ord(&mut self, k0: u64) -> Option<u64> {
        let off = self.lookup_ord_(k0) as isize;
        let k = *(self.p.offset(off) as *mut u64);
        if k == k0 {
            Some(*(self.p.offset(off + 8) as *mut u64))
        } else {
            None
        }
    }
    pub unsafe fn put_ord(&mut self, k0: u64, v0: u64, _rr: u64) {
        let size = self.size();
        let off = self.lookup_ord_(k0);
        if size > off {
            std::ptr::copy(self.p.offset(off as isize), self.p.offset(off as isize + 24), (size - off) as usize);
        }
        *self.offset(off as isize + 8) = k0.to_le();
        *self.offset(off as isize + 16) = v0.to_le();
        self.set_size(size + 24);
    }
}

[package]
name = "sanakirja2"
version = "0.1.0"
authors = ["pe"]
edition = "2018"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]