alvinalexander.com | career | drupal | java | mac | mysql | perl | scala | uml | unix  

What this is

This file is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Other links

The source code

/*
 *                 Sun Public License Notice
 * 
 * The contents of this file are subject to the Sun Public License
 * Version 1.0 (the "License"). You may not use this file except in
 * compliance with the License. A copy of the License is available at
 * http://www.sun.com/
 * 
 * The Original Code is NetBeans. The Initial Developer of the Original
 * Code is Sun Microsystems, Inc. Portions Copyright 1997-2001 Sun
 * Microsystems, Inc. All Rights Reserved.
 */
package org.netbeans.mdr.persistence.btreeimpl.btreeindex;
import org.netbeans.mdr.persistence.*;
import org.netbeans.mdr.persistence.btreeimpl.btreestorage.*;    /* for Converter */
import java.io.*;

/**
 * Implementation of a BtreePage with variable length keys and fixed length 
 * data. 
 */
 /*The format of a page in the page buffer is as follows:
 *
 * The BtreePage header fields are followed by a series of 2-byte integers
 * Each of these is the offset of an entry on the page.  The entries are
 * maintained in key order, and each entry consists of its key followed
 * by its data value.  Entries start from the end of the page and grow
 * backwards towards the offset table.
 *
 *                    freeStart
 *                    |
 *                    V
 * ------------------------------------------------------
 * | header | offsets | free space                      |
 * |                    | used space                    |
 * ------------------------------------------------------
 * 			^				^
 *			|				|
 *			offsets[0]			offsets[nextOffset]
 *							= page size
 *
 * The header fields and offsets are not updated in the page buffer until
 * the page is serialized.
 */
public class VarKeyPage extends BtreePage {

    private int[]	offsets;
    private int	nextOffset;	// index into offsets array
    private static final int SIZE_OF_OFFSET = SIZE_OF_SHORT;

    /**
     * Initialize a newly-instantiated or recycled VarKeyPage. Note that the
     * isNew parameter pertains to whether a new page is being added to the
     * btree, not to whether this BtreePage object is new or recycled.
     *
     * @param	btree		btree to which this page belongs
     * @param	pageId		page ID in byte array
     * @param	pageBuffer	page buffer
     * @param	isNew		is this page new to the btree
     */
    public void init(Btree btree, byte[] pageId, byte[] pageBuffer, 
    				boolean isNew) throws StorageException {

	int maxOffsets;

	if (initialized) {
	    /* This page was found in cache and doesn't need initialization */
	    return;
	}

        super.init(btree, pageId, pageBuffer, isNew);

	/* Allocate offsets table.  Only the entries actually in use
	 * will be written to the page buffer, so it doesn't matter
	 * if we allocate this bigger than necessary. We don't have
	 * the information yet to do a better estimate.
	 *
	 * No need to allocate if this is a recycled page.
	 */
	if (offsets == null) {
	    maxOffsets = (btree.pageSize - headerLength)/SIZE_OF_OFFSET;
	    offsets = new int[maxOffsets];
	}
	initOffsets(isNew);
    }

    private void initOffsets(boolean isNew) {

	int pageOffset = headerLength;

	if (isNew) {
	    nextOffset = 0;
	} else {
	    nextOffset = (freeStart - headerLength)/SIZE_OF_OFFSET;
	    for (int i = 0; i < nextOffset; i++) {
		offsets[i] = (int) Converter.readShort(pageBuffer, 
							pageOffset);
		pageOffset += 2;
	    }
	}
	offsets[nextOffset] = btree.pageSize;
    }

    /**
     * Write VarKeyPage header data to the page buffer.
     */
    public void store() {

	int pageOffset = headerLength;

	super.store();

	if (nextOffset > 0) {
	    for (int i = 0; i < nextOffset; i++) {
		Converter.writeShort(pageBuffer, pageOffset, (short)offsets[i]);
		pageOffset += 2;
	    }
	}
    }

    /**
     * Returns the number of entries currently on this page.
     *
     * @return	number of entries on this page
     */
    int numEntries() {
        return nextOffset;
    }

    /**
     * Returns the offset in the page where a specified entry's key is located.
     *
     * @param	entryNum	entry number
     *
     * @return	offset of entryNum's key
     */
    int keyOffset(int entryNum) {
        return offsets[entryNum];
    }

