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