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