{"header":{"message":"Fully commented implementation of Sized nodes + massive cleanup","description":null,"timestamp":"2021-02-14T22:29:02.363047998Z","authors":[{"full_name":"Pierre-Étienne Meunier","name":"pmeunier"}]},"hash":"TSMS6W4DOKQNUQ4PEMTLOIODR33VFPN6MMNS73ZPSU4BOQVRGPNAC","authors":[],"deps":{"hashes":[["TSMS6W4DOKQNUQ4PEMTLOIODR33VFPN6MMNS73ZPSU4BOQVRGPNAC","Fully commented implementation of Sized nodes + massive cleanup"],["AA",null],["CCNPHVQCIGINWTLXCHOASGVWUPBZXFOLM2F7HTKMEA2DMFTOX7TAC","Cleanup, comments, renaming"],["KM3JAFGPFV7MP7M2LJIYRVAUTU646B3IRXADTRZKOU2RF7LUB62QC","Adding a test for next/prev"],["KMT3MF5NLEQIPZLHCRYDGQ5EA46HJCG3C2ANEPMZGKGHDK77ADPAC","Drop a database"],["ONES3V466GLO5CXKRF5ENK7VFOQPWM3YXLVRGWB56V5SH3W7XNBQC","reference counting works for put"],["7P43FPFAXMDYUIQV7U2DGPN4UI3RNHYFWEUEA22UBDSQTYBJRAQQC","When deleting in internal nodes, set the correct child"],["6DMPXOAT5GQ3BQQOMUZN2GMBQPRA4IB7CCPHTQTIFGO3KWWAKF3QC","More debugging"],["OTWDDJE7TTE73D6BGF4ZN6BH2NFUFLPME2VJ3CPALH463UGWLEIQC","Trait/type cleanup"],["UUUVNC4DWEEL7WV5IRPKPZ6HZMYCPA53XM7LJWICUD4E6GN37IRQC","Debugging/cleanup around cursors"],["YXKP4AIWDBIWBBUDWF66YIPG5ECMHNKEV3PX6KYXOVXY3EWG3WGQC","New file locks, with multiple sets of free pages"],["Q7DRIBBRE4MNG4NP3PVIXAJF5PQYLFWYIVK2O4VVLEO6XY3BOSFQC","Debugging replace (which cannot be del+put)"],["DV4A2LR7Q5LAEGAQHLO34PZCHGJUHPAMRZFGT7GUFNKVQKPJNOYQC","Double-inserts (rebalancing near an internal deletion)"],["KX3WVNZW5KHVEH6EOQTZ4RBEFFJ3SGF5I467X3JWZ74PURRK4HVAC","Testing/debugging \"rebalance causes split of the root\""],["6UVFCERMGSGNRWCVC3GWO5HWV6MSWE433DXBJVC7KRPP6LLJLCSQC","Formatting, debugging, etc."],["EHJFNMB2R4MYG6ZSHHEENRFCSPFVWKVHLD5DXAE5HXUGXP5ZVHKQC","Debugging"],["FMN7X4J24EYPOJNBUWM4NKGWSJTRV2DHCIBMPV2AXLZVVAMNOBKQC","Micro-improvements, now noticeably faster than std::collections::BTreeMap"],["HN6Z5DU4WYMAIOOSNVHLIIMNF6Q53TNJ7YC27SLKWNXVYCTACQKQC","Cleanup"],["QEUTVAZ4F4EJXRDMWDMYXF6XEDMX7YPVG4IIXEKPIR3K54E5W5OAC","Splitting btree::page"],["EAAYH6BQWDK52EC5RG3BEZQU3FJPN5RRRN4U5KDKDVPKXBVJMNDAC","Debugging put"],["OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC","Resetting history"],["H3FVSQIQGFCFKCPXVOSFHP4OSUOBBURJESCZNGQTNDAAD3WQSBEQC","Unsized pages"],["APPY2E7M5NHNC6MFYXSVEKJVAILK7YAZVTVE3W75EK2JNFVS3XBQC","Unsized deletions + custom sizes back"],["LROAI3NBBSCU4T2YA6EHJYKKKL75AU5A7C7WIRCGIQ56S6HPLRXQC","Two iterators (convenience functions), along with tests to move cursors (put and del still destroy cursors though)"],["7WJNSPEWJSJROOYHU6QROWPUZ6WNIOUG2BPSOPDPCK6RG2NQU6OQC","Using the same definition of the \"occupied\" field uniform everywhere"],["XEU2QVLCHPYOOD4TQIPEEVYOVSFMKFPLJYWEJYXYJAZ7S54KWDZAC","Debugging after plugging this into Pijul"],["PXF3R6SVXJXN2NMLMWNY5OFV5QYVE2VZTLGIZDZVK5ZVLFTVSSWQC","Improving test coverage for btree::cursor"],["UAQX27N4PI4LHEW6LSHJETIE5MV7JTEMPLTJFYUBMYVPC43H7VOAC","Tests"],["WS4ZQM4RMIHZ6XZKSDQJGHN5SSSWFL4H236USOPUA33S6RC53RFAC","Debugging, tests, etc."],["X3QVVQIS7B7L3XYZAWL3OOBUXOJ6RMOKQ45YMLLGAHYPEEKZ45ZAC","More debugging (del seems to work now)"],["73Z2UB3JGRLFNFORE7D64O4IHIFSZASD4G4FLJ4FJLHANT75MGIAC","Cleanup + comments"],["RV2L6CZWTMUQ2A52YDAFVHDFGURZL3H4SSCDC347UGN23D3J5KZQC","A few comments"],["ESUI5EUZUBDPHNN3APU33IFORYPYR6J3WEMEZG57FKF3EH66ZBHAC","Making as_page() unsafe"],["LSQ6V7M66TEGLJ7QBLRVDX4E7UKJTDQTEXZOS3KGPGFKVXNLPKBQC","Cleanup + docs"],["OFINGD26ZWCRDVVDI2ZIBLMHXKEMJA6MRNLANJYUHQPIJLPA7J2AC","implementing prev() on cursors (+ some cleanup)"],["6DCQHIFPEH4GZKSRRS32GMKDRPZH4MTCGOUEI7YEUVKWENBF3JWAC","Minor changes after benchmarking"],["T73WR2BX2QDQ6APOREBXUKNH52FDLJNBGWPQUYB2TAF2PT7XCL2AC","Cleaner RC increments for keys and values containing references + more comments in `del`"],["MSRWB47YP6L5BVTS53QQPBOHY5SXTSTR5KD6IIF35UWCTEUOCQWQC","Deletions at immutable leaves weren't really deleting anything"],["QYDGYIZRNFRIQD7RUCY5YAN3F2THZA74E5UOHPIFWSULEJFAFVJQC","Split trait Representable into its mandatory part and an optional part"],["AOX2XQISHGWNNAFBYRN44Q6AWG7H5DPBK5YMFHK42HQNZ2TMHEJQC","Actually, with the correct functions, Unsized pages are always slower than Sized pages (especially for writing)"],["W26CFMAQOXMUK4ZOJMAN4SMBXMWFQHO7HCTEVW73FQSRMJZFGJIQC","Improving safety of cursors"],["NXMFNPZ7VWJRLC3M5QJJVTICXCMGE24F3HVIZA7A7RLVMLQMLDVQC","Comments + debugging drop"]],"deps":["CCNPHVQCIGINWTLXCHOASGVWUPBZXFOLM2F7HTKMEA2DMFTOX7TAC"],"known":["OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC","FMN7X4J24EYPOJNBUWM4NKGWSJTRV2DHCIBMPV2AXLZVVAMNOBKQC","EHJFNMB2R4MYG6ZSHHEENRFCSPFVWKVHLD5DXAE5HXUGXP5ZVHKQC","WS4ZQM4RMIHZ6XZKSDQJGHN5SSSWFL4H236USOPUA33S6RC53RFAC","EAAYH6BQWDK52EC5RG3BEZQU3FJPN5RRRN4U5KDKDVPKXBVJMNDAC","ONES3V466GLO5CXKRF5ENK7VFOQPWM3YXLVRGWB56V5SH3W7XNBQC","PXF3R6SVXJXN2NMLMWNY5OFV5QYVE2VZTLGIZDZVK5ZVLFTVSSWQC","UAQX27N4PI4LHEW6LSHJETIE5MV7JTEMPLTJFYUBMYVPC43H7VOAC","X3QVVQIS7B7L3XYZAWL3OOBUXOJ6RMOKQ45YMLLGAHYPEEKZ45ZAC","YXKP4AIWDBIWBBUDWF66YIPG5ECMHNKEV3PX6KYXOVXY3EWG3WGQC","DV4A2LR7Q5LAEGAQHLO34PZCHGJUHPAMRZFGT7GUFNKVQKPJNOYQC","QEUTVAZ4F4EJXRDMWDMYXF6XEDMX7YPVG4IIXEKPIR3K54E5W5OAC","6DMPXOAT5GQ3BQQOMUZN2GMBQPRA4IB7CCPHTQTIFGO3KWWAKF3QC","OTWDDJE7TTE73D6BGF4ZN6BH2NFUFLPME2VJ3CPALH463UGWLEIQC","H3FVSQIQGFCFKCPXVOSFHP4OSUOBBURJESCZNGQTNDAAD3WQSBEQC","6UVFCERMGSGNRWCVC3GWO5HWV6MSWE433DXBJVC7KRPP6LLJLCSQC","APPY2E7M5NHNC6MFYXSVEKJVAILK7YAZVTVE3W75EK2JNFVS3XBQC","AOX2XQISHGWNNAFBYRN44Q6AWG7H5DPBK5YMFHK42HQNZ2TMHEJQC","KMT3MF5NLEQIPZLHCRYDGQ5EA46HJCG3C2ANEPMZGKGHDK77ADPAC","W26CFMAQOXMUK4ZOJMAN4SMBXMWFQHO7HCTEVW73FQSRMJZFGJIQC","UUUVNC4DWEEL7WV5IRPKPZ6HZMYCPA53XM7LJWICUD4E6GN37IRQC","6DCQHIFPEH4GZKSRRS32GMKDRPZH4MTCGOUEI7YEUVKWENBF3JWAC","KX3WVNZW5KHVEH6EOQTZ4RBEFFJ3SGF5I467X3JWZ74PURRK4HVAC","7WJNSPEWJSJROOYHU6QROWPUZ6WNIOUG2BPSOPDPCK6RG2NQU6OQC","OFINGD26ZWCRDVVDI2ZIBLMHXKEMJA6MRNLANJYUHQPIJLPA7J2AC","KM3JAFGPFV7MP7M2LJIYRVAUTU646B3IRXADTRZKOU2RF7LUB62QC","LROAI3NBBSCU4T2YA6EHJYKKKL75AU5A7C7WIRCGIQ56S6HPLRXQC","XEU2QVLCHPYOOD4TQIPEEVYOVSFMKFPLJYWEJYXYJAZ7S54KWDZAC","T73WR2BX2QDQ6APOREBXUKNH52FDLJNBGWPQUYB2TAF2PT7XCL2AC","MSRWB47YP6L5BVTS53QQPBOHY5SXTSTR5KD6IIF35UWCTEUOCQWQC","7P43FPFAXMDYUIQV7U2DGPN4UI3RNHYFWEUEA22UBDSQTYBJRAQQC","Q7DRIBBRE4MNG4NP3PVIXAJF5PQYLFWYIVK2O4VVLEO6XY3BOSFQC","73Z2UB3JGRLFNFORE7D64O4IHIFSZASD4G4FLJ4FJLHANT75MGIAC","NXMFNPZ7VWJRLC3M5QJJVTICXCMGE24F3HVIZA7A7RLVMLQMLDVQC","RV2L6CZWTMUQ2A52YDAFVHDFGURZL3H4SSCDC347UGN23D3J5KZQC","HN6Z5DU4WYMAIOOSNVHLIIMNF6Q53TNJ7YC27SLKWNXVYCTACQKQC","ESUI5EUZUBDPHNN3APU33IFORYPYR6J3WEMEZG57FKF3EH66ZBHAC","LSQ6V7M66TEGLJ7QBLRVDX4E7UKJTDQTEXZOS3KGPGFKVXNLPKBQC","QYDGYIZRNFRIQD7RUCY5YAN3F2THZA74E5UOHPIFWSULEJFAFVJQC"]},"hunks":[{"Replacement":{"inode":{"change":3,"pos":91},"path":"sanakirja-core/src/lib.rs","line":284,"ins":{"up_context":[{"change":3,"pos":201}],"down_context":[{"change":2,"pos":3112}],"flag":"BLOCK","start":0,"end":74,"inode":{"change":3,"pos":91}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":201},"to":{"change":2,"start":3044,"end":3112},"introduced_by":2}],"inode":{"change":3,"pos":91}},"ins_contents":[{"Add":" /// Same as [`Self::decr_rc`], but for pages allocated by the current"}],"del_contents":[{"Del":" /// Same as [`decr_rc`], but for pages allocated by the current\n"}]}},{"Edit":{"inode":{"change":3,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":1,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":3448}],"down_context":[{"change":3,"pos":3927}],"flag":"BLOCK","start":75,"end":105,"inode":{"change":3,"pos":3448}}},"contents":[{"Add":"//! Insertions into a B tree."}]}},{"Edit":{"inode":{"change":3,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":4,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":3963}],"down_context":[{"change":3,"pos":3975}],"flag":"BLOCK","start":106,"end":349,"inode":{"change":3,"pos":3448}}},"contents":[{"Add":""},{"Add":"/// The representation of the update to a page."},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Ok {"},{"Add":" /// The new page, possibly the same as the previous version."},{"Add":" pub page: MutPage,"},{"Add":" /// The freed page, or 0 if no page was freed."},{"Add":" pub freed: u64,"},{"Add":"}"}]}},{"Edit":{"inode":{"change":3,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":14,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":3976}],"down_context":[{"change":3,"pos":0}],"flag":"BLOCK","start":350,"end":629,"inode":{"change":3,"pos":3448}}},"contents":[{"Add":"/// The result of an insertion, i.e. either an update or a split."},{"Add":"#[derive(Debug)]"},{"Add":"pub enum Put<'a, K: ?Sized, V: ?Sized> {"},{"Add":" Ok(Ok),"},{"Add":" Split {"},{"Add":" split_key: &'a K,"},{"Add":" split_value: &'a V,"},{"Add":" left: MutPage,"},{"Add":" right: MutPage,"},{"Add":" freed: u64,"},{"Add":" },"},{"Add":"}"},{"Add":""}]}},{"Replacement":{"inode":{"change":3,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":45,"ins":{"up_context":[{"change":3,"pos":44}],"down_context":[{"change":3,"pos":193}],"flag":"BLOCK","start":630,"end":684,"inode":{"change":3,"pos":3448}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":44},"to":{"change":3,"start":4355,"end":4417},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4355},"to":{"change":3,"start":4355,"end":4417},"introduced_by":3}],"inode":{"change":3,"pos":3448}},"ins_contents":[{"Add":" if cursor.set(txn, key, Some(value))?.is_some() {"}],"del_contents":[{"Del":" if cursor.set(txn, Some((key, Some(value))))?.is_some() {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":55,"ins":{"up_context":[{"change":3,"pos":1970}],"down_context":[{"change":3,"pos":2014}],"flag":"BLOCK","start":685,"end":731,"inode":{"change":3,"pos":3448}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1970},"to":{"change":3,"start":1970,"end":2014},"introduced_by":3}],"inode":{"change":3,"pos":3448}},"ins_contents":[{"Add":" let is_owned = p < cursor.first_rc_len();"}],"del_contents":[{"Del":" let is_owned = p < cursor.first_rc_len;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":128,"ins":{"up_context":[{"change":3,"pos":1770}],"down_context":[{"change":3,"pos":2310}],"flag":"BLOCK","start":732,"end":801,"inode":{"change":3,"pos":3448}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1770},"to":{"change":3,"start":2243,"end":2310},"introduced_by":3}],"inode":{"change":3,"pos":3448}},"ins_contents":[{"Add":" let is_owned = cursor.len() < cursor.first_rc_len();"}],"del_contents":[{"Del":" let is_owned = cursor.len() < cursor.first_rc_len;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":182,"ins":{"up_context":[{"change":3,"pos":2656}],"down_context":[{"change":3,"pos":2899}],"flag":"BLOCK","start":802,"end":871,"inode":{"change":3,"pos":3448}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2656},"to":{"change":3,"start":2832,"end":2899},"introduced_by":3}],"inode":{"change":3,"pos":3448}},"ins_contents":[{"Add":" let is_owned = cursor.len() < cursor.first_rc_len();"}],"del_contents":[{"Del":" let is_owned = cursor.len() < cursor.first_rc_len;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":214,"ins":{"up_context":[{"change":3,"pos":7700}],"down_context":[{"change":3,"pos":2893}],"flag":"BLOCK","start":872,"end":918,"inode":{"change":3,"pos":3448}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7700},"to":{"change":3,"start":2986,"end":3030},"introduced_by":3}],"inode":{"change":3,"pos":3448}},"ins_contents":[{"Add":" if cursor.len() < cursor.first_rc_len() {"}],"del_contents":[{"Del":" if cursor.len() < cursor.first_rc_len {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":3448},"path":"sanakirja-core/src/btree/put.rs","line":222,"ins":{"up_context":[{"change":3,"pos":3172}],"down_context":[{"change":3,"pos":7918}],"flag":"BLOCK","start":919,"end":970,"inode":{"change":3,"pos":3448}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3172},"to":{"change":3,"start":3068,"end":3117},"introduced_by":3}],"inode":{"change":3,"pos":3448}},"ins_contents":[{"Add":" if cursor.len() == cursor.first_rc_len() {"}],"del_contents":[{"Del":" if cursor.len() == cursor.first_rc_len {\n"}]}},{"Edit":{"inode":{"change":3,"pos":2014},"path":"sanakirja-core/src/btree/page_unsized.rs","line":2,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":2029}],"down_context":[{"change":3,"pos":2029}],"flag":"BLOCK","start":971,"end":1023,"inode":{"change":3,"pos":2014}}},"contents":[{"Add":"use crate::btree::del::*;"},{"Add":"use crate::btree::put::*;"}]}},{"Edit":{"inode":{"change":3,"pos":2014},"path":"sanakirja-core/src/btree/page_unsized.rs","line":27,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2521},"to":{"change":3,"start":2521,"end":2556},"introduced_by":3}],"inode":{"change":3,"pos":2014}}},"contents":[{"Del":" debug!(\"init {:?}\", page);\n"}]}},{"Edit":{"inode":{"change":3,"pos":2014},"path":"sanakirja-core/src/btree/page_unsized.rs","line":29,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2608},"to":{"change":3,"start":2608,"end":2641},"introduced_by":3}],"inode":{"change":3,"pos":2014}}},"contents":[{"Del":" debug!(\"init: {:?}\", h);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":2014},"path":"sanakirja-core/src/btree/page_unsized.rs","line":36,"ins":{"up_context":[{"change":3,"pos":147}],"down_context":[{"change":3,"pos":236}],"flag":"BLOCK","start":1024,"end":1113,"inode":{"change":3,"pos":2014}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":147},"to":{"change":3,"start":111,"end":204},"introduced_by":3}],"inode":{"change":3,"pos":2014}},"ins_contents":[{"Add":" unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {"},{"Add":" (&*s.0, &*s.1)"}],"del_contents":[{"Del":" fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {\n unsafe { (&*s.0, &*s.1) }\n"}]}},{"Replacement":{"inode":{"change":3,"pos":2014},"path":"sanakirja-core/src/btree/page_unsized.rs","line":51,"ins":{"up_context":[{"change":3,"pos":3866}],"down_context":[{"change":3,"pos":381}],"flag":"BLOCK","start":1114,"end":1176,"inode":{"change":3,"pos":2014}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3866},"to":{"change":3,"start":3866,"end":3909},"introduced_by":3}],"inode":{"change":3,"pos":2014}},"ins_contents":[{"Add":" ) -> Result, T::Error> {"}],"del_contents":[{"Del":" ) -> Result, T::Error> {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":2014},"path":"sanakirja-core/src/btree/page_unsized.rs","line":88,"ins":{"up_context":[{"change":3,"pos":4734}],"down_context":[{"change":3,"pos":4766}],"flag":"BLOCK","start":1177,"end":1228,"inode":{"change":3,"pos":2014}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4734},"to":{"change":3,"start":4734,"end":4766},"introduced_by":3}],"inode":{"change":3,"pos":2014}},"ins_contents":[{"Add":" ) -> Result {"}],"del_contents":[{"Del":" ) -> Result {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":2014},"path":"sanakirja-core/src/btree/page_unsized.rs","line":385,"ins":{"up_context":[{"change":3,"pos":15095}],"down_context":[{"change":3,"pos":15112}],"flag":"BLOCK","start":1229,"end":1249,"inode":{"change":3,"pos":2014}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15095},"to":{"change":3,"start":15095,"end":15112},"introduced_by":3}],"inode":{"change":3,"pos":2014}},"ins_contents":[{"Add":" txn: &'a T,"}],"del_contents":[{"Del":" txn: &T,\n"}]}},{"Edit":{"inode":{"change":3,"pos":2014},"path":"sanakirja-core/src/btree/page_unsized.rs","line":392,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":15266}],"down_context":[{"change":3,"pos":15266}],"flag":"BLOCK","start":1250,"end":1569,"inode":{"change":3,"pos":2014}}},"contents":[{"Add":" // `lookup` has the same semantic as"},{"Add":" // `core::slice::binary_search`, i.e. it returns either"},{"Add":" // `Ok(n)`, where `n` is the position where `(k0, v0)` was"},{"Add":" // found, or `Err(n)` where `n` is the position where"},{"Add":" // `(k0, v0)` can be inserted to preserve the order."}]}},{"Replacement":{"inode":{"change":3,"pos":27023},"path":"sanakirja-core/src/btree/page_unsized/put.rs","line":21,"ins":{"up_context":[{"change":3,"pos":27358}],"down_context":[{"change":3,"pos":27397}],"flag":"BLOCK","start":1570,"end":1628,"inode":{"change":3,"pos":27023}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":27358},"to":{"change":3,"start":27358,"end":27397},"introduced_by":3}],"inode":{"change":3,"pos":27023}},"ins_contents":[{"Add":") -> Result, T::Error> {"}],"del_contents":[{"Del":") -> Result, T::Error> {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":27023},"path":"sanakirja-core/src/btree/page_unsized/put.rs","line":108,"ins":{"up_context":[{"change":3,"pos":29538}],"down_context":[{"change":3,"pos":3235}],"flag":"BLOCK","start":1629,"end":1687,"inode":{"change":3,"pos":27023}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":29538},"to":{"change":3,"start":29538,"end":29577},"introduced_by":3}],"inode":{"change":3,"pos":27023}},"ins_contents":[{"Add":") -> Result, T::Error> {"}],"del_contents":[{"Del":") -> Result, T::Error> {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":15503},"path":"sanakirja-core/src/btree/page_unsized/header.rs","line":14,"ins":{"up_context":[{"change":3,"pos":15659}],"down_context":[{"change":3,"pos":2621}],"flag":"BLOCK","start":1688,"end":1749,"inode":{"change":3,"pos":15503}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15659},"to":{"change":3,"start":2560,"end":2621},"introduced_by":3}],"inode":{"change":3,"pos":15503}},"ins_contents":[{"Add":" self.data = (((PAGE_SIZE as u16) << 3) | 1).to_le();"}],"del_contents":[{"Del":" self.data = (((PAGE_SIZE as u16) << 1) | 1).to_le();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":15503},"path":"sanakirja-core/src/btree/page_unsized/header.rs","line":41,"ins":{"up_context":[{"change":3,"pos":16289}],"down_context":[{"change":3,"pos":16321}],"flag":"BLOCK","start":1750,"end":1787,"inode":{"change":3,"pos":15503}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":16289},"to":{"change":3,"start":2743,"end":2780},"introduced_by":3}],"inode":{"change":3,"pos":15503}},"ins_contents":[{"Add":" u16::from_le(self.data) >> 3"}],"del_contents":[{"Del":" u16::from_le(self.data) >> 1\n"}]}},{"Replacement":{"inode":{"change":3,"pos":15503},"path":"sanakirja-core/src/btree/page_unsized/header.rs","line":45,"ins":{"up_context":[{"change":3,"pos":16369}],"down_context":[{"change":3,"pos":16399}],"flag":"BLOCK","start":1788,"end":1884,"inode":{"change":3,"pos":15503}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":16369},"to":{"change":3,"start":2781,"end":2877},"introduced_by":3}],"inode":{"change":3,"pos":15503}},"ins_contents":[{"Add":" let dirty = u16::from_le(self.data) & 7;"},{"Add":" self.data = ((d << 3) | dirty).to_le()"}],"del_contents":[{"Del":" let dirty = u16::from_le(self.data) & 1;\n self.data = ((d << 1) | dirty).to_le()\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":1,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":8623}],"down_context":[{"change":3,"pos":8624}],"flag":"BLOCK","start":1885,"end":4602,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":"//! Implementation of B tree pages for Sized types, i.e. types whose"},{"Add":"//! representation has a size known at compile time (and the same as"},{"Add":"//! `core::mem::size_of()`)."},{"Add":"//!"},{"Add":"//! The details of the implementation are as follows:"},{"Add":"//!"},{"Add":"//! - The page starts with a 16 bytes header of the following form"},{"Add":"//! (where all the fields are encoded in Little-Endian):"},{"Add":"//!"},{"Add":"//! ```"},{"Add":"//! #[repr(C)]"},{"Add":"//! pub struct Header {"},{"Add":""},{"Add":"//! /// Offset to the first entry in the page, shifted 3 bits"},{"Add":"//! /// to the right to allow for the dirty bit (plus two"},{"Add":"//! /// extra bits, zero for now), as explained in the"},{"Add":"//! /// documentation of CowPage, at the root of this"},{"Add":"//! /// crate. This is 4096 for empty pages, and it is unused"},{"Add":"//! /// for leaves. Moreover, this field can't be increased:"},{"Add":"//! /// when it reaches the bottom, the page must be cloned."},{"Add":"//! data: u16,"},{"Add":"//! /// Number of entries on the page."},{"Add":"//! n: u16,"},{"Add":"//! /// CRC (if used)."},{"Add":"//! crc: u32,"},{"Add":""},{"Add":"//! /// The 52 most significant bits are the left child of"},{"Add":"//! /// this page (0 for leaves), while the 12 LSBs represent"},{"Add":"//! /// the space this page would take when cloned from scratch,"},{"Add":"//! /// minus the header. The reason for this is that entries"},{"Add":"//! /// in internal nodes aren't really removed when deleted,"},{"Add":"//! /// they're only \"unlinked\" from the array of offsets (see"},{"Add":"//! /// below). Therefore, we must have a way to tell when a"},{"Add":"//! /// page can be \"compacted\" to reclaim space."},{"Add":""},{"Add":"//! left_page: u64,"},{"Add":"//! }"},{"Add":"//! ```"},{"Add":""},{"Add":"//! - For leaves, the rest of the page has the same representation as"},{"Add":"//! an array of length `n`, of elements of type `Tuple`:"},{"Add":"//! ```"},{"Add":"//! #[repr(C)]"},{"Add":"//! struct Tuple {"},{"Add":"//! k: K,"},{"Add":"//! v: V,"},{"Add":"//! }"},{"Add":"//! ```"},{"Add":"//! If the alignment of that structure is more than 16 bytes, we"},{"Add":"//! need to add some padding between the header and that array."},{"Add":""},{"Add":"//! - For internal nodes, the rest of the page starts with an array of"},{"Add":"//! length `n` of Little-Endian-encoded `u64`, where the 12 least"},{"Add":"//! significant bits of each `u64` are an offset to a `Tuple` in"},{"Add":"//! the page, and the 52 other bits are an offset in the file to the"},{"Add":"//! right child of the entry."},{"Add":"//!"},{"Add":"//! Moreover, the offset represented by the 12 LSBs is after (or at)"},{"Add":"//! `header.data`."},{"Add":""},{"Add":"//! We say we can \"allocate\" in the page if the `data` of the header"},{"Add":"//! is greater than or equal to the position of the last \"offset\","},{"Add":"//! plus the size we want to allocate (note that since we allocate"},{"Add":"//! from the end of the page, `data` is always a multiple of the"},{"Add":"//! alignment of `Tuple`)."},{"Add":""}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":68,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":8638}],"down_context":[{"change":3,"pos":244}],"flag":"BLOCK","start":4603,"end":4655,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":"use crate::btree::del::*;"},{"Add":"use crate::btree::put::*;"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":73,"ins":{"up_context":[{"change":3,"pos":8651}],"down_context":[{"change":3,"pos":20}],"flag":"BLOCK","start":4656,"end":4948,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":9},"to":{"change":3,"start":9,"end":20},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":20},"to":{"change":3,"start":4992,"end":5001},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":"mod alloc; // The \"alloc\" trait, to provide common methods for leaves and internal nodes."},{"Add":""},{"Add":"mod put; // Inserting a new value onto a page (possibly splitting the page)."},{"Add":""},{"Add":"mod rebalance; // Rebalance two sibling pages to the left or to the right."},{"Add":""},{"Add":"use super::page_unsized::{header, PageCursor};"}],"del_contents":[{"Del":"mod alloc;\n"},{"Del":"mod put;\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":82,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":61},"to":{"change":3,"start":61,"end":76},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":76},"to":{"change":3,"start":3234,"end":3267},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":3267},"to":{"change":3,"start":928,"end":969},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":94},"to":{"change":3,"start":928,"end":969},"introduced_by":3}],"inode":{"change":3,"pos":8623}}},"contents":[{"Del":"mod rebalance;\n"},{"Del":"use super::page_unsized::header;\n"},{"Del":"pub use super::page_unsized::PageCursor;\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":96,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":8683}],"down_context":[{"change":3,"pos":8683}],"flag":"BLOCK","start":4949,"end":5009,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":"/// Empty type implementing `BTreePage` and `BTreeMutPage`."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":101,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":4796}],"down_context":[{"change":3,"pos":2311}],"flag":"BLOCK","start":5010,"end":5476,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // Cursors are quite straightforward. One non-trivial thing is"},{"Add":" // that they represent both a position on a page and the interval"},{"Add":" // from that position to the end of the page, as is apparent in"},{"Add":" // their `split_at` method."},{"Add":" //"},{"Add":" // Another thing to note is that -1 and `c.total` are valid"},{"Add":" // positions for a cursor `c`. The reason for this is that"},{"Add":" // position `-1` has a right child (which is the left child of the"},{"Add":" // first element)."},{"Add":""}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":128,"ins":{"up_context":[{"change":3,"pos":2709}],"down_context":[{"change":3,"pos":3963}],"flag":"BLOCK","start":5477,"end":5728,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2709},"to":{"change":3,"start":2709,"end":2742},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2742},"to":{"change":3,"start":4797,"end":4815},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":4815},"to":{"change":3,"start":2759,"end":2855},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2759},"to":{"change":3,"start":2759,"end":2855},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2855},"to":{"change":3,"start":2855,"end":2954},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2954},"to":{"change":3,"start":7103,"end":7160},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7160},"to":{"change":3,"start":2996,"end":3020},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2996},"to":{"change":3,"start":2996,"end":3020},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3020},"to":{"change":3,"start":4816,"end":4879},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":4879},"to":{"change":3,"start":3069,"end":3200},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3069},"to":{"change":3,"start":3069,"end":3200},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3200},"to":{"change":3,"start":4880,"end":5009},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5009},"to":{"change":3,"start":3470,"end":3648},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3470},"to":{"change":3,"start":3470,"end":3648},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3648},"to":{"change":3,"start":5010,"end":5160},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5160},"to":{"change":3,"start":3939,"end":3963},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3939},"to":{"change":3,"start":3939,"end":3963},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":""},{"Add":" fn split_at(c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {"},{"Add":" ("},{"Add":" PageCursor {"},{"Add":" cur: 0,"},{"Add":" total: c.cur.max(0) as usize,"},{"Add":" is_leaf: c.is_leaf,"},{"Add":" },"},{"Add":" *c,"},{"Add":" )"}],"del_contents":[{"Del":" fn current<'a, T: LoadPage>(\n"},{"Del":" _txn: &T,\n"},{"Del":" page: crate::Page<'a>,\n c: &Self::Cursor,\n ) -> Option<(&'a K, &'a V, u64)> {\n"},{"Del":" if c.cur < 0 || c.cur >= c.total as isize {\n None\n } else if c.is_leaf {\n"},{"Del":" let f = core::mem::size_of::>();\n"},{"Del":" let off = {\n"},{"Del":" let al = core::mem::align_of::>();\n"},{"Del":" let hdr = (HDR + al - 1) & !(al - 1);\n hdr + c.cur as usize * f\n };\n unsafe {\n"},{"Del":" let kv = &*(page.data.as_ptr().add(off as usize) as *const Tuple);\n Some((&kv.k, &kv.v, 0))\n"},{"Del":" }\n } else {\n unsafe {\n let off =\n u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur as usize));\n"},{"Del":" let kv = &*(page.data.as_ptr().add((off as usize) & 0xfff) as *const Tuple);\n Some((&kv.k, &kv.v, off & !0xfff))\n"},{"Del":" }\n }\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":163,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":4803}],"down_context":[{"change":3,"pos":4803}],"flag":"BLOCK","start":5729,"end":8219,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // This is the first non-trivial method, let's explain it."},{"Add":" fn current<'a, T: LoadPage>("},{"Add":" _txn: &T,"},{"Add":" page: crate::Page<'a>,"},{"Add":" c: &Self::Cursor,"},{"Add":" ) -> Option<(&'a K, &'a V, u64)> {"},{"Add":" // First, there's no current entry if the cursor is outside"},{"Add":" // the range of entries."},{"Add":" if c.cur < 0 || c.cur >= c.total as isize {"},{"Add":" None"},{"Add":" } else if c.is_leaf {"},{"Add":" // Else, if this is a leaf, the elements are packed"},{"Add":" // together in a contiguous array."},{"Add":" //"},{"Add":" // This means that the header may be followed by"},{"Add":" // padding. These are constants known at compile-time, by"},{"Add":" // the way, so `al` and `hdr` are optimised away by the"},{"Add":" // compiler."},{"Add":" let al = core::mem::align_of::>();"},{"Add":""},{"Add":" // The following is a way to compute the first multiple of"},{"Add":" // `al` after `HDR`, assuming `al` is a power of 2 (which"},{"Add":" // is always the case since we get it from `align_of`)."},{"Add":" let hdr = (HDR + al - 1) & !(al - 1);"},{"Add":""},{"Add":" // The position of the `Tuple` we're looking for is"},{"Add":" // `f * cur` bytes after the padded header:"},{"Add":" let f = core::mem::size_of::>();"},{"Add":" let kv = unsafe {"},{"Add":" &*(page.data.as_ptr().add(hdr + c.cur as usize * f) as *const Tuple)"},{"Add":" };"},{"Add":" Some((&kv.k, &kv.v, 0))"},{"Add":" } else {"},{"Add":" // Internal nodes have an extra level of indirection: we"},{"Add":" // first need to find `off`, the offset in the page, in"},{"Add":" // the initial array of offsets. Since these offsets are"},{"Add":" // `u64`, and the header is of size 16 bytes, the array is"},{"Add":" // already aligned."},{"Add":" unsafe {"},{"Add":" let off ="},{"Add":" u64::from_le(*(page.data.as_ptr().add(HDR + 8 * c.cur as usize) as *const u64));"},{"Add":""},{"Add":" // Check that we aren't reading outside of the page"},{"Add":" // (for example because of a malformed offset)."},{"Add":" assert!((off as usize & 0xfff) + core::mem::size_of::>() <= 4096);"},{"Add":""},{"Add":" // Once we have the offset, cast its 12 LSBs to a"},{"Add":" // position in the page, and read the `Tuple` at"},{"Add":" // that position."},{"Add":" let kv = &*(page.data.as_ptr().add((off as usize) & 0xfff) as *const Tuple);"},{"Add":" Some((&kv.k, &kv.v, off & !0xfff))"},{"Add":" }"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":220,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":4819}],"down_context":[{"change":3,"pos":4819}],"flag":"BLOCK","start":8220,"end":8601,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":""},{"Add":" // The left and right child methods aren't really surprising. One"},{"Add":" // thing to note is that cursors are always in positions between"},{"Add":" // `-1` and `c.total` (bounds included), so we only have to check"},{"Add":" // one side of the bound in the assertions."},{"Add":" //"},{"Add":" // We also check, before entering the `unsafe` sections, that"},{"Add":" // we're only reading data that is on a page."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":229,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4883},"to":{"change":3,"start":4883,"end":4912},"introduced_by":3}],"inode":{"change":3,"pos":8623}}},"contents":[{"Del":" assert!(c.cur >= 0);\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":232,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":4966}],"down_context":[{"change":3,"pos":4966}],"flag":"BLOCK","start":8602,"end":8675,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" assert!(c.cur >= 0 && HDR as isize + c.cur * 8 - 8 <= 4088);"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":239,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5208},"to":{"change":3,"start":5208,"end":5251},"introduced_by":3}],"inode":{"change":3,"pos":8623}}},"contents":[{"Del":" assert!(c.cur < c.total as isize);\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":242,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":5305}],"down_context":[{"change":3,"pos":5305}],"flag":"BLOCK","start":8676,"end":8763,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" assert!(c.cur < c.total as isize && HDR as isize + c.cur * 8 - 8 <= 4088);"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":248,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":5479}],"down_context":[{"change":3,"pos":5479}],"flag":"BLOCK","start":8764,"end":8765,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":""}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":250,"ins":{"up_context":[{"change":3,"pos":5515}],"down_context":[{"change":3,"pos":5532}],"flag":"BLOCK","start":8766,"end":8786,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5515},"to":{"change":3,"start":5515,"end":5532},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" txn: &'a T,"}],"del_contents":[{"Del":" txn: &T,\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":257,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":5690}],"down_context":[{"change":3,"pos":5690}],"flag":"BLOCK","start":8787,"end":9106,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // `lookup` has the same semantic as"},{"Add":" // `core::slice::binary_search`, i.e. it returns either"},{"Add":" // `Ok(n)`, where `n` is the position where `(k0, v0)` was"},{"Add":" // found, or `Err(n)` where `n` is the position where"},{"Add":" // `(k0, v0)` can be inserted to preserve the order."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":263,"ins":{"up_context":[{"change":3,"pos":5745}],"down_context":[{"change":3,"pos":5804}],"flag":"BLOCK","start":9107,"end":9134,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5745},"to":{"change":3,"start":5745,"end":5804},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" match lookup {"}],"del_contents":[{"Del":" let result;\n c.cur = match lookup {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":265,"ins":{"up_context":[{"change":3,"pos":5831}],"down_context":[{"change":3,"pos":7214}],"flag":"BLOCK","start":9135,"end":9310,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5831},"to":{"change":3,"start":5831,"end":5875},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" c.cur = n as isize;"},{"Add":" // Just read the tuple, as we did multiple times"},{"Add":" // before."},{"Add":" if c.is_leaf {"}],"del_contents":[{"Del":" result = if c.is_leaf {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":270,"ins":{"up_context":[{"change":3,"pos":7283}],"down_context":[{"change":3,"pos":6236}],"flag":"BLOCK","start":9311,"end":9627,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":7283},"to":{"change":3,"start":5929,"end":5965},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5929},"to":{"change":3,"start":5929,"end":5965},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5965},"to":{"change":3,"start":5372,"end":5447},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5447},"to":{"change":3,"start":6026,"end":6183},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6026},"to":{"change":3,"start":6026,"end":6183},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6183},"to":{"change":3,"start":6183,"end":6236},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" let al = core::mem::align_of::>();"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" let tup ="},{"Add":" &*(page.data.as_ptr().add(hdr_size + f * n) as *const Tuple);"},{"Add":" Ok((&tup.k, &tup.v, 0))"}],"del_contents":[{"Del":" let off = {\n"},{"Del":" let al = core::mem::align_of::>();\n"},{"Del":" let hdr_size = (HDR + al - 1) & !(al - 1);\n (0, (hdr_size + f * n) as u16)\n };\n"},{"Del":" Ok(Leaf::kv(txn, page, off))\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":278,"ins":{"up_context":[{"change":3,"pos":6395}],"down_context":[{"change":3,"pos":6650}],"flag":"BLOCK","start":9628,"end":9843,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6395},"to":{"change":3,"start":6395,"end":6596},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6596},"to":{"change":3,"start":6596,"end":6650},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" let tup ="},{"Add":" &*(page.data.as_ptr().add(off as usize & 0xfff) as *const Tuple);"},{"Add":" Ok((&tup.k, &tup.v, off & !0xfff))"},{"Add":" }"}],"del_contents":[{"Del":" Ok(Internal::kv(\n txn,\n page,\n (off & !0xfff, (off & 0xfff) as u16),\n ))\n"},{"Del":" };\n n as isize\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":284,"ins":{"up_context":[{"change":3,"pos":6696}],"down_context":[{"change":3,"pos":6764}],"flag":"BLOCK","start":9844,"end":9911,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6696},"to":{"change":3,"start":6696,"end":6764},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" c.cur = n as isize;"},{"Add":" Err(n)"}],"del_contents":[{"Del":" result = Err(n);\n n as isize\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":287,"ins":{"up_context":[{"change":3,"pos":6782}],"down_context":[{"change":3,"pos":6816}],"flag":"BLOCK","start":9912,"end":9926,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6782},"to":{"change":3,"start":6782,"end":6816},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" }"}],"del_contents":[{"Del":" };\n result\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":289,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6826},"to":{"change":3,"start":6826,"end":6832},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6832},"to":{"change":3,"start":8769,"end":8770},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":554},"to":{"change":3,"start":8769,"end":8770},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8769},"to":{"change":3,"start":8769,"end":8770},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8770},"to":{"change":3,"start":6833,"end":7083},"introduced_by":3}],"inode":{"change":3,"pos":8623}}},"contents":[{"Del":" }\n"},{"Del":"\n"},{"Del":" fn split_at(c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {\n (\n PageCursor {\n cur: 0,\n total: c.cur.max(0) as usize,\n is_leaf: c.is_leaf,\n },\n *c,\n )\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":295,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":9834}],"down_context":[{"change":3,"pos":1267}],"flag":"BLOCK","start":9927,"end":9977,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // Once again, this is quite straightforward."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":301,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":9933}],"down_context":[{"change":3,"pos":672}],"flag":"BLOCK","start":9978,"end":10574,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // When deleting from internal nodes, we take a replacement from"},{"Add":" // one of the leaves (in our current implementation, the leftmost"},{"Add":" // entry of the right subtree). This method copies an entry from"},{"Add":" // the leaf onto the program stack, which is necessary since"},{"Add":" // deletions in leaves overwrites entries."},{"Add":" //"},{"Add":" // Another design choice would have been to do the same as for the"},{"Add":" // unsized implementation, but in this case this would have meant"},{"Add":" // copying the saved value to the end of the leaf, potentially"},{"Add":" // preventing merges, and not even saving a memory copy."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":312,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":697}],"down_context":[{"change":3,"pos":697}],"flag":"BLOCK","start":10575,"end":10576,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":""}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":323,"ins":{"up_context":[{"change":3,"pos":10101}],"down_context":[{"change":3,"pos":1219}],"flag":"BLOCK","start":10577,"end":10708,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":10101},"to":{"change":3,"start":7093,"end":7228},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {"},{"Add":" (core::mem::transmute(&s.0), core::mem::transmute(&s.1))"}],"del_contents":[{"Del":" fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {\n unsafe { (core::mem::transmute(&s.0), core::mem::transmute(&s.1)) }\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":327,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":1226}],"down_context":[{"change":3,"pos":1522}],"flag":"BLOCK","start":10709,"end":10826,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // `put` inserts one or two entries onto a node (internal or"},{"Add":" // leaf). This is implemented the `put` module."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":340,"ins":{"up_context":[{"change":3,"pos":11100}],"down_context":[{"change":3,"pos":4849}],"flag":"BLOCK","start":10827,"end":10882,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":11100},"to":{"change":3,"start":11100,"end":11143},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" ) -> Result, T::Error> {"}],"del_contents":[{"Del":" ) -> Result, T::Error> {\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":371,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":11472}],"down_context":[{"change":3,"pos":1588}],"flag":"BLOCK","start":10883,"end":10982,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // This function updates an internal node, setting the left child"},{"Add":" // of the cursor to `l`."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":378,"ins":{"up_context":[{"change":3,"pos":11595}],"down_context":[{"change":3,"pos":11672}],"flag":"BLOCK","start":10983,"end":11127,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":11595},"to":{"change":3,"start":11595,"end":11672},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" l: u64,"},{"Add":" ) -> Result {"},{"Add":" assert!(!c.is_leaf && c.cur >= 0 && (c.cur as usize) < c.total + 1);"}],"del_contents":[{"Del":" r: u64,\n ) -> Result {\n assert!(!c.is_leaf);\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":383,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":3655}],"down_context":[{"change":3,"pos":11747}],"flag":"BLOCK","start":11128,"end":11237,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // If the page is mutable (dirty), just convert it to a"},{"Add":" // mutable page, and update."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":386,"ins":{"up_context":[{"change":3,"pos":11770}],"down_context":[{"change":3,"pos":11796}],"flag":"BLOCK","start":11238,"end":11264,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":11770},"to":{"change":3,"start":2197,"end":2247},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" MutPage(page)"}],"del_contents":[{"Del":" unsafe { core::mem::transmute(page) }\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":388,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":11813}],"down_context":[{"change":3,"pos":2248}],"flag":"BLOCK","start":11265,"end":11302,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // Else, clone the page."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":391,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":1693}],"down_context":[{"change":3,"pos":7284}],"flag":"BLOCK","start":11303,"end":11358,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // First clone the left child of the page."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":395,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":328}],"down_context":[{"change":3,"pos":7350}],"flag":"BLOCK","start":11359,"end":11405,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // And then the rest of the page."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":397,"ins":{"up_context":[{"change":3,"pos":7421}],"down_context":[{"change":3,"pos":3656}],"flag":"BLOCK","start":11406,"end":11540,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":7421},"to":{"change":3,"start":2431,"end":2458},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":3183},"to":{"change":3,"start":2431,"end":2458},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2431},"to":{"change":3,"start":2431,"end":2458},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2458},"to":{"change":3,"start":7422,"end":7496},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" clone::(page.as_page(), &mut new, s, &mut 0);"},{"Add":" // Mark the former version of the page as free."}],"del_contents":[{"Del":" let mut n = 0;\n"},{"Del":" clone::(page.as_page(), &mut new, s, &mut n);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":402,"ins":{"up_context":[{"change":3,"pos":12313}],"down_context":[{"change":3,"pos":12351}],"flag":"BLOCK","start":11541,"end":11598,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":12313},"to":{"change":3,"start":5073,"end":5136},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" // Finally, update the left child of the cursor."}],"del_contents":[{"Del":" assert!(c.cur >= 0 && (c.cur as usize) < c.total + 1);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":404,"ins":{"up_context":[{"change":3,"pos":12368}],"down_context":[{"change":3,"pos":12516}],"flag":"BLOCK","start":11599,"end":11738,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":12368},"to":{"change":3,"start":12368,"end":12516},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur - 1);"},{"Add":" *off = (l | (u64::from_le(*off) & 0xfff)).to_le();"}],"del_contents":[{"Del":" let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur as isize - 1);\n *off = (r | (u64::from_le(*off) & 0xfff)).to_le();\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":419,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":3768}],"down_context":[{"change":3,"pos":2803}],"flag":"BLOCK","start":11739,"end":11831,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // In the mutable case, we just need to move some memory"},{"Add":" // around."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":422,"ins":{"up_context":[{"change":3,"pos":2834}],"down_context":[{"change":3,"pos":2909}],"flag":"BLOCK","start":11832,"end":11874,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2834},"to":{"change":3,"start":2834,"end":2909},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" let mut page = MutPage(page);"}],"del_contents":[{"Del":" let mut page: MutPage = unsafe { core::mem::transmute(page) };\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":424,"ins":{"up_context":[{"change":3,"pos":2954}],"down_context":[{"change":3,"pos":5616}],"flag":"BLOCK","start":11875,"end":12526,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2954},"to":{"change":3,"start":1672,"end":1693},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1693},"to":{"change":3,"start":7497,"end":7558},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7558},"to":{"change":3,"start":1693,"end":1770},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":1485},"to":{"change":3,"start":1693,"end":1770},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5373},"to":{"change":3,"start":1693,"end":1770},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1693},"to":{"change":3,"start":1693,"end":1770},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" let f = core::mem::size_of::>();"},{"Add":" if c.is_leaf {"},{"Add":" // In leaves, we need to move the n - c - 1 elements"},{"Add":" // that are strictly after the cursor, by `f` (the"},{"Add":" // size of an entry)."},{"Add":" //"},{"Add":" // Here's the reasoning to avoid off-by-one errors: if"},{"Add":" // `c` is 0 (i.e. we're deleting the first element on"},{"Add":" // the page), we remove one entry, so there are n - 1"},{"Add":" // remaining entries."},{"Add":" let n = hdr.n() as usize;"},{"Add":" let hdr_size = {"},{"Add":" // As usual, header + padding"}],"del_contents":[{"Del":" unsafe {\n"},{"Del":" let f = core::mem::size_of::>();\n"},{"Del":" if c.is_leaf {\n let n = hdr.n() as usize;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":438,"ins":{"up_context":[{"change":3,"pos":5683}],"down_context":[{"change":3,"pos":5339}],"flag":"BLOCK","start":12527,"end":13031,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":5683},"to":{"change":3,"start":44726,"end":44789},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":44726},"to":{"change":3,"start":44726,"end":44789},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":44789},"to":{"change":3,"start":5197,"end":5247},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5247},"to":{"change":3,"start":44830,"end":44886},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":44830},"to":{"change":3,"start":44830,"end":44886},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":44886},"to":{"change":3,"start":5248,"end":5338},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5338},"to":{"change":3,"start":44967,"end":45000},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":44967},"to":{"change":3,"start":44967,"end":45000},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":45000},"to":{"change":3,"start":2544,"end":2569},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2544},"to":{"change":3,"start":2544,"end":2569},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" (HDR + al - 1) & !(al - 1)"},{"Add":" };"},{"Add":" let off = hdr_size + c.cur as usize * f;"},{"Add":" unsafe {"},{"Add":" core::ptr::copy(p.add(off + f), p.add(off), f * (n - c.cur as usize - 1));"},{"Add":" }"},{"Add":" // Removing `f` bytes from the page."},{"Add":" hdr.decr(f);"},{"Add":" } else {"},{"Add":" // Internal nodes are easier to deal with, as we just"},{"Add":" // have to move the offsets."},{"Add":" unsafe {"}],"del_contents":[{"Del":" let hdr_size = (HDR + al - 1) & !(al - 1);\n"},{"Del":" let off = c.cur as usize * f;\n"},{"Del":" let kv_ptr = p.add(hdr_size + off);\n"},{"Del":" core::ptr::copy(kv_ptr.add(f), kv_ptr, f * (n - c.cur as usize - 1));\n"},{"Del":" hdr.decr(f);\n"},{"Del":" } else {\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":452,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":5506},"to":{"change":3,"start":5374,"end":5415},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6750},"to":{"change":3,"start":5374,"end":5415},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2148},"to":{"change":3,"start":5374,"end":5415},"introduced_by":3}],"inode":{"change":3,"pos":8623}}},"contents":[{"Del":" (&mut *hdr).decr(f);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":453,"ins":{"up_context":[{"change":3,"pos":2960}],"down_context":[{"change":3,"pos":4220}],"flag":"BLOCK","start":13032,"end":13175,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2960},"to":{"change":3,"start":2960,"end":2975},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":2975},"to":{"change":3,"start":4160,"end":4220},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4160},"to":{"change":3,"start":4160,"end":4220},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" // Removing `f` bytes from the page (the tuple), plus"},{"Add":" // one 8-bytes offset."},{"Add":" hdr.decr(f + 8);"},{"Add":""}],"del_contents":[{"Del":" };\n"},{"Del":" if l > 0 {\n assert!(!c.is_leaf);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":458,"ins":{"up_context":[{"change":3,"pos":4276}],"down_context":[{"change":3,"pos":14459}],"flag":"BLOCK","start":13176,"end":13416,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4276},"to":{"change":3,"start":4276,"end":4301},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4301},"to":{"change":3,"start":192,"end":275},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":4375},"to":{"change":3,"start":14388,"end":14459},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":275},"to":{"change":3,"start":14388,"end":14459},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":14388},"to":{"change":3,"start":14388,"end":14459},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" if l > 0 {"},{"Add":" unsafe {"},{"Add":" let off = (p.add(HDR) as *mut u64).offset(c.cur as isize - 1);"},{"Add":" *off = (l | (u64::from_le(*off) & 0xfff)).to_le();"},{"Add":" }"}],"del_contents":[{"Del":" unsafe {\n"},{"Del":" let off = (p.add(HDR) as *mut u64).offset(c.cur as isize - 1);\n"},{"Del":" *off = (l | (u64::from_le(*off) & 0xfff)).to_le();\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":466,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":312}],"down_context":[{"change":3,"pos":6751}],"flag":"BLOCK","start":13417,"end":13495,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // Returning the mutable page itself, and 0 (for \"no page freed\")"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":469,"ins":{"up_context":[{"change":3,"pos":14597}],"down_context":[{"change":3,"pos":7152}],"flag":"BLOCK","start":13496,"end":15416,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":14597},"to":{"change":3,"start":14597,"end":14618},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":14618},"to":{"change":3,"start":4450,"end":4499},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4499},"to":{"change":3,"start":2149,"end":2217},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":4570},"to":{"change":3,"start":14729,"end":14760},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":2217},"to":{"change":3,"start":14729,"end":14760},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":14729},"to":{"change":3,"start":14729,"end":14760},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":14760},"to":{"change":3,"start":4571,"end":4646},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4646},"to":{"change":3,"start":6778,"end":6821},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6821},"to":{"change":3,"start":5507,"end":5570},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4646},"to":{"change":3,"start":5507,"end":5570},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5570},"to":{"change":3,"start":102,"end":152},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":152},"to":{"change":3,"start":6822,"end":6882},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5570},"to":{"change":3,"start":14932,"end":14967},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":152},"to":{"change":3,"start":14932,"end":14967},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6882},"to":{"change":3,"start":14932,"end":14967},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":14932},"to":{"change":3,"start":14932,"end":14967},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":14967},"to":{"change":3,"start":2218,"end":2376},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":4811},"to":{"change":3,"start":15111,"end":15136},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":2376},"to":{"change":3,"start":15111,"end":15136},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15111},"to":{"change":3,"start":15111,"end":15136},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15136},"to":{"change":3,"start":4812,"end":4891},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4891},"to":{"change":3,"start":6883,"end":6926},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6926},"to":{"change":3,"start":5571,"end":5634},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4891},"to":{"change":3,"start":5571,"end":5634},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5634},"to":{"change":3,"start":153,"end":203},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":203},"to":{"change":3,"start":6927,"end":6991},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5634},"to":{"change":3,"start":15312,"end":15347},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":203},"to":{"change":3,"start":15312,"end":15347},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6991},"to":{"change":3,"start":15312,"end":15347},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15312},"to":{"change":3,"start":15312,"end":15347},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15347},"to":{"change":3,"start":2377,"end":2460},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2460},"to":{"change":3,"start":6992,"end":7152},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" // Immutable pages need to be cloned. The strategy is the"},{"Add":" // same in both cases: get an \"offset slice\", split it at"},{"Add":" // the cursor, remove the first entry of the second half,"},{"Add":" // and clone."},{"Add":" let mut new = txn.alloc_page()?;"},{"Add":" as BTreeMutPage>::init(&mut new);"},{"Add":" if c.is_leaf {"},{"Add":" let s = Leaf::offset_slice::(page.as_page());"},{"Add":" let (s0, s1) = s.split_at(c.cur as usize);"},{"Add":" let (_, s1) = s1.split_at(1);"},{"Add":" let mut n = 0;"},{"Add":" clone::(page.as_page(), &mut new, s0, &mut n);"},{"Add":" clone::(page.as_page(), &mut new, s1, &mut n);"},{"Add":" } else {"},{"Add":" // Internal nodes a bit trickier, since the left child"},{"Add":" // is not counted in the \"offset slice\", so we need to"},{"Add":" // clone it separately. Also, the `l` argument to this"},{"Add":" // function might be non-zero in this case."},{"Add":" let s = Internal::offset_slice::(page.as_page());"},{"Add":" let (s0, s1) = s.split_at(c.cur as usize);"},{"Add":" let (_, s1) = s1.split_at(1);"},{"Add":""},{"Add":" // First, clone the left child of the page."},{"Add":" let hdr = header(page.as_page());"},{"Add":" let left = hdr.left_page() & !0xfff;"},{"Add":" unsafe { *(new.0.data.add(HDR - 8) as *mut u64) = left.to_le() };"},{"Add":""},{"Add":" // Then, clone the entries strictly before the cursor"},{"Add":" // (i.e. clone `s0`)."},{"Add":" let mut n = 0;"},{"Add":" clone::(page.as_page(), &mut new, s0, &mut n);"},{"Add":""},{"Add":" // If we need to update the left child of the deleted"},{"Add":" // item, do it."},{"Add":" if l > 0 {"},{"Add":" unsafe {"},{"Add":" let off = new.0.data.offset(HDR as isize + (n - 1) * 8) as *mut u64;"}],"del_contents":[{"Del":" unsafe {\n"},{"Del":" let mut new = txn.alloc_page()?;\n"},{"Del":" as BTreeMutPage>::init(&mut new);\n"},{"Del":" if c.is_leaf {\n"},{"Del":" let s = Leaf::offset_slice::(page.as_page());\n"},{"Del":" debug!(\"s = {:?}\", s);\n"},{"Del":" let (s0, s1) = s.split_at(c.cur as usize);\n"},{"Del":" let (_, s1) = s1.split_at(1);\n"},{"Del":" debug!(\"leaf s0 {:?} s1 {:?}\", s0, s1);\n"},{"Del":" let mut n = 0;\n"},{"Del":" clone::(page.as_page(), &mut new, s0, &mut n);\n clone::(page.as_page(), &mut new, s1, &mut n);\n"},{"Del":" } else {\n"},{"Del":" let s = Internal::offset_slice::(page.as_page());\n"},{"Del":" debug!(\"s = {:?}\", s);\n"},{"Del":" let (s0, s1) = s.split_at(c.cur as usize);\n"},{"Del":" let (_, s1) = s1.split_at(1);\n"},{"Del":" debug!(\"internal s0 {:?} s1 {:?}\", s0, s1);\n"},{"Del":" let mut n = 0;\n"},{"Del":" clone::(page.as_page(), &mut new, s0, &mut n);\n"},{"Del":" debug!(\"offset {:?}\", n);\n if l > 0 {\n let off = (new.0.data.add(HDR) as *mut u64).offset(n - 1);\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":507,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7227},"to":{"change":3,"start":7227,"end":7526},"introduced_by":3}],"inode":{"change":3,"pos":8623}}},"contents":[{"Del":" debug!(\"set offset {:?} {:?}\", *off, l);\n } else {\n let hdr = header(page.as_page());\n let left = hdr.left_page() & !0xfff;\n *(new.0.data.add(HDR) as *mut u64).offset(-1) = left.to_le();\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":508,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":143},"to":{"change":3,"start":2461,"end":2544},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7548},"to":{"change":3,"start":2461,"end":2544},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15539},"to":{"change":3,"start":2461,"end":2544},"introduced_by":3}],"inode":{"change":3,"pos":8623}}},"contents":[{"Del":" clone::(page.as_page(), &mut new, s1, &mut n);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":509,"ins":{"up_context":[{"change":3,"pos":15633}],"down_context":[{"change":3,"pos":15657}],"flag":"BLOCK","start":15417,"end":15566,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15633},"to":{"change":3,"start":7549,"end":7588},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":""},{"Add":" // Finally, clone the right half of the page (`s1`)."},{"Add":" clone::(page.as_page(), &mut new, s1, &mut n);"}],"del_contents":[{"Del":" Ok((new, page.offset))\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":513,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":15671}],"down_context":[{"change":3,"pos":15671}],"flag":"BLOCK","start":15567,"end":15602,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" Ok((new, page.offset))"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":517,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":15688}],"down_context":[{"change":3,"pos":2545}],"flag":"BLOCK","start":15603,"end":15708,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // Decide what to do with the concatenation of two neighbouring"},{"Add":" // pages, with a middle element."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":523,"ins":{"up_context":[{"change":3,"pos":15824}],"down_context":[{"change":3,"pos":5684}],"flag":"BLOCK","start":15709,"end":15839,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15824},"to":{"change":3,"start":15824,"end":15906},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15906},"to":{"change":3,"start":7595,"end":7652},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" // First evaluate the size of the middle element on a page."},{"Add":" let (hdr_size, mid_size) = if m.modified.c0.is_leaf {"}],"del_contents":[{"Del":" let mut hdr_size = HDR;\n let mid_size = if m.modified.c0.is_leaf {\n"},{"Del":" let f = core::mem::size_of::>();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":526,"ins":{"up_context":[{"change":3,"pos":5743}],"down_context":[{"change":3,"pos":16193}],"flag":"BLOCK","start":15840,"end":15965,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":5743},"to":{"change":3,"start":45103,"end":45168},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":45103},"to":{"change":3,"start":45103,"end":45168},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" ("},{"Add":" (HDR + al - 1) & !(al - 1),"},{"Add":" core::mem::size_of::>(),"},{"Add":" )"}],"del_contents":[{"Del":" hdr_size = (HDR + al - 1) & !(al - 1);\n f\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":531,"ins":{"up_context":[{"change":3,"pos":16210}],"down_context":[{"change":3,"pos":16281}],"flag":"BLOCK","start":15966,"end":16025,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":16210},"to":{"change":3,"start":5744,"end":5796},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" (HDR, 8 + core::mem::size_of::>())"}],"del_contents":[{"Del":" 8 + core::mem::size_of::>()\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":533,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":16292}],"down_context":[{"change":3,"pos":7305}],"flag":"BLOCK","start":16026,"end":16138,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":""},{"Add":" // Evaluate the size of the modified half of the concatenation"},{"Add":" // (which includes the header)."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":537,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":7355}],"down_context":[{"change":3,"pos":5228}],"flag":"BLOCK","start":16139,"end":16203,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // Add the \"occupied\" size (which excludes the header)."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":542,"ins":{"up_context":[{"change":3,"pos":16473}],"down_context":[{"change":3,"pos":7934}],"flag":"BLOCK","start":16204,"end":16861,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":16473},"to":{"change":3,"start":1827,"end":1889},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":3218},"to":{"change":3,"start":16536,"end":16588},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":1889},"to":{"change":3,"start":16536,"end":16588},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5401},"to":{"change":3,"start":16536,"end":16588},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":16536},"to":{"change":3,"start":16536,"end":16588},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":16588},"to":{"change":3,"start":5402,"end":5447},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5447},"to":{"change":3,"start":2797,"end":2861},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2861},"to":{"change":3,"start":7703,"end":7934},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":""},{"Add":" // One surprising observation here is that adding the sizes"},{"Add":" // works. This is surprising because of alignment and"},{"Add":" // padding. It works because we can split the sizes into an"},{"Add":" // offset part (always 8 bytes) and a data part (of a constant"},{"Add":" // alignment), and thus we never need any padding anywhere on"},{"Add":" // the page."},{"Add":" if mod_size + mid_size + occupied <= PAGE_SIZE {"},{"Add":" // If the concatenation fits on a page, merge."},{"Add":" let (page, freed) = if m.modified.c0.is_leaf {"},{"Add":" merge::<_, _, _, Leaf>(txn, m)?"},{"Add":" } else {"},{"Add":" merge::<_, _, _, Internal>(txn, m)?"}],"del_contents":[{"Del":" let size = hdr_size + mod_size + mid_size + occupied;\n"},{"Del":" if size <= PAGE_SIZE {\n // merge\n"},{"Del":" let mut new = txn.alloc_page()?;\n"},{"Del":" as BTreeMutPage>::init(&mut new);\n"},{"Del":" let freed = {\n let b0 = if m.modified.page.is_dirty() { 1 } else { 0 };\n let b1 = if m.other.is_dirty() { 1 } else { 0 };\n [m.modified.page.offset | b0, m.other.offset | b1]\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":556,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":7949},"to":{"change":3,"start":7356,"end":7395},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2861},"to":{"change":3,"start":7356,"end":7395},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7395},"to":{"change":3,"start":7395,"end":7452},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7452},"to":{"change":3,"start":7452,"end":7473},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7473},"to":{"change":3,"start":7473,"end":7534},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7534},"to":{"change":3,"start":16904,"end":16918},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":16904},"to":{"change":3,"start":16904,"end":16918},"introduced_by":3}],"inode":{"change":3,"pos":8623}}},"contents":[{"Del":" if m.modified.c0.is_leaf {\n"},{"Del":" merge::<_, _, _, Leaf>(txn, &mut new, m)\n"},{"Del":" } else {\n"},{"Del":" merge::<_, _, _, Internal>(txn, &mut new, m)\n"},{"Del":" }\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":557,"ins":{"up_context":[{"change":3,"pos":17149}],"down_context":[{"change":3,"pos":7950}],"flag":"BLOCK","start":16862,"end":16884,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":17149},"to":{"change":3,"start":17149,"end":17176},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" page,"}],"del_contents":[{"Del":" page: new,\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":562,"ins":{"up_context":[{"change":3,"pos":17328}],"down_context":[{"change":3,"pos":3485}],"flag":"BLOCK","start":16885,"end":17422,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":17328},"to":{"change":3,"start":3900,"end":3947},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3947},"to":{"change":3,"start":7974,"end":8051},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":8051},"to":{"change":3,"start":3352,"end":3405},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":3419},"to":{"change":3,"start":3352,"end":3405},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5920},"to":{"change":3,"start":3352,"end":3405},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3405},"to":{"change":3,"start":549,"end":640},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" // If the modified page is large enough, or if the other page"},{"Add":" // has only just barely the minimum number of elements to be"},{"Add":" // at least half-full, return."},{"Add":" //"},{"Add":" // The situation where the other page isn't full enough might"},{"Add":" // happen for example if elements occupy exactly 1/5th of a"},{"Add":" // page + 1 byte, and the modified page has 2 of them after"},{"Add":" // the deletion, while the other page has 3."},{"Add":" if mod_size >= PAGE_SIZE / 2 || hdr_size + occupied - mid_size < PAGE_SIZE / 2 {"}],"del_contents":[{"Del":" let rc = PageCursor::new(&m.other, 0);\n"},{"Del":" let first_size = >::current_size(m.other.as_page(), &rc);\n"},{"Del":" // If we can't rebalance, modify and return.\n"},{"Del":" if mod_size >= PAGE_SIZE / 2 || hdr_size + occupied - first_size < PAGE_SIZE / 2 {\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":572,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":3536}],"down_context":[{"change":3,"pos":7535}],"flag":"BLOCK","start":17423,"end":17488,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // Perform the required modification and return."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":577,"ins":{"up_context":[{"change":3,"pos":6126}],"down_context":[{"change":3,"pos":6126}],"flag":"BLOCK","start":17489,"end":17532,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6126},"to":{"change":3,"start":7581,"end":7607},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" m.modified.skip_first,"}],"del_contents":[{"Del":" true,\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":586,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":6309}],"down_context":[{"change":3,"pos":7589}],"flag":"BLOCK","start":17533,"end":17856,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // `ins2` is only ever used when the page immediately"},{"Add":" // below a deletion inside an internal node has split,"},{"Add":" // and we need to replace the deleted value, *and*"},{"Add":" // insert the middle entry of the split."},{"Add":" debug_assert!(m.modified.ins2.is_none());"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":601,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":18260}],"down_context":[{"change":3,"pos":223}],"flag":"BLOCK","start":17857,"end":18032,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":""},{"Add":" // Finally, if we're here, we can rebalance. There are four"},{"Add":" // (relatively explicit) cases, see the `rebalance` submodule"},{"Add":" // to see how this is done."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":621,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":18476}],"down_context":[{"change":3,"pos":5797}],"flag":"BLOCK","start":18033,"end":18085,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":"/// Size of a modified page (including the header)."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":633,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":7964}],"down_context":[{"change":3,"pos":5935}],"flag":"BLOCK","start":18086,"end":18173,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":""},{"Add":" // Extra size for the offsets."},{"Add":" let extra = if m.c1.is_leaf { 0 } else { 8 };"},{"Add":""}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":638,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":5960},"to":{"change":3,"start":7998,"end":8052},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7998},"to":{"change":3,"start":7998,"end":8052},"introduced_by":3}],"inode":{"change":3,"pos":8623}}},"contents":[{"Del":" let extra = if m.c1.is_leaf { 0 } else { 8 };\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":643,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":20175}],"down_context":[{"change":3,"pos":8214}],"flag":"BLOCK","start":18174,"end":18236,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // If we skip the first entry of `m.c1`, remove its size."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":645,"ins":{"up_context":[{"change":3,"pos":8236}],"down_context":[{"change":3,"pos":26184}],"flag":"BLOCK","start":18237,"end":18298,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8236},"to":{"change":3,"start":8097,"end":8195},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" total -= extra + core::mem::size_of::>()"}],"del_contents":[{"Del":" total -= as BTreePage>::current_size(m.page.as_page(), &m.c1) as usize;\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":650,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":9543}],"down_context":[{"change":3,"pos":6119}],"flag":"BLOCK","start":18299,"end":18368,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":"/// Linear search, leaf version. This is relatively straightforward."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":678,"ins":{"up_context":[{"change":3,"pos":4487}],"down_context":[{"change":3,"pos":4551}],"flag":"BLOCK","start":18369,"end":18537,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4487},"to":{"change":3,"start":6182,"end":6236},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":"/// An equivalent of `Ord::cmp` on `Tuple` but using"},{"Add":"/// `Storable::compare` instead of `Ord::cmp` on `K` and `V`."},{"Add":"fn cmp("}],"del_contents":[{"Del":"unsafe fn cmp(\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":688,"ins":{"up_context":[{"change":3,"pos":4687}],"down_context":[{"change":3,"pos":6318}],"flag":"BLOCK","start":18538,"end":18708,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4687},"to":{"change":3,"start":6237,"end":6318},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" assert!(off as usize + core::mem::size_of::>() <= PAGE_SIZE);"},{"Add":" let tup = unsafe { &*(p.as_ptr().offset(off as isize & 0xfff) as *const Tuple) };"}],"del_contents":[{"Del":" let tup = &*(p.as_ptr().offset(off as isize & 0xfff) as *const Tuple);\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":702,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":5085}],"down_context":[{"change":3,"pos":6394}],"flag":"BLOCK","start":18709,"end":18766,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":"/// Linear search for internal nodes. Does what it says."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":710,"ins":{"up_context":[{"change":3,"pos":5269}],"down_context":[{"change":3,"pos":306}],"flag":"BLOCK","start":18767,"end":18885,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5269},"to":{"change":3,"start":5269,"end":5636},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5636},"to":{"change":3,"start":268,"end":306},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":268},"to":{"change":3,"start":268,"end":306},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" for (n, off) in s.iter().enumerate() {"},{"Add":" match cmp(txn, k0, v0, p, *off) {"},{"Add":" Ordering::Less => {}"}],"del_contents":[{"Del":" let mut a = 0;\n let mut b = s.len();\n for _ in 0..4 {\n let mid = (a + b) / 2;\n match cmp(txn, k0, v0, p, s[mid]) {\n Ordering::Less => a = mid,\n Ordering::Greater => b = mid,\n Ordering::Equal => b = mid + 1,\n }\n }\n let mut n = a;\n for &off in &s[a..b] {\n match cmp(txn, k0, v0, p, off) {\n"},{"Del":" Ordering::Less => n += 1,\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":717,"ins":{"up_context":[{"change":3,"pos":415}],"down_context":[{"change":3,"pos":426}],"flag":"BLOCK","start":18886,"end":18903,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":415},"to":{"change":3,"start":415,"end":426},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" Err(s.len())"}],"del_contents":[{"Del":" Err(n)\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":720,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":429}],"down_context":[{"change":3,"pos":6461}],"flag":"BLOCK","start":18904,"end":19030,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":"/// Lookup just forms slices of offsets (for internal nodes) or values"},{"Add":"/// (for leaves), and runs an internal search on them."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":749,"ins":{"up_context":[{"change":3,"pos":12021}],"down_context":[{"change":3,"pos":5491}],"flag":"BLOCK","start":19031,"end":19163,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":12021},"to":{"change":3,"start":6575,"end":6673},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":"/// Perform the modifications on a page, by copying it onto page `new`."},{"Add":"fn modify("}],"del_contents":[{"Del":"fn modify(\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":756,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":34802}],"down_context":[{"change":3,"pos":8196}],"flag":"BLOCK","start":19164,"end":19347,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // First trick: in order to save code lines, set `l` to the left"},{"Add":" // page, and let `alloc` set it in `new` in the while loop"},{"Add":" // (setting `l = 0` in subsequent iterations)."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":764,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":35045}],"down_context":[{"change":3,"pos":710}],"flag":"BLOCK","start":19348,"end":19417,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // If there's an insertion on two in the modified page, do them."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":773,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":35155}],"down_context":[{"change":3,"pos":35155}],"flag":"BLOCK","start":19418,"end":19539,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // If there's no insertion, we have had no opportunity to set"},{"Add":" // the updated left chlid, so set it here."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":777,"ins":{"up_context":[{"change":3,"pos":35177}],"down_context":[{"change":3,"pos":6050}],"flag":"BLOCK","start":19540,"end":19790,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":35177},"to":{"change":3,"start":35177,"end":35214},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":35214},"to":{"change":3,"start":8351,"end":8438},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":8438},"to":{"change":3,"start":35287,"end":35371},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":20454},"to":{"change":3,"start":35287,"end":35371},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":3873},"to":{"change":3,"start":35287,"end":35371},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5933},"to":{"change":3,"start":35287,"end":35371},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":35287},"to":{"change":3,"start":35287,"end":35371},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" // Then, clone `m.c1`, possibly skipping the first element."},{"Add":" let mut c1 = m.c1.clone();"},{"Add":" if m.skip_first {"},{"Add":" >::move_next(&mut c1);"},{"Add":" }"},{"Add":" while let Some((k, v, r)) = >::next(txn, m.page.as_page(), &mut c1) {"}],"del_contents":[{"Del":" let mut is_first = m.skip_first;\n"},{"Del":" while let Some((k, v, r)) = >::next(txn, m.page.as_page(), &mut m.c1) {\n"},{"Del":" if is_first {\n is_first = false;\n continue;\n }\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":788,"ins":{"up_context":[{"change":3,"pos":35449}],"down_context":[{"change":3,"pos":8439}],"flag":"BLOCK","start":19791,"end":19979,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":35449},"to":{"change":3,"start":6674,"end":6771},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6771},"to":{"change":3,"start":6089,"end":6102},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6100},"to":{"change":3,"start":6089,"end":6102},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6089},"to":{"change":3,"start":6089,"end":6102},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":8887},"to":{"change":3,"start":20505,"end":20528},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":1958},"to":{"change":3,"start":20505,"end":20528},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6102},"to":{"change":3,"start":20505,"end":20528},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":35531},"to":{"change":3,"start":20505,"end":20528},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":"/// The very unsurprising `merge` function"},{"Add":"fn merge<"},{"Add":" T: AllocPage + LoadPage,"},{"Add":" K: Storable + core::fmt::Debug,"},{"Add":" V: Storable + core::fmt::Debug,"},{"Add":" L: Alloc,"},{"Add":">("},{"Add":" txn: &mut T,"}],"del_contents":[{"Del":"fn merge(\n"},{"Del":" txn: &T,\n"},{"Del":" new: &mut MutPage,\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":797,"ins":{"up_context":[{"change":3,"pos":8476}],"down_context":[{"change":3,"pos":35631}],"flag":"BLOCK","start":19980,"end":20452,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":8476},"to":{"change":3,"start":35590,"end":35594},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6141},"to":{"change":3,"start":35590,"end":35594},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":35590},"to":{"change":3,"start":35590,"end":35594},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":") -> Result<(MutPage, [u64; 2]), T::Error> {"},{"Add":" // This algorithm is probably a bit naive, especially for leaves,"},{"Add":" // where if the left page is mutable, we can copy the other page"},{"Add":" // onto it."},{"Add":""},{"Add":" // Indeed, we first allocate a page, then clone both pages onto"},{"Add":" // it, in a different order depending on whether the modified page"},{"Add":" // is the left or the right child."},{"Add":" let mut new = txn.alloc_page()?;"},{"Add":" as BTreeMutPage>::init(&mut new);"}],"del_contents":[{"Del":") {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":809,"ins":{"up_context":[{"change":3,"pos":35673}],"down_context":[{"change":3,"pos":5733}],"flag":"BLOCK","start":20453,"end":20523,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":35673},"to":{"change":3,"start":6142,"end":6207},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" modify::<_, _, _, L>(txn, &mut new, &mut m.modified, &mut n);"}],"del_contents":[{"Del":" modify::<_, _, _, L>(txn, new, &mut m.modified, &mut n);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":812,"ins":{"up_context":[{"change":3,"pos":8543}],"down_context":[{"change":3,"pos":8544}],"flag":"BLOCK","start":20524,"end":20592,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":8543},"to":{"change":3,"start":6208,"end":6271},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":3951},"to":{"change":3,"start":6208,"end":6271},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":20723},"to":{"change":3,"start":6208,"end":6271},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" alloc::<_, _, L>(&mut new, m.mid.0, m.mid.1, 0, l, &mut n);"}],"del_contents":[{"Del":" alloc::<_, _, L>(new, m.mid.0, m.mid.1, 0, l, &mut n);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":814,"ins":{"up_context":[{"change":3,"pos":8634}],"down_context":[{"change":3,"pos":36058}],"flag":"BLOCK","start":20593,"end":20653,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":8634},"to":{"change":3,"start":6361,"end":6416},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":4053},"to":{"change":3,"start":6361,"end":6416},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6361},"to":{"change":3,"start":6361,"end":6416},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" alloc::<_, _, L>(&mut new, k, v, 0, r, &mut n);"}],"del_contents":[{"Del":" alloc::<_, _, L>(new, k, v, 0, r, &mut n);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":820,"ins":{"up_context":[{"change":3,"pos":8795}],"down_context":[{"change":3,"pos":36340}],"flag":"BLOCK","start":20654,"end":20714,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":8795},"to":{"change":3,"start":6507,"end":6562},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":4236},"to":{"change":3,"start":6507,"end":6562},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6507},"to":{"change":3,"start":6507,"end":6562},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" alloc::<_, _, L>(&mut new, k, v, l, r, &mut n);"}],"del_contents":[{"Del":" alloc::<_, _, L>(new, k, v, l, r, &mut n);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":823,"ins":{"up_context":[{"change":3,"pos":36369}],"down_context":[{"change":3,"pos":36499}],"flag":"BLOCK","start":20715,"end":20853,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":36369},"to":{"change":3,"start":6563,"end":6626},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6626},"to":{"change":3,"start":6626,"end":6691},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" alloc::<_, _, L>(&mut new, m.mid.0, m.mid.1, 0, 0, &mut n);"},{"Add":" modify::<_, _, _, L>(txn, &mut new, &mut m.modified, &mut n);"}],"del_contents":[{"Del":" alloc::<_, _, L>(new, m.mid.0, m.mid.1, 0, 0, &mut n);\n"},{"Del":" modify::<_, _, _, L>(txn, new, &mut m.modified, &mut n);\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":826,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":36505}],"down_context":[{"change":3,"pos":36505}],"flag":"BLOCK","start":20854,"end":21081,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" let freed = {"},{"Add":" let b0 = if m.modified.page.is_dirty() { 1 } else { 0 };"},{"Add":" let b1 = if m.other.is_dirty() { 1 } else { 0 };"},{"Add":" [m.modified.page.offset | b0, m.other.offset | b1]"},{"Add":" };"},{"Add":" Ok((new, freed))"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":834,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":36508}],"down_context":[{"change":3,"pos":6772}],"flag":"BLOCK","start":21082,"end":21479,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":"/// Clone a slice of offsets onto a page. This essentially does what"},{"Add":"/// it says. Note that the leftmost child of a page is not included in"},{"Add":"/// the offset slices, so we don't have to handle it here."},{"Add":"///"},{"Add":"/// This should really be in the `Alloc` trait, but Rust doesn't have"},{"Add":"/// associated type constructors, so we can't have an associated type"},{"Add":"/// that's sometimes a slice and sometimes a \"Range\"."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":844,"ins":{"up_context":[{"change":3,"pos":22551}],"down_context":[{"change":3,"pos":38809}],"flag":"BLOCK","start":21480,"end":21496,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":22551},"to":{"change":3,"start":38782,"end":38809},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":38782},"to":{"change":3,"start":38782,"end":38809},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" s: Offsets,"}],"del_contents":[{"Del":" s: Offsets,\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":849,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":38877}],"down_context":[{"change":3,"pos":38877}],"flag":"BLOCK","start":21497,"end":21552,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // We know we're in an internal node here."}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":851,"ins":{"up_context":[{"change":3,"pos":38911}],"down_context":[{"change":3,"pos":22604}],"flag":"BLOCK","start":21553,"end":21636,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":38911},"to":{"change":3,"start":38911,"end":38969},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" let r = (*off) & !0xfff;"},{"Add":" let off = (*off) & 0xfff;"}],"del_contents":[{"Del":" let (r, off): (u64, u16) = (*off).into();\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":856,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":6887}],"down_context":[{"change":3,"pos":22804}],"flag":"BLOCK","start":21637,"end":21691,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":""},{"Add":" // Reserve the space on the page"}]}},{"Replacement":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":859,"ins":{"up_context":[{"change":3,"pos":22851}],"down_context":[{"change":3,"pos":23126}],"flag":"BLOCK","start":21692,"end":22413,"inode":{"change":3,"pos":8623}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":22851},"to":{"change":3,"start":6888,"end":6981},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6981},"to":{"change":3,"start":22970,"end":23126},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":22970},"to":{"change":3,"start":22970,"end":23126},"introduced_by":3}],"inode":{"change":3,"pos":8623}},"ins_contents":[{"Add":" let data = hdr.data() as u16;"},{"Add":" let off_new = data - size as u16;"},{"Add":" hdr.set_data(off_new);"},{"Add":" hdr.set_n(hdr.n() + 1);"},{"Add":" hdr.incr(8 + size);"},{"Add":""},{"Add":" // Copy the entry from the original page to its"},{"Add":" // position on the new page."},{"Add":" core::ptr::copy_nonoverlapping(ptr, new.0.data.add(off_new as usize), size);"},{"Add":""},{"Add":" // Set the offset to this new entry in the offset"},{"Add":" // array, along with the right child page."},{"Add":" let ptr = new.0.data.offset(HDR as isize + *n * 8) as *mut u64;"},{"Add":" *ptr = (r | off_new as u64).to_le();"}],"del_contents":[{"Del":" let off_new = L::alloc(hdr, size, core::mem::align_of::>());\n"},{"Del":" core::ptr::copy_nonoverlapping(ptr, new.0.data.offset(off_new as isize), size);\n L::set_offset(new, *n, r, off_new);\n"}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":890,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":39972}],"down_context":[{"change":3,"pos":23459}],"flag":"BLOCK","start":22414,"end":22533,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":" // On leaves, we do have to update everything manually,"},{"Add":" // because we're simply copying stuff."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":899,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":39991}],"down_context":[{"change":3,"pos":7040}],"flag":"BLOCK","start":22534,"end":22626,"inode":{"change":3,"pos":8623}}},"contents":[{"Add":"/// Simply allocate an entry in the page, copy it, and set"},{"Add":"/// its right and left children."}]}},{"Edit":{"inode":{"change":3,"pos":8623},"path":"sanakirja-core/src/btree/page.rs","line":914,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7352},"to":{"change":3,"start":7352,"end":7411},"introduced_by":3}],"inode":{"change":3,"pos":8623}}},"contents":[{"Del":" debug!(\"allocated {:?} {:?} {:?}\", new_ptr, l, r);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":16,"ins":{"up_context":[{"change":3,"pos":810}],"down_context":[{"change":3,"pos":5837}],"flag":"BLOCK","start":22627,"end":22733,"inode":{"change":3,"pos":387}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":810},"to":{"change":3,"start":810,"end":823},"introduced_by":3}],"inode":{"change":3,"pos":387}},"ins_contents":[{"Add":" // page, i.e. return a middle element, and append the current"},{"Add":" // middle element to the left page."}],"del_contents":[{"Del":" // page.\n"}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":24,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":1209}],"down_context":[{"change":3,"pos":9040}],"flag":"BLOCK","start":22734,"end":22944,"inode":{"change":3,"pos":387}}},"contents":[{"Add":" // First, perform the modification on the modified page, which we"},{"Add":" // know is the left page, and return the resulting mutable page"},{"Add":" // (the modified page may or may not be mutable before we do this)."}]}},{"Replacement":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":33,"ins":{"up_context":[{"change":3,"pos":1414}],"down_context":[{"change":3,"pos":1414}],"flag":"BLOCK","start":22945,"end":22980,"inode":{"change":3,"pos":387}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1414},"to":{"change":3,"start":8434,"end":8452},"introduced_by":3}],"inode":{"change":3,"pos":387}},"ins_contents":[{"Add":" m.modified.skip_first,"}],"del_contents":[{"Del":" true,\n"}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":64,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":1736}],"down_context":[{"change":3,"pos":9308}],"flag":"BLOCK","start":22981,"end":23173,"inode":{"change":3,"pos":387}}},"contents":[{"Add":""},{"Add":" // Append the middle element of the concatenation at the end of"},{"Add":" // the left page. We know the left page to be mutable by now, and"},{"Add":" // we also know there's enough space to do this."}]}},{"Replacement":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":80,"ins":{"up_context":[{"change":3,"pos":9569}],"down_context":[{"change":3,"pos":46383}],"flag":"BLOCK","start":23174,"end":23499,"inode":{"change":3,"pos":387}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":9569},"to":{"change":3,"start":46209,"end":46383},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":1788},"to":{"change":3,"start":46209,"end":46383},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":46209},"to":{"change":3,"start":46209,"end":46383},"introduced_by":3}],"inode":{"change":3,"pos":387}},"ins_contents":[{"Add":" let (new_right, k, v) = if r == 0 && m.other_is_mutable && right_hdr.is_dirty() {"},{"Add":" // Since `r == 0`, we know this is a leaf. Therefore, we need"},{"Add":" // to rewrite the deleted element to the end of the page, so"},{"Add":" // that the pointer to the new middle entry is valid when this"},{"Add":" // function returns."}],"del_contents":[{"Del":" let (new_right, k, v) = if r == 0 && right_hdr.is_dirty() {\n // Rewrite the deleted element at the end of the page, so that\n // the pointer is still valid.\n"}]}},{"Replacement":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":88,"ins":{"up_context":[{"change":3,"pos":46506}],"down_context":[{"change":3,"pos":46598}],"flag":"BLOCK","start":23500,"end":23543,"inode":{"change":3,"pos":387}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":46506},"to":{"change":3,"start":7485,"end":7540},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7540},"to":{"change":3,"start":46547,"end":46598},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":46547},"to":{"change":3,"start":46547,"end":46598},"introduced_by":3}],"inode":{"change":3,"pos":387}},"ins_contents":[{"Add":" // Remove the space for one entry."}],"del_contents":[{"Del":" let al = core::mem::align_of::>();\n"},{"Del":" let hdr_size = (HDR + al - 1) & !(al - 1);\n"}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":92,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":46706}],"down_context":[{"change":3,"pos":46706}],"flag":"BLOCK","start":23544,"end":23651,"inode":{"change":3,"pos":387}}},"contents":[{"Add":""},{"Add":" let al = core::mem::align_of::>();"},{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":97,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":46792}],"down_context":[{"change":3,"pos":46792}],"flag":"BLOCK","start":23652,"end":23778,"inode":{"change":3,"pos":387}}},"contents":[{"Add":" // Save the leftmost element (we can't directly copy it to"},{"Add":" // the end, because the page may be full)."}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":104,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":46958}],"down_context":[{"change":3,"pos":46958}],"flag":"BLOCK","start":23779,"end":23846,"inode":{"change":3,"pos":387}}},"contents":[{"Add":" // Move the n - 1 last elements one entry to the left."}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":110,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":47143}],"down_context":[{"change":3,"pos":47143}],"flag":"BLOCK","start":23847,"end":23908,"inode":{"change":3,"pos":387}}},"contents":[{"Add":" // Copy the last element to the end of the page."}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":116,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":47398}],"down_context":[{"change":3,"pos":9570}],"flag":"BLOCK","start":23909,"end":24279,"inode":{"change":3,"pos":387}}},"contents":[{"Add":" // If this isn't a leaf, or isn't mutable, use the standard"},{"Add":" // deletion function, because we know this will leave the"},{"Add":" // pointer to the current entry valid."},{"Add":""},{"Add":" // We extend the pointer's lifetime here, because we know the"},{"Add":" // current deletion (we only rebalance during deletions) won't"},{"Add":" // touch this page anymore after this."}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":126,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":9675}],"down_context":[{"change":3,"pos":9675}],"flag":"BLOCK","start":24280,"end":24367,"inode":{"change":3,"pos":387}}},"contents":[{"Add":" // If this frees the old \"other\" page, add it to the \"freed\""},{"Add":" // array."}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":145,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":3871}],"down_context":[{"change":3,"pos":3871}],"flag":"BLOCK","start":24368,"end":24692,"inode":{"change":3,"pos":387}}},"contents":[{"Add":"// Surprisingly, the `rebalance_right` function is simpler,"},{"Add":"// since:"},{"Add":"//"},{"Add":"// - if we call it to rebalance two internal nodes, we're in the easy"},{"Add":"// case of rebalance_left."},{"Add":"//"},{"Add":"// - Else, the middle element is the last one on the left page, and"},{"Add":"// isn't erased be leaf deletions, because these just move entries to"},{"Add":"// the left."}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":175,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":4736}],"down_context":[{"change":3,"pos":8510}],"flag":"BLOCK","start":24693,"end":24747,"inode":{"change":3,"pos":387}}},"contents":[{"Add":" // Perform the modification on the modified page."}]}},{"Replacement":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":182,"ins":{"up_context":[{"change":3,"pos":4942}],"down_context":[{"change":3,"pos":4942}],"flag":"BLOCK","start":24748,"end":24783,"inode":{"change":3,"pos":387}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4942},"to":{"change":3,"start":8662,"end":8680},"introduced_by":3}],"inode":{"change":3,"pos":387}},"ins_contents":[{"Add":" m.modified.skip_first,"}],"del_contents":[{"Del":" true,\n"}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":211,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":8722}],"down_context":[{"change":3,"pos":10278}],"flag":"BLOCK","start":24784,"end":24986,"inode":{"change":3,"pos":387}}},"contents":[{"Add":""},{"Add":" // Add the middle element of the concatenation as the first"},{"Add":" // element of the right page. We know the right page is mutable,"},{"Add":" // since we just modified it (hence the `assert_eq!(freed, 0)`."}]}},{"Edit":{"inode":{"change":3,"pos":387},"path":"sanakirja-core/src/btree/page/rebalance.rs","line":233,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":5465}],"down_context":[{"change":3,"pos":10369}],"flag":"BLOCK","start":24987,"end":25160,"inode":{"change":3,"pos":387}}},"contents":[{"Add":" // As explained in the general comment on this function, this"},{"Add":" // entry isn't erased by the deletion in `m.other` below, so we"},{"Add":" // can safely extend its lifetime."}]}},{"Replacement":{"inode":{"change":3,"pos":5929},"path":"sanakirja-core/src/btree/page/put.rs","line":20,"ins":{"up_context":[{"change":3,"pos":6271}],"down_context":[{"change":3,"pos":7817}],"flag":"BLOCK","start":25161,"end":25270,"inode":{"change":3,"pos":5929}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6271},"to":{"change":3,"start":6271,"end":6310},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6310},"to":{"change":3,"start":7687,"end":7816},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7816},"to":{"change":3,"start":6416,"end":6458},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6416},"to":{"change":3,"start":6416,"end":6458},"introduced_by":3}],"inode":{"change":3,"pos":5929}},"ins_contents":[{"Add":") -> Result, T::Error> {"},{"Add":" let size = if k1v1.is_some() { 2 } else { 1 };"}],"del_contents":[{"Del":") -> Result, T::Error> {\n"},{"Del":" let size = core::mem::size_of::>()\n + if k1v1.is_some() {\n core::mem::size_of::>()\n"},{"Del":" } else {\n 0\n };\n"}]}},{"Edit":{"inode":{"change":3,"pos":5929},"path":"sanakirja-core/src/btree/page/put.rs","line":34,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":9326},"to":{"change":3,"start":7866,"end":7930},"introduced_by":3}],"inode":{"change":3,"pos":5929}}},"contents":[{"Del":" let size = core::mem::size_of::>();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":5929},"path":"sanakirja-core/src/btree/page/put.rs","line":35,"ins":{"up_context":[{"change":3,"pos":9575}],"down_context":[{"change":3,"pos":9656}],"flag":"BLOCK","start":25271,"end":25338,"inode":{"change":3,"pos":5929}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":9624},"to":{"change":3,"start":9624,"end":9656},"introduced_by":3}],"inode":{"change":3,"pos":5929}},"ins_contents":[{"Add":" hdr.decr(8 + core::mem::size_of::>());"}],"del_contents":[{"Del":" hdr.decr(size);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":5929},"path":"sanakirja-core/src/btree/page/put.rs","line":97,"ins":{"up_context":[{"change":3,"pos":8681}],"down_context":[{"change":3,"pos":8720}],"flag":"BLOCK","start":25339,"end":25397,"inode":{"change":3,"pos":5929}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8681},"to":{"change":3,"start":8681,"end":8720},"introduced_by":3}],"inode":{"change":3,"pos":5929}},"ins_contents":[{"Add":") -> Result, T::Error> {"}],"del_contents":[{"Del":") -> Result, T::Error> {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":5929},"path":"sanakirja-core/src/btree/page/put.rs","line":113,"ins":{"up_context":[{"change":3,"pos":9266}],"down_context":[{"change":3,"pos":9449}],"flag":"BLOCK","start":25398,"end":25469,"inode":{"change":3,"pos":5929}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":9266},"to":{"change":3,"start":11192,"end":11268},"introduced_by":3}],"inode":{"change":3,"pos":5929}},"ins_contents":[{"Add":" let (k, v, r) = L::kv(page.as_page(), L::first::(&s1a));"}],"del_contents":[{"Del":" let (k, v, r) = L::kv(txn, page.as_page(), s1a.first::());\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":3,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":17248}],"down_context":[{"change":3,"pos":17248}],"flag":"BLOCK","start":25470,"end":25731,"inode":{"change":3,"pos":17232}}},"contents":[{"Add":"/// This trait contains methods common to leaves and internal"},{"Add":"/// nodes. These methods are meant to be just a few lines long each,"},{"Add":"/// and avoid duplicating code in higher-level functions where just a"},{"Add":"/// few constants change between internal nodes and leaves."}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":8,"ins":{"up_context":[{"change":3,"pos":17273}],"down_context":[{"change":3,"pos":17612}],"flag":"BLOCK","start":25732,"end":25888,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":17273},"to":{"change":3,"start":8265,"end":8425},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":8425},"to":{"change":3,"start":17546,"end":17612},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6456},"to":{"change":3,"start":17546,"end":17612},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":10568},"to":{"change":3,"start":17546,"end":17612},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":17546},"to":{"change":3,"start":17546,"end":17612},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" /// Is there enough room to add one entry into this page (without cloning)?"},{"Add":" fn can_alloc(hdr: &Header, n: usize) -> bool;"}],"del_contents":[{"Del":" fn can_alloc(hdr: &Header, size: usize) -> bool;\n fn can_compact(hdr: &Header, size: usize) -> bool;\n"},{"Del":" fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":11,"ins":{"up_context":[{"change":3,"pos":17613}],"down_context":[{"change":3,"pos":8426}],"flag":"BLOCK","start":25889,"end":26496,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":17613},"to":{"change":3,"start":17613,"end":17650},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" /// If we clone the page, will there be enough room for one entry?"},{"Add":" fn can_compact(hdr: &Header, n: usize) -> bool;"},{"Add":""},{"Add":" /// Remove the leftmost `n` elements from the page. On leaves,"},{"Add":" /// this moves the last truncated element to the end of the page"},{"Add":" /// and returns a pointer to that element (this function is only"},{"Add":" /// used in `crate::btree::put`, and the pointer becomes invalid"},{"Add":" /// at the end of the `crate::btree::put`)."},{"Add":" ///"},{"Add":" /// Returning the last deleted element isn't required for internal"},{"Add":" /// nodes, since the entries are still valid there."}],"del_contents":[{"Del":" // n = number of items to remove\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":27,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":17803}],"down_context":[{"change":3,"pos":8475}],"flag":"BLOCK","start":26497,"end":26620,"inode":{"change":3,"pos":17232}}},"contents":[{"Add":" /// Allocate a new entry (size inferred), and return the offset on"},{"Add":" /// the page where the new entry can be copied."}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":30,"ins":{"up_context":[{"change":3,"pos":8573}],"down_context":[{"change":3,"pos":18038}],"flag":"BLOCK","start":26621,"end":26760,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":8573},"to":{"change":3,"start":17972,"end":18038},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":17972},"to":{"change":3,"start":17972,"end":18038},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":""},{"Add":" /// Set the right child of the `n`th entry to `r`. If `n == -1`,"},{"Add":" /// this method can be used to set the leftmost child of a page."}],"del_contents":[{"Del":" fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":34,"ins":{"up_context":[{"change":3,"pos":18099}],"down_context":[{"change":3,"pos":8574}],"flag":"BLOCK","start":26761,"end":26881,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":18099},"to":{"change":3,"start":18099,"end":18160},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":""},{"Add":" /// \"Slices\" of offsets, which aren't really slices in the case of"},{"Add":" /// leaves, but just intervals or \"ranges\"."}],"del_contents":[{"Del":" type Offset: Into<(u64, u16)> + Copy + core::fmt::Debug;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":39,"ins":{"up_context":[{"change":3,"pos":18261}],"down_context":[{"change":3,"pos":18439}],"flag":"BLOCK","start":26882,"end":27331,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":18261},"to":{"change":3,"start":18261,"end":18297},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":18297},"to":{"change":3,"start":8639,"end":8693},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":8693},"to":{"change":3,"start":10825,"end":10842},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5234},"to":{"change":3,"start":10825,"end":10842},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":10825},"to":{"change":3,"start":10825,"end":10842},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":10842},"to":{"change":3,"start":18357,"end":18439},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":18357},"to":{"change":3,"start":18357,"end":18439},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" ) -> Offsets<'a>;"},{"Add":""},{"Add":" /// First element of a slice offset. For the sake of code"},{"Add":" /// simplicity, we return a `u64` even for leaves. In internal"},{"Add":" /// nodes, the 52 MSBs encode a child page, and the 12 LSBs encode"},{"Add":" /// an offset in the page."},{"Add":" fn first<'a, K, V>(off: &Offsets<'a>) -> u64;"},{"Add":""},{"Add":" /// The tuple and right child at offset `off`."},{"Add":" fn kv<'a, K: Storable, V: Storable>(page: crate::Page, off: u64) -> (&'a K, &'a V, u64);"}],"del_contents":[{"Del":" ) -> Offsets<'a, Self::Offset>;\n"},{"Del":" fn kv<'a, T: LoadPage, K: Storable, V: Storable>(\n"},{"Del":" txn: &T,\n"},{"Del":" page: crate::Page,\n off: (u64, u16),\n ) -> (&'a K, &'a V, u64);\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":51,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":18442}],"down_context":[{"change":3,"pos":18442}],"flag":"BLOCK","start":27332,"end":27357,"inode":{"change":3,"pos":17232}}},"contents":[{"Add":"/// The type of offsets."}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":53,"ins":{"up_context":[{"change":3,"pos":18466}],"down_context":[{"change":3,"pos":18512}],"flag":"BLOCK","start":27358,"end":27499,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":18466},"to":{"change":3,"start":18466,"end":18512},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":"pub enum Offsets<'a> {"},{"Add":" /// Slices of child pages and offset-in-page for internal nodes,"},{"Add":" Slice(&'a [u64]),"},{"Add":" /// Ranges for leaves."}],"del_contents":[{"Del":"pub enum Offsets<'a, A> {\n Slice(&'a [A]),\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":60,"ins":{"up_context":[{"change":3,"pos":18551}],"down_context":[{"change":3,"pos":18605}],"flag":"BLOCK","start":27500,"end":27703,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":18551},"to":{"change":3,"start":18551,"end":18605},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":"impl<'a> Offsets<'a> {"},{"Add":" /// Splitting an offset slice, with the same semantics as"},{"Add":" /// `split_at` for slices, except if `mid` is equal to the length,"},{"Add":" /// in which case we return `(self, &[])`."}],"del_contents":[{"Del":"impl<'a, A: Into<(u64, u16)> + Copy> Offsets<'a, A> {\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":67,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":18735},"to":{"change":3,"start":18735,"end":18796},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" debug!(\"split_at: {:?} {:?}\", s.len(), mid);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":80,"ins":{"up_context":[{"change":3,"pos":19245}],"down_context":[{"change":3,"pos":19397}],"flag":"BLOCK","start":27704,"end":28802,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":19245},"to":{"change":3,"start":8694,"end":8763},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":8763},"to":{"change":3,"start":19330,"end":19397},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":10922},"to":{"change":3,"start":19330,"end":19397},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":19330},"to":{"change":3,"start":19330,"end":19397},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":"}"},{"Add":""},{"Add":"pub struct Leaf {}"},{"Add":"pub struct Internal {}"},{"Add":""},{"Add":"impl Alloc for Leaf {"},{"Add":" // Checking if there's enough room is just bookkeeping."},{"Add":" fn can_alloc(hdr: &Header, n: usize) -> bool {"},{"Add":" let f = core::mem::size_of::>();"},{"Add":" let al = core::mem::align_of::>();"},{"Add":" let header_size = (HDR + al - 1) & !(al - 1);"},{"Add":" header_size + (hdr.n() as usize + n) * f <= PAGE_SIZE"},{"Add":" }"},{"Add":""},{"Add":" /// There's no possible compaction on leaves, it's the same as allocating."},{"Add":" fn can_compact(hdr: &Header, n: usize) -> bool {"},{"Add":" Self::can_alloc::(hdr, n)"},{"Add":" }"},{"Add":""},{"Add":" fn set_right_child(_: &mut MutPage, _: isize, _: u64) {}"},{"Add":""},{"Add":" fn offset_slice<'a, T: LoadPage, K: Storable, V: Storable>("},{"Add":" page: crate::Page<'a>,"},{"Add":" ) -> Offsets<'a> {"},{"Add":" let hdr = header(page);"},{"Add":" Offsets::Range(0..(hdr.n() as usize))"},{"Add":" }"},{"Add":""},{"Add":" /// This returns an offset on the page, so we need to compute that."},{"Add":" fn first<'a, K, V>(off: &Offsets<'a>) -> u64 {"},{"Add":" match off {"},{"Add":" Offsets::Slice(_) => unreachable!(),"}],"del_contents":[{"Del":" pub fn first(&self) -> (u64, u16) {\n"},{"Del":" match self {\n Offsets::Slice(s) => s[0].into(),\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":116,"ins":{"up_context":[{"change":3,"pos":19601}],"down_context":[{"change":3,"pos":19657}],"flag":"BLOCK","start":28803,"end":28854,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":19601},"to":{"change":3,"start":19601,"end":19657},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" (hdr_size + r.start * size) as u64"}],"del_contents":[{"Del":" (0, (hdr_size + r.start * size) as u16)\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":120,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":19687},"to":{"change":3,"start":19687,"end":19689},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":"}\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":121,"ins":{"up_context":[{"change":3,"pos":19690}],"down_context":[{"change":3,"pos":19732}],"flag":"BLOCK","start":28855,"end":29100,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":19690},"to":{"change":3,"start":19690,"end":19732},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" fn kv<'a, K: Storable, V: Storable>(page: crate::Page, off: u64) -> (&'a K, &'a V, u64) {"},{"Add":" unsafe {"},{"Add":" let tup = &*(page.data.as_ptr().add(off as usize) as *const Tuple);"},{"Add":" (&tup.k, &tup.v, 0)"},{"Add":" }"},{"Add":" }"}],"del_contents":[{"Del":"pub struct Leaf {}\npub struct Internal {}\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":128,"ins":{"up_context":[{"change":3,"pos":19733}],"down_context":[{"change":3,"pos":12455}],"flag":"BLOCK","start":29101,"end":29356,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":19733},"to":{"change":3,"start":19733,"end":19755},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":19755},"to":{"change":3,"start":8828,"end":8908},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" /// Here, we just move `total - *n` elements to the right, and"},{"Add":" /// increase the bookkeeping values (occupied bytes and number of"},{"Add":" /// elements)."},{"Add":" fn alloc_insert(new: &mut MutPage, n: &mut isize, _: u64) -> usize {"}],"del_contents":[{"Del":"impl Alloc for Leaf {\n"},{"Del":" fn can_alloc(hdr: &Header, size: usize) -> bool {\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":133,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":12508},"to":{"change":3,"start":8909,"end":8964},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":8964},"to":{"change":3,"start":6548,"end":6582},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":47760},"to":{"change":3,"start":6548,"end":6582},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6582},"to":{"change":3,"start":47760,"end":47814},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":47760},"to":{"change":3,"start":47760,"end":47814},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":47814},"to":{"change":3,"start":6583,"end":6648},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":47888},"to":{"change":3,"start":20371,"end":20377},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6648},"to":{"change":3,"start":20371,"end":20377},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":20371},"to":{"change":3,"start":20371,"end":20377},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":20377},"to":{"change":3,"start":8965,"end":9047},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" let al = core::mem::align_of::>();\n"},{"Del":" assert_eq!(size % al, 0);\n"},{"Del":" let header_size = (HDR + al - 1) & !(al - 1);\n"},{"Del":" header_size + (hdr.n() as usize) * f + size <= PAGE_SIZE\n"},{"Del":" }\n"},{"Del":" fn can_compact(hdr: &Header, size: usize) -> bool {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":134,"ins":{"up_context":[{"change":3,"pos":9102}],"down_context":[{"change":3,"pos":20836}],"flag":"BLOCK","start":29357,"end":29827,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":9102},"to":{"change":3,"start":6742,"end":6776},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":47930},"to":{"change":3,"start":6742,"end":6776},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6776},"to":{"change":3,"start":47930,"end":47984},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":47930},"to":{"change":3,"start":47930,"end":47984},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":47984},"to":{"change":3,"start":6777,"end":7011},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" let hdr_size = (HDR + al - 1) & !(al - 1);"},{"Add":" let hdr_n = header_mut(new).n();"},{"Add":" unsafe {"},{"Add":" core::ptr::copy("},{"Add":" new.0.data.add(hdr_size + (*n as usize) * f),"},{"Add":" new.0.data.add(hdr_size + (*n as usize) * f + f),"},{"Add":" (hdr_n as usize - (*n as usize)) * f,"},{"Add":" );"},{"Add":" }"},{"Add":" let hdr = header_mut(new);"},{"Add":" hdr.set_n(hdr.n() + 1);"},{"Add":" hdr.incr(f);"},{"Add":" hdr_size + (*n as usize) * f"}],"del_contents":[{"Del":" assert_eq!(size % al, 0);\n"},{"Del":" let header_size = (HDR + al - 1) & !(al - 1);\n"},{"Del":" debug!(\n \"can_compact, leaf: {:?} {:?} {:?}\",\n header_size,\n hdr.left_page() & 0xfff,\n size\n );\n header_size + ((hdr.left_page() & 0xfff) as usize) + size <= PAGE_SIZE\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":148,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":20842}],"down_context":[{"change":3,"pos":9103}],"flag":"BLOCK","start":29828,"end":29829,"inode":{"change":3,"pos":17232}}},"contents":[{"Add":""}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":153,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":20995},"to":{"change":3,"start":20995,"end":21047},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" debug!(\"truncate_left {:?} {:?}\", page, n);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":156,"ins":{"up_context":[{"change":3,"pos":48230}],"down_context":[{"change":3,"pos":21303}],"flag":"BLOCK","start":29830,"end":29957,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":48230},"to":{"change":3,"start":48230,"end":48327},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" let hdr = header_mut(page);"},{"Add":" let hdr_n = hdr.n();"},{"Add":" hdr.set_n(hdr_n - n as u16);"},{"Add":" hdr.decr(n * f);"}],"del_contents":[{"Del":" // debug!(\"{:?} {:?} {:?}\", new, hdr.n(), *n);\n let hdr_n = header_mut(page).n();\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":161,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":21304}],"down_context":[{"change":3,"pos":48328}],"flag":"BLOCK","start":29958,"end":30570,"inode":{"change":3,"pos":17232}}},"contents":[{"Add":" // Now, this is a bit trickier. This performs a rotation by 1"},{"Add":" // without all the rotation machinery from the Rust core"},{"Add":" // library."},{"Add":" //"},{"Add":" // Indeed, since we're in a leaf, we are effectively erasing"},{"Add":" // the split entry. There is a choice to be made here, between"},{"Add":" // passing the entry by value or by reference. Because splits"},{"Add":" // might cascade with the same middle entry, passing it by"},{"Add":" // value may be significantly worse if the tree is deep, and"},{"Add":" // is never significantly better (we'll end up copying this"},{"Add":" // entry twice anyway)."}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":173,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":48345},"to":{"change":3,"start":12563,"end":12677},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" // This performs a rotation by 1 without all the rotation\n // machinery from the core lib.\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":189,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":48980},"to":{"change":3,"start":48980,"end":49146},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" }\n debug!(\"{:?} - {:?}\", hdr_n, n);\n let hdr = header_mut(page);\n hdr.set_n(hdr_n - n as u16);\n hdr.decr(n * f);\n unsafe {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":194,"ins":{"up_context":[{"change":3,"pos":23204}],"down_context":[{"change":3,"pos":23456}],"flag":"BLOCK","start":30571,"end":31052,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":23204},"to":{"change":3,"start":23204,"end":23271},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":23271},"to":{"change":3,"start":7213,"end":7250},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7250},"to":{"change":3,"start":23387,"end":23443},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":23387},"to":{"change":3,"start":23387,"end":23443},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":23443},"to":{"change":3,"start":7251,"end":7261},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":"}"},{"Add":""},{"Add":"impl Alloc for Internal {"},{"Add":" fn can_alloc(hdr: &Header, n: usize) -> bool {"},{"Add":" (HDR as usize) + (hdr.n() as usize) * 8 + n * (8 + core::mem::size_of::>())"},{"Add":" < hdr.data() as usize"},{"Add":" }"},{"Add":""},{"Add":" fn can_compact(hdr: &Header, n: usize) -> bool {"},{"Add":" (HDR as usize)"},{"Add":" + ((hdr.left_page() & 0xfff) as usize)"},{"Add":" + n * (8 + core::mem::size_of::>())"},{"Add":" <= PAGE_SIZE"}],"del_contents":[{"Del":" fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {\n"},{"Del":" assert_eq!(size % align, 0);\n"},{"Del":" hdr.set_n(hdr.n() + 1);\n hdr.incr(size);\n"},{"Del":" 0\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":208,"ins":{"up_context":[{"change":3,"pos":23462}],"down_context":[{"change":3,"pos":49628}],"flag":"BLOCK","start":31053,"end":31210,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":23462},"to":{"change":3,"start":9362,"end":9461},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":9461},"to":{"change":3,"start":12678,"end":12731},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":23632},"to":{"change":3,"start":12678,"end":12731},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":12731},"to":{"change":3,"start":9462,"end":9517},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":9517},"to":{"change":3,"start":49481,"end":49532},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":49481},"to":{"change":3,"start":49481,"end":49532},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":49587},"to":{"change":3,"start":49587,"end":49628},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":""},{"Add":" /// Set the right-hand child in the offset array, preserving the"},{"Add":" /// current offset."},{"Add":" fn set_right_child(page: &mut MutPage, n: isize, r: u64) {"}],"del_contents":[{"Del":" fn alloc_insert(new: &mut MutPage, n: &mut isize, _: u64) -> usize {\n"},{"Del":" let f = core::mem::size_of::>();\n"},{"Del":" let al = core::mem::align_of::>();\n"},{"Del":" let hdr_size = (HDR + al - 1) & !(al - 1);\n"},{"Del":" let hdr_n = header_mut(new).n();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":213,"ins":{"up_context":[{"change":3,"pos":49645}],"down_context":[{"change":3,"pos":24915}],"flag":"BLOCK","start":31211,"end":31426,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":49645},"to":{"change":3,"start":49645,"end":49871},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" debug_assert_eq!(r & 0xfff, 0);"},{"Add":" let ptr = page.0.data.offset(HDR as isize + n * 8) as *mut u64;"},{"Add":" let off = u64::from_le(*ptr) & 0xfff;"},{"Add":" *ptr = (r | off as u64).to_le();"}],"del_contents":[{"Del":" core::ptr::copy(\n new.0.data.add(hdr_size + (*n as usize) * f),\n new.0.data.add(hdr_size + (*n as usize) * f + f),\n (hdr_n as usize - (*n as usize)) * f,\n );\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":218,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":24925},"to":{"change":3,"start":49872,"end":49997},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" let hdr = header_mut(new);\n hdr.set_n(hdr.n() + 1);\n hdr.incr(f);\n hdr_size + (*n as usize) * f\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":219,"ins":{"up_context":[{"change":3,"pos":24931}],"down_context":[{"change":3,"pos":24998}],"flag":"BLOCK","start":31427,"end":31553,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":24931},"to":{"change":3,"start":24931,"end":24998},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":""},{"Add":" fn offset_slice<'a, T, K: Storable, V: Storable>(page: crate::Page<'a>) -> Offsets<'a> {"},{"Add":" let hdr = header(page);"}],"del_contents":[{"Del":" fn set_offset(new: &mut MutPage, n: isize, _: u64, off: u16) {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":223,"ins":{"up_context":[{"change":3,"pos":25015}],"down_context":[{"change":3,"pos":25122}],"flag":"BLOCK","start":31554,"end":31718,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":25015},"to":{"change":3,"start":25015,"end":25122},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" Offsets::Slice(core::slice::from_raw_parts("},{"Add":" page.data.as_ptr().add(HDR) as *const u64,"},{"Add":" hdr.n() as usize,"},{"Add":" ))"}],"del_contents":[{"Del":" let ptr = new.0.data.offset(HDR as isize + n * 2) as *mut u16;\n *ptr = off.to_le();\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":229,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":25138},"to":{"change":3,"start":25138,"end":25229},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" fn set_right_child(_: &mut MutPage, _: isize, _: u64) {}\n type Offset = LeafOffset;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":230,"ins":{"up_context":[{"change":3,"pos":25230}],"down_context":[{"change":3,"pos":25746}],"flag":"BLOCK","start":31719,"end":31888,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":25230},"to":{"change":3,"start":9518,"end":9582},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":9582},"to":{"change":3,"start":25300,"end":25400},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5381},"to":{"change":3,"start":25300,"end":25400},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":11936},"to":{"change":3,"start":25300,"end":25400},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":25300},"to":{"change":3,"start":25300,"end":25400},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":25400},"to":{"change":3,"start":49998,"end":50044},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" fn first<'a, K, V>(off: &Offsets<'a>) -> u64 {"},{"Add":" match off {"},{"Add":" Offsets::Slice(s) => s[0],"},{"Add":" Offsets::Range(_) => unreachable!(),"},{"Add":" }"}],"del_contents":[{"Del":" fn offset_slice<'a, T: LoadPage, K: Storable, V: Storable>(\n"},{"Del":" page: crate::Page<'a>,\n ) -> Offsets<'a, Self::Offset> {\n let hdr = header(page);\n"},{"Del":" Offsets::Range(0..(hdr.n() as usize))\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":236,"ins":{"up_context":[{"change":3,"pos":25752}],"down_context":[{"change":3,"pos":25900}],"flag":"BLOCK","start":31889,"end":31984,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":25752},"to":{"change":3,"start":9583,"end":9655},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":9655},"to":{"change":3,"start":25812,"end":25900},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":12053},"to":{"change":3,"start":25812,"end":25900},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":25812},"to":{"change":3,"start":25812,"end":25900},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":""},{"Add":" fn kv<'a, K: Storable, V: Storable>(page: crate::Page, off: u64) -> (&'a K, &'a V, u64) {"}],"del_contents":[{"Del":" fn kv<'a, T: LoadPage, K: Storable, V: Storable>(\n _txn: &T,\n"},{"Del":" page: crate::Page,\n (_, off): (u64, u16),\n ) -> (&'a K, &'a V, u64) {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":239,"ins":{"up_context":[{"change":3,"pos":25917}],"down_context":[{"change":3,"pos":26023}],"flag":"BLOCK","start":31985,"end":32124,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":25917},"to":{"change":3,"start":9656,"end":9829},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" let tup = &*(page.data.as_ptr().add((off & 0xfff) as usize) as *const Tuple);"},{"Add":" (&tup.k, &tup.v, off & !0xfff)"}],"del_contents":[{"Del":" let tup = &*(page.data.as_ptr().add(off as usize) as *const Tuple);\n debug!(\">>>>>>>> kv {:?} {:?}\", off, tup);\n (&tup.k, &tup.v, 0)\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":243,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":26039},"to":{"change":3,"start":26039,"end":26041},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":"}\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":244,"ins":{"up_context":[{"change":3,"pos":26042}],"down_context":[{"change":3,"pos":9994}],"flag":"BLOCK","start":32125,"end":32263,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":26042},"to":{"change":3,"start":26042,"end":26068},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":26068},"to":{"change":3,"start":9830,"end":9910},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":9910},"to":{"change":3,"start":10176,"end":10222},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7404},"to":{"change":3,"start":10176,"end":10222},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":10222},"to":{"change":3,"start":26259,"end":26346},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7404},"to":{"change":3,"start":26259,"end":26346},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":12370},"to":{"change":3,"start":26259,"end":26346},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":26259},"to":{"change":3,"start":26259,"end":26346},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":26346},"to":{"change":3,"start":9911,"end":9993},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":9993},"to":{"change":3,"start":7497,"end":7746},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7497},"to":{"change":3,"start":7497,"end":7746},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7746},"to":{"change":3,"start":5447,"end":5472},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7766},"to":{"change":3,"start":26527,"end":26533},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5472},"to":{"change":3,"start":26527,"end":26533},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":26527},"to":{"change":3,"start":26527,"end":26533},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" // Much simpler than in leaves, because we just need to move the"},{"Add":" // offsets. There's a little bit of bookkeeping involved though."}],"del_contents":[{"Del":"impl Alloc for Internal {\n"},{"Del":" fn can_alloc(hdr: &Header, size: usize) -> bool {\n"},{"Del":" debug!(\"can_alloc {:?}\", hdr.data());\n"},{"Del":" (HDR as usize) + (hdr.n() as usize) * 8 + 8 + size < hdr.data() as usize\n }\n"},{"Del":" fn can_compact(hdr: &Header, size: usize) -> bool {\n"},{"Del":" debug!(\n \"can_compact, internal: {:?} {:?} {:?}\",\n HDR,\n hdr.left_page() & 0xfff,\n size\n );\n (HDR as usize) + (hdr.n() as usize) * 8 + ((hdr.left_page() & 0xfff) as usize) + 8 + size\n"},{"Del":" <= PAGE_SIZE\n"},{"Del":" }\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":250,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":26686},"to":{"change":3,"start":26686,"end":26795},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" // The following line copies the left child of the last entry\n // (hence the `- 8` and `- 1`)\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":252,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":26854}],"down_context":[{"change":3,"pos":26854}],"flag":"BLOCK","start":32264,"end":32399,"inode":{"change":3,"pos":17232}}},"contents":[{"Add":" // We want to copy the left child of the first entry that"},{"Add":" // will be kept alive as the left child of the page."}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":257,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":26977}],"down_context":[{"change":3,"pos":26977}],"flag":"BLOCK","start":32400,"end":32570,"inode":{"change":3,"pos":17232}}},"contents":[{"Add":" // We're removing n entries, so we need to copy the"},{"Add":" // remaining `hdr_n - n`, plus the leftmost child"},{"Add":" // (hence the + 1)."}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":263,"ins":{"up_context":[{"change":3,"pos":27048}],"down_context":[{"change":3,"pos":27627}],"flag":"BLOCK","start":32571,"end":32723,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":27048},"to":{"change":3,"start":12732,"end":12785},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":12785},"to":{"change":3,"start":7767,"end":7831},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":2033},"to":{"change":3,"start":7767,"end":7831},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50098},"to":{"change":3,"start":7767,"end":7831},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" // Remaining occupied size on the page (minus the header)."},{"Add":" let size = (8 + core::mem::size_of::>()) * (hdr_n as usize - n);"}],"del_contents":[{"Del":" let f = core::mem::size_of::>();\n"},{"Del":" let size = { ((8 + f) * (hdr_n as usize - n)) as u64 };\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":267,"ins":{"up_context":[{"change":3,"pos":27700}],"down_context":[{"change":3,"pos":27798}],"flag":"BLOCK","start":32724,"end":33008,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":27700},"to":{"change":3,"start":27700,"end":27798},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" // Because the leftmost child has been copied from an entry"},{"Add":" // containing an offset, its 12 LBSs are still enconding an"},{"Add":" // offset on the page, whereas it should encode the occupied"},{"Add":" // bytes on the page. Reset it."},{"Add":" hdr.set_occupied(size as u64);"}],"del_contents":[{"Del":" debug!(\"truncate_left {:?} {:?}\", hdr.left_page(), size);\n hdr.set_occupied(size);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":274,"ins":{"up_context":[{"change":3,"pos":27817}],"down_context":[{"change":3,"pos":10043}],"flag":"BLOCK","start":33009,"end":33010,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":27817},"to":{"change":3,"start":27817,"end":27884},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":27884},"to":{"change":3,"start":7832,"end":7942},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7942},"to":{"change":3,"start":28000,"end":28056},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":28000},"to":{"change":3,"start":28000,"end":28056},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":28056},"to":{"change":3,"start":7943,"end":7970},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7970},"to":{"change":3,"start":28069,"end":28075},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":28069},"to":{"change":3,"start":28069,"end":28075},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":""}],"del_contents":[{"Del":" fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {\n"},{"Del":" assert_eq!(size % align, 0);\n let data = hdr.data();\n hdr.set_data(data - size as u16);\n"},{"Del":" hdr.set_n(hdr.n() + 1);\n hdr.incr(size);\n"},{"Del":" data - size as u16\n"},{"Del":" }\n"}]}},{"Replacement":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":276,"ins":{"up_context":[{"change":3,"pos":10142}],"down_context":[{"change":3,"pos":28451}],"flag":"BLOCK","start":33011,"end":33440,"inode":{"change":3,"pos":17232}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":10142},"to":{"change":3,"start":10142,"end":10251},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":10251},"to":{"change":3,"start":28245,"end":28356},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":28245},"to":{"change":3,"start":28245,"end":28356},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":28356},"to":{"change":3,"start":10252,"end":10336},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":10336},"to":{"change":3,"start":28426,"end":28451},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":28426},"to":{"change":3,"start":28426,"end":28451},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":28451},"to":{"change":3,"start":10337,"end":10380},"introduced_by":3}],"inode":{"change":3,"pos":17232}},"ins_contents":[{"Add":" let hdr = header_mut(new);"},{"Add":""},{"Add":" // Move the `data` field one entry to the left."},{"Add":" let data = hdr.data() as u16;"},{"Add":" let off_new = data - core::mem::size_of::>() as u16;"},{"Add":" hdr.set_data(off_new);"},{"Add":""},{"Add":" // Increment the number of entries, add the newly occupied size."},{"Add":" hdr.set_n(hdr.n() + 1);"},{"Add":" hdr.incr(8 + core::mem::size_of::>());"},{"Add":""},{"Add":" let hdr_n = hdr.n();"}],"del_contents":[{"Del":" let size = core::mem::size_of::>();\n debug!(\"alloc internal {:?} {:?}\", n, size);\n"},{"Del":" let (hdr_n, off_new) = {\n let hdr = header_mut(new);\n (\n hdr.n(),\n"},{"Del":" Self::alloc(&mut *hdr, size, core::mem::align_of::>()),\n"},{"Del":" )\n };\n"},{"Del":" debug!(\"off_new = {:?}\", off_new);\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":289,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":28468}],"down_context":[{"change":3,"pos":28468}],"flag":"BLOCK","start":33441,"end":33544,"inode":{"change":3,"pos":17232}}},"contents":[{"Add":" // Make space in the offset array by moving the last"},{"Add":" // `hdr_n - *n` elements."}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":296,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":28684}],"down_context":[{"change":3,"pos":28684}],"flag":"BLOCK","start":33545,"end":33701,"inode":{"change":3,"pos":17232}}},"contents":[{"Add":" // Add the offset."},{"Add":" let ptr = new.0.data.offset(HDR as isize + *n * 8) as *mut u64;"},{"Add":" *ptr = (r | off_new as u64).to_le();"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":300,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":28694},"to":{"change":3,"start":28694,"end":28741},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" Self::set_offset(new, *n, r, off_new);\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":301,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":28766},"to":{"change":3,"start":28766,"end":29253},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" }\n fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16) {\n unsafe {\n let ptr = new.0.data.offset(HDR as isize + n * 8) as *mut u64;\n *ptr = (r | off as u64).to_le();\n }\n }\n fn set_right_child(page: &mut MutPage, n: isize, r: u64) {\n unsafe {\n let ptr = page.0.data.offset(HDR as isize + n * 8) as *mut u64;\n let off = u64::from_le(*ptr) & 0xfff;\n *ptr = (r | off as u64).to_le();\n }\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":302,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":29259},"to":{"change":3,"start":29259,"end":29294},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":29294},"to":{"change":3,"start":10381,"end":10435},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":10435},"to":{"change":3,"start":29364,"end":29672},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":12822},"to":{"change":3,"start":29364,"end":29672},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":29364},"to":{"change":3,"start":29364,"end":29672},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":29672},"to":{"change":3,"start":10436,"end":10508},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":10508},"to":{"change":3,"start":29732,"end":29837},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":12894},"to":{"change":3,"start":29732,"end":29837},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":29732},"to":{"change":3,"start":29732,"end":29837},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":29837},"to":{"change":3,"start":10509,"end":10627},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":10627},"to":{"change":3,"start":29943,"end":29959},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":13046},"to":{"change":3,"start":29943,"end":29959},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":29943},"to":{"change":3,"start":29943,"end":29959},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":" type Offset = InternalOffset;\n\n"},{"Del":" fn offset_slice<'a, T, K: Storable, V: Storable>(\n"},{"Del":" page: crate::Page<'a>,\n ) -> Offsets<'a, Self::Offset> {\n let hdr = header(page);\n unsafe {\n Offsets::Slice(core::slice::from_raw_parts(\n page.data.as_ptr().add(HDR) as *const InternalOffset,\n hdr.n() as usize,\n ))\n }\n }\n"},{"Del":" fn kv<'a, T: LoadPage, K: Storable, V: Storable>(\n _txn: &T,\n"},{"Del":" page: crate::Page,\n (r, off): (u64, u16),\n ) -> (&'a K, &'a V, u64) {\n unsafe {\n"},{"Del":" let tup = &*(page.data.as_ptr().add(off as usize) as *const Tuple);\n (&tup.k, &tup.v, r)\n"},{"Del":" }\n }\n"}]}},{"Edit":{"inode":{"change":3,"pos":17232},"path":"sanakirja-core/src/btree/page/alloc.rs","line":303,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":29961},"to":{"change":3,"start":29961,"end":30539},"introduced_by":3}],"inode":{"change":3,"pos":17232}}},"contents":[{"Del":"#[derive(Debug, Clone, Copy)]\n#[repr(C)]\npub struct LeafOffset(u16);\n\nimpl Into<(u64, u16)> for LeafOffset {\n fn into(self) -> (u64, u16) {\n (0, self.0)\n }\n}\n\nimpl Into for LeafOffset {\n fn into(self) -> usize {\n self.0 as usize\n }\n}\n\n#[derive(Debug, Clone, Copy)]\n#[repr(C)]\npub struct InternalOffset(u64);\n\nimpl Into<(u64, u16)> for InternalOffset {\n fn into(self) -> (u64, u16) {\n (self.0 & !0xfff, (self.0 & 0xfff) as u16)\n }\n}\n\nimpl Into for InternalOffset {\n fn into(self) -> usize {\n self.0 as usize\n }\n}\n"}]}},{"Replacement":{"inode":{"change":3,"pos":45735},"path":"sanakirja-core/src/btree/mod.rs","line":1,"ins":{"up_context":[{"change":3,"pos":45735}],"down_context":[{"change":3,"pos":45736}],"flag":"BLOCK","start":33702,"end":34468,"inode":{"change":3,"pos":45735}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":45735},"to":{"change":3,"start":6033,"end":6067},"introduced_by":3}],"inode":{"change":3,"pos":45735}},"ins_contents":[{"Add":"//! An implementation of B trees. The core operations on B trees"},{"Add":"//! (lookup, iterate, put and del) are generic in the actual"},{"Add":"//! implementation of nodes, via the [`BTreePage`] and"},{"Add":"//! [`BTreeMutPage`]. This allows for a simpler code for the"},{"Add":"//! high-level functions, as well as specialised, high-performance"},{"Add":"//! implementations for the nodes."},{"Add":"//!"},{"Add":"//! Two different implementations are supplied: one in [`page`] for"},{"Add":"//! types with a size known at compile-time, which yields denser"},{"Add":"//! leaves, and hence shallower trees (if the values are really using"},{"Add":"//! the space). The other one, in [`page_unsized`], is for"},{"Add":"//! dynamic-sized types, or types whose representation is dynamic, for"},{"Add":"//! example enums that are `Sized` in Rust, but whose cases vary"},{"Add":"//! widely in size."}],"del_contents":[{"Del":"//! An implementation of B trees.\n"}]}},{"Edit":{"inode":{"change":3,"pos":45735},"path":"sanakirja-core/src/btree/mod.rs","line":16,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":45750}],"down_context":[{"change":3,"pos":45750}],"flag":"BLOCK","start":34469,"end":34484,"inode":{"change":3,"pos":45735}}},"contents":[{"Add":"#[doc(hidden)]"}]}},{"Replacement":{"inode":{"change":3,"pos":45735},"path":"sanakirja-core/src/btree/mod.rs","line":19,"ins":{"up_context":[{"change":3,"pos":5595}],"down_context":[{"change":3,"pos":45816}],"flag":"BLOCK","start":34485,"end":34547,"inode":{"change":3,"pos":45735}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":1668},"to":{"change":3,"start":45766,"end":45816},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5595},"to":{"change":3,"start":45766,"end":45816},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":45766},"to":{"change":3,"start":45766,"end":45816},"introduced_by":3}],"inode":{"change":3,"pos":45735}},"ins_contents":[{"Add":"pub mod del;"},{"Add":"pub use del::del;"},{"Add":"pub mod put;"},{"Add":"pub use put::put;"}],"del_contents":[{"Del":"mod del;\npub use del::*;\nmod put;\npub use put::*;\n"}]}},{"Edit":{"inode":{"change":3,"pos":45735},"path":"sanakirja-core/src/btree/mod.rs","line":26,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":8427},"to":{"change":3,"start":45830,"end":45919},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":50142},"to":{"change":3,"start":45830,"end":45919},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":45830},"to":{"change":3,"start":45830,"end":45919},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":45919},"to":{"change":3,"start":50143,"end":50184},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":50184},"to":{"change":3,"start":45944,"end":46098},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":45944},"to":{"change":3,"start":45944,"end":46098},"introduced_by":3}],"inode":{"change":3,"pos":45735}}},"contents":[{"Del":"\n#[derive(Debug)]\npub struct Ok {\n page: MutPage,\n freed: u64,\n}\n\n#[derive(Debug)]\n"},{"Del":"pub enum Put<'a, K: ?Sized, V: ?Sized> {\n"},{"Del":" Ok(Ok),\n Split {\n split_key: &'a K,\n split_value: &'a V,\n left: MutPage,\n right: MutPage,\n freed: u64,\n },\n}\n"}]}},{"Replacement":{"inode":{"change":3,"pos":45735},"path":"sanakirja-core/src/btree/mod.rs","line":122,"ins":{"up_context":[{"change":3,"pos":13839}],"down_context":[{"change":3,"pos":29463}],"flag":"BLOCK","start":34548,"end":34568,"inode":{"change":3,"pos":45735}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":13839},"to":{"change":3,"start":47307,"end":47324},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":47307},"to":{"change":3,"start":47307,"end":47324},"introduced_by":3}],"inode":{"change":3,"pos":45735}},"ins_contents":[{"Add":" txn: &'a T,"}],"del_contents":[{"Del":" txn: &T,\n"}]}},{"Replacement":{"inode":{"change":3,"pos":45735},"path":"sanakirja-core/src/btree/mod.rs","line":163,"ins":{"up_context":[{"change":3,"pos":48458}],"down_context":[{"change":3,"pos":48500}],"flag":"BLOCK","start":34569,"end":34630,"inode":{"change":3,"pos":45735}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":48458},"to":{"change":3,"start":48458,"end":48500},"introduced_by":3}],"inode":{"change":3,"pos":45735}},"ins_contents":[{"Add":" ) -> Result, T::Error>;"}],"del_contents":[{"Del":" ) -> Result, T::Error>;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":45735},"path":"sanakirja-core/src/btree/mod.rs","line":173,"ins":{"up_context":[{"change":3,"pos":48633}],"down_context":[{"change":3,"pos":48664}],"flag":"BLOCK","start":34631,"end":34681,"inode":{"change":3,"pos":45735}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":48633},"to":{"change":3,"start":48633,"end":48664},"introduced_by":3}],"inode":{"change":3,"pos":45735}},"ins_contents":[{"Add":" ) -> Result;"}],"del_contents":[{"Del":" ) -> Result;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":45735},"path":"sanakirja-core/src/btree/mod.rs","line":183,"ins":{"up_context":[{"change":3,"pos":11326}],"down_context":[{"change":3,"pos":2177}],"flag":"BLOCK","start":34682,"end":34747,"inode":{"change":3,"pos":45735}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":11326},"to":{"change":3,"start":11326,"end":11384},"introduced_by":3}],"inode":{"change":3,"pos":45735}},"ins_contents":[{"Add":" unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V);"}],"del_contents":[{"Del":" fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":45735},"path":"sanakirja-core/src/btree/mod.rs","line":199,"ins":{"up_context":[{"change":3,"pos":49260}],"down_context":[{"change":3,"pos":51192}],"flag":"BLOCK","start":34748,"end":34837,"inode":{"change":3,"pos":45735}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":49260},"to":{"change":3,"start":12786,"end":12821},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":12821},"to":{"change":3,"start":49299,"end":49343},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":30037},"to":{"change":3,"start":49299,"end":49343},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":14472},"to":{"change":3,"start":49299,"end":49343},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":49299},"to":{"change":3,"start":49299,"end":49343},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":14606},"to":{"change":3,"start":50201,"end":50204},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50201},"to":{"change":3,"start":50201,"end":50204},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50204},"to":{"change":3,"start":0,"end":107},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":107},"to":{"change":3,"start":3868,"end":3885},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50204},"to":{"change":3,"start":3868,"end":3885},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3885},"to":{"change":3,"start":10971,"end":11014},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":50567},"to":{"change":3,"start":50267,"end":50280},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":11014},"to":{"change":3,"start":50267,"end":50280},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":9428},"to":{"change":3,"start":50267,"end":50280},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":14664},"to":{"change":3,"start":50267,"end":50280},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50267},"to":{"change":3,"start":50267,"end":50280},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50280},"to":{"change":3,"start":108,"end":136},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":136},"to":{"change":3,"start":50280,"end":50303},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50280},"to":{"change":3,"start":50280,"end":50303},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50303},"to":{"change":3,"start":137,"end":196},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":196},"to":{"change":3,"start":50303,"end":50398},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50303},"to":{"change":3,"start":50303,"end":50398},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50398},"to":{"change":3,"start":197,"end":224},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":224},"to":{"change":3,"start":30618,"end":30636},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50398},"to":{"change":3,"start":30618,"end":30636},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":30636},"to":{"change":3,"start":225,"end":254},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":254},"to":{"change":3,"start":30636,"end":30654},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":30636},"to":{"change":3,"start":30636,"end":30654},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":30654},"to":{"change":3,"start":255,"end":324},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":324},"to":{"change":3,"start":168,"end":194},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":30654},"to":{"change":3,"start":168,"end":194},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":194},"to":{"change":3,"start":325,"end":351},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":194},"to":{"change":3,"start":50436,"end":50452},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":351},"to":{"change":3,"start":50436,"end":50452},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":30654},"to":{"change":3,"start":50436,"end":50452},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50436},"to":{"change":3,"start":50436,"end":50452},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50452},"to":{"change":3,"start":352,"end":379},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":379},"to":{"change":3,"start":50452,"end":50468},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50452},"to":{"change":3,"start":50452,"end":50468},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50468},"to":{"change":3,"start":380,"end":443},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":443},"to":{"change":3,"start":50468,"end":50527},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50468},"to":{"change":3,"start":50468,"end":50527},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50527},"to":{"change":3,"start":444,"end":499},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":499},"to":{"change":3,"start":6361,"end":6378},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6378},"to":{"change":3,"start":11015,"end":11087},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":11087},"to":{"change":3,"start":30668,"end":30691},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50680},"to":{"change":3,"start":30668,"end":30691},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":30691},"to":{"change":3,"start":195,"end":249},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":249},"to":{"change":3,"start":50760,"end":50858},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":30597},"to":{"change":3,"start":50760,"end":50858},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50760},"to":{"change":3,"start":50760,"end":50858},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50858},"to":{"change":3,"start":14163,"end":14233},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":14233},"to":{"change":3,"start":50920,"end":50936},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50920},"to":{"change":3,"start":50920,"end":50936},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50936},"to":{"change":3,"start":14234,"end":14303},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":14303},"to":{"change":3,"start":5975,"end":5991},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5975},"to":{"change":3,"start":5975,"end":5991},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5991},"to":{"change":3,"start":50936,"end":50974},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50936},"to":{"change":3,"start":50936,"end":50974},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":50974},"to":{"change":3,"start":5992,"end":6029},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6029},"to":{"change":3,"start":500,"end":601},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":601},"to":{"change":3,"start":14304,"end":14342},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6029},"to":{"change":3,"start":14304,"end":14342},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":14342},"to":{"change":3,"start":51022,"end":51192},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":30734},"to":{"change":3,"start":51022,"end":51192},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":6029},"to":{"change":3,"start":51022,"end":51192},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":51022},"to":{"change":3,"start":51022,"end":51192},"introduced_by":3}],"inode":{"change":3,"pos":45735}},"ins_contents":[{"Add":" m: del::Concat<'a, K, V, Self>,"},{"Add":" ) -> Result, T::Error>;"}],"del_contents":[{"Del":" m: Concat<'a, K, V, Self>,\n"},{"Del":" ) -> Result, T::Error>;\n"},{"Del":"}\n\n"},{"Del":"/// Represents the result of a merge or rebalance, without touching\n/// the parent of the merge/rebalance.\n"},{"Del":"#[derive(Debug)]\n"},{"Del":"pub enum Op<'a, T, K: ?Sized, V: ?Sized> {\n"},{"Del":" Merged {\n"},{"Del":" // New merged page.\n"},{"Del":" page: MutPage,\n"},{"Del":" // Pages freed by the merge (0 meaning \"no page\").\n"},{"Del":" freed: [u64; 2],\n marker: core::marker::PhantomData,\n },\n Rebalanced {\n"},{"Del":" // New middle key.\n"},{"Del":" k: &'a K,\n"},{"Del":" // New middle value.\n"},{"Del":" v: &'a V,\n"},{"Del":" // Do `k` and `v` come from a page shared with another tree?\n"},{"Del":" incr_kv_rc: bool,\n"},{"Del":" // New left page.\n"},{"Del":" l: u64,\n"},{"Del":" // New right page.\n"},{"Del":" r: u64,\n"},{"Del":" // Pages freed by the rebalance (0 meaning \"no page\").\n"},{"Del":" freed: [u64; 2],\n },\n Put(Put<'a, K, V>),\n}\n\n"},{"Del":"/// Represents a page with modifications from a merge.\n"},{"Del":"#[derive(Debug)]\n"},{"Del":"pub struct ModifiedPage<'a, K: ?Sized, V: ?Sized, P: BTreePage> {\n"},{"Del":" pub page: CowPage,\n"},{"Del":" // Whether the page is mutable with another tree.\n"},{"Del":" pub mutable: bool,\n // Start copying c0 (keep `page`'s left child).\n pub c0: P::Cursor,\n"},{"Del":" // If > 0, replace the right child of c0's last element with `l`.\n"},{"Del":" pub l: u64,\n"},{"Del":" // If > 0, replace the left child of c1's last element with `r`.\n"},{"Del":" pub r: u64,\n"},{"Del":" // Possibly insert a new binding.\n"},{"Del":" pub ins: Option<(&'a K, &'a V)>,\n"},{"Del":" // If a rebalance causes a split, we might need to insert an entry\n // after the replacement.\n"},{"Del":" pub ins2: Option<(&'a K, &'a V)>,\n"},{"Del":" // The first element of c1 is to be deleted, the others must be copied.\n pub c1: P::Cursor,\n // Whether to skip `c1`'s first element.\n pub skip_first: bool,\n"}]}},{"Edit":{"inode":{"change":3,"pos":45735},"path":"sanakirja-core/src/btree/mod.rs","line":203,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":51195},"to":{"change":3,"start":602,"end":698},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":698},"to":{"change":3,"start":51660,"end":51677},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":51660},"to":{"change":3,"start":51660,"end":51677},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":51677},"to":{"change":3,"start":11088,"end":11154},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":11154},"to":{"change":3,"start":699,"end":791},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":9834},"to":{"change":3,"start":699,"end":791},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":791},"to":{"change":3,"start":31033,"end":31062},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":9834},"to":{"change":3,"start":31033,"end":31062},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":51779},"to":{"change":3,"start":31033,"end":31062},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":31062},"to":{"change":3,"start":792,"end":830},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":830},"to":{"change":3,"start":31110,"end":31134},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":14954},"to":{"change":3,"start":31110,"end":31134},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":31110},"to":{"change":3,"start":31110,"end":31134},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":31134},"to":{"change":3,"start":831,"end":919},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":919},"to":{"change":3,"start":51969,"end":51996},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":51969},"to":{"change":3,"start":51969,"end":51996},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":51996},"to":{"change":3,"start":920,"end":1118},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":1118},"to":{"change":3,"start":5818,"end":5850},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":51996},"to":{"change":3,"start":5818,"end":5850},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":5850},"to":{"change":3,"start":51996,"end":51999},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":51996},"to":{"change":3,"start":51996,"end":51999},"introduced_by":3}],"inode":{"change":3,"pos":45735}}},"contents":[{"Del":"/// Represents the concatenation of a modified page and one of its\n/// sibling (left or right).\n"},{"Del":"#[derive(Debug)]\n"},{"Del":"pub struct Concat<'a, K: ?Sized, V: ?Sized, P: BTreePage> {\n"},{"Del":" /// Modified page.\n pub modified: ModifiedPage<'a, K, V, P>,\n /// Middle element.\n"},{"Del":" pub mid: (&'a K, &'a V),\n"},{"Del":" /// Sibling of the modified page.\n"},{"Del":" pub other: CowPage,\n"},{"Del":" /// Is the modified field on the left or on the right of the\n /// concatenation?\n"},{"Del":" pub mod_is_left: bool,\n"},{"Del":" /// Is the other page owned by this tree? If not, it means `other`\n /// is shared with another tree, and hence we need to increase the\n /// reference count of entries coming from `other`.\n"},{"Del":" pub other_is_mutable: bool,\n"},{"Del":"}\n\n"}]}},{"Edit":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":1,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":52511}],"down_context":[{"change":3,"pos":52989}],"flag":"BLOCK","start":34838,"end":34867,"inode":{"change":3,"pos":52511}}},"contents":[{"Add":"//! Deletions from a B tree."}]}},{"Edit":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":3,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":53011}],"down_context":[{"change":3,"pos":53011}],"flag":"BLOCK","start":34868,"end":34895,"inode":{"change":3,"pos":52511}}},"contents":[{"Add":"use super::put::{Ok, Put};"}]}},{"Edit":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":6,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":53046}],"down_context":[{"change":3,"pos":53074}],"flag":"BLOCK","start":34896,"end":37281,"inode":{"change":3,"pos":52511}}},"contents":[{"Add":""},{"Add":"/// Represents the result of a merge or rebalance, without touching"},{"Add":"/// the parent of the merge/rebalance."},{"Add":"#[derive(Debug)]"},{"Add":"pub enum Op<'a, T, K: ?Sized, V: ?Sized> {"},{"Add":" Merged {"},{"Add":" // New merged page."},{"Add":" page: MutPage,"},{"Add":" // Pages freed by the merge (0 meaning \"no page\")."},{"Add":" freed: [u64; 2],"},{"Add":" marker: core::marker::PhantomData,"},{"Add":" },"},{"Add":" Rebalanced {"},{"Add":" // New middle key."},{"Add":" k: &'a K,"},{"Add":" // New middle value."},{"Add":" v: &'a V,"},{"Add":" // Do `k` and `v` come from a page shared with another tree?"},{"Add":" incr_kv_rc: bool,"},{"Add":" // New left page."},{"Add":" l: u64,"},{"Add":" // New right page."},{"Add":" r: u64,"},{"Add":" // Pages freed by the rebalance (0 meaning \"no page\")."},{"Add":" freed: [u64; 2],"},{"Add":" },"},{"Add":" Put(crate::btree::put::Put<'a, K, V>),"},{"Add":"}"},{"Add":""},{"Add":"/// Represents a page with modifications from a merge."},{"Add":"#[derive(Debug)]"},{"Add":"pub struct ModifiedPage<'a, K: ?Sized, V: ?Sized, P: BTreePage> {"},{"Add":" pub page: CowPage,"},{"Add":" // Whether the page is mutable with another tree."},{"Add":" pub mutable: bool,"},{"Add":" // Start copying c0 (keep `page`'s left child)."},{"Add":" pub c0: P::Cursor,"},{"Add":" // If > 0, replace the right child of c0's last element with `l`."},{"Add":" pub l: u64,"},{"Add":" // If > 0, replace the left child of c1's last element with `r`."},{"Add":" pub r: u64,"},{"Add":" // Possibly insert a new binding."},{"Add":" pub ins: Option<(&'a K, &'a V)>,"},{"Add":" // If a rebalance causes a split, we might need to insert an entry"},{"Add":" // after the replacement."},{"Add":" pub ins2: Option<(&'a K, &'a V)>,"},{"Add":" // The first element of c1 is to be deleted, the others must be copied."},{"Add":" pub c1: P::Cursor,"},{"Add":" // Whether to skip `c1`'s first element."},{"Add":" pub skip_first: bool,"},{"Add":"}"},{"Add":""},{"Add":"/// Represents the concatenation of a modified page and one of its"},{"Add":"/// sibling (left or right)."},{"Add":"#[derive(Debug)]"},{"Add":"pub struct Concat<'a, K: ?Sized, V: ?Sized, P: BTreePage> {"},{"Add":" /// Modified page."},{"Add":" pub modified: ModifiedPage<'a, K, V, P>,"},{"Add":" /// Middle element."},{"Add":" pub mid: (&'a K, &'a V),"},{"Add":" /// Sibling of the modified page."},{"Add":" pub other: CowPage,"},{"Add":" /// Is the modified field on the left or on the right of the"},{"Add":" /// concatenation?"},{"Add":" pub mod_is_left: bool,"},{"Add":" /// Is the other page owned by this tree? If not, it means `other`"},{"Add":" /// is shared with another tree, and hence we need to increase the"},{"Add":" /// reference count of entries coming from `other`."},{"Add":" pub other_is_mutable: bool,"},{"Add":"}"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":92,"ins":{"up_context":[{"change":3,"pos":9635}],"down_context":[{"change":3,"pos":7504}],"flag":"BLOCK","start":37282,"end":37330,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":9635},"to":{"change":3,"start":7448,"end":7504},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" if cursor.set(txn, key, value)?.is_none() {"}],"del_contents":[{"Del":" if cursor.set(txn, Some((key, value)))?.is_none() {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":104,"ins":{"up_context":[{"change":3,"pos":53703}],"down_context":[{"change":3,"pos":53703}],"flag":"BLOCK","start":37331,"end":37432,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":53703},"to":{"change":3,"start":404,"end":449},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":"/// Delete the entry pointed to by `cursor`. The cursor can't be used"},{"Add":"/// after this."},{"Add":"#[doc(hidden)]"}],"del_contents":[{"Del":"/// Delete the entry pointed to by `cursor`.\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":127,"ins":{"up_context":[{"change":3,"pos":7959}],"down_context":[{"change":3,"pos":9636}],"flag":"BLOCK","start":37433,"end":37469,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7959},"to":{"change":3,"start":13531,"end":13565},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" if p0 < cursor.first_rc_len() {"}],"del_contents":[{"Del":" if p0 < cursor.first_rc_len {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":140,"ins":{"up_context":[{"change":3,"pos":7994}],"down_context":[{"change":3,"pos":6150}],"flag":"BLOCK","start":37470,"end":37655,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7994},"to":{"change":3,"start":13637,"end":13710},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":13710},"to":{"change":3,"start":8067,"end":8093},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7185},"to":{"change":3,"start":8067,"end":8093},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8067},"to":{"change":3,"start":8067,"end":8093},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8093},"to":{"change":3,"start":13711,"end":13841},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":13841},"to":{"change":3,"start":8093,"end":8182},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8093},"to":{"change":3,"start":8093,"end":8182},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8182},"to":{"change":3,"start":13842,"end":13900},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":13900},"to":{"change":3,"start":8240,"end":8302},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":7255},"to":{"change":3,"start":8240,"end":8302},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8240},"to":{"change":3,"start":8240,"end":8302},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8302},"to":{"change":3,"start":13901,"end":13963},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" let right_subtree = P::right_child(cur.page.as_page(), &cur.cursor);"},{"Add":" cursor.set_first_leaf(txn, right_subtree)?;"},{"Add":" let leaf_is_shared = cursor.len() >= cursor.first_rc_len();"}],"del_contents":[{"Del":" let mut left_page = P::right_child(cur.page.as_page(), &cur.cursor);\n"},{"Del":" while left_page > 0 {\n"},{"Del":" if cursor.first_rc_len >= N_CURSORS && txn.rc(left_page)? >= 2 {\n cursor.first_rc_len = cursor.len()\n }\n"},{"Del":" let page = txn.load_page(left_page)?;\n let curs = P::cursor_first(&page);\n"},{"Del":" left_page = P::left_child(page.as_page(), &curs);\n"},{"Del":" cursor.push(PageCursor { page, cursor: curs });\n }\n"},{"Del":" let leaf_is_shared = cursor.len() >= cursor.first_rc_len;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":188,"ins":{"up_context":[{"change":3,"pos":15224}],"down_context":[{"change":3,"pos":8824}],"flag":"BLOCK","start":37656,"end":37711,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15224},"to":{"change":3,"start":15224,"end":15277},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" if cursor.len() + 1 >= cursor.first_rc_len() {"}],"del_contents":[{"Del":" if cursor.len() + 1 >= cursor.first_rc_len {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":195,"ins":{"up_context":[{"change":3,"pos":15368}],"down_context":[{"change":3,"pos":8927}],"flag":"BLOCK","start":37712,"end":37765,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15368},"to":{"change":3,"start":15368,"end":15419},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" let root_is_shared = cursor.first_rc_len() == 1;"}],"del_contents":[{"Del":" let root_is_shared = cursor.first_rc_len == 1;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":227,"ins":{"up_context":[{"change":3,"pos":2827}],"down_context":[{"change":3,"pos":15473}],"flag":"BLOCK","start":37766,"end":37821,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2827},"to":{"change":3,"start":15420,"end":15473},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" let is_rc = cursor.len() >= cursor.first_rc_len();"}],"del_contents":[{"Del":" let is_rc = cursor.len() >= cursor.first_rc_len;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":278,"ins":{"up_context":[{"change":3,"pos":15719}],"down_context":[{"change":3,"pos":33754}],"flag":"BLOCK","start":37822,"end":37864,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":15719},"to":{"change":3,"start":15719,"end":15759},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" let rc_level = cursor.first_rc_len();"}],"del_contents":[{"Del":" let rc_level = cursor.first_rc_len;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":285,"ins":{"up_context":[{"change":3,"pos":2423}],"down_context":[{"change":3,"pos":2496}],"flag":"BLOCK","start":37865,"end":37938,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2423},"to":{"change":3,"start":11700,"end":11762},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" let (k0, v0) = unsafe { P::from_saved(k0v0.as_ref().unwrap()) };"}],"del_contents":[{"Del":" let (k0, v0) = P::from_saved(k0v0.as_ref().unwrap());\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":364,"ins":{"up_context":[{"change":3,"pos":20246}],"down_context":[{"change":3,"pos":34437}],"flag":"BLOCK","start":37939,"end":37995,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":20246},"to":{"change":3,"start":16352,"end":16406},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" let mutable = cursor.len() < cursor.first_rc_len();"}],"del_contents":[{"Del":" let mutable = cursor.len() < cursor.first_rc_len;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":431,"ins":{"up_context":[{"change":3,"pos":3208}],"down_context":[{"change":3,"pos":3280}],"flag":"BLOCK","start":37996,"end":38068,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3208},"to":{"change":3,"start":11814,"end":11875},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" last_op.ins = Some(unsafe { P::from_saved(k0v0) });"}],"del_contents":[{"Del":" last_op.ins = Some(P::from_saved(k0v0));\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":460,"ins":{"up_context":[{"change":3,"pos":3342}],"down_context":[{"change":3,"pos":3414}],"flag":"BLOCK","start":38069,"end":38141,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3342},"to":{"change":3,"start":11876,"end":11937},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" last_op.ins = Some(unsafe { P::from_saved(k0v0) });"}],"del_contents":[{"Del":" last_op.ins = Some(P::from_saved(k0v0));\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":476,"ins":{"up_context":[{"change":3,"pos":16879}],"down_context":[{"change":3,"pos":6243}],"flag":"BLOCK","start":38142,"end":38208,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":16879},"to":{"change":3,"start":11938,"end":11993},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6177},"to":{"change":3,"start":11938,"end":11993},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" let (k0, _) = unsafe { P::from_saved(k0v0) };"}],"del_contents":[{"Del":" let (k0, _) = P::from_saved(k0v0);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":486,"ins":{"up_context":[{"change":3,"pos":37212}],"down_context":[{"change":2,"pos":3640}],"flag":"BLOCK","start":38209,"end":38288,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":37212},"to":{"change":3,"start":16880,"end":16957},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" if cursor.len() + 2 >= cursor.first_rc_len() && !split_key_is_k0 {"}],"del_contents":[{"Del":" if cursor.len() + 2 >= cursor.first_rc_len && !split_key_is_k0 {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":500,"ins":{"up_context":[{"change":3,"pos":6539}],"down_context":[{"change":3,"pos":17071}],"flag":"BLOCK","start":38289,"end":38339,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6539},"to":{"change":3,"start":17023,"end":17071},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" if cursor.len() + 1 < cursor.first_rc_len() {"}],"del_contents":[{"Del":" if cursor.len() + 1 < cursor.first_rc_len {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":633,"ins":{"up_context":[{"change":3,"pos":3885}],"down_context":[{"change":3,"pos":12151}],"flag":"BLOCK","start":38340,"end":38402,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3885},"to":{"change":3,"start":12237,"end":12288},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":" let (k0, _) = unsafe { P::from_saved(k0v0) };"}],"del_contents":[{"Del":" let (k0, _) = P::from_saved(k0v0);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":52511},"path":"sanakirja-core/src/btree/del.rs","line":678,"ins":{"up_context":[{"change":3,"pos":13063}],"down_context":[{"change":3,"pos":12584}],"flag":"BLOCK","start":38403,"end":38454,"inode":{"change":3,"pos":52511}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":13063},"to":{"change":3,"start":12514,"end":12553},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":12514},"to":{"change":3,"start":12514,"end":12553},"introduced_by":3}],"inode":{"change":3,"pos":52511}},"ins_contents":[{"Add":") -> Result, T::Error> {"}],"del_contents":[{"Del":") -> Result, T::Error> {\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":4,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":63754},"to":{"change":3,"start":584,"end":596},"introduced_by":3}],"inode":{"change":3,"pos":63682}}},"contents":[{"Del":"use log::*;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":22,"ins":{"up_context":[{"change":3,"pos":13799}],"down_context":[{"change":3,"pos":12479}],"flag":"BLOCK","start":38455,"end":38483,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":13799},"to":{"change":3,"start":64907,"end":64963},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":64907},"to":{"change":3,"start":64907,"end":64963},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":"/// A position in a B tree."}],"del_contents":[{"Del":"/// A position in a database (mostly for internal use).\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":24,"ins":{"up_context":[{"change":3,"pos":12541}],"down_context":[{"change":3,"pos":2584}],"flag":"BLOCK","start":38484,"end":38542,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":12541},"to":{"change":3,"start":2475,"end":2584},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":11010},"to":{"change":3,"start":2475,"end":2584},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" /// Invariant: the first `len` items are initialised."}],"del_contents":[{"Del":" // Invariant: all items up to (and including) stack[pointer],\n // except possibly 0, are initialised.\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":26,"ins":{"up_context":[{"change":3,"pos":2653}],"down_context":[{"change":3,"pos":17736}],"flag":"BLOCK","start":38543,"end":38909,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2653},"to":{"change":3,"start":17707,"end":17736},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" /// The length of the stack at the position of the first page"},{"Add":" /// shared with another tree. This definition is a little bit"},{"Add":" /// convoluted, but allows for efficient comparisons between"},{"Add":" /// `first_rc_len` and `len` to check whether a page is shared"},{"Add":" /// with another tree."},{"Add":" first_rc_len: usize,"},{"Add":" /// Number of initialised items on the stack."}],"del_contents":[{"Del":" pub first_rc_len: usize,\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":36,"ins":{"up_context":[{"change":3,"pos":65195}],"down_context":[{"change":3,"pos":10823}],"flag":"BLOCK","start":38910,"end":39050,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":65195},"to":{"change":3,"start":12542,"end":12611},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":"impl> Cursor {"},{"Add":" /// Create a new cursor, initialised to the first entry of the B tree."}],"del_contents":[{"Del":"impl<'a, K: ?Sized, V: ?Sized, P: BTreePage> Cursor {\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":91,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":3694},"to":{"change":3,"start":65651,"end":65653},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":65651},"to":{"change":3,"start":65651,"end":65653},"introduced_by":3}],"inode":{"change":3,"pos":63682}}},"contents":[{"Del":"}\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":92,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":65654},"to":{"change":3,"start":12612,"end":12677},"introduced_by":3}],"inode":{"change":3,"pos":63682}}},"contents":[{"Del":"impl> Cursor {\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":99,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":18520}],"down_context":[{"change":3,"pos":3753}],"flag":"BLOCK","start":39051,"end":39133,"inode":{"change":3,"pos":63682}}},"contents":[{"Add":" }"},{"Add":""},{"Add":" pub(super) fn first_rc_len(&self) -> usize {"},{"Add":" self.first_rc_len"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":120,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":34044}],"down_context":[{"change":3,"pos":25073}],"flag":"BLOCK","start":39134,"end":40294,"inode":{"change":3,"pos":63682}}},"contents":[{"Add":" pub(super) fn set_first_leaf("},{"Add":" &mut self,"},{"Add":" txn: &T,"},{"Add":" mut left_page: u64,"},{"Add":" ) -> Result<(), T::Error> {"},{"Add":" while left_page > 0 {"},{"Add":" if self.first_rc_len >= N_CURSORS && txn.rc(left_page)? >= 2 {"},{"Add":" self.first_rc_len = self.len"},{"Add":" }"},{"Add":" let page = txn.load_page(left_page)?;"},{"Add":" let curs = P::cursor_first(&page);"},{"Add":" left_page = P::left_child(page.as_page(), &curs);"},{"Add":" self.push(PageCursor { page, cursor: curs });"},{"Add":" }"},{"Add":" Ok(())"},{"Add":" }"},{"Add":""},{"Add":" /// Reset the cursor to the first element of the database."},{"Add":" pub fn reset<'a, T: LoadPage>(&mut self) {"},{"Add":" self.len = 1;"},{"Add":" let init = unsafe { &mut *self.stack[0].as_mut_ptr() };"},{"Add":" init.cursor = P::cursor_before(&init.page);"},{"Add":" }"},{"Add":""},{"Add":" // An invariant of cursors, fundamental to understand the `next`"},{"Add":" // and `prev` functions below, is that the lower levels (in the"},{"Add":" // tree, upper levels on the stack) are the left children of the"},{"Add":" // cursor's position on a page."},{"Add":""},{"Add":" /// Set the cursor to the first position larger than or equal to"},{"Add":" /// the specified key and value."}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":154,"ins":{"up_context":[{"change":3,"pos":65938}],"down_context":[{"change":3,"pos":34065}],"flag":"BLOCK","start":40295,"end":40333,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":65938},"to":{"change":3,"start":65938,"end":65975},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" k: &K,"},{"Add":" v: Option<&V>,"}],"del_contents":[{"Del":" k: Option<(&K, Option<&V>)>,\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":168,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":18985},"to":{"change":3,"start":18985,"end":19034},"introduced_by":3}],"inode":{"change":3,"pos":63682}}},"contents":[{"Del":" debug!(\"set cursor {:?}\", self.len);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":173,"ins":{"up_context":[{"change":3,"pos":11167}],"down_context":[{"change":3,"pos":67027}],"flag":"BLOCK","start":40334,"end":40510,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":11167},"to":{"change":3,"start":811,"end":847},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":66693},"to":{"change":3,"start":811,"end":847},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":847},"to":{"change":3,"start":66693,"end":66731},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":66693},"to":{"change":3,"start":66693,"end":66731},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":66731},"to":{"change":3,"start":19265,"end":19365},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":15269},"to":{"change":3,"start":66814,"end":66973},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":19365},"to":{"change":3,"start":66814,"end":66973},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":34329},"to":{"change":3,"start":66814,"end":66973},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":8407},"to":{"change":3,"start":66814,"end":66973},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":66814},"to":{"change":3,"start":66814,"end":66973},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":66973},"to":{"change":3,"start":19366,"end":19416},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":19416},"to":{"change":3,"start":848,"end":873},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":67027},"to":{"change":3,"start":848,"end":873},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":873},"to":{"change":3,"start":15270,"end":15337},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" if let Ok((kk, vv, _)) = P::set_cursor(txn, current.page.as_page(), cursor, k, v) {"},{"Add":" if v.is_some() {"},{"Add":" return Ok(Some((kk, vv)));"}],"del_contents":[{"Del":" debug!(\"{:?}\", cursor);\n"},{"Del":" if let Some((k, v)) = k {\n"},{"Del":" if let Ok((kk, vv, _)) = P::set_cursor(txn, current.page.as_page(), cursor, k, v) {\n"},{"Del":" if v.is_some() {\n return Ok(Some((kk, vv)));\n }\n last_match = Some((kk, vv));\n"},{"Del":" last_matching_page = self.len\n"},{"Del":" } else {\n"},{"Del":" debug!(\"not found on page {:?}\", current.page)\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":177,"ins":{"up_context":[{"change":3,"pos":67045}],"down_context":[{"change":3,"pos":67045}],"flag":"BLOCK","start":40511,"end":40602,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":67045},"to":{"change":3,"start":7891,"end":7912},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":7912},"to":{"change":3,"start":15338,"end":15396},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" last_match = Some((kk, vv));"},{"Add":" last_matching_page = self.len"}],"del_contents":[{"Del":" } else {\n"},{"Del":" *cursor = P::cursor_first(¤t.page);\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":199,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":67642}],"down_context":[{"change":3,"pos":11211}],"flag":"BLOCK","start":40603,"end":40742,"inode":{"change":3,"pos":63682}}},"contents":[{"Add":" /// Set the cursor after the last element, so that [`Self::next`]"},{"Add":" /// returns `None`, and [`Self::prev`] returns the last element."}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":228,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":68805},"to":{"change":3,"start":1018,"end":1020},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1020},"to":{"change":3,"start":3453,"end":3459},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3459},"to":{"change":3,"start":11917,"end":11929},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":11929},"to":{"change":3,"start":12678,"end":12776},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":12776},"to":{"change":3,"start":11930,"end":11963},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3567},"to":{"change":3,"start":11930,"end":11963},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":11963},"to":{"change":3,"start":3595,"end":3619},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3595},"to":{"change":3,"start":3595,"end":3619},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2136},"to":{"change":3,"start":2136,"end":2291},"introduced_by":3}],"inode":{"change":3,"pos":63682}}},"contents":[{"Del":"}\n"},{"Del":"impl<\n"},{"Del":" 'a,\n"},{"Del":" K: Storable + ?Sized + core::fmt::Debug,\n V: Storable + ?Sized + core::fmt::Debug,\n"},{"Del":" P: BTreePage + 'a,\n"},{"Del":" > Cursor\n{\n"},{"Del":" // Cursor invariant: the lower levels (in the tree, upper levels\n // on the stack) are the left children of the cursor's position on\n // a page.\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":229,"ins":{"up_context":[{"change":3,"pos":2292}],"down_context":[{"change":3,"pos":68933}],"flag":"BLOCK","start":40743,"end":40969,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2292},"to":{"change":3,"start":7972,"end":8070},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":12059},"to":{"change":3,"start":1156,"end":1184},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":8070},"to":{"change":3,"start":1156,"end":1184},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":11441},"to":{"change":3,"start":1156,"end":1184},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" /// Return the current position of the cursor, and move the cursor"},{"Add":" /// to the next position."},{"Add":" pub fn next<'a, T: LoadPage>("},{"Add":" &mut self,"},{"Add":" txn: &'a T,"},{"Add":" ) -> Result, T::Error> {"}],"del_contents":[{"Del":" pub fn next(&mut self, txn: &'a T) -> Result, T::Error> {\n"},{"Del":" debug!(\"=== next\");\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":236,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":68948},"to":{"change":3,"start":19951,"end":19995},"introduced_by":3}],"inode":{"change":3,"pos":63682}}},"contents":[{"Del":" debug!(\"next: {:?}\", self.len);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":240,"ins":{"up_context":[{"change":3,"pos":13408}],"down_context":[{"change":3,"pos":12354}],"flag":"BLOCK","start":40970,"end":41043,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":13408},"to":{"change":3,"start":2368,"end":2446},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2368},"to":{"change":3,"start":2368,"end":2446},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" // Visit the left child of the page (if any), i.e. push."}],"del_contents":[{"Del":" // Then visit the left child of the page (if any), i.e. push.\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":258,"ins":{"up_context":[{"change":3,"pos":664}],"down_context":[{"change":3,"pos":20265}],"flag":"BLOCK","start":41044,"end":41176,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":664},"to":{"change":3,"start":13036,"end":13077},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" unsafe {"},{"Add":" return Ok(Some((core::mem::transmute(k), core::mem::transmute(v))));"},{"Add":" }"}],"del_contents":[{"Del":" return Ok(Some((k, v)));\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":269,"ins":{"up_context":[{"change":3,"pos":13211}],"down_context":[{"change":3,"pos":13306}],"flag":"BLOCK","start":41177,"end":41380,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":13211},"to":{"change":3,"start":8187,"end":8285},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":8285},"to":{"change":3,"start":457,"end":490},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":13306},"to":{"change":3,"start":457,"end":490},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" /// Move the cursor to the previous entry, and return that"},{"Add":" /// entry."},{"Add":" pub fn prev<'a, T: LoadPage>("},{"Add":" &mut self,"},{"Add":" txn: &'a T,"},{"Add":" ) -> Result, T::Error> {"}],"del_contents":[{"Del":" pub fn prev(&mut self, txn: &'a T) -> Result, T::Error> {\n"},{"Del":" debug!(\"======== prev\");\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":277,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":20415},"to":{"change":3,"start":8286,"end":8347},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":13403},"to":{"change":3,"start":8286,"end":8347},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8347},"to":{"change":3,"start":20416,"end":20471},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":20471},"to":{"change":3,"start":8406,"end":8421},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":8406},"to":{"change":3,"start":8406,"end":8421},"introduced_by":3}],"inode":{"change":3,"pos":63682}}},"contents":[{"Del":" debug!(\n \"prev = {:?} {:?} {:?}\",\n"},{"Del":" self.len, current.page, current.cursor\n"},{"Del":" );\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":278,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":15844},"to":{"change":3,"start":581,"end":614},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":13473},"to":{"change":3,"start":581,"end":614},"introduced_by":3}],"inode":{"change":3,"pos":63682}}},"contents":[{"Del":" debug!(\"empty\");\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":290,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":8537},"to":{"change":3,"start":615,"end":668},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":13959},"to":{"change":3,"start":615,"end":668},"introduced_by":3}],"inode":{"change":3,"pos":63682}}},"contents":[{"Del":" debug!(\"current = {:?} {:?}\", k, v);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":300,"ins":{"up_context":[{"change":3,"pos":70731}],"down_context":[{"change":3,"pos":20739}],"flag":"BLOCK","start":41381,"end":41513,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":70731},"to":{"change":3,"start":8538,"end":8579},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" unsafe {"},{"Add":" return Ok(Some((core::mem::transmute(k), core::mem::transmute(v))));"},{"Add":" }"}],"del_contents":[{"Del":" return Ok(Some((k, v)));\n"}]}},{"Edit":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":304,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":20776},"to":{"change":3,"start":669,"end":700},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":14413},"to":{"change":3,"start":669,"end":700},"introduced_by":3}],"inode":{"change":3,"pos":63682}}},"contents":[{"Del":" debug!(\"pop\");\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":331,"ins":{"up_context":[{"change":3,"pos":3598}],"down_context":[{"change":3,"pos":8864}],"flag":"BLOCK","start":41514,"end":41587,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3598},"to":{"change":3,"start":3598,"end":3628},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" if let Some((k, v)) = origin {"},{"Add":" cursor.set(txn, k, v)?;"},{"Add":" }"}],"del_contents":[{"Del":" cursor.set(txn, origin)?;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":63682},"path":"sanakirja-core/src/btree/cursor.rs","line":369,"ins":{"up_context":[{"change":3,"pos":4441}],"down_context":[{"change":3,"pos":9376}],"flag":"BLOCK","start":41588,"end":41661,"inode":{"change":3,"pos":63682}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4441},"to":{"change":3,"start":4441,"end":4471},"introduced_by":3}],"inode":{"change":3,"pos":63682}},"ins_contents":[{"Add":" if let Some((k, v)) = origin {"},{"Add":" cursor.set(txn, k, v)?;"},{"Add":" }"}],"del_contents":[{"Del":" cursor.set(txn, origin)?;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":11},"path":"sanakirja/src/tests.rs","line":58,"ins":{"up_context":[{"change":3,"pos":14758}],"down_context":[{"change":3,"pos":2551}],"flag":"BLOCK","start":41662,"end":41737,"inode":{"change":3,"pos":11}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":14758},"to":{"change":3,"start":2441,"end":2551},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2441},"to":{"change":3,"start":2441,"end":2551},"introduced_by":3}],"inode":{"change":3,"pos":11}},"ins_contents":[{"Add":" let (k, v) = curs.set(&txn, &((i0 * i0) % m), None).unwrap().unwrap();"}],"del_contents":[{"Del":" let (k, v) = curs\n .set(&txn, Some((&((i0 * i0) % m), None)))\n .unwrap()\n .unwrap();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":11},"path":"sanakirja/src/tests.rs","line":64,"ins":{"up_context":[{"change":3,"pos":25750}],"down_context":[{"change":3,"pos":2855}],"flag":"BLOCK","start":41738,"end":41817,"inode":{"change":3,"pos":11}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":25750},"to":{"change":3,"start":2741,"end":2855},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2741},"to":{"change":3,"start":2741,"end":2855},"introduced_by":3}],"inode":{"change":3,"pos":11}},"ins_contents":[{"Add":" let (k, v) = curs.set(&txn, &((i0 * i0) % m), Some(&a)).unwrap().unwrap();"}],"del_contents":[{"Del":" let (k, v) = curs\n .set(&txn, Some((&((i0 * i0) % m), Some(&a))))\n .unwrap()\n .unwrap();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":11},"path":"sanakirja/src/tests.rs","line":252,"ins":{"up_context":[{"change":3,"pos":15153}],"down_context":[{"change":3,"pos":6953}],"flag":"BLOCK","start":41818,"end":41863,"inode":{"change":3,"pos":11}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":15153},"to":{"change":3,"start":26151,"end":26204},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":6899},"to":{"change":3,"start":26151,"end":26204},"introduced_by":3}],"inode":{"change":3,"pos":11}},"ins_contents":[{"Add":" curs.set(&txn, &500, Some(&a)).unwrap();"}],"del_contents":[{"Del":" curs.set(&txn, Some((&500, Some(&a)))).unwrap();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":11},"path":"sanakirja/src/tests.rs","line":870,"ins":{"up_context":[{"change":3,"pos":10602}],"down_context":[{"change":3,"pos":10678}],"flag":"BLOCK","start":41864,"end":41932,"inode":{"change":3,"pos":11}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":10602},"to":{"change":3,"start":10602,"end":10678},"introduced_by":3}],"inode":{"change":3,"pos":11}},"ins_contents":[{"Add":" let (&k, v) = cursor.set(&txn, &i, None).unwrap().unwrap();"}],"del_contents":[{"Del":" let (&k, v) = cursor.set(&txn, Some((&i, None))).unwrap().unwrap();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":11},"path":"sanakirja/src/tests.rs","line":881,"ins":{"up_context":[{"change":3,"pos":11005}],"down_context":[{"change":3,"pos":11081}],"flag":"BLOCK","start":41933,"end":42001,"inode":{"change":3,"pos":11}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":11005},"to":{"change":3,"start":11005,"end":11081},"introduced_by":3}],"inode":{"change":3,"pos":11}},"ins_contents":[{"Add":" let (&k, v) = cursor.set(&txn, &i, None).unwrap().unwrap();"}],"del_contents":[{"Del":" let (&k, v) = cursor.set(&txn, Some((&i, None))).unwrap().unwrap();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":80166},"path":"sanakirja/src/environment/muttxn.rs","line":231,"ins":{"up_context":[{"change":3,"pos":86898}],"down_context":[{"change":3,"pos":86955}],"flag":"BLOCK","start":42002,"end":42064,"inode":{"change":3,"pos":80166}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":86898},"to":{"change":3,"start":86898,"end":86955},"introduced_by":3}],"inode":{"change":3,"pos":80166}},"ins_contents":[{"Add":" btree::del::del_at_cursor(self, &mut db, &mut curs)?;"}],"del_contents":[{"Del":" btree::del_at_cursor(self, &mut db, &mut curs)?;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":80166},"path":"sanakirja/src/environment/muttxn.rs","line":275,"ins":{"up_context":[{"change":3,"pos":16374}],"down_context":[{"change":3,"pos":38419}],"flag":"BLOCK","start":42065,"end":42106,"inode":{"change":3,"pos":80166}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":16374},"to":{"change":3,"start":88609,"end":88658},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":88609},"to":{"change":3,"start":88609,"end":88658},"introduced_by":3}],"inode":{"change":3,"pos":80166}},"ins_contents":[{"Add":" curs.set(self, &off, None)?;"}],"del_contents":[{"Del":" curs.set(self, Some((&off, None)))?;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":80166},"path":"sanakirja/src/environment/muttxn.rs","line":308,"ins":{"up_context":[{"change":3,"pos":16443}],"down_context":[{"change":3,"pos":38930}],"flag":"BLOCK","start":42107,"end":42148,"inode":{"change":3,"pos":80166}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":16443},"to":{"change":3,"start":38881,"end":38930},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":89390},"to":{"change":3,"start":38881,"end":38930},"introduced_by":3}],"inode":{"change":3,"pos":80166}},"ins_contents":[{"Add":" curs.set(self, &off, None)?;"}],"del_contents":[{"Del":" curs.set(self, Some((&off, None)))?;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":80166},"path":"sanakirja/src/environment/muttxn.rs","line":343,"ins":{"up_context":[{"change":3,"pos":16512}],"down_context":[{"change":3,"pos":39474}],"flag":"BLOCK","start":42149,"end":42223,"inode":{"change":3,"pos":80166}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":16512},"to":{"change":3,"start":39392,"end":39474},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":90231},"to":{"change":3,"start":39392,"end":39474},"introduced_by":3}],"inode":{"change":3,"pos":80166}},"ins_contents":[{"Add":" let rc = if let Some((rc, _)) = curs.set(self, &off, None)? {"}],"del_contents":[{"Del":" let rc = if let Some((rc, _)) = curs.set(self, Some((&off, None)))? {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":80166},"path":"sanakirja/src/environment/muttxn.rs","line":353,"ins":{"up_context":[{"change":3,"pos":39628}],"down_context":[{"change":3,"pos":90653}],"flag":"BLOCK","start":42224,"end":42295,"inode":{"change":3,"pos":80166}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":39628},"to":{"change":3,"start":39628,"end":39694},"introduced_by":3}],"inode":{"change":3,"pos":80166}},"ins_contents":[{"Add":" btree::del::del_at_cursor(self, &mut rc_, &mut curs)?;"}],"del_contents":[{"Del":" btree::del_at_cursor(self, &mut rc_, &mut curs)?;\n"}]}}],"owner":"pijul","repo":"sanakirja","token":"uYO67XzadZLqBxfbTL5Ec1WgrzebMXZN3jiQB77/OGU=","login":null}

…

Dependencies

Change contents