|
What this is
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 |
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.