jena-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From a...@apache.org
Subject [41/50] [abbrv] jena git commit: JENA-1396: Merge //github/afs/mantis as subdirectory jena-db/
Date Thu, 28 Sep 2017 11:08:57 GMT
http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/BPlusTreeRewriter.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/BPlusTreeRewriter.java
index 0000000,0000000..16a535b
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/BPlusTreeRewriter.java
@@@ -1,0 -1,0 +1,361 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree.rewriter ;
++
++import static org.seaborne.dboe.trans.bplustree.rewriter.BPlusTreeRewriterUtils.divider ;
++import static org.seaborne.dboe.trans.bplustree.rewriter.BPlusTreeRewriterUtils.printIndexBlocks ;
++import static org.seaborne.dboe.trans.bplustree.rewriter.BPlusTreeRewriterUtils.summarizeDataBlocks ;
++
++import java.util.Iterator ;
++import java.util.List ;
++
++import org.apache.jena.atlas.iterator.Iter ;
++import org.apache.jena.atlas.iterator.IteratorWithBuffer ;
++import org.apache.jena.atlas.lib.Pair ;
++import org.seaborne.dboe.base.block.BlockMgr ;
++import org.seaborne.dboe.base.buffer.PtrBuffer ;
++import org.seaborne.dboe.base.buffer.RecordBuffer ;
++import org.seaborne.dboe.base.file.BufferChannel ;
++import org.seaborne.dboe.base.record.Record ;
++import org.seaborne.dboe.base.record.RecordFactory ;
++import org.seaborne.dboe.base.recordbuffer.RecordBufferPage ;
++import org.seaborne.dboe.base.recordbuffer.RecordBufferPageMgr ;
++import org.seaborne.dboe.trans.bplustree.* ;
++import org.slf4j.Logger ;
++import org.slf4j.LoggerFactory ;
++
++public class BPlusTreeRewriter {
++    static private Logger log         = LoggerFactory.getLogger(BPlusTreeRewriter.class) ;
++
++    static boolean        rebalance   = true ;
++    static boolean        debug       = false ;
++    static boolean        materialize = debug ;
++
++    // Process:
++    // 1/ Take a stream of records and create leaves.
++    // Emit the RecordBufferPage (B+Tree leaves).
++    // 2/ Take a stream of RecordBufferPage and create the first level of
++    // branches.
++    // 3/ Take each branch level and create upper branches until root hit.
++    // 4/ Copy root block to root real location.
++
++    // --------------------------------
++
++    /**
++     * Given a stream of records and details of the B+Tree to build, go and
++     * build it.
++     * 
++     * @return A newly built BPlusTree
++     */
++    public static BPlusTree packIntoBPlusTree(Iterator<Record> iterRecords, BPlusTreeParams bptParams, RecordFactory recordFactory,
++                                              BufferChannel bptState, BlockMgr blkMgrNodes, BlockMgr blkMgrRecords) {
++        // **** Attach to storage.
++        // Small caches as we mostly work on a block then move on.
++        // Only read behind and look ahead actually do any work on an existing
++        // block.
++        // (check this by rerunning with different cache sizes).
++
++        if ( !iterRecords.hasNext() )
++            // No records. Just return a B+Tree.
++            return BPlusTreeFactory.createNonTxn(bptParams, bptState, blkMgrNodes, blkMgrRecords) ;
++
++        
++        // Initial B+tree needed to carry parameters around - not legal at this point.
++        BPlusTree bpt2 = BPT.createRootOnlyBPTree(bptParams, bptState, blkMgrNodes, blkMgrRecords) ;
++        // Get the root node.
++        // We will use this slot later and write in the correct root.
++        // The root has to be block zero currently.
++        BPTreeNode root = bpt2.getNodeManager().getWrite(BPlusTreeParams.RootId, BPlusTreeParams.RootParent) ;
++        // ******** Pack data blocks.
++        Iterator<Pair<Integer, Record>> iter = writePackedDataBlocks(iterRecords, bpt2) ;
++        
++        // ******** Index layer
++        // Loop until one block only.
++        // Never zero blocks.
++        // Output is a single pair pointing to the root - but the root is in the
++        // wrong place.
++
++        boolean leafLayer = true ;
++        while (true) {
++            iter = genTreeLevel(iter, bpt2, leafLayer) ;
++            // Advances iter.
++            IteratorWithBuffer<Pair<Integer, Record>> iter2 = new IteratorWithBuffer<>(iter, 2) ;
++            boolean singleBlock = (iter2.peek(1) == null) ;
++            // Having peeked ahead, use the real stream.
++            iter = iter2 ;
++            if ( singleBlock )
++                break ;
++            leafLayer = false ;
++        }
++
++        // ******** Put root in right place.
++        Pair<Integer, Record> pair = iter.next() ;
++        if ( iter.hasNext() ) {
++            log.error("**** Building index layers didn't result in a single block") ;
++            return null ;
++        }
++        fixupRoot(root, pair, bpt2) ;
++        // ****** Finish the tree.
++        //bpt2.getStateManager().
++        blkMgrNodes.sync() ;
++        blkMgrRecords.sync() ;
++        return bpt2 ;
++    }
++
++    // **** data block phase
++
++    /** Pack record blocks into linked RecordBufferPages */
++    private static Iterator<Pair<Integer, Record>> writePackedDataBlocks(Iterator<Record> records, final BPlusTree bpt) {
++        if ( debug ) {
++            divider() ;
++            System.out.println("---- Data level") ;
++        }
++
++        final RecordBufferPageMgr mgr = bpt.getRecordsMgr().getRecordBufferPageMgr() ;
++        Iterator<RecordBufferPage> iter = new RecordBufferPageLinker(new RecordBufferPagePacker(records, mgr)) ;
++
++        // Write and convert to split pairs.
++        Iterator<Pair<Integer, Record>> iter2 = Iter.map(iter, rbp-> {
++            mgr.put(rbp) ;
++            Record r = rbp.getRecordBuffer().getHigh() ;
++            r = bpt.getRecordFactory().createKeyOnly(r) ;
++            return new Pair<>(rbp.getId(), r) ;
++        }) ;
++
++        if ( debug ) {
++            if ( rebalance )
++                System.out.println("Before rebalance (data)") ;
++            iter2 = summarizeDataBlocks(iter2, bpt.getRecordsMgr().getRecordBufferPageMgr()) ;
++            // iter2 = printDataBlocks(iter2,
++            // bpt.getRecordsMgr().getRecordBufferPageMgr()) ;
++        }
++
++        if ( rebalance )
++            iter2 = new RebalenceDataEnd(iter2, bpt) ;
++
++        // Testing - materialize - debug wil have done this
++        if ( materialize && !debug )
++            iter2 = Iter.toList(iter2).iterator() ;
++
++        if ( debug && rebalance ) {
++            System.out.println("After rebalance (data)") ;
++            iter2 = summarizeDataBlocks(iter2, bpt.getRecordsMgr().getRecordBufferPageMgr()) ;
++            // iter2 = printDataBlocks(iter2,
++            // bpt.getRecordsMgr().getRecordBufferPageMgr()) ;
++        }
++        return iter2 ;
++    }
++
++    private static class RebalenceDataEnd extends RebalenceBase {
++        private RecordBufferPageMgr mgr ;
++        private BPlusTree           bpt ;
++
++        public RebalenceDataEnd(Iterator<Pair<Integer, Record>> iter, BPlusTree bpt) {
++            super(iter) ;
++            this.bpt = bpt ;
++        }
++
++        @Override
++        protected Record rebalance(int id1, Record r1, int id2, Record r2) {
++            RecordBufferPageMgr mgr = bpt.getRecordsMgr().getRecordBufferPageMgr() ;
++            RecordBufferPage page1 = mgr.getWrite(id1) ;
++            RecordBufferPage page2 = mgr.getWrite(id2) ;
++
++            // Wrong calculatation.
++            for ( int i = page2.getCount() ; i < page1.getMaxSize() / 2 ; i++ ) {
++                // shiftOneup(node1, node2) ;
++                Record r = page1.getRecordBuffer().getHigh() ;
++                page1.getRecordBuffer().removeTop() ;
++
++                page2.getRecordBuffer().add(0, r) ;
++            }
++
++            mgr.put(page1) ;
++            mgr.put(page2) ;
++
++            Record splitPoint = page1.getRecordBuffer().getHigh() ;
++            splitPoint = bpt.getRecordFactory().createKeyOnly(splitPoint) ;
++            // Record splitPoint = node1.maxRecord() ;
++            return splitPoint ;
++        }
++    }
++
++    // ---------------------------------------------------------------------------------------------
++
++    // **** tree block phase
++
++    /*
++     * Status: need to address the parent issue - how to set the parent as we
++     * work up the BPT. One way is to work in memory and assume that there is
++     * enough room for the B+Tree nodes (not the record nodes).
++     * 
++     * Another way is to rely on the caching and two-pass each new layer to fix
++     * up parents.
++     * 
++     * 3rd way - parents aren't actually used in B+Trees. Set the BPT code to
++     * ignore parent of -2. Always set the new nodes to -2 for a rebuild.
++     */
++
++    // Idea a layer processor for BPT nodes has a sink that is the parent.
++    // Need to rebal the last two blocks of a level.
++    // Same for data blocks.
++
++    // ---- Block stream to BTreeNodeStream.
++
++    private static Iterator<Pair<Integer, Record>> genTreeLevel(Iterator<Pair<Integer, Record>> iter, BPlusTree bpt, boolean leafLayer) {
++        if ( debug ) {
++            divider() ;
++            System.out.println("---- Index level") ;
++            List<Pair<Integer, Record>> x = Iter.toList(iter) ;
++            System.out.println(x) ;
++            iter = x.iterator() ;
++        }
++
++        Iterator<Pair<Integer, Record>> iter2 = new BPTreeNodeBuilder(iter, bpt.getNodeManager(), leafLayer, bpt.getRecordFactory()) ;
++
++        if ( debug ) {
++            if ( rebalance )
++                System.out.println("Before rebalance (index)") ;
++            // iter2 = summarizeIndexBlocks(iter2, bpt.getNodeManager()) ;
++            iter2 = printIndexBlocks(iter2, bpt.getNodeManager()) ;
++        }
++
++        if ( rebalance )
++            iter2 = new RebalenceIndexEnd(iter2, bpt, leafLayer) ;
++
++        if ( materialize && !debug )
++            iter2 = Iter.toList(iter2).iterator() ;
++
++        if ( debug && rebalance ) {
++            System.out.println("After rebalance (index)") ;
++            // iter2 = summarizeIndexBlocks(iter2, bpt.getNodeManager()) ;
++            iter2 = printIndexBlocks(iter2, bpt.getNodeManager()) ;
++        }
++        return iter2 ;
++    }
++
++    private abstract static class RebalenceBase extends IteratorWithBuffer<Pair<Integer, Record>> {
++        protected RebalenceBase(Iterator<Pair<Integer, Record>> iter) {
++            super(iter, 2) ;
++        }
++
++        @Override
++        protected final void endReachedInner() {
++            Pair<Integer, Record> pair1 = peek(0) ;
++            Pair<Integer, Record> pair2 = peek(1) ;
++            if ( pair1 == null || pair2 == null )
++                // Insufficient blocks to repack.
++                return ;
++
++            if ( debug )
++                System.out.printf("Rebalance: %s %s\n", pair1, pair2) ;
++            Record newSplitPoint = rebalance(pair1.car(), pair1.cdr(), pair2.car(), pair2.cdr()) ;
++            // Needed??
++            if ( newSplitPoint != null ) {
++                if ( debug )
++                    System.out.println("Reset split point: " + pair1.cdr() + " => " + newSplitPoint) ;
++                pair1 = new Pair<>(pair1.car(), newSplitPoint) ;
++                if ( debug )
++                    System.out.printf("   %s %s\n", pair1, pair2) ;
++                set(0, pair1) ;
++            }
++        }
++
++        protected abstract Record rebalance(int id1, Record r1, int id2, Record r2) ;
++    }
++
++    private static class RebalenceIndexEnd extends RebalenceBase {
++        private BPlusTree bpt ;
++
++        public RebalenceIndexEnd(Iterator<Pair<Integer, Record>> iter, BPlusTree bpt, boolean leafLayer) {
++            super(iter) ;
++            this.bpt = bpt ;
++        }
++
++        @Override
++        protected Record rebalance(int id1, Record r1, int id2, Record r2) {
++            BPTreeNodeMgr mgr = bpt.getNodeManager() ;
++            BPTreeNode node1 = mgr.getWrite(id1) ;
++            BPTreeNode node2 = mgr.getWrite(id2) ;
++
++            // rebalence
++            // ** Need rebalance of data leaf layer.
++            int count = node2.getCount() ;
++            if ( count >= bpt.getParams().getMinRec() )
++                return null ;
++
++            Record splitPoint = r1 ;
++
++            // Shift up all in one go and use .set.
++            // Convert to block move ; should be code in BPTreeNode to do this
++            // (insert).
++            for ( int i = count ; i < bpt.getParams().getMinRec() ; i++ ) {
++
++                Record r = splitPoint ;
++
++                // shiftOneup(node1, node2) ;
++                int ptr = node1.getPtrBuffer().getHigh() ;
++                splitPoint = node1.getRecordBuffer().getHigh() ;
++
++                node1.getPtrBuffer().removeTop() ;
++                node1.getRecordBuffer().removeTop() ;
++                node1.setCount(node1.getCount() - 1) ;
++
++                node2.getPtrBuffer().add(0, ptr) ;
++                node2.getRecordBuffer().add(0, r) ;
++                node2.setCount(node2.getCount() + 1) ;
++
++                // Need high of moved substree.
++
++                if ( debug )
++                    System.out.printf("-- Shift up: %d %s\n", ptr, r) ;
++            }
++            mgr.put(node1) ;
++            mgr.put(node2) ;
++
++            return splitPoint ;
++        }
++    }
++
++    private static void fixupRoot(BPTreeNode root, Pair<Integer, Record> pair, BPlusTree bpt2) {
++        root.getPtrBuffer().clear() ;
++        root.getRecordBuffer().clear() ;
++
++        if ( BPlusTreeRewriter.debug ) {
++            divider() ;
++            System.out.printf("** Process root: %s\n", pair) ;
++        }
++
++        // Node or records?
++        // BPTreeNode => BPTree copy.
++        BPTreeNode node = bpt2.getNodeManager().getRead(pair.car(), BPlusTreeParams.RootParent) ;
++        copyBPTreeNode(node, root, bpt2) ;
++        bpt2.getNodeManager().release(node) ;
++        bpt2.getNodeManager().write(root);
++    }
++
++    private static void copyBPTreeNode(BPTreeNode nodeSrc, BPTreeNode nodeDst, BPlusTree bpt2) {
++        PtrBuffer pBuff = nodeSrc.getPtrBuffer() ;
++        pBuff.copy(0, nodeDst.getPtrBuffer(), 0, pBuff.getSize()) ;
++        RecordBuffer rBuff = nodeSrc.getRecordBuffer() ;
++        rBuff.copy(0, nodeDst.getRecordBuffer(), 0, rBuff.getSize()) ;
++        nodeDst.setCount(nodeSrc.getCount()) ;
++        nodeDst.setIsLeaf(nodeSrc.isLeaf()) ;
++        bpt2.getNodeManager().put(nodeDst) ;
++    }
++}

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/BPlusTreeRewriterUtils.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/BPlusTreeRewriterUtils.java
index 0000000,0000000..77cfdb2
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/BPlusTreeRewriterUtils.java
@@@ -1,0 -1,0 +1,104 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree.rewriter ;
++
++import java.util.Iterator ;
++import java.util.List ;
++
++import org.apache.jena.atlas.iterator.Iter ;
++import org.apache.jena.atlas.lib.Pair ;
++import org.seaborne.dboe.base.record.Record ;
++import org.seaborne.dboe.base.recordbuffer.RecordBufferPage ;
++import org.seaborne.dboe.base.recordbuffer.RecordBufferPageMgr ;
++import org.seaborne.dboe.trans.bplustree.BPTreeNode ;
++import org.seaborne.dboe.trans.bplustree.BPTreeNodeMgr ;
++import org.seaborne.dboe.trans.bplustree.BPlusTreeParams ;
++
++class BPlusTreeRewriterUtils {
++    static String divider     = "----------------------------------------" ;
++    static String nextDivider = null ;
++
++    static Iterator<Pair<Integer, Record>> summarizeDataBlocks(Iterator<Pair<Integer, Record>> iter, RecordBufferPageMgr recordPageMgr) {
++        divider() ;
++        List<Pair<Integer, Record>> pairs = Iter.toList(iter) ;
++        System.out.println("summarizeDataBlocks: " + pairs) ;
++        for ( Pair<Integer, Record> pair : pairs ) {
++            RecordBufferPage rbp = recordPageMgr.getRead(pair.car()) ;
++            System.out.printf("%s -- RecordBufferPage[id=%d,link=%d] (%d) -> [%s]\n", pair, rbp.getId(), rbp.getLink(), rbp.getCount(),
++                              rbp.getRecordBuffer().getHigh()) ;
++            recordPageMgr.release(rbp) ;
++        }
++        return pairs.iterator() ;
++    }
++
++    static Iterator<Pair<Integer, Record>> summarizeIndexBlocks(Iterator<Pair<Integer, Record>> iter2, BPTreeNodeMgr bptNodeMgr) {
++        divider() ;
++        List<Pair<Integer, Record>> pairs = Iter.toList(iter2) ;
++        for ( Pair<Integer, Record> pair : pairs ) {
++            BPTreeNode bpNode = bptNodeMgr.getRead(pair.car(), BPlusTreeParams.RootParent) ;
++
++            String hr = "null" ;
++            if ( !bpNode.getRecordBuffer().isEmpty() )
++                hr = bpNode.getRecordBuffer().getHigh().toString() ;
++
++            System.out.printf("%s -- BPTreeNode: %d (%d) -> [%s]\n", pair, bpNode.getId(), bpNode.getCount(), hr) ;
++            bptNodeMgr.release(bpNode) ;
++        }
++        return pairs.iterator() ;
++    }
++
++    private static Iterator<Pair<Integer, Record>> printDataBlocks(Iterator<Pair<Integer, Record>> iter, RecordBufferPageMgr recordPageMgr) {
++        divider() ;
++        List<Pair<Integer, Record>> pairs = Iter.toList(iter) ;
++        System.out.printf(">>Packed data blocks\n") ;
++        for ( Pair<Integer, Record> pair : pairs ) {
++            System.out.printf("  %s\n", pair) ;
++            RecordBufferPage rbp = recordPageMgr.getRead(pair.car()) ;
++            // System.out.printf("RecordBufferPage[id=%d,link=%d] %d\n",
++            // rbp.getId(), rbp.getLink(), rbp.getCount() ) ;
++            System.out.println(rbp) ;
++            recordPageMgr.release(rbp) ;
++        }
++        System.out.printf("<<Packed data blocks\n") ;
++        System.out.printf("Blocks: %d\n", pairs.size()) ;
++        return pairs.iterator() ;
++    }
++
++    static Iterator<Pair<Integer, Record>> printIndexBlocks(Iterator<Pair<Integer, Record>> iter2, BPTreeNodeMgr bptNodeMgr) {
++        divider() ;
++        List<Pair<Integer, Record>> pairs = Iter.toList(iter2) ;
++        System.out.printf(">>Packed index blocks\n") ;
++        for ( Pair<Integer, Record> pair : pairs ) {
++            System.out.printf("  %s\n", pair) ;
++            BPTreeNode bpNode = bptNodeMgr.getRead(pair.car(), BPlusTreeParams.RootParent) ;
++            bpNode.setIsLeaf(true) ;
++            System.out.printf("BPTreeNode: %d\n", bpNode.getId()) ;
++            System.out.println(bpNode) ;
++            bptNodeMgr.release(bpNode) ;
++        }
++        System.out.printf("<<Packed index blocks\n") ;
++        return pairs.iterator() ;
++    }
++
++    static void divider() {
++        if ( nextDivider != null )
++            System.out.println(nextDivider) ;
++        nextDivider = divider ;
++    }
++
++}

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/RecordBufferPageLinker.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/RecordBufferPageLinker.java
index 0000000,0000000..42c2b9c
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/RecordBufferPageLinker.java
@@@ -1,0 -1,0 +1,81 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree.rewriter ;
++
++import java.util.Iterator ;
++import java.util.NoSuchElementException ;
++
++import org.apache.jena.atlas.iterator.PeekIterator ;
++import org.seaborne.dboe.base.recordbuffer.RecordBufferPage ;
++
++/**
++ * From a stream of RecordBufferPage, manage the link fields. That is, be a one
++ * slot delay so that the "link" field can point to the next page. Be careful
++ * about the last block.
++ *
++ */
++class RecordBufferPageLinker implements Iterator<RecordBufferPage> {
++    PeekIterator<RecordBufferPage> peekIter ;
++
++    RecordBufferPage               slot = null ;
++
++    RecordBufferPageLinker(Iterator<RecordBufferPage> iter) {
++        if ( !iter.hasNext() ) {
++            peekIter = null ;
++            return ;
++        }
++
++        peekIter = new PeekIterator<>(iter) ;
++    }
++
++    @Override
++    public boolean hasNext() {
++        if ( slot != null )
++            return true ;
++
++        if ( peekIter == null )
++            return false ;
++
++        if ( !peekIter.hasNext() ) {
++            peekIter = null ;
++            return false ;
++        }
++
++        slot = peekIter.next() ;
++        RecordBufferPage nextSlot = peekIter.peek() ;
++        // If null, no slot ahead so no linkage field to set.
++        if ( nextSlot != null )
++            // Set the slot to the id of the next one
++            slot.setLink(nextSlot.getId()) ;
++        return true ;
++    }
++
++    @Override
++    public RecordBufferPage next() {
++        if ( !hasNext() )
++            throw new NoSuchElementException() ;
++        RecordBufferPage rbp = slot ;
++        slot = null ;
++        return rbp ;
++    }
++
++    @Override
++    public void remove() {
++        throw new UnsupportedOperationException() ;
++    }
++}

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/RecordBufferPagePacker.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/RecordBufferPagePacker.java
index 0000000,0000000..bb0485a
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/rewriter/RecordBufferPagePacker.java
@@@ -1,0 -1,0 +1,90 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree.rewriter ;
++
++import java.util.Iterator ;
++import java.util.NoSuchElementException ;
++
++import org.seaborne.dboe.base.buffer.RecordBuffer ;
++import org.seaborne.dboe.base.record.Record ;
++import org.seaborne.dboe.base.recordbuffer.RecordBufferPage ;
++import org.seaborne.dboe.base.recordbuffer.RecordBufferPageMgr ;
++
++/**
++ * Iterate over a stream of records, packing them into RecordBufferPage -- the
++ * leaf of a B+Tree This class does not write the blocks back to the block
++ * manager. This class does allocate block ids and blocks.
++ * 
++ * @see RecordBufferPageLinker
++ */
++
++class RecordBufferPagePacker implements Iterator<RecordBufferPage> {
++    Iterator<Record>    records          = null ;
++    RecordBufferPage    recordBufferPage = null ;
++    RecordBufferPageMgr rbMgr            = null ;
++
++    RecordBufferPagePacker(Iterator<Record> records, RecordBufferPageMgr rbMgr) {
++        this.records = records ;
++        this.rbMgr = rbMgr ;
++    }
++
++    @Override
++    public boolean hasNext() {
++        if ( recordBufferPage == null ) {
++            if ( records == null )
++                return false ;
++
++            if ( !records.hasNext() ) {
++                records = null ;
++                return false ;
++            }
++            // At least one record to be processed.
++            // No pending RecordBufferPage
++            // ==> There will be a RecordBufferPage to yield.
++
++            // int id = rbMgr.allocateId() ;
++            // //System.out.println("Allocate : "+id) ;
++            recordBufferPage = rbMgr.create() ;
++
++            RecordBuffer rb = recordBufferPage.getRecordBuffer() ;
++            while (!rb.isFull() && records.hasNext()) {
++                Record r = records.next() ;
++                rb.add(r) ;
++            }
++            if ( !records.hasNext() )
++                records = null ;
++            return true ;
++        }
++        return true ;
++
++    }
++
++    @Override
++    public RecordBufferPage next() {
++        if ( !hasNext() )
++            throw new NoSuchElementException() ;
++        RecordBufferPage rbp = recordBufferPage ;
++        recordBufferPage = null ;
++        return rbp ;
++    }
++
++    @Override
++    public void remove() {
++        throw new UnsupportedOperationException() ;
++    }
++}

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/data/TransBinaryDataFile.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/data/TransBinaryDataFile.java
index 0000000,0000000..569db33
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/data/TransBinaryDataFile.java
@@@ -1,0 -1,0 +1,237 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.data;
++
++import java.nio.ByteBuffer ;
++import java.util.concurrent.atomic.AtomicLong ;
++
++import org.apache.jena.atlas.RuntimeIOException ;
++import org.apache.jena.atlas.io.IO ;
++import org.apache.jena.query.ReadWrite ;
++import org.seaborne.dboe.base.file.BinaryDataFile ;
++import org.seaborne.dboe.base.file.BufferChannel ;
++import org.seaborne.dboe.transaction.txn.* ;
++
++/** Transactional {@link BinaryDataFile}.
++ *  An binary file that is append-only and allows only one writer at a time.
++ *  All readers see the file up to the last commit point at the time 
++ *  they started.  The sole writer sees more of the file.
++ */
++
++public class TransBinaryDataFile extends TransactionalComponentLifecycle<TransBinaryDataFile.TxnBinFile>
++    implements BinaryDataFile {
++
++    /*
++     * The file is written to as we go along so abort requires some action. We
++     * can't recover from just the file, without any redo or undo recovery
++     * action.
++     */
++    
++    private final FileState stateMgr ;
++
++    // The current committed position and the limit as seen by readers.
++    // This is also the abort point.
++    private final AtomicLong committedLength ;
++    
++    // The per thread runtime state
++    static class TxnBinFile {
++        final long length ; 
++
++        TxnBinFile(long length) {
++            this.length = length ;
++        }
++    }
++
++    // Prepare record
++    static class FileState extends StateMgrData {
++        FileState(BufferChannel bufferChannel, long length, long position) {
++            super(bufferChannel, length, position) ;
++        }
++        private static int idxLength = 0 ; 
++        long length()               { return get(idxLength) ; }
++        void length(long len)       { set(idxLength, len) ; } 
++    }
++
++    private final BinaryDataFile binFile ;
++    
++    /** Create a transactional BinaryDataFile over a base implementation.
++     *  The base file must provide thread-safe operation.   
++     */
++    public TransBinaryDataFile(BinaryDataFile binFile, ComponentId cid, BufferChannel bufferChannel) {
++        super(cid) ;
++        stateMgr = new FileState(bufferChannel, 0L, 0L) ;
++        this.binFile = binFile ;
++        if ( ! binFile.isOpen() )
++            binFile.open();
++        // Internal state may be updated by recovery. Start by
++        // setting to the "clean start" settings.
++        committedLength = new AtomicLong(binFile.length()) ;
++    }
++    
++    private boolean recoveryAction = false ; 
++
++    @Override
++    public void startRecovery() {
++        recoveryAction = false ;
++    }
++    
++    @Override
++    public void recover(ByteBuffer ref) {
++        stateMgr.setState(ref);
++        committedLength.set(stateMgr.length()) ;
++        recoveryAction = true ;
++    }
++
++    @Override
++    public void finishRecovery() {
++        if ( recoveryAction ) {
++            long length = committedLength.get() ;
++            binFile.truncate(length) ;
++            binFile.sync();
++            committedLength.set(length) ; 
++        }
++    }
++    
++    @Override
++    public void cleanStart() { }
++
++    @Override
++    protected TxnBinFile _begin(ReadWrite readWrite, TxnId txnId) {
++        // Atomic read across the two because it's called from within 
++        // TransactionCoordinator.begin$ where there is a lock.
++        return createState() ;
++    }
++    
++    private TxnBinFile createState() {
++        long xLength = committedLength.get() ;
++        return new TxnBinFile(xLength) ;
++    }
++
++    @Override
++    protected TxnBinFile _promote(TxnId txnId, TxnBinFile state) {
++        return createState() ;
++    }
++
++    @Override
++    protected ByteBuffer _commitPrepare(TxnId txnId, TxnBinFile state) {
++        // Force to disk but do not set the on disk state to record that.
++        binFile.sync();
++        stateMgr.length(binFile.length()) ;
++        return stateMgr.getState() ;
++    }
++
++    @Override
++    protected void _commit(TxnId txnId, TxnBinFile state) {
++        if ( isWriteTxn() ) {
++            // Force to disk happens in _commitPrepare
++            stateMgr.writeState();
++            // Move visible commit point forward (not strictly necessary - transaction is ending. 
++            committedLength.set(binFile.length()) ;
++        }
++    }
++
++    @Override
++    protected void _commitEnd(TxnId txnId, TxnBinFile state) {
++    }
++
++    @Override
++    protected void _abort(TxnId txnId, TxnBinFile state) {
++        if ( isWriteTxn() ) {
++            binFile.truncate(committedLength.get()) ;
++            binFile.sync() ;
++        }
++    }
++
++    @Override
++    protected void _complete(TxnId txnId, TxnBinFile state) {}
++
++    @Override
++    protected void _shutdown() {}
++    
++    private void checkBoundsReader(long requestedPoint, TxnBinFile state) { }
++    
++    @Override
++    public void open() {
++        if ( ! binFile.isOpen() )
++            binFile.open();
++    }
++
++    @Override
++    public boolean isOpen() {
++        return binFile.isOpen() ;
++    }
++
++    @Override
++    public int read(long posn, byte[] b, int start, int length) {
++        checkTxn();
++        if ( isReadTxn() )
++            checkRead(posn) ;
++        return binFile.read(posn, b, start, length) ;
++    }
++
++    private void checkRead(long posn) {
++        if ( posn > getDataState().length )
++            IO.exception("Out of bounds: (limit "+getDataState().length+")"+posn) ;
++    }
++
++    @Override
++    public long write(byte[] b, int start, int length) {
++        checkWriteTxn() ;
++        return binFile.write(b, start, length);
++    }
++
++    /** 
++     * Truncate only supported for an abort - this transactional version of
++     * BinaryDataFile will not truncate to earlier than the commited length.
++     */
++    @Override
++    public void truncate(long size) {
++        checkWriteTxn();
++        TxnBinFile state = getDataState() ;
++        if ( size < state.length )
++            throw new RuntimeIOException("truncate("+size+") to smaller than commited length "+state.length) ;
++        binFile.truncate(size) ;
++    }
++
++    @Override
++    public void sync() {
++        // No-op in transactional mode.
++        checkWriteTxn();
++    }
++
++    @Override
++    public void close() {
++        binFile.close() ;
++    }
++
++    @Override
++    public long length() {
++        super.checkTxn();
++        if ( isReadTxn() )
++            // Reader view.
++            return getDataState().length ;
++        return binFile.length() ;
++    }
++    
++    @Override
++    public boolean isEmpty() {
++        super.checkTxn();
++        return binFile.isEmpty() ;
++    }    
++}
++

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/data/TransBlob.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/data/TransBlob.java
index 0000000,0000000..a2dfbf3
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/main/java/org/seaborne/dboe/trans/data/TransBlob.java
@@@ -1,0 -1,0 +1,209 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.data;
++
++import java.nio.ByteBuffer ;
++import java.util.concurrent.atomic.AtomicReference ;
++
++import org.apache.jena.atlas.RuntimeIOException ;
++import org.apache.jena.atlas.lib.Bytes ;
++import org.apache.jena.query.ReadWrite ;
++import org.seaborne.dboe.base.file.BufferChannel ;
++import org.seaborne.dboe.transaction.txn.ComponentId ;
++import org.seaborne.dboe.transaction.txn.TransactionalComponentLifecycle ;
++import org.seaborne.dboe.transaction.txn.TxnId ;
++
++/** Manage a single binary (not too large) object.
++ * It is written and read from a file in one action, 
++ * so changes completely replace the original contents.
++ * The whole object is written to the journal during prepare.  
++ */
++public class TransBlob extends TransactionalComponentLifecycle<TransBlob.BlobState> {
++
++    // The last commited state.
++    // Immutable ByteBuffer.
++    private final AtomicReference<ByteBuffer> blobRef = new AtomicReference<>() ;
++    private final BufferChannel file ;
++
++    static class BlobState {
++        boolean hasChanged = false; 
++        ByteBuffer $txnBlob ;
++        
++        BlobState(ByteBuffer bb) {
++            setByteBuffer(bb) ;
++        }
++        void setByteBuffer(ByteBuffer bb) {
++            $txnBlob = bb ;
++            // Could compare - seems like added complexity.
++            hasChanged = true;
++        }
++
++        ByteBuffer getByteBuffer() { return $txnBlob ; } 
++    }
++    
++    public TransBlob(ComponentId cid, BufferChannel file) {
++        super(cid) ;
++        this.file = file ;
++        read() ;
++    }
++    
++    private void read() {
++        long x = file.size() ;
++        ByteBuffer blob = ByteBuffer.allocate((int)x) ;
++        int len = file.read(blob) ;
++        if ( len != x )
++            throw new RuntimeIOException("Short read: "+len+" of "+x) ;
++        blob.rewind() ;
++        blobRef.set(blob) ; 
++    }
++
++    private void write() {
++        ByteBuffer blob = blobRef.get();
++        blob.rewind() ;
++        int x = blob.remaining() ;
++        file.truncate(0);
++        int len = file.write(blob) ;
++        if ( len != x )
++            throw new RuntimeIOException("Short write: "+len+" of "+x) ;
++        file.sync(); 
++        blob.rewind() ;
++    }
++
++    /** Set the byte buffer.
++     * The byte buffer should not be accessed except by {@link #getBlob}.
++     * We avoid a copy in and copy out - we trust the caller.
++     * The byte buffer should be configured for read if used with {@link #getString}.
++     */
++    public void setBlob(ByteBuffer bb) {
++        checkWriteTxn();
++        getDataState().setByteBuffer(bb);
++    }
++    
++    public ByteBuffer getBlob() {
++        if ( isActiveTxn() )
++            return getDataState().getByteBuffer() ;
++        return blobRef.get() ;
++    }
++
++    /**  Set data from string - convenience operation */ 
++    public void setString(String dataStr) {
++        checkWriteTxn();
++        if ( dataStr == null ) {
++            setBlob(null);
++            return ;
++        }
++
++        // Attempt to reuse the write-transaction byte buffer
++        // We can't reuse if it's the blobRef (shared by other transactions)
++        // but if it's a new to this write transaction buffer we can reuse.
++        
++        int maxNeeded = dataStr.length()*4 ;
++        ByteBuffer bb = getDataState().getByteBuffer() ;
++        if ( bb == blobRef.get() )
++            bb = ByteBuffer.allocate(maxNeeded) ;
++        else if ( bb.capacity() >= maxNeeded )
++            bb.clear() ;
++        else
++            bb = ByteBuffer.allocate(maxNeeded) ;
++        Bytes.toByteBuffer(dataStr, bb) ;
++        bb.flip() ;
++        setBlob(bb);
++    }
++    
++    /**  Get data as string - convenience operation */ 
++    public String getString() {
++        ByteBuffer bb = getBlob() ;
++        if (bb == null )
++            return null ;
++        int x = bb.position() ;
++        String s = Bytes.fromByteBuffer(bb) ;
++        bb.position(x) ;
++        return s ;
++    }
++
++    private boolean recoveryChange = false ; 
++    @Override
++    public void startRecovery() {
++        recoveryChange = false ;
++    }
++
++    @Override
++    public void recover(ByteBuffer ref) {
++        blobRef.set(ref) ;
++        recoveryChange = true ;
++    }
++
++    @Override
++    public void finishRecovery() {
++        if ( recoveryChange )
++            write() ;
++    }
++
++    @Override
++    public void cleanStart() { }
++    
++    @Override
++    protected BlobState _begin(ReadWrite readWrite, TxnId txnId) {
++        return createState();
++    }
++
++    private BlobState createState() {
++        ByteBuffer blob = blobRef.get() ;
++        // Save reference to ByteBuffer into the transaction state.
++        return new BlobState(blob) ;
++    }
++    
++    @Override
++    protected BlobState _promote(TxnId txnId, BlobState state) {
++        // Our write state is the read state.
++        return createState();
++    }
++    
++    @Override
++    protected ByteBuffer _commitPrepare(TxnId txnId, BlobState state) {
++        if ( ! state.hasChanged )
++            return null;
++        return state.getByteBuffer() ;
++    }
++
++    @Override
++    protected void _commit(TxnId txnId, BlobState state) {
++        if ( ! state.hasChanged )
++            return;
++        // NB Change reference. 
++        blobRef.set(state.getByteBuffer()) ;
++        write() ;
++    }
++
++    @Override
++    protected void _commitEnd(TxnId txnId, BlobState state) {}
++
++    @Override
++    protected void _abort(TxnId txnId, BlobState state) {}
++
++    @Override
++    protected void _complete(TxnId txnId, BlobState state) {}
++
++    @Override
++    protected void _shutdown() {}
++    
++    @Override
++    public String toString()    { return getComponentId().label() ; } 
++
++}
++

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/TC_TransData.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/TC_TransData.java
index 0000000,0000000..9681f2c
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/TC_TransData.java
@@@ -1,0 -1,0 +1,33 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans;
++
++import org.junit.runner.RunWith ;
++import org.junit.runners.Suite ;
++import org.seaborne.dboe.trans.bplustree.TS_TxnBPTree ;
++import org.seaborne.dboe.trans.data.TS_TransData ;
++import org.seaborne.dboe.trans.recovery.TestRecovery ;
++
++@RunWith(Suite.class)
++@Suite.SuiteClasses( {
++    TS_TransData.class
++    , TS_TxnBPTree.class 
++    , TestRecovery.class
++})
++public class TC_TransData {}
++

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/BPlusTreeMaker.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/BPlusTreeMaker.java
index 0000000,0000000..5487178
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/BPlusTreeMaker.java
@@@ -1,0 -1,0 +1,55 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree;
++
++import org.seaborne.dboe.index.Index ;
++import org.seaborne.dboe.index.RangeIndex ;
++import org.seaborne.dboe.trans.bplustree.BPlusTree ;
++import org.seaborne.dboe.index.test.RangeIndexMaker ;
++import org.seaborne.dboe.test.RecordLib ;
++
++public class BPlusTreeMaker implements RangeIndexMaker
++{
++    private int order ;
++    private int recordOrder ;
++    private boolean trackers ;
++
++
++    public BPlusTreeMaker(int order, int recordOrder, boolean trackers)
++    { 
++        this.order = order ; 
++        this.recordOrder = recordOrder ;
++        this.trackers = trackers ;
++    }
++    
++    @Override
++    public Index makeIndex() { return makeRangeIndex() ; }
++
++    @Override
++    public RangeIndex makeRangeIndex()
++    {
++        BPlusTree bpTree = BPlusTreeFactory.makeMem(order, recordOrder, RecordLib.TestRecordLength, 0) ;
++        if ( trackers )
++            bpTree = BPlusTreeFactory.addTracking(bpTree) ;
++        return bpTree ;
++    }
++
++    @Override
++    public String getLabel() { return "B+Tree order = "+order ; } 
++
++}

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TS_TxnBPTree.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TS_TxnBPTree.java
index 0000000,0000000..e8016c8
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TS_TxnBPTree.java
@@@ -1,0 -1,0 +1,41 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree;
++
++import org.junit.runner.RunWith ;
++import org.junit.runners.Suite ;
++import org.seaborne.dboe.trans.bplustree.rewriter.TestBPlusTreeRewriterNonTxn ;
++
++@RunWith(Suite.class)
++@Suite.SuiteClasses( {
++    
++    // Non-transactional tests -- that is, algorithms and machinary. 
++    TestBPTreeRecordsNonTxn.class,
++    TestBPlusTreeIndexNonTxn.class,
++    TestBPlusTreeNonTxn.class,
++    TestBPTreeModes.class,
++    
++    // Transactional tests
++    TestBPlusTreeTxn.class,
++    
++    // Rewriter
++    TestBPlusTreeRewriterNonTxn.class
++} )
++
++public class TS_TxnBPTree
++{ }

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPTreeModes.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPTreeModes.java
index 0000000,0000000..71168cb
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPTreeModes.java
@@@ -1,0 -1,0 +1,77 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree;
++
++import java.util.Arrays ;
++import java.util.Collection ;
++
++import org.junit.After ;
++import org.junit.AfterClass ;
++import org.junit.Before ;
++import org.junit.BeforeClass ;
++import org.junit.runner.RunWith ;
++import org.junit.runners.Parameterized ;
++import org.junit.runners.Parameterized.Parameters ;
++
++/** Run the B+Tree algorithm tests but for each combination of explicit 
++ * write-in-place / always copy modes.  
++ */
++@RunWith(Parameterized.class)
++public class TestBPTreeModes extends TestBPlusTreeNonTxn
++{
++    @Parameters(name="Node dup={0}, Record dup={1}")
++    public static Collection<Object[]> data()
++    {
++        return Arrays.asList(new Object[][]{
++            {true, true},
++            {true, false},
++            {false, true},
++            {false, false}
++            }) ;
++    }
++    
++    public TestBPTreeModes(boolean nodeMode, boolean recordsMode) {
++        
++        BPT.promoteDuplicateNodes = nodeMode ;
++        BPT.promoteDuplicateRecords = recordsMode ;
++    }
++
++    boolean modeAtStartNodes ;
++    boolean modeAtStartRecords ;
++    
++    @BeforeClass public static void setupSuite() {
++        BPT.forcePromoteModes = true ;
++    }
++    
++    @AfterClass public static void resetSuite() {
++        BPT.forcePromoteModes = false ;
++    }
++    
++    @Before public void setModes() {
++        BPT.forcePromoteModes = true ;
++        modeAtStartNodes = BPT.promoteDuplicateNodes ;
++        modeAtStartRecords = BPT.promoteDuplicateRecords ;
++    }
++
++    
++    @After public void resetModes() {
++        BPT.promoteDuplicateNodes = modeAtStartNodes ;
++        BPT.promoteDuplicateRecords = modeAtStartRecords ;
++    }
++
++}

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPTreeRecordsNonTxn.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPTreeRecordsNonTxn.java
index 0000000,0000000..fad84f4
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPTreeRecordsNonTxn.java
@@@ -1,0 -1,0 +1,326 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree ;
++
++import org.junit.* ;
++import org.seaborne.dboe.base.block.BlockMgr ;
++import org.seaborne.dboe.base.block.BlockMgrFactory ;
++import org.seaborne.dboe.base.buffer.RecordBuffer ;
++import org.seaborne.dboe.base.record.Record ;
++import org.seaborne.dboe.base.record.RecordFactory ;
++import org.seaborne.dboe.base.recordbuffer.RecordBufferPage ;
++import org.seaborne.dboe.base.recordbuffer.RecordBufferPageMgr ;
++import org.seaborne.dboe.sys.SystemIndex ;
++import org.seaborne.dboe.test.RecordLib ;
++
++public class TestBPTreeRecordsNonTxn extends Assert {
++    static private boolean             oldNullOut ;
++
++    static private int                 blockSize ;
++    static private RecordFactory       recordFactory ;
++
++    static private int                 bufSizeRecord ;
++    static private BlockMgr            blkMgrRecords ;
++    static private RecordBufferPageMgr recordBufferPageMgr ;
++
++    @BeforeClass
++    public static void beforeClass() {
++        oldNullOut = SystemIndex.getNullOut() ;
++        SystemIndex.setNullOut(true) ;
++
++        blockSize = 4 * 8 ; // Which is 6 int records
++        recordFactory = new RecordFactory(4, 0) ;
++
++        bufSizeRecord = RecordBufferPage.calcRecordSize(recordFactory, blockSize) ;
++        blkMgrRecords = BlockMgrFactory.createMem("BPTreeRecords", blockSize) ;
++        recordBufferPageMgr = new RecordBufferPageMgr(recordFactory, blkMgrRecords) ;
++
++        BlockMgr blkMgrNodes = BlockMgrFactory.createMem("BPTreeNs", blockSize) ;
++        
++        // Copy on write.
++        BPT.forcePromoteModes = true ;
++        BPT.promoteDuplicateRecords = true ;
++    }
++
++    @AfterClass
++    public static void afterClass() {
++        SystemIndex.setNullOut(oldNullOut) ;
++        BPT.forcePromoteModes = false ;
++    }
++
++    @Before
++    public void before() {
++        blkMgrRecords.beginUpdate() ;
++    }
++
++    @After
++    public void after() {
++        blkMgrRecords.endUpdate() ;
++    }
++
++    @Test
++    public void bpt_records_1() {
++        BPTreeRecords bpr = make() ;
++        fill(bpr) ;
++        check(bpr) ;
++        bpr.release() ;
++    }
++
++    @Test
++    public void bpt_records_2() {
++        BPTreeRecords bpr = make() ;
++        fill(bpr) ;
++        int s = bpr.getCount() ;
++        assertTrue(bpr.isFull()) ;
++        BPTreePage z = bpr.split() ;
++        assertTrue(z instanceof BPTreeRecords) ;
++        assertEquals(s, z.getCount() + bpr.getCount()) ;
++        check(bpr) ;
++        check((BPTreeRecords)z) ;
++        bpr.release() ;
++        z.release() ;
++    }
++
++    @Test
++    public void bpt_records_3() {
++        BPTreeRecords bpr = make() ;
++        for ( int i = 0 ; bpr.getCount() < bpr.getMaxSize() ; i++ )
++            insert(bpr, (i + 0x20)) ;
++        check(bpr) ;
++        bpr.release() ;
++    }
++
++    @Test
++    public void bpt_records_4() {
++        BPTreeRecords bpr = make() ;
++        for ( int i = bpr.getMaxSize() - 1 ; i >= 0 ; i-- )
++            insert(bpr, i + 0x20) ;
++        check(bpr) ;
++        bpr.release() ;
++    }
++
++    @Test
++    public void bpt_records_5() {
++        BPTreeRecords bpr = make() ;
++        int N = bpr.getMaxSize() ;
++
++        for ( int i = bpr.getMaxSize() - 1 ; i >= 0 ; i-- )
++            insert(bpr, (i + 0x20)) ;
++
++        delete(bpr, (1 + 0x20)) ;
++        assertEquals(N - 1, bpr.getCount()) ;
++        check(bpr) ;
++
++        delete(bpr, (2 + 0x20)) ;
++        assertEquals(N - 2, bpr.getCount()) ;
++        check(bpr) ;
++
++        delete(bpr, bpr.getLowRecord()) ;
++        assertEquals(N - 3, bpr.getCount()) ;
++        check(bpr) ;
++
++        delete(bpr, bpr.getHighRecord()) ;
++        assertEquals(N - 4, bpr.getCount()) ;
++        check(bpr) ;
++
++        bpr.release() ;
++    }
++
++    @Test
++    public void bpt_records_6() {
++        BPTreeRecords bpr = make() ;
++        fill(bpr) ;
++
++        // No match.
++        assertNull(search(bpr, RecordLib.intToRecord(0x20))) ;
++
++        Record r = RecordLib.intToRecord(0x32) ;
++        Record r2 = search(bpr, r) ;
++        assertTrue(Record.keyEQ(r, r2)) ;
++
++        r = bpr.getLowRecord() ;
++        r2 = search(bpr, r) ;
++        assertTrue(Record.keyEQ(r, r2)) ;
++
++        r = bpr.getHighRecord() ;
++        r2 = search(bpr, r) ;
++        assertTrue(Record.keyEQ(r, r2)) ;
++
++        bpr.release() ;
++    }
++
++    @Test
++    public void bpt_shift_1() {
++        BPTreeRecords bpr1 = make() ;
++        BPTreeRecords bpr2 = make() ;
++
++        insert(bpr1, 10) ;
++        Record r = bpr1.shiftRight(bpr2, null) ;
++        assertNull(r) ;
++        // assertTrue(Record.keyEQ(r, RecordTestLib.intToRecord(10))) ;
++        contains(bpr1) ;
++        contains(bpr2, 10) ;
++
++        bpr1.release() ;
++        bpr2.release() ;
++
++    }
++
++    @Test
++    public void bpt_shift_2() {
++        BPTreeRecords bpr1 = make() ;
++        BPTreeRecords bpr2 = make() ;
++
++        insert(bpr1, 10) ;
++        Record r = bpr2.shiftLeft(bpr1, null) ;
++
++        assertTrue(Record.keyEQ(r, RecordLib.intToRecord(10))) ;
++        contains(bpr1) ;
++        contains(bpr2, 10) ;
++        bpr1.release() ;
++        bpr2.release() ;
++    }
++
++    @Test
++    public void bpt_shift_3() {
++        BPTreeRecords bpr1 = make() ;
++        BPTreeRecords bpr2 = make() ;
++
++        insert(bpr1, 10, 20) ;
++        insert(bpr2, 99) ;
++
++        Record r = bpr1.shiftRight(bpr2, null) ;
++
++        assertTrue(r + " != " + RecordLib.intToRecord(10), Record.keyEQ(r, RecordLib.intToRecord(10))) ;
++        contains(bpr1, 10) ;
++        contains(bpr2, 20, 99) ;
++        bpr1.release() ;
++        bpr2.release() ;
++    }
++
++    @Test
++    public void bpt_shift_4() {
++        BPTreeRecords bpr1 = make() ;
++        BPTreeRecords bpr2 = make() ;
++
++        insert(bpr1, 10, 20) ;
++        insert(bpr2, 5) ;
++
++        Record r = bpr2.shiftLeft(bpr1, null) ;
++        assertTrue(Record.keyEQ(r, RecordLib.intToRecord(10))) ;
++
++        contains(bpr1, 20) ;
++        contains(bpr2, 5, 10) ;
++        bpr1.release() ;
++        bpr2.release() ;
++    }
++
++    @Test
++    public void bpt_merge_1() {
++        BPTreeRecords bpr1 = make() ;
++        BPTreeRecords bpr2 = make() ;
++
++        insert(bpr1, 10, 20) ;
++        insert(bpr2, 99) ;
++
++        BPTreeRecords bpr3 = (BPTreeRecords)bpr1.merge(bpr2, null) ;
++        contains(bpr1, 10, 20, 99) ;
++        contains(bpr2) ;
++        assertSame(bpr1, bpr3) ;
++        bpr1.release() ;
++        bpr2.release() ;
++    }
++
++    @Test
++    public void bpt_merge_2() {
++        BPTreeRecords bpr1 = make() ;
++        BPTreeRecords bpr2 = make() ;
++
++        insert(bpr1, 10, 20) ;
++        insert(bpr2, 5) ;
++
++        BPTreeRecords bpr3 = (BPTreeRecords)bpr2.merge(bpr1, null) ;
++        contains(bpr1) ;
++        contains(bpr2, 5, 10, 20) ;
++        assertSame(bpr2, bpr3) ;
++        bpr1.release() ;
++        bpr2.release() ;
++    }
++
++    protected static void check(BPTreeRecords bpr) {
++        assertTrue(bpr.getCount() >= 0) ;
++        assertTrue(bpr.getCount() <= bpr.getMaxSize()) ;
++
++        assertEquals(bpr.getRecordBuffer().getLow(), bpr.getLowRecord()) ;
++        assertEquals(bpr.getRecordBuffer().getHigh(), bpr.getHighRecord()) ;
++
++        for ( int i = 1 ; i < bpr.getCount() ; i++ ) {
++            Record r1 = bpr.getRecordBuffer().get(i - 1) ;
++            Record r2 = bpr.getRecordBuffer().get(i) ;
++            assertTrue(Record.keyLE(r1, r2)) ;
++        }
++    }
++
++    private static Record search(BPTreeRecords bpr, int x) {
++        return search(bpr, RecordLib.intToRecord(x)) ;
++    }
++
++    private static Record search(BPTreeRecords bpr, Record r) {
++        return bpr.internalSearch(null, r) ;
++    }
++
++    private static void insert(BPTreeRecords bpr, int... values) {
++        for ( int value : values ) {
++            bpr.internalInsert(null, RecordLib.intToRecord(value)) ;
++        }
++    }
++
++    private static void insert(BPTreeRecords bpr, Record r) {
++        bpr.internalInsert(null, r) ;
++    }
++
++    private static void delete(BPTreeRecords bpr, int... values) {
++        for ( int value : values ) {
++            delete(bpr, RecordLib.intToRecord(value)) ;
++        }
++    }
++
++    private static void delete(BPTreeRecords bpr, Record r) {
++        bpr.internalDelete(null, r) ;
++    }
++
++    private static void contains(BPTreeRecords bpr, int... values) {
++        assertEquals(values.length, bpr.getCount()) ;
++        for ( int i = 1 ; i < values.length ; i++ )
++            assertTrue(Record.compareByKeyValue(RecordLib.intToRecord(values[i]), bpr.getRecordBuffer().get(i)) == 0) ;
++    }
++
++    protected static BPTreeRecords make() {
++        RecordBufferPage page = recordBufferPageMgr.create() ;
++        BPTreeRecordsMgr mgr = new BPTreeRecordsMgr(null, recordFactory, recordBufferPageMgr) ;
++        return new BPTreeRecords(mgr, page) ;
++    }
++
++    protected static void fill(BPTreeRecords bpr) {
++        int N = bpr.getRecordBuffer().maxSize() ;
++        for ( int i = 0 ; i < N ; i++ ) {
++            RecordBuffer rb = bpr.getRecordBuffer() ;
++            insert(bpr, (i + 0x30)) ;
++        }
++    }
++}

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPlusTreeIndexNonTxn.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPlusTreeIndexNonTxn.java
index 0000000,0000000..1834f77
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPlusTreeIndexNonTxn.java
@@@ -1,0 -1,0 +1,60 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree ;
++
++import org.apache.jena.atlas.logging.LogCtl ;
++import org.junit.AfterClass ;
++import org.junit.BeforeClass ;
++import org.seaborne.dboe.base.block.BlockMgr ;
++import org.seaborne.dboe.index.test.AbstractTestIndex ;
++import org.seaborne.dboe.sys.SystemIndex ;
++import org.seaborne.dboe.test.RecordLib ;
++
++/** Run the tests in default settings for a tree in "non-transactional" mode */ 
++public class TestBPlusTreeIndexNonTxn extends AbstractTestIndex {
++    static boolean addTracker = true  ;
++    // Panic.
++    static boolean addLogger  = false  ;
++
++    static boolean originalNullOut ;
++    @BeforeClass
++    static public void beforeClass() {
++        BPT.CheckingNode = true ;
++        originalNullOut = SystemIndex.getNullOut() ;
++        SystemIndex.setNullOut(true) ;
++    }
++
++    @AfterClass
++    static public void afterClass() {
++        SystemIndex.setNullOut(originalNullOut) ;
++    }
++    @Override
++    protected BPlusTree makeIndex(int order, int minRecords) {
++        BPlusTree bpt = BPlusTreeFactory.makeMem(order, minRecords, RecordLib.TestRecordLength, 0) ;
++        if ( addLogger ) {
++            // Put it in but disable it so that it can be enabled
++            // in the middle of a complex operation.
++            LogCtl.disable(BlockMgr.class) ;
++            bpt = BPlusTreeFactory.addLogging(bpt) ;
++        }
++        if ( addTracker )
++            bpt = BPlusTreeFactory.addTracking(bpt) ;
++        bpt.nonTransactional() ;
++        return bpt ;
++    }
++}

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPlusTreeNonTxn.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPlusTreeNonTxn.java
index 0000000,0000000..266326a
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPlusTreeNonTxn.java
@@@ -1,0 -1,0 +1,90 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree ;
++
++import static org.seaborne.dboe.index.test.IndexTestLib.add ;
++import static org.seaborne.dboe.test.RecordLib.intToRecord ;
++
++import java.util.List ;
++
++import org.apache.jena.atlas.logging.LogCtl ;
++import org.junit.AfterClass ;
++import org.junit.BeforeClass ;
++import org.seaborne.dboe.base.block.BlockMgr ;
++import org.seaborne.dboe.base.record.Record ;
++import org.seaborne.dboe.index.test.AbstractTestRangeIndex ;
++import org.seaborne.dboe.sys.SystemIndex ;
++import org.seaborne.dboe.test.RecordLib ;
++
++/** Run the tests in default settings for a tree in "non-transactional" mode */ 
++public class TestBPlusTreeNonTxn extends AbstractTestRangeIndex {
++    // See TestBPTreeModes for parameterised tests for the duplication modes.
++    
++    // Add tracker or not (usually not)
++    // The tracker checking can impose more constraints than are needed
++    // giving false negatives.  Iterator aren't tracked (they may not
++    // be consumed; don't release pages properly)
++    static boolean addTracker = false  ;
++    // Panic.
++    static boolean addLogger  = false  ;
++
++    static boolean originalNullOut ;
++    @BeforeClass
++    static public void beforeClass() {
++        BPT.CheckingNode = true ;
++        originalNullOut = SystemIndex.getNullOut() ;
++        SystemIndex.setNullOut(true) ;
++    }
++
++    @AfterClass
++    static public void afterClass() {
++        SystemIndex.setNullOut(originalNullOut) ;
++    }
++    
++    protected void testClearX(int N) {
++        int[] keys = new int[N] ; // Slice is 1000.
++        for ( int i = 0 ; i < keys.length ; i++ )
++            keys[i] = i ;
++        BPlusTree rIndex = makeRangeIndex(2, 2) ;
++        add(rIndex, keys) ;
++        rIndex.dump() ;
++        if ( N > 0 )
++            assertFalse(rIndex.isEmpty()) ;
++        List<Record> x = intToRecord(keys, RecordLib.TestRecordLength) ;
++        for ( int i = 0 ; i < keys.length ; i++ ) {
++            System.out.println(i+": "+x.get(i)) ;
++            rIndex.delete(x.get(i)) ;
++        }
++        assertTrue(rIndex.isEmpty()) ;
++    }
++    
++    @Override
++    protected BPlusTree makeRangeIndex(int order, int minRecords) {
++        BPlusTree bpt = BPlusTreeFactory.makeMem(order, minRecords, RecordLib.TestRecordLength, 0) ;
++        if ( addLogger ) {
++            // Put it in but disable it so that it can be enabled
++            // in the middle of a complex operation.
++            LogCtl.disable(BlockMgr.class) ;
++            bpt = BPlusTreeFactory.addLogging(bpt) ;
++        }
++        if ( addTracker )
++            bpt = BPlusTreeFactory.addTracking(bpt) ;
++        bpt.nonTransactional() ;
++        return bpt ;
++    }
++}

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPlusTreeTxn.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPlusTreeTxn.java
index 0000000,0000000..70000f6
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/TestBPlusTreeTxn.java
@@@ -1,0 -1,0 +1,205 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree;
++
++import org.apache.jena.query.ReadWrite ;
++import org.junit.Assert ;
++import org.junit.Test ;
++import org.seaborne.dboe.base.file.Location ;
++import org.seaborne.dboe.index.test.IndexTestLib ;
++import org.seaborne.dboe.jenax.Txn ;
++import org.seaborne.dboe.test.RecordLib ;
++import org.seaborne.dboe.transaction.Transactional ;
++import org.seaborne.dboe.transaction.TransactionalFactory ;
++import org.seaborne.dboe.transaction.txn.TransactionalComponent ;
++
++/** Tests of B+Tree and transactions */ 
++public class TestBPlusTreeTxn extends Assert {
++    
++    static BPlusTree createBPTree() { 
++        return BPlusTreeFactory.makeMem(2, 2, RecordLib.TestRecordLength, 0) ;
++    }
++    
++    static Transactional transactional(TransactionalComponent ... components) {
++        return transactional(Location.mem(), components) ;
++    }
++    
++    static Transactional transactional(Location location, TransactionalComponent ... components) {
++        return TransactionalFactory.createTransactional(location, components) ;
++    }
++    
++    // Commit
++    @Test public void bptree_txn_01() {
++        BPlusTree bpt = createBPTree() ;
++        assertNotNull(bpt.getComponentId()) ;
++        int outerRootIdx1 = bpt.getRootId() ;
++        Transactional thing = transactional(bpt) ;
++        Txn.executeWrite(thing, () -> { 
++            IndexTestLib.add(bpt, 1, 2, 3, 4) ;
++        } ); 
++        int outerRootIdx2 = bpt.getRootId() ;
++        assertNotEquals("After txn", outerRootIdx1, outerRootIdx2); 
++    }
++ 
++    // Commit - only the first changes the root.
++    @Test public void bptree_txn_02() {
++        BPlusTree bpt = createBPTree() ;
++        int outerRootIdx1 = bpt.getRootId() ;
++        Transactional thing = transactional(bpt) ;
++        Txn.executeWrite(thing, () -> { 
++            int rootIdx1 = bpt.getRootId() ;
++            assertEquals("Inside txn (1)", outerRootIdx1, rootIdx1);
++            IndexTestLib.add(bpt, 1) ;
++            int rootIdx2 = bpt.getRootId() ;
++            assertNotEquals("Inside txn (2)", rootIdx1, rootIdx2);
++            IndexTestLib.add(bpt, 2, 3, 4) ;
++            int rootIdx3 = bpt.getRootId() ;
++            assertEquals("Inside txn (3)", rootIdx2, rootIdx3);
++        } ) ; 
++        int outerRootIdx2 = bpt.getRootId() ;
++        assertNotEquals("After txn", outerRootIdx1, outerRootIdx2); 
++    }
++
++    // Abort
++    @Test public void bptree_txn_03() {
++        BPlusTree bpt = createBPTree() ;
++        int outerRootIdx1 = bpt.getRootId() ;
++        Transactional thing = transactional(bpt) ;
++        thing.begin(ReadWrite.WRITE);
++        IndexTestLib.add(bpt, 1, 2, 3, 4) ;
++        thing.abort() ;
++        thing.end() ;
++        int outerRootIdx2 = bpt.getRootId() ;
++        assertEquals("After txn", outerRootIdx1, outerRootIdx2); 
++    }
++    
++    // Two transactions
++    @Test public void bptree_txn_04() {
++        BPlusTree bpt = createBPTree() ;
++        int outerRootIdx1 = bpt.getRootId() ;
++        Transactional thing = transactional(bpt) ;
++        Txn.executeWrite(thing, () -> { 
++            IndexTestLib.add(bpt, 1, 2, 3, 4) ;
++        } ); 
++        int outerRootIdx2 = bpt.getRootId() ;
++        assertNotEquals("After txn(1)", outerRootIdx1, outerRootIdx2); 
++        Txn.executeWrite(thing, () -> { 
++            IndexTestLib.add(bpt, 5, 6) ;
++        } ); 
++        int outerRootIdx3 = bpt.getRootId() ;
++        assertNotEquals("After txn (2)", outerRootIdx1, outerRootIdx3); 
++        assertNotEquals("After txn (3)", outerRootIdx2, outerRootIdx3); 
++    }
++    
++    // Two transactions, second an insert no-op.
++    // Relies on all blocks not being full and so not being
++    // split on the way down due to the early split algorithm. 
++    @Test public void bptree_txn_05() {
++        BPlusTree bpt = createBPTree() ;
++        int outerRootIdx1 = bpt.getRootId() ;
++        Transactional thing = transactional(bpt) ;
++        Txn.executeWrite(thing, () -> { 
++            IndexTestLib.add(bpt, 1, 2, 3) ;
++        } ); 
++        int outerRootIdx2 = bpt.getRootId() ;
++        assertNotEquals("After txn(1)", outerRootIdx1, outerRootIdx2); 
++        Txn.executeWrite(thing, () -> { 
++            IndexTestLib.add(bpt, 1, 2) ;
++        } ); 
++        int outerRootIdx3 = bpt.getRootId() ;
++        assertNotEquals("After txn (2)", outerRootIdx1, outerRootIdx3); 
++        assertEquals("After txn (3)", outerRootIdx2, outerRootIdx3); 
++    }
++
++    // Two transactions, second a delete no-op.
++    // Relies on all blocks not being min0size so not rebalanced.
++    @Test public void bptree_txn_06() {
++        BPlusTree bpt = createBPTree() ;
++        int outerRootIdx1 = bpt.getRootId() ;
++        Transactional thing = transactional(bpt) ;
++        Txn.executeWrite(thing, () -> { 
++            IndexTestLib.add(bpt, 1, 2, 3) ;
++        } ); 
++        int outerRootIdx2 = bpt.getRootId() ;
++        assertNotEquals("After txn(1)", outerRootIdx1, outerRootIdx2); 
++        Txn.executeWrite(thing, () -> { 
++            IndexTestLib.delete(bpt, 5, 6) ;
++        } ); 
++        int outerRootIdx3 = bpt.getRootId() ;
++        assertNotEquals("After txn (2)", outerRootIdx1, outerRootIdx3); 
++        assertEquals("After txn (3)", outerRootIdx2, outerRootIdx3); 
++    }
++    
++    // Two trees
++    @Test public void bptree_txn_10() {
++        BPlusTree bpt1 = createBPTree() ;
++        BPlusTree bpt2 = createBPTree() ;
++        assertNotEquals(bpt1.getComponentId(), bpt2.getComponentId()) ;
++        
++        Transactional thing = transactional(bpt1, bpt2) ;
++        Txn.executeWrite(thing, () -> { 
++            IndexTestLib.add(bpt1, 1, 2, 3) ;
++            IndexTestLib.add(bpt2, 4, 5) ;
++        } );
++        Txn.executeRead(thing, ()->{
++            IndexTestLib.testIndexContents(bpt2, 4, 5);
++            IndexTestLib.testIndexContents(bpt1, 1, 2, 3);
++        } );
++    }
++    
++    @Test public void bptree_txn_11() {
++        BPlusTree bpt1 = createBPTree() ;
++        BPlusTree bpt2 = createBPTree() ;
++        assertNotEquals(bpt1.getComponentId(), bpt2.getComponentId()) ;
++        
++        Transactional thing = transactional(bpt1, bpt2) ;
++        
++        // Commit 1
++        Txn.executeWrite(thing, () -> { 
++            IndexTestLib.add(bpt1, 2, 1) ;
++            IndexTestLib.add(bpt2, 3, 4, 5) ;
++        }) ;
++        Txn.executeRead(thing, ()->{
++            IndexTestLib.testIndexContents(bpt2, 3, 4, 5);
++            IndexTestLib.testIndexContents(bpt1, 1, 2);
++        } );
++        
++        // Abort
++        thing.begin(ReadWrite.WRITE);
++        IndexTestLib.add(bpt1, 9, 10) ;
++        IndexTestLib.delete(bpt2, 3, 11) ;
++        thing.abort() ;
++        Txn.executeRead(thing, ()->{
++            IndexTestLib.testIndexContents(bpt2, 3, 4, 5);
++            IndexTestLib.testIndexContents(bpt1, 1, 2);
++        } );
++        
++        // Commit 2
++        Txn.executeWrite(thing, () -> { 
++            IndexTestLib.delete(bpt1, 1,3) ;
++            IndexTestLib.add(bpt1, 4) ;
++            IndexTestLib.add(bpt2, 11, 12, 13) ;
++        }) ;
++        Txn.executeRead(thing, ()->{
++            IndexTestLib.testIndexContents(bpt2, 3, 4, 5, 11, 12, 13);
++            IndexTestLib.testIndexContents(bpt1, 2, 4);
++        } );
++    }
++    
++    
++}

