cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject svn commit: r1057652 - in /cassandra/trunk: src/java/org/apache/cassandra/db/context/ src/java/org/apache/cassandra/utils/ test/unit/org/apache/cassandra/db/ test/unit/org/apache/cassandra/db/context/
Date Tue, 11 Jan 2011 14:18:33 GMT
Author: jbellis
Date: Tue Jan 11 14:18:33 2011
New Revision: 1057652

URL: http://svn.apache.org/viewvc?rev=1057652&view=rev
Log:
Keep partitioned counter contexts sorted
patch by slebresne; reviewed by Kelvin Kakugawa for CASSANDRA-1937

Modified:
    cassandra/trunk/src/java/org/apache/cassandra/db/context/CounterContext.java
    cassandra/trunk/src/java/org/apache/cassandra/utils/FBUtilities.java
    cassandra/trunk/test/unit/org/apache/cassandra/db/CounterColumnTest.java
    cassandra/trunk/test/unit/org/apache/cassandra/db/SuperColumnTest.java
    cassandra/trunk/test/unit/org/apache/cassandra/db/context/CounterContextTest.java

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/context/CounterContext.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/context/CounterContext.java?rev=1057652&r1=1057651&r2=1057652&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/context/CounterContext.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/context/CounterContext.java Tue Jan 11
14:18:33 2011
@@ -46,7 +46,7 @@ import org.apache.cassandra.utils.FBUtil
 public class CounterContext implements IContext
 {
     private static final int idLength;
-    private static final FBUtilities.ByteArrayWrapper idWrapper;
+    private static final byte[] localId;
     private static final int clockLength = DBConstants.longSize_;
     private static final int countLength = DBConstants.longSize_;
     private static final int stepLength; // length: id + logical clock + count
@@ -59,9 +59,8 @@ public class CounterContext implements I
 
     static
     {
-        byte[] id  = FBUtilities.getLocalAddress().getAddress();
-        idLength   = id.length;
-        idWrapper  = new FBUtilities.ByteArrayWrapper(id);
+        localId  = FBUtilities.getLocalAddress().getAddress();
+        idLength   = localId.length;
         stepLength = idLength + clockLength + countLength;
     }
 
@@ -95,103 +94,45 @@ public class CounterContext implements I
         FBUtilities.copyIntoBytes(context, offset + idLength + clockLength, count);
     }
 
+    public byte[] insertElementAtStepOffset(byte[] context, int stepOffset, byte[] id, long
clock, long count)
+    {
+        int offset = stepOffset * stepLength;
+        byte[] newContext = new byte[context.length + stepLength];
+        System.arraycopy(context, 0, newContext, 0, offset);
+        writeElementAtStepOffset(newContext, stepOffset, id, clock, count);
+        System.arraycopy(context, offset, newContext, offset + stepLength, context.length
- offset);
+        return newContext;
+    }
+
     public byte[] update(byte[] context, InetAddress node, long delta)
     {
         // calculate node id
         byte[] nodeId = node.getAddress();
+        int idCount = context.length / stepLength;
 
         // look for this node id
-        for (int offset = 0; offset < context.length; offset += stepLength)
-        {
-            if (FBUtilities.compareByteSubArrays(nodeId, 0, context, offset, idLength) !=
0)
-                continue;
-
-            // node id found: increment clock, update count; shift to front
-            long clock = FBUtilities.byteArrayToLong(context, offset + idLength);
-            long count = FBUtilities.byteArrayToLong(context, offset + idLength + clockLength);
-
-            System.arraycopy(
-                context,
-                0,
-                context,
-                stepLength,
-                offset);
-            writeElement(context, nodeId, clock + 1L, count + delta);
-
-            return context;
-        }
-
-        // node id not found: widen context
-        byte[] previous = context;
-        context = new byte[previous.length + stepLength];
-
-        writeElement(context, nodeId, 1L, delta);
-        System.arraycopy(
-            previous,
-            0,
-            context,
-            stepLength,
-            previous.length);
-
-        return context;
-    }
-
-    // swap bytes of step length in context
-    protected static void swapElement(byte[] context, int left, int right)
-    {
-        if (left == right) return;
-
-        byte temp;
-        for (int i = 0; i < stepLength; i++)
+        for (int stepOffset = 0; stepOffset < idCount; ++stepOffset)
         {
-            temp = context[left+i];
-            context[left+i] = context[right+i];
-            context[right+i] = temp;
-        }
-    }
-
-    // partition bytes of step length in context (for quicksort)
-    protected static int partitionElements(byte[] context, int left, int right, int pivotIndex)
-    {
-        int leftOffset  = left       * stepLength;
-        int rightOffset = right      * stepLength;
-        int pivotOffset = pivotIndex * stepLength;
+            int offset = stepOffset * stepLength;
+            int cmp = FBUtilities.compareByteSubArrays(nodeId, 0, context, offset, idLength);
+            if (cmp == 0)
+            {
+                // node id found: increment clock, update count; shift to front
+                long clock = FBUtilities.byteArrayToLong(context, offset + idLength);
+                long count = FBUtilities.byteArrayToLong(context, offset + idLength + clockLength);
 
-        byte[] pivotValue = ArrayUtils.subarray(context, pivotOffset, pivotOffset + stepLength);
-        swapElement(context, pivotOffset, rightOffset);
-        int storeOffset = leftOffset;
-        for (int i = leftOffset; i < rightOffset; i += stepLength)
-        {
-            if (FBUtilities.compareByteSubArrays(context, i, pivotValue, 0, stepLength) <=
0)
+                writeElementAtStepOffset(context, stepOffset, nodeId, clock + 1L, count +
delta);
+                return context;
+            }
+            if (cmp < 0)
             {
-                swapElement(context, i, storeOffset);
-                storeOffset += stepLength;
+                // id at offset is greater that the one we are updating, inserting
+                return insertElementAtStepOffset(context, stepOffset, nodeId, 1L, delta);
             }
         }
-        swapElement(context, storeOffset, rightOffset);
-        return storeOffset / stepLength;
-    }
 
