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

/**
 * These pages contain keys which are too big to be handled normally.
 * Each BigKeyPage contains a single key or a portion of a single key,
 * and possibly the data associated with the key.  All of the BigKeyPages
 * are in a single chain attached to the root (i.e., root.nextPage points to
 * the first BigKeyPage).  They are maintained in key order.
 *
 * The first page for a given key contains the full key length in keyLength.
 * If the key doesn't fit on a single page it is continued on subsequent pages.
 * If the data fits completely on the same page as the last portion of the key,
 * it is put there; otherwise, it is put on a separate page.
 *
 * When a big key record gets deleted, the pages are removed from the chain
 * and the space is never reused.
 *
 * This is not a very efficient implementation because we don't really expect
 * it to be used (it gets used if a key is longer than 670 bytes).
 *
 * @author	Dana Bergen
 * @version	1.0
 */
public class BigKeyPage extends BtreePage {

    private int	keyLength;	

    public BigKeyPage() {}

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

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

        super.init(btree, pageId, pageBuffer, isNew);
	if (isNew) {
	    keyLength = 0;
	    flags = 0;
	} else {
	    /* keyLength is stored in the same slot as freeStart which
	     * is not used by BigKeyPage
	     */
	    keyLength = freeStart;
	}
    }

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

	freeStart = keyLength;
	super.store();
    }

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

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

    /**
     * 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) throws StorageException {

	byte[] data = new byte[dataLength];
	int pageSpace = btree.pageSize - headerLength;

	if ((keyLength + dataLength) < pageSpace) {
	    System.arraycopy(pageBuffer, headerLength + keyLength,
				data, 0, dataLength);
	} else {
	    SearchResult location = getDataLocation();
	    System.arraycopy(location.page.pageBuffer, location.entryNum,
				data, 0, dataLength);
	    if (location.page != this) {
		pageSource.unpinPage(location.page);
	    }
	}
	return data;
    }

    private SearchResult getDataLocation() throws StorageException {

	BtreePage current;
	byte[] next;
	int left;
	int pageSpace = btree.pageSize - headerLength;

	/* Find the last page of this key */
	current = this;
	left = keyLength;
	while (left > pageSpace) {
	    left -= pageSpace;
	    next = current.nextPage;
	    if (current != this) {
		pageSource.unpinPage(current);
	    }
	    current = pageSource.getPage(next, btree);
	}
	if ((left + dataLength) <= pageSpace) {
	    /* The data is on the current page */
	    return new SearchResult(true, headerLength+left, current);
	} else {
	    /* The data is on the next page */
	    next = current.nextPage;
	    if (current != this) {
		pageSource.unpinPage(current);
	    }
	    current = pageSource.getPage(next, btree);
	    return new SearchResult(true, headerLength, current);
	}
    }
    /**
     * Returns the key for the specified entry.
     *
     * @param entryNum entry number
     *
     * @return	new byte array containing the key at entryNum
     */
    byte[] getKey(int entryNum) throws StorageException {

	byte[] next;
	byte[] key = new byte[keyLength];
	int pageSpace = btree.pageSize - headerLength;

	if (keyLength < pageSpace) {
	    System.arraycopy(pageBuffer, headerLength,
				key, 0, keyLength);
	} else {
	    BtreePage page = this;
	    int left = keyLength;
	    while (left > pageSpace) {
	        System.arraycopy(page.pageBuffer, headerLength,
				key, keyLength - left, pageSpace);
	        left -= pageSpace;
		next = page.nextPage;
		if (page != this) {
		    pageSource.unpinPage(page);
		}
		page = pageSource.getPage(next, btree);
	    }
	    if (left > 0) {
	        System.arraycopy(page.pageBuffer, headerLength,
				key, keyLength - left, left);
	    }
	    if (page != this) {
		pageSource.unpinPage(page);
	    }
	}
	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 {

	SearchResult location;

        pageSource.dirtyPage(this);
	location = getDataLocation();
	if (location.page != this) {
	    pageSource.dirtyPage(location.page);
	}
	System.arraycopy(entry.data, 0, location.page.pageBuffer, 
			 location.entryNum, entry.data.length);
	if (location.page != this) {
	    pageSource.unpinPage(location.page);
	}
        
        // record position of inserted entry
        if (resultPosition != null) {
            resultPosition.matched = true;
            resultPosition.skipCount = 0;            
            resultPosition.page = this;
            resultPosition.entryNum = entryNum;
        }
        
	return null;
    }

    /*
     * Inserts an entry at the specified location.
     *
     * @param entry BtreeEntry to be inserted
     * @param entryNum 	0 if entry should be inserted before this one
     * 			1 if we're pointing to the last entry, and this entry
     *			  should be inserted after it
     *
     */
    BtreeEntry insert(BtreeEntry entry, int entryNum, SearchResult resultPosition) 
    				throws StorageException {

	BigKeyPage current, previous, newNext;
	BtreePage newPrevious;
	byte[] next;
	int left;
	int pageSpace = btree.pageSize - headerLength;

	if (keyLength == 0) {
	    /* This is the first BigKeyPage and it's already linked */
	    current = this;
	    pageSource.dirtyPage(current);
	    newNext = null;
	} else {
	    /* Create the first new page for the new entry */
	    current = pageSource.newBigKeyPage(btree);
	    if (entryNum == 0) {
		/* Insert before this page */
	        newPrevious = pageSource.getPage(this.previousPage, btree);
		newNext = this;
		pageSource.dirtyPage(this);
	    } else {
		/* Insert at end of chain */
		newNext = null;
		newPrevious = this;
		next = newPrevious.nextPage;
		while (!pageSource.isNoPage(next)) {
		    if (newPrevious != this) {
		        pageSource.unpinPage(newPrevious);
		    }
		    newPrevious = pageSource.getPage(next, btree);
		    next = newPrevious.nextPage;
		}
	    }
	    pageSource.dirtyPage(newPrevious);
	    linkNewPage(current, newPrevious, newNext);
	    pageSource.unpinPage(newPrevious);
	}

        // record position of inserted entry
        if (resultPosition != null) {
            resultPosition.matched = true;
            resultPosition.skipCount = 0;            
            resultPosition.page = current;
            resultPosition.entryNum = entryNum; // [PENDING]
        }
        
	current.keyLength = entry.key.length;

	left = entry.key.length;
	while (left > pageSpace) {
	    System.arraycopy(entry.key, entry.key.length - left, 
	    			current.pageBuffer, headerLength, pageSpace);
	    left -= pageSpace;
	    previous = current;
	    current = pageSource.newBigKeyPage(btree);
	    linkNewPage(current, previous, newNext);
	    if (previous != this) {
		pageSource.unpinPage(previous);
	    }
	}
	if (left > 0) {
	    System.arraycopy(entry.key, entry.key.length - left, 
	    			current.pageBuffer, headerLength, left);
	}
	if ((left + dataLength) > pageSpace) {
	    previous = current;
	    current = pageSource.newBigKeyPage(btree);
	    linkNewPage(current, previous, newNext);
	    if (previous != this) {
		pageSource.unpinPage(previous);
	    }
	    left = 0;
	}
	System.arraycopy(entry.data, 0, current.pageBuffer, headerLength + left,
							dataLength);
	if (current != this) {
	    pageSource.unpinPage(current);
	}
	if ((newNext != null) && (newNext != this)) {
	    pageSource.unpinPage(newNext);
	}
	return null;
    }

    private void linkNewPage(BtreePage newPage, BtreePage left, 
    				BtreePage right) {
	System.arraycopy(left.pageId, 0, newPage.previousPage, 0,
					    left.pageId.length);
	System.arraycopy(left.nextPage, 0, newPage.nextPage, 0,
					    left.pageId.length);
	System.arraycopy(newPage.pageId, 0, left.nextPage, 0,
					    newPage.pageId.length);
	if (right != null) {
	    System.arraycopy(newPage.pageId, 0, right.previousPage, 0,
						newPage.pageId.length);
	}
    }

    /**
     * Deletes an entry or range of entries from this page.
     *
     * @param	first	ignored
     * @param	last	ignored
     */

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

	BtreePage next, previous, current;
	int pageSpace = btree.pageSize - headerLength;
	int left = keyLength;

	current = this;
	previous = pageSource.getPage(this.previousPage, btree);
	pageSource.dirtyPage(previous);
	while (left > pageSpace) {
	    left -= pageSpace;
	    next = pageSource.getPage(current.nextPage, btree);
	    if (current != this) {
		pageSource.unpinPage(current);
	    }
	    current = next;
	}
	if ((left + dataLength) > pageSpace) {
	    /* The data is on the next page */
	    next = pageSource.getPage(current.nextPage, btree);
    	    pageSource.unpinPage(current);
	    current = next;
	}
	/* current is the last page to be deleted */
	System.arraycopy(current.nextPage, 0, previous.nextPage, 0,
					current.nextPage.length);
	if (!pageSource.isNoPage(current.nextPage)) {
	    next = pageSource.getPage(current.nextPage, btree);
	    pageSource.dirtyPage(next);
	    System.arraycopy(previous.pageId, 0, next.previousPage, 0,
					previous.pageId.length);
	    pageSource.unpinPage(next);
	}
	if (previous.isRoot() && pageSource.isNoPage(previous.nextPage)) {
	    btree.unsetHasBigKeys();
	}
	pageSource.unpinPage(previous);
	if (current != this) {
	    pageSource.unpinPage(current);
	}
    }

    /*
     * Do nothing.
     */
    byte[] splitEntries(BtreePage leftBP, BtreePage rightBP, BtreeEntry entry,
    			int newEntryNum, SearchResult resultPosition) throws StorageException {
	return null;
    }

    /**
     * Search for the key starting from this page. We do this in a very
     * inefficient way.
     */
    SearchResult searchBigKeys(byte[] key) throws StorageException {

	BigKeyPage current, next;
        byte[] currentKey;
	SearchResult result;
	byte compare;

	next = this;
	result = null;
	do {
	    current = next;
	    currentKey = current.getKey(0);
	    compare = btree.keyInfo.compare(key, currentKey, 0, currentKey.length);
	    if (compare == EntryTypeInfo.EQUAL) {
	        result = new SearchResult(true, 0, current);
	    } else if (compare == EntryTypeInfo.LESS) {
	        result = new SearchResult(false, 0, current);
	    } else {
	        next = current.getNextKeyStart();
		if (current != this) {
		    pageSource.unpinPage(current);
		}
	    }
	} while ((result == null) && (next != null));

	if (result == null) {
	    result = new SearchResult(false, 1, current);
	}
	return result;
    }

    /*
     * Get the next entry, starting from the passed in result.  The
     * result is updated to point to the next entry and indicate whether
     * it matched the key. If key is null, it is considered a match as long
     * as any record was found.
     *
     * If testOnly is true, result.matched is updated but result.page and
     * result.entry are left unchanged.
     */
    static void getNext(byte[] key, SearchResult result, boolean testOnly) 
	      				throws StorageException {
 
 	BigKeyPage page;
	byte[] currentKey;
	Btree btree = result.page.btree;
	
	if (result.entryNum == -1) {
	    page = (BigKeyPage)result.page;
	    if (!testOnly) {
	        result.entryNum = 0;
	    }
	} else {
	    page = ((BigKeyPage)result.page).getNextKeyStart();
	}
	if (page == null) {
	    result.matched = false;
	    result.entryNum = 1;
	    return;
	}
	
	if (key != null) {
	    currentKey = page.getKey(0);
	    if (btree.keyInfo.compare(key, currentKey, 0, currentKey.length)
	    		== EntryTypeInfo.EQUAL) {
		result.matched = true;
	    } else {
	        result.matched = false;
	    }
	} else {
	    result.matched = true;
	}
	if (!testOnly) {
	    result.page = page;
	}
    }

    BigKeyPage getNextKeyStart() throws StorageException {

	BigKeyPage next, currentDataPage;

	currentDataPage = (BigKeyPage) getDataLocation().page;
	if (!pageSource.isNoPage(currentDataPage.nextPage)) {
	    next = (BigKeyPage) pageSource.getPage(currentDataPage.nextPage, 
	    								btree);
	} else {
	    next = null;
	}
	if (currentDataPage != this) {
	    pageSource.unpinPage(currentDataPage);
	}
	return next;
    }

    /*
     * Gets the previous entry location.  This only operates within the
     * big key chain, i.e., calling getPrevious when positioned at the first
     * big key entry will not backup to the last normal entry.  Instead,
     * it will return the location of the first big key, matched = false,
     * and set entryNum to -1.
     */
    static void getPrevious(byte[] key, SearchResult result, boolean testOnly) 
	      				throws StorageException {
 	BigKeyPage page;
	byte[] currentKey;
	Btree btree = result.page.btree;
	
	page = ((BigKeyPage)result.page).getPreviousKeyStart();
	if (page == null) {
	    if (!testOnly) {
	        result.entryNum = -1;
	    }
	    result.matched = false;
	    return;
	}
	
	if (key != null) {
	    currentKey = page.getKey(0);
	    if (btree.keyInfo.compare(key, currentKey, 0, currentKey.length)
	    		== EntryTypeInfo.EQUAL) {
		result.matched = true;
	    } else {
	        result.matched = false;
	    }
	} else {
	    result.matched = true;
	}
	if (!testOnly) {
	    result.page = page;
	}
    }

    BigKeyPage getPreviousKeyStart() throws StorageException {

        int currentLength = 0;
	BtreePage current, previous;
	
	current = this;
	do {
	    previous = pageSource.getPage(current.previousPage, btree);
	    if (current != this) {
	        pageSource.unpinPage(current);
	    }
	    current = previous;
	    if (!(current instanceof BigKeyPage)) {
	        /* we're back at the root */
	        pageSource.unpinPage(current);
		current = null;
	    } else {
	        currentLength = ((BigKeyPage)current).keyLength;
	    }
	} while ((current != null) && (currentLength == 0));

	return (BigKeyPage)current;
    }

    /*
     * Make the first BigKeyPage and link it to the root.
     */
    static BtreePage makeFirst(BtreePage root, BtreePageSource pageSource) 
    						throws StorageException {

	BtreePage newPage;

	newPage = pageSource.newBigKeyPage(root.btree);
	System.arraycopy(newPage.pageId, 0, root.nextPage, 0, 
					    newPage.pageId.length);
	System.arraycopy(root.pageId, 0, newPage.previousPage, 0, 
					    newPage.pageId.length);
	root.btree.setHasBigKeys();
	return newPage;
    }
    
    void dumpLevel(PrintWriter out) throws StorageException {
    
        BigKeyPage current, next;
	current = this;
        do {
	    current.dumpPage(out);
	    next = current.getNextKeyStart();
	    if (current != this) {
	        pageSource.unpinPage(current);
	    }
	    current = next;
	} while (current != null);
    }

    public void dumpPageHeader(PrintWriter out) {
        super.dumpPageHeader(out);
	out.println("Key length: " + keyLength + "\n");
    }

    public void dumpPageEntries(PrintWriter out) throws StorageException {

        out.println("\nPage entries:\n\n");

        out.print(btree.keyInfo.fromBuffer(getKey(0)) + ", ");
	out.println(btree.dataInfo.fromBuffer(getData(0)));
    }
}
... 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.