ceph/src/rocksdb/table/block_based/block_prefix_index.h

   1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 #pragma once
   6
   7 #include <stdint.h>
   8
   9 #include "db/dbformat.h"
  10 #include "rocksdb/status.h"
  11
  12 namespace ROCKSDB_NAMESPACE {
  13
  14 class Comparator;
  15 class Iterator;
  16 class Slice;
  17 class SliceTransform;
  18
  19 // Build a hash-based index to speed up the lookup for "index block".
  20 // BlockHashIndex accepts a key and, if found, returns its restart index within
  21 // that index block.
  22 class BlockPrefixIndex {
  23  public:
  24   // Maps a key to a list of data blocks that could potentially contain
  25   // the key, based on the prefix.
  26   // Returns the total number of relevant blocks, 0 means the key does
  27   // not exist.
  28   uint32_t GetBlocks(const Slice& key, uint32_t** blocks);
  29
  30   size_t ApproximateMemoryUsage() const {
  31     return sizeof(BlockPrefixIndex) +
  32            (num_block_array_buffer_entries_ + num_buckets_) * sizeof(uint32_t);
  33   }
  34
  35   // Create hash index by reading from the metadata blocks.
  36   // Note: table reader (caller) is responsible for keeping shared_ptr to
  37   // underlying prefix extractor
  38   // @params prefixes: a sequence of prefixes.
  39   // @params prefix_meta: contains the "metadata" to of the prefixes.
  40   static Status Create(const SliceTransform* hash_key_extractor,
  41                        const Slice& prefixes, const Slice& prefix_meta,
  42                        BlockPrefixIndex** prefix_index);
  43
  44   ~BlockPrefixIndex() {
  45     delete[] buckets_;
  46     delete[] block_array_buffer_;
  47   }
  48
  49  private:
  50   class Builder;
  51   friend Builder;
  52
  53   BlockPrefixIndex(const SliceTransform* prefix_extractor, uint32_t num_buckets,
  54                    uint32_t* buckets, uint32_t num_block_array_buffer_entries,
  55                    uint32_t* block_array_buffer)
  56       : internal_prefix_extractor_(prefix_extractor),
  57         num_buckets_(num_buckets),
  58         num_block_array_buffer_entries_(num_block_array_buffer_entries),
  59         buckets_(buckets),
  60         block_array_buffer_(block_array_buffer) {}
  61
  62   InternalKeySliceTransform internal_prefix_extractor_;
  63
  64   uint32_t num_buckets_;
  65   uint32_t num_block_array_buffer_entries_;
  66   uint32_t* buckets_;
  67   uint32_t* block_array_buffer_;
  68 };
  69
  70 }  // namespace ROCKSDB_NAMESPACE