src/kudu/cfile/index_block.h

// 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.

#ifndef KUDU_CFILE_INDEX_BLOCK_H
#define KUDU_CFILE_INDEX_BLOCK_H

#include <cstddef>
#include <cstdint>
#include <vector>

#include "kudu/cfile/block_pointer.h"
#include "kudu/cfile/cfile.pb.h"
#include "kudu/gutil/macros.h"
#include "kudu/util/faststring.h"
#include "kudu/util/slice.h"
#include "kudu/util/status.h"

namespace kudu {
namespace cfile {

// Forward decl.
class IndexBlockIterator;

struct WriterOptions;

// Index Block Builder for a particular key type.
// This works like the rest of the builders in the cfile package.
// After repeatedly calling Add(), call Finish() to encode it
// into a Slice, then you may Reset to re-use buffers.
class IndexBlockBuilder {
 public:
  explicit IndexBlockBuilder(const WriterOptions *options,
                             bool is_leaf);

  // Append an entry into the index.
  void Add(const Slice &key, const BlockPointer &ptr);

  // Finish the current index block.
  // Returns a fully encoded Slice including the data
  // as well as any necessary footer.
  // The Slice is only valid until the next call to
  // Reset().
  Slice Finish();

  // Return the key of the first entry in this index block.
  // The pointed-to data is only valid until the next call to this builder.
  Status GetFirstKey(Slice *key) const;

  // Return the number of entries already added to this index
  // block.
  size_t count() const {
    return entry_offsets_.size();
  }

  // Return an estimate of the post-encoding size of this
  // index block. This estimate should be conservative --
  // it will over-estimate rather than under-estimate, and
  // should be accurate to within a reasonable threshold,
  // but is not exact.
  size_t EstimateEncodedSize() const;

  void Reset();

 private:
  DISALLOW_COPY_AND_ASSIGN(IndexBlockBuilder);

#ifdef __clang__
  __attribute__((__unused__))
#endif
  const WriterOptions *options_;

  // Is the builder currently between Finish() and Reset()
  bool finished_;

  // Is this a leaf block?
  bool is_leaf_;

  faststring buffer_;
  std::vector<uint32_t> entry_offsets_;
};

class IndexBlockReader {
 public:
  IndexBlockReader();

  void Reset();

  // Parse the given index block.
  //
  // This function may be called repeatedly to "reset" the reader to process
  // a new block.
  //
  // Note: this does not copy the data, so the slice must
  // remain valid for the lifetime of the reader (or until the next Parse call).
  Status Parse(const Slice &data);

  size_t Count() const;

  IndexBlockIterator *NewIterator() const;

  bool IsLeaf();

 private:
  friend class IndexBlockIterator;

  int CompareKey(int idx_in_block, const Slice &search_key) const;

  Status ReadEntry(size_t idx, Slice *key, BlockPointer *block_ptr) const;

  // Set *ptr to the beginning of the index data for the given index
  // entry.
  // Set *limit to the 'limit' pointer for that entry (i.e a pointer
  // beyond which the data no longer is part of that entry).
  //   - *limit can be used to prevent overrunning in the case of a
  //     corrupted length varint or length prefix
  void GetKeyPointer(int idx_in_block, const uint8_t **ptr, const uint8_t **limit) const;

  static const int kMaxTrailerSize = 64*1024;
  Slice data_;

  IndexBlockTrailerPB trailer_;
  const uint8_t *key_offsets_;
  bool parsed_;

  DISALLOW_COPY_AND_ASSIGN(IndexBlockReader);
};

class IndexBlockIterator {
 public:
  explicit IndexBlockIterator(const IndexBlockReader *reader);

  // Reset the state of this iterator. This should be used
  // after the associated 'reader' object parses a different block.
  void Reset();

  // Find the highest block pointer in this index
  // block which has a value <= the given key.
  // If such a block is found, returns OK status.
  // If no such block is found (i.e the smallest key in the
  // index is still larger than the provided key), then
  // Status::NotFound is returned.
  //
  // If this function returns an error, then the state of this
  // iterator is undefined (i.e it may or may not have moved
  // since the previous call)
  Status SeekAtOrBefore(const Slice &search_key);

  Status SeekToIndex(size_t idx);

  bool HasNext() const;

  Status Next();

  const BlockPointer &GetCurrentBlockPointer() const;

  const Slice GetCurrentKey() const;

 private:
  const IndexBlockReader *reader_;
  size_t cur_idx_;
  Slice cur_key_;
  BlockPointer cur_ptr_;
  bool seeked_;

  DISALLOW_COPY_AND_ASSIGN(IndexBlockIterator);
};

} // namespace cfile
} // namespace kudu
#endif