cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject [1/5] git commit: apply BTree update function correctly patch by Benedict Elliott Smith; reviewed by jbellis for CASSANDRA-6692
Date Wed, 12 Mar 2014 23:30:26 GMT
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 <jbellis@apache.org>
Authored: Wed Mar 12 18:29:40 2014 -0500
Committer: Jonathan Ellis <jbellis@apache.org>
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++];
+    }
+
+}


Mime
View raw message