-    // quicksort helper
-    protected static void sortElementsByIdHelper(byte[] context, int left, int right)
-    {
-        if (right <= left) return;
-
-        int pivotIndex = (left + right) / 2;
-        int pivotIndexNew = partitionElements(context, left, right, pivotIndex);
-        sortElementsByIdHelper(context, left, pivotIndexNew - 1);
-        sortElementsByIdHelper(context, pivotIndexNew + 1, right);
-    }
-
-    // quicksort context by id
-    protected static byte[] sortElementsById(byte[] context)
-    {
-        assert 0 == (context.length % stepLength) : "context size is not correct.";
-        sortElementsByIdHelper(
-            context,
-            0,
-            (int)(context.length / stepLength) - 1);
-        return context;
+        // node id not found: adding at the end
+        return insertElementAtStepOffset(context, idCount, nodeId, 1L, delta);
     }
 
     /**
@@ -213,9 +154,6 @@ public class CounterContext implements I
      */
     public ContextRelationship diff(byte[] left, byte[] right)
     {
-        left  = sortElementsById(left);
-        right = sortElementsById(right);
-
         ContextRelationship relationship = ContextRelationship.EQUAL;
 
         int leftIndex  = 0;
@@ -382,87 +320,99 @@ public class CounterContext implements I
      */
     public byte[] merge(byte[] left, byte[] right)
     {
-        // strategy:
-        //   1) map id -> (clock, count)
-        //      a) local id:  sum clocks, counts
-        //      b) remote id: keep highest clock, count (reconcile)
-        //   2) create a context from sorted array
-        Map<FBUtilities.ByteArrayWrapper, CounterNode> contextsMap =
-            new HashMap<FBUtilities.ByteArrayWrapper, CounterNode>();
-
-        // map left context: id -> (clock, count)
-        for (int offset = 0; offset < left.length; offset += stepLength)
+        if (left.length > right.length)
         {
-            FBUtilities.ByteArrayWrapper id = new FBUtilities.ByteArrayWrapper(
-                ArrayUtils.subarray(left, offset, offset + idLength));
-            long clock = FBUtilities.byteArrayToLong(left, offset + idLength);
-            long count = FBUtilities.byteArrayToLong(left, offset + idLength + clockLength);
-
-            contextsMap.put(id, new CounterNode(clock, count));
+            byte[] tmp = right;
+            right = left;
+            left = tmp;
         }
 
-        // map right context: id -> (clock, count)
-        for (int offset = 0; offset < right.length; offset += stepLength)
+        // Compute size of result
+        int size = 0;
+        int leftOffset  = 0;
+        int rightOffset = 0;
+        while ((leftOffset < left.length) && (rightOffset < right.length))
         {
-            FBUtilities.ByteArrayWrapper id = new FBUtilities.ByteArrayWrapper(
-                ArrayUtils.subarray(right, offset, offset + idLength));
-            long clock = FBUtilities.byteArrayToLong(right, offset + idLength);
-            long count = FBUtilities.byteArrayToLong(right, offset + idLength + clockLength);
-
-            if (!contextsMap.containsKey(id))
+            int cmp = FBUtilities.compareByteSubArrays(left, leftOffset, right, rightOffset,
idLength);
+            if (cmp == 0)
             {
-                contextsMap.put(id, new CounterNode(clock, count));
-                continue;
+                ++size;
+                rightOffset += stepLength;
+                leftOffset += stepLength;
             }
-
-            CounterNode node = contextsMap.get(id);
-
-            // local id: sum clocks, counts
-            if (this.idWrapper.equals(id))
+            else if (cmp > 0)
             {
-                contextsMap.put(id, new CounterNode(
-                    clock + node.clock,
-                    count + node.count));
-                continue;
+                ++size;
+                rightOffset += stepLength;
             }
-
-            // remote id: keep highest clock and its count
-            if (node.clock < clock)
+            else // cmp < 0
             {
-                contextsMap.put(id, new CounterNode(clock, count));
+                ++size;
+                leftOffset += stepLength;
             }
         }
+        size += (left.length  - leftOffset)  / stepLength;
+        size += (right.length - rightOffset) / stepLength;
+
+        byte[] merged = new byte[size * stepLength];
 
-        // sort merged tuples
-        List<Map.Entry<FBUtilities.ByteArrayWrapper, CounterNode>> contextsList
=
-            new ArrayList<Map.Entry<FBUtilities.ByteArrayWrapper, CounterNode>>(
-                    contextsMap.entrySet());
-        Collections.sort(
-            contextsList,
-            new Comparator<Map.Entry<FBUtilities.ByteArrayWrapper, CounterNode>>()
+        // Do the actual merge:
+        //   a) local id:  sum clocks, counts
+        //   b) remote id: keep highest clock, count (reconcile)
+        int mergedOffset = 0; leftOffset = 0; rightOffset = 0;
+        while ((leftOffset < left.length) && (rightOffset < right.length))
+        {
+            int cmp = FBUtilities.compareByteSubArrays(left, leftOffset, right, rightOffset,
idLength);
+            if (cmp == 0)
             {
-                public int compare(
-                    Map.Entry<FBUtilities.ByteArrayWrapper, CounterNode> e1,
-                    Map.Entry<FBUtilities.ByteArrayWrapper, CounterNode> e2)
+                // sum for local id, keep highest othewise
+                long leftClock = FBUtilities.byteArrayToLong(left, leftOffset + idLength);
+                long rightClock = FBUtilities.byteArrayToLong(right, rightOffset + idLength);
+                if (FBUtilities.compareByteSubArrays(left, leftOffset, localId, 0, idLength)
== 0)
                 {
-                    // reversed
-                    return e2.getValue().compareClockTo(e1.getValue());
+                    long leftCount = FBUtilities.byteArrayToLong(left, leftOffset + idLength
+ clockLength);
+                    long rightCount = FBUtilities.byteArrayToLong(right, rightOffset + idLength
+ clockLength);
+                    writeElementAtStepOffset(merged, mergedOffset / stepLength, localId,
leftClock + rightClock, leftCount + rightCount);
                 }
-            });
-
-        // create merged context
-        int length = contextsList.size();
-        byte[] merged = new byte[length * stepLength];
-        for (int i = 0; i < length; i++)
-        {
-            Map.Entry<FBUtilities.ByteArrayWrapper, CounterNode> entry = contextsList.get(i);
-            writeElementAtStepOffset(
-                merged,
-                i,
-                entry.getKey().data,
-                entry.getValue().clock,
-                entry.getValue().count);
+                else
+                {
+                    if (leftClock >= rightClock)
+                        System.arraycopy(left, leftOffset, merged, mergedOffset, stepLength);
+                    else
+                        System.arraycopy(right, rightOffset, merged, mergedOffset, stepLength);
+                }
+                mergedOffset += stepLength;
+                rightOffset += stepLength;
+                leftOffset += stepLength;
+            }
+            else if (cmp > 0)
+            {
+                System.arraycopy(right, rightOffset, merged, mergedOffset, stepLength);
+                mergedOffset += stepLength;
+                rightOffset += stepLength;
+            }
+            else // cmp < 0
+            {
+                System.arraycopy(left, leftOffset, merged, mergedOffset, stepLength);
+                mergedOffset += stepLength;
+                leftOffset += stepLength;
+            }
         }
+        if (leftOffset < left.length)
+            System.arraycopy(
+                left,
+                leftOffset,
+                merged,
+                mergedOffset,
+                left.length - leftOffset);
+        if (rightOffset < right.length)
+            System.arraycopy(
+                right,
+                rightOffset,
+                merged,
+                mergedOffset,
+                right.length - rightOffset);
+
         return merged;
     }
 
@@ -528,19 +478,26 @@ public class CounterContext implements I
         // look for this node id
         for (int offset = 0; offset < context.length; offset += stepLength)
         {
-            if (FBUtilities.compareByteSubArrays(context, offset, nodeId, 0, idLength) !=
0)
+            int cmp = FBUtilities.compareByteSubArrays(context, offset, nodeId, 0, idLength);
+            if (cmp < 0)
                 continue;
-
-            // node id found: remove node count
-            byte[] truncatedContext = new byte[context.length - stepLength];
-            System.arraycopy(context, 0, truncatedContext, 0, offset);
-            System.arraycopy(
-                context,
-                offset + stepLength,
-                truncatedContext,
-                offset,
-                context.length - (offset + stepLength));
-            return truncatedContext;
+            else if (cmp == 0)
+            {
+                // node id found: remove node count
+                byte[] truncatedContext = new byte[context.length - stepLength];
+                System.arraycopy(context, 0, truncatedContext, 0, offset);
+                System.arraycopy(
+                        context,
+                        offset + stepLength,
+                        truncatedContext,
+                        offset,
+                        context.length - (offset + stepLength));
+                return truncatedContext;
+            }
+            else // cmp > 0
+            {
+                break; // node id not present
+            }
         }
 
         return context;

Modified: cassandra/trunk/src/java/org/apache/cassandra/utils/FBUtilities.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/utils/FBUtilities.java?rev=1057652&r1=1057651&r2=1057652&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/utils/FBUtilities.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/utils/FBUtilities.java Tue Jan 11 14:18:33
2011
@@ -637,43 +637,6 @@ public class FBUtilities
         return Charsets.UTF_8.newDecoder().decode(bytes.duplicate()).toString();
     }
 
