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