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.*;
/**
* Abstract class containing the main logic for searching and updating a Btree.
* It searches and updates the structure of the pages that make up the tree.
* Pages are obtained by calls on the associated BtreePageSource.
* Searching and updating of the entries on a given page is handled by the
* subclass for the specific page format.
*
* There are two types of normal pages: FixedKeyPage and VarKeyPage. A
* given btree will have either all FixedKeyPages or all VarKeyPages,
* depending on the key type. These are kept in a tree structure where
* leaf pages contain the actual data and intermediate pages contain
* pageIds of the pages on the level below.
*
* The exception to this is BigKeyPages, which may coexist with VarKeyPages
* in the same btree. These are used when a key is encountered whose length is
* such that the key plus its data would take up more than one-third the
* available space on a page (for a btree with MOFID data items this would
* be a key longer than 670 bytes). All BigKeyPages are kept on a single chain
* attached to the root on the right.
*
* @author Dana Bergen
* @version 1.0
*/
public abstract class BtreePage extends Object implements Streamable {
Btree btree; /* Btree to which this page belongs*/
BtreePageSource pageSource; /* obtained from Btree */
/*
* The pageBuffer contains all the entries for this page. The first
* headerLength bytes of the pageBuffer are reserved for the header fields.
* The header fields are read from the pageBuffer when it is instantiated
* and written to the pageBuffer when it is about to be stored persistently.
* During the life of an instantiated BtreePage object, header data is
* only updated in the object members, not in the PageBuffer.
*/
public byte[] pageBuffer;
/* Persistently stored page header fields */
public byte[] pageId; /* this page's ID */
byte[] nextPage; /* right sibling */
byte[] previousPage; /* left sibling */
short flags;
int freeStart; /* start of free space in page buffer */
/* flag values */
static final short BTREE_LEAF_PAGE = 0x01;
static final short BTREE_ROOT_PAGE = 0x02;
static final int SIZE_OF_SHORT = 2;
int dataLength; /* length of a data entry on this page */
int headerLength; /* depends on type of page and type of tree */
boolean initialized = false;
/* Object for passing around btree entries */
static class BtreeEntry extends Object {
byte[] key;
byte[] data;
BtreeEntry(byte[] key, byte[] data) {
this.key = key;
this.data = data;
}
BtreeEntry() {}
int length() {
return key.length + data.length;
}
}
private static class ParentEntry extends BtreeEntry {
int skipCount;
ParentEntry(BtreeEntry entry, int skipCount) {
key = entry.key;
data = entry.data;
this.skipCount = skipCount;
}
}
/*
* @param resultPosition if this parameter is not null, a new location of the inserted
* entry is recorded here
*/
abstract BtreeEntry insert(BtreeEntry entry, int entryNum, SearchResult resultPosition)
throws StorageException;
abstract BtreeEntry replace(BtreeEntry entry, int entryNum, SearchResult resultPosition)
throws StorageException;
abstract void delete(int first, int last) throws StorageException;
abstract byte[] getData(int entryNum) throws StorageException;
abstract byte[] getKey(int entryNum) throws StorageException;
abstract int numEntries();
abstract int keyOffset(int entryNum);
abstract int keyLength(int entryNum);
abstract byte[] splitEntries(BtreePage left, BtreePage right,
BtreeEntry entry, int entryNum, SearchResult resultPosition)
throws StorageException;
/**
* Construct an empty BtreePage. All the real work is done in init().
*/
public BtreePage() {
}
/**
* Initialize a newly-instantiated or recycled BtreePage. 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;
}
this.btree = btree;
this.pageSource = btree.pageSource;
headerLength = btree.pageIdLength*2 + SIZE_OF_SHORT*2;
/* If this is a recycled page we don't need to allocate the pageId's */
if (this.pageId == null) {
this.pageId = new byte[btree.pageIdLength];
nextPage = new byte[btree.pageIdLength];
previousPage = new byte[btree.pageIdLength];
}
System.arraycopy(pageId, 0, this.pageId, 0, pageId.length);
if (pageBuffer == null) {
throw new StoragePersistentDataException("Received null page buffer");
} else if (pageBuffer.length != btree.pageSize) {
throw new StoragePersistentDataException(
"Page buffer size " + pageBuffer.length +
" doesn't match expected page size " + btree.pageSize);
}
this.pageBuffer = pageBuffer;
if (isNew) {
pageSource.setNoPage(nextPage);
pageSource.setNoPage(previousPage);
freeStart = headerLength;
makeLeaf();
} else {
readHeader(pageBuffer);
}
initialized = true;
}
/*
* Initialize the BtreePage's attributes using the values in the
* header portion of the page buffer.
*/
private void readHeader(byte[] pageBuffer) {
int pageIdLength;
int offset = 0;
pageIdLength = pageId.length;
for (int i=0; i < pageIdLength; i++) {
nextPage[i] = Converter.readByte(pageBuffer, offset++);
}
for (int i=0; i < pageIdLength; i++) {
previousPage[i] = Converter.readByte(pageBuffer, offset++);
}
flags = Converter.readShort(pageBuffer, offset);
offset += 2;
freeStart = (int) Converter.readShort(pageBuffer, offset);
if (isLeaf()) {
makeLeaf();
} else {
makeInternal();
}
}
/**
* Write BtreePage header data to the page buffer.
*/
public void store() {
/*
* We don't need synchronization because this will only happen
* at commit, or when the object is known to not be in use.
*/
int pageIdLength = pageId.length;
int offset = 0;
System.arraycopy(nextPage, 0, pageBuffer, offset, pageIdLength);
offset += pageIdLength;
System.arraycopy(previousPage, 0, pageBuffer, offset, pageIdLength);
offset += pageIdLength;
Converter.writeShort(pageBuffer, offset, flags);
offset += 2;
short shortFreeStart = (short) freeStart;
Converter.writeShort(pageBuffer, offset, shortFreeStart);
}
/**
* (Streamable Interface) Populate the pageBuffer from the InputStream.
* The page is not usable until init() has also been called. This is
* done in pageSource.getPage because it requires a reference to the Btree.
*
* @param in InputStream to read from
*/
public void read(InputStream in) throws StorageException {
try {
pageBuffer = new byte[in.available()];
in.read(pageBuffer);
} catch (IOException e) {
throw new StorageIOException(e);
}
}
/**
* (Streamable Interface) Write this page to the OutputStream.
*
* @param out OutputStream to write page to
*/
public void write(OutputStream out) throws StorageException {
/*
* We don't need synchronization because this will only happen
* at commit, or when the object is known to not be in use.
*/
store();
try {
out.write(pageBuffer);
} catch (IOException e) {
throw new StorageIOException(e);
}
}
public void uninit() {
initialized = false;
}
/**
* Add an entry to the btree, navigating down from this page.
*
* @param key byte array containing key
* @param data byte array containing data
*/
public void put(byte[] key, byte[] data, byte operation, int index)
throws StorageException {
if (!isBigKey(key)) {
put(new BtreeEntry(key, data), operation, index, null);
} else {
putBigKey(new BtreeEntry(key, data), operation, index, null);
}
}
/**
* Add an entry to the btree, navigating down from this page.
*
* @param key byte array containing key
* @param data byte array containing data
* @param resultPosition location of inserted element is recorded in case this parameter is not null
* and the oparation to perform is insert (add).
*/
public void put(byte[] key, byte[] data, byte operation, int index, SearchResult resultPosition)
throws StorageException {
if (!isBigKey(key)) {
put(new BtreeEntry(key, data), operation, index, resultPosition);
} else {
putBigKey(new BtreeEntry(key, data), operation, index, resultPosition);
}
}
/**
* Add an entry to the btree, navigating down from this page. put()
* recursively calls itself on its children until a leaf page is reached.
* The entry is then inserted. Page splits may result, in which case put()
* may return a BtreeEntry to be inserted to its parent.
*
* @param entry BtreeEntry to be inserted
*
* @return ParentEntry to be inserted to this page's parent
* due to a page split
*/
ParentEntry put(BtreeEntry entry, byte operation, int index, SearchResult resultPosition)
throws StorageException {
SearchResult searchResult;
ParentEntry parentEntry;
searchResult = searchPage(entry.key);
if (isLeaf()) {
BtreePage page = searchResult.page;
parentEntry = page.putHere(operation, searchResult, entry, index, resultPosition);
if (searchResult.page != page) {
pageSource.unpinPage(searchResult.page);
}
if (page != this) {
pageSource.unpinPage(page);
}
} else {
BtreePage child;
ParentEntry myEntry;
child = searchResult.page.getChild(searchResult);
myEntry = child.put(entry, operation, index, resultPosition);
pageSource.unpinPage(child);
if (myEntry == null) {
parentEntry = null;
} else {
parentEntry = insertParentEntry(myEntry, searchResult);
}
}
return parentEntry;
}
/*
* After a split, insert an entry in the appropriate parent page pointing
* to the newly created page. In a MultivaluedOrderedBtree, when doing an
* indexed insert we may have traversed sibling pages, so the original
* parent location may not be the correct place for this insert. In that
* case we need to move forward one entry at this level for each page
* that was traversed at the child level.
*/
private ParentEntry insertParentEntry(ParentEntry entry,
SearchResult location) throws StorageException {
ParentEntry newParentEntry = null;
BtreeEntry splitEntry = null;
/*
* entry.skipCount is the number of entries to skip at this level.
* If there was an exact match at this level, add 1 to skip past
* the original leftmost entry for this key.
*/
if (location.matched) {
entry.skipCount++;
}
if (entry.skipCount > 0) {
findNth(location, null, entry.skipCount, true);
}
/*
* Don't add a new page entry 0 here,
* or the parent key pointing to this page may
* become incorrect. Make it the last entry
* of the previous page instead.
*/
if (location.entryNum == 0) {
getPrevious(entry.key, location);
location.entryNum++;
}
splitEntry = location.page.insert(entry, location.entryNum, null);
/*
* location.skipCount now contains the number of entries to be skipped
* at our parent's level.
*/
if (splitEntry != null) {
newParentEntry = new ParentEntry(splitEntry, location.skipCount);
}
return newParentEntry;
}
private ParentEntry putHere(byte operation, SearchResult location,
BtreeEntry entry, int index, SearchResult resultPosition) throws StorageException {
ParentEntry parentEntry = null;
BtreeEntry splitEntry;
SearchResult testLocation;
switch (operation) {
case Btree.ADD:
if (location.matched && btree.uniqueKeys) {
btree.failed = true;
} else {
if (location.matched && btree.uniqueValues) {
testLocation = new SearchResult(location.matched,
location.entryNum, location.page);
btree.failed = findMatchingData(testLocation, entry.key,
entry.data);
if ((testLocation.page != location.page)
&& (testLocation.page != this)) {
pageSource.unpinPage(testLocation.page);
}
}
if (!btree.failed && (index > 0)) {
btree.failed = !findNth(location, entry.key,
index, true);
}
if (!btree.failed) {
splitEntry = location.page.insert(entry,
location.entryNum, resultPosition);
if (splitEntry != null) {
parentEntry = new ParentEntry(splitEntry,
location.skipCount);
}
}
}
break;
case Btree.REPLACE:
if (!location.matched) {
btree.failed = true;
} else {
if (index > 0) {
btree.failed = !findNth(location, entry.key,
index, false);
}
if (!btree.failed) {
splitEntry = location.page.replace(entry,
location.entryNum, resultPosition);
if (splitEntry != null) {
parentEntry = new ParentEntry(splitEntry,
location.skipCount);
}
}
}
break;
case Btree.REPLACE_IF_EXISTS:
if (!location.matched) {
splitEntry = insert(entry, location.entryNum, resultPosition);
} else {
splitEntry = replace(entry, location.entryNum, resultPosition);
btree.replaced = true;
}
if (splitEntry != null) {
parentEntry = new ParentEntry(splitEntry, 0);
}
break;
}
return parentEntry;
}
/*
* Find the nth (starting from 0) entry matching the key, or the first
* entry that doesn't match.
*
* Returns true if searchResult now points to the nth entry and it
* matched. Returns false if the nth entry is not a match, with the
* following exceptions:
*
* If n is Integer.MAX_VALUE, we're adding a new last entry. Or,
* if the target entry is the first non-matching entry and this is an
* add operation, we're also adding a new last entry. In either case,
* set searchResult to point to the correct insert location and return true.
*/
boolean findNth(SearchResult searchResult, byte[] key,
int target, boolean adding) throws StorageException {
BtreePage page;
/*
* If we're adding at the end and the list is empty, we're
* already correctly positioned, so just return.
*/
if ((target == Integer.MAX_VALUE) && !searchResult.matched) {
return true;
}
/* We already have entry 0, so start counting from 1. */
for (int i = 1; i <= target; i++) {
page = searchResult.page;
getNext(key, searchResult, false);
if ((searchResult.page != page) && (page != this)) {
pageSource.unpinPage(page);
}
if (!searchResult.matched) {
if (adding &&
((i == target) || (target == Integer.MAX_VALUE))) {
/* We're adding a new last entry for this key. Don't
* add a new page entry 0 that doesn't match the key of
* the existing entry 0, or the parent key pointing to
* this page will be incorrect. Make it the last entry
* of the previous page instead.
*/
if ((searchResult.entryNum == 0) && !isBigKey(key)) {
getPrevious(key, searchResult);
searchResult.entryNum++;
}
return true;
} else {
return false;
}
}
}
return true;
}
/*
* Search for a key/value pair matching the parameters passed in.
* The searchResult is presumed to already point to the first entry
* matching the key. If a match is found, on return searchResult points
* to the matching entry.
*/
private boolean findMatchingData(SearchResult searchResult,
byte[] key, byte[] value) throws StorageException {
boolean found;
BtreePage page;
do {
found = (searchResult.page.compareData(
value, searchResult.entryNum) == EntryTypeInfo.EQUAL);
if (!found) {
page = searchResult.page;
getNext(key, searchResult, false);
if ((searchResult.page != page) && (page != this)) {
pageSource.unpinPage(page);
searchResult.skipCount++;
}
}
} while (!found && searchResult.matched);
return found;
}
/**
* Retrieves the value associated with the given key.
*
* @param key key to find the entry for
*
* @return the data associated with the passed-in key, or null
* if it was not found.
*/
public byte[] get(byte[] key) throws StorageException {
SearchResult searchResult;
BtreePage page;
byte[] data;
searchResult = getLocation(key);
page = searchResult.page;
if (searchResult.matched) {
data = page.getData(searchResult.entryNum);
} else {
data = null;
}
if (page != this) {
pageSource.unpinPage(page);
}
return data;
}
/**
* Finds the first entry associated with the given key, navigating down
* the btree from this page.
* Recursively calls itself on its children until a leaf page is reached.
*
* @param key key to find the entry for
*
* @return SearchResult pointing to the entry. If no match was
* found, SearchResult.matched will be false.
*/
public SearchResult getLocation(byte[] key) throws StorageException {
SearchResult searchResult;
if (isBigKey(key)) {
return searchBigKeys(key);
}
searchResult = searchPage(key);
if (isLeaf()) {
return searchResult;
} else {
BtreePage child;
child = searchResult.page.getChild(searchResult);
searchResult = child.getLocation(key);
if (searchResult.page != child) {
pageSource.unpinPage(child);
}
}
return searchResult;
}
/**
* Return the first entry in the btree. This method is
* called on the root page.
*/
SearchResult getFirst() throws StorageException {
SearchResult location;
BtreePage current, parent;
location = new SearchResult(false, 0, this);
while (!location.page.isLeaf()) {
parent = location.page;
location.page = location.page.getChild(location);
if (parent != location.page) {
pageSource.unpinPage(parent);
}
}
/* We now have the first leaf page. Get the first real entry. */
location.entryNum = -1;
getNext(null, location);
if ((!location.matched) && (btree.hasBigKeys())) {
getFirstBigKey(location, false);
}
return location;
}
/**
* Remove all entries from the btree that match the given key.
*
* @param key the key to be matched
*
* @return boolean indicating whether a match was found
*/
public boolean remove(byte[] key) throws StorageException {
SearchResult result;
BtreePage page = null;
int first, last;
boolean found;
result = getLocation(key);
if (!result.matched) {
found = false;
} else {
found = true;
if (btree.uniqueKeys) {
result.page.delete(result.entryNum, result.entryNum);
} else {
// Call delete() on each page that has matching entries
page = result.page;
while (result.matched) {
page = result.page;
first = result.entryNum;
last = result.entryNum;
// Find the last matching entry on this page
while (result.matched && (result.page == page)) {
last = result.entryNum;
getNext(key, result);
}
page.delete(first, last);
if (page != this) {
pageSource.unpinPage(page);
}
}
}
}
if ((result.page != this) && (result.page != page)) {
pageSource.unpinPage(result.page);
}
return found;
}
/**
* Remove the first entry encountered that matches the key/value pair.
*
* @param key the key to be matched
* @param data the data value to be matched
*
* @return boolean indicating whether a match was found
*/
public boolean remove(byte[] key, byte[] data) throws StorageException {
SearchResult result;
BtreePage page;
boolean found;
result = getLocation(key);
if (!result.matched) {
found = false;
} else {
page = result.page;
if (page.findMatchingData(result, key, data)) {
found = true;
result.page.delete(result.entryNum, result.entryNum);
} else {
found = false;
}
if ((page != this) && (page != result.page)) {
pageSource.unpinPage(page);
}
}
if (result.page != this) {
pageSource.unpinPage(result.page);
}
return found;
}
/**
* Remove the item matching the key at the indexed position.
*
* @param key the key to be matched
* @param index position within key's entries of the target entry
*
* @return boolean indicating whether a match was found
*/
public boolean remove(byte[] key, int index) throws StorageException {
SearchResult result;
BtreePage page;
boolean found;
result = getLocation(key);
if (!result.matched) {
found = false;
} else {
page = result.page;
if (page.findNth(result, key, index, false)) {
found = true;
result.page.delete(result.entryNum, result.entryNum);
} else {
found = false;
}
if ((page != this) && (page != result.page)) {
pageSource.unpinPage(page);
}
}
if (result.page != this) {
pageSource.unpinPage(result.page);
}
return found;
}
/*
* Get the child page pointed to by the given searchResult.
* A SearchResult points to the first entry >= the search key. So, if
* it wasn't an exact match, we need to back up one entry to find the
* correct child page.
*/
private BtreePage getChild(SearchResult searchResult)
throws StorageException {
int childEntry;
if (searchResult.matched || searchResult.entryNum == 0) {
childEntry = searchResult.entryNum;
} else {
childEntry = searchResult.entryNum - 1;
}
return pageSource.getPage(getData(childEntry), btree);
}
/*
* Search the page for an entry matching the specified key. The leftmost
* matching entry is returned, which may or may not be on this page. If
* no match was found, the location where this key would be inserted is
* returned.
*/
private SearchResult searchPage(byte[] key) throws StorageException {
int base;
int limit;
int midpoint;
byte compare;
SearchResult test, result;
// Binary search the entries on this page
base = 0;
result = null;
if (numEntries() > 0) {
for (base=0, limit=numEntries(); limit > 0; limit = limit/2) {
midpoint = base + limit/2;
if ((compare = compare(key, midpoint))
== EntryTypeInfo.EQUAL) {
result = new SearchResult(true, midpoint, this);
break;
} else if (compare == EntryTypeInfo.GREATER) {
base = midpoint + 1;
limit--;
}
}
}
if (result == null) {
result = new SearchResult(false, base, this);
}
// If this is a non-unique index, we're not done.
if (!btree.uniqueKeys) {
test = new SearchResult(result);
if (!result.matched && isLeaf()) {
// If there was no match, and this is a leaf page,
// there could be a match on an adjoining page (this
// could happen if there were duplicate entries
// on this page that were deleted).
if (result.entryNum == 0) {
getPrevious(key, test);
if (test.matched) {
test.copy(result);
}
}
if (!result.matched &&
result.entryNum == numEntries()) {
result.copy(test);
getNext(key, test);
if (test.matched) {
test.copy(result);
}
}
}
// Get the leftmost match
if (result.matched) {
result.copy(test);
do {
getPrevious(key, test);
if (test.matched) {
if ((test.page != result.page)
&& (result.page != this)) {
pageSource.unpinPage(result.page);
}
test.copy(result);
}
} while (test.matched);
}
}
return result;
}
/*
* Search the page for an entry matching the specified key. The leftmost
* matching entry is returned, which may or may not be on this page. If
* no match was found, the location where this key would be inserted is
* returned.
*
* This methods first of all checks if the leftmost matching entry is on the
* specified position. If not, standard search page method is called.
*/
SearchResult searchPage(byte[] key, int position) throws StorageException {
if (isLeaf() && (position < numEntries()) && (compare(key, position) == EntryTypeInfo.EQUAL)) {
SearchResult result = new SearchResult(true, position, this);
if (position > 0) {
if (compare(key, position - 1) != EntryTypeInfo.EQUAL)
return result;
} else {
getPrevious(key, result);
if (!result.matched) {
result.matched = true;
result.entryNum = position;
result.page = this;
return result;
}
}
}
return getLocation(key);
}
/*
* Get the previous entry, starting from the passed in result. The
* result is updated to point to the previous entry and indicate whether
* it matched the key. If key is null, it is considered a match as long
* as any record was found.
*
* Only empty pages get unpinned here. Any other page fetched here
* will be returned in a SearchResult and must be unpinned by the caller.
*/
static void getPrevious(byte[] key, SearchResult result)
throws StorageException {
BtreePage page, newPage;
int entry;
boolean endOfChain;
Btree btree;
BtreePageSource pageSource;
int traversed = 0;
entry = result.entryNum;
page = result.page;
endOfChain = false;
btree = page.btree;
pageSource = btree.pageSource;
if (page instanceof BigKeyPage) {
BigKeyPage.getPrevious(key, result);
return;
}
// Get previous page if necessary, skipping over empty pages
while (!(endOfChain = pageSource.isNoPage(page.previousPage))
&& (entry == 0)) {
newPage = pageSource.getPage(page.previousPage, btree);
traversed++;
if ((page.numEntries() == 0) && (page != result.page)) {
pageSource.unpinPage(page);
}
page = newPage;
entry = page.numEntries();
}
if (endOfChain && (entry == 0)) {
result.matched = false;
} else {
entry--;
if ((key == null) ||
(page.compare(key, entry) == EntryTypeInfo.EQUAL)) {
result.matched = true;
} else {
result.matched = false;
}
result.entryNum = entry;
result.page = page;
result.skipCount -= traversed;
}
}
static boolean hasNext(byte[] key, SearchResult result)
throws StorageException {
getNext(key, result, true);
return result.matched;
}
static void getNext(byte[] key, SearchResult result)
throws StorageException {
getNext(key, result, false);
}
/*
* 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.
*
* Empty pages fetched here are unpinned here. Normally a non-empty page
* fetched here will be returned in the SearchResult and must be unpinned
* by the caller. However if testOnly is true, a non-empty page fetched
* here is unpinned here since it will not be returned.
*/
static void getNext(byte[] key, SearchResult result,
boolean testOnly)
throws StorageException {
BtreePage page, newPage;
int entry;
boolean endOfChain;
Btree btree;
BtreePageSource pageSource;
int traversed = 0;
page = result.page;
btree = page.btree;
pageSource = btree.pageSource;
endOfChain = false;
if (page instanceof BigKeyPage) {
BigKeyPage.getNext(key, result, testOnly);
return;
}
if (page.numEntries() > 0) {
entry = result.entryNum;
} else {
entry = -1;
}
// Get next page if necessary, skipping over empty pages
while (!(endOfChain =
(page.isRoot() || pageSource.isNoPage(page.nextPage)))
&& (entry >= page.numEntries() - 1)) {
newPage = pageSource.getPage(page.nextPage, btree);
traversed++;
if ((page.numEntries() == 0) && (page != result.page)) {
/*
* This would be a good place to optionally trace
* empty pages in the tree.
*/
pageSource.unpinPage(page);
}
page = newPage;
entry = -1;
}
entry++;
if (endOfChain && (entry >= page.numEntries())) {
if ((key == null) && page.isLeaf() && btree.hasBigKeys()) {
getFirstBigKey(result, testOnly);
return;
}
result.matched = false;
} else {
if ((key == null) ||
(page.compare(key, entry) == EntryTypeInfo.EQUAL)) {
result.matched = true;
} else {
result.matched = false;
}
}
if (!testOnly) {
result.entryNum = entry;
result.page = page;
result.skipCount += traversed;
} else if (page != result.page) {
pageSource.unpinPage(page);
}
}
/*
* Splits this page, inserting the new entry in its correct location.
* This method allocates a new page and links it in to the tree. It
* then calls splitEntries() which moves the entries around
* and does the insert.
*
* @param resultPosition if this parameter is not null, a new location of the inserted
* entry is recorded here
*/
protected BtreeEntry split(BtreeEntry entry, int entryNum, SearchResult resultPosition)
throws StorageException {
BtreePage right, oldRight;
byte[] rightKey, rightId;
pageSource.dirtyPage(this);
if (isRoot()) {
splitRoot(entry, entryNum, resultPosition);
return null;
} else {
right = pageSource.newPage(btree);
if (isLeaf()) {
right.makeLeaf();
} else {
right.makeInternal();
}
if (!pageSource.isNoPage(nextPage)) {
oldRight = pageSource.getPage(nextPage, btree);
pageSource.dirtyPage(oldRight);
System.arraycopy(right.pageId, 0, oldRight.previousPage, 0,
right.pageId.length);
pageSource.unpinPage(oldRight);
}
System.arraycopy(this.pageId, 0, right.previousPage, 0,
this.pageId.length);
System.arraycopy(this.nextPage, 0, right.nextPage, 0,
this.pageId.length);
System.arraycopy(right.pageId, 0, this.nextPage, 0,
right.pageId.length);
/*
* Now split the entries between the two pages. If we're adding
* a new last record, it may be the case that sequential inserts
* are being done. If so, it's much more efficient to just move
* the new insert onto the new page instead of splitting in the
* middle which would just waste space. If not, no harm done
* by doing this.
*/
if (pageSource.isNoPage(right.nextPage) && (entryNum == numEntries())) {
right.insert(entry, 0, resultPosition);
rightKey = entry.key;
} else {
rightKey = splitEntries(this, right, entry, entryNum, resultPosition);
}
rightId = new byte[right.pageId.length];
System.arraycopy(right.pageId, 0, rightId, 0, right.pageId.length);
pageSource.unpinPage(right);
return new BtreeEntry(rightKey, rightId);
}
}
/*
* Splits a root page, which is a special case of splitting a page, and
* inserts the entry in the correct location.
*/
private void splitRoot(BtreeEntry entry, int entryNum, SearchResult resultPosition)
throws StorageException {
BtreePage right;
BtreePage left;
byte[] rightKey;
byte[] leftKey;
pageSource.dirtyPage(this);
// Make two new pages
left = pageSource.newPage(btree);
right = pageSource.newPage(btree);
System.arraycopy(right.pageId, 0, left.nextPage, 0,
right.pageId.length);
System.arraycopy(left.pageId, 0, right.previousPage, 0,
left.pageId.length);
if (this.isLeaf()) {
left.makeLeaf();
right.makeLeaf();
} else {
left.makeInternal();
right.makeInternal();
}
// Move the entries to the new child pages, clear them from the
// current page, and insert the entry that caused the split.
rightKey = splitEntries(left, right, entry, entryNum, resultPosition);
// The leftmost key will never be used, so just put a placeholder there.
// See compare() below for explanation.
leftKey = new byte[rightKey.length];
if (isLeaf()) {
makeInternal();
}
insert(new BtreeEntry(leftKey, left.pageId), 0, null);
insert(new BtreeEntry(rightKey, right.pageId), 1, null);
pageSource.unpinPage(right);
pageSource.unpinPage(left);
}
/**
* Compares the key with that of the specified entry. Just handles one
* special case and then calls btree.keyInfo.compare().
*
* @param key search key
* @param entryNum entry number of target entry
* @return EntryTypeInfo.EQUAL if the two keys are equal
* EntryTypeInfo.GREATER if search key is greater than entry's key
* EntryTypeInfo.LESS if search key is less than entry's key
*/
protected byte compare(byte[] key, int entryNum) {
// The leftmost key on the leftmost page at a non-leaf level
// is forced to compare as less than any search key. This avoids
// having to update the leftmost key on internal pages when
// a key gets inserted that is smaller than anything previously
// inserted.
if (!isLeaf() && (entryNum == 0)
&& pageSource.isNoPage(previousPage)) {
return EntryTypeInfo.GREATER;
} else {
return btree.keyInfo.compare(key, pageBuffer,
keyOffset(entryNum),
keyLength(entryNum));
}
}
protected byte compareData(byte[] data, int entryNum) {
return btree.dataInfo.compare(data, pageBuffer,
keyOffset(entryNum) + keyLength(entryNum), data.length);
}
private void makeLeaf() {
flags |= BTREE_LEAF_PAGE;
dataLength = btree.dataLength;
}
private void makeInternal() {
flags &= ~BTREE_LEAF_PAGE;
dataLength = btree.pageIdLength;
}
public void makeRoot() {
flags |= BTREE_ROOT_PAGE;
}
boolean isLeaf() {
return (flags == (flags | BTREE_LEAF_PAGE));
}
boolean isRoot() {
return (flags == (flags | BTREE_ROOT_PAGE));
}
/*
* BigKey handling methods. Except for isBigKey(), these are all called
* on the root page. Once we have a BigKeyPage to work with, a
* BigKeyPage method is invoked.
*/
boolean isBigKey(byte[] key) {
return (key.length + btree.dataLength)
> ((btree.pageSize - headerLength - 4) / 3);
}
void putBigKey(BtreeEntry entry, byte operation, int index, SearchResult resultPosition)
throws StorageException {
SearchResult location;
BtreePage firstBig;
location = searchBigKeys(entry.key);
if (location.page == this) {
/* There are no big key pages yet */
if (operation == Btree.REPLACE) {
btree.failed = true;
return;
}
firstBig = BigKeyPage.makeFirst(this, pageSource);
location.page = firstBig;
location.entryNum = 0;
}
putHere(operation, location, entry, index, resultPosition);
}
SearchResult searchBigKeys(byte[] key) throws StorageException {
BtreePage page;
SearchResult location;
if (!btree.hasBigKeys()) {
return new SearchResult(false, 0, this);
} else {
page = pageSource.getPage(nextPage, btree);
location = page.searchBigKeys(key);
if (location.page != page) {
pageSource.unpinPage(page);
}
return location;
}
}
static void getFirstBigKey(SearchResult result, boolean testOnly)
throws StorageException {
Btree btree = result.page.btree;
BtreePageSource pageSource = btree.pageSource;
BtreePage root = pageSource.getPage(btree.rootPageId, btree);
if (pageSource.isNoPage(root.nextPage)) {
result.matched = false;
} else {
result.matched = true;
if (!testOnly) {
result.page = pageSource.getPage(root.nextPage, btree);
}
}
pageSource.unpinPage(root);
}
/* ******************************************************************
*
* Debugging methods
*
* *****************************************************************/
/**
* Print BtreePage contents for debugging.
*
* @param out PrintWriter to print to
*/
public void dumpPage(PrintWriter out) throws StorageException {
dumpPageHeader(out);
dumpPageEntries(out);
}
/**
* Print BtreePage header for debugging.
*
* @param out PrintWriter to print to
*/
public void dumpPageHeader(PrintWriter out) {
out.println("\n");
out.println("Page ID: " + pageSource.getPageIdInfo().fromBuffer(pageId) + "\n");
out.println("Next page: " + pageSource.getPageIdInfo().fromBuffer(nextPage) + "\n");
out.println("Previous page: " + pageSource.getPageIdInfo().fromBuffer(previousPage) + "\n");
out.println("Flags: " + flags + "\n");
out.println("Free start: " + freeStart + "\n");
}
/**
* Print BtreePage entries for debugging.
*
* @param out PrintWriter to print to
*/
public void dumpPageEntries(PrintWriter out) throws StorageException {
EntryTypeInfo pageIdInfo = pageSource.getPageIdInfo();
out.println("\nPage entries:\n\n");
for (int i = 0; i < numEntries(); i++) {
out.print(i + ": ");
// could change these to not allocate
out.print(btree.keyInfo.fromBuffer(getKey(i)) + ", ");
if (isLeaf()) {
out.println(btree.dataInfo.fromBuffer(getData(i)));
} else {
out.println(pageIdInfo.fromBuffer(getData(i)));
}
}
}
/**
* Print raw page buffer contents for debugging.
*
* @param out PrintWriter to print to
*/
public void dumpPageBuffer(PrintWriter out) {
DataInputStream in = new DataInputStream
(new ByteArrayInputStream(pageBuffer));
out.println("\nPage buffer contents:");
try {
int count = 0;
while (true) {
if (count%8== 0) {
out.println();
}
out.print(Integer.toHexString(in.readInt()));
out.print(" ");
count++;
}
} catch (Exception e) {}
out.println();
}
/**
* Print tree starting from this page for debugging.
*
* @param out PrintWriter to print to
*/
public void dumpTree(PrintWriter out) throws StorageException {
out.println("\n Dumping Btree:");
BtreePage current = this;
BtreePage old;
int level = 1;
SearchResult leftEntry = new SearchResult(true, 0, this);
while (!current.isLeaf()) {
out.println("\n Level " + level);
current.dumpLevel(out);
level++;
old = current;
current = current.getChild(leftEntry);
if (old != this) {
pageSource.unpinPage(old);
}
}
out.println("\n Leaf Level " + level);
current.dumpLevel(out);
if (current != this) {
pageSource.unpinPage(current);
}
}
void dumpLevel(PrintWriter out)
throws StorageException {
BtreePage current = this;
byte[] next;
do {
if (current instanceof BigKeyPage) {
current.dumpLevel(out);
return;
}
current.dumpPage(out);
next = current.nextPage;
if (current != this) {
pageSource.unpinPage(current);
}
} while (!pageSource.isNoPage(next) &&
(current = pageSource.getPage(next, btree)) != null);
}
public int consistencyCheck(PrintWriter out) throws StorageException {
BtreePage leftPage = this;
BtreePage old;
int level = 1;
SearchResult leftEntry = new SearchResult(true, 0, this);
SearchResult current = new SearchResult(true, 0, this);
boolean done = false;
int errors = 0;
byte[] previous;
EntryTypeInfo pageIdInfo = pageSource.getPageIdInfo();
out.println("\nBtree Consistency Check:\n");
/* Check consistency of each level */
while (!done) {
current.entryNum = 0;
current.page = leftPage;
current.matched = true;
getNext(null, current);
/* Check that keys on this level are in correct order. At the
* leaf level, also verify that each record can be navigated
* to correctly by its key.
*/
while (current.matched) {
previous = current.page.getKey(current.entryNum);
if (current.page.isLeaf() && btree instanceof SinglevaluedBtree
&& (((SinglevaluedBtree)btree).getIfExists(
btree.keyInfo.fromBuffer(previous)) == null)) {
out.println("Record with key "
+ btree.keyInfo.fromBuffer(previous)
+ " exists at page "
+ pageIdInfo.fromBuffer(current.page.pageId)
+ " , entry " + current.entryNum
+ " but cannot be reached.");
}
old = current.page;
getNext(null, current);
if ((current.page != old) && (old != leftPage)) {
pageSource.unpinPage(old);
}
if (current.matched && !(current.page instanceof BigKeyPage)
&& (current.page.compare(previous, current.entryNum)
== EntryTypeInfo.GREATER)) {
errors++;
out.println("Key is less than previous key: page "
+ pageIdInfo.fromBuffer(current.page.pageId)
+ " , entry " + current.entryNum
+ " , level " + level);
}
}
if (current.page != this) {
pageSource.unpinPage(current.page);
}
/* Go to the beginning of the next level */
level++;
old = leftPage;
if (!(done = leftPage.isLeaf())) {
leftPage = leftPage.getChild(leftEntry);
}
if (old != this) {
pageSource.unpinPage(old);
}
}
out.println("\nBtree Consistency Check Completed\n");
out.flush();
return errors;
}
}
|
The search page
Other source code files at this package level
Click here to learn more about this project
