maedhroz commented on code in PR #2267: URL: https://github.com/apache/cassandra/pull/2267#discussion_r1179704381
########## src/java/org/apache/cassandra/io/sstable/format/bti/RowIndexReader.java: ########## @@ -0,0 +1,190 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.cassandra.io.sstable.format.bti; + +import java.io.IOException; +import java.io.PrintStream; +import java.nio.ByteBuffer; + +import org.apache.cassandra.db.DeletionTime; +import org.apache.cassandra.io.tries.SerializationNode; +import org.apache.cassandra.io.tries.TrieNode; +import org.apache.cassandra.io.tries.TrieSerializer; +import org.apache.cassandra.io.tries.Walker; +import org.apache.cassandra.io.util.DataOutputPlus; +import org.apache.cassandra.io.util.FileHandle; +import org.apache.cassandra.io.util.SizedInts; +import org.apache.cassandra.utils.bytecomparable.ByteComparable; + +/** + * Reader class for row index files. + * + * Row index "tries" do not need to store whole keys, as what we need from them is to be able to tell where in the data file + * to start looking for a given key. Instead, we store some prefix that is greater than the greatest key of the previous + * index section and smaller than or equal to the smallest key of the next. So for a given key the first index section + * that could potentially contain it is given by the trie's floor for that key. + * + * This builds upon the trie Walker class which provides basic trie walking functionality. The class is thread-unsafe + * and must be re-instantiated for every thread that needs access to the trie (its overhead is below that of a + * RandomAccessReader). + */ +public class RowIndexReader extends Walker<RowIndexReader> +{ + private static final int FLAG_OPEN_MARKER = 8; + + public static class IndexInfo + { + public final long offset; + public final DeletionTime openDeletion; + + IndexInfo(long offset, DeletionTime openDeletion) + { + this.offset = offset; + this.openDeletion = openDeletion; + } + } + + public RowIndexReader(FileHandle file, long root) + { + super(file.instantiateRebufferer(null), root); + } + + public RowIndexReader(FileHandle file, TrieIndexEntry entry) + { + this(file, entry.indexTrieRoot); + } + + /** + * Computes the floor for a given key. + */ + public IndexInfo separatorFloor(ByteComparable key) + { + // Check for a prefix and find closest smaller branch. + IndexInfo res = prefixAndNeighbours(key, RowIndexReader::readPayload); + // If there's a prefix, in a separator trie it could be less than, equal, or greater than sought value. + // Sought value is still greater than max of previous section. + // On match the prefix must be used as a starting point. + if (res != null) + return res; + + // Otherwise return the IndexInfo for the closest entry of the smaller branch (which is the max of lesserBranch). + // Note (see prefixAndNeighbours): since we accept prefix matches above, at this point there cannot be another + // prefix match that is closer than max(lesserBranch). + if (lesserBranch == -1) Review Comment: nit: Might be a good idea to pull up a named constant for `-1` in `Walker`, use it there and here. Not super particular about what it's called, as long as it connotes something about the branch not existing... -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
