Repository: cassandra Updated Branches: refs/heads/cassandra-2.1 caf609cf6 -> 0cb1e3d24 refs/heads/trunk f32c4da2b -> c1647c59e
apply BTree update function correctly patch by Benedict Elliott Smith; reviewed by jbellis for CASSANDRA-6692 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/0cb1e3d2 Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/0cb1e3d2 Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/0cb1e3d2 Branch: refs/heads/cassandra-2.1 Commit: 0cb1e3d248eb3d14f197217256d8ec29c4b3717c Parents: 6041433 Author: Jonathan Ellis <[email protected]> Authored: Wed Mar 12 18:29:40 2014 -0500 Committer: Jonathan Ellis <[email protected]> Committed: Wed Mar 12 18:30:04 2014 -0500 ---------------------------------------------------------------------- CHANGES.txt | 2 +- .../org/apache/cassandra/utils/btree/BTree.java | 49 ++++++-- .../apache/cassandra/utils/btree/Builder.java | 8 +- .../cassandra/utils/btree/NodeBuilder.java | 2 +- .../cassandra/utils/btree/UpdateFunction.java | 1 - .../org/apache/cassandra/utils/BTreeTest.java | 125 +++++++++++++++++++ 6 files changed, 171 insertions(+), 16 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/0cb1e3d2/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index d346499..912e6af 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -6,7 +6,7 @@ * Add broadcast_rpc_address option to cassandra.yaml (CASSANDRA-5899) * Auto reload GossipingPropertyFileSnitch config (CASSANDRA-5897) * Fix overflow of memtable_total_space_in_mb (CASSANDRA-6573) - * Fix ABTC NPE (CASSANDRA-6692) + * Fix ABTC NPE and apply update function correctly (CASSANDRA-6692) * Allow nodetool to use a file or prompt for password (CASSANDRA-6660) * Fix AIOOBE when concurrently accessing ABSC (CASSANDRA-6742) * Fix assertion error in ALTER TYPE RENAME (CASSANDRA-6705) http://git-wip-us.apache.org/repos/asf/cassandra/blob/0cb1e3d2/src/java/org/apache/cassandra/utils/btree/BTree.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/BTree.java b/src/java/org/apache/cassandra/utils/btree/BTree.java index 69cf145..ad5065e 100644 --- a/src/java/org/apache/cassandra/utils/btree/BTree.java +++ b/src/java/org/apache/cassandra/utils/btree/BTree.java @@ -83,6 +83,11 @@ public class BTree return EMPTY_LEAF; } + public static <V> Object[] build(Collection<V> source, Comparator<V> comparator, boolean sorted, UpdateFunction<V> updateF) + { + return build(source, source.size(), comparator, sorted, updateF); + } + /** * Creates a BTree containing all of the objects in the provided collection * @@ -92,17 +97,23 @@ public class BTree * @param <V> * @return */ - public static <V> Object[] build(Collection<V> source, Comparator<V> comparator, boolean sorted, UpdateFunction<V> updateF) + public static <V> Object[] build(Iterable<V> source, int size, Comparator<V> comparator, boolean sorted, UpdateFunction<V> updateF) { - int size = source.size(); - if (size < FAN_FACTOR) { // pad to even length to match contract that all leaf nodes are even - V[] values = source.toArray((V[]) new Object[size + (size & 1)]); + V[] values = (V[]) new Object[size + (size & 1)]; + { + int i = 0; + for (V v : source) + values[i++] = v; + } + // inline sorting since we're already calling toArray if (!sorted) Arrays.sort(values, 0, size, comparator); + + // if updateF is specified if (updateF != null) { for (int i = 0 ; i < size ; i++) @@ -119,7 +130,7 @@ public class BTree Builder builder = queue.poll(); if (builder == null) builder = new Builder(); - Object[] btree = builder.build(source, size); + Object[] btree = builder.build(source, updateF, size); queue.add(builder); return btree; } @@ -139,6 +150,15 @@ public class BTree return update(btree, comparator, updateWith, updateWithIsSorted, UpdateFunction.NoOp.<V>instance()); } + public static <V> Object[] update(Object[] btree, + Comparator<V> comparator, + Collection<V> updateWith, + boolean updateWithIsSorted, + UpdateFunction<V> updateF) + { + return update(btree, comparator, updateWith, updateWith.size(), updateWithIsSorted, updateF); + } + /** * Returns a new BTree with the provided set inserting/replacing as necessary any equal items * @@ -152,15 +172,16 @@ public class BTree */ public static <V> Object[] update(Object[] btree, Comparator<V> comparator, - Collection<V> updateWith, + Iterable<V> updateWith, + int updateWithLength, boolean updateWithIsSorted, UpdateFunction<V> updateF) { if (btree.length == 0) - return build(updateWith, comparator, updateWithIsSorted, updateF); + return build(updateWith, updateWithLength, comparator, updateWithIsSorted, updateF); if (!updateWithIsSorted) - updateWith = sorted(updateWith, comparator, updateWith.size()); + updateWith = sorted(updateWith, comparator, updateWithLength); Queue<Builder> queue = modifier.get(); Builder builder = queue.poll(); @@ -316,6 +337,11 @@ public class BTree return (node.length & 1) == 0; } + public static boolean isEmpty(Object[] tree) + { + return tree.length == 0; + } + // Special class for making certain operations easier, so we can define a +/- Inf private static interface Special extends Comparable<Object> { } static final Special POSITIVE_INFINITY = new Special() @@ -343,9 +369,12 @@ public class BTree }; // return a sorted collection - private static <V> Collection<V> sorted(Collection<V> collection, Comparator<V> comparator, int size) + private static <V> Collection<V> sorted(Iterable<V> source, Comparator<V> comparator, int size) { - V[] vs = collection.toArray((V[]) new Object[size]); + V[] vs = (V[]) new Object[size]; + int i = 0; + for (V v : source) + vs[i++] = v; Arrays.sort(vs, comparator); return Arrays.asList(vs); } http://git-wip-us.apache.org/repos/asf/cassandra/blob/0cb1e3d2/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 03a7941..36325fe 100644 --- a/src/java/org/apache/cassandra/utils/btree/Builder.java +++ b/src/java/org/apache/cassandra/utils/btree/Builder.java @@ -55,7 +55,7 @@ final class Builder * we assume @param source has been sorted, e.g. by BTree.update, so the update of each key resumes where * the previous left off. */ - public <V> Object[] update(Object[] btree, Comparator<V> comparator, Collection<V> source, UpdateFunction<V> updateF) + public <V> Object[] update(Object[] btree, Comparator<V> comparator, Iterable<V> source, UpdateFunction<V> updateF) { assert updateF != null; @@ -97,15 +97,17 @@ final class Builder return r; } - public <V> Object[] build(Collection<V> source, int size) + public <V> Object[] build(Iterable<V> source, UpdateFunction<V> updateF, int size) { + assert updateF != null; + NodeBuilder current = rootBuilder; // we descend only to avoid wasting memory; in update() we will often descend into existing trees // so here we want to descend also, so we don't have lg max(N) depth in both directions while ((size >>= FAN_SHIFT) > 0) current = current.ensureChild(); - current.reset(EMPTY_LEAF, POSITIVE_INFINITY, UpdateFunction.NoOp.instance(), null); + current.reset(EMPTY_LEAF, POSITIVE_INFINITY, updateF, null); for (V key : source) current.addNewKey(key); http://git-wip-us.apache.org/repos/asf/cassandra/blob/0cb1e3d2/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 759ffaa..7039380 100644 --- a/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java +++ b/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java @@ -280,7 +280,7 @@ final class NodeBuilder void addNewKey(Object key) { ensureRoom(buildKeyPosition + 1); - buildKeys[buildKeyPosition++] = key; + buildKeys[buildKeyPosition++] = updateFunction.apply(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/0cb1e3d2/src/java/org/apache/cassandra/utils/btree/UpdateFunction.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/UpdateFunction.java b/src/java/org/apache/cassandra/utils/btree/UpdateFunction.java index e4062a4..355028e 100644 --- a/src/java/org/apache/cassandra/utils/btree/UpdateFunction.java +++ b/src/java/org/apache/cassandra/utils/btree/UpdateFunction.java @@ -19,7 +19,6 @@ package org.apache.cassandra.utils.btree; import com.google.common.base.Function; - /** * An interface defining a function to be applied to both the object we are replacing in a BTree and * the object that is intended to replace it, returning the object to actually replace it. http://git-wip-us.apache.org/repos/asf/cassandra/blob/0cb1e3d2/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 new file mode 100644 index 0000000..b4a960b --- /dev/null +++ b/test/unit/org/apache/cassandra/utils/BTreeTest.java @@ -0,0 +1,125 @@ +/* + * 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.util.ArrayList; +import java.util.Comparator; +import java.util.List; +import java.util.Random; +import java.util.concurrent.ThreadLocalRandom; + +import org.junit.Test; + +import org.apache.cassandra.utils.btree.BTree; +import org.apache.cassandra.utils.btree.BTreeSet; +import org.apache.cassandra.utils.btree.UpdateFunction; + +public class BTreeTest +{ + + static Integer[] ints = new Integer[20]; + static + { + System.setProperty("cassandra.btree.fanfactor", "4"); + for (int i = 0 ; i < ints.length ; i++) + ints[i] = new Integer(i); + } + + static final UpdateFunction<Integer> updateF = new UpdateFunction<Integer>() + { + public Integer apply(Integer replacing, Integer update) + { + return ints[update]; + } + + public boolean abortEarly() + { + return false; + } + + public void allocated(long heapSize) + { + + } + + public Integer apply(Integer integer) + { + return ints[integer]; + } + }; + + private static List<Integer> seq(int count) + { + List<Integer> r = new ArrayList<>(); + for (int i = 0 ; i < count ; i++) + r.add(i); + return r; + } + + private static List<Integer> rand(int count) + { + Random rand = ThreadLocalRandom.current(); + List<Integer> r = seq(count); + for (int i = 0 ; i < count - 1 ; i++) + { + int swap = i + rand.nextInt(count - i); + Integer tmp = r.get(i); + r.set(i, r.get(swap)); + r.set(swap, tmp); + } + return r; + } + + private static final Comparator<Integer> CMP = new Comparator<Integer>() + { + public int compare(Integer o1, Integer o2) + { + return Integer.compare(o1, o2); + } + }; + + @Test + public void testBuilding_UpdateFunctionReplacement() + { + for (int i = 0; i < 20 ; i++) + { + checkResult(i, BTree.build(seq(i), CMP, true, updateF)); + checkResult(i, BTree.build(rand(i), CMP, false, updateF)); + } + } + + @Test + public void testUpdate_UpdateFunctionReplacement() + { + for (int i = 0; i < 20 ; i++) + { + checkResult(i, BTree.update(BTree.build(seq(i), CMP, true, UpdateFunction.NoOp.<Integer>instance()), CMP, seq(i), true, updateF)); + checkResult(i, BTree.update(BTree.build(rand(i), CMP, false, UpdateFunction.NoOp.<Integer>instance()), CMP, rand(i), false, updateF)); + } + } + + 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 j == ints[i++]; + } + +}
