/*
 * Copyright 2004-2019 H2 Group. Multiple-Licensed under the MPL 2.0,
 * and the EPL 1.0 (http://h2database.com/html/license.html).
 * Initial Developer: H2 Group
 */
package org.h2.index;

import java.util.Arrays;
import org.h2.api.ErrorCode;
import org.h2.engine.Constants;
import org.h2.engine.Session;
import org.h2.message.DbException;
import org.h2.result.SearchRow;
import org.h2.store.Data;
import org.h2.store.Page;
import org.h2.store.PageStore;

A b-tree leaf page that contains index data. Format:

page type: byte
checksum: short
parent page id (0 for root): int
index id: varInt
entry count: short
list of offsets: short
data (key: varLong, value,...)

/**
 * A b-tree leaf page that contains index data. Format:
 * <ul>
 * <li>page type: byte</li>
 * <li>checksum: short</li>
 * <li>parent page id (0 for root): int</li>
 * <li>index id: varInt</li>
 * <li>entry count: short</li>
 * <li>list of offsets: short</li>
 * <li>data (key: varLong, value,...)</li>
 * </ul>
 */
public class PageBtreeLeaf extends PageBtree {

    private static final int OFFSET_LENGTH = 2;

    private final boolean optimizeUpdate;
    private boolean writtenData;

    private PageBtreeLeaf(PageBtreeIndex index, int pageId, Data data) {
        super(index, pageId, data);
        this.optimizeUpdate = index.getDatabase().getSettings().optimizeUpdate;
    }

    
Read a b-tree leaf page.
Params:
index – the index
data – the data
pageId – the page id
Returns:
the page/**
     * Read a b-tree leaf page.
     *
     * @param index the index
     * @param data the data
     * @param pageId the page id
     * @return the page
     */
    public static Page read(PageBtreeIndex index, Data data, int pageId) {
        PageBtreeLeaf p = new PageBtreeLeaf(index, pageId, data);
        p.read();
        return p;
    }

    
Create a new page.
Params:
index – the index
pageId – the page id
parentPageId – the parent
Returns:
the page/**
     * Create a new page.
     *
     * @param index the index
     * @param pageId the page id
     * @param parentPageId the parent
     * @return the page
     */
    static PageBtreeLeaf create(PageBtreeIndex index, int pageId,
            int parentPageId) {
        PageBtreeLeaf p = new PageBtreeLeaf(index, pageId, index.getPageStore()
                .createData());
        index.getPageStore().logUndo(p, null);
        p.rows = SearchRow.EMPTY_ARRAY;
        p.parentPageId = parentPageId;
        p.writeHead();
        p.start = p.data.length();
        return p;
    }

    private void read() {
        data.reset();
        int type = data.readByte();
        data.readShortInt();
        this.parentPageId = data.readInt();
        onlyPosition = (type & Page.FLAG_LAST) == 0;
        int indexId = data.readVarInt();
        if (indexId != index.getId()) {
            throw DbException.get(ErrorCode.FILE_CORRUPTED_1,
                    "page:" + getPos() + " expected index:" + index.getId() +
                    "got:" + indexId);
        }
        entryCount = data.readShortInt();
        offsets = new int[entryCount];
        rows = new SearchRow[entryCount];
        for (int i = 0; i < entryCount; i++) {
            offsets[i] = data.readShortInt();
        }
        start = data.length();
        written = true;
        writtenData = true;
    }

    @Override
    int addRowTry(SearchRow row) {
        int x = addRow(row, true);
        memoryChange();
        return x;
    }

