ceph/src/rocksdb/table/cuckoo_table_builder.h

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