-    /** 
-     * Thin wrapper around byte[] to provide meaningful equals() and hashCode() operations
-     * caveat: assumed that wrapped byte[] will not be modified
-     */
-    public static final class ByteArrayWrapper
-    {
-        public final byte[] data;
-
-        public ByteArrayWrapper(byte[] data)
-        {
-            if ( null == data )
-            {
-                throw new NullPointerException();
-            }
-            this.data = data;
-        }
-
-        public boolean equals(Object other)
-        {
-            if ( !( other instanceof ByteArrayWrapper ) )
-            {
-                return false;
-            }
-            return Arrays.equals(data, ((ByteArrayWrapper)other).data);
-        }
-
-        public int hashCode()
-        {
-            return Arrays.hashCode(data);
-        }
-
-        public String toString()
-        {
-            return ArrayUtils.toString(data);
-        }
-    }
-
     public static String resourceToFile(String filename) throws ConfigurationException
     {
         ClassLoader loader = PropertyFileSnitch.class.getClassLoader();

Modified: cassandra/trunk/test/unit/org/apache/cassandra/db/CounterColumnTest.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/db/CounterColumnTest.java?rev=1057652&r1=1057651&r2=1057652&view=diff
==============================================================================
--- cassandra/trunk/test/unit/org/apache/cassandra/db/CounterColumnTest.java (original)
+++ cassandra/trunk/test/unit/org/apache/cassandra/db/CounterColumnTest.java Tue Jan 11 14:18:33
2011
@@ -106,13 +106,13 @@ public class CounterColumnTest
 
         assert c.partitionedCounter().length == (2 * stepLength);
 
-        assert   2 == FBUtilities.byteArrayToInt(c.partitionedCounter(),  0*stepLength);
-        assert  3L == FBUtilities.byteArrayToLong(c.partitionedCounter(), 0*stepLength +
idLength);
-        assert 14L == FBUtilities.byteArrayToLong(c.partitionedCounter(), 0*stepLength +
idLength + clockLength);
-
-        assert  1 == FBUtilities.byteArrayToInt(c.partitionedCounter(),  1*stepLength);
-        assert 1L == FBUtilities.byteArrayToLong(c.partitionedCounter(), 1*stepLength + idLength);
-        assert 1L == FBUtilities.byteArrayToLong(c.partitionedCounter(), 1*stepLength + idLength
+ clockLength);
+        assert  1 == FBUtilities.byteArrayToInt(c.partitionedCounter(),  0*stepLength);
+        assert 1L == FBUtilities.byteArrayToLong(c.partitionedCounter(), 0*stepLength + idLength);
+        assert 1L == FBUtilities.byteArrayToLong(c.partitionedCounter(), 0*stepLength + idLength
+ clockLength);
+
+        assert   2 == FBUtilities.byteArrayToInt(c.partitionedCounter(),  1*stepLength);
+        assert  3L == FBUtilities.byteArrayToLong(c.partitionedCounter(), 1*stepLength +
idLength);
+        assert 14L == FBUtilities.byteArrayToLong(c.partitionedCounter(), 1*stepLength +
idLength + clockLength);
     }
 
     @Test
