ostore.dataobj
Class Btree

java.lang.Object
  |
  +--ostore.dataobj.Btree

All Implemented Interfaces:

BtreeNode, Cacheable, QuickSerializable, VerifiableBlock

public class Btree

extends Object

implements BtreeNode, QuickSerializable

The Btree forms the basis for storing data in OceanStore. While it is based on the ideas of standard Btree, it is not a generic, general-purpose Btree. Note that a Btree is initialized with the desired size of the nodes rather than the traditional degree of the tree. This is the case because it is more important that we know the size of the blocks (for network transmission, archival, etc.) than the branching factor.

Version:

$Id: Btree.java,v 1.68 2004/03/23 03:06:54 hweather Exp $

Author:

Patrick R. Eaton

Nested Class Summary

static interface	Btree.Callback This interface must be implemented by clients wishing to use any of the Depth-First Search (DFS) methods.
static class	Btree.InteriorNode The InteriorNode object is the interior node of the Btree.
static interface	Btree.Predicate This interface must be implemented by clients wishing to use any of the Depth-First Search (DFS) methods.
static interface	Btree.Record

Field Summary

static int	DATA_BTREE
static int	INDEX_BTREE

Constructor Summary

Btree(Btree old_btree)
Create a new Btree tree by cloning an existing Btree.

Btree(InputBuffer buffer)

Btree(int btree_type, int blocksize)
Create a new Btree.

Method Summary

Btree	begin()
void	commit(HandleStore handle_store, DataCache cache)
SecureHash	computeGuid() Compute and return the guid of the object.
SecureHash	computeVhash() Compute and return the verification hash of the object.
protected Object	dfs_helper(BtreeNode node, Btree.Predicate pred, Btree.Callback cb, Btree.Record rec, int level, boolean pre, HandleStore handle_store, DataCache cache)
Object	dfsPostorder(Btree.Predicate pred, Btree.Callback cb, Btree.Record rec, HandleStore handle_store, DataCache cache) Traverse the tree in depth-first order, guided by the predicate pred, and invoke the callback cb on each node as it is left.
Object	dfsPreorder(Btree.Predicate pred, Btree.Callback cb, Btree.Record rec, HandleStore handle_store, DataCache cache) Traverse the tree in depth-first order, guided by the predicate pred, and invoke the callback cb on each node as it is entered.
static Btree	fromGuidBytes(byte[] data, int[] offset)
static Btree	fromGuidBytes(InputBuffer buffer)
int	getBlockSize()
SecureHash	getFhash() Return the secure hash at the root of the verification tree constructed from the erasure-encoded fragments of a block.
Btree.InteriorNode	getRoot()
void	insert(BtreeKey key, BtreeNode data, HandleStore handle_store, CacheablePinned memory_handle, DataCache cache)
void	insert(BtreeKey key, BtreeNode data, HandleStore handle_store, DataCache cache)
boolean	isDataNode()
boolean	isLeaf()
Collection	readPath(BtreeKey key, HandleStore handle_store, DataCache cache)
boolean	replace(BtreeKey key, BtreeNode data, CacheablePinned memory_handle, HandleStore handle_store, DataCache cache, LinkedList reserved_blocks)
boolean	replace(BtreeKey key, BtreeNode data, HandleStore handle_store, DataCache cache)
CacheablePinned	search(BtreeKey key, HandleStore handle_store, DataCache cache)
void	serialize(OutputBuffer buffer) Add the object to the buffer.
void	setFhash(SecureHash fhash) Record the secure hash at the root of the verification tree constructed from the erasure-encoded fragments of a block.
void	setRoot(Btree.InteriorNode root)
void	toGuidBytes(byte[] data, int[] offset) Serialize the object in a form suitable for computing the block guid of the object.
String	toString()
void	toVhashBytes(byte[] data, int[] offset) Serialize the object in a form suitable for computing the verification hash of the object.
boolean	verifyGuid(SecureHash guid) Verify the contents of the object against its given guid.
boolean	verifyVhash(SecureHash vhash) Verify the contents of the object against its given verification hash.

Methods inherited from class java.lang.Object

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

Field Detail

DATA_BTREE

public static final int DATA_BTREE

See Also:

Constant Field Values

INDEX_BTREE

public static final int INDEX_BTREE

See Also:

Constant Field Values

Constructor Detail

Btree

public Btree(int btree_type,
             int blocksize)

Create a new Btree.

Parameters:

blocksize - the maximum size in bytes to be used by each node in the Btree

Btree

public Btree(Btree old_btree)

Create a new Btree tree by cloning an existing Btree. The clone is a deep copy.

Parameters:

old_btree - the old Btree to clone

Btree

public Btree(InputBuffer buffer)
      throws QSException

Method Detail

fromGuidBytes

public static Btree fromGuidBytes(byte[] data,
                                  int[] offset)
                           throws QSException

QSException

fromGuidBytes

public static Btree fromGuidBytes(InputBuffer buffer)
                           throws QSException

QSException

getBlockSize

public int getBlockSize()

begin

public Btree begin()

commit

public void commit(HandleStore handle_store,
                   DataCache cache)

insert

public void insert(BtreeKey key,
                   BtreeNode data,
                   HandleStore handle_store,
                   DataCache cache)
            throws CacheException

CacheException

insert

public void insert(BtreeKey key,
                   BtreeNode data,
                   HandleStore handle_store,
                   CacheablePinned memory_handle,
                   DataCache cache)
            throws CacheException

CacheException

search

public CacheablePinned search(BtreeKey key,
                              HandleStore handle_store,
                              DataCache cache)
                       throws CacheException

CacheException

replace

public boolean replace(BtreeKey key,
                       BtreeNode data,
                       HandleStore handle_store,
                       DataCache cache)
                throws CacheException

