bamboo.dmgr
Class MerkleTree.Node

java.lang.Object
  bamboo.dmgr.MerkleTree.Node

Enclosing class:

MerkleTree

public class MerkleTree.Node
extends Object

A node in the tree. Most tree operations are done on these objects. To get the root node, call MerkleTree.root ().

Nested Class Summary

class

MerkleTree.Node.Iter A class for iterating over this node's children.

Field Summary

protected long	earliest_expiry_usec The earliest expiration time in subtree below this node.
protected byte[]	hash The hash of this node's children; may be null, in which case fill_holes may be called to fill it in.
protected long	leaves_below A count of how many leaves are below this node, so that fill_holes knows when we need to create or remove child nodes.
protected int	level This node's level in the tree; leaves are below level 0.
protected long	low The lowest timestamp value that this node is a parent of.

Constructor Summary

MerkleTree.Node(int level, long low)

Method Summary

boolean	children_are_leaves()
MerkleTree.Node.Iter	children() Returns an iterator over this node's children.
long	earliest_expiry_usec()
protected MerkleTree.FillHolesState	fill_holes_have_children(MerkleTree.FillHolesState state, long now_ms)
protected MerkleTree.FillHolesState	fill_holes_no_children(MerkleTree.FillHolesState state, long now_ms)
MerkleTree.FillHolesState	fill_holes(MerkleTree.FillHolesState state, long now_ms) Fills in the holes in the tree.
boolean	has_children()
byte[]	hash()
void	invalidate_path(long time_usec) Invalidate all nodes between this one and the one which has (or would have) timestamp time_usec as its leaf.
void	invalidate() Notify this node that its current hash value should be recomputed, presumably because of a change in the underlying database.
long	leaves_below()
int	level() This node's level in the tree; leaves are below level 0.
protected long	max()
long	range_high() Returns the highest timestamp covered by this node.
long	range_low() Returns the lowest timestamp covered by this node.
void	set_earliest_expiry_usec(long e_e)
void	set_hash(byte[] value)
void	set_leaves_below(long value)
String	toString()
boolean	valid(long now_ms) Is the hash of this node up to date? Have any of this node's progeny expired?

Methods inherited from class java.lang.Object

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

Field Detail

low

protected long low

The lowest timestamp value that this node is a parent of.

level

protected int level

This node's level in the tree; leaves are below level 0.

hash

protected byte[] hash

The hash of this node's children; may be null, in which case fill_holes may be called to fill it in.

earliest_expiry_usec

protected long earliest_expiry_usec

The earliest expiration time in subtree below this node.

leaves_below

protected long leaves_below

A count of how many leaves are below this node, so that fill_holes knows when we need to create or remove child nodes. If there are less than or equal to 2^expansion leaves below this node, it'll have no children, otherwise, it'll have at least two.

Constructor Detail

MerkleTree.Node

public MerkleTree.Node(int level,
                       long low)

Method Detail

range_low

public long range_low()

Returns the lowest timestamp covered by this node.

range_high

public long range_high()

Returns the highest timestamp covered by this node.

children

public MerkleTree.Node.Iter children()

Returns an iterator over this node's children. Only valid for nodes above level 0.

Throws:

UnsupportedOperationException - if this node is at level 0

has_children

public boolean has_children()

invalidate

public void invalidate()

Notify this node that its current hash value should be recomputed, presumably because of a change in the underlying database.

valid

public boolean valid(long now_ms)

Is the hash of this node up to date? Have any of this node's progeny expired?

level

public int level()

This node's level in the tree; leaves are below level 0.

children_are_leaves

public boolean children_are_leaves()

leaves_below

public long leaves_below()

set_leaves_below

public void set_leaves_below(long value)

hash

public byte[] hash()

earliest_expiry_usec

public long earliest_expiry_usec()

set_hash

public void set_hash(byte[] value)

set_earliest_expiry_usec

public void set_earliest_expiry_usec(long e_e)

toString

public String toString()

Overrides:

toString in class Object

invalidate_path

public void invalidate_path(long time_usec)

Invalidate all nodes between this one and the one which has (or would have) timestamp time_usec as its leaf.

fill_holes

public MerkleTree.FillHolesState fill_holes(MerkleTree.FillHolesState state,
                                            long now_ms)

Fills in the holes in the tree. If all of the children of this node are valid, this function will compute the hash and leaves_below data members for this node correctly and return null. Otherwise, it will discover a range of data for which it needs a hash and a count of the number of items before it can complete successfully. In this case, it will return a FillHoleState to indicate the range it needs. The caller should perform the scan over the range range_low to range_high inclusive. If there are less than or equal to max_leaves_below items in the range, it should set leaves_below to the total number of items and store their digest in digest. Otherwise, it should set leaves_below to the number of items read and set digest to null. It should not change range_low, range_high, or max_leaves_below.

fill_holes_have_children

protected MerkleTree.FillHolesState fill_holes_have_children(MerkleTree.FillHolesState state,
                                                             long now_ms)

max

protected long max()

fill_holes_no_children

protected MerkleTree.FillHolesState fill_holes_no_children(MerkleTree.FillHolesState state,
                                                           long now_ms)