Better solution for CASSANDRA-6742 patch by Aleksey Yeschenko; reviewed by Benedict Elliott Smith for CASSANDRA-6742
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/e69e526b Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/e69e526b Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/e69e526b Branch: refs/heads/trunk Commit: e69e526b9053e3d3634a005cc94a8954c2d7d41f Parents: 5223c47 Author: Aleksey Yeschenko <alek...@apache.org> Authored: Thu Feb 20 21:26:21 2014 +0300 Committer: Aleksey Yeschenko <alek...@apache.org> Committed: Thu Feb 20 21:35:33 2014 +0300 ---------------------------------------------------------------------- .../cassandra/db/ArrayBackedSortedColumns.java | 86 ++++++++++---------- 1 file changed, 42 insertions(+), 44 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/e69e526b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java index 24a0755..0ce36e2 100644 --- a/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java +++ b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java @@ -43,12 +43,12 @@ public class ArrayBackedSortedColumns extends ColumnFamily private static final int MINIMAL_CAPACITY = 10; private final boolean reversed; - private DeletionInfo deletionInfo; + private DeletionInfo deletionInfo; private Cell[] cells; - - private volatile int size; - private volatile int sortedSize; + private int size; + private int sortedSize; + private volatile boolean isSorted; public static final ColumnFamily.Factory<ArrayBackedSortedColumns> factory = new Factory<ArrayBackedSortedColumns>() { @@ -66,6 +66,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily this.cells = EMPTY_ARRAY; this.size = 0; this.sortedSize = 0; + this.isSorted = true; } private ArrayBackedSortedColumns(ArrayBackedSortedColumns original) @@ -76,6 +77,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily this.cells = Arrays.copyOf(original.cells, original.size); this.size = original.size; this.sortedSize = original.sortedSize; + this.isSorted = original.isSorted; } public ColumnFamily.Factory getFactory() @@ -100,7 +102,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily private void maybeSortCells() { - if (size != sortedSize) + if (!isSorted) sortCells(); } @@ -109,8 +111,8 @@ public class ArrayBackedSortedColumns extends ColumnFamily */ private synchronized void sortCells() { - if (size == sortedSize) - return; // Just sorted by a previous call. + if (isSorted) + return; // Just sorted by a previous call Comparator<Cell> comparator = reversed ? getComparator().columnReverseComparator() @@ -133,8 +135,8 @@ public class ArrayBackedSortedColumns extends ColumnFamily int rightStart = sortedSize; int rightEnd = size; - sortedSize = -1; // Set to -1 to avoid the pos == sortedSize edge case - size = pos; // 'Trim' the size to what's left without the leftCopy + // 'Trim' the sizes to what's left without the leftCopy + size = sortedSize = pos; // Merge the cells from both segments. When adding from the left segment we can rely on it not having any // duplicate cells, and thus omit the comparison with the previously entered cell - we'll never need to reconcile. @@ -143,23 +145,38 @@ public class ArrayBackedSortedColumns extends ColumnFamily { int cmp = comparator.compare(leftCopy[l], cells[r]); if (cmp < 0) - internalAppend(leftCopy[l++]); + append(leftCopy[l++]); else if (cmp == 0) - internalAppend(leftCopy[l++].reconcile(cells[r++])); + append(leftCopy[l++].reconcile(cells[r++])); else - internalAppendOrReconcile(cells[r++]); + appendOrReconcile(cells[r++]); } while (l < leftCopy.length) - internalAppend(leftCopy[l++]); + append(leftCopy[l++]); while (r < rightEnd) - internalAppendOrReconcile(cells[r++]); - - // Fully sorted at this point - sortedSize = size; + appendOrReconcile(cells[r++]); // Nullify the remainder of the array (in case we had duplicate cells that got reconciled) for (int i = size; i < rightEnd; i++) cells[i] = null; + + // Fully sorted at this point + isSorted = true; + } + + private void appendOrReconcile(Cell cell) + { + if (size > 0 && cells[size - 1].name().equals(cell.name())) + reconcileWith(size - 1, cell); + else + append(cell); + } + + private void append(Cell cell) + { + cells[size] = cell; + size++; + sortedSize++; } public Cell getColumn(CellName name) @@ -200,9 +217,14 @@ public class ArrayBackedSortedColumns extends ColumnFamily { int pos = binarySearch(cell.name()); if (pos >= 0) // Reconcile with an existing cell + { reconcileWith(pos, cell); + } else + { internalAdd(cell); // Append to the end, making cells unsorted from now on + isSorted = false; + } } } @@ -223,33 +245,8 @@ public class ArrayBackedSortedColumns extends ColumnFamily */ private void internalAdd(Cell cell) { - if (cells == EMPTY_ARRAY) - cells = new Cell[MINIMAL_CAPACITY]; - else if (cells.length == size) - cells = Arrays.copyOf(cells, size * 3 / 2 + 1); - - cells[size++] = cell; - } - - /** - * Appends a cell to the array, with the knowledge that array has enough capacity for the new cell, and that - * the cell is being added in the sorted order, but may or may not need to be reconciled with the previously - * appended one. - */ - private void internalAppendOrReconcile(Cell cell) - { - if (size > 0 && cells[size - 1].name().equals(cell.name())) - reconcileWith(size - 1, cell); - else - internalAppend(cell); - } - - /** - * Appends a cell to the array, with the knowledge that array has enough capacity for the new cell, and that - * the cell is being added in the sorted order, and the added cell is not a duplicate of a previously inserted one. - */ - private void internalAppend(Cell cell) - { + if (cells.length == size) + cells = Arrays.copyOf(cells, Math.max(MINIMAL_CAPACITY, size * 3 / 2 + 1)); cells[size++] = cell; } @@ -328,6 +325,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily for (int i = 0; i < size; i++) cells[i] = null; size = sortedSize = 0; + isSorted = true; } public DeletionInfo deletionInfo()
