#pragma once
#ifndef ROCKSDB_LITE
#include <string>
#include <vector>
#include "db/dbformat.h"
#include "monitoring/histogram.h"
#include "options/cf_options.h"
#include "rocksdb/options.h"
#include "util/arena.h"
#include "util/hash.h"
#include "util/murmurhash.h"
namespace rocksdb {
class PlainTableIndex {
public:
enum IndexSearchResult {
kNoPrefixForBucket = 0,
kDirectToFile = 1,
kSubindex = 2
};
explicit PlainTableIndex(Slice data) { InitFromRawData(data); }
PlainTableIndex()
: index_size_(0),
sub_index_size_(0),
num_prefixes_(0),
index_(nullptr),
sub_index_(nullptr) {}
IndexSearchResult GetOffset(uint32_t prefix_hash,
uint32_t* bucket_value) const;
Status InitFromRawData(Slice data);
const char* GetSubIndexBasePtrAndUpperBound(uint32_t offset,
uint32_t* upper_bound) const {
const char* index_ptr = &sub_index_[offset];
return GetVarint32Ptr(index_ptr, index_ptr + 4, upper_bound);
}
uint32_t GetIndexSize() const { return index_size_; }
uint32_t GetSubIndexSize() const { return sub_index_size_; }
uint32_t GetNumPrefixes() const { return num_prefixes_; }
static const uint64_t kMaxFileSize = (1u << 31) - 1;
static const uint32_t kSubIndexMask = 0x80000000;
static const size_t kOffsetLen = sizeof(uint32_t);
private:
uint32_t index_size_;
uint32_t sub_index_size_;
uint32_t num_prefixes_;
uint32_t* index_;
char* sub_index_;
};
class PlainTableIndexBuilder {
public:
PlainTableIndexBuilder(Arena* arena, const ImmutableCFOptions& ioptions,
size_t index_sparseness, double hash_table_ratio,
size_t huge_page_tlb_size)
: arena_(arena),
ioptions_(ioptions),
record_list_(kRecordsPerGroup),
is_first_record_(true),
due_index_(false),
num_prefixes_(0),
num_keys_per_prefix_(0),
prev_key_prefix_hash_(0),
index_sparseness_(index_sparseness),
prefix_extractor_(ioptions.prefix_extractor),
hash_table_ratio_(hash_table_ratio),
huge_page_tlb_size_(huge_page_tlb_size) {}
void AddKeyPrefix(Slice key_prefix_slice, uint32_t key_offset);
Slice Finish();
uint32_t GetTotalSize() const {
return VarintLength(index_size_) + VarintLength(num_prefixes_) +
PlainTableIndex::kOffsetLen * index_size_ + sub_index_size_;
}
static const std::string kPlainTableIndexBlock;
private:
struct IndexRecord {
uint32_t hash; uint32_t offset; IndexRecord* next;
};
class IndexRecordList {
public:
explicit IndexRecordList(size_t num_records_per_group)
: kNumRecordsPerGroup(num_records_per_group),
current_group_(nullptr),
num_records_in_current_group_(num_records_per_group) {}
~IndexRecordList() {
for (size_t i = 0; i < groups_.size(); i++) {
delete[] groups_[i];
}
}
void AddRecord(uint32_t hash, uint32_t offset);
size_t GetNumRecords() const {
return (groups_.size() - 1) * kNumRecordsPerGroup +
num_records_in_current_group_;
}
IndexRecord* At(size_t index) {
return &(groups_[index / kNumRecordsPerGroup]
[index % kNumRecordsPerGroup]);
}
private:
IndexRecord* AllocateNewGroup() {
IndexRecord* result = new IndexRecord[kNumRecordsPerGroup];
groups_.push_back(result);
return result;
}
const size_t kNumRecordsPerGroup;
IndexRecord* current_group_;
std::vector<IndexRecord*> groups_;
size_t num_records_in_current_group_;
};
void AllocateIndex();
void BucketizeIndexes(std::vector<IndexRecord*>* hash_to_offsets,
std::vector<uint32_t>* entries_per_bucket);
Slice FillIndexes(const std::vector<IndexRecord*>& hash_to_offsets,
const std::vector<uint32_t>& entries_per_bucket);
Arena* arena_;
const ImmutableCFOptions ioptions_;
HistogramImpl keys_per_prefix_hist_;
IndexRecordList record_list_;
bool is_first_record_;
bool due_index_;
uint32_t num_prefixes_;
uint32_t num_keys_per_prefix_;
uint32_t prev_key_prefix_hash_;
size_t index_sparseness_;
uint32_t index_size_;
uint32_t sub_index_size_;
const SliceTransform* prefix_extractor_;
double hash_table_ratio_;
size_t huge_page_tlb_size_;
std::string prev_key_prefix_;
static const size_t kRecordsPerGroup = 256;
};
};
#endif