bamboo.dmgr
Class MerkleTree

java.lang.Object
  bamboo.dmgr.MerkleTree

public class MerkleTree
extends Object

A Merkle Tree over the keys stored on a Bamboo node.

Version:

$Id: MerkleTree.java,v 1.25 2004/02/13 04:39:29 srhea Exp $

Author:

Sean C. Rhea

Nested Class Summary

static class	MerkleTree.FillHolesState The data structure returned by fill_holes.
class	MerkleTree.Node A node in the tree.

Field Summary

protected MessageDigest	dont_use If you need a new digest, call new_digest; don't use this variable.
protected int	expansion Each node in this tree has at most 2^expansion children.
protected org.apache.log4j.Logger	logger
protected Map[]	nodes A array of maps that store the nodes in a given level of the tree.

Constructor Summary

MerkleTree(int exp, MessageDigest md)
Create a new MerkleTree with 2^exp children per node and using the algorithm of md to compute digests.

Method Summary

protected MessageDigest	new_digest()
MerkleTree.Node	node(int level, long low)
MerkleTree.Node	root()

Methods inherited from class java.lang.Object

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

Field Detail

logger

protected org.apache.log4j.Logger logger

expansion

protected int expansion

Each node in this tree has at most 2^expansion children.

nodes

protected Map[] nodes

A array of maps that store the nodes in a given level of the tree. The nodes in level i are stored in nodes[i]; level is the level of internal nodes closest to the leaves, which are the items of the database this Merkle tree covers. Within the maps, the nodes are indexed by the lowest timestamp value that they cover. If a node has no children, it is not stored in this data structure. (Otherwise, we'd need a lot of memory to store them all.)

dont_use

protected MessageDigest dont_use

If you need a new digest, call new_digest; don't use this variable. new_digest just clones this digest, which is always in the initialized state. I expect this to be faster than doing a call to new MessageDigest ("SHA") or whatever.

Constructor Detail

MerkleTree

public MerkleTree(int exp,
                  MessageDigest md)

Create a new MerkleTree with 2^exp children per node and using the algorithm of md to compute digests. Note that a clone of md will be used rather than md itself.

Method Detail

root

public MerkleTree.Node root()

node

public MerkleTree.Node node(int level,
                            long low)

new_digest

protected MessageDigest new_digest()