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 {
                let v = p.lookup(i * i);
                assert_eq!(v, Some(i * i * i));
            }
            total_lookup += now.elapsed().unwrap();
        }
    }
    println!("linked-list: {:?} {:?}", 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 {
                let v = p.lookup_ord(i * i);
                assert_eq!(v, Some(i * i * i));
            }
            total_lookup += now.elapsed().unwrap();
        }
    }
    println!("ordered-vec: {:?} {:?}", 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!("skip-list: {:?} {:?}", 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, u16) {
        let mut a = 0;
        let mut b = (self.size() - 16) / 24;
        while a < b {
            let mid = (a + b) / 2;
            let k = *(self.p.offset((16 + mid * 24 + 8) as isize) as *mut u64);
            if k < k0 {
                if a == mid {
                    break
                }
                a = mid
            } else if k == k0 {
                a = mid;
                b = mid;
                break
            } else {
                b = mid
            }
        }
        (16 + a * 24, 16 + b * 24)
    }
    pub unsafe fn lookup_ord(&mut self, k0: u64) -> Option<u64> {
        let (off, _) = self.lookup_ord_(k0);
        let off = off as isize;
        let k = *(self.p.offset(off + 8) as *mut u64);
        if k == k0 {
            Some(*(self.p.offset(off + 16) 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);
    }

}