    /**
     * Returns the length of a specified entry's key.
     *
     * @param entryNum	entry number
     *
     * @return	length of entryNum's key
     */
    int keyLength(int entryNum) {
        if (entryNum != nextOffset) {
            return offsets[entryNum+1] - offsets[entryNum] - dataLength;
	} else {
	    // this should never happen
	    return 0;
	}
    }

    /**
     * Returns the data value for the specified entry.
     *
     * @param entryNum entry number
     *
     * @return	new byte array containing the data at entryNum
     */
    byte[] getData(int entryNum) {

	byte[] data = new byte[dataLength];
	System.arraycopy(pageBuffer, offsets[entryNum+1] - dataLength,
				data, 0, dataLength);
	return data;
    }

    /**
     * Returns the key for the specified entry.
     *
     * @param entryNum entry number
     *
     * @return	new byte array containing the key at entryNum
     */
    byte[] getKey(int entryNum) {

	byte[] key = new byte[keyLength(entryNum)];
	System.arraycopy(pageBuffer, offsets[entryNum], key, 0, key.length);
	return key;
    }

    /*
     * Replaces the entry at the specified location with the passed-in entry.
     * Since data is fixed length, we know it will fit.
     *
     * @param entry BtreeEntry to be inserted
     * @param entryNum location where entry is to be inserted
     *
     * @return	Always returns null
     */

    BtreeEntry replace(BtreeEntry entry, int entryNum, SearchResult resultPosition) throws StorageException {

        pageSource.dirtyPage(this);
	System.arraycopy(entry.data, 0, 
			 pageBuffer, offsets[entryNum+1] - entry.data.length,
			 entry.data.length);
        
        // record position of inserted entry
        if (resultPosition != null) {
            resultPosition.matched = true;
            resultPosition.skipCount = 0;            
            resultPosition.page = this;
            resultPosition.entryNum = entryNum;
        }
        
	// We didn't split so there is no parent entry to return
	return null;
    }

    /*
     * Inserts an entry at the specified location.
     *
     * @param entry BtreeEntry to be inserted
     * @param entryNum location where entry is to be inserted
     *
     * @return	If a split occurred, an entry to be inserted in this page's
     *		parent is returned; otherwise null is returned.
     */
    BtreeEntry insert(BtreeEntry entry, int entryNum, SearchResult resultPosition)
    				throws StorageException {

	int entriesStart;
	int entriesSplit;

        pageSource.dirtyPage(this);

	if (!haveSpaceForInsert(entry)) {
	    return split(entry, entryNum, resultPosition);
	} else {
	    entriesStart = offsets[0];
	    entriesSplit = offsets[entryNum];
	    shiftOffsets(this, entryNum, entry.length());
	    if (entryNum != 0) {
	        System.arraycopy(pageBuffer, entriesStart, 
	    		pageBuffer, entriesStart - entry.length(),
	    		entriesSplit - entriesStart);
	    }
	    System.arraycopy(entry.key, 0, pageBuffer, offsets[entryNum], 
	    		entry.key.length);
	    System.arraycopy(entry.data, 0, pageBuffer, 
	    		offsets[entryNum] + entry.key.length, 
	    		entry.data.length);
	    freeStart += SIZE_OF_OFFSET;
            
            if (resultPosition != null) {
                resultPosition.entryNum = entryNum;
                resultPosition.matched = true;
                resultPosition.page = this;
                resultPosition.skipCount = 0;
            }
	    return null;
	}
    }

    /**
     * Deletes an entry or range of entries from this page.
     *
     * @param	first	entry number of first entry to be deleted
     * @param	last	entry number of last entry to be deleted
     */

    void delete(int first, int last) throws StorageException {

        int startOffset, endOffset;
	int bytesDeleted;
	int numDeleted;

	pageSource.dirtyPage(this);

	startOffset = offsets[first];
	endOffset = offsets[last+1];
	bytesDeleted = endOffset - startOffset;
	numDeleted = last - first + 1;

	if (first != 0) {
	    System.arraycopy(pageBuffer, offsets[0], 
		    	 pageBuffer, offsets[0] + bytesDeleted,
			 startOffset - offsets[0]);
	}
	// Shift the offset entries up
	for (int i = last + 1; i <= nextOffset; i++) {
	    offsets[i - numDeleted] = offsets[i];
	}
	nextOffset -= numDeleted;
	freeStart -= numDeleted*SIZE_OF_OFFSET;

	// Update the offset entries for entries that got moved down
	if (first != 0) {
	    for (int i = 0; i < first; i++) {
	        offsets[i] += bytesDeleted;
	    }
	}
    }

