You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by ju...@apache.org on 2009/12/05 19:44:25 UTC
svn commit: r887573 - in /incubator/cassandra/trunk:
src/java/org/apache/cassandra/utils/MerkleTree.java
test/unit/org/apache/cassandra/utils/MerkleTreeTest.java
Author: junrao
Date: Sat Dec 5 18:44:25 2009
New Revision: 887573
URL: http://svn.apache.org/viewvc?rev=887573&view=rev
Log:
add Merkle tree; patched by Stu Hood, reviewed by junrao for CASSANDRA-193
Added:
incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/MerkleTree.java
incubator/cassandra/trunk/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java
Added: incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/MerkleTree.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/MerkleTree.java?rev=887573&view=auto
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/MerkleTree.java (added)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/MerkleTree.java Sat Dec 5 18:44:25 2009
@@ -0,0 +1,874 @@
+/*
+* Licensed to the Apache Software Foundation (ASF) under one
+* or more contributor license agreements. See the NOTICE file
+* distributed with this work for additional information
+* regarding copyright ownership. The ASF licenses this file
+* to you under the Apache License, Version 2.0 (the
+* "License"); you may not use this file except in compliance
+* with the License. You may obtain a copy of the License at
+*
+* http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing,
+* software distributed under the License is distributed on an
+* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+* KIND, either express or implied. See the License for the
+* specific language governing permissions and limitations
+* under the License.
+*/
+package org.apache.cassandra.utils;
+
+import java.io.Serializable;
+import java.util.*;
+import java.math.BigInteger;
+
+import com.google.common.collect.AbstractIterator;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.PeekingIterator;
+
+import org.apache.cassandra.dht.*;
+
+/**
+ * A MerkleTree implemented as a binary tree.
+ *
+ * A MerkleTree is a full binary that represents a perfect binary tree of
+ * depth 'hashdepth'. In a perfect binary tree, each leaf contains a
+ * sequentially hashed range, and each inner node contains the binary hash of
+ * its two children. In the MerkleTree, many ranges will not be split to the
+ * full depth of the perfect binary tree: the leaves of this tree are Leaf objects,
+ * which contain the computed values of the nodes that would be below them if
+ * the tree were perfect.
+ *
+ * All nodes of the perfect tree are calculated using a MD5 hash: leaves are
+ * sequential hashes of the rows that fall into the range they represent, and
+ * inner nodes are a binary hash of their children.
+ *
+ * If two MerkleTrees have the same hashdepth, they represent a perfect tree
+ * of the same depth, and can always be compared, regardless of size or splits.
+ */
+public class MerkleTree implements Serializable
+{
+ private static final long serialVersionUID = 1L;
+
+ public static final byte RECOMMENDED_DEPTH = (byte)64;
+
+ public static final int CONSISTENT = 0;
+ public static final int FULLY_INCONSISTENT = 1;
+ public static final int PARTIALLY_INCONSISTENT = 2;
+
+ // cache of empty hash trees up to the maximum depth (0 to 127)
+ public static final byte[][] EMPTIES = new byte[Byte.MAX_VALUE][];
+ static {
+ EMPTIES[0] = new byte[0];
+ for (int i = 1; i < EMPTIES.length; i++)
+ {
+ EMPTIES[i] = Hashable.binaryHash(EMPTIES[i-1], EMPTIES[i-1]);
+ }
+ }
+
+ public final byte hashdepth;
+
+ private transient IPartitioner partitioner;
+
+ private int maxsize;
+ private int size;
+ private Hashable root;
+
+ /**
+ * @param partitioner The partitioner in use.
+ * @param hashdepth The maximum depth of the tree. 100/(2^depth) is the %
+ * of the key space covered by each subrange of a fully populated tree.
+ * @param maxsize The maximum number of subranges in the tree.
+ */
+ public MerkleTree(IPartitioner partitioner, byte hashdepth, int maxsize)
+ {
+ this.partitioner = partitioner;
+ this.hashdepth = hashdepth;
+ this.maxsize = maxsize;
+
+ size = 1;
+ root = new Leaf(null);
+ }
+
+ static byte inc(byte in)
+ {
+ assert in < Byte.MAX_VALUE;
+ return (byte)(in + 1);
+ }
+
+ /**
+ * Initializes this tree by splitting it into maxsize ranges, or
+ * until hashdepth is reached.
+ *
+ * TODO: could be optimized as breadth first generation of nodes.
+ *
+ * NB: asserts that the tree is of size 1.
+ */
+ public void init()
+ {
+ assert size() == 1;
+
+ Queue<Range> ranges = new ArrayDeque<Range>();
+ ranges.add(new Range(partitioner.getMinimumToken(),
+ partitioner.getMinimumToken()));
+ while (true)
+ {
+ Range range = ranges.remove();
+ Token mid = partitioner.midpoint(range.left(),
+ range.right());
+ if (!split(mid))
+ // we've reached maxsize or hashdepth
+ return;
+
+ ranges.add(new Range(range.left(), mid));
+ ranges.add(new Range(mid, range.right()));
+ }
+ }
+
+ Hashable root()
+ {
+ return root;
+ }
+
+ public IPartitioner partitioner()
+ {
+ return partitioner;
+ }
+
+ /**
+ * The number of distinct ranges contained in this tree. This is a reasonable
+ * measure of the memory usage of the tree (assuming 'this.order' is significant).
+ */
+ public int size()
+ {
+ return size;
+ }
+
+ public int maxsize()
+ {
+ return maxsize;
+ }
+
+ public void maxsize(int maxsize)
+ {
+ this.maxsize = maxsize;
+ }
+
+ /**
+ * TODO: Find another way to use the local partitioner after serialization.
+ */
+ public void partitioner(IPartitioner partitioner)
+ {
+ this.partitioner = partitioner;
+ }
+
+ /**
+ * @param ltree First tree.
+ * @param rtree Second tree.
+ * @param active Only ranges that intersect this range will be returned.
+ * @return A list of the largest contiguous ranges where the given trees disagree.
+ */
+ public static List<Range> difference(MerkleTree ltree, MerkleTree rtree)
+ {
+ List<Range> diff = new ArrayList<Range>();
+ Token mintoken = ltree.partitioner.getMinimumToken();
+ Range active = new Range(mintoken, mintoken);
+
+ byte[] lhash = ltree.hash(active);
+ byte[] rhash = rtree.hash(active);
+
+ if (lhash != null && rhash != null && !Arrays.equals(lhash, rhash))
+ {
+ if (FULLY_INCONSISTENT == differenceHelper(ltree, rtree, diff, active))
+ diff.add(active);
+ }
+ else if (lhash == null || rhash == null)
+ diff.add(active);
+ return diff;
+ }
+
+ /**
+ * TODO: This function could be optimized into a depth first traversal of
+ * the two trees in parallel.
+ *
+ * Takes two trees and a range for which they have hashes, but are inconsistent.
+ * @return FULLY_INCONSISTENT if active is inconsistent, PARTIALLY_INCONSISTENT if only a subrange is inconsistent.
+ */
+ static int differenceHelper(MerkleTree ltree, MerkleTree rtree, List<Range> diff, Range active)
+ {
+ Token midpoint = ltree.partitioner().midpoint(active.left(), active.right());
+ Range left = new Range(active.left(), midpoint);
+ Range right = new Range(midpoint, active.right());
+ byte[] lhash;
+ byte[] rhash;
+
+ // see if we should recurse left
+ lhash = ltree.hash(left);
+ rhash = rtree.hash(left);
+ int ldiff = CONSISTENT;
+ boolean lreso = lhash != null && rhash != null;
+ if (lreso && !Arrays.equals(lhash, rhash))
+ ldiff = differenceHelper(ltree, rtree, diff, left);
+ else if (!lreso)
+ ldiff = FULLY_INCONSISTENT;
+
+
+ // see if we should recurse right
+ lhash = ltree.hash(right);
+ rhash = rtree.hash(right);
+ int rdiff = CONSISTENT;
+ boolean rreso = lhash != null && rhash != null;
+ if (rreso && !Arrays.equals(lhash, rhash))
+ rdiff = differenceHelper(ltree, rtree, diff, right);
+ else if (!rreso)
+ rdiff = FULLY_INCONSISTENT;
+
+ if (ldiff == FULLY_INCONSISTENT && rdiff == FULLY_INCONSISTENT)
+ {
+ // both children are fully inconsistent
+ return FULLY_INCONSISTENT;
+ }
+ else if (ldiff == FULLY_INCONSISTENT)
+ {
+ diff.add(left);
+ return PARTIALLY_INCONSISTENT;
+ }
+ else if (rdiff == FULLY_INCONSISTENT)
+ {
+ diff.add(right);
+ return PARTIALLY_INCONSISTENT;
+ }
+ return PARTIALLY_INCONSISTENT;
+ }
+
+ /**
+ * For testing purposes.
+ * Gets the smallest range containing the token.
+ */
+ TreeRange get(Token t)
+ {
+ Token mintoken = partitioner.getMinimumToken();
+ return getHelper(root, mintoken, mintoken, (byte)0, t);
+ }
+
+ TreeRange getHelper(Hashable hashable, Token pleft, Token pright, byte depth, Token t)
+ {
+ if (hashable instanceof Leaf)
+ {
+ // we've reached a hash: wrap it up and deliver it
+ return new TreeRange(this, pleft, pright, depth, hashable);
+ }
+ // else: node.
+
+ Inner node = (Inner)hashable;
+ if (Range.contains(pleft, node.token, t))
+ // left child contains token
+ return getHelper(node.lchild, pleft, node.token, inc(depth), t);
+ // else: right child contains token
+ return getHelper(node.rchild, node.token, pright, inc(depth), t);
+ }
+
+ /**
+ * Invalidates the ranges containing the given token.
+ */
+ public void invalidate(Token t)
+ {
+ Token mintoken = partitioner.getMinimumToken();
+ invalidateHelper(root, mintoken, mintoken, (byte)0, t);
+ }
+
+ public void invalidateHelper(Hashable hashable, Token pleft, Token pright, byte depth, Token t)
+ {
+ hashable.hash(null);
+ if (hashable instanceof Leaf)
+ return;
+ // else: node.
+
+ Inner node = (Inner)hashable;
+ if (Range.contains(pleft, node.token, t))
+ // left child contains token
+ invalidateHelper(node.lchild, pleft, node.token, inc(depth), t);
+ else
+ // right child contains token
+ invalidateHelper(node.rchild, node.token, pright, inc(depth), t);
+ }
+
+ /**
+ * Hash the given range in the tree. The range must have been generated
+ * with recursive applications of partitioner.midpoint().
+ *
+ * NB: Currently does not support wrapping ranges that do not end with
+ * partitioner.getMinimumToken().
+ *
+ * @return Null if any subrange of the range is invalid, or if the exact
+ * range cannot be calculated using this tree.
+ */
+ public byte[] hash(Range range)
+ {
+ Token mintoken = partitioner.getMinimumToken();
+ try
+ {
+ return hashHelper(root, new Range(mintoken, mintoken), range);
+ }
+ catch (StopRecursion e)
+ {
+ return null;
+ }
+ }
+
+ /**
+ * @throws StopRecursion If no match could be found for the range.
+ */
+ byte[] hashHelper(Hashable hashable, Range active, Range range) throws StopRecursion
+ {
+ if (hashable instanceof Leaf)
+ {
+ if (!range.contains(active))
+ // we are not fully contained in this range!
+ throw new StopRecursion.BadRange();
+ return hashable.hash();
+ }
+ // else: node.
+
+ Inner node = (Inner)hashable;
+ Range leftactive = new Range(active.left(), node.token);
+ Range rightactive = new Range(node.token, active.right());
+
+ if (range.contains(active))
+ {
+ // this node is fully contained in the range
+ if (node.hash() != null)
+ // we had a cached value
+ return node.hash();
+ // continue recursing to hash our children
+ byte[] lhash = hashHelper(node.lchild(), leftactive, range);
+ byte[] rhash = hashHelper(node.rchild(), rightactive, range);
+ // cache the computed value (even if it is null)
+ node.hash(lhash, rhash);
+ return node.hash();
+ } // else: one of our children contains the range
+
+ if (leftactive.contains(range))
+ // left child contains/matches the range
+ return hashHelper(node.lchild, leftactive, range);
+ else if (rightactive.contains(range))
+ // right child contains/matches the range
+ return hashHelper(node.rchild, rightactive, range);
+ else
+ throw new StopRecursion.BadRange();
+ }
+
+ /**
+ * Splits the range containing the given token, if no tree limits would be
+ * violated. If the range would be split to a depth below hashdepth, or if
+ * the tree already contains maxsize subranges, this operation will fail.
+ *
+ * @return True if the range was successfully split.
+ */
+ public boolean split(Token t)
+ {
+ if (!(size < maxsize))
+ return false;
+
+ Token mintoken = partitioner.getMinimumToken();
+ try
+ {
+ root = splitHelper(root, mintoken, mintoken, (byte)0, t);
+ }
+ catch (StopRecursion.TooDeep e)
+ {
+ return false;
+ }
+ return true;
+ }
+
+ Hashable splitHelper(Hashable hashable, Token pleft, Token pright, byte depth, Token t) throws StopRecursion.TooDeep
+ {
+ if (depth >= hashdepth)
+ throw new StopRecursion.TooDeep();
+
+ if (hashable instanceof Leaf)
+ {
+ // split
+ size++;
+ Token midpoint = partitioner.midpoint(pleft, pright);
+ return new Inner(midpoint, new Leaf(), new Leaf());
+ }
+ // else: node.
+
+ // recurse on the matching child
+ Inner node = (Inner)hashable;
+ if (Range.contains(pleft, node.token, t))
+ // left child contains token
+ node.lchild(splitHelper(node.lchild, pleft, node.token, inc(depth), t));
+ else
+ // else: right child contains token
+ node.rchild(splitHelper(node.rchild, node.token, pright, inc(depth), t));
+ return node;
+ }
+
+ /**
+ * Compacts the smallest subranges evenly split by the given token into a
+ * single range.
+ *
+ * Asserts that the given Token falls between two compactable subranges.
+ */
+ public void compact(Token t)
+ {
+ Token mintoken = partitioner.getMinimumToken();
+ root = compactHelper(root, mintoken, mintoken, t);
+ }
+
+ Hashable compactHelper(Hashable hashable, Token pleft, Token pright, Token t)
+ {
+ // we reached a Leaf without finding an Inner to compact
+ assert !(hashable instanceof Leaf);
+
+ Inner node = (Inner)hashable;
+ int comp = t.compareTo(node.token);
+ if (comp == 0)
+ {
+ // this is the node to compact
+ assert node.lchild() instanceof Leaf && node.rchild() instanceof Leaf :
+ "Can only compact a subrange evenly split by the given token!";
+
+ // hash our children together into a new value to replace ourself
+ size--;
+ return new Leaf(node.lchild().hash(), node.rchild().hash());
+ }
+ else if (comp < 0)
+ // recurse to the left
+ node.lchild(compactHelper(node.lchild(), pleft, node.token, t));
+ else
+ // recurse to the right
+ node.rchild(compactHelper(node.rchild(), node.token, pright, t));
+ return node;
+ }
+
+ /**
+ * Returns a lazy iterator of invalid TreeRanges that need to be filled
+ * in order to make the given Range valid.
+ *
+ * @param range The range to find invalid subranges for.
+ */
+ public TreeRangeIterator invalids(Range range)
+ {
+ return new TreeRangeIterator(this, range);
+ }
+
+ @Override
+ public String toString()
+ {
+ StringBuilder buff = new StringBuilder();
+ buff.append("#<MerkleTree root=");
+ root.toString(buff, 8);
+ buff.append(">");
+ return buff.toString();
+ }
+
+ /**
+ * The public interface to a range in the tree.
+ *
+ * NB: A TreeRange should not be returned by a public method unless the
+ * parents of the range it represents are already invalidated, since it
+ * will allow someone to modify the hash.
+ */
+ public static class TreeRange extends Range
+ {
+ private final MerkleTree tree;
+ public final byte depth;
+ public final Hashable hashable;
+
+ TreeRange(MerkleTree tree, Token left, Token right, byte depth, Hashable hashable)
+ {
+ super(left, right);
+ this.tree = tree;
+ this.depth = depth;
+ this.hashable = hashable;
+ }
+
+ public void hash(byte[] hash)
+ {
+ hashable.hash(hash);
+ }
+
+ public byte[] hash()
+ {
+ return hashable.hash();
+ }
+
+ /**
+ * Consumes a collection of entries within this range.
+ */
+ public void validate(Collection<RowHash> entries)
+ {
+ PeekingIterator<RowHash> iter = Iterators.peekingIterator(entries.iterator());
+ validate(iter);
+ }
+
+ /**
+ * Consumes an iterator over entries within this range, setting the
+ * value of this range's Leaf to the computed value.
+ */
+ public void validate(PeekingIterator<RowHash> entries)
+ {
+ assert hashable instanceof Leaf;
+ byte[] roothash;
+ try
+ {
+ roothash = validateHelper(left(), right(), depth, entries);
+ }
+ catch (StopRecursion e)
+ {
+ throw new RuntimeException("Iterator contained invalid entry!");
+ }
+
+ // check that all values were consumed from the iterator, and that
+ // a valid hash could be generated
+ if (entries.hasNext() || roothash == null)
+ throw new RuntimeException("Bad iterator for " + this + "!");
+ hashable.hash(roothash);
+ }
+
+ /**
+ * Collects values from the given iterator that fall into the
+ * range represented by left and right. Recurses until we reach
+ * hashdepth, where hashes are added sequentially, and then binary
+ * hashes the results back to the root.
+ *
+ * @param left The left token of the active range.
+ * @param right The right token of the active range.
+ * @param depth The depth of the active range.
+ * @param entries A peek()able iterator.
+ */
+ private byte[] validateHelper(Token left, Token right, byte depth, PeekingIterator<RowHash> entries) throws StopRecursion.InvalidHash
+ {
+ if (entries.hasNext() && Range.contains(left, right, entries.peek().token))
+ {
+ // see if we can recurse deeper
+ if (depth < tree.hashdepth)
+ {
+ Token midpoint = tree.partitioner().midpoint(left, right);
+ if (left.compareTo(midpoint) < 0 && midpoint.compareTo(right) < 0)
+ {
+ // we can recurse deeper
+ byte[] lhash = validateHelper(left, midpoint, inc(depth), entries);
+ byte[] rhash = validateHelper(midpoint, right, inc(depth), entries);
+ return Hashable.binaryHash(lhash, rhash);
+ }
+ // else: the Token impl. cannot provide more resolution for this range
+ }
+
+ // hash relevant values from the iterator, and add to the context
+ return consume(left, right, depth, entries);
+ }
+ else
+ {
+ // this range is empty: return static hash value:
+ // the hash is the one generated by a binary tree of depth (tree.hashdepth-depth)
+ return EMPTIES[tree.hashdepth-depth];
+ }
+ }
+
+ /**
+ * Consumes and sequentially hashes values from the iterator that fall into the active
+ * range. Should be called with an iterator that contains at least one matching entry.
+ */
+ private byte[] consume(Token left, Token right, byte depth, PeekingIterator<RowHash> entries)
+ {
+ byte[] sequentialHash = entries.next().hash;
+ while (entries.hasNext() && Range.contains(left, right, entries.peek().token))
+ sequentialHash = Hashable.binaryHash(sequentialHash, entries.next().hash);
+ return sequentialHash;
+ }
+
+ @Override
+ public String toString()
+ {
+ StringBuilder buff = new StringBuilder("#<TreeRange ");
+ buff.append(super.toString()).append(" depth=").append(depth);
+ return buff.append(" hash=").append(hashable.hash()).append(">").toString();
+ }
+ }
+
+ /**
+ * Performs a depth-first, inorder traversal of invalid nodes under the given root
+ * and intersecting the given range.
+ */
+ public static class TreeRangeIterator extends AbstractIterator<TreeRange> implements Iterable<TreeRange>, PeekingIterator<TreeRange>
+ {
+ // stack of ranges to visit
+ private final ArrayDeque<TreeRange> tovisit;
+ // interesting range
+ private final Range range;
+ private final MerkleTree tree;
+
+ TreeRangeIterator(MerkleTree tree, Range range)
+ {
+ Token mintoken = tree.partitioner().getMinimumToken();
+ tovisit = new ArrayDeque<TreeRange>();
+ tovisit.add(new TreeRange(tree, mintoken, mintoken, (byte)0, tree.root));
+
+ this.tree = tree;
+ this.range = range;
+ }
+
+ /**
+ * Find the next TreeRange.
+ *
+ * @return The next TreeRange.
+ */
+ @Override
+ public TreeRange computeNext()
+ {
+ while (!tovisit.isEmpty())
+ {
+ TreeRange active = tovisit.pop();
+
+ if (active.hashable.hash() != null)
+ // skip valid ranges
+ continue;
+
+ if (active.hashable instanceof Leaf)
+ // found a leaf invalid range
+ return active;
+
+ Inner node = (Inner)active.hashable;
+ // push intersecting children onto the stack
+ TreeRange left = new TreeRange(tree, active.left(), node.token, inc(active.depth), node.lchild);
+ TreeRange right = new TreeRange(tree, node.token, active.right(), inc(active.depth), node.rchild);
+ if (right.intersects(range))
+ tovisit.push(right);
+ if (left.intersects(range))
+ tovisit.push(left);
+
+ }
+ return endOfData();
+ }
+
+ public Iterator<TreeRange> iterator()
+ {
+ return this;
+ }
+ }
+
+ /**
+ * An inner node in the MerkleTree. Inners can contain cached hash values, which
+ * are the binary hash of their two children.
+ */
+ static class Inner extends Hashable
+ {
+ public final Token token;
+ private Hashable lchild;
+ private Hashable rchild;
+
+ /**
+ * Constructs an Inner with the given token and children, and a null hash.
+ */
+ public Inner(Token token, Hashable lchild, Hashable rchild)
+ {
+ super(null);
+ this.token = token;
+ this.lchild = lchild;
+ this.rchild = rchild;
+ }
+
+ public Hashable lchild()
+ {
+ return lchild;
+ }
+
+ public Hashable rchild()
+ {
+ return rchild;
+ }
+
+ public void lchild(Hashable child)
+ {
+ lchild = child;
+ }
+
+ public void rchild(Hashable child)
+ {
+ rchild = child;
+ }
+
+ /**
+ * Recursive toString.
+ */
+ @Override
+ public void toString(StringBuilder buff, int maxdepth)
+ {
+ buff.append("#<").append(getClass().getSimpleName());
+ buff.append(" ").append(token);
+ buff.append(" hash=").append(Hashable.toString(hash()));
+ buff.append(" children=[");
+ if (maxdepth < 1)
+ {
+ buff.append("#");
+ }
+ else
+ {
+ if (lchild == null)
+ buff.append("null");
+ else
+ lchild.toString(buff, maxdepth-1);
+ buff.append(" ");
+ if (rchild == null)
+ buff.append("null");
+ else
+ rchild.toString(buff, maxdepth-1);
+ }
+ buff.append("]>");
+ }
+
+ @Override
+ public String toString()
+ {
+ StringBuilder buff = new StringBuilder();
+ toString(buff, 1);
+ return buff.toString();
+ }
+ }
+
+ /**
+ * A leaf node in the MerkleTree. Because the MerkleTree represents a much
+ * larger perfect binary tree of depth hashdepth, a Leaf object contains
+ * the value that would be contained in the perfect tree at its position.
+ *
+ * When rows are added to the MerkleTree using TreeRange.validate(), the
+ * tree extending below the Leaf is generated in memory, but only the root
+ * is stored in the Leaf.
+ */
+ static class Leaf extends Hashable
+ {
+ /**
+ * Constructs a null hash.
+ */
+ public Leaf()
+ {
+ super(null);
+ }
+
+ public Leaf(byte[] hash)
+ {
+ super(hash);
+ }
+
+ public Leaf(byte[] lefthash, byte[] righthash)
+ {
+ super(Hashable.binaryHash(lefthash, righthash));
+ }
+
+ @Override
+ public void toString(StringBuilder buff, int maxdepth)
+ {
+ buff.append(toString());
+ }
+
+ @Override
+ public String toString()
+ {
+ return "#<Leaf " + Hashable.toString(hash()) + ">";
+ }
+ }
+
+ /**
+ * Hash value representing a row, to be used to pass hashes to the MerkleTree.
+ * The byte[] hash value should contain a digest of the key and value of the row.
+ */
+ public static class RowHash
+ {
+ public final Token token;
+ public final byte[] hash;
+ public RowHash(Token token, byte[] hash)
+ {
+ this.token = token;
+ this.hash = hash;
+ }
+
+ @Override
+ public String toString()
+ {
+ return "#<RowHash " + token + " " + Hashable.toString(hash) + ">";
+ }
+ }
+
+ /**
+ * Abstract class containing hashing logic, and containing a single hash field.
+ */
+ static abstract class Hashable implements Serializable
+ {
+ private static final long serialVersionUID = 1L;
+
+ protected byte[] hash;
+
+ protected Hashable(byte[] hash)
+ {
+ this.hash = hash;
+ }
+
+ public byte[] hash()
+ {
+ return hash;
+ }
+
+ void hash(byte[] hash)
+ {
+ this.hash = hash;
+ }
+
+ /**
+ * Sets the value of this hash to binaryHash of its children.
+ * @param lefthash Hash of left child.
+ * @param righthash Hash of right child.
+ */
+ void hash(byte[] lefthash, byte[] righthash)
+ {
+ hash = binaryHash(lefthash, righthash);
+ }
+
+ /**
+ * The primitive with which all hashing should be accomplished: hashes
+ * a left and right value together.
+ */
+ static byte[] binaryHash(final byte[] left, final byte[] right)
+ {
+ if (left == null || right == null)
+ return null;
+ else
+ return FBUtilities.hash("MD5", left, right);
+ }
+
+ public abstract void toString(StringBuilder buff, int maxdepth);
+
+ public static String toString(byte[] hash)
+ {
+ if (hash == null)
+ return "null";
+ return "[" + FBUtilities.bytesToHex(hash) + "]";
+ }
+ }
+
+ /**
+ * Exceptions that stop recursion early when we are sure that no answer
+ * can be found.
+ */
+ static abstract class StopRecursion extends Exception
+ {
+ static class BadRange extends StopRecursion
+ {
+ public BadRange(){ super(); }
+ }
+
+ static class InvalidHash extends StopRecursion
+ {
+ public InvalidHash(){ super(); }
+ }
+
+ static class TooDeep extends StopRecursion
+ {
+ public TooDeep(){ super(); }
+ }
+ }
+}
Added: incubator/cassandra/trunk/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java?rev=887573&view=auto
==============================================================================
--- incubator/cassandra/trunk/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java (added)
+++ incubator/cassandra/trunk/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java Sat Dec 5 18:44:25 2009
@@ -0,0 +1,592 @@
+/*
+* Licensed to the Apache Software Foundation (ASF) under one
+* or more contributor license agreements. See the NOTICE file
+* distributed with this work for additional information
+* regarding copyten ownership. The ASF licenses this file
+* to you under the Apache License, Version 2.0 (the
+* "License"); you may not use this file except in compliance
+* with the License. You may obtain a copy of the License at
+*
+* http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing,
+* software distributed under the License is distributed on an
+* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+* KIND, either express or implied. See the License for the
+* specific language governing permissions and limitations
+* under the License.
+*/
+package org.apache.cassandra.utils;
+
+import java.io.*;
+import java.util.*;
+import java.math.BigInteger;
+
+import org.apache.cassandra.dht.*;
+import static org.apache.cassandra.utils.MerkleTree.*;
+
+import org.apache.log4j.Logger;
+
+import com.google.common.collect.AbstractIterator;
+import com.google.common.collect.PeekingIterator;
+
+import org.junit.Before;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class MerkleTreeTest
+{
+ private static final Logger logger = Logger.getLogger(MerkleTreeTest.class);
+
+ public static byte[] DUMMY = "blah".getBytes();
+
+ /**
+ * If a test assumes that the tree is 8 units wide, then it should set this value
+ * to 8.
+ */
+ public static BigInteger TOKEN_SCALE = new BigInteger("8");
+
+ protected IPartitioner partitioner;
+ protected MerkleTree mt;
+
+ @Before
+ public void clear()
+ {
+ TOKEN_SCALE = new BigInteger("8");
+ partitioner = new RandomPartitioner();
+ mt = new MerkleTree(partitioner, RECOMMENDED_DEPTH, Integer.MAX_VALUE);
+ }
+
+ public static void assertHashEquals(final byte[] left, final byte[] right)
+ {
+ assertHashEquals("", left, right);
+ }
+
+ public static void assertHashEquals(String message, final byte[] left, final byte[] right)
+ {
+ String lstring = left == null ? "null" : FBUtilities.bytesToHex(left);
+ String rstring = right == null ? "null" : FBUtilities.bytesToHex(right);
+ assertEquals(message, lstring, rstring);
+ }
+
+ /**
+ * The value returned by this method is affected by TOKEN_SCALE: setting TOKEN_SCALE
+ * to 8 means that passing 0 through 8 for this method will return values mapped
+ * between 0 and Token.MAX_VALUE.
+ */
+ public static BigIntegerToken tok(int i)
+ {
+ BigInteger md5_max = new BigInteger("2").pow(127);
+ BigInteger bint = md5_max.divide(TOKEN_SCALE).multiply(new BigInteger(""+i));
+ return new BigIntegerToken(bint);
+ }
+
+ @Test
+ public void testSplit()
+ {
+ // split the range (zero, zero] into:
+ // (zero,four], (four,six], (six,seven] and (seven, zero]
+ mt.split(tok(4));
+ mt.split(tok(6));
+ mt.split(tok(7));
+
+ assertEquals(4, mt.size());
+ assertEquals(new Range(tok(7), tok(0)), mt.get(tok(0)));
+ assertEquals(new Range(tok(0), tok(4)), mt.get(tok(3)));
+ assertEquals(new Range(tok(0), tok(4)), mt.get(tok(4)));
+ assertEquals(new Range(tok(4), tok(6)), mt.get(tok(6)));
+ assertEquals(new Range(tok(6), tok(7)), mt.get(tok(7)));
+
+ // check depths
+ assertEquals((byte)1, mt.get(tok(4)).depth);
+ assertEquals((byte)2, mt.get(tok(6)).depth);
+ assertEquals((byte)3, mt.get(tok(7)).depth);
+ assertEquals((byte)3, mt.get(tok(0)).depth);
+
+ try
+ {
+ mt.split(tok(-1));
+ fail("Shouldn't be able to split outside the initial range.");
+ }
+ catch (AssertionError e)
+ {
+ // pass
+ }
+ }
+
+ @Test
+ public void testSplitLimitDepth()
+ {
+ mt = new MerkleTree(partitioner, (byte)2, Integer.MAX_VALUE);
+
+ assertTrue(mt.split(tok(4)));
+ assertTrue(mt.split(tok(2)));
+ assertEquals(3, mt.size());
+
+ // should fail to split below hashdepth
+ assertFalse(mt.split(tok(1)));
+ assertEquals(3, mt.size());
+ assertEquals(new Range(tok(4), tok(0)), mt.get(tok(0)));
+ assertEquals(new Range(tok(0), tok(2)), mt.get(tok(2)));
+ assertEquals(new Range(tok(2), tok(4)), mt.get(tok(4)));
+ }
+
+ @Test
+ public void testSplitLimitSize()
+ {
+ mt = new MerkleTree(partitioner, RECOMMENDED_DEPTH, 2);
+
+ assertTrue(mt.split(tok(4)));
+ assertEquals(2, mt.size());
+
+ // should fail to split above maxsize
+ assertFalse(mt.split(tok(2)));
+ assertEquals(2, mt.size());
+ assertEquals(new Range(tok(4), tok(0)), mt.get(tok(0)));
+ assertEquals(new Range(tok(0), tok(4)), mt.get(tok(4)));
+ }
+
+ @Test
+ public void testCompact()
+ {
+ // (zero, one], (one,two], ... (seven, zero]
+ mt.split(tok(4));
+ mt.split(tok(2));
+ mt.split(tok(6));
+ mt.split(tok(1));
+ mt.split(tok(3));
+ mt.split(tok(5));
+ mt.split(tok(7));
+
+ // compact (zero,two] and then (four,six]
+ mt.compact(tok(1));
+ mt.compact(tok(5));
+ assertEquals(6, mt.size());
+ assertEquals(new Range(tok(0), tok(2)), mt.get(tok(2)));
+ assertEquals(new Range(tok(2), tok(3)), mt.get(tok(3)));
+ assertEquals(new Range(tok(3), tok(4)), mt.get(tok(4)));
+ assertEquals(new Range(tok(4), tok(6)), mt.get(tok(5)));
+ assertEquals(new Range(tok(6), tok(7)), mt.get(tok(7)));
+ assertEquals(new Range(tok(7), tok(0)), mt.get(tok(0)));
+ // compacted ranges should be at depth 2, and the rest at 3
+ for (int i : new int[]{2,6}){ assertEquals((byte)2, mt.get(tok(i)).depth); }
+ for (int i : new int[]{3,4,7,0}){ assertEquals((byte)3, mt.get(tok(i)).depth); }
+
+ // compact (two,four] and then (six,zero]
+ mt.compact(tok(3));
+ mt.compact(tok(7));
+ assertEquals(4, mt.size());
+ assertEquals(new Range(tok(0), tok(2)), mt.get(tok(2)));
+ assertEquals(new Range(tok(2), tok(4)), mt.get(tok(4)));
+ assertEquals(new Range(tok(4), tok(6)), mt.get(tok(5)));
+ assertEquals(new Range(tok(6), tok(0)), mt.get(tok(0)));
+ for (int i : new int[]{2,4,5,0}){ assertEquals((byte)2, mt.get(tok(i)).depth); }
+
+ // compact (zero,four]
+ mt.compact(tok(2));
+ assertEquals(3, mt.size());
+ assertEquals(new Range(tok(0), tok(4)), mt.get(tok(2)));
+ assertEquals(new Range(tok(4), tok(6)), mt.get(tok(6)));
+ assertEquals(new Range(tok(6), tok(0)), mt.get(tok(0)));
+
+ // compact (four, zero]
+ mt.compact(tok(6));
+ assertEquals(2, mt.size());
+ assertEquals(new Range(tok(0), tok(4)), mt.get(tok(2)));
+ assertEquals(new Range(tok(4), tok(0)), mt.get(tok(6)));
+ assertEquals((byte)1, mt.get(tok(2)).depth);
+ assertEquals((byte)1, mt.get(tok(6)).depth);
+
+ // compact (zero, zero] (the root)
+ mt.compact(tok(4));
+ assertEquals(1, mt.size());
+ assertEquals(new Range(tok(0), tok(0)), mt.get(tok(0)));
+ assertEquals((byte)0, mt.get(tok(0)).depth);
+ }
+
+ @Test
+ public void testCompactHash()
+ {
+ byte[] val = DUMMY;
+ byte[] valXval = hashed(val, 1, 1);
+
+ // (zero, four], (four,zero]
+ mt.split(tok(4));
+
+ // validate both ranges
+ mt.get(tok(4)).hash(val);
+ mt.get(tok(0)).hash(val);
+
+ // compact (zero, eight]
+ mt.compact(tok(4));
+ assertHashEquals(valXval, mt.get(tok(0)).hash());
+ }
+
+ @Test
+ public void testInvalids()
+ {
+ Iterator<TreeRange> ranges;
+
+ // (zero, zero]
+ ranges = mt.invalids(new Range(tok(0), tok(0)));
+ assertEquals(new Range(tok(0), tok(0)), ranges.next());
+ assertFalse(ranges.hasNext());
+
+ // all invalid
+ mt.split(tok(4));
+ mt.split(tok(2));
+ mt.split(tok(6));
+ mt.split(tok(3));
+ mt.split(tok(5));
+ ranges = mt.invalids(new Range(tok(0), tok(0)));
+ assertEquals(new Range(tok(0), tok(2)), ranges.next());
+ assertEquals(new Range(tok(2), tok(3)), ranges.next());
+ assertEquals(new Range(tok(3), tok(4)), ranges.next());
+ assertEquals(new Range(tok(4), tok(5)), ranges.next());
+ assertEquals(new Range(tok(5), tok(6)), ranges.next());
+ assertEquals(new Range(tok(6), tok(0)), ranges.next());
+ assertFalse(ranges.hasNext());
+
+ // some invalid
+ mt.get(tok(2)).hash("non-null!".getBytes());
+ mt.get(tok(4)).hash("non-null!".getBytes());
+ mt.get(tok(5)).hash("non-null!".getBytes());
+ mt.get(tok(0)).hash("non-null!".getBytes());
+ ranges = mt.invalids(new Range(tok(0), tok(0)));
+ assertEquals(new Range(tok(2), tok(3)), ranges.next());
+ assertEquals(new Range(tok(5), tok(6)), ranges.next());
+ assertFalse(ranges.hasNext());
+
+ // some invalid in left subrange
+ ranges = mt.invalids(new Range(tok(0), tok(6)));
+ assertEquals(new Range(tok(2), tok(3)), ranges.next());
+ assertEquals(new Range(tok(5), tok(6)), ranges.next());
+ assertFalse(ranges.hasNext());
+
+ // some invalid in right subrange
+ ranges = mt.invalids(new Range(tok(2), tok(0)));
+ assertEquals(new Range(tok(2), tok(3)), ranges.next());
+ assertEquals(new Range(tok(5), tok(6)), ranges.next());
+ assertFalse(ranges.hasNext());
+ }
+
+ @Test
+ public void testHashFull()
+ {
+ byte[] val = DUMMY;
+ Range range = new Range(tok(0), tok(0));
+
+ // (zero, zero]
+ assertNull(mt.hash(range));
+
+ // validate the range
+ mt.get(tok(0)).hash(val);
+
+ assertHashEquals(val, mt.hash(range));
+ }
+
+ @Test
+ public void testHashPartial()
+ {
+ byte[] val = DUMMY;
+ byte[] leftval = hashed(val, 1, 1);
+ byte[] partialval = hashed(val, 1);
+ Range left = new Range(tok(0), tok(4));
+ Range partial = new Range(tok(2), tok(4));
+ Range right = new Range(tok(4), tok(0));
+ Range linvalid = new Range(tok(1), tok(4));
+ Range rinvalid = new Range(tok(4), tok(6));
+
+ // (zero,two] (two,four] (four, zero]
+ mt.split(tok(4));
+ mt.split(tok(2));
+ assertNull(mt.hash(left));
+ assertNull(mt.hash(partial));
+ assertNull(mt.hash(right));
+ assertNull(mt.hash(linvalid));
+ assertNull(mt.hash(rinvalid));
+
+ // validate the range
+ mt.get(tok(2)).hash(val);
+ mt.get(tok(4)).hash(val);
+ mt.get(tok(0)).hash(val);
+
+ assertHashEquals(leftval, mt.hash(left));
+ assertHashEquals(partialval, mt.hash(partial));
+ assertHashEquals(val, mt.hash(right));
+ assertNull(mt.hash(linvalid));
+ assertNull(mt.hash(rinvalid));
+ }
+
+ @Test
+ public void testHashInner()
+ {
+ byte[] val = DUMMY;
+ byte[] lchildval = hashed(val, 3, 3, 2);
+ byte[] rchildval = hashed(val, 2, 2);
+ byte[] fullval = hashed(val, 3, 3, 2, 2, 2);
+ Range full = new Range(tok(0), tok(0));
+ Range lchild = new Range(tok(0), tok(4));
+ Range rchild = new Range(tok(4), tok(0));
+ Range invalid = new Range(tok(1), tok(0));
+
+ // (zero,one] (one, two] (two,four] (four, six] (six, zero]
+ mt.split(tok(4));
+ mt.split(tok(2));
+ mt.split(tok(6));
+ mt.split(tok(1));
+ assertNull(mt.hash(full));
+ assertNull(mt.hash(lchild));
+ assertNull(mt.hash(rchild));
+ assertNull(mt.hash(invalid));
+
+ // validate the range
+ mt.get(tok(1)).hash(val);
+ mt.get(tok(2)).hash(val);
+ mt.get(tok(4)).hash(val);
+ mt.get(tok(6)).hash(val);
+ mt.get(tok(0)).hash(val);
+
+ assertHashEquals(fullval, mt.hash(full));
+ assertHashEquals(lchildval, mt.hash(lchild));
+ assertHashEquals(rchildval, mt.hash(rchild));
+ assertNull(mt.hash(invalid));
+ }
+
+ @Test
+ public void testHashDegenerate()
+ {
+ TOKEN_SCALE = new BigInteger("32");
+
+ byte[] val = DUMMY;
+ byte[] childfullval = hashed(val, 5, 5, 4);
+ byte[] fullval = hashed(val, 5, 5, 4, 3, 2, 1);
+ Range childfull = new Range(tok(0), tok(4));
+ Range full = new Range(tok(0), tok(0));
+ Range invalid = new Range(tok(4), tok(0));
+
+ mt = new MerkleTree(partitioner, RECOMMENDED_DEPTH, Integer.MAX_VALUE);
+ mt.split(tok(16));
+ mt.split(tok(8));
+ mt.split(tok(4));
+ mt.split(tok(2));
+ mt.split(tok(1));
+ assertNull(mt.hash(full));
+ assertNull(mt.hash(childfull));
+ assertNull(mt.hash(invalid));
+
+ // validate the range
+ mt.get(tok(1)).hash(val);
+ mt.get(tok(2)).hash(val);
+ mt.get(tok(4)).hash(val);
+ mt.get(tok(8)).hash(val);
+ mt.get(tok(16)).hash(val);
+ mt.get(tok(0)).hash(val);
+
+ assertHashEquals(fullval, mt.hash(full));
+ assertHashEquals(childfullval, mt.hash(childfull));
+ assertNull(mt.hash(invalid));
+ }
+
+ @Test
+ public void testHashRandom()
+ {
+ int max = 1000000;
+ TOKEN_SCALE = new BigInteger("" + max);
+
+ mt = new MerkleTree(partitioner, RECOMMENDED_DEPTH, 32);
+ Random random = new Random();
+ while (true)
+ {
+ if (!mt.split(tok(random.nextInt(max))))
+ break;
+ }
+
+ // validate the tree
+ TreeRangeIterator ranges = mt.invalids(new Range(tok(0), tok(0)));
+ for (TreeRange range : ranges)
+ range.validate(new HIterator(/*empty*/ new int[0]));
+
+ assert null != mt.hash(new Range(tok(0), tok(0))) :
+ "Could not hash tree " + mt;
+ }
+
+ /**
+ * Generate two trees with different splits, but containing the same keys, and
+ * check that they compare equally.
+ *
+ * The set of keys used in this test is: #{2,4,6,8,12,14,0}
+ */
+ @Test
+ public void testValidateTree()
+ {
+ TOKEN_SCALE = new BigInteger("16"); // this test needs slightly more resolution
+
+ Range full = new Range(tok(0), tok(0));
+ Iterator<TreeRange> ranges;
+ MerkleTree mt2 = new MerkleTree(partitioner, RECOMMENDED_DEPTH, Integer.MAX_VALUE);
+
+ mt.split(tok(8));
+ mt.split(tok(4));
+ mt.split(tok(12));
+ mt.split(tok(6));
+ mt.split(tok(10));
+
+ ranges = mt.invalids(full);
+ ranges.next().validate(new HIterator(2, 4)); // (0,4]: depth 2
+ ranges.next().validate(new HIterator(6)); // (4,6]
+ ranges.next().validate(new HIterator(8)); // (6,8]
+ ranges.next().validate(new HIterator(/*empty*/ new int[0])); // (8,10]
+ ranges.next().validate(new HIterator(12)); // (10,12]
+ ranges.next().validate(new HIterator(14, 0)); // (12,0]: depth 2
+
+
+ mt2.split(tok(8));
+ mt2.split(tok(4));
+ mt2.split(tok(12));
+ mt2.split(tok(2));
+ mt2.split(tok(10));
+ mt2.split(tok(9));
+ mt2.split(tok(11));
+
+ ranges = mt2.invalids(full);
+ ranges.next().validate(new HIterator(2)); // (0,2]
+ ranges.next().validate(new HIterator(4)); // (2,4]
+ ranges.next().validate(new HIterator(6, 8)); // (4,8]: depth 2
+ ranges.next().validate(new HIterator(/*empty*/ new int[0])); // (8,9]
+ ranges.next().validate(new HIterator(/*empty*/ new int[0])); // (9,10]
+ ranges.next().validate(new HIterator(/*empty*/ new int[0])); // (10,11]: depth 4
+ ranges.next().validate(new HIterator(12)); // (11,12]: depth 4
+ ranges.next().validate(new HIterator(14, 0)); // (12,0]: depth 2
+
+ byte[] mthash = mt.hash(full);
+ byte[] mt2hash = mt2.hash(full);
+ assertHashEquals("Tree hashes did not match: " + mt + " && " + mt2, mthash, mt2hash);
+ }
+
+ @Test
+ public void testSerialization() throws Exception
+ {
+ Range full = new Range(tok(0), tok(0));
+ ByteArrayOutputStream bout = new ByteArrayOutputStream();
+ ObjectOutputStream oout = new ObjectOutputStream(bout);
+
+ // populate and validate the tree
+ mt.maxsize(256);
+ mt.init();
+ for (TreeRange range : mt.invalids(full))
+ range.validate(new HIterator(range.right()));
+
+ byte[] initialhash = mt.hash(full);
+ oout.writeObject(mt);
+ oout.close();
+
+ ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
+ ObjectInputStream oin = new ObjectInputStream(bin);
+ MerkleTree restored = (MerkleTree)oin.readObject();
+
+ // restore partitioner after serialization
+ restored.partitioner(partitioner);
+
+ assertHashEquals(initialhash, restored.hash(full));
+ }
+
+ @Test
+ public void testDifference()
+ {
+ Range full = new Range(tok(0), tok(0));
+ int maxsize = 16;
+ mt.maxsize(maxsize);
+ MerkleTree mt2 = new MerkleTree(partitioner, RECOMMENDED_DEPTH, maxsize);
+ mt.init();
+ mt2.init();
+
+ TreeRange leftmost = null;
+ TreeRange middle = null;
+ TreeRange rightmost = null;
+
+ // compact the leftmost, and split the rightmost
+ Iterator<TreeRange> ranges = mt.invalids(full);
+ leftmost = ranges.next();
+ rightmost = null;
+ while (ranges.hasNext())
+ rightmost = ranges.next();
+ mt.compact(leftmost.right());
+ leftmost = mt.get(leftmost.right()); // leftmost is now a larger range
+ mt.split(rightmost.right());
+
+ // set the hash for the left neighbor of rightmost
+ middle = mt.get(rightmost.left());
+ middle.hash("arbitrary!".getBytes());
+ byte depth = middle.depth;
+
+ // add dummy hashes to the rest of both trees
+ for (TreeRange range : mt.invalids(full))
+ range.validate(new HIterator(range.right()));
+ for (TreeRange range : mt2.invalids(full))
+ range.validate(new HIterator(range.right()));
+
+ // trees should disagree for leftmost, (middle.left, rightmost.right]
+ List<Range> diffs = MerkleTree.difference(mt, mt2);
+ assertEquals(diffs + " contains wrong number of differences:", 2, diffs.size());
+ assertTrue(diffs.contains(leftmost));
+ assertTrue(diffs.contains(new Range(middle.left(), rightmost.right())));
+ }
+
+ /**
+ * Return the root hash of a binary tree with leaves at the given depths
+ * and with the given hash val in each leaf.
+ */
+ byte[] hashed(byte[] val, Integer... depths)
+ {
+ ArrayDeque<Integer> dstack = new ArrayDeque<Integer>();
+ ArrayDeque<byte[]> hstack = new ArrayDeque<byte[]>();
+ Iterator<Integer> depthiter = Arrays.asList(depths).iterator();
+ if (depthiter.hasNext())
+ {
+ dstack.push(depthiter.next());
+ hstack.push(val);
+ }
+ while (depthiter.hasNext())
+ {
+ Integer depth = depthiter.next();
+ byte[] hash = val;
+ while (dstack.peek() == depth)
+ {
+ // consume the stack
+ hash = Hashable.binaryHash(hstack.pop(), hash);
+ depth = dstack.pop()-1;
+ }
+ dstack.push(depth);
+ hstack.push(hash);
+ }
+ assert hstack.size() == 1;
+ return hstack.pop();
+ }
+
+ static class HIterator extends AbstractIterator<RowHash> implements PeekingIterator<RowHash>
+ {
+ private Iterator<Token> tokens;
+
+ public HIterator(int... tokens)
+ {
+ List<Token> tlist = new LinkedList<Token>();
+ for (int token : tokens)
+ tlist.add(tok(token));
+ this.tokens = tlist.iterator();
+ }
+
+ public HIterator(Token... tokens)
+ {
+ this.tokens = Arrays.asList(tokens).iterator();
+ }
+
+ @Override
+ public RowHash computeNext()
+ {
+ if (tokens.hasNext())
+ return new RowHash(tokens.next(), DUMMY);
+ return endOfData();
+ }
+ }
+}