@@ -204,8 +204,9 @@ public class CounterColumnTest
         right = new CounterColumn(ByteBufferUtil.bytes("x"), ByteBuffer.wrap(cc.total(context)),
3L, context, 4L);
 
         reconciled = left.reconcile(right);
+
         assert reconciled.name() == left.name();
-        assert 9L == reconciled.value().getLong(reconciled.value().arrayOffset());
+        assert 9L == reconciled.value().getLong(reconciled.value().position());
         assert reconciled.timestamp() == 9L;
 
         context = ((CounterColumn)reconciled).partitionedCounter();

Modified: cassandra/trunk/test/unit/org/apache/cassandra/db/SuperColumnTest.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/db/SuperColumnTest.java?rev=1057652&r1=1057651&r2=1057652&view=diff
==============================================================================
--- cassandra/trunk/test/unit/org/apache/cassandra/db/SuperColumnTest.java (original)
+++ cassandra/trunk/test/unit/org/apache/cassandra/db/SuperColumnTest.java Tue Jan 11 14:18:33
2011
@@ -50,24 +50,24 @@ public class SuperColumnTest
     	SuperColumn sc = new SuperColumn(ByteBufferUtil.bytes("sc1"), LongType.instance);
 
         context = concatByteArrays(
-            FBUtilities.getLocalAddress().getAddress(), FBUtilities.toByteArray(3L), FBUtilities.toByteArray(3L),
             FBUtilities.toByteArray(1), FBUtilities.toByteArray(7L), FBUtilities.toByteArray(0L),
             FBUtilities.toByteArray(2), FBUtilities.toByteArray(5L), FBUtilities.toByteArray(7L),
-            FBUtilities.toByteArray(4), FBUtilities.toByteArray(2L), FBUtilities.toByteArray(9L)
+            FBUtilities.toByteArray(4), FBUtilities.toByteArray(2L), FBUtilities.toByteArray(9L),
+            FBUtilities.getLocalAddress().getAddress(), FBUtilities.toByteArray(3L), FBUtilities.toByteArray(3L)
             );
     	sc.addColumn(new CounterColumn(getBytes(1), ByteBuffer.wrap(cc.total(context)), 3L,
context, 0L));
         context = concatByteArrays(
-            FBUtilities.getLocalAddress().getAddress(), FBUtilities.toByteArray(9L), FBUtilities.toByteArray(5L),
-            FBUtilities.toByteArray(8), FBUtilities.toByteArray(9L), FBUtilities.toByteArray(0L),
+            FBUtilities.toByteArray(2), FBUtilities.toByteArray(3L), FBUtilities.toByteArray(4L),
             FBUtilities.toByteArray(4), FBUtilities.toByteArray(4L), FBUtilities.toByteArray(1L),
-            FBUtilities.toByteArray(2), FBUtilities.toByteArray(3L), FBUtilities.toByteArray(4L)
+            FBUtilities.toByteArray(8), FBUtilities.toByteArray(9L), FBUtilities.toByteArray(0L),
+            FBUtilities.getLocalAddress().getAddress(), FBUtilities.toByteArray(9L), FBUtilities.toByteArray(5L)
             );
     	sc.addColumn(new CounterColumn(getBytes(1), ByteBuffer.wrap(cc.total(context)), 10L,
context, 0L));
 
         context = concatByteArrays(
+            FBUtilities.toByteArray(2), FBUtilities.toByteArray(1L), FBUtilities.toByteArray(0L),
             FBUtilities.toByteArray(3), FBUtilities.toByteArray(6L), FBUtilities.toByteArray(0L),
-            FBUtilities.toByteArray(7), FBUtilities.toByteArray(3L), FBUtilities.toByteArray(0L),
-            FBUtilities.toByteArray(2), FBUtilities.toByteArray(1L), FBUtilities.toByteArray(0L)
+            FBUtilities.toByteArray(7), FBUtilities.toByteArray(3L), FBUtilities.toByteArray(0L)
             );
     	sc.addColumn(new CounterColumn(getBytes(2), ByteBuffer.wrap(cc.total(context)), 9L,
context, 0L));
                     
