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