use crate::{util, Arc, Data, MData, Ordering, Rc, Record, RefCell, DB};
pub type PagePtr = Rc<RefCell<Page>>;
const NODE_OVERHEAD: usize = 3;
const NODE_BASE: usize = 8;
const PAGE_ID_SIZE: usize = 6;
const NODE_ID_BITS: usize = 11;
const NF: usize = NODE_ID_BITS - 8;
const MAX_NODE: usize = bitmask!(0, NODE_ID_BITS);
pub struct Page {
pub data: MData,
pub pnum: u64,
pub count: usize,
pub level: u8,
pub is_dirty: bool,
pub node_size: usize,
pub root: usize,
pub first_page: u64,
free: usize,
alloc: usize,
}
impl Page {
pub fn size(&self) -> usize {
NODE_BASE + self.alloc * self.node_size + if self.level != 0 { PAGE_ID_SIZE } else { 0 }
}
pub fn new(rec_size: usize, level: u8, mut data: Data, pnum: u64) -> Page {
let node_size = rec_size + if level != 0 { PAGE_ID_SIZE } else { 0 } + NODE_OVERHEAD;
if data.len() == 0 {
let data = Data::make_mut(&mut data);
data.resize(NODE_BASE + if level != 0 { PAGE_ID_SIZE } else { 0 }, 0);
}
let u = util::getu64(&data, 0); let root = getbits!(u, 8, NODE_ID_BITS) as usize;
let count = getbits!(u, 8 + NODE_ID_BITS, NODE_ID_BITS) as usize;
let free = getbits!(u, 8 + NODE_ID_BITS * 2, NODE_ID_BITS) as usize;
let alloc = getbits!(u, 8 + NODE_ID_BITS * 3, NODE_ID_BITS) as usize;
let first_page = if level != 0 {
util::get(&data, NODE_BASE + alloc * node_size, PAGE_ID_SIZE)
} else {
0
};
Page {
data: MData::new(data),
node_size,
root,
count,
free,
alloc,
first_page,
level,
pnum,
is_dirty: false,
}
}
pub fn write_header(&mut self) {
debug_assert!(self.size() == self.data.len());
let u = self.level as u64
| ((self.root as u64) << 8)
| ((self.count as u64) << (8 + NODE_ID_BITS))
| ((self.free as u64) << (8 + 2 * NODE_ID_BITS))
| ((self.alloc as u64) << (8 + 3 * NODE_ID_BITS));
let level = self.level;
let first_page = self.first_page;
let data = &mut self.data;
util::setu64(data, u); if level != 0 {
let off = data.len() - PAGE_ID_SIZE;
util::set(data, off, first_page, PAGE_ID_SIZE);
}
}
pub fn full(&self, page_limit: usize) -> bool {
self.free == 0
&& (self.alloc == MAX_NODE
|| NODE_BASE
+ (self.alloc + 1) * self.node_size
+ if self.level != 0 { PAGE_ID_SIZE } else { 0 }
> page_limit)
}
pub fn new_page(&self, capacity: usize) -> Page {
Page::new(
self.rec_size(),
self.level,
Arc::new(Vec::with_capacity(capacity)),
u64::MAX,
)
}
pub fn find_child(&self, db: &DB, r: &dyn Record) -> u64 {
let mut x = self.root;
let mut rx = 0;
while x != 0 {
let c = self.compare(db, r, x);
match c {
Ordering::Greater => x = self.left(x),
Ordering::Less => {
rx = x;
x = self.right(x);
}
Ordering::Equal => {
rx = x;
break;
}
}
}
if rx == 0 {
self.first_page
} else {
self.child_page(rx)
}
}
pub fn find_equal(&self, db: &DB, r: &dyn Record) -> usize {
let mut x = self.root;
while x != 0 {
let c = self.compare(db, r, x);
match c {
Ordering::Greater => x = self.left(x),
Ordering::Less => x = self.right(x),
Ordering::Equal => {
return x;
}
}
}
0
}
pub fn remove(&mut self, db: &DB, r: &dyn Record) {
let mut mp = MutPage {
data: &mut self.data,
node_size: self.node_size,
level: self.level,
target: 0,
};
self.root = mp.remove_from(db, self.root, r).0;
let target = mp.target;
if target != 0 {
self.free_node(target);
}
}
fn do_insert(&mut self, target: usize, r: Option<(&DB, &dyn Record)>) {
let mut mp = MutPage {
data: &mut self.data,
node_size: self.node_size,
level: self.level,
target,
};
self.root = mp.insert_into(self.root, r).0;
}
pub fn insert(&mut self, db: &DB, r: &dyn Record) {
let target = self.alloc_node();
self.set_record(target, r);
self.do_insert(target, Some((db, r)));
}
pub fn insert_page(&mut self, db: &DB, r: &dyn Record, cp: u64) {
let target = self.alloc_node();
self.set_record(target, r);
self.set_child_page(target, cp);
self.do_insert(target, Some((db, r)));
}
pub fn append_page(&mut self, r: &dyn Record, cp: u64) {
let target = self.alloc_node();
self.set_record(target, r);
self.set_child_page(target, cp);
self.do_insert(target, None);
}
pub fn append_from(&mut self, from: &Page, x: usize) {
if self.level != 0 && self.first_page == 0 {
self.first_page = from.child_page(x);
} else {
let target = self.alloc_node();
let dest_off = self.rec_offset(target);
let src_off = from.rec_offset(x);
let n = self.node_size - NODE_OVERHEAD;
self.data[dest_off..dest_off + n].copy_from_slice(&from.data[src_off..src_off + n]);
self.do_insert(target, None);
}
}
pub fn append_page_copy(&mut self, b: &[u8], cp: u64) {
let target = self.alloc_node();
let off = self.rec_offset(target);
let n = self.node_size - NODE_OVERHEAD - PAGE_ID_SIZE;
debug_assert!(n == b.len());
self.data[off..off + n].copy_from_slice(&b[0..n]);
self.set_child_page(target, cp);
self.do_insert(target, None);
}
pub fn copy(&self, x: usize) -> Vec<u8> {
let n = self.node_size - NODE_OVERHEAD - PAGE_ID_SIZE;
let off = self.rec_offset(x);
let mut b = vec![0; n];
b.copy_from_slice(&self.data[off..off + n]);
b
}
fn over_off(&self, x: usize) -> usize {
debug_assert!(x != 0);
(NODE_BASE - NODE_OVERHEAD) + x * self.node_size
}
pub fn rec_offset(&self, x: usize) -> usize {
debug_assert!(x != 0);
NODE_BASE + (x - 1) * self.node_size
}
pub fn rec_size(&self) -> usize {
self.node_size - NODE_OVERHEAD - if self.level != 0 { PAGE_ID_SIZE } else { 0 }
}
pub fn left(&self, x: usize) -> usize {
let off = self.over_off(x);
let data = &self.data;
unsafe_assert!(off + 1 < data.len());
data[off + 1] as usize | (getbits!(data[off] as usize, 2, NF) << 8)
}
pub fn right(&self, x: usize) -> usize {
let off = self.over_off(x);
let data = &self.data;
unsafe_assert!(off + 2 < data.len());
data[off + 2] as usize | (getbits!(data[off] as usize, 2 + NF, NF) << 8)
}
fn set_left(&mut self, x: usize, y: usize) {
let off = self.over_off(x);
let data = &mut self.data;
data[off + 1] = (y & 255) as u8;
setbits!(data[off], 2, NF, (y >> 8) as u8);
debug_assert!(self.left(x) == y);
}
pub fn child_page(&self, x: usize) -> u64 {
debug_assert!(self.level != 0);
let off = self.over_off(x) - PAGE_ID_SIZE;
util::get(&self.data, off, PAGE_ID_SIZE)
}
pub fn set_child_page(&mut self, x: usize, pnum: u64) {
debug_assert!(self.level != 0);
let off = self.over_off(x) - PAGE_ID_SIZE;
util::set(&mut self.data, off, pnum, PAGE_ID_SIZE);
}
fn set_record(&mut self, x: usize, r: &dyn Record) {
let off = self.rec_offset(x);
let size = self.rec_size();
r.save(&mut self.data[off..off + size]);
}
pub fn compare(&self, db: &DB, r: &dyn Record, x: usize) -> Ordering {
let off = self.rec_offset(x);
let size = self.rec_size();
r.compare(db, &self.data[off..off + size])
}
pub fn get_key(&self, db: &DB, x: usize, r: &dyn Record) -> Box<dyn Record> {
let off = self.rec_offset(x);
let size = self.rec_size();
r.key(db, &self.data[off..off + size])
}
pub fn clear(&mut self) {
self.root = 0;
self.count = 0;
self.alloc = 0;
self.resize_data();
}
pub fn drop_key(&self, db: &DB, x: usize, r: &dyn Record) {
r.drop_key(db, &self.data[self.rec_offset(x)..]);
}
fn resize_data(&mut self) {
let size = self.size();
self.data.resize(size, 0);
}
fn alloc_node(&mut self) -> usize {
self.count += 1;
if self.free == 0 {
self.alloc += 1;
self.resize_data();
self.count
} else {
let result = self.free;
self.free = self.left(self.free);
result
}
}
fn free_node(&mut self, x: usize) {
self.set_left(x, self.free);
self.free = x;
self.count -= 1;
}
pub fn compress(&mut self, db: &DB) {
let saving = (self.alloc - self.count) * self.node_size;
if saving != 0 && db.apd.compress(self.size(), saving) {
let mut flist = Vec::new();
let mut f = self.free;
while f != 0 {
if f <= self.count {
flist.push(f);
}
f = self.left(f);
}
if !flist.is_empty() {
let mut mp = MutPage {
data: &mut self.data,
node_size: self.node_size,
level: self.level,
target: self.count,
};
self.root = mp.relocate(self.root, &mut flist);
}
self.free = 0;
self.alloc = self.count;
}
self.resize_data();
}
} #[derive(PartialEq)]
enum Balance {
LeftHigher = 0,
Balanced = 1,
RightHigher = 2,
}
use Balance::*;
struct MutPage<'a> {
data: &'a mut Vec<u8>,
node_size: usize,
level: u8,
target: usize,
}
impl<'a> MutPage<'a> {
fn over_off(&self, x: usize) -> usize {
debug_assert!(x != 0);
(NODE_BASE - NODE_OVERHEAD) + x * self.node_size
}
fn rec_offset(&self, x: usize) -> usize {
debug_assert!(x != 0);
NODE_BASE + (x - 1) * self.node_size
}
fn rec_size(&self) -> usize {
self.node_size - NODE_OVERHEAD - if self.level != 0 { PAGE_ID_SIZE } else { 0 }
}
fn balance(&self, x: usize) -> Balance {
let off = self.over_off(x);
unsafe_assert!(off < self.data.len());
match getbits!(self.data[off], 0, 2) {
0 => LeftHigher,
1 => Balanced,
_ => RightHigher,
}
}
fn set_balance(&mut self, x: usize, balance: Balance) {
let off = self.over_off(x);
unsafe_assert!(off < self.data.len());
setbits!(self.data[off], 0, 2, balance as u8);
}
fn left(&self, x: usize) -> usize {
let off = self.over_off(x);
let data = &self.data;
unsafe_assert!(off + 1 < data.len());
data[off + 1] as usize | (getbits!(data[off] as usize, 2, NF) << 8)
}
fn right(&self, x: usize) -> usize {
let off = self.over_off(x);
let data = &self.data;
unsafe_assert!(off + 2 < data.len());
data[off + 2] as usize | (getbits!(data[off] as usize, 2 + NF, NF) << 8)
}
fn set_left(&mut self, x: usize, y: usize) {
let off = self.over_off(x);
let data = &mut self.data;
unsafe_assert!(off + 1 < data.len());
data[off + 1] = (y & 255) as u8;
setbits!(data[off], 2, NF, (y >> 8) as u8);
debug_assert!(self.left(x) == y);
}
fn set_right(&mut self, x: usize, y: usize) {
let off = self.over_off(x);
let data = &mut self.data;
unsafe_assert!(off + 2 < data.len());
data[off + 2] = (y & 255) as u8;
setbits!(data[off], 2 + NF, NF, (y >> 8) as u8);
debug_assert!(self.right(x) == y);
}
fn compare(&self, db: &DB, r: &dyn Record, x: usize) -> Ordering {
let off = self.rec_offset(x);
let size = self.rec_size();
unsafe_assert!(off + size < self.data.len());
r.compare(db, &self.data[off..off + size])
}
fn insert_into(&mut self, mut x: usize, r: Option<(&DB, &dyn Record)>) -> (usize, bool) {
let mut height_increased: bool;
if x == 0 {
x = self.target;
self.set_balance(x, Balanced);
self.set_left(x, 0);
self.set_right(x, 0);
height_increased = true;
} else {
let c = match r {
Some((db, r)) => self.compare(db, r, x),
None => Ordering::Less,
};
if c == Ordering::Greater {
let p = self.insert_into(self.left(x), r);
self.set_left(x, p.0);
height_increased = p.1;
if height_increased {
let bx = self.balance(x);
if bx == Balanced {
self.set_balance(x, LeftHigher);
} else {
height_increased = false;
if bx == LeftHigher {
return (self.rotate_right(x).0, false);
}
self.set_balance(x, Balanced);
}
}
} else if c == Ordering::Less {
let p = self.insert_into(self.right(x), r);
self.set_right(x, p.0);
height_increased = p.1;
if height_increased {
let bx = self.balance(x);
if bx == Balanced {
self.set_balance(x, RightHigher);
} else {
if bx == RightHigher {
return (self.rotate_left(x).0, false);
}
height_increased = false;
self.set_balance(x, Balanced);
}
}
} else {
panic!("Duplicate key");
}
}
(x, height_increased)
}
fn rotate_right(&mut self, x: usize) -> (usize, bool) {
let mut height_decreased = true;
let z = self.left(x);
let y = self.right(z);
let zb = self.balance(z);
if zb != RightHigher
{
self.set_right(z, x);
self.set_left(x, y);
if zb == Balanced
{
self.set_balance(x, LeftHigher);
self.set_balance(z, RightHigher);
height_decreased = false;
} else {
self.set_balance(x, Balanced);
self.set_balance(z, Balanced);
}
(z, height_decreased)
} else {
self.set_left(x, self.right(y));
self.set_right(z, self.left(y));
self.set_right(y, x);
self.set_left(y, z);
let yb = self.balance(y);
if yb == LeftHigher {
self.set_balance(x, RightHigher);
self.set_balance(z, Balanced);
} else if yb == Balanced {
self.set_balance(x, Balanced);
self.set_balance(z, Balanced);
} else {
self.set_balance(x, Balanced);
self.set_balance(z, LeftHigher);
}
self.set_balance(y, Balanced);
(y, height_decreased)
}
}
fn rotate_left(&mut self, x: usize) -> (usize, bool) {
let mut height_decreased = true;
let z = self.right(x);
let y = self.left(z);
let zb = self.balance(z);
if zb != LeftHigher
{
self.set_left(z, x);
self.set_right(x, y);
if zb == Balanced
{
self.set_balance(x, RightHigher);
self.set_balance(z, LeftHigher);
height_decreased = false;
} else {
self.set_balance(x, Balanced);
self.set_balance(z, Balanced);
}
(z, height_decreased)
} else {
self.set_right(x, self.left(y));
self.set_left(z, self.right(y));
self.set_left(y, x);
self.set_right(y, z);
let yb = self.balance(y);
if yb == RightHigher {
self.set_balance(x, LeftHigher);
self.set_balance(z, Balanced);
} else if yb == Balanced {
self.set_balance(x, Balanced);
self.set_balance(z, Balanced);
} else {
self.set_balance(x, Balanced);
self.set_balance(z, RightHigher);
}
self.set_balance(y, Balanced);
(y, height_decreased)
}
}
pub fn remove_from(&mut self, db: &DB, mut x: usize, r: &dyn Record) -> (usize, bool) {
if x == 0
{
return (x, false);
}
let mut height_decreased: bool = true;
let compare = self.compare(db, r, x);
if compare == Ordering::Equal {
let deleted = x;
if self.left(x) == 0 {
x = self.right(x);
} else if self.right(x) == 0 {
x = self.left(x);
} else {
let t = self.remove_least(self.right(deleted));
let right = t.0;
x = t.1;
height_decreased = t.2;
self.set_left(x, self.left(deleted));
self.set_right(x, right);
self.set_balance(x, self.balance(deleted));
if height_decreased {
if self.balance(x) == LeftHigher {
let rr = self.rotate_right(x);
x = rr.0;
height_decreased = rr.1;
} else if self.balance(x) == RightHigher {
self.set_balance(x, Balanced);
} else {
self.set_balance(x, LeftHigher);
height_decreased = false;
}
}
}
self.target = deleted;
} else if compare == Ordering::Greater {
let rem = self.remove_from(db, self.left(x), r);
self.set_left(x, rem.0);
height_decreased = rem.1;
if height_decreased {
let xb = self.balance(x);
if xb == RightHigher {
return self.rotate_left(x);
}
if xb == LeftHigher {
self.set_balance(x, Balanced);
} else {
self.set_balance(x, RightHigher);
height_decreased = false;
}
}
} else {
let rem = self.remove_from(db, self.right(x), r);
self.set_right(x, rem.0);
height_decreased = rem.1;
if height_decreased {
let xb = self.balance(x);
if xb == LeftHigher {
return self.rotate_right(x);
}
if self.balance(x) == RightHigher {
self.set_balance(x, Balanced);
} else {
self.set_balance(x, LeftHigher);
height_decreased = false;
}
}
}
(x, height_decreased)
}
fn remove_least(&mut self, x: usize) -> (usize, usize, bool) {
if self.left(x) == 0 {
(self.right(x), x, true)
} else {
let t = self.remove_least(self.left(x));
self.set_left(x, t.0);
let least = t.1;
let mut height_decreased = t.2;
if height_decreased {
let xb = self.balance(x);
if xb == RightHigher {
let rl = self.rotate_left(x);
return (rl.0, least, rl.1);
}
if xb == LeftHigher {
self.set_balance(x, Balanced);
} else {
self.set_balance(x, RightHigher);
height_decreased = false;
}
}
(x, least, height_decreased)
}
}
fn relocate(&mut self, mut x: usize, flist: &mut Vec<usize>) -> usize {
if x != 0 {
if x > self.target {
let to = flist.pop().unwrap();
let n = self.node_size;
let src = self.rec_offset(x);
let dest = self.rec_offset(to);
self.data.copy_within(src..src + n, dest);
x = to;
}
let c = self.left(x);
let c1 = self.relocate(c, flist);
if c1 != c {
self.set_left(x, c1);
}
let c = self.right(x);
let c1 = self.relocate(c, flist);
if c1 != c {
self.set_right(x, c1);
}
}
x
}
}