    private int addRow(SearchRow row, boolean tryOnly) {
        int rowLength = index.getRowSize(data, row, onlyPosition);
        int pageSize = index.getPageStore().getPageSize();
        int last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
        if (last - rowLength < start + OFFSET_LENGTH) {
            if (tryOnly && entryCount > 1) {
                int x = find(row, false, true, true);
                if (entryCount < 5) {
                    // required, otherwise the index doesn't work correctly
                    return entryCount / 2;
                }
                // split near the insertion point to better fill pages
                // split in half would be:
                // return entryCount / 2;
                int third = entryCount / 3;
                return x < third ? third : x >= 2 * third ? 2 * third : x;
            }
            readAllRows();
            writtenData = false;
            onlyPosition = true;
            // change the offsets (now storing only positions)
            int o = pageSize;
            for (int i = 0; i < entryCount; i++) {
                o -= index.getRowSize(data, getRow(i), true);
                offsets[i] = o;
            }
            last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
            rowLength = index.getRowSize(data, row, true);
            if (last - rowLength < start + OFFSET_LENGTH) {
                throw DbException.throwInternalError();
            }
        }
        index.getPageStore().logUndo(this, data);
        if (!optimizeUpdate) {
            readAllRows();
        }
        changeCount = index.getPageStore().getChangeCount();
        written = false;
        int x;
        if (entryCount == 0) {
            x = 0;
        } else {
            x = find(row, false, true, true);
        }
        start += OFFSET_LENGTH;
        int offset = (x == 0 ? pageSize : offsets[x - 1]) - rowLength;
        if (optimizeUpdate && writtenData) {
            if (entryCount > 0) {
                byte[] d = data.getBytes();
                int dataStart = offsets[entryCount - 1];
                System.arraycopy(d, dataStart, d, dataStart - rowLength,
                        offset - dataStart + rowLength);
            }
            index.writeRow(data, offset, row, onlyPosition);
        }
        offsets = insert(offsets, entryCount, x, offset);
        add(offsets, x + 1, entryCount + 1, -rowLength);
        rows = insert(rows, entryCount, x, row);
        entryCount++;
        index.getPageStore().update(this);
        return -1;
    }

    private void removeRow(int at) {
        if (!optimizeUpdate) {
            readAllRows();
        }
        index.getPageStore().logUndo(this, data);
        entryCount--;
        written = false;
        changeCount = index.getPageStore().getChangeCount();
        if (entryCount <= 0) {
            DbException.throwInternalError(Integer.toString(entryCount));
        }
        int startNext = at > 0 ? offsets[at - 1] : index.getPageStore().getPageSize();
        int rowLength = startNext - offsets[at];
        start -= OFFSET_LENGTH;

        if (optimizeUpdate) {
            if (writtenData) {
                byte[] d = data.getBytes();
                int dataStart = offsets[entryCount];
                System.arraycopy(d, dataStart, d,
                        dataStart + rowLength, offsets[at] - dataStart);
                Arrays.fill(d, dataStart, dataStart + rowLength, (byte) 0);
            }
        }

        offsets = remove(offsets, entryCount + 1, at);
        add(offsets, at, entryCount, rowLength);
        rows = remove(rows, entryCount + 1, at);
    }

    int getEntryCount() {
        return entryCount;
    }

    @Override
    PageBtree split(int splitPoint) {
        int newPageId = index.getPageStore().allocatePage();
        PageBtreeLeaf p2 = PageBtreeLeaf.create(index, newPageId, parentPageId);
        while (splitPoint < entryCount) {
            p2.addRow(getRow(splitPoint), false);
            removeRow(splitPoint);
        }
        memoryChange();
        p2.memoryChange();
        return p2;
    }

    @Override
    PageBtreeLeaf getFirstLeaf() {
        return this;
    }

    @Override
    PageBtreeLeaf getLastLeaf() {
        return this;
    }

    @Override
    SearchRow remove(SearchRow row) {
        int at = find(row, false, false, true);
        SearchRow delete = getRow(at);
        if (index.compareRows(row, delete) != 0 || delete.getKey() != row.getKey()) {
            throw DbException.get(ErrorCode.ROW_NOT_FOUND_WHEN_DELETING_1,
                    index.getSQL(new StringBuilder(), false).append(": ").append(row).toString());
        }
        index.getPageStore().logUndo(this, data);
        if (entryCount == 1) {
            // the page is now empty
            return row;
        }
        removeRow(at);
        memoryChange();
        index.getPageStore().update(this);
        if (at == entryCount) {
            // the last row changed
            return getRow(at - 1);
        }
        // the last row didn't change
        return null;
    }

