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
6 #pragma once
7 #ifndef ROCKSDB_LITE
8
9 #include <string>
10 #include "rocksdb/table.h"
11 #include "util/murmurhash.h"
12 #include "rocksdb/options.h"
13
14 namespace ROCKSDB_NAMESPACE {
15
16 const uint32_t kCuckooMurmurSeedMultiplier = 816922183;
CuckooHash(const Slice & user_key,uint32_t hash_cnt,bool use_module_hash,uint64_t table_size_,bool identity_as_first_hash,uint64_t (* get_slice_hash)(const Slice &,uint32_t,uint64_t))17 static inline uint64_t CuckooHash(
18 const Slice& user_key, uint32_t hash_cnt, bool use_module_hash,
19 uint64_t table_size_, bool identity_as_first_hash,
20 uint64_t (*get_slice_hash)(const Slice&, uint32_t, uint64_t)) {
21 #if !defined NDEBUG || defined OS_WIN
22 // This part is used only in unit tests but we have to keep it for Windows
23 // build as we run test in both debug and release modes under Windows.
24 if (get_slice_hash != nullptr) {
25 return get_slice_hash(user_key, hash_cnt, table_size_);
26 }
27 #else
28 (void)get_slice_hash;
29 #endif
30
31 uint64_t value = 0;
32 if (hash_cnt == 0 && identity_as_first_hash) {
33 value = (*reinterpret_cast<const int64_t*>(user_key.data()));
34 } else {
35 value = MurmurHash(user_key.data(), static_cast<int>(user_key.size()),
36 kCuckooMurmurSeedMultiplier * hash_cnt);
37 }
38 if (use_module_hash) {
39 return value % table_size_;
40 } else {
41 return value & (table_size_ - 1);
42 }
43 }
44
45 // Cuckoo Table is designed for applications that require fast point lookups
46 // but not fast range scans.
47 //
48 // Some assumptions:
49 // - Key length and Value length are fixed.
50 // - Does not support Snapshot.
51 // - Does not support Merge operations.
52 // - Does not support prefix bloom filters.
53 class CuckooTableFactory : public TableFactory {
54 public:
CuckooTableFactory(const CuckooTableOptions & table_options)55 explicit CuckooTableFactory(const CuckooTableOptions& table_options)
56 : table_options_(table_options) {}
~CuckooTableFactory()57 ~CuckooTableFactory() {}
58
Name()59 const char* Name() const override { return "CuckooTable"; }
60
61 Status NewTableReader(
62 const TableReaderOptions& table_reader_options,
63 std::unique_ptr<RandomAccessFileReader>&& file, uint64_t file_size,
64 std::unique_ptr<TableReader>* table,
65 bool prefetch_index_and_filter_in_cache = true) const override;
66
67 TableBuilder* NewTableBuilder(
68 const TableBuilderOptions& table_builder_options,
69 uint32_t column_family_id, WritableFileWriter* file) const override;
70
71 // Sanitizes the specified DB Options.
SanitizeOptions(const DBOptions &,const ColumnFamilyOptions &)72 Status SanitizeOptions(
73 const DBOptions& /*db_opts*/,
74 const ColumnFamilyOptions& /*cf_opts*/) const override {
75 return Status::OK();
76 }
77
78 std::string GetPrintableTableOptions() const override;
79
GetOptions()80 void* GetOptions() override { return &table_options_; }
81
GetOptionString(std::string *,const std::string &)82 Status GetOptionString(std::string* /*opt_string*/,
83 const std::string& /*delimiter*/) const override {
84 return Status::OK();
85 }
86
87 private:
88 CuckooTableOptions table_options_;
89 };
90
91 } // namespace ROCKSDB_NAMESPACE
92 #endif // ROCKSDB_LITE
93