rustdb/
page.rs

1//!
2//! A page has up to MAX_NODE (2047) fixed size nodes, which implement a balanced binary tree.
3//!
4//! Nodes are numbered from 1..MAX_NODE, with 0 indicating a null ( non-existent ) node.
5//!
6//! Each record has a 3 byte overhead, 2 bits to store the balance, 2 x 11 bits to store left and right node ids.
7//!
8//! Note that the left node is greater than the parent node.
9
10use crate::{Arc, DB, Data, MData, Ordering, Rc, Record, RefCell, util};
11
12/// ```Rc<RefCell<Page>>```
13pub type PagePtr = Rc<RefCell<Page>>;
14
15/* Note: the page size must be big enough that a good number of records fits into a page.
16   A record with 20 fields of 16 bytes is 320 bytes.
17   The page size should be at least 2kb, and the constants below should be chosen to make this the case.
18*/
19
20/// = 3. Size of Balance,Left,Right in a Node ( 2 + 2 x 11 = 24 bits = 3 bytes ).
21const NODE_OVERHEAD: usize = 3;
22
23/// = 8. 45 bits ( 1 + 4 x 11 ) needs 6 bytes, but use 8.
24const NODE_BASE: usize = 8;
25
26/// = 6. Number of bytes used to store a page number.
27const PAGE_ID_SIZE: usize = 6;
28
29/// = 11. Node ids are 11 bits.
30const NODE_ID_BITS: usize = 11;
31
32/// = 3. Fragment of Node Id that doesn't fit in byte.
33const NF: usize = NODE_ID_BITS - 8;
34
35/// = 2047. Largest Node id.
36const MAX_NODE: usize = bitmask!(0, NODE_ID_BITS);
37
38/// A page in a SortedFile.
39/// Note that left subtree has nodes that compare greater.
40pub struct Page {
41    /// Data storage.
42    pub data: MData,
43
44    /// Page number in file where page is saved.
45    pub pnum: u64,
46
47    /// Number of records currently stored in the page.
48    pub count: usize,
49
50    /// Page level. 0 means a child page, more than 0 a parent page.
51    pub level: u8,
52
53    /// Has the page been modified?
54    pub is_dirty: bool,
55
56    /// Number of bytes required for each node.
57    pub node_size: usize,
58
59    /// Root node for the page.
60    pub root: usize,
61
62    /// First child page ( for a parent page ).    
63    pub first_page: u64,
64
65    /// First Free node.
66    free: usize,
67
68    /// Number of Nodes currently allocated.     
69    alloc: usize,
70}
71
72impl Page {
73    /// The size of the page in bytes.
74    pub fn size(&self) -> usize {
75        NODE_BASE + self.alloc * self.node_size + if self.level != 0 { PAGE_ID_SIZE } else { 0 }
76    }
77
78    /// Construct a new page.
79    pub fn new(rec_size: usize, level: u8, mut data: Data, pnum: u64) -> Page {
80        let node_size = rec_size + if level != 0 { PAGE_ID_SIZE } else { 0 } + NODE_OVERHEAD;
81
82        if data.is_empty() {
83            let data = Data::make_mut(&mut data);
84            data.resize(NODE_BASE + if level != 0 { PAGE_ID_SIZE } else { 0 }, 0);
85        }
86
87        let u = util::getu64(&data, 0); // Possible since NODE_BASE = 8.
88        let root = getbits!(u, 8, NODE_ID_BITS) as usize;
89        let count = getbits!(u, 8 + NODE_ID_BITS, NODE_ID_BITS) as usize;
90        let free = getbits!(u, 8 + NODE_ID_BITS * 2, NODE_ID_BITS) as usize;
91        let alloc = getbits!(u, 8 + NODE_ID_BITS * 3, NODE_ID_BITS) as usize;
92        let first_page = if level != 0 {
93            util::get(&data, NODE_BASE + alloc * node_size, PAGE_ID_SIZE)
94        } else {
95            0
96        };
97        Page {
98            data: MData::new(data),
99            node_size,
100            root,
101            count,
102            free,
103            alloc,
104            first_page,
105            level,
106            pnum,
107            is_dirty: false,
108        }
109    }
110
111    /// Sets header and trailer (if parent) data. Called just before page is saved to file.
112    pub fn write_header(&mut self) {
113        debug_assert!(self.size() == self.data.len());
114
115        let u = self.level as u64
116            | ((self.root as u64) << 8)
117            | ((self.count as u64) << (8 + NODE_ID_BITS))
118            | ((self.free as u64) << (8 + 2 * NODE_ID_BITS))
119            | ((self.alloc as u64) << (8 + 3 * NODE_ID_BITS));
120        let level = self.level;
121        let first_page = self.first_page;
122        let data = &mut self.data;
123        util::setu64(data, u); // Possible since NODE_BASE = 8.
124        if level != 0 {
125            let off = data.len() - PAGE_ID_SIZE;
126            util::set(data, off, first_page, PAGE_ID_SIZE);
127        }
128    }
129
130    /// Is the page full?
131    pub fn full(&self, page_limit: usize) -> bool {
132        self.free == 0
133            && (self.alloc == MAX_NODE
134                || NODE_BASE
135                    + (self.alloc + 1) * self.node_size
136                    + if self.level != 0 { PAGE_ID_SIZE } else { 0 }
137                    > page_limit)
138    }
139
140    /// Construct a new empty page inheriting record size and level from self.
141    /// Used when splitting a page that is full.
142    pub fn new_page(&self, capacity: usize) -> Page {
143        Page::new(
144            self.rec_size(),
145            self.level,
146            Arc::new(Vec::with_capacity(capacity)),
147            u64::MAX,
148        )
149    }
150
151    /// Find child page number.
152    pub fn find_child(&self, db: &DB, r: &dyn Record) -> u64 {
153        let mut x = self.root;
154        let mut rx = 0;
155        while x != 0 {
156            let c = self.compare(db, r, x);
157            match c {
158                Ordering::Greater => x = self.left(x),
159                Ordering::Less => {
160                    rx = x;
161                    x = self.right(x);
162                }
163                Ordering::Equal => {
164                    rx = x;
165                    break;
166                }
167            }
168        }
169        if rx == 0 {
170            self.first_page
171        } else {
172            self.child_page(rx)
173        }
174    }
175
176    /// Returns node id of Record equal to r, or zero if no such node exists.
177    pub fn find_equal(&self, db: &DB, r: &dyn Record) -> usize {
178        let mut x = self.root;
179        while x != 0 {
180            let c = self.compare(db, r, x);
181            match c {
182                Ordering::Greater => x = self.left(x),
183                Ordering::Less => x = self.right(x),
184                Ordering::Equal => {
185                    return x;
186                }
187            }
188        }
189        0
190    }
191
192    /// Remove record from this page.
193    pub fn remove(&mut self, db: &DB, r: &dyn Record) {
194        let mut mp = MutPage {
195            data: &mut self.data,
196            node_size: self.node_size,
197            level: self.level,
198            target: 0,
199        };
200        self.root = mp.remove_from(db, self.root, r).0;
201        let target = mp.target;
202        if target != 0 {
203            self.free_node(target);
204        }
205    }
206
207    fn do_insert(&mut self, target: usize, r: Option<(&DB, &dyn Record)>) {
208        let mut mp = MutPage {
209            data: &mut self.data,
210            node_size: self.node_size,
211            level: self.level,
212            target,
213        };
214        self.root = mp.insert_into(self.root, r).0;
215    }
216
217    /// Insert a record into the page ( panics if the key is a duplicate ).
218    pub fn insert(&mut self, db: &DB, r: &dyn Record) {
219        let target = self.alloc_node();
220        self.set_record(target, r);
221        self.do_insert(target, Some((db, r)));
222    }
223
224    /// Insert a child page with specified key and number.
225    pub fn insert_page(&mut self, db: &DB, r: &dyn Record, cp: u64) {
226        let target = self.alloc_node();
227        self.set_record(target, r);
228        self.set_child_page(target, cp);
229        self.do_insert(target, Some((db, r)));
230    }
231
232    /// Append a child page with specified key and number.
233    pub fn append_page(&mut self, r: &dyn Record, cp: u64) {
234        let target = self.alloc_node();
235        self.set_record(target, r);
236        self.set_child_page(target, cp);
237        self.do_insert(target, None);
238    }
239
240    /// Append record x from specified page to this page.
241    pub fn append_from(&mut self, from: &Page, x: usize) {
242        if self.level != 0 && self.first_page == 0 {
243            self.first_page = from.child_page(x);
244        } else {
245            let target = self.alloc_node();
246            let dest_off = self.rec_offset(target);
247            let src_off = from.rec_offset(x);
248            let n = self.node_size - NODE_OVERHEAD;
249            self.data[dest_off..dest_off + n].copy_from_slice(&from.data[src_off..src_off + n]);
250            self.do_insert(target, None);
251        }
252    }
253
254    /// Append a copied parent key.
255    pub fn append_page_copy(&mut self, b: &[u8], cp: u64) {
256        let target = self.alloc_node();
257        let off = self.rec_offset(target);
258        let n = self.node_size - NODE_OVERHEAD - PAGE_ID_SIZE;
259        debug_assert!(n == b.len());
260        self.data[off..off + n].copy_from_slice(&b[0..n]);
261        self.set_child_page(target, cp);
262        self.do_insert(target, None);
263    }
264
265    /// Make a copy of a parent key record.
266    pub fn copy(&self, x: usize) -> Vec<u8> {
267        let n = self.node_size - NODE_OVERHEAD - PAGE_ID_SIZE;
268        let off = self.rec_offset(x);
269        let mut b = vec![0; n];
270        b.copy_from_slice(&self.data[off..off + n]);
271        b
272    }
273
274    // Node access functions.
275    // Layout of a Node is
276    // Client data
277    // Possibly padding
278    // Child page number ( if parent page ) ( 6 bytes )
279    // Node overhead ( 3 bytes )
280
281    /// Offset of the 3 byte node overhead  for node x.
282    fn over_off(&self, x: usize) -> usize {
283        debug_assert!(x != 0);
284        (NODE_BASE - NODE_OVERHEAD) + x * self.node_size
285    }
286
287    /// Offset of the client data for node x.
288    pub fn rec_offset(&self, x: usize) -> usize {
289        debug_assert!(x != 0);
290        NODE_BASE + (x - 1) * self.node_size
291    }
292
293    /// The client data size.
294    pub fn rec_size(&self) -> usize {
295        self.node_size - NODE_OVERHEAD - if self.level != 0 { PAGE_ID_SIZE } else { 0 }
296    }
297
298    /// Get the left child node for node x. Result is zero if there is no child.
299    pub fn left(&self, x: usize) -> usize {
300        let off = self.over_off(x);
301        let data = &self.data;
302        unsafe_assert!(off + 1 < data.len());
303        data[off + 1] as usize | (getbits!(data[off] as usize, 2, NF) << 8)
304    }
305
306    /// Get the right child node for node x. Result is zero if there is no child.
307    pub fn right(&self, x: usize) -> usize {
308        let off = self.over_off(x);
309        let data = &self.data;
310        unsafe_assert!(off + 2 < data.len());
311        data[off + 2] as usize | (getbits!(data[off] as usize, 2 + NF, NF) << 8)
312    }
313
314    /// Set the left child node for node x.
315    fn set_left(&mut self, x: usize, y: usize) {
316        let off = self.over_off(x);
317        let data = &mut self.data;
318        data[off + 1] = (y & 255) as u8;
319        setbits!(data[off], 2, NF, (y >> 8) as u8);
320        debug_assert!(self.left(x) == y);
321    }
322
323    /// Get the child page number for node x in a parent page.
324    pub fn child_page(&self, x: usize) -> u64 {
325        debug_assert!(self.level != 0);
326        let off = self.over_off(x) - PAGE_ID_SIZE;
327        util::get(&self.data, off, PAGE_ID_SIZE)
328    }
329
330    /// Set the child page for node x.
331    pub fn set_child_page(&mut self, x: usize, pnum: u64) {
332        // println!("set child page page pnum={} x={} pnum={}", self.pnum, x, pnum);
333        debug_assert!(self.level != 0);
334        let off = self.over_off(x) - PAGE_ID_SIZE;
335        util::set(&mut self.data, off, pnum, PAGE_ID_SIZE);
336    }
337
338    /// Set the record data for node x.
339    fn set_record(&mut self, x: usize, r: &dyn Record) {
340        let off = self.rec_offset(x);
341        let size = self.rec_size();
342        r.save(&mut self.data[off..off + size]);
343    }
344
345    /// Compare record data for node x with record r.
346    pub fn compare(&self, db: &DB, r: &dyn Record, x: usize) -> Ordering {
347        let off = self.rec_offset(x);
348        let size = self.rec_size();
349        r.compare(db, &self.data[off..off + size])
350    }
351
352    /// Get record key for node x.
353    pub fn get_key(&self, db: &DB, x: usize, r: &dyn Record) -> Box<dyn Record> {
354        let off = self.rec_offset(x);
355        let size = self.rec_size();
356        r.key(db, &self.data[off..off + size])
357    }
358
359    // Node Id Allocation.
360
361    /// Clear the page ( no nodes ).
362    pub fn clear(&mut self) {
363        self.root = 0;
364        self.count = 0;
365        self.alloc = 0;
366        self.resize_data();
367    }
368
369    /// Drop the key for the specified node.
370    pub fn drop_key(&self, db: &DB, x: usize, r: &dyn Record) {
371        r.drop_key(db, &self.data[self.rec_offset(x)..]);
372    }
373
374    /// Resize data.
375    fn resize_data(&mut self) {
376        let size = self.size();
377        self.data.resize(size, 0);
378    }
379
380    /// Allocate a node.
381    fn alloc_node(&mut self) -> usize {
382        self.count += 1;
383        if self.free == 0 {
384            self.alloc += 1;
385            self.resize_data();
386            self.count
387        } else {
388            let result = self.free;
389            self.free = self.left(self.free);
390            result
391        }
392    }
393
394    /// Free node x.
395    fn free_node(&mut self, x: usize) {
396        self.set_left(x, self.free);
397        self.free = x;
398        self.count -= 1;
399    }
400
401    /// Reduce page size using free nodes.
402    pub fn compress(&mut self, db: &DB) {
403        let saving = (self.alloc - self.count) * self.node_size;
404        if saving != 0 && db.apd.compress(self.size(), saving) {
405            let mut flist = Vec::new();
406            let mut f = self.free;
407            while f != 0 {
408                if f <= self.count {
409                    flist.push(f);
410                }
411                f = self.left(f);
412            }
413            if !flist.is_empty() {
414                let mut mp = MutPage {
415                    data: &mut self.data,
416                    node_size: self.node_size,
417                    level: self.level,
418                    target: self.count,
419                };
420                self.root = mp.relocate(self.root, &mut flist);
421            }
422            self.free = 0;
423            self.alloc = self.count;
424        }
425        self.resize_data();
426    }
427} // end impl Page
428
429/// Node balance - indicates which child tree is higher.
430#[derive(PartialEq)]
431enum Balance {
432    LeftHigher = 0,
433    Balanced = 1,
434    RightHigher = 2,
435}
436use Balance::*;
437
438/// To reduce the number of calls to Arc::make_mut.
439struct MutPage<'a> {
440    /// Data.
441    data: &'a mut Vec<u8>,
442    /// Node size for page.
443    node_size: usize,
444    /// Page level.
445    level: u8,
446    /// Target - used for various purposes.
447    target: usize,
448}
449
450impl<'a> MutPage<'a> {
451    // Node access functions.
452    // Layout of a Node is
453    // Client data
454    // Possibly padding
455    // Child page number ( if parent page ) ( 6 bytes )
456    // Node overhead ( 3 bytes )
457
458    /// Offset of the 3 byte node overhead  for node x.
459    fn over_off(&self, x: usize) -> usize {
460        debug_assert!(x != 0);
461        (NODE_BASE - NODE_OVERHEAD) + x * self.node_size
462    }
463
464    /// Offset of the client data for node x.
465    fn rec_offset(&self, x: usize) -> usize {
466        debug_assert!(x != 0);
467        NODE_BASE + (x - 1) * self.node_size
468    }
469
470    /// The client data size.
471    fn rec_size(&self) -> usize {
472        self.node_size - NODE_OVERHEAD - if self.level != 0 { PAGE_ID_SIZE } else { 0 }
473    }
474
475    /// Get balance for node x.
476    fn balance(&self, x: usize) -> Balance {
477        let off = self.over_off(x);
478        unsafe_assert!(off < self.data.len());
479        match getbits!(self.data[off], 0, 2) {
480            0 => LeftHigher,
481            1 => Balanced,
482            _ => RightHigher,
483        }
484    }
485
486    /// Set balance for node x.
487    fn set_balance(&mut self, x: usize, balance: Balance) {
488        let off = self.over_off(x);
489        unsafe_assert!(off < self.data.len());
490        setbits!(self.data[off], 0, 2, balance as u8);
491    }
492
493    /// Get the left child node for node x. Result is zero if there is no child.
494    fn left(&self, x: usize) -> usize {
495        let off = self.over_off(x);
496        let data = &self.data;
497        unsafe_assert!(off + 1 < data.len());
498        data[off + 1] as usize | (getbits!(data[off] as usize, 2, NF) << 8)
499    }
500
501    /// Get the right child node for node x. Result is zero if there is no child.
502    fn right(&self, x: usize) -> usize {
503        let off = self.over_off(x);
504        let data = &self.data;
505        unsafe_assert!(off + 2 < data.len());
506        data[off + 2] as usize | (getbits!(data[off] as usize, 2 + NF, NF) << 8)
507    }
508
509    /// Set the left child node for node x.
510    fn set_left(&mut self, x: usize, y: usize) {
511        let off = self.over_off(x);
512        let data = &mut self.data;
513        unsafe_assert!(off + 1 < data.len());
514        data[off + 1] = (y & 255) as u8;
515        setbits!(data[off], 2, NF, (y >> 8) as u8);
516        debug_assert!(self.left(x) == y);
517    }
518
519    /// Set the right child node for node x.
520    fn set_right(&mut self, x: usize, y: usize) {
521        let off = self.over_off(x);
522        let data = &mut self.data;
523        unsafe_assert!(off + 2 < data.len());
524        data[off + 2] = (y & 255) as u8;
525        setbits!(data[off], 2 + NF, NF, (y >> 8) as u8);
526        debug_assert!(self.right(x) == y);
527    }
528
529    /// Compare record data for node x with record r.
530    fn compare(&self, db: &DB, r: &dyn Record, x: usize) -> Ordering {
531        let off = self.rec_offset(x);
532        let size = self.rec_size();
533        unsafe_assert!(off + size < self.data.len());
534        r.compare(db, &self.data[off..off + size])
535    }
536
537    /// Insert into node x. Result is node and whether tree height increased.
538    fn insert_into(&mut self, mut x: usize, r: Option<(&DB, &dyn Record)>) -> (usize, bool) {
539        let mut height_increased: bool;
540        if x == 0 {
541            x = self.target;
542            self.set_balance(x, Balanced);
543            self.set_left(x, 0);
544            self.set_right(x, 0);
545            height_increased = true;
546        } else {
547            let c = match r {
548                Some((db, r)) => self.compare(db, r, x),
549                None => Ordering::Less,
550            };
551            if c == Ordering::Greater {
552                let p = self.insert_into(self.left(x), r);
553                self.set_left(x, p.0);
554                height_increased = p.1;
555                if height_increased {
556                    let bx = self.balance(x);
557                    if bx == Balanced {
558                        self.set_balance(x, LeftHigher);
559                    } else {
560                        height_increased = false;
561                        if bx == LeftHigher {
562                            return (self.rotate_right(x).0, false);
563                        }
564                        self.set_balance(x, Balanced);
565                    }
566                }
567            } else if c == Ordering::Less {
568                let p = self.insert_into(self.right(x), r);
569                self.set_right(x, p.0);
570                height_increased = p.1;
571                if height_increased {
572                    let bx = self.balance(x);
573                    if bx == Balanced {
574                        self.set_balance(x, RightHigher);
575                    } else {
576                        if bx == RightHigher {
577                            return (self.rotate_left(x).0, false);
578                        }
579                        height_increased = false;
580                        self.set_balance(x, Balanced);
581                    }
582                }
583            } else {
584                panic!("Duplicate key");
585            }
586        }
587        (x, height_increased)
588    }
589
590    /// Rotate right to rebalance tree.
591    fn rotate_right(&mut self, x: usize) -> (usize, bool) {
592        // Left is 2 levels higher than Right.
593        let mut height_decreased = true;
594        let z = self.left(x);
595        let y = self.right(z);
596        let zb = self.balance(z);
597        if zb != RightHigher
598        // Single rotation.
599        {
600            self.set_right(z, x);
601            self.set_left(x, y);
602            if zb == Balanced
603            // Can only occur when deleting Records.
604            {
605                self.set_balance(x, LeftHigher);
606                self.set_balance(z, RightHigher);
607                height_decreased = false;
608            } else {
609                // zb = LeftHigher
610                self.set_balance(x, Balanced);
611                self.set_balance(z, Balanced);
612            }
613            (z, height_decreased)
614        } else {
615            // Double rotation.
616            self.set_left(x, self.right(y));
617            self.set_right(z, self.left(y));
618            self.set_right(y, x);
619            self.set_left(y, z);
620            let yb = self.balance(y);
621            if yb == LeftHigher {
622                self.set_balance(x, RightHigher);
623                self.set_balance(z, Balanced);
624            } else if yb == Balanced {
625                self.set_balance(x, Balanced);
626                self.set_balance(z, Balanced);
627            } else {
628                // yb == RightHigher
629                self.set_balance(x, Balanced);
630                self.set_balance(z, LeftHigher);
631            }
632            self.set_balance(y, Balanced);
633            (y, height_decreased)
634        }
635    }
636
637    /// Rotate left to rebalance tree.
638    fn rotate_left(&mut self, x: usize) -> (usize, bool) {
639        // Right is 2 levels higher than Left.
640        let mut height_decreased = true;
641        let z = self.right(x);
642        let y = self.left(z);
643        let zb = self.balance(z);
644        if zb != LeftHigher
645        // Single rotation.
646        {
647            self.set_left(z, x);
648            self.set_right(x, y);
649            if zb == Balanced
650            // Can only occur when deleting Records.
651            {
652                self.set_balance(x, RightHigher);
653                self.set_balance(z, LeftHigher);
654                height_decreased = false;
655            } else {
656                // zb = RightHigher
657                self.set_balance(x, Balanced);
658                self.set_balance(z, Balanced);
659            }
660            (z, height_decreased)
661        } else {
662            // Double rotation
663            self.set_right(x, self.left(y));
664            self.set_left(z, self.right(y));
665            self.set_left(y, x);
666            self.set_right(y, z);
667            let yb = self.balance(y);
668            if yb == RightHigher {
669                self.set_balance(x, LeftHigher);
670                self.set_balance(z, Balanced);
671            } else if yb == Balanced {
672                self.set_balance(x, Balanced);
673                self.set_balance(z, Balanced);
674            } else {
675                // yb == LeftHigher
676                self.set_balance(x, Balanced);
677                self.set_balance(z, RightHigher);
678            }
679            self.set_balance(y, Balanced);
680            (y, height_decreased)
681        }
682    }
683
684    /// Remove record from tree x.
685    pub fn remove_from(&mut self, db: &DB, mut x: usize, r: &dyn Record) -> (usize, bool) // out bool heightDecreased
686    {
687        if x == 0
688        // key not found.
689        {
690            return (x, false);
691        }
692        let mut height_decreased: bool = true;
693        let compare = self.compare(db, r, x);
694        if compare == Ordering::Equal {
695            let deleted = x;
696            if self.left(x) == 0 {
697                x = self.right(x);
698            } else if self.right(x) == 0 {
699                x = self.left(x);
700            } else {
701                // Remove the smallest element in the right sub-tree and substitute it for x.
702                let t = self.remove_least(self.right(deleted));
703                let right = t.0;
704                x = t.1;
705                height_decreased = t.2;
706                self.set_left(x, self.left(deleted));
707                self.set_right(x, right);
708                self.set_balance(x, self.balance(deleted));
709                if height_decreased {
710                    if self.balance(x) == LeftHigher {
711                        let rr = self.rotate_right(x);
712                        x = rr.0;
713                        height_decreased = rr.1;
714                    } else if self.balance(x) == RightHigher {
715                        self.set_balance(x, Balanced);
716                    } else {
717                        self.set_balance(x, LeftHigher);
718                        height_decreased = false;
719                    }
720                }
721            }
722            self.target = deleted;
723        } else if compare == Ordering::Greater {
724            let rem = self.remove_from(db, self.left(x), r);
725            self.set_left(x, rem.0);
726            height_decreased = rem.1;
727            if height_decreased {
728                let xb = self.balance(x);
729                if xb == RightHigher {
730                    return self.rotate_left(x);
731                }
732                if xb == LeftHigher {
733                    self.set_balance(x, Balanced);
734                } else {
735                    self.set_balance(x, RightHigher);
736                    height_decreased = false;
737                }
738            }
739        } else {
740            let rem = self.remove_from(db, self.right(x), r);
741            self.set_right(x, rem.0);
742            height_decreased = rem.1;
743            if height_decreased {
744                let xb = self.balance(x);
745                if xb == LeftHigher {
746                    return self.rotate_right(x);
747                }
748                if self.balance(x) == RightHigher {
749                    self.set_balance(x, Balanced);
750                } else {
751                    self.set_balance(x, LeftHigher);
752                    height_decreased = false;
753                }
754            }
755        }
756        (x, height_decreased)
757    }
758
759    /// Remove smallest node from tree x. Returns root of tree, removed node and height_decreased.
760    fn remove_least(&mut self, x: usize) -> (usize, usize, bool) {
761        if self.left(x) == 0 {
762            (self.right(x), x, true)
763        } else {
764            let t = self.remove_least(self.left(x));
765            self.set_left(x, t.0);
766            let least = t.1;
767            let mut height_decreased = t.2;
768            if height_decreased {
769                let xb = self.balance(x);
770                if xb == RightHigher {
771                    let rl = self.rotate_left(x);
772                    return (rl.0, least, rl.1);
773                }
774                if xb == LeftHigher {
775                    self.set_balance(x, Balanced);
776                } else {
777                    self.set_balance(x, RightHigher);
778                    height_decreased = false;
779                }
780            }
781            (x, least, height_decreased)
782        }
783    }
784
785    /// Relocate node x (or any child of x) if it is greater than page count ( for fn compress ).
786    fn relocate(&mut self, mut x: usize, flist: &mut Vec<usize>) -> usize {
787        if x != 0 {
788            if x > self.target {
789                let to = flist.pop().unwrap();
790                let n = self.node_size;
791                let src = self.rec_offset(x);
792                let dest = self.rec_offset(to);
793                self.data.copy_within(src..src + n, dest);
794                x = to;
795            }
796            let c = self.left(x);
797            let c1 = self.relocate(c, flist);
798            if c1 != c {
799                self.set_left(x, c1);
800            }
801            let c = self.right(x);
802            let c1 = self.relocate(c, flist);
803            if c1 != c {
804                self.set_right(x, c1);
805            }
806        }
807        x
808    }
809}
rustdb/page.rs

rustdb/
page.rs