    @Override
    void freeRecursive() {
        index.getPageStore().logUndo(this, data);
        index.getPageStore().free(getPos());
    }

    @Override
    int getRowCount() {
        return entryCount;
    }

    @Override
    void setRowCountStored(int rowCount) {
        // ignore
    }

    @Override
    public void write() {
        writeData();
        index.getPageStore().writePage(getPos(), data);
    }

    private void writeHead() {
        data.reset();
        data.writeByte((byte) (Page.TYPE_BTREE_LEAF |
                (onlyPosition ? 0 : Page.FLAG_LAST)));
        data.writeShortInt(0);
        data.writeInt(parentPageId);
        data.writeVarInt(index.getId());
        data.writeShortInt(entryCount);
    }

    private void writeData() {
        if (written) {
            return;
        }
        if (!optimizeUpdate) {
            readAllRows();
        }
        writeHead();
        for (int i = 0; i < entryCount; i++) {
            data.writeShortInt(offsets[i]);
        }
        if (!writtenData || !optimizeUpdate) {
            for (int i = 0; i < entryCount; i++) {
                index.writeRow(data, offsets[i], rows[i], onlyPosition);
            }
            writtenData = true;
        }
        written = true;
        memoryChange();
    }

    @Override
    void find(PageBtreeCursor cursor, SearchRow first, boolean bigger) {
        int i = find(first, bigger, false, false);
        if (i > entryCount) {
            if (parentPageId == PageBtree.ROOT) {
                return;
            }
            PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
            next.find(cursor, first, bigger);
            return;
        }
        cursor.setCurrent(this, i);
    }

    @Override
    void last(PageBtreeCursor cursor) {
        cursor.setCurrent(this, entryCount - 1);
    }

    @Override
    void remapChildren() {
        // nothing to do
    }

    
Set the cursor to the first row of the next page.
Params:
cursor – the cursor/**
     * Set the cursor to the first row of the next page.
     *
     * @param cursor the cursor
     */
    void nextPage(PageBtreeCursor cursor) {
        if (parentPageId == PageBtree.ROOT) {
            cursor.setCurrent(null, 0);
            return;
        }
        PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
        next.nextPage(cursor, getPos());
    }

    
Set the cursor to the last row of the previous page.
Params:
cursor – the cursor/**
     * Set the cursor to the last row of the previous page.
     *
     * @param cursor the cursor
     */
    void previousPage(PageBtreeCursor cursor) {
        if (parentPageId == PageBtree.ROOT) {
            cursor.setCurrent(null, 0);
            return;
        }
        PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
        next.previousPage(cursor, getPos());
    }

    @Override
    public String toString() {
        return "page[" + getPos() + "] b-tree leaf table:" +
                index.getId() + " entries:" + entryCount;
    }

    @Override
    public void moveTo(Session session, int newPos) {
        PageStore store = index.getPageStore();
        readAllRows();
        PageBtreeLeaf p2 = PageBtreeLeaf.create(index, newPos, parentPageId);
        store.logUndo(this, data);
        store.logUndo(p2, null);
        p2.rows = rows;
        p2.entryCount = entryCount;
        p2.offsets = offsets;
        p2.onlyPosition = onlyPosition;
        p2.parentPageId = parentPageId;
        p2.start = start;
        store.update(p2);
        if (parentPageId == ROOT) {
            index.setRootPageId(session, newPos);
        } else {
            PageBtreeNode p = (PageBtreeNode) store.getPage(parentPageId);
            p.moveChild(getPos(), newPos);
        }
        store.free(getPos());
    }

    @Override
    protected void memoryChange() {
        if (!PageBtreeIndex.isMemoryChangeRequired()) {
            return;
        }
        int memory = Constants.MEMORY_PAGE_BTREE + index.getPageStore().getPageSize();
        if (rows != null) {
            memory += getEntryCount() * (4 + Constants.MEMORY_POINTER);
            for (int i = 0; i < entryCount; i++) {
                SearchRow r = rows[i];
                if (r != null) {
                    memory += r.getMemory();
                }
            }
        }
        index.memoryChange(memory >> 2);
    }

}