    /**
     * Splits the entries on the current page between two pages, and inserts
     * an entry into its correct location on one of those pages. The left
     * page may be this page or it may be a different page.  The right page is
     * always a different page from this.
     *
     * @param	left	left page to move entries to (may be this page)
     * @param	right	right page to move entries to
     * @param	entry	BtreeEntry to be inserted 
     * @param	newEntryNum insert location relative to the current page
     *
     * @return	new byte array containing first key on right page
     */
    byte[] splitEntries(BtreePage leftBP, BtreePage rightBP, BtreeEntry entry,
    			int newEntryNum, SearchResult resultPosition) throws StorageException {

        int halfBytes;
	int splitEntryNum;
	int rightNewEntryNum;
	int spaceAvailable;
	int spaceNeeded;
	boolean insertLeft;
	int pageSize;		// save getting this repeatedly
	VarKeyPage left, right;
	int rightKeyLength;
	byte[] rightKey;

	left = (VarKeyPage) leftBP;
	right = (VarKeyPage) rightBP;
	pageSize = btree.pageSize;

	// Find the place to split at
	spaceAvailable = pageSize - headerLength;
	halfBytes = (spaceAvailable - nextOffset*SIZE_OF_OFFSET)/2;
	splitEntryNum = 0;
	while ((offsets[splitEntryNum] < halfBytes) 
		    && (splitEntryNum < nextOffset)) {
	    splitEntryNum++;
	}

	// If the new entry goes on the left page, make sure it will fit there.
	// If not, adjust the split point.
	if (newEntryNum < splitEntryNum) {
	    do {
	        spaceNeeded = splitEntryNum*SIZE_OF_OFFSET
	    		  + offsets[splitEntryNum] - offsets[0]
			  + entry.length() + SIZE_OF_OFFSET;
		if (spaceNeeded > spaceAvailable) {
		    splitEntryNum--;
		}
	    } while ((spaceNeeded > spaceAvailable) 
	    		&& (newEntryNum < splitEntryNum));
	}
	insertLeft = newEntryNum < splitEntryNum ? true : false;

        // record position of inserted entry
        if (resultPosition != null) {
            resultPosition.matched = true;
            resultPosition.skipCount = 0;
            if (insertLeft) {
                resultPosition.page = left;
                resultPosition.entryNum = newEntryNum;
            } else {
                resultPosition.page = right;
                resultPosition.entryNum = newEntryNum - splitEntryNum;
            }
        }
        
	if (!insertLeft) {
	    spaceNeeded = splitEntryNum*SIZE_OF_OFFSET
	    		  + pageSize - offsets[splitEntryNum]
			  + entry.length() + SIZE_OF_OFFSET;
	}
	
	// Move entries to right page. First copy offset table entries over, 
	// making the entry at splitEntryNum the first offset entry on the right
	// page. 
	for (int from = splitEntryNum, to = 0; from < nextOffset; 
							from++, to++) {
	    right.offsets[to] = this.offsets[from];
	}
	right.nextOffset = this.nextOffset - splitEntryNum;
	right.offsets[right.nextOffset] = btree.pageSize;
	right.freeStart = headerLength + right.nextOffset*SIZE_OF_OFFSET;

	if (insertLeft) {
	    // Copy all the entries starting at the split point.
	    System.arraycopy(this.pageBuffer, offsets[splitEntryNum], 
	    			right.pageBuffer, offsets[splitEntryNum], 
				pageSize - offsets[splitEntryNum]);
	} else {
	    // Adjust right page's offset table to accommodate new entry
	    rightNewEntryNum = newEntryNum - splitEntryNum; 
	    shiftOffsets(right, rightNewEntryNum, entry.length());
	    right.freeStart += SIZE_OF_OFFSET;

	    // Copy the entries preceding the insert point
	    if (newEntryNum != splitEntryNum) {
	        System.arraycopy(this.pageBuffer, this.offsets[splitEntryNum], 
	    		right.pageBuffer, right.offsets[0],
			this.offsets[newEntryNum] - this.offsets[splitEntryNum]);
	    }
	    // Copy the new entry
	    System.arraycopy(entry.key, 0, right.pageBuffer, 
	    		right.offsets[rightNewEntryNum], entry.key.length);
	    System.arraycopy(entry.data, 0, right.pageBuffer, 
	    		right.offsets[rightNewEntryNum] + entry.key.length,
	    		dataLength);

	    // Copy the entries following the insert point 
	    if (newEntryNum != nextOffset) {
	        System.arraycopy(this.pageBuffer, this.offsets[newEntryNum],
	    		right.pageBuffer, right.offsets[rightNewEntryNum + 1],
	    		pageSize - this.offsets[newEntryNum]);
	    }
	}

	// Now do the left page.  Note that in the following code, "this"
	// and "left" may or may not be the same page. If they are
	// different, the entries are moved from this to left.  Otherwise,
	// the effect is to move the entries to their new location on the
	// same page, being careful to move data in the right order to 
	// avoid clobbering data we still need.

	// save some values in case we're overwriting this page
	int bytesRemoved = pageSize - this.offsets[splitEntryNum];
	int splitPoint = this.offsets[splitEntryNum];
	int entriesStart = this.offsets[0];
	int insertPoint = this.offsets[newEntryNum];

	for (int i = 0; i < splitEntryNum; i++) {
	    left.offsets[i] = this.offsets[i] + bytesRemoved;
	}
	left.nextOffset = splitEntryNum;
	left.offsets[left.nextOffset] = pageSize;
	left.freeStart = headerLength + left.nextOffset*SIZE_OF_OFFSET;

	if (!insertLeft) {
	    System.arraycopy(this.pageBuffer, entriesStart, left.pageBuffer,
	    		left.offsets[0], splitPoint - entriesStart);
	} else {
	    // Adjust left page's offset table to accommodate new entry
	    shiftOffsets(left, newEntryNum, entry.length());
	    left.freeStart += SIZE_OF_OFFSET; 

	    // The chunks have to be copied in this order to be sure not to
	    // overwrite existing entries before they've been copied.
	    
	    // Copy the entries following the insert point 
	    if (insertPoint != splitPoint) {
	        System.arraycopy(this.pageBuffer, insertPoint,
	    		left.pageBuffer, left.offsets[newEntryNum + 1],
	    		splitPoint - insertPoint);
	    }
	    // Copy the entries preceding the insert point.  This chunk could
	    // get moved up or down depending on the relative sizes of
	    // bytesRemoved and the entry size.
	    if (insertPoint != entriesStart) {
	        System.arraycopy(this.pageBuffer, entriesStart,
	    		left.pageBuffer, left.offsets[0],
			insertPoint - entriesStart);
	    }

	    // Copy the new entry
	    System.arraycopy(entry.key, 0, left.pageBuffer, 
	    		left.offsets[newEntryNum], entry.key.length);
	    System.arraycopy(entry.data, 0, left.pageBuffer, 
	    		left.offsets[newEntryNum] + entry.key.length,
	    		dataLength);
	}

	if (left != this) {
	    this.nextOffset = 0;
	    this.freeStart = headerLength;
	    this.offsets[0] = pageSize;
	}	

	// Get key to insert to parent page
	rightKeyLength = right.keyLength(0);
	rightKey = new byte[rightKeyLength];
	System.arraycopy(right.pageBuffer, right.offsets[0], rightKey, 0, 
							rightKeyLength);
	return rightKey;
    }

