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 #include "rocksdb/status.h"
9 
10 namespace ROCKSDB_NAMESPACE {
11 
12 class Comparator;
13 class Iterator;
14 class Slice;
15 class SliceTransform;
16 
17 // Build a hash-based index to speed up the lookup for "index block".
18 // BlockHashIndex accepts a key and, if found, returns its restart index within
19 // that index block.
20 class BlockPrefixIndex {
21  public:
22   // Maps a key to a list of data blocks that could potentially contain
23   // the key, based on the prefix.
24   // Returns the total number of relevant blocks, 0 means the key does
25   // not exist.
26   uint32_t GetBlocks(const Slice& key, uint32_t** blocks);
27 
ApproximateMemoryUsage()28   size_t ApproximateMemoryUsage() const {
29     return sizeof(BlockPrefixIndex) +
30            (num_block_array_buffer_entries_ + num_buckets_) * sizeof(uint32_t);
31   }
32 
33   // Create hash index by reading from the metadata blocks.
34   // @params prefixes: a sequence of prefixes.
35   // @params prefix_meta: contains the "metadata" to of the prefixes.
36   static Status Create(const SliceTransform* hash_key_extractor,
37                        const Slice& prefixes, const Slice& prefix_meta,
38                        BlockPrefixIndex** prefix_index);
39 
~BlockPrefixIndex()40   ~BlockPrefixIndex() {
41     delete[] buckets_;
42     delete[] block_array_buffer_;
43   }
44 
45  private:
46   class Builder;
47   friend Builder;
48 
BlockPrefixIndex(const SliceTransform * internal_prefix_extractor,uint32_t num_buckets,uint32_t * buckets,uint32_t num_block_array_buffer_entries,uint32_t * block_array_buffer)49   BlockPrefixIndex(const SliceTransform* internal_prefix_extractor,
50                    uint32_t num_buckets, uint32_t* buckets,
51                    uint32_t num_block_array_buffer_entries,
52                    uint32_t* block_array_buffer)
53       : internal_prefix_extractor_(internal_prefix_extractor),
54         num_buckets_(num_buckets),
55         num_block_array_buffer_entries_(num_block_array_buffer_entries),
56         buckets_(buckets),
57         block_array_buffer_(block_array_buffer) {}
58 
59   const SliceTransform* internal_prefix_extractor_;
60   uint32_t num_buckets_;
61   uint32_t num_block_array_buffer_entries_;
62   uint32_t* buckets_;
63   uint32_t* block_array_buffer_;
64 };
65 
66 }  // namespace ROCKSDB_NAMESPACE
67