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);