@@ -76,11 +76,11 @@ public class SuperColumnTest
 
         // column: 1
     	byte[] c1 = concatByteArrays(
-                FBUtilities.getLocalAddress().getAddress(), FBUtilities.toByteArray(12L),
FBUtilities.toByteArray(8L),
-                FBUtilities.toByteArray(8), FBUtilities.toByteArray(9L), FBUtilities.toByteArray(0L),
                 FBUtilities.toByteArray(1), FBUtilities.toByteArray(7L), FBUtilities.toByteArray(0L),
                 FBUtilities.toByteArray(2), FBUtilities.toByteArray(5L), FBUtilities.toByteArray(7L),
-                FBUtilities.toByteArray(4), FBUtilities.toByteArray(4L), FBUtilities.toByteArray(1L)
+                FBUtilities.toByteArray(4), FBUtilities.toByteArray(4L), FBUtilities.toByteArray(1L),
+                FBUtilities.toByteArray(8), FBUtilities.toByteArray(9L), FBUtilities.toByteArray(0L),
+                FBUtilities.getLocalAddress().getAddress(), FBUtilities.toByteArray(12L),
FBUtilities.toByteArray(8L)
                 );
         assert 0 == FBUtilities.compareByteSubArrays(
             ((CounterColumn)sc.getSubColumn(getBytes(1))).partitionedCounter(),
@@ -91,9 +91,9 @@ public class SuperColumnTest
 
         // column: 2
         byte[] c2 = concatByteArrays(
+                FBUtilities.toByteArray(2), FBUtilities.toByteArray(1L), FBUtilities.toByteArray(0L),
                 FBUtilities.toByteArray(3), FBUtilities.toByteArray(6L), FBUtilities.toByteArray(0L),
-                FBUtilities.toByteArray(7), FBUtilities.toByteArray(3L), FBUtilities.toByteArray(0L),
-                FBUtilities.toByteArray(2), FBUtilities.toByteArray(1L), FBUtilities.toByteArray(0L)
+                FBUtilities.toByteArray(7), FBUtilities.toByteArray(3L), FBUtilities.toByteArray(0L)
                 );
         assert 0 == FBUtilities.compareByteSubArrays(
             ((CounterColumn)sc.getSubColumn(getBytes(2))).partitionedCounter(),

Modified: cassandra/trunk/test/unit/org/apache/cassandra/db/context/CounterContextTest.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/db/context/CounterContextTest.java?rev=1057652&r1=1057651&r2=1057652&view=diff
==============================================================================
--- cassandra/trunk/test/unit/org/apache/cassandra/db/context/CounterContextTest.java (original)
+++ cassandra/trunk/test/unit/org/apache/cassandra/db/context/CounterContextTest.java Tue
Jan 11 14:18:33 2011
@@ -73,13 +73,13 @@ public class CounterContextTest
     }
 
     @Test
-    public void testUpdatePresentReorder() throws UnknownHostException
+    public void testUpdatePresent() throws UnknownHostException
     {
         byte[] context;
 
         context = new byte[stepLength * defaultEntries];
 
-        for (int i = 0; i < defaultEntries - 1; i++)
+        for (int i = 0; i < defaultEntries; i++)
         {
             cc.writeElementAtStepOffset(
                 context,
@@ -88,58 +88,23 @@ public class CounterContextTest
                 1L,
                 1L);
         }
-        cc.writeElementAtStepOffset(
-            context,
-            (defaultEntries - 1),
-            id,
-            2L,
-            3L);
-
-        context = cc.update(context, idAddress, 10L);
+        context = cc.update(context, InetAddress.getByAddress(FBUtilities.toByteArray(defaultEntries
- 1)), 10L);
 
         assertEquals(context.length, stepLength * defaultEntries);
-        assertEquals(  3L, FBUtilities.byteArrayToLong(context, idLength));
-        assertEquals( 13L, FBUtilities.byteArrayToLong(context, idLength + clockLength));
-        for (int i = 1; i < defaultEntries; i++)
+        int offset = (defaultEntries - 1) * stepLength;
+        assertEquals(  2L, FBUtilities.byteArrayToLong(context, offset + idLength));
+        assertEquals( 11L, FBUtilities.byteArrayToLong(context, offset + idLength + clockLength));
+        for (int i = 0; i < defaultEntries - 1; i++)
         {
-            int offset = i * stepLength;
-            assertEquals( i-1, FBUtilities.byteArrayToInt(context,  offset));
+            offset = i * stepLength;
+            assertEquals( i, FBUtilities.byteArrayToInt(context,  offset));
             assertEquals(1L, FBUtilities.byteArrayToLong(context, offset + idLength));
             assertEquals(1L, FBUtilities.byteArrayToLong(context, offset + idLength + clockLength));
         }
     }
 
     @Test
-    public void testUpdateNotPresent()
-    {
-        byte[] context = new byte[stepLength * 2];
-
-        for (int i = 0; i < 2; i++)
-        {
-            cc.writeElementAtStepOffset(
-                context,
-                i,
-                FBUtilities.toByteArray(i),
-                1L,
-                1L);
-        }
-
-        context = cc.update(context, idAddress, 328L);
-
-        assert context.length == stepLength * 3;
-        assert   1L == FBUtilities.byteArrayToLong(context, idLength);
-        assert 328L == FBUtilities.byteArrayToLong(context, idLength + clockLength);
-        for (int i = 1; i < 3; i++)
-        {
-            int offset = i * stepLength;
-            assert i-1 == FBUtilities.byteArrayToInt(context,  offset);
-            assert  1L == FBUtilities.byteArrayToLong(context, offset + idLength);
-            assert  1L == FBUtilities.byteArrayToLong(context, offset + idLength + clockLength);
-        }
-    }
-
-    @Test
-    public void testSwapElement()
+    public void testUpdateNotPresent() throws UnknownHostException
     {
         byte[] context = new byte[stepLength * 3];
 
@@ -148,84 +113,28 @@ public class CounterContextTest
             cc.writeElementAtStepOffset(
                 context,
                 i,
-                FBUtilities.toByteArray(i),
+                FBUtilities.toByteArray(i * 2),
                 1L,
                 1L);
         }
-        cc.swapElement(context, 0, 2*stepLength);
-
-        assert 2 == FBUtilities.byteArrayToInt(context, 0);
-        assert 0 == FBUtilities.byteArrayToInt(context, 2*stepLength);
-
-        cc.swapElement(context, 0, 1*stepLength);
-
-        assert 1 == FBUtilities.byteArrayToInt(context, 0);
-        assert 2 == FBUtilities.byteArrayToInt(context, 1*stepLength);
-    }
-
-    @Test
-    public void testPartitionElements()
-    {
-        byte[] context = new byte[stepLength * 10];
 
-        cc.writeElementAtStepOffset(context, 0, FBUtilities.toByteArray(5), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 1, FBUtilities.toByteArray(3), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 2, FBUtilities.toByteArray(6), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 3, FBUtilities.toByteArray(7), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 4, FBUtilities.toByteArray(8), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 5, FBUtilities.toByteArray(9), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 6, FBUtilities.toByteArray(2), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 7, FBUtilities.toByteArray(4), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 8, FBUtilities.toByteArray(1), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 9, FBUtilities.toByteArray(3), 1L, 1L);
-
-        cc.partitionElements(
-            context,
-            0, // left
-            9, // right (inclusive)
-            2  // pivot
-            );
-
-        assert 5 == FBUtilities.byteArrayToInt(context, 0*stepLength);
-        assert 3 == FBUtilities.byteArrayToInt(context, 1*stepLength);
-        assert 3 == FBUtilities.byteArrayToInt(context, 2*stepLength);
-        assert 2 == FBUtilities.byteArrayToInt(context, 3*stepLength);
-        assert 4 == FBUtilities.byteArrayToInt(context, 4*stepLength);
-        assert 1 == FBUtilities.byteArrayToInt(context, 5*stepLength);
-        assert 6 == FBUtilities.byteArrayToInt(context, 6*stepLength);
-        assert 8 == FBUtilities.byteArrayToInt(context, 7*stepLength);
-        assert 9 == FBUtilities.byteArrayToInt(context, 8*stepLength);
-        assert 7 == FBUtilities.byteArrayToInt(context, 9*stepLength);
-    }
-
-    @Test
-    public void testSortElementsById()
-    {
-        byte[] context = new byte[stepLength * 10];
-
-        cc.writeElementAtStepOffset(context, 0, FBUtilities.toByteArray(5), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 1, FBUtilities.toByteArray(3), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 2, FBUtilities.toByteArray(6), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 3, FBUtilities.toByteArray(7), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 4, FBUtilities.toByteArray(8), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 5, FBUtilities.toByteArray(9), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 6, FBUtilities.toByteArray(2), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 7, FBUtilities.toByteArray(4), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 8, FBUtilities.toByteArray(1), 1L, 1L);
-        cc.writeElementAtStepOffset(context, 9, FBUtilities.toByteArray(3), 1L, 1L);
-        
-        byte[] sorted = cc.sortElementsById(context);
+        context = cc.update(context, InetAddress.getByAddress(FBUtilities.toByteArray(3)),
328L);
 
-        assertEquals( 1, FBUtilities.byteArrayToInt(sorted, 0*stepLength));
-        assertEquals( 2, FBUtilities.byteArrayToInt(sorted, 1*stepLength));
-        assertEquals( 3, FBUtilities.byteArrayToInt(sorted, 2*stepLength));
-        assertEquals( 3, FBUtilities.byteArrayToInt(sorted, 3*stepLength));
-        assertEquals( 4, FBUtilities.byteArrayToInt(sorted, 4*stepLength));
-        assertEquals( 5, FBUtilities.byteArrayToInt(sorted, 5*stepLength));
-        assertEquals( 6, FBUtilities.byteArrayToInt(sorted, 6*stepLength));
-        assertEquals( 7, FBUtilities.byteArrayToInt(sorted, 7*stepLength));
-        assertEquals( 8, FBUtilities.byteArrayToInt(sorted, 8*stepLength));
-        assertEquals( 9, FBUtilities.byteArrayToInt(sorted, 9*stepLength));
+        assert context.length == stepLength * 4;
+        int offset = 2 * stepLength;
+        assert   1L == FBUtilities.byteArrayToLong(context, offset + idLength);
+        assert 328L == FBUtilities.byteArrayToLong(context, offset + idLength + clockLength);
+        for (int i = 1; i < 2; i++)
+        {
+            offset = i * stepLength;
+            assert 2 * i == FBUtilities.byteArrayToInt(context,  offset);
+            assert    1L == FBUtilities.byteArrayToLong(context, offset + idLength);
+            assert    1L == FBUtilities.byteArrayToLong(context, offset + idLength + clockLength);
+        }
+        offset = 3 * stepLength;
+        assert  4 == FBUtilities.byteArrayToInt(context,  offset);
+        assert 1L == FBUtilities.byteArrayToLong(context, offset + idLength);
+        assert 1L == FBUtilities.byteArrayToLong(context, offset + idLength + clockLength);
     }
 
     @Test
