Repository: cassandra Updated Branches: refs/heads/trunk 06f626acd -> a604b14bf
BTree updates may call provided update function twice patch by Benjamin; reviewed by Benedict for CASSANDRA-8018 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/5ab1d95b Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/5ab1d95b Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/5ab1d95b Branch: refs/heads/trunk Commit: 5ab1d95b29509ee5a061eddda39d7f4189abbe37 Parents: d15c918 Author: Benedict Elliott Smith <bened...@apache.org> Authored: Tue Dec 2 17:17:35 2014 +0000 Committer: Benedict Elliott Smith <bened...@apache.org> Committed: Tue Dec 2 17:18:51 2014 +0000 ---------------------------------------------------------------------- CHANGES.txt | 1 + .../apache/cassandra/utils/btree/Builder.java | 2 +- .../cassandra/utils/btree/NodeBuilder.java | 6 +- .../org/apache/cassandra/utils/BTreeTest.java | 120 +++++++++++++++++-- 4 files changed, 117 insertions(+), 12 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/5ab1d95b/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 7df396d..c5ac66c 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -1,4 +1,5 @@ 2.1.3 + * BTree updates may call provided update function twice (CASSANDRA-8018) * Release sstable references after anticompaction (CASSANDRA-8386) * Handle abort() in SSTableRewriter properly (CASSANDRA-8320) * Fix high size calculations for prepared statements (CASSANDRA-8231) http://git-wip-us.apache.org/repos/asf/cassandra/blob/5ab1d95b/src/java/org/apache/cassandra/utils/btree/Builder.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/Builder.java b/src/java/org/apache/cassandra/utils/btree/Builder.java index f6677d4..0f2fd5b 100644 --- a/src/java/org/apache/cassandra/utils/btree/Builder.java +++ b/src/java/org/apache/cassandra/utils/btree/Builder.java @@ -109,7 +109,7 @@ final class Builder current.reset(EMPTY_LEAF, POSITIVE_INFINITY, updateF, null); for (V key : source) - current.addNewKey(key); + current.addNewKey(updateF.apply(key)); current = current.ascendToRoot(); http://git-wip-us.apache.org/repos/asf/cassandra/blob/5ab1d95b/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java b/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java index 9d57182..c715873 100644 --- a/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java +++ b/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java @@ -133,7 +133,7 @@ final class NodeBuilder int i = copyFromKeyPosition; boolean found; // exact key match? - boolean owns = true; // true iff this node (or a child) should contain the key + boolean owns = true; // true if this node (or a child) should contain the key if (i == copyFromKeyEnd) { found = false; @@ -185,7 +185,7 @@ final class NodeBuilder } else { - // if not found, we need to apply updateFunction still + // if not found, we still need to apply the update function key = updateFunction.apply(key); addNewKey(key); // handles splitting parent if necessary via ensureRoom } @@ -319,7 +319,7 @@ final class NodeBuilder void addNewKey(Object key) { ensureRoom(buildKeyPosition + 1); - buildKeys[buildKeyPosition++] = updateFunction.apply(key); + buildKeys[buildKeyPosition++] = key; } // copies children from copyf to the builder, up to the provided index in copyf (exclusive) http://git-wip-us.apache.org/repos/asf/cassandra/blob/5ab1d95b/test/unit/org/apache/cassandra/utils/BTreeTest.java ---------------------------------------------------------------------- diff --git a/test/unit/org/apache/cassandra/utils/BTreeTest.java b/test/unit/org/apache/cassandra/utils/BTreeTest.java index a6d4528..e1bf388 100644 --- a/test/unit/org/apache/cassandra/utils/BTreeTest.java +++ b/test/unit/org/apache/cassandra/utils/BTreeTest.java @@ -17,22 +17,21 @@ */ package org.apache.cassandra.utils; -import java.util.ArrayList; -import java.util.Comparator; -import java.util.List; -import java.util.Random; +import java.util.*; import java.util.concurrent.ThreadLocalRandom; import org.junit.Test; -import junit.framework.Assert; import org.apache.cassandra.utils.btree.BTree; import org.apache.cassandra.utils.btree.BTreeSet; import org.apache.cassandra.utils.btree.UpdateFunction; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertArrayEquals; +import static org.junit.Assert.assertTrue; + public class BTreeTest { - static Integer[] ints = new Integer[20]; static { @@ -114,13 +113,78 @@ public class BTreeTest } } + /** + * Tests that the apply method of the <code>UpdateFunction</code> is only called once with each key update. + * (see CASSANDRA-8018). + */ + @Test + public void testUpdate_UpdateFunctionCallBack() + { + Object[] btree = new Object[0]; + CallsMonitor monitor = new CallsMonitor(); + + btree = BTree.update(btree, CMP, Arrays.asList(1), true, monitor); + assertArrayEquals(new Object[] {1, null}, btree); + assertEquals(1, monitor.getNumberOfCalls(1)); + + monitor.clear(); + btree = BTree.update(btree, CMP, Arrays.asList(2), true, monitor); + assertArrayEquals(new Object[] {1, 2}, btree); + assertEquals(1, monitor.getNumberOfCalls(2)); + + // with existing value + monitor.clear(); + btree = BTree.update(btree, CMP, Arrays.asList(1), true, monitor); + assertArrayEquals(new Object[] {1, 2}, btree); + assertEquals(1, monitor.getNumberOfCalls(1)); + + // with two non-existing values + monitor.clear(); + btree = BTree.update(btree, CMP, Arrays.asList(3, 4), true, monitor); + assertArrayEquals(new Object[] {1, 2, 3, 4}, btree); + assertEquals(1, monitor.getNumberOfCalls(3)); + assertEquals(1, monitor.getNumberOfCalls(4)); + + // with one existing value and one non existing value in disorder + monitor.clear(); + btree = BTree.update(btree, CMP, Arrays.asList(5, 2), false, monitor); + assertArrayEquals(new Object[] {3, new Object[]{1, 2}, new Object[]{4, 5}}, btree); + assertEquals(1, monitor.getNumberOfCalls(2)); + assertEquals(1, monitor.getNumberOfCalls(5)); + } + + /** + * Tests that the apply method of the <code>UpdateFunction</code> is only called once per value with each build call. + */ + @Test + public void testBuilding_UpdateFunctionCallBack() + { + CallsMonitor monitor = new CallsMonitor(); + Object[] btree = BTree.build(Arrays.asList(1), CMP, true, monitor); + assertArrayEquals(new Object[] {1, null}, btree); + assertEquals(1, monitor.getNumberOfCalls(1)); + + monitor.clear(); + btree = BTree.build(Arrays.asList(1, 2), CMP, true, monitor); + assertArrayEquals(new Object[] {1, 2}, btree); + assertEquals(1, monitor.getNumberOfCalls(1)); + assertEquals(1, monitor.getNumberOfCalls(2)); + + monitor.clear(); + btree = BTree.build(Arrays.asList(3, 1, 2), CMP, false, monitor); + assertArrayEquals(new Object[] {1, 2, 3, null}, btree); + assertEquals(1, monitor.getNumberOfCalls(1)); + assertEquals(1, monitor.getNumberOfCalls(2)); + assertEquals(1, monitor.getNumberOfCalls(3)); + } + private static void checkResult(int count, Object[] btree) { BTreeSet<Integer> vs = new BTreeSet<>(btree, CMP); assert vs.size() == count; int i = 0; for (Integer j : vs) - Assert.assertEquals(j, ints[i++]); + assertEquals(j, ints[i++]); } @Test @@ -137,7 +201,7 @@ public class BTreeTest Object[] btree = BTree.build(ranges(range(0, 8)), cmp, true, UpdateFunction.NoOp.<String>instance()); BTree.update(btree, cmp, ranges(range(0, 94)), false, new AbortAfterX(90)); btree = BTree.update(btree, cmp, ranges(range(0, 94)), false, UpdateFunction.NoOp.<String>instance()); - Assert.assertTrue(BTree.isWellFormed(btree, cmp)); + assertTrue(BTree.isWellFormed(btree, cmp)); } private static final class AbortAfterX implements UpdateFunction<String> @@ -181,4 +245,44 @@ public class BTreeTest } return r; } + + /** + * <code>UpdateFunction</code> that count the number of call made to apply for each value. + */ + public static final class CallsMonitor implements UpdateFunction<Integer> + { + private int[] numberOfCalls = new int[20]; + + public Integer apply(Integer replacing, Integer update) + { + numberOfCalls[update] = numberOfCalls[update] + 1; + return update; + } + + public boolean abortEarly() + { + return false; + } + + public void allocated(long heapSize) + { + + } + + public Integer apply(Integer integer) + { + numberOfCalls[integer] = numberOfCalls[integer] + 1; + return integer; + } + + public int getNumberOfCalls(Integer key) + { + return numberOfCalls[key]; + } + + public void clear() + { + Arrays.fill(numberOfCalls, 0); + } + }; }
