* @param sequence
     *            The insert sequence (FORWARD, REVERSE or NONE)
     * @param policy
     *            The SplitPolicy for this insertion
     * @return offset of the inserted key block. If positive, this value denotes
     *         a location in this Buffer. If negative, it denotes a location in
     *         the right sibling Buffer.
     * @throws PersistitException
     */
    final int split(Buffer rightSibling, Key key, ValueHelper valueHelper, int foundAt, Key indexKey,
            Sequence sequence, SplitPolicy policy) throws PersistitException {
        // Make sure the right sibling page is empty.

        Debug.$assert0.t(rightSibling._keyBlockEnd == KEY_BLOCK_START);
        Debug.$assert0.t(rightSibling._alloc == rightSibling._bufferSize);
        if (Debug.ENABLED) {
            assertVerify();
        }

        if (_mvvCount > 0) {
            rightSibling._mvvCount = Integer.MAX_VALUE;
        }

        // First we calculate how large the virtual page containing the
        // modified or inserted key/value pair would be.
        //
        int currentSize = _bufferSize - _alloc - _slack + _keyBlockEnd - KEY_BLOCK_START;

        int foundAtPosition = foundAt & P_MASK;
        boolean exact = (foundAt & EXACT_MASK) != 0;
        int depth = (foundAt & DEPTH_MASK) >>> DEPTH_SHIFT;
        boolean fixupSuccessor = (foundAt & FIXUP_MASK) > 0;

        int ebcNew;
        int ebcSuccessor;
        int deltaSuccessorTailSize = 0;
        int deltaSuccessorEbc = 0;

        if (fixupSuccessor) {
            int kbSuccessor = getInt(foundAtPosition);
            int tbSuccessor = getInt(decodeKeyBlockTail(kbSuccessor));
            ebcNew = decodeKeyBlockEbc(kbSuccessor);
            ebcSuccessor = depth;
            int tbSize = decodeTailBlockSize(tbSuccessor);

            // This is the number of bytes by which the successor key
            // can have its elided byte count increased.
            deltaSuccessorEbc = ebcSuccessor - ebcNew;

            int oldSize = (tbSize + ~TAILBLOCK_MASK) & TAILBLOCK_MASK;
            int newSize = (tbSize - deltaSuccessorEbc + ~TAILBLOCK_MASK) & TAILBLOCK_MASK;

            // This is the number of bytes by which the successor tail block
            // can be reduced (because its elision count has increased.)
            deltaSuccessorTailSize = oldSize - newSize;
        } else {
            ebcSuccessor = 0;
            ebcNew = depth;
        }
        int keyBlockSizeDelta = KEYBLOCK_LENGTH;
        int oldTailBlockSize = 0;
        int newTailBlockSize;
        int newValueSize;
        if (exact) {
            int kbData = getInt(foundAtPosition);
            int tail = decodeKeyBlockTail(kbData);
            int tbData = getInt(tail);
            int tbSize = decodeTailBlockSize(tbData);
            int klength = decodeTailBlockKLength(tbData);
            oldTailBlockSize = (tbSize + ~TAILBLOCK_MASK) & TAILBLOCK_MASK;
            keyBlockSizeDelta = 0;
            ebcNew = decodeKeyBlockEbc(kbData);
            newValueSize = valueHelper.requiredLength(_bytes, tail + _tailHeaderSize + klength, tbSize
                    - _tailHeaderSize - klength);
        } else {
            newValueSize = valueHelper.requiredLength(_bytes, 0, -1);
        }
        newTailBlockSize = ((isIndexPage() ? 0 : newValueSize) + _tailHeaderSize + key.getEncodedSize() - ebcNew - 1 + ~TAILBLOCK_MASK)
                & TAILBLOCK_MASK;

        int virtualSize = currentSize + newTailBlockSize - oldTailBlockSize + keyBlockSizeDelta
                - deltaSuccessorTailSize;

        int splitBest = 0; // Maximal fitness measure
        int splitAt = 0; // Offset to first keyblock in right sibling

        int leftSize = 0; // Bytes in left sibling page

        boolean armed = true;
        int whereInserted = -1;

        int rightKeyBlock = _keyBlockEnd - KEYBLOCK_LENGTH;
        for (int p = KEY_BLOCK_START; p < rightKeyBlock;) {
            int splitCandidate = 0;
            if (p == foundAtPosition && armed) {

                // Here we are adding the newly inserted (or replacing) record
                // to the left side. The key block pointed to by p is our
                // candidate for the first key in the right sibling page.

                leftSize += newTailBlockSize + KEYBLOCK_LENGTH;
                if (exact) {
                    p += KEYBLOCK_LENGTH;
                }

                // Compute the number of bytes by which the successor tailblock
                // will grow due to its elision count becoming zero.
                //
                int kbData = getInt(p);
                int tbData = getInt(decodeKeyBlockTail(kbData));
                int ebc = decodeKeyBlockEbc(kbData);
                int tbSize = decodeTailBlockSize(tbData);
                int tbSizeDelta = ((tbSize + ebc + ~TAILBLOCK_MASK) & TAILBLOCK_MASK)
                        - ((tbSize + ~TAILBLOCK_MASK) & TAILBLOCK_MASK);

                int edgeTailBlockSize = (decodeTailBlockKLength(tbData) - deltaSuccessorEbc + _tailHeaderSize + ~TAILBLOCK_MASK)
                        & TAILBLOCK_MASK;

                if (p < rightKeyBlock) {
                    int rightSize = virtualSize - leftSize + tbSizeDelta;

                    splitCandidate = policy.splitFit(this, p, foundAtPosition, exact, leftSize + KEYBLOCK_LENGTH
                            + edgeTailBlockSize, rightSize, currentSize, virtualSize, _bufferSize - KEY_BLOCK_START,
                            splitBest, sequence);
                    if (splitCandidate > splitBest) {
                        splitBest = splitCandidate;
                        splitAt = p | EXACT_MASK;
                    }
                }
                armed = false;
            } else {
                // Here we are proposing the key block pointed to by p as the
                // last key of the left page.
                int kbData = getInt(p);
                int tbData = getInt(decodeKeyBlockTail(kbData));
                int tbSizeDelta;
                int tailBlockSize = (decodeTailBlockSize(tbData) + ~TAILBLOCK_MASK) & TAILBLOCK_MASK;
                leftSize += tailBlockSize + KEYBLOCK_LENGTH;

                p += KEYBLOCK_LENGTH;
                int edgeTailBlockSize;

                if (p == foundAtPosition && armed) {
                    tbSizeDelta = (((isIndexPage() ? 0 : newValueSize) + _tailHeaderSize + key.getEncodedSize() + ~TAILBLOCK_MASK) & TAILBLOCK_MASK)
                            - newTailBlockSize;

                    edgeTailBlockSize = (key.getEncodedSize() - depth + _tailHeaderSize + ~TAILBLOCK_MASK)
                            & TAILBLOCK_MASK;
                } else {
                    kbData = getInt(p);
                    tbData = getInt(decodeKeyBlockTail(kbData));
                    int ebc = decodeKeyBlockEbc(kbData);
                    int tbSize = decodeTailBlockSize(tbData);

                    tbSizeDelta = ((tbSize + ebc + ~TAILBLOCK_MASK) & TAILBLOCK_MASK)
                            - ((tbSize + ~TAILBLOCK_MASK) & TAILBLOCK_MASK);

                    edgeTailBlockSize = (decodeTailBlockKLength(tbData) + _tailHeaderSize + ~TAILBLOCK_MASK)
                            & TAILBLOCK_MASK;
                }

                if (p < rightKeyBlock) {
                    int rightSize = virtualSize - leftSize + tbSizeDelta;

                    splitCandidate = policy.splitFit(this, p, foundAtPosition, exact, leftSize + KEYBLOCK_LENGTH
                            + edgeTailBlockSize, rightSize, currentSize, virtualSize, _bufferSize - KEY_BLOCK_START,
                            splitBest, sequence);
                    if (splitCandidate > splitBest) {
                        splitBest = splitCandidate;
                        splitAt = p;
                    }
                }
            }
            // Following is true when we have gone past the best split
            // point.
            if (splitCandidate == 0 && splitBest != 0) {
                break;
            }
        }

        if (splitBest == 0) {
            throw new InvalidPageStructureException("Can't split page " + this + " exact=" + exact + " insertAt="
                    + foundAtPosition + " currentSize=" + currentSize + " virtualSize=" + virtualSize + " leftSize="
                    + leftSize);
        }
        //
        // Now move the keys and records.
        //
        byte[] indexKeyBytes = indexKey.getEncodedBytes();
        int splitAtPosition = splitAt & P_MASK;

        boolean lastLeft = (splitAt & EXACT_MASK) != 0;
        boolean firstRight = !lastLeft && splitAtPosition == foundAtPosition;
        int indexKeyDepth = 0;
        //
        // First we need to compute the full key in the right sibling page.
        //
        int scanStart = KEY_BLOCK_START;
        if (foundAtPosition <= splitAt) {
            // We know that the value of key is at or before foundAt, so we
            // can just copy the bytes from key and avoid scanning the records
            // to the left of foundAt.
            //
            scanStart = foundAtPosition;
            indexKeyDepth = key.getEncodedSize();
            System.arraycopy(key.getEncodedBytes(), 0, indexKeyBytes, 0, indexKeyDepth);
        }
        //
        // If we are inserting the new key as the first key of the right
        // page, then do not scan because the insert key is the same as the
        // split key.
        //
        if (!firstRight) {
            for (int p = scanStart; p <= splitAtPosition; p += KEYBLOCK_LENGTH) {
                int kbData = getInt(p);
                int ebc = decodeKeyBlockEbc(kbData);
                int db = decodeKeyBlockDb(kbData);
                int tail = decodeKeyBlockTail(kbData);
                if (ebc > indexKeyDepth) {
                    throw new InvalidPageStructureException("ebc at " + p + " ebc=" + ebc + " > indexKeyDepth="
                            + indexKeyDepth);
                }
                indexKeyDepth = ebc;
                indexKeyBytes[indexKeyDepth++] = (byte) db;
                int tbData = getInt(tail);
                int klength = decodeTailBlockKLength(tbData);

                System.arraycopy(_bytes, tail + _tailHeaderSize, indexKeyBytes, indexKeyDepth, klength);
                indexKeyDepth += klength;
            }
        }
        indexKey.setEncodedSize(indexKeyDepth);
        //
        // Set the keyblock end for the right sibling so that alloc() knows
        // its bounds.
        //
        rightSibling.setKeyBlockEnd(_keyBlockEnd - (splitAtPosition - KEY_BLOCK_START));
        int rightP = KEY_BLOCK_START;
        //
        // Now move all the records from the split point forward to the
        // right page and deallocate their space in the left page.
        //

        for (int p = splitAtPosition; p < _keyBlockEnd; p += KEYBLOCK_LENGTH) {

            final int kbData = getInt(p);
            final int db = decodeKeyBlockDb(kbData);
            final int ebc = decodeKeyBlockEbc(kbData);
            final int tail = decodeKeyBlockTail(kbData);

            final int tbData = getInt(tail);
            final int klength = decodeTailBlockKLength(tbData);
            final int tailBlockSize = decodeTailBlockSize(tbData);
            final int dataSize = tailBlockSize - _tailHeaderSize - klength;
            final int newKeyLength;
            final int newDb;
            final int newEbc;
            //
            // Adjust for first key in right page
            //
            if (p == splitAtPosition) {
                newKeyLength = klength + ebc;
                newDb = ebc > 0 ? indexKeyBytes[0] : db;
                newEbc = 0;
            } else {
                newKeyLength = klength;
                newDb = db;
                newEbc = ebc;
            }
            //
            // Adjust for replacement case.
            //
            int newDataSize;
            if (exact && isDataPage() && foundAtPosition == p) {
                newDataSize = newValueSize;
                Debug.$assert0.t(newDataSize > dataSize);
            } else {
                newDataSize = dataSize;
            }
            newTailBlockSize = newKeyLength + newDataSize + _tailHeaderSize;
            //
            // Allocate the new tail block.
            //
            final int newTailBlock = rightSibling.allocTail(newTailBlockSize);
            Debug.$assert0.t(newTailBlock >= 0 && newTailBlock < rightSibling._bufferSize);
            Debug.$assert0.t(newTailBlock != -1);

            rightSibling.putInt(newTailBlock, encodeTailBlock(newTailBlockSize, newKeyLength));

            if (p == splitAtPosition && ebc > 0) {
                System.arraycopy(indexKeyBytes, 1, // Note: byte 0 is the
                                                   // discriminator byte
                        rightSibling._bytes, newTailBlock + _tailHeaderSize, ebc - 1);

                rightSibling.putByte(newTailBlock + _tailHeaderSize + ebc - 1, db);

                System.arraycopy(_bytes, tail + _tailHeaderSize, rightSibling._bytes, newTailBlock + _tailHeaderSize
                        + ebc, klength);
            } else {
                System.arraycopy(_bytes, tail + _tailHeaderSize, rightSibling._bytes, newTailBlock + _tailHeaderSize,
                        klength);
            }

            if (isDataPage()) {
                System.arraycopy(_bytes, tail + _tailHeaderSize + klength, rightSibling._bytes, newTailBlock
                        + _tailHeaderSize + newKeyLength, dataSize);
            } else {
                rightSibling.putInt(newTailBlock + TAILBLOCK_POINTER, getInt(tail + TAILBLOCK_POINTER));
            }

            //
            // Put the key block into the right page.
            //
            rightSibling.putInt(rightP, encodeKeyBlock(newEbc, newDb, newTailBlock));
            rightP += KEYBLOCK_LENGTH;
            //
            // Deallocate the tailblock from the left page. If this is the
            // split key, then we deallocate the whole tail only if the
            // insert key is going in as the first key in the right sibling.
            // Otherwise, we simply deallocate the data.
            //
            //
            if (p != splitAtPosition || (firstRight && !exact)) {
                // deallocate the whole tail block. If this is the split
                // position, then we are going to add a new, different edge
                // key below.
                //
                deallocTail(tail, tailBlockSize);
            } else {
                // This is the split position, and the insert key is either
                // an exact match for the first key in the right sibling page,
                // or it is not being inserted there. In this case, the key
                // we are examining in the left sibling page will become the
                // new edge key. All we need to do is deallocate any extra
                // space needed by this key's data.
                //
                // Later, we will fix up the edge key in the case where the
                // insert key will be the first key of the right sibling.
                //
                if (isDataPage()) {
                    currentSize = (tailBlockSize + ~TAILBLOCK_MASK) & TAILBLOCK_MASK;

                    int newSize = (tailBlockSize - dataSize + ~TAILBLOCK_MASK) & TAILBLOCK_MASK;
                    if (newSize != currentSize) {
                        deallocTail(tail + newSize, currentSize - newSize);
                    }
                    putInt(tail, encodeTailBlock(_tailHeaderSize + klength, klength));
                } else {
                    // edge key for index block. We destroy the pointer value
                    // so that we don't get confused later.
                    putInt(tail + TAILBLOCK_POINTER, -1);
                }
            }
        }
        //
        // Fix up the right edge key in the left page.
        //
        int kbData = getInt(splitAtPosition);
        int edgeTail = decodeKeyBlockTail(kbData);
        int ebc = decodeKeyBlockEbc(kbData);
        depth = (foundAt & DEPTH_MASK) >>> DEPTH_SHIFT;

        if (firstRight && !exact) {
            //
            // Handle the special case where the inserted key is the first
            // key of the right page.
            //
            if (fixupSuccessor) {
                depth = ebc;
            }
            int db = indexKeyBytes[depth];

            int edgeKeyLength = indexKey.getEncodedSize() - depth - 1;
            int edgeTailBlockSize = edgeKeyLength + _tailHeaderSize;
            edgeTail = allocTail(edgeTailBlockSize);
            if (edgeTail == -1) {
                setKeyBlockEnd(splitAtPosition);
                repack();
                edgeTail = allocTail(edgeTailBlockSize);
            }

            if (edgeTail == -1) {
                _persistit
                        .fatal("Insufficient space for edgeTail records in " + this + " at =" + splitAtPosition, null);
            }
            putInt(edgeTail, encodeTailBlock(edgeTailBlockSize, edgeKeyLength));

            System.arraycopy(indexKeyBytes, depth + 1, _bytes, edgeTail + _tailHeaderSize, edgeKeyLength);

            putInt(splitAtPosition, encodeKeyBlock(depth, db, edgeTail));
        }
        //
        // In any case, the new key block end is at the split position.
        //
        setKeyBlockEnd(splitAtPosition + KEYBLOCK_LENGTH);
        //
        // If this is in index level, then set the pointer value to -1 so that
        // it does not later get confused and interpreted as a valid pointer.
        //
        if (isIndexPage()) {
            putInt(edgeTail + TAILBLOCK_POINTER, -1);
        }

        invalidateFastIndex();
        rightSibling.invalidateFastIndex();

        Debug.$assert0.t(rightSibling._keyBlockEnd > KEY_BLOCK_START + KEYBLOCK_LENGTH ? rightSibling
                .adjacentKeyCheck(KEY_BLOCK_START) : true);

        if (!exact) {
            if (foundAtPosition >= splitAtPosition && (!lastLeft || foundAtPosition > splitAtPosition)) {
                foundAt -= (splitAtPosition - KEY_BLOCK_START);
                if (firstRight && !fixupSuccessor) {
                    foundAt = (foundAt & P_MASK) | (ebc > 0 ? FIXUP_MASK : 0) | (ebc << DEPTH_SHIFT);
                }
                final int t = rightSibling.putValue(key, valueHelper, foundAt, true);
                whereInserted = -foundAt;
                Debug.$assert0.t(t != -1);
            } else {
                final int t = putValue(key, valueHelper, foundAt, true);
                whereInserted = foundAt;
                Debug.$assert0.t(t != -1);
            }
        } else {
            if (foundAtPosition < splitAtPosition) {
                whereInserted = replaceValue(key, valueHelper, foundAtPosition);
            } else {
                whereInserted = rightSibling.replaceValue(key, valueHelper, foundAtPosition - splitAtPosition
                        + KEY_BLOCK_START);
            }
            //
            // It is really bad if whereInserted is less than 0. Means that we
            // failed to replace the value.
            //
            Debug.$assert0.t(whereInserted > 0);
            if (whereInserted <= 0) {
                throw new IllegalStateException("p = " + whereInserted + " foundAtPosition=" + foundAtPosition
                        + " splitAtPosition=" + splitAtPosition);
            }
        }

        Debug.$assert0.t(KEY_BLOCK_START + KEYBLOCK_LENGTH < _keyBlockEnd);
        Debug.$assert0.t(KEY_BLOCK_START + KEYBLOCK_LENGTH < rightSibling._keyBlockEnd);

        // Indicate that both buffers have changed.
        bumpGeneration();
        rightSibling.bumpGeneration();

        if (Debug.ENABLED) {
            assertVerify();
            rightSibling.assertVerify();
        }

        return whereInserted;
    }