ceph/src/rocksdb/table/cuckoo/cuckoo_table_factory.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
   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;
  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:
  55   explicit CuckooTableFactory(const CuckooTableOptions& table_options)
  56     : table_options_(table_options) {}
  57   ~CuckooTableFactory() {}
  58
  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.
  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
  80   void* GetOptions() override { return &table_options_; }
  81
  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