import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
protected static Holder build(UnfilteredRowIterator iterator, int initialRowCapacity, boolean ordered)
{
    CFMetaData metadata = iterator.metadata();
    PartitionColumns columns = iterator.columns();
    boolean reversed = iterator.isReverseOrder();

    BTree.Builder<Row> builder = BTree.builder(metadata.comparator, initialRowCapacity);
    builder.auto(!ordered);
    MutableDeletionInfo.Builder deletionBuilder = MutableDeletionInfo.builder(iterator.partitionLevelDeletion(), metadata.comparator, reversed);

    while (iterator.hasNext())
    {
        Unfiltered unfiltered = iterator.next();
        if (unfiltered.kind() == Unfiltered.Kind.ROW)
            builder.add((Row)unfiltered);
        else
            deletionBuilder.add((RangeTombstoneMarker)unfiltered);
    }

    if (reversed)
        builder.reverse();

    return new Holder(columns, builder.build(), deletionBuilder.build(), iterator.staticRow(), iterator.stats());
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
/**
 * Returns the result of merging this {@code Columns} object with the
 * provided one.
 *
 * @param other the other {@code Columns} to merge this object with.
 *
 * @return the result of merging/taking the union of {@code this} and
 * {@code other}. The returned object may be one of the operand and that
 * operand is a subset of the other operand.
 */
public Columns mergeTo(Columns other)
{
    if (this == other || other == NONE)
        return this;
    if (this == NONE)
        return other;

    Object[] tree = BTree.<ColumnDefinition>merge(this.columns, other.columns, Comparator.naturalOrder(),
                                                  UpdateFunction.noOp());
    if (tree == this.columns)
        return this;
    if (tree == other.columns)
        return other;

    return new Columns(tree, findFirstComplexIdx(tree));
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
public Columns deserialize(DataInputPlus in, CFMetaData metadata) throws IOException
{
    int length = (int)in.readUnsignedVInt();
    BTree.Builder<ColumnDefinition> builder = BTree.builder(Comparator.naturalOrder());
    builder.auto(false);
    for (int i = 0; i < length; i++)
    {
        ByteBuffer name = ByteBufferUtil.readWithVIntLength(in);
        ColumnDefinition column = metadata.getColumnDefinition(name);
        if (column == null)
        {
            // If we don't find the definition, it could be we have data for a dropped column, and we shouldn't
            // fail deserialization because of that. So we grab a "fake" ColumnDefinition that ensure proper
            // deserialization. The column will be ignore later on anyway.
            column = metadata.getDroppedColumnDefinition(name);
            if (column == null)
                throw new RuntimeException("Unknown column " + UTF8Type.instance.getString(name) + " during deserialization");
        }
        builder.add(column);
    }
    return new Columns(builder.build());
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
private <V> Collection<V> collection(final boolean forwards, final Function<Cell, V> f)
{
    final Holder ref = this.ref;
    return new AbstractCollection<V>()
    {
        public Iterator<V> iterator()
        {
            return Iterators.transform(BTree.<Cell>slice(ref.tree, forwards), f);
        }

        public int size()
        {
            return BTree.slice(ref.tree, true).count();
        }
    };
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
@Test
public void testSlicingAllSmallTrees() throws ExecutionException, InterruptedException
{
    Object[] cur = BTree.empty();
    TreeSet<Integer> canon = new TreeSet<>();
    // we set FAN_FACTOR to 4, so 128 items is four levels deep, three fully populated
    for (int i = 0 ; i < 128 ; i++)
    {
        String id = String.format("[0..%d)", canon.size());
        System.out.println("Testing " + id);
        Futures.allAsList(testAllSlices(id, cur, canon)).get();
        Object[] next = null;
        while (next == null)
            next = BTree.update(cur, ICMP, Arrays.asList(i), true, SPORADIC_ABORT);
        cur = next;
        canon.add(i);
    }
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
@Test
public void testClearOnAbort()
{
    final Comparator<String> cmp = new Comparator<String>()
    {
        public int compare(String o1, String o2)
        {
            return o1.compareTo(o2);
        }
    };

    Object[] btree = BTree.build(ranges(range(0, 8)), cmp, true, UpdateFunction.NoOp.<String>instance());
    BTree.update(btree, cmp, ranges(range(0, 94)), false, new AbortAfterX(90));
    btree = BTree.update(btree, cmp, ranges(range(0, 94)), false, UpdateFunction.NoOp.<String>instance());
    Assert.assertTrue(BTree.isWellFormed(btree, cmp));
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
protected static Holder build(UnfilteredRowIterator iterator, int initialRowCapacity)
{
    CFMetaData metadata = iterator.metadata();
    PartitionColumns columns = iterator.columns();
    boolean reversed = iterator.isReverseOrder();

    BTree.Builder<Row> builder = BTree.builder(metadata.comparator, initialRowCapacity);
    builder.auto(false);
    MutableDeletionInfo.Builder deletionBuilder = MutableDeletionInfo.builder(iterator.partitionLevelDeletion(), metadata.comparator, reversed);

    while (iterator.hasNext())
    {
        Unfiltered unfiltered = iterator.next();
        if (unfiltered.kind() == Unfiltered.Kind.ROW)
            builder.add((Row)unfiltered);
        else
            deletionBuilder.add((RangeTombstoneMarker)unfiltered);
    }

    if (reversed)
        builder.reverse();

    return new Holder(columns, builder.build(), deletionBuilder.build(), iterator.staticRow(), iterator.stats());
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
/**
 * Tests that the apply method of the <code>UpdateFunction</code> is only called once per value with each build call.
 */
@Test
public void testBuilding_UpdateFunctionCallBack()
{
    CallsMonitor monitor = new CallsMonitor();
    Object[] btree = BTree.build(Arrays.asList(1), monitor);
    assertArrayEquals(new Object[] {1}, btree);
    assertEquals(1, monitor.getNumberOfCalls(1));

    monitor.clear();
    btree = BTree.build(Arrays.asList(1, 2), monitor);
    assertArrayEquals(new Object[] {1, 2, null}, btree);
    assertEquals(1, monitor.getNumberOfCalls(1));
    assertEquals(1, monitor.getNumberOfCalls(2));

    monitor.clear();
    btree = BTree.build(Arrays.asList(1, 2, 3), monitor);
    assertArrayEquals(new Object[] {1, 2, 3}, btree);
    assertEquals(1, monitor.getNumberOfCalls(1));
    assertEquals(1, monitor.getNumberOfCalls(2));
    assertEquals(1, monitor.getNumberOfCalls(3));
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
private UnfilteredRowIterator sliceIterator(ColumnFilter selection, Slice slice, boolean reversed, Holder current, Row staticRow)
{
    ClusteringBound start = slice.start() == ClusteringBound.BOTTOM ? null : slice.start();
    ClusteringBound end = slice.end() == ClusteringBound.TOP ? null : slice.end();
    Iterator<Row> rowIter = BTree.slice(current.tree, metadata.comparator, start, true, end, true, desc(reversed));
    Iterator<RangeTombstone> deleteIter = current.deletionInfo.rangeIterator(slice, reversed);
    return merge(rowIter, deleteIter, selection, reversed, current, staticRow);
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
public Row lastRow()
{
    Object[] tree = holder().tree;
    if (BTree.isEmpty(tree))
        return null;

    return BTree.findByIndex(tree, BTree.size(tree) - 1);
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
private PartitionUpdate(CFMetaData metadata,
                        DecoratedKey key,
                        PartitionColumns columns,
                        MutableDeletionInfo deletionInfo,
                        int initialRowCapacity,
                        boolean canHaveShadowedData)
{
    super(metadata, key);
    this.deletionInfo = deletionInfo;
    this.holder = new Holder(columns, BTree.empty(), deletionInfo, Rows.EMPTY_STATIC_ROW, EncodingStats.NO_STATS);
    this.canHaveShadowedData = canHaveShadowedData;
    rowBuilder = builder(initialRowCapacity);
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
private static int findFirstComplexIdx(Object[] tree)
{
    // have fast path for common no-complex case
    int size = BTree.size(tree);
    if (!BTree.isEmpty(tree) && BTree.<ColumnDefinition>findByIndex(tree, size - 1).isSimple())
        return size;
    return BTree.ceilIndex(tree, Comparator.naturalOrder(), FIRST_COMPLEX);
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
/**
 * Whether this object is a superset of the provided other {@code Columns object}.
 *
 * @param other the other object to test for inclusion in this object.
 *
 * @return whether all the columns of {@code other} are contained by this object.
 */
public boolean containsAll(Collection<?> other)
{
    if (other == this)
        return true;
    if (other.size() > this.size())
        return false;

    BTreeSearchIterator<ColumnDefinition, ColumnDefinition> iter = BTree.slice(columns, Comparator.naturalOrder(), BTree.Dir.ASC);
    for (Object def : other)
        if (iter.next((ColumnDefinition) def) == null)
            return false;
    return true;
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
@Override
public boolean equals(Object other)
{
    if (other == this)
        return true;
    if (!(other instanceof Columns))
        return false;

    Columns that = (Columns)other;
    return this.complexIdx == that.complexIdx && BTree.equals(this.columns, that.columns);
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
public Columns deserializeSubset(Columns superset, DataInputPlus in) throws IOException
{
    long encoded = in.readUnsignedVInt();
    if (encoded == 0L)
    {
        return superset;
    }
    else if (superset.size() >= 64)
    {
        return deserializeLargeSubset(in, superset, (int) encoded);
    }
    else
    {
        BTree.Builder<ColumnDefinition> builder = BTree.builder(Comparator.naturalOrder());
        int firstComplexIdx = 0;
        for (ColumnDefinition column : superset)
        {
            if ((encoded & 1) == 0)
            {
                builder.add(column);
                if (column.isSimple())
                    ++firstComplexIdx;
            }
            encoded >>>= 1;
        }
        return new Columns(builder.build(), firstComplexIdx);
    }
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
public static BTreeRow create(Clustering clustering,
                              LivenessInfo primaryKeyLivenessInfo,
                              Deletion deletion,
                              Object[] btree)
{
    int minDeletionTime = Math.min(minDeletionTime(primaryKeyLivenessInfo), minDeletionTime(deletion.time()));
    if (minDeletionTime != Integer.MIN_VALUE)
    {
        for (ColumnData cd : BTree.<ColumnData>iterable(btree))
            minDeletionTime = Math.min(minDeletionTime, minDeletionTime(cd));
    }

    return create(clustering, primaryKeyLivenessInfo, deletion, btree, minDeletionTime);
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
public static BTreeRow singleCellRow(Clustering clustering, Cell cell)
{
    if (cell.column().isSimple())
        return new BTreeRow(clustering, BTree.singleton(cell), minDeletionTime(cell));

    ComplexColumnData complexData = new ComplexColumnData(cell.column(), new Cell[]{ cell }, DeletionTime.LIVE);
    return new BTreeRow(clustering, BTree.singleton(complexData), minDeletionTime(cell));
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
private static int minDeletionTime(Object[] btree, LivenessInfo info, DeletionTime rowDeletion)
{
    //we have to wrap this for the lambda
    final WrappedInt min = new WrappedInt(Math.min(minDeletionTime(info), minDeletionTime(rowDeletion)));

    BTree.<ColumnData>apply(btree, cd -> min.set( Math.min(min.get(), minDeletionTime(cd)) ), cd -> min.get() == Integer.MIN_VALUE, false);
    return min.get();
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
private Row transformAndFilter(LivenessInfo info, Deletion deletion, Function<ColumnData, ColumnData> function)
{
    Object[] transformed = BTree.transformAndFilter(btree, function);

    if (btree == transformed && info == this.primaryKeyLivenessInfo && deletion == this.deletion)
        return this;

    if (info.isEmpty() && deletion.isLive() && BTree.isEmpty(transformed))
        return null;

    int minDeletionTime = minDeletionTime(transformed, info, deletion.time());
    return BTreeRow.create(clustering, info, deletion, transformed, minDeletionTime);
}
 

import org.apache.cassandra.utils.btree.BTree; //导入依赖的package包/类
public long unsharedHeapSizeExcludingData()
{
    long heapSize = EMPTY_SIZE
                  + clustering.unsharedHeapSizeExcludingData()
                  + BTree.sizeOfStructureOnHeap(btree);

    for (ColumnData cd : this)
        heapSize += cd.unsharedHeapSizeExcludingData();
    return heapSize;
}