    private void shiftOffsets(VarKeyPage page, int entryNum, int entryLength) {

	if (entryNum != page.nextOffset) {
	    // For the offsets following the entryNum, shift them all
	    // down one slot to make room for the new one.
	    for (int i = page.nextOffset; i > entryNum; i--) {
		page.offsets[i] = page.offsets[i-1];
	    }
	}
	page.nextOffset++;
	page.offsets[page.nextOffset] = btree.pageSize;

	// For the offsets up to and including the one at entryNum,
	// subtract entryLength from each offset to reflect that entry's
	// new location on the page.

	for (int i = entryNum; i >= 0; i--) {
	    page.offsets[i] -= entryLength;
	}
    }

    boolean haveSpaceForInsert(BtreeEntry entry) {

        int freeSpace = offsets[0] - freeStart;

	if ((entry.length() + SIZE_OF_OFFSET) <= freeSpace) {
	    return true;
	} else {
	    return false;
	}
    }

    public void dumpPageHeader(PrintWriter out) {

        super.dumpPageHeader(out);

	out.println("\nOffsets table:\n");

	for (int i = 0; i < nextOffset; i++) {
	    out.print(offsets[i] + " ");
	}
	out.println();
    }
}
... this post is sponsored by my books ...

#1 New Release!

FP Best Seller

 

new blog posts

 

Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.