org.netbeans.mdr.persistence.btreeimpl.btreeindex

Class BtreePage

java.lang.Object

org.netbeans.mdr.persistence.btreeimpl.btreeindex.BtreePage

All Implemented Interfaces:

Streamable

Direct Known Subclasses:

BigKeyPage, FixedKeyPage, ShrinkablePage, VarKeyPage, VarRecordPage

public abstract class BtreePage
extends java.lang.Object
implements Streamable

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.

Version:

1.0

Author:

Dana Bergen

Field Summary

Fields

Modifier and Type	Field and Description
byte[]	pageBuffer
byte[]	pageId

Constructor Summary

Constructors

Constructor and Description
BtreePage() Construct an empty BtreePage.

Method Summary

Methods

Modifier and Type	Method and Description
protected byte	compare(byte[] key, int entryNum) Compares the key with that of the specified entry.
protected byte	compareData(byte[] data, int entryNum)
int	consistencyCheck(java.io.PrintWriter out)
void	dumpPage(java.io.PrintWriter out) Print BtreePage contents for debugging.
void	dumpPageBuffer(java.io.PrintWriter out) Print raw page buffer contents for debugging.
void	dumpPageEntries(java.io.PrintWriter out) Print BtreePage entries for debugging.
void	dumpPageHeader(java.io.PrintWriter out) Print BtreePage header for debugging.
void	dumpTree(java.io.PrintWriter out) Print tree starting from this page for debugging.
byte[]	get(byte[] key) Retrieves the value associated with the given key.
org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult	getLocation(byte[] key) Finds the first entry associated with the given key, navigating down the btree from this page.
void	init(Btree btree, byte[] pageId, byte[] pageBuffer, boolean isNew) Initialize a newly-instantiated or recycled BtreePage.
void	makeRoot()
void	put(byte[] key, byte[] data, byte operation, int index) Add an entry to the btree, navigating down from this page.
void	put(byte[] key, byte[] data, byte operation, int index, org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult resultPosition) Add an entry to the btree, navigating down from this page.
void	read(java.io.InputStream in) (Streamable Interface) Populate the pageBuffer from the InputStream.
boolean	remove(byte[] key) Remove all entries from the btree that match the given key.
boolean	remove(byte[] key, byte[] data) Remove the first entry encountered that matches the key/value pair.
boolean	remove(byte[] key, int index) Remove the item matching the key at the indexed position.
protected org.netbeans.mdr.persistence.btreeimpl.btreeindex.BtreePage.BtreeEntry	split(org.netbeans.mdr.persistence.btreeimpl.btreeindex.BtreePage.BtreeEntry entry, int entryNum, org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult resultPosition)
void	store() Write BtreePage header data to the page buffer.
void	uninit()
void	write(java.io.OutputStream out) (Streamable Interface) Write this page to the OutputStream.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

pageBuffer

public byte[] pageBuffer

pageId

public byte[] pageId

Constructor Detail

BtreePage

public BtreePage()

Construct an empty BtreePage. All the real work is done in init().

Method Detail

init

public void init(Btree btree,
        byte[] pageId,
        byte[] pageBuffer,
        boolean isNew)
          throws StorageException

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.

Parameters:

btree - Btree to which this page belongs

pageId - page ID in byte array

pageBuffer - page buffer

isNew - is this page new to the btree

Throws:

StorageException

store

public void store()

Write BtreePage header data to the page buffer.

read

public void read(java.io.InputStream in)
          throws StorageException

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

Specified by:

read in interface Streamable

Parameters:

in - InputStream to read from

Throws:

StorageException

write

public void write(java.io.OutputStream out)
           throws StorageException

(Streamable Interface) Write this page to the OutputStream.

Specified by:

write in interface Streamable

Parameters:

out - OutputStream to write page to

Throws:

StorageException

uninit

public void uninit()

put

public void put(byte[] key,
       byte[] data,
       byte operation,
       int index)
         throws StorageException

Add an entry to the btree, navigating down from this page.

Parameters:

key - byte array containing key

data - byte array containing data

Throws:

StorageException

put

public void put(byte[] key,
       byte[] data,
       byte operation,
       int index,
       org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult resultPosition)
         throws StorageException

Add an entry to the btree, navigating down from this page.

Parameters:

key - byte array containing key

data - byte array containing data

resultPosition - location of inserted element is recorded in case this parameter is not null and the oparation to perform is insert (add).

Throws:

StorageException

get

public byte[] get(byte[] key)
           throws StorageException

Retrieves the value associated with the given key.

Parameters:

key - key to find the entry for

Returns:

the data associated with the passed-in key, or null if it was not found.

Throws:

StorageException

getLocation

public org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult getLocation(byte[] key)
                                                                           throws StorageException

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.

Parameters:

key - key to find the entry for

Returns:

SearchResult pointing to the entry. If no match was found, SearchResult.matched will be false.

Throws:

StorageException

remove

public boolean remove(byte[] key)
               throws StorageException

Remove all entries from the btree that match the given key.

Parameters:

key - the key to be matched

Returns:

boolean indicating whether a match was found

Throws:

StorageException

remove

public boolean remove(byte[] key,
             byte[] data)
               throws StorageException

Remove the first entry encountered that matches the key/value pair.

Parameters:

key - the key to be matched

data - the data value to be matched

Returns:

boolean indicating whether a match was found

Throws:

StorageException

remove

public boolean remove(byte[] key,
             int index)
               throws StorageException

Remove the item matching the key at the indexed position.

Parameters:

key - the key to be matched

index - position within key's entries of the target entry

Returns:

boolean indicating whether a match was found

Throws:

StorageException

split

protected org.netbeans.mdr.persistence.btreeimpl.btreeindex.BtreePage.BtreeEntry split(org.netbeans.mdr.persistence.btreeimpl.btreeindex.BtreePage.BtreeEntry entry,
                                                                           int entryNum,
                                                                           org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult resultPosition)
                                                                                throws StorageException

Throws:

StorageException

compare

protected byte compare(byte[] key,
           int entryNum)

Compares the key with that of the specified entry. Just handles one special case and then calls btree.keyInfo.compare().

Parameters:

key - search key

entryNum - entry number of target entry

Returns:

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

compareData

protected byte compareData(byte[] data,
               int entryNum)

makeRoot

public void makeRoot()

dumpPage

public void dumpPage(java.io.PrintWriter out)
              throws StorageException

Print BtreePage contents for debugging.

Parameters:

out - PrintWriter to print to

Throws:

StorageException

dumpPageHeader

public void dumpPageHeader(java.io.PrintWriter out)

Print BtreePage header for debugging.

Parameters:

out - PrintWriter to print to

dumpPageEntries

public void dumpPageEntries(java.io.PrintWriter out)
                     throws StorageException

Print BtreePage entries for debugging.

Parameters:

out - PrintWriter to print to

Throws:

StorageException

dumpPageBuffer

public void dumpPageBuffer(java.io.PrintWriter out)

Print raw page buffer contents for debugging.

Parameters:

out - PrintWriter to print to

dumpTree

public void dumpTree(java.io.PrintWriter out)
              throws StorageException

Print tree starting from this page for debugging.

Parameters:

out - PrintWriter to print to

Throws:

StorageException

consistencyCheck

public int consistencyCheck(java.io.PrintWriter out)
                     throws StorageException

Throws:

StorageException