Author: slebresne Date: Thu Dec 8 17:31:07 2011 New Revision: 1211999 URL: http://svn.apache.org/viewvc?rev=1211999&view=rev Log: Improve memtable slice iteration performance patch by slebresne; reviewed by jbellis for CASSANDRA-3545
Modified: cassandra/trunk/CHANGES.txt cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilyStore.java cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java cassandra/trunk/src/java/org/apache/cassandra/db/RowIteratorFactory.java cassandra/trunk/src/java/org/apache/cassandra/db/ThreadSafeSortedColumns.java cassandra/trunk/src/java/org/apache/cassandra/db/TreeMapBackedSortedColumns.java cassandra/trunk/src/java/org/apache/cassandra/db/filter/IFilter.java cassandra/trunk/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java cassandra/trunk/src/java/org/apache/cassandra/db/filter/QueryFilter.java cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java cassandra/trunk/src/java/org/apache/cassandra/db/index/keys/KeysSearcher.java cassandra/trunk/src/java/org/apache/cassandra/service/RowRepairResolver.java cassandra/trunk/test/unit/org/apache/cassandra/db/ArrayBackedSortedColumnsTest.java Modified: cassandra/trunk/CHANGES.txt URL: http://svn.apache.org/viewvc/cassandra/trunk/CHANGES.txt?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/CHANGES.txt (original) +++ cassandra/trunk/CHANGES.txt Thu Dec 8 17:31:07 2011 @@ -21,6 +21,7 @@ * fix potential race in AES when a repair fails (CASSANDRA-3548) * Remove columns shadowed by a deleted container even when we cannot purge (CASSANDRA-3538) + * Improve memtable slice iteration performance (CASSANDRA-3545) 1.0.6 Modified: cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java Thu Dec 8 17:31:07 2011 @@ -234,6 +234,21 @@ public abstract class AbstractColumnCont return columns.iterator(); } + public Iterator<IColumn> reverseIterator() + { + return columns.reverseIterator(); + } + + public Iterator<IColumn> iterator(ByteBuffer start) + { + return columns.iterator(start); + } + + public Iterator<IColumn> reverseIterator(ByteBuffer start) + { + return columns.reverseIterator(start); + } + protected static class DeletionInfo { public final long markedForDeleteAt; Modified: cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java Thu Dec 8 17:31:07 2011 @@ -289,17 +289,39 @@ public class ArrayBackedSortedColumns ex @Override public Iterator<IColumn> iterator() { - return reversed ? reverseInternalIterator() : super.iterator(); + return reversed ? reverseInternalIterator(size()) : super.iterator(); } public Iterator<IColumn> reverseIterator() { - return reversed ? super.iterator() : reverseInternalIterator(); + return reversed ? super.iterator() : reverseInternalIterator(size()); } - private Iterator<IColumn> reverseInternalIterator() + public Iterator<IColumn> iterator(ByteBuffer start) { - final ListIterator<IColumn> iter = listIterator(size()); + int idx = binarySearch(start); + if (idx < 0) + idx = -idx - 1; + else if (reversed) + // listIterator.previous() doesn't return the current element at first but the previous one + idx++; + return reversed ? reverseInternalIterator(idx) : listIterator(idx); + } + + public Iterator<IColumn> reverseIterator(ByteBuffer start) + { + int idx = binarySearch(start); + if (idx < 0) + idx = -idx - 1; + else if (!reversed) + // listIterator.previous() doesn't return the current element at first but the previous one + idx++; + return reversed ? listIterator(idx) : reverseInternalIterator(idx); + } + + private Iterator<IColumn> reverseInternalIterator(int idx) + { + final ListIterator<IColumn> iter = listIterator(idx); return new Iterator<IColumn>() { public boolean hasNext() Modified: cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java Thu Dec 8 17:31:07 2011 @@ -85,7 +85,7 @@ public class CollationController { for (Memtable memtable : view.memtables) { - IColumnIterator iter = filter.getMemtableColumnIterator(memtable, cfs.metadata.comparator); + IColumnIterator iter = filter.getMemtableColumnIterator(memtable); if (iter != null) { iterators.add(iter); @@ -149,7 +149,7 @@ public class CollationController } }; ColumnFamily returnCF = container.cloneMeShallow(); - filter.collateColumns(returnCF, Collections.singletonList(toCollate), cfs.metadata.comparator, gcBefore); + filter.collateColumns(returnCF, Collections.singletonList(toCollate), gcBefore); // "hoist up" the requested data into a more recent sstable if (sstablesIterated > cfs.getMinimumCompactionThreshold() @@ -219,7 +219,7 @@ public class CollationController { for (Memtable memtable : view.memtables) { - IColumnIterator iter = filter.getMemtableColumnIterator(memtable, cfs.metadata.comparator); + IColumnIterator iter = filter.getMemtableColumnIterator(memtable); if (iter != null) { returnCF.delete(iter.getColumnFamily()); @@ -243,7 +243,7 @@ public class CollationController if (iterators.isEmpty()) return null; - filter.collateColumns(returnCF, iterators, cfs.metadata.comparator, gcBefore); + filter.collateColumns(returnCF, iterators, gcBefore); // Caller is responsible for final removeDeletedCF. This is important for cacheRow to work correctly: return returnCF; Modified: cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilyStore.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilyStore.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilyStore.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilyStore.java Thu Dec 8 17:31:07 2011 @@ -1183,8 +1183,8 @@ public class ColumnFamilyStore implement ColumnFamily filterColumnFamily(ColumnFamily cached, QueryFilter filter, int gcBefore) { ColumnFamily cf = cached.cloneMeShallow(ArrayBackedSortedColumns.factory(), filter.filter.isReversed()); - IColumnIterator ci = filter.getMemtableColumnIterator(cached, null, getComparator()); - filter.collateColumns(cf, Collections.singletonList(ci), getComparator(), gcBefore); + IColumnIterator ci = filter.getMemtableColumnIterator(cached, null); + filter.collateColumns(cf, Collections.singletonList(ci), gcBefore); // TODO this is necessary because when we collate supercolumns together, we don't check // their subcolumns for relevance, so we need to do a second prune post facto here. return cf.isSuper() ? removeDeleted(cf, gcBefore) : removeDeletedCF(cf, gcBefore); @@ -1299,7 +1299,7 @@ public class ColumnFamilyStore implement ViewFragment view = markReferenced(startWith, stopAt); try { - CloseableIterator<Row> iterator = RowIteratorFactory.getIterator(view.memtables, view.sstables, startWith, stopAt, filter, getComparator(), this); + CloseableIterator<Row> iterator = RowIteratorFactory.getIterator(view.memtables, view.sstables, startWith, stopAt, filter, this); rows = new ArrayList<Row>(); try Modified: cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java Thu Dec 8 17:31:07 2011 @@ -125,6 +125,18 @@ public interface ISortedColumns extends public Iterator<IColumn> reverseIterator(); /** + * Returns an iterator over the columns of this map starting from the + * first column whose name is equal or greater than @param start. + */ + public Iterator<IColumn> iterator(ByteBuffer start); + + /** + * Returns a reversed iterator over the columns of this map starting from + * the last column whose name is equal or lesser than @param start. + */ + public Iterator<IColumn> reverseIterator(ByteBuffer start); + + /** * Returns if this map only support inserts in reverse order. */ public boolean isInsertReversed(); Modified: cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java Thu Dec 8 17:31:07 2011 @@ -343,24 +343,12 @@ public class Memtable /** * obtain an iterator of columns in this memtable in the specified order starting from a given column. */ - public static IColumnIterator getSliceIterator(final DecoratedKey key, final ColumnFamily cf, SliceQueryFilter filter, AbstractType typeComparator) + public static IColumnIterator getSliceIterator(final DecoratedKey key, final ColumnFamily cf, SliceQueryFilter filter) { assert cf != null; - final boolean isSuper = cf.isSuper(); - final Collection<IColumn> filteredColumns = filter.reversed ? cf.getReverseSortedColumns() : cf.getSortedColumns(); - - // ok to not have subcolumnComparator since we won't be adding columns to this object - IColumn startColumn = isSuper ? new SuperColumn(filter.start, (AbstractType)null) : new Column(filter.start); - Comparator<IColumn> comparator = filter.getColumnComparator(typeComparator); - - final PeekingIterator<IColumn> filteredIter = Iterators.peekingIterator(filteredColumns.iterator()); - if (!filter.reversed || filter.start.remaining() != 0) - { - while (filteredIter.hasNext() && comparator.compare(filteredIter.peek(), startColumn) < 0) - { - filteredIter.next(); - } - } + final Iterator<IColumn> filteredIter = filter.reversed + ? (filter.start.remaining() == 0 ? cf.reverseIterator() : cf.reverseIterator(filter.start)) + : cf.iterator(filter.start); return new AbstractColumnIterator() { @@ -381,7 +369,7 @@ public class Memtable public IColumn next() { - return filteredIter.next(); + return filteredIter.next(); } }; } Modified: cassandra/trunk/src/java/org/apache/cassandra/db/RowIteratorFactory.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/RowIteratorFactory.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/RowIteratorFactory.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/RowIteratorFactory.java Thu Dec 8 17:31:07 2011 @@ -61,7 +61,6 @@ public class RowIteratorFactory final RowPosition startWith, final RowPosition stopAt, final QueryFilter filter, - final AbstractType comparator, final ColumnFamilyStore cfs) { // fetch data from current memtable, historical memtables, and SSTables in the correct order. @@ -80,7 +79,7 @@ public class RowIteratorFactory // memtables for (Memtable memtable : memtables) { - iterators.add(new ConvertToColumnIterator(filter, comparator, p, memtable.getEntryIterator(startWith))); + iterators.add(new ConvertToColumnIterator(filter, p, memtable.getEntryIterator(startWith))); } for (SSTableReader sstable : sstables) @@ -120,7 +119,7 @@ public class RowIteratorFactory ColumnFamily cached = cfs.getRawCachedRow(key); if (cached == null) // not cached: collate - filter.collateColumns(returnCF, colIters, comparator, gcBefore); + filter.collateColumns(returnCF, colIters, gcBefore); else { QueryFilter keyFilter = new QueryFilter(key, filter.path, filter.filter); @@ -141,14 +140,12 @@ public class RowIteratorFactory private static class ConvertToColumnIterator extends AbstractIterator<IColumnIterator> implements CloseableIterator<IColumnIterator> { private final QueryFilter filter; - private final AbstractType comparator; private final Predicate<IColumnIterator> pred; private final Iterator<Map.Entry<DecoratedKey, ColumnFamily>> iter; - public ConvertToColumnIterator(QueryFilter filter, AbstractType comparator, Predicate<IColumnIterator> pred, Iterator<Map.Entry<DecoratedKey, ColumnFamily>> iter) + public ConvertToColumnIterator(QueryFilter filter, Predicate<IColumnIterator> pred, Iterator<Map.Entry<DecoratedKey, ColumnFamily>> iter) { this.filter = filter; - this.comparator = comparator; this.pred = pred; this.iter = iter; } @@ -158,7 +155,7 @@ public class RowIteratorFactory while (iter.hasNext()) { Map.Entry<DecoratedKey, ColumnFamily> entry = iter.next(); - IColumnIterator ici = filter.getMemtableColumnIterator(entry.getValue(), entry.getKey(), comparator); + IColumnIterator ici = filter.getMemtableColumnIterator(entry.getValue(), entry.getKey()); if (pred.apply(ici)) return ici; } Modified: cassandra/trunk/src/java/org/apache/cassandra/db/ThreadSafeSortedColumns.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/ThreadSafeSortedColumns.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/ThreadSafeSortedColumns.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/ThreadSafeSortedColumns.java Thu Dec 8 17:31:07 2011 @@ -162,4 +162,14 @@ public class ThreadSafeSortedColumns ext { return getReverseSortedColumns().iterator(); } + + public Iterator<IColumn> iterator(ByteBuffer start) + { + return tailMap(start).values().iterator(); + } + + public Iterator<IColumn> reverseIterator(ByteBuffer start) + { + return descendingMap().tailMap(start).values().iterator(); + } } Modified: cassandra/trunk/src/java/org/apache/cassandra/db/TreeMapBackedSortedColumns.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/TreeMapBackedSortedColumns.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/TreeMapBackedSortedColumns.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/TreeMapBackedSortedColumns.java Thu Dec 8 17:31:07 2011 @@ -180,4 +180,14 @@ public class TreeMapBackedSortedColumns { return getReverseSortedColumns().iterator(); } + + public Iterator<IColumn> iterator(ByteBuffer start) + { + return tailMap(start).values().iterator(); + } + + public Iterator<IColumn> reverseIterator(ByteBuffer start) + { + return descendingMap().tailMap(start).values().iterator(); + } } Modified: cassandra/trunk/src/java/org/apache/cassandra/db/filter/IFilter.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/filter/IFilter.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/filter/IFilter.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/filter/IFilter.java Thu Dec 8 17:31:07 2011 @@ -42,7 +42,7 @@ public interface IFilter * returns an iterator that returns columns from the given memtable * matching the Filter criteria in sorted order. */ - public abstract IColumnIterator getMemtableColumnIterator(ColumnFamily cf, DecoratedKey<?> key, AbstractType comparator); + public abstract IColumnIterator getMemtableColumnIterator(ColumnFamily cf, DecoratedKey<?> key); /** * Get an iterator that returns columns from the given SSTable using the opened file Modified: cassandra/trunk/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java Thu Dec 8 17:31:07 2011 @@ -50,7 +50,7 @@ public class NamesQueryFilter implements this(FBUtilities.singleton(column)); } - public IColumnIterator getMemtableColumnIterator(ColumnFamily cf, DecoratedKey<?> key, AbstractType comparator) + public IColumnIterator getMemtableColumnIterator(ColumnFamily cf, DecoratedKey<?> key) { return Memtable.getNamesIterator(key, cf, this); } Modified: cassandra/trunk/src/java/org/apache/cassandra/db/filter/QueryFilter.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/filter/QueryFilter.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/filter/QueryFilter.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/filter/QueryFilter.java Thu Dec 8 17:31:07 2011 @@ -55,20 +55,20 @@ public class QueryFilter superFilter = path.superColumnName == null ? null : new NamesQueryFilter(path.superColumnName); } - public IColumnIterator getMemtableColumnIterator(Memtable memtable, AbstractType comparator) + public IColumnIterator getMemtableColumnIterator(Memtable memtable) { ColumnFamily cf = memtable.getColumnFamily(key); if (cf == null) return null; - return getMemtableColumnIterator(cf, key, comparator); + return getMemtableColumnIterator(cf, key); } - public IColumnIterator getMemtableColumnIterator(ColumnFamily cf, DecoratedKey<?> key, AbstractType comparator) + public IColumnIterator getMemtableColumnIterator(ColumnFamily cf, DecoratedKey<?> key) { assert cf != null; if (path.superColumnName == null) - return filter.getMemtableColumnIterator(cf, key, comparator); - return superFilter.getMemtableColumnIterator(cf, key, comparator); + return filter.getMemtableColumnIterator(cf, key); + return superFilter.getMemtableColumnIterator(cf, key); } // TODO move gcBefore into a field @@ -87,10 +87,10 @@ public class QueryFilter } // TODO move gcBefore into a field - public void collateColumns(final ColumnFamily returnCF, List<? extends CloseableIterator<IColumn>> toCollate, AbstractType comparator, final int gcBefore) + public void collateColumns(final ColumnFamily returnCF, List<? extends CloseableIterator<IColumn>> toCollate, final int gcBefore) { IFilter topLevelFilter = (superFilter == null ? filter : superFilter); - Comparator<IColumn> fcomp = topLevelFilter.getColumnComparator(comparator); + Comparator<IColumn> fcomp = topLevelFilter.getColumnComparator(returnCF.getComparator()); // define a 'reduced' iterator that merges columns w/ the same name, which // greatly simplifies computing liveColumns in the presence of tombstones. MergeIterator.Reducer<IColumn, IColumn> reducer = new MergeIterator.Reducer<IColumn, IColumn>() Modified: cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java Thu Dec 8 17:31:07 2011 @@ -56,9 +56,9 @@ public class SliceQueryFilter implements this.count = count; } - public IColumnIterator getMemtableColumnIterator(ColumnFamily cf, DecoratedKey<?> key, AbstractType comparator) + public IColumnIterator getMemtableColumnIterator(ColumnFamily cf, DecoratedKey<?> key) { - return Memtable.getSliceIterator(key, cf, this, comparator); + return Memtable.getSliceIterator(key, cf, this); } public IColumnIterator getSSTableColumnIterator(SSTableReader sstable, DecoratedKey<?> key) Modified: cassandra/trunk/src/java/org/apache/cassandra/db/index/keys/KeysSearcher.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/index/keys/KeysSearcher.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/db/index/keys/KeysSearcher.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/db/index/keys/KeysSearcher.java Thu Dec 8 17:31:07 2011 @@ -235,8 +235,8 @@ public class KeysSearcher extends Second { ColumnFamily expandedData = data; data = expandedData.cloneMeShallow(); - IColumnIterator iter = dataFilter.getMemtableColumnIterator(expandedData, dk, baseCfs.getComparator()); - new QueryFilter(dk, path, dataFilter).collateColumns(data, Collections.singletonList(iter), baseCfs.getComparator(), baseCfs.gcBefore()); + IColumnIterator iter = dataFilter.getMemtableColumnIterator(expandedData, dk); + new QueryFilter(dk, path, dataFilter).collateColumns(data, Collections.singletonList(iter), baseCfs.gcBefore()); } rows.add(new Row(dk, data)); Modified: cassandra/trunk/src/java/org/apache/cassandra/service/RowRepairResolver.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/service/RowRepairResolver.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/service/RowRepairResolver.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/service/RowRepairResolver.java Thu Dec 8 17:31:07 2011 @@ -168,7 +168,7 @@ public class RowRepairResolver extends A continue; iters.add(FBUtilities.closeableIterator(version.iterator())); } - filter.collateColumns(resolved, iters, resolved.metadata().comparator, Integer.MIN_VALUE); + filter.collateColumns(resolved, iters, Integer.MIN_VALUE); return ColumnFamilyStore.removeDeleted(resolved, Integer.MIN_VALUE); } Modified: cassandra/trunk/test/unit/org/apache/cassandra/db/ArrayBackedSortedColumnsTest.java URL: http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/db/ArrayBackedSortedColumnsTest.java?rev=1211999&r1=1211998&r2=1211999&view=diff ============================================================================== --- cassandra/trunk/test/unit/org/apache/cassandra/db/ArrayBackedSortedColumnsTest.java (original) +++ cassandra/trunk/test/unit/org/apache/cassandra/db/ArrayBackedSortedColumnsTest.java Thu Dec 8 17:31:07 2011 @@ -133,13 +133,53 @@ public class ArrayBackedSortedColumnsTes assertSame(names, map.getColumnNames()); } + @Test + public void testIterator() + { + testIteratorInternal(false); + //testIteratorInternal(true); + } + + private void testIteratorInternal(boolean reversed) + { + ISortedColumns map = ArrayBackedSortedColumns.factory().create(BytesType.instance, reversed); + + List<ByteBuffer> names = new ArrayList<ByteBuffer>(); + int[] values = new int[]{ 1, 2, 3, 5, 9 }; + for (int v : values) + names.add(ByteBufferUtil.bytes(v)); + + for (int i = 0; i < values.length; ++i) + map.addColumn(new Column(ByteBufferUtil.bytes(values[reversed ? values.length - 1 - i : i])), HeapAllocator.instance); + + //assertSame(new int[]{ 3, 5, 9 }, map.iterator(ByteBufferUtil.bytes(3))); + //assertSame(new int[]{ 5, 9 }, map.iterator(ByteBufferUtil.bytes(4))); + + assertSame(new int[]{ 3, 2, 1 }, map.reverseIterator(ByteBufferUtil.bytes(3))); + assertSame(new int[]{ 3, 2, 1 }, map.reverseIterator(ByteBufferUtil.bytes(4))); + + assertSame(map.iterator(), map.iterator(ByteBufferUtil.EMPTY_BYTE_BUFFER)); + } + private <T> void assertSame(Collection<T> c1, Collection<T> c2) { - Iterator<T> iter1 = c1.iterator(); - Iterator<T> iter2 = c2.iterator(); + assertSame(c1.iterator(), c2.iterator()); + } + + private <T> void assertSame(Iterator<T> iter1, Iterator<T> iter2) + { while (iter1.hasNext() && iter2.hasNext()) assertEquals(iter1.next(), iter2.next()); if (iter1.hasNext() || iter2.hasNext()) fail("The collection don't have the same size"); } + + private void assertSame(int[] names, Iterator<IColumn> iter) + { + for (int name : names) + { + assert iter.hasNext(); + assert name == ByteBufferUtil.toInt(iter.next().name()); + } + } }