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 java.io.*;

/**
 * Implementation of a BtreePage with fixed length keys and fixed length data.
 *
 * @author	Dana Bergen
 * @version	1.0
 */
public class FixedKeyPage extends BtreePage {

    int		keyLength;	// cached here for easy access

    /**
     * Initialize a newly-instantiated or recycled FixedKeyPage. 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 {

        super.init(btree, pageId, pageBuffer, isNew);
	keyLength = btree.keyInfo.getLength();
    }

    /**
     * Returns the number of entries currently on this page.
     *
     * @return	number of entries on this page
     */
    int numEntries() {
        return (freeStart  - headerLength)/(keyLength + dataLength);
    }

    /**
     * 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 headerLength + (entryNum * (keyLength + dataLength));
    }

    /**
     * Returns the length of a specified entry's key.
     *
     * @param entryNum	entry number
     *
     * @return	length of entryNum's key
     */
    int keyLength(int entryNum) {
        return keyLength;
    }
    
    /**
     * 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, keyOffset(entryNum) + keyLength,
				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];
	System.arraycopy(pageBuffer, keyOffset(entryNum), key, 0, keyLength);
	return key;
    }

    /*
     * 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 offset;

        pageSource.dirtyPage(this);

        if (btree.pageSize - freeStart >= entry.length()) {
	    insertHere(entry, entryNum, resultPosition);
	    return null;
	} else {
	    return split(entry, entryNum, resultPosition);
	}
    }

    /*
     * 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);
        int offset = keyOffset(entryNum) + keyLength;
	System.arraycopy(entry.data, 0, pageBuffer, offset, 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;
    }
    
    private void insertHere(BtreeEntry entry, int entryNum, SearchResult resultPosition) {

        int offset;

        
        
	offset = keyOffset(entryNum);
	if (offset != freeStart) {
	    /* Shift entries down to make room for this one */
	    System.arraycopy(pageBuffer, offset, 
		    pageBuffer, offset + entry.length(),
		    freeStart - offset);
	}
	System.arraycopy(entry.key, 0, pageBuffer, offset, keyLength);
	System.arraycopy(entry.data, 0, 
				pageBuffer, offset+keyLength, dataLength);
	freeStart += keyLength + dataLength;
        
        if (resultPosition != null) {
            resultPosition.entryNum = entryNum;
            resultPosition.matched = true;
            resultPosition.page = this;
            resultPosition.skipCount = 0;
        }
    }

    /**
     * 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 firstEntry, int lastEntry) throws StorageException {

        int startOffset, endOffset;
	
	pageSource.dirtyPage(this);
	
	startOffset = keyOffset(firstEntry);
	endOffset = keyOffset(lastEntry+1);
	if (freeStart != endOffset) {
	    System.arraycopy(pageBuffer, endOffset, pageBuffer, startOffset,
				freeStart - endOffset);
	}
	freeStart -= endOffset - startOffset;
    }

    /**
     * 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 left, BtreePage right, BtreeEntry entry,
    			int entryNum, SearchResult resultPosition) { 
    
	int 	entryLength;
	int 	offset;
	int 	midpoint;
        int     half;
	int 	copyLength;
	boolean insertLeft;
	byte[]	rightKey;

	offset = keyOffset(entryNum);
	entryLength = keyLength + dataLength;
        half = numEntries()/2;
	midpoint = headerLength + half*entryLength;
	insertLeft = offset < midpoint;
	
	// Move second half of entries to right page.
	if (insertLeft) {
	    copyLength = this.freeStart - midpoint;
	} else {
	    // First just copy entries up to the insert point
	    copyLength = offset - midpoint;
	}
        
        // record position of inserted entry
        if (resultPosition != null) {
            resultPosition.matched = true;
            resultPosition.skipCount = 0;
            if (insertLeft) {
                resultPosition.page = left;
                resultPosition.entryNum = entryNum;
            } else {
                resultPosition.page = right;
                resultPosition.entryNum = entryNum - half;
            }
        }
        
	if (copyLength > 0) {
	    System.arraycopy(this.pageBuffer, midpoint, right.pageBuffer, 
			right.freeStart, copyLength);
	    right.freeStart += copyLength;
	}
	if (!insertLeft) {
	    System.arraycopy(entry.key, 0, right.pageBuffer, right.freeStart, 
	    							keyLength);
	    right.freeStart += keyLength;
	    System.arraycopy(entry.data, 0, right.pageBuffer, right.freeStart,
	    							dataLength);
	    right.freeStart += dataLength;
	    if (this.freeStart != offset) {
	        System.arraycopy(this.pageBuffer, offset, right.pageBuffer, 
			right.freeStart, this.freeStart - offset);
	        right.freeStart += this.freeStart - offset;
	    }
	}
	
	// Move first half of entries to left page, if left page is new.
	// Either way, insert the new entry if it belongs here.
	if (left != this) {
	    if (insertLeft) {
		copyLength = offset - headerLength;
	    } else {
		copyLength = midpoint - headerLength;
	    } 
	    if (copyLength > 0) {
	        System.arraycopy(this.pageBuffer, headerLength, 
				left.pageBuffer, left.freeStart, copyLength);
	    }
	}

	if (insertLeft) {
	    if (midpoint != offset) {
	        System.arraycopy(this.pageBuffer, offset, left.pageBuffer, 
			offset+entryLength, midpoint - offset);
	    }
	    System.arraycopy(entry.key, 0, left.pageBuffer, offset, keyLength);
	    System.arraycopy(entry.data, 0, left.pageBuffer, offset + keyLength, dataLength);
	    left.freeStart = midpoint + entryLength;
	} else {
	    left.freeStart = midpoint;
	}
	if (left != this) {
	    // All entries were moved off of this page
	    this.freeStart = headerLength;
	}
	rightKey = new byte[keyLength];
	System.arraycopy(right.pageBuffer, headerLength, rightKey, 0, keyLength);
	return rightKey;
    }
}
... 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.