@@ -431,44 +340,44 @@ public class CounterContextTest
             3L);
 
         byte[] right = new byte[3 * stepLength];
-        cc.writeElementAtStepOffset(right, 2, FBUtilities.toByteArray(5), 5L, 5L);
-        cc.writeElementAtStepOffset(right, 1, FBUtilities.toByteArray(4), 4L, 4L);
+        cc.writeElementAtStepOffset(right, 0, FBUtilities.toByteArray(4), 4L, 4L);
+        cc.writeElementAtStepOffset(right, 1, FBUtilities.toByteArray(5), 5L, 5L);
         cc.writeElementAtStepOffset(
             right,
-            0,
+            2,
             FBUtilities.getLocalAddress().getAddress(),
             2L,
             9L);
 
         byte[] merged = cc.merge(left, right);
 
+        assertEquals(5 * stepLength, merged.length);
         // local node id's counts are aggregated
-        assertEquals(0, FBUtilities.compareUnsigned(
+        assertEquals(0, FBUtilities.compareByteSubArrays(
             FBUtilities.getLocalAddress().getAddress(),
-            merged, 
             0,
-            0*stepLength,
-            4,
+            merged,
+            4*stepLength,
             4));
-        assertEquals(  9L, FBUtilities.byteArrayToLong(merged, 0*stepLength + idLength));
-        assertEquals(12L,  FBUtilities.byteArrayToLong(merged, 0*stepLength + idLength +
clockLength));
+        assertEquals(  9L, FBUtilities.byteArrayToLong(merged, 4*stepLength + idLength));
+        assertEquals(12L,  FBUtilities.byteArrayToLong(merged, 4*stepLength + idLength +
clockLength));
 
         // remote node id counts are reconciled (i.e. take max)
-        assertEquals( 4,   FBUtilities.byteArrayToInt(merged,  1*stepLength));
-        assertEquals( 6L,  FBUtilities.byteArrayToLong(merged, 1*stepLength + idLength));
-        assertEquals( 3L,  FBUtilities.byteArrayToLong(merged, 1*stepLength + idLength +
clockLength));
-
-        assertEquals( 5,   FBUtilities.byteArrayToInt(merged,  2*stepLength));
-        assertEquals( 5L,  FBUtilities.byteArrayToLong(merged, 2*stepLength + idLength));
-        assertEquals( 5L,  FBUtilities.byteArrayToLong(merged, 2*stepLength + idLength +
clockLength));
-
-        assertEquals( 2,   FBUtilities.byteArrayToInt(merged,  3*stepLength));
-        assertEquals( 2L,  FBUtilities.byteArrayToLong(merged, 3*stepLength + idLength));
-        assertEquals( 2L,  FBUtilities.byteArrayToLong(merged, 3*stepLength + idLength +
clockLength));
-
-        assertEquals( 1,   FBUtilities.byteArrayToInt(merged,  4*stepLength));
-        assertEquals( 1L,  FBUtilities.byteArrayToLong(merged, 4*stepLength + idLength));
-        assertEquals( 1L,  FBUtilities.byteArrayToLong(merged, 4*stepLength + idLength +
clockLength));
+        assertEquals( 4,   FBUtilities.byteArrayToInt(merged,  2*stepLength));
+        assertEquals( 6L,  FBUtilities.byteArrayToLong(merged, 2*stepLength + idLength));
+        assertEquals( 3L,  FBUtilities.byteArrayToLong(merged, 2*stepLength + idLength +
clockLength));
+
+        assertEquals( 5,   FBUtilities.byteArrayToInt(merged,  3*stepLength));
+        assertEquals( 5L,  FBUtilities.byteArrayToLong(merged, 3*stepLength + idLength));
+        assertEquals( 5L,  FBUtilities.byteArrayToLong(merged, 3*stepLength + idLength +
clockLength));
+
+        assertEquals( 2,   FBUtilities.byteArrayToInt(merged,  1*stepLength));
+        assertEquals( 2L,  FBUtilities.byteArrayToLong(merged, 1*stepLength + idLength));
+        assertEquals( 2L,  FBUtilities.byteArrayToLong(merged, 1*stepLength + idLength +
clockLength));
+
+        assertEquals( 1,   FBUtilities.byteArrayToInt(merged,  0*stepLength));
+        assertEquals( 1L,  FBUtilities.byteArrayToLong(merged, 0*stepLength + idLength));
+        assertEquals( 1L,  FBUtilities.byteArrayToLong(merged, 0*stepLength + idLength +
clockLength));
     }
 
     @Test
@@ -486,11 +395,11 @@ public class CounterContextTest
             3L);
 
         byte[] right = new byte[3 * stepLength];
-        cc.writeElementAtStepOffset(right, 2, FBUtilities.toByteArray(5), 5L, 5L);
-        cc.writeElementAtStepOffset(right, 1, FBUtilities.toByteArray(4), 4L, 4L);
+        cc.writeElementAtStepOffset(right, 0, FBUtilities.toByteArray(4), 4L, 4L);
+        cc.writeElementAtStepOffset(right, 1, FBUtilities.toByteArray(5), 5L, 5L);
         cc.writeElementAtStepOffset(
             right,
-            0,
+            2,
             FBUtilities.getLocalAddress().getAddress(),
             9L,
             9L);



Mime
View raw message