ceph/src/rocksdb/table/cuckoo/cuckoo_table_builder.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 #include <stdint.h>
   9
  10 #include <limits>
  11 #include <string>
  12 #include <utility>
  13 #include <vector>
  14
  15 #include "db/version_edit.h"
  16 #include "port/port.h"
  17 #include "rocksdb/status.h"
  18 #include "rocksdb/table.h"
  19 #include "rocksdb/table_properties.h"
  20 #include "table/table_builder.h"
  21 #include "util/autovector.h"
  22
  23 namespace ROCKSDB_NAMESPACE {
  24
  25 class CuckooTableBuilder : public TableBuilder {
  26  public:
  27   CuckooTableBuilder(
  28       WritableFileWriter* file, double max_hash_table_ratio,
  29       uint32_t max_num_hash_func, uint32_t max_search_depth,
  30       const Comparator* user_comparator, uint32_t cuckoo_block_size,
  31       bool use_module_hash, bool identity_as_first_hash,
  32       uint64_t (*get_slice_hash)(const Slice&, uint32_t, uint64_t),
  33       uint32_t column_family_id, const std::string& column_family_name,
  34       const std::string& db_id = "", const std::string& db_session_id = "",
  35       uint64_t file_number = 0);
  36   // No copying allowed
  37   CuckooTableBuilder(const CuckooTableBuilder&) = delete;
  38   void operator=(const CuckooTableBuilder&) = delete;
  39
  40   // REQUIRES: Either Finish() or Abandon() has been called.
  41   ~CuckooTableBuilder() {}
  42
  43   // Add key,value to the table being constructed.
  44   // REQUIRES: key is after any previously added key according to comparator.
  45   // REQUIRES: Finish(), Abandon() have not been called
  46   void Add(const Slice& key, const Slice& value) override;
  47
  48   // Return non-ok iff some error has been detected.
  49   Status status() const override { return status_; }
  50
  51   // Return non-ok iff some error happens during IO.
  52   IOStatus io_status() const override { return io_status_; }
  53
  54   // Finish building the table.  Stops using the file passed to the
  55   // constructor after this function returns.
  56   // REQUIRES: Finish(), Abandon() have not been called
  57   Status Finish() override;
  58
  59   // Indicate that the contents of this builder should be abandoned.  Stops
  60   // using the file passed to the constructor after this function returns.
  61   // If the caller is not going to call Finish(), it must call Abandon()
  62   // before destroying this builder.
  63   // REQUIRES: Finish(), Abandon() have not been called
  64   void Abandon() override;
  65
  66   // Number of calls to Add() so far.
  67   uint64_t NumEntries() const override;
  68
  69   // Size of the file generated so far.  If invoked after a successful
  70   // Finish() call, returns the size of the final generated file.
  71   uint64_t FileSize() const override;
  72
  73   TableProperties GetTableProperties() const override { return properties_; }
  74
  75   // Get file checksum
  76   std::string GetFileChecksum() const override;
  77
  78   // Get file checksum function name
  79   const char* GetFileChecksumFuncName() const override;
  80
  81  private:
  82   struct CuckooBucket {
  83     CuckooBucket() : vector_idx(kMaxVectorIdx), make_space_for_key_call_id(0) {}
  84     uint32_t vector_idx;
  85     // This number will not exceed kvs_.size() + max_num_hash_func_.
  86     // We assume number of items is <= 2^32.
  87     uint32_t make_space_for_key_call_id;
  88   };
  89   static const uint32_t kMaxVectorIdx = std::numeric_limits<int32_t>::max();
  90
  91   bool MakeSpaceForKey(const autovector<uint64_t>& hash_vals,
  92                        const uint32_t call_id,
  93                        std::vector<CuckooBucket>* buckets, uint64_t* bucket_id);
  94   Status MakeHashTable(std::vector<CuckooBucket>* buckets);
  95
  96   inline bool IsDeletedKey(uint64_t idx) const;
  97   inline Slice GetKey(uint64_t idx) const;
  98   inline Slice GetUserKey(uint64_t idx) const;
  99   inline Slice GetValue(uint64_t idx) const;
 100
 101   uint32_t num_hash_func_;
 102   WritableFileWriter* file_;
 103   const double max_hash_table_ratio_;
 104   const uint32_t max_num_hash_func_;
 105   const uint32_t max_search_depth_;
 106   const uint32_t cuckoo_block_size_;
 107   uint64_t hash_table_size_;
 108   bool is_last_level_file_;
 109   bool has_seen_first_key_;
 110   bool has_seen_first_value_;
 111   uint64_t key_size_;
 112   uint64_t value_size_;
 113   // A list of fixed-size key-value pairs concatenating into a string.
 114   // Use GetKey(), GetUserKey(), and GetValue() to retrieve a specific
 115   // key / value given an index
 116   std::string kvs_;
 117   std::string deleted_keys_;
 118   // Number of key-value pairs stored in kvs_ + number of deleted keys
 119   uint64_t num_entries_;
 120   // Number of keys that contain value (non-deletion op)
 121   uint64_t num_values_;
 122   Status status_;
 123   IOStatus io_status_;
 124   TableProperties properties_;
 125   const Comparator* ucomp_;
 126   bool use_module_hash_;
 127   bool identity_as_first_hash_;
 128   uint64_t (*get_slice_hash_)(const Slice& s, uint32_t index,
 129                               uint64_t max_num_buckets);
 130   std::string largest_user_key_ = "";
 131   std::string smallest_user_key_ = "";
 132
 133   bool closed_;  // Either Finish() or Abandon() has been called.
 134 };
 135
 136 }  // namespace ROCKSDB_NAMESPACE
 137
 138 #endif  // ROCKSDB_LITE