http://git-wip-us.apache.org/repos/asf/jena/blob/d9da3592/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/rewriter/TestBPlusTreeRewriterNonTxn.java
----------------------------------------------------------------------
diff --cc jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/rewriter/TestBPlusTreeRewriterNonTxn.java
index 0000000,0000000..d9c2b6a
new file mode 100644
--- /dev/null
+++ b/jena-db/dboe-trans-data/src/test/java/org/seaborne/dboe/trans/bplustree/rewriter/TestBPlusTreeRewriterNonTxn.java
@@@ -1,0 -1,0 +1,179 @@@
++/*
++ *  Licensed under the Apache License, Version 2.0 (the "License");
++ *  you may not use this file except in compliance with the License.
++ *  You may obtain a copy of the License at
++ *
++ *      http://www.apache.org/licenses/LICENSE-2.0
++ *
++ *  Unless required by applicable law or agreed to in writing, software
++ *  distributed under the License is distributed on an "AS IS" BASIS,
++ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
++ *  See the License for the specific language governing permissions and
++ *  limitations under the License.
++ *
++ *  See the NOTICE file distributed with this work for additional
++ *  information regarding copyright ownership.
++ */
++
++package org.seaborne.dboe.trans.bplustree.rewriter;
++
++import java.util.ArrayList ;
++import java.util.Iterator ;
++import java.util.List ;
++
++import org.apache.jena.atlas.lib.Bytes ;
++import org.junit.AfterClass ;
++import org.junit.Assert ;
++import org.junit.BeforeClass ;
++import org.junit.Test ;
++import org.seaborne.dboe.base.block.BlockMgr ;
++import org.seaborne.dboe.base.block.BlockMgrFactory ;
++import org.seaborne.dboe.base.file.BufferChannel ;
++import org.seaborne.dboe.base.file.FileFactory ;
++import org.seaborne.dboe.base.file.FileSet ;
++import org.seaborne.dboe.base.record.Record ;
++import org.seaborne.dboe.base.record.RecordFactory ;
++import org.seaborne.dboe.sys.Names ;
++import org.seaborne.dboe.trans.bplustree.BPTreeException ;
++import org.seaborne.dboe.trans.bplustree.BPlusTree ;
++import org.seaborne.dboe.trans.bplustree.BPlusTreeParams ;
++//import org.seaborne.dboe.trans.bplustree.rewriter.BPlusTreeRewriter ;
++
++public class TestBPlusTreeRewriterNonTxn extends Assert
++{
++    // See also CmdTestBlusTreeRewriter for randomized soak testing. 
++    
++    static int KeySize     = 4 ;
++    static int ValueSize   = 8 ;
++    static RecordFactory recordFactory = new RecordFactory(KeySize,ValueSize) ;
++    
++    // The BPlusTreeRewriter works directly on storage.
++    static boolean b ; 
++    @BeforeClass public static void beforeClass()   { b = BlockMgrFactory.AddTracker ; BlockMgrFactory.AddTracker = false ; }
++    @AfterClass  public static void afterClass()    { BlockMgrFactory.AddTracker = b  ;}
++    
++    @Test public void bpt_rewrite_01()  { runTest(2, 0) ; }
++    @Test public void bpt_rewrite_02()  { runTest(3, 0) ; }
++
++    @Test public void bpt_rewrite_03()  { runTest(2, 1) ; }
++    @Test public void bpt_rewrite_04()  { runTest(3, 1) ; }
++
++    @Test public void bpt_rewrite_05()  { runTest(2, 2) ; }
++    @Test public void bpt_rewrite_06()  { runTest(3, 2) ; }
++    
++    @Test public void bpt_rewrite_07()  { runTest(2, 100) ; }
++    @Test public void bpt_rewrite_08()  { runTest(3, 100) ; }
++    
++    @Test public void bpt_rewrite_99()  { runTest(5, 1000) ; }
++    
++    static void runTest(int order, int N)
++    { runOneTest(order, N , recordFactory, false) ; }
++    
++    public static void runOneTest(int order, int N, RecordFactory recordFactory, boolean debug)
++    {
++        BPlusTreeParams bptParams = new BPlusTreeParams(order, recordFactory) ;
++        BPlusTreeRewriter.debug = debug ;
++
++        // ---- Test data
++        List<Record> originaldata = TestBPlusTreeRewriterNonTxn.createData(N, recordFactory) ;
++        if ( debug )
++            System.out.println("Test data: "+originaldata) ;
++
++        FileSet destination = FileSet.mem() ;
++        // ---- Rewrite
++        BufferChannel rootState = FileFactory.createBufferChannel(destination, Names.extBptState) ;
++        // Write leaves to ...
++        BlockMgr blkMgr1 = BlockMgrFactory.create(destination, Names.extBptTree, bptParams.getCalcBlockSize(), 10, 10) ;
++        // Write nodes to ...
++        BlockMgr blkMgr2 = BlockMgrFactory.create(destination, Names.extBptTree, bptParams.getCalcBlockSize(), 10, 10) ;
++        
++        BPlusTree bpt2 = BPlusTreeRewriter.packIntoBPlusTree(originaldata.iterator(), bptParams, recordFactory,
++                                                             rootState, blkMgr1, blkMgr2) ;
++        if ( debug )
++        {
++            BPlusTreeRewriterUtils.divider() ;
++            bpt2.dump();
++        }
++        
++        // ---- Checking
++        bpt2.check() ;
++        
++        scanComparision(originaldata, bpt2) ;
++        findComparison(originaldata, bpt2) ;
++        sizeComparison(originaldata, bpt2) ;
++    }
++    
++    public static void scanComparision(List<Record> originaldata, BPlusTree bpt2)
++    {
++        // ** Scan comparisonSetupIndex
++        Iterator<Record> iter1 = originaldata.iterator() ;
++        Iterator<Record> iter2 = bpt2.iterator() ;
++        long count = 0 ;
++        for ( ; iter1.hasNext() ; )
++        {
++            count++ ;
++            Record r1 = iter1.next();
++            if ( ! iter2.hasNext() )
++                error("Deviation: new B+Tree is smaller") ; 
++            Record r2 = iter2.next();
++    
++            if ( ! Record.equals(r1, r2) )
++                error("Deviation in iteration record %d: %s : %s", count, r1, r2) ;
++        }
++        if ( iter2.hasNext() )
++            error("New B+Tree larger than original") ; 
++    }
++
++    public static void findComparison(List<Record> originaldata, BPlusTree bpt2)
++    {
++        Iterator<Record> iter1 = originaldata.iterator() ;
++    
++        long count = 0 ;
++        for ( ; iter1.hasNext() ; )
++        {
++            count++ ;
++            Record r1 = iter1.next();
++            
++            Record r3 = bpt2.find(r1) ;
++            if ( r3 == null )
++            {
++                r3 = bpt2.find(r1) ;
++                error("Deviation in find at record %d: %s : null", count, r1) ;
++            }
++            if ( ! Record.equals(r1, r3) )
++                error("Deviation in find at record %d: %s : %s", count, r1, r3) ;
++        }
++    
++    }
++
++    public static void sizeComparison(List<Record> originaldata, BPlusTree bpt2)
++    {
++      long count1 = originaldata.size() ;
++      long count2 = bpt2.size() ;
++      //System.out.printf("Sizes = %d / %d\n", count1, count2) ;
++      if ( count1 != count2 )
++          // Not error - this test does not identify why there was a problem so continue.
++          System.err.println("**** DIFFERENT") ;
++    }
++
++    static List<Record> createData(int N, RecordFactory recordFactory)
++    {
++        List<Record> originaldata = new ArrayList<>(N) ;
++        for ( int i = 0; i < N ; i++ )
++        {
++            Record record = recordFactory.create() ;
++            Bytes.setInt(i+1, record.getKey()) ;
++            if ( recordFactory.hasValue() )
++                Bytes.setInt(10*i+1, record.getValue()) ;
++            originaldata.add(record) ;
++        }
++        return originaldata ;
++    }
++    
++    private static void error(String string, Object ...args)
++    {
++        String msg = String.format(string, args) ;
++        System.err.println(msg) ;
++        throw new BPTreeException(msg) ;
++    }
++}


Mime
View raw message