CacheException

replace

public boolean replace(BtreeKey key,
                       BtreeNode data,
                       CacheablePinned memory_handle,
                       HandleStore handle_store,
                       DataCache cache,
                       LinkedList reserved_blocks)
                throws CacheException

CacheException

readPath

public Collection readPath(BtreeKey key,
                           HandleStore handle_store,
                           DataCache cache)
                    throws CacheException

CacheException

getRoot

public Btree.InteriorNode getRoot()

setRoot

public void setRoot(Btree.InteriorNode root)

dfsPreorder

public Object dfsPreorder(Btree.Predicate pred,
                          Btree.Callback cb,
                          Btree.Record rec,
                          HandleStore handle_store,
                          DataCache cache)
                   throws CacheException

Traverse the tree in depth-first order, guided by the predicate pred, and invoke the callback cb on each node as it is entered.

Parameters:

pred - the predicate that determines whether a node is visited

cb - the callback to invoke as each node is entered

CacheException

dfsPostorder

public Object dfsPostorder(Btree.Predicate pred,
                           Btree.Callback cb,
                           Btree.Record rec,
                           HandleStore handle_store,
                           DataCache cache)
                    throws CacheException

Traverse the tree in depth-first order, guided by the predicate pred, and invoke the callback cb on each node as it is left.

Parameters:

pred - the predicate that determines whether a node is visited

cb - the callback to invoke as each node is left

CacheException

dfs_helper

protected Object dfs_helper(BtreeNode node,
                            Btree.Predicate pred,
                            Btree.Callback cb,
                            Btree.Record rec,
                            int level,
                            boolean pre,
                            HandleStore handle_store,
                            DataCache cache)
                     throws CacheException

CacheException

toString

public String toString()

Overrides:

toString in class Object

getFhash

public SecureHash getFhash()

Description copied from interface: VerifiableBlock

Return the secure hash at the root of the verification tree constructed from the erasure-encoded fragments of a block. The root hash verifies the the fragments of the block and is a component in the computation of the block GUID.

Specified by:

getFhash in interface VerifiableBlock

Returns:

the secure hash at the root of the verification tree

setFhash

public void setFhash(SecureHash fhash)

Description copied from interface: VerifiableBlock

Record the secure hash at the root of the verification tree constructed from the erasure-encoded fragments of a block. The root hash verifies the the fragments of the block and is a component in the computation of the block GUID.

Specified by:

setFhash in interface VerifiableBlock

Parameters:

fhash - the secure hash at the root of the verification tree

computeVhash

public SecureHash computeVhash()

Description copied from interface: VerifiableBlock

Compute and return the verification hash of the object.

Specified by:

computeVhash in interface VerifiableBlock

Returns:

the vhash of the object

toVhashBytes

public void toVhashBytes(byte[] data,
                         int[] offset)

Description copied from interface: VerifiableBlock

Serialize the object in a form suitable for computing the verification hash of the object. The parameters and their meaning mimic those of the QuickSerializable.to_bytes() method. @see ostore.util.QuickSerializable#to_bytes

Specified by:

toVhashBytes in interface VerifiableBlock

Parameters:

data - See ostore.util.QuickSerializable.to_bytes

offset - See ostore.util.QuickSerializable.to_bytes

verifyVhash

public boolean verifyVhash(SecureHash vhash)

Description copied from interface: VerifiableBlock

Verify the contents of the object against its given verification hash. This method will compute the verification hash of the object and compare that hash against the alleged hash of the object to determine its validity.

Specified by:

verifyVhash in interface VerifiableBlock

Parameters:

vhash - the vhash against which to verify the object

Returns:

true iff the hash of the object matches vhash; false otherwise

computeGuid

public SecureHash computeGuid()
                       throws BlockNotGuidVerifiableException

Description copied from interface: VerifiableBlock

Compute and return the guid of the object. As a precondition, the secure hash of the root of the fragment verification tree must be set.

Specified by:

computeGuid in interface VerifiableBlock

Returns:

the guid of the object

BlockNotGuidVerifiableException

See Also:

VerifiableBlock.setFhash(ostore.util.SecureHash)

toGuidBytes

public void toGuidBytes(byte[] data,
                        int[] offset)
                 throws BlockNotGuidVerifiableException

Description copied from interface: VerifiableBlock

Serialize the object in a form suitable for computing the block guid of the object. The parameters and their meaning mimic those of the QuickSerializable.to_bytes() method. @see ostore.util.QuickSerializable#to_bytes As a precondition, the secure hash of the root of the fragment verification tree must be set.

Specified by:

toGuidBytes in interface VerifiableBlock

Parameters:

data - See ostore.util.QuickSerializable.to_bytes

offset - See ostore.util.QuickSerializable.to_bytes

BlockNotGuidVerifiableException

verifyGuid

public boolean verifyGuid(SecureHash guid)
                   throws BlockNotGuidVerifiableException

Description copied from interface: VerifiableBlock

Verify the contents of the object against its given guid. This method will compute the guid of the object and compare that hash against the alleged name of the object to determine its validity. As a precondition, the secure hash of the root of the fragment verification tree must be set.

Specified by:

verifyGuid in interface VerifiableBlock

Parameters:

guid - the block guid against which to verify the object

Returns:

true iff the guid of the object matches bguid; false otherwise

BlockNotGuidVerifiableException

serialize

public void serialize(OutputBuffer buffer)

Description copied from interface: QuickSerializable

Add the object to the buffer.

Specified by:

serialize in interface QuickSerializable

Parameters:

buffer - the output buffer to add the object to

isDataNode

public boolean isDataNode()

Specified by:

isDataNode in interface BtreeNode

isLeaf

public boolean isLeaf()

Specified by:

isLeaf in interface BtreeNode