http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/c123bd49/storage/FastSeparateChainingHashTable.hpp ---------------------------------------------------------------------- diff --git a/storage/FastSeparateChainingHashTable.hpp b/storage/FastSeparateChainingHashTable.hpp index 0670993..886a8ca 100644 --- a/storage/FastSeparateChainingHashTable.hpp +++ b/storage/FastSeparateChainingHashTable.hpp @@ -27,8 +27,8 @@ #include <utility> #include <vector> -#include "storage/HashTable.hpp" #include "storage/FastHashTable.hpp" +#include "storage/HashTable.hpp" #include "storage/HashTableBase.hpp" #include "storage/HashTableKeyManager.hpp" #include "storage/StorageBlob.hpp" @@ -55,43 +55,42 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -class FastSeparateChainingHashTable : public FastHashTable<resizable, - serializable, - force_key_copy, - allow_duplicate_keys> { +class FastSeparateChainingHashTable + : public FastHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys> { public: - FastSeparateChainingHashTable(const std::vector<const Type*> &key_types, - const std::size_t num_entries, - const std::vector<std::size_t> &payload_sizes, - const std::vector<AggregationHandle *> &handles, - StorageManager *storage_manager); - - FastSeparateChainingHashTable(const std::vector<const Type*> &key_types, - void *hash_table_memory, - const std::size_t hash_table_memory_size, - const bool new_hash_table, - const bool hash_table_memory_zeroed); + FastSeparateChainingHashTable(const std::vector<const Type *> &key_types, + const std::size_t num_entries, + const std::vector<std::size_t> &payload_sizes, + const std::vector<AggregationHandle *> &handles, + StorageManager *storage_manager); + + FastSeparateChainingHashTable(const std::vector<const Type *> &key_types, + void *hash_table_memory, + const std::size_t hash_table_memory_size, + const bool new_hash_table, + const bool hash_table_memory_zeroed); // Delegating constructors for single scalar keys. FastSeparateChainingHashTable(const Type &key_type, - const std::size_t num_entries, - StorageManager *storage_manager) - : FastSeparateChainingHashTable(std::vector<const Type*>(1, &key_type), - num_entries, - storage_manager) { - } + const std::size_t num_entries, + StorageManager *storage_manager) + : FastSeparateChainingHashTable(std::vector<const Type *>(1, &key_type), + num_entries, + storage_manager) {} FastSeparateChainingHashTable(const Type &key_type, - void *hash_table_memory, - const std::size_t hash_table_memory_size, - const bool new_hash_table, - const bool hash_table_memory_zeroed) - : FastSeparateChainingHashTable(std::vector<const Type*>(1, &key_type), - hash_table_memory, - hash_table_memory_size, - new_hash_table, - hash_table_memory_zeroed) { - } + void *hash_table_memory, + const std::size_t hash_table_memory_size, + const bool new_hash_table, + const bool hash_table_memory_zeroed) + : FastSeparateChainingHashTable(std::vector<const Type *>(1, &key_type), + hash_table_memory, + hash_table_memory_size, + new_hash_table, + hash_table_memory_zeroed) {} ~FastSeparateChainingHashTable() override { DestroyValues(buckets_, @@ -106,48 +105,54 @@ class FastSeparateChainingHashTable : public FastHashTable<resizable, return header_->buckets_allocated.load(std::memory_order_relaxed); } - const uint8_t* getSingle(const TypedValue &key) const override; - const uint8_t* getSingleCompositeKey(const std::vector<TypedValue> &key) const override; - const uint8_t* getSingleCompositeKey(const std::vector<TypedValue> &key, int index) const override; + const std::uint8_t* getSingle(const TypedValue &key) const override; + const std::uint8_t* getSingleCompositeKey( + const std::vector<TypedValue> &key) const override; + const std::uint8_t* getSingleCompositeKey(const std::vector<TypedValue> &key, + int index) const override; void getAll(const TypedValue &key, - std::vector<const uint8_t*> *values) const override; - void getAllCompositeKey(const std::vector<TypedValue> &key, - std::vector<const uint8_t*> *values) const override; + std::vector<const std::uint8_t *> *values) const override; + void getAllCompositeKey( + const std::vector<TypedValue> &key, + std::vector<const std::uint8_t *> *values) const override; protected: - HashTablePutResult putInternal(const TypedValue &key, - const std::size_t variable_key_size, - const uint8_t &value, - HashTablePreallocationState *prealloc_state) override; - - HashTablePutResult putCompositeKeyInternalFast(const std::vector<TypedValue> &key, - const std::size_t variable_key_size, - const std::uint8_t *init_value_ptr, - HashTablePreallocationState *prealloc_state) override; - - uint8_t* upsertInternalFast(const TypedValue &key, - const std::size_t variable_key_size, - const std::uint8_t *init_value_ptr) override; - - uint8_t* upsertCompositeKeyInternalFast(const std::vector<TypedValue> &key, - const std::uint8_t *init_value_ptr, - const std::size_t variable_key_size) override; + HashTablePutResult putInternal( + const TypedValue &key, + const std::size_t variable_key_size, + const std::uint8_t &value, + HashTablePreallocationState *prealloc_state) override; + + HashTablePutResult putCompositeKeyInternalFast( + const std::vector<TypedValue> &key, + const std::size_t variable_key_size, + const std::uint8_t *init_value_ptr, + HashTablePreallocationState *prealloc_state) override; + + std::uint8_t* upsertInternalFast(const TypedValue &key, + const std::size_t variable_key_size, + const std::uint8_t *init_value_ptr) override; + + std::uint8_t* upsertCompositeKeyInternalFast( + const std::vector<TypedValue> &key, + const std::uint8_t *init_value_ptr, + const std::size_t variable_key_size) override; bool getNextEntry(TypedValue *key, - const uint8_t **value, + const std::uint8_t **value, std::size_t *entry_num) const override; bool getNextEntryCompositeKey(std::vector<TypedValue> *key, - const uint8_t **value, + const std::uint8_t **value, std::size_t *entry_num) const override; bool getNextEntryForKey(const TypedValue &key, const std::size_t hash_code, - const uint8_t **value, + const std::uint8_t **value, std::size_t *entry_num) const override; bool getNextEntryForCompositeKey(const std::vector<TypedValue> &key, const std::size_t hash_code, - const uint8_t **value, + const std::uint8_t **value, std::size_t *entry_num) const override; bool hasKey(const TypedValue &key) const override; @@ -157,15 +162,16 @@ class FastSeparateChainingHashTable : public FastHashTable<resizable, const std::size_t extra_variable_storage, const std::size_t retry_num = 0) override; - bool preallocateForBulkInsert(const std::size_t total_entries, - const std::size_t total_variable_key_size, - HashTablePreallocationState *prealloc_state) override; + bool preallocateForBulkInsert( + const std::size_t total_entries, + const std::size_t total_variable_key_size, + HashTablePreallocationState *prealloc_state) override; + private: struct Header { std::size_t num_slots; std::size_t num_buckets; - alignas(kCacheLineBytes) - std::atomic<std::size_t> buckets_allocated; + alignas(kCacheLineBytes) std::atomic<std::size_t> buckets_allocated; alignas(kCacheLineBytes) std::atomic<std::size_t> variable_length_bytes_allocated; }; @@ -179,16 +185,18 @@ class FastSeparateChainingHashTable : public FastHashTable<resizable, // Round bucket size up to a multiple of kBucketAlignment. constexpr std::size_t ComputeBucketSize(const std::size_t fixed_key_size) { - return (((kValueOffset + this->total_payload_size_ + fixed_key_size - 1) / kBucketAlignment) + 1) - * kBucketAlignment; + return (((kValueOffset + this->total_payload_size_ + fixed_key_size - 1) / + kBucketAlignment) + + 1) * + kBucketAlignment; } // If ValueT is not trivially destructible, invoke its destructor for all // values held in the specified buckets (including those in "empty" buckets // that were default constructed). If ValueT is trivially destructible, this // is a no-op. void DestroyValues(void *buckets, - const std::size_t num_buckets, - const std::size_t bucket_size); + const std::size_t num_buckets, + const std::size_t bucket_size); // Attempt to find an empty bucket to insert 'hash_code' into, starting after // '*bucket' in the chain (or, if '*bucket' is NULL, starting from the slot @@ -201,30 +209,33 @@ class FastSeparateChainingHashTable : public FastHashTable<resizable, // attempt to allocate storage for a variable-length key BEFORE allocating a // bucket, so that no bucket number below 'header_->num_buckets' is ever // deallocated after being allocated. - inline bool locateBucketForInsertion(const std::size_t hash_code, - const std::size_t variable_key_allocation_required, - void **bucket, - std::atomic<std::size_t> **pending_chain_ptr, - std::size_t *pending_chain_ptr_finish_value, - HashTablePreallocationState *prealloc_state); + inline bool locateBucketForInsertion( + const std::size_t hash_code, + const std::size_t variable_key_allocation_required, + void **bucket, + std::atomic<std::size_t> **pending_chain_ptr, + std::size_t *pending_chain_ptr_finish_value, + HashTablePreallocationState *prealloc_state); // Write a scalar 'key' and its 'hash_code' into the '*bucket', which was // found by locateBucketForInsertion(). Assumes that storage for a // variable-length key copy (if any) was already allocated by a successful // call to allocateVariableLengthKeyStorage(). - inline void writeScalarKeyToBucket(const TypedValue &key, - const std::size_t hash_code, - void *bucket, - HashTablePreallocationState *prealloc_state); + inline void writeScalarKeyToBucket( + const TypedValue &key, + const std::size_t hash_code, + void *bucket, + HashTablePreallocationState *prealloc_state); // Write a composite 'key' and its 'hash_code' into the '*bucket', which was // found by locateBucketForInsertion(). Assumes that storage for // variable-length key copies (if any) was already allocated by a successful // call to allocateVariableLengthKeyStorage(). - inline void writeCompositeKeyToBucket(const std::vector<TypedValue> &key, - const std::size_t hash_code, - void *bucket, - HashTablePreallocationState *prealloc_state); + inline void writeCompositeKeyToBucket( + const std::vector<TypedValue> &key, + const std::size_t hash_code, + void *bucket, + HashTablePreallocationState *prealloc_state); // Determine whether it is actually necessary to resize this hash table. // Checks that there is at least one unallocated bucket, and that there is @@ -275,30 +286,37 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::FastSeparateChainingHashTable(const std::vector<const Type*> &key_types, - const std::size_t num_entries, - const std::vector<std::size_t> &payload_sizes, - const std::vector<AggregationHandle *> &handles, - StorageManager *storage_manager) - : FastHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys>( - key_types, - num_entries, - handles, - payload_sizes, - storage_manager, - false, - false, - true), - kBucketAlignment(alignof(std::atomic<std::size_t>)), - kValueOffset(sizeof(std::atomic<std::size_t>) + sizeof(std::size_t)), - key_manager_(this->key_types_, kValueOffset + this->total_payload_size_), - bucket_size_(ComputeBucketSize(key_manager_.getFixedKeySize())) { - init_payload_ = static_cast<std::uint8_t *>(calloc(this->total_payload_size_, 1)); +FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + FastSeparateChainingHashTable( + const std::vector<const Type *> &key_types, + const std::size_t num_entries, + const std::vector<std::size_t> &payload_sizes, + const std::vector<AggregationHandle *> &handles, + StorageManager *storage_manager) + : FastHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>(key_types, + num_entries, + handles, + payload_sizes, + storage_manager, + false, + false, + true), + kBucketAlignment(alignof(std::atomic<std::size_t>)), + kValueOffset(sizeof(std::atomic<std::size_t>) + sizeof(std::size_t)), + key_manager_(this->key_types_, kValueOffset + this->total_payload_size_), + bucket_size_(ComputeBucketSize(key_manager_.getFixedKeySize())) { + init_payload_ = + static_cast<std::uint8_t *>(calloc(this->total_payload_size_, 1)); int k = 0; for (auto handle : handles) { - handle->initPayload(init_payload_+this->payload_offsets_[k]); - k++; + handle->initPayload(init_payload_ + this->payload_offsets_[k]); + k++; } // Bucket size always rounds up to the alignment requirement of the atomic // size_t "next" pointer at the front or a ValueT, whichever is larger. @@ -308,19 +326,23 @@ FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_dup this->setKeyInline(key_manager_.getKeyInline()); // Pick out a prime number of slots and calculate storage requirements. - std::size_t num_slots_tmp = get_next_prime_number(num_entries * kHashTableLoadFactor); - std::size_t required_memory = sizeof(Header) - + num_slots_tmp * sizeof(std::atomic<std::size_t>) - + (num_slots_tmp / kHashTableLoadFactor) - * (bucket_size_ + key_manager_.getEstimatedVariableKeySize()); - std::size_t num_storage_slots = this->storage_manager_->SlotsNeededForBytes(required_memory); + std::size_t num_slots_tmp = + get_next_prime_number(num_entries * kHashTableLoadFactor); + std::size_t required_memory = + sizeof(Header) + num_slots_tmp * sizeof(std::atomic<std::size_t>) + + (num_slots_tmp / kHashTableLoadFactor) * + (bucket_size_ + key_manager_.getEstimatedVariableKeySize()); + std::size_t num_storage_slots = + this->storage_manager_->SlotsNeededForBytes(required_memory); if (num_storage_slots == 0) { - FATAL_ERROR("Storage requirement for SeparateChainingHashTable " - "exceeds maximum allocation size."); + FATAL_ERROR( + "Storage requirement for SeparateChainingHashTable " + "exceeds maximum allocation size."); } // Get a StorageBlob to hold the hash table. - const block_id blob_id = this->storage_manager_->createBlob(num_storage_slots); + const block_id blob_id = + this->storage_manager_->createBlob(num_storage_slots); this->blob_ = this->storage_manager_->getBlobMutable(blob_id); void *aligned_memory_start = this->blob_->getMemoryMutable(); @@ -328,14 +350,14 @@ FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_dup if (align(alignof(Header), sizeof(Header), aligned_memory_start, - available_memory) - == nullptr) { + available_memory) == nullptr) { // With current values from StorageConstants.hpp, this should be // impossible. A blob is at least 1 MB, while a Header has alignment // requirement of just kCacheLineBytes (64 bytes). - FATAL_ERROR("StorageBlob used to hold resizable " - "SeparateChainingHashTable is too small to meet alignment " - "requirements of SeparateChainingHashTable::Header."); + FATAL_ERROR( + "StorageBlob used to hold resizable " + "SeparateChainingHashTable is too small to meet alignment " + "requirements of SeparateChainingHashTable::Header."); } else if (aligned_memory_start != this->blob_->getMemoryMutable()) { // This should also be impossible, since the StorageManager allocates slots // aligned to kCacheLineBytes. @@ -346,8 +368,9 @@ FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_dup } // Locate the header. - header_ = static_cast<Header*>(aligned_memory_start); - aligned_memory_start = static_cast<char*>(aligned_memory_start) + sizeof(Header); + header_ = static_cast<Header *>(aligned_memory_start); + aligned_memory_start = + static_cast<char *>(aligned_memory_start) + sizeof(Header); available_memory -= sizeof(Header); // Recompute the number of slots & buckets using the actual available memory. @@ -355,19 +378,20 @@ FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_dup // the storage blob's size. It's also possible (though very unlikely) that we // will wind up with fewer buckets than we initially wanted because of screwy // alignment requirements for ValueT. - std::size_t num_buckets_tmp - = available_memory / (kHashTableLoadFactor * sizeof(std::atomic<std::size_t>) - + bucket_size_ - + key_manager_.getEstimatedVariableKeySize()); - num_slots_tmp = get_previous_prime_number(num_buckets_tmp * kHashTableLoadFactor); + std::size_t num_buckets_tmp = + available_memory / + (kHashTableLoadFactor * sizeof(std::atomic<std::size_t>) + bucket_size_ + + key_manager_.getEstimatedVariableKeySize()); + num_slots_tmp = + get_previous_prime_number(num_buckets_tmp * kHashTableLoadFactor); num_buckets_tmp = num_slots_tmp / kHashTableLoadFactor; DEBUG_ASSERT(num_slots_tmp > 0); DEBUG_ASSERT(num_buckets_tmp > 0); // Locate the slot array. - slots_ = static_cast<std::atomic<std::size_t>*>(aligned_memory_start); - aligned_memory_start = static_cast<char*>(aligned_memory_start) - + sizeof(std::atomic<std::size_t>) * num_slots_tmp; + slots_ = static_cast<std::atomic<std::size_t> *>(aligned_memory_start); + aligned_memory_start = static_cast<char *>(aligned_memory_start) + + sizeof(std::atomic<std::size_t>) * num_slots_tmp; available_memory -= sizeof(std::atomic<std::size_t>) * num_slots_tmp; // Locate the buckets. @@ -375,17 +399,16 @@ FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_dup // Extra-paranoid: If ValueT has an alignment requirement greater than that // of std::atomic<std::size_t>, we may need to adjust the start of the bucket // array. - if (align(kBucketAlignment, - bucket_size_, - buckets_, - available_memory) - == nullptr) { - FATAL_ERROR("StorageBlob used to hold resizable " - "SeparateChainingHashTable is too small to meet " - "alignment requirements of buckets."); + if (align(kBucketAlignment, bucket_size_, buckets_, available_memory) == + nullptr) { + FATAL_ERROR( + "StorageBlob used to hold resizable " + "SeparateChainingHashTable is too small to meet " + "alignment requirements of buckets."); } else if (buckets_ != aligned_memory_start) { - DEV_WARNING("Bucket array start position adjusted to meet alignment " - "requirement for SeparateChainingHashTable's value type."); + DEV_WARNING( + "Bucket array start position adjusted to meet alignment " + "requirement for SeparateChainingHashTable's value type."); if (num_buckets_tmp * bucket_size_ > available_memory) { --num_buckets_tmp; } @@ -401,7 +424,7 @@ FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_dup // Locate variable-length key storage region, and give it all the remaining // bytes in the blob. key_manager_.setVariableLengthStorageInfo( - static_cast<char*>(buckets_) + header_->num_buckets * bucket_size_, + static_cast<char *>(buckets_) + header_->num_buckets * bucket_size_, available_memory, &(header_->variable_length_bytes_allocated)); } @@ -410,36 +433,43 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::FastSeparateChainingHashTable(const std::vector<const Type*> &key_types, - void *hash_table_memory, - const std::size_t hash_table_memory_size, - const bool new_hash_table, - const bool hash_table_memory_zeroed) - : FastHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys>( - key_types, - hash_table_memory, - hash_table_memory_size, - new_hash_table, - hash_table_memory_zeroed, - false, - false, - true), - kBucketAlignment(alignof(std::atomic<std::size_t>) < alignof(uint8_t) ? alignof(uint8_t) - : alignof(std::atomic<std::size_t>)), - kValueOffset(sizeof(std::atomic<std::size_t>) + sizeof(std::size_t)), - key_manager_(this->key_types_, kValueOffset + sizeof(uint8_t)), - bucket_size_(ComputeBucketSize(key_manager_.getFixedKeySize())) { +FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + FastSeparateChainingHashTable(const std::vector<const Type *> &key_types, + void *hash_table_memory, + const std::size_t hash_table_memory_size, + const bool new_hash_table, + const bool hash_table_memory_zeroed) + : FastHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>(key_types, + hash_table_memory, + hash_table_memory_size, + new_hash_table, + hash_table_memory_zeroed, + false, + false, + true), + kBucketAlignment(alignof(std::atomic<std::size_t>) < alignof(std::uint8_t) + ? alignof(std::uint8_t) + : alignof(std::atomic<std::size_t>)), + kValueOffset(sizeof(std::atomic<std::size_t>) + sizeof(std::size_t)), + key_manager_(this->key_types_, kValueOffset + sizeof(std::uint8_t)), + bucket_size_(ComputeBucketSize(key_manager_.getFixedKeySize())) { // Bucket size always rounds up to the alignment requirement of the atomic // size_t "next" pointer at the front or a ValueT, whichever is larger. // // Make sure that the larger of the two alignment requirements also satisfies // the smaller. - static_assert(alignof(std::atomic<std::size_t>) < alignof(uint8_t) - ? alignof(uint8_t) % alignof(std::atomic<std::size_t>) == 0 - : alignof(std::atomic<std::size_t>) % alignof(uint8_t) == 0, - "Alignment requirement of std::atomic<std::size_t> does not " - "evenly divide with alignment requirement of ValueT."); + static_assert( + alignof(std::atomic<std::size_t>) < alignof(std::uint8_t) + ? alignof(std::uint8_t) % alignof(std::atomic<std::size_t>) == 0 + : alignof(std::atomic<std::size_t>) % alignof(std::uint8_t) == 0, + "Alignment requirement of std::atomic<std::size_t> does not " + "evenly divide with alignment requirement of ValueT."); // Give base HashTable information about what key components are stored // inline from 'key_manager_'. @@ -460,12 +490,13 @@ FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_dup if (align(alignof(Header), sizeof(Header), aligned_memory_start, - available_memory) - == nullptr) { + available_memory) == nullptr) { FATAL_ERROR("Attempted to create a non-resizable " << "SeparateChainingHashTable with " - << available_memory << " bytes of memory at " - << aligned_memory_start << " which either can not fit a " + << available_memory + << " bytes of memory at " + << aligned_memory_start + << " which either can not fit a " << "SeparateChainingHashTable::Header or meet its alignement " << "requirement."); } else if (aligned_memory_start != this->hash_table_memory_) { @@ -477,32 +508,36 @@ FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_dup << "SeparateChainingHashTable::Header."); } - header_ = static_cast<Header*>(aligned_memory_start); - aligned_memory_start = static_cast<char*>(aligned_memory_start) + sizeof(Header); + header_ = static_cast<Header *>(aligned_memory_start); + aligned_memory_start = + static_cast<char *>(aligned_memory_start) + sizeof(Header); available_memory -= sizeof(Header); if (new_hash_table) { - std::size_t estimated_bucket_capacity - = available_memory / (kHashTableLoadFactor * sizeof(std::atomic<std::size_t>) - + bucket_size_ - + key_manager_.getEstimatedVariableKeySize()); - std::size_t num_slots = get_previous_prime_number(estimated_bucket_capacity * kHashTableLoadFactor); + std::size_t estimated_bucket_capacity = + available_memory / + (kHashTableLoadFactor * sizeof(std::atomic<std::size_t>) + + bucket_size_ + key_manager_.getEstimatedVariableKeySize()); + std::size_t num_slots = get_previous_prime_number( + estimated_bucket_capacity * kHashTableLoadFactor); // Fill in the header. header_->num_slots = num_slots; header_->num_buckets = num_slots / kHashTableLoadFactor; header_->buckets_allocated.store(0, std::memory_order_relaxed); - header_->variable_length_bytes_allocated.store(0, std::memory_order_relaxed); + header_->variable_length_bytes_allocated.store(0, + std::memory_order_relaxed); } // Locate the slot array. - slots_ = static_cast<std::atomic<std::size_t>*>(aligned_memory_start); - aligned_memory_start = static_cast<char*>(aligned_memory_start) - + sizeof(std::atomic<std::size_t>) * header_->num_slots; + slots_ = static_cast<std::atomic<std::size_t> *>(aligned_memory_start); + aligned_memory_start = static_cast<char *>(aligned_memory_start) + + sizeof(std::atomic<std::size_t>) * header_->num_slots; available_memory -= sizeof(std::atomic<std::size_t>) * header_->num_slots; if (new_hash_table && !hash_table_memory_zeroed) { - std::memset(slots_, 0x0, sizeof(std::atomic<std::size_t>) * header_->num_slots); + std::memset( + slots_, 0x0, sizeof(std::atomic<std::size_t>) * header_->num_slots); } // Locate the buckets. @@ -510,20 +545,20 @@ FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_dup // Extra-paranoid: sizeof(Header) should almost certainly be a multiple of // kBucketAlignment, unless ValueT has some members with seriously big // (> kCacheLineBytes) alignment requirements specified using alignas(). - if (align(kBucketAlignment, - bucket_size_, - buckets_, - available_memory) - == nullptr) { + if (align(kBucketAlignment, bucket_size_, buckets_, available_memory) == + nullptr) { FATAL_ERROR("Attempted to create a non-resizable " << "SeparateChainingHashTable with " - << this->hash_table_memory_size_ << " bytes of memory at " - << this->hash_table_memory_ << ", which can hold an aligned " + << this->hash_table_memory_size_ + << " bytes of memory at " + << this->hash_table_memory_ + << ", which can hold an aligned " << "SeparateChainingHashTable::Header but does not have " << "enough remaining space for even a single hash bucket."); } else if (buckets_ != aligned_memory_start) { - DEV_WARNING("Bucket array start position adjusted to meet alignment " - "requirement for SeparateChainingHashTable's value type."); + DEV_WARNING( + "Bucket array start position adjusted to meet alignment " + "requirement for SeparateChainingHashTable's value type."); if (header_->num_buckets * bucket_size_ > available_memory) { DEBUG_ASSERT(new_hash_table); --(header_->num_buckets); @@ -538,7 +573,7 @@ FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_dup // Locate variable-length key storage region. key_manager_.setVariableLengthStorageInfo( - static_cast<char*>(buckets_) + header_->num_buckets * bucket_size_, + static_cast<char *>(buckets_) + header_->num_buckets * bucket_size_, available_memory, &(header_->variable_length_bytes_allocated)); } @@ -547,16 +582,18 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::clear() { - const std::size_t used_buckets = header_->buckets_allocated.load(std::memory_order_relaxed); +void FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>::clear() { + const std::size_t used_buckets = + header_->buckets_allocated.load(std::memory_order_relaxed); // Destroy existing values, if necessary. - DestroyValues(buckets_, - used_buckets, - bucket_size_); + DestroyValues(buckets_, used_buckets, bucket_size_); // Zero-out slot array. - std::memset(slots_, 0x0, sizeof(std::atomic<std::size_t>) * header_->num_slots); + std::memset( + slots_, 0x0, sizeof(std::atomic<std::size_t>) * header_->num_slots); // Zero-out used buckets. std::memset(buckets_, 0x0, used_buckets * bucket_size_); @@ -570,24 +607,33 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -const uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::getSingle(const TypedValue &key) const { +const std::uint8_t* FastSeparateChainingHashTable< + resizable, + serializable, + force_key_copy, + allow_duplicate_keys>::getSingle(const TypedValue &key) const { DEBUG_ASSERT(!allow_duplicate_keys); DEBUG_ASSERT(this->key_types_.size() == 1); - DEBUG_ASSERT(key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); + DEBUG_ASSERT( + key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); const std::size_t hash_code = key.getHash(); - std::size_t bucket_ref = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + std::size_t bucket_ref = + slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); while (bucket_ref != 0) { DEBUG_ASSERT(bucket_ref != std::numeric_limits<std::size_t>::max()); - const char *bucket = static_cast<const char*>(buckets_) + (bucket_ref - 1) * bucket_size_; - const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + const char *bucket = + static_cast<const char *>(buckets_) + (bucket_ref - 1) * bucket_size_; + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t *>( bucket + sizeof(std::atomic<std::size_t>)); - if ((bucket_hash == hash_code) && key_manager_.scalarKeyCollisionCheck(key, bucket)) { + if ((bucket_hash == hash_code) && + key_manager_.scalarKeyCollisionCheck(key, bucket)) { // Match located. - return reinterpret_cast<const uint8_t*>(bucket + kValueOffset); + return reinterpret_cast<const std::uint8_t *>(bucket + kValueOffset); } - bucket_ref = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + bucket_ref = + reinterpret_cast<const std::atomic<std::size_t> *>(bucket)->load( + std::memory_order_relaxed); } // Reached the end of the chain and didn't find a match. @@ -598,23 +644,31 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -const uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::getSingleCompositeKey(const std::vector<TypedValue> &key) const { +const std::uint8_t* FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + getSingleCompositeKey(const std::vector<TypedValue> &key) const { DEBUG_ASSERT(!allow_duplicate_keys); DEBUG_ASSERT(this->key_types_.size() == key.size()); const std::size_t hash_code = this->hashCompositeKey(key); - std::size_t bucket_ref = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + std::size_t bucket_ref = + slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); while (bucket_ref != 0) { DEBUG_ASSERT(bucket_ref != std::numeric_limits<std::size_t>::max()); - const char *bucket = static_cast<const char*>(buckets_) + (bucket_ref - 1) * bucket_size_; - const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + const char *bucket = + static_cast<const char *>(buckets_) + (bucket_ref - 1) * bucket_size_; + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t *>( bucket + sizeof(std::atomic<std::size_t>)); - if ((bucket_hash == hash_code) && key_manager_.compositeKeyCollisionCheck(key, bucket)) { + if ((bucket_hash == hash_code) && + key_manager_.compositeKeyCollisionCheck(key, bucket)) { // Match located. - return reinterpret_cast<const uint8_t*>(bucket + kValueOffset); + return reinterpret_cast<const std::uint8_t *>(bucket + kValueOffset); } - bucket_ref = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + bucket_ref = + reinterpret_cast<const std::atomic<std::size_t> *>(bucket)->load( + std::memory_order_relaxed); } // Reached the end of the chain and didn't find a match. @@ -625,23 +679,32 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -const uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::getSingleCompositeKey(const std::vector<TypedValue> &key, int index) const { +const std::uint8_t* FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + getSingleCompositeKey(const std::vector<TypedValue> &key, int index) const { DEBUG_ASSERT(!allow_duplicate_keys); DEBUG_ASSERT(this->key_types_.size() == key.size()); const std::size_t hash_code = this->hashCompositeKey(key); - std::size_t bucket_ref = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + std::size_t bucket_ref = + slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); while (bucket_ref != 0) { DEBUG_ASSERT(bucket_ref != std::numeric_limits<std::size_t>::max()); - const char *bucket = static_cast<const char*>(buckets_) + (bucket_ref - 1) * bucket_size_; - const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + const char *bucket = + static_cast<const char *>(buckets_) + (bucket_ref - 1) * bucket_size_; + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t *>( bucket + sizeof(std::atomic<std::size_t>)); - if ((bucket_hash == hash_code) && key_manager_.compositeKeyCollisionCheck(key, bucket)) { + if ((bucket_hash == hash_code) && + key_manager_.compositeKeyCollisionCheck(key, bucket)) { // Match located. - return reinterpret_cast<const uint8_t*>(bucket + kValueOffset)+this->payload_offsets_[index]; + return reinterpret_cast<const std::uint8_t *>(bucket + kValueOffset) + + this->payload_offsets_[index]; } - bucket_ref = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + bucket_ref = + reinterpret_cast<const std::atomic<std::size_t> *>(bucket)->load( + std::memory_order_relaxed); } // Reached the end of the chain and didn't find a match. @@ -652,26 +715,38 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::getAll(const TypedValue &key, std::vector<const uint8_t*> *values) const { +void FastSeparateChainingHashTable< + resizable, + serializable, + force_key_copy, + allow_duplicate_keys>::getAll(const TypedValue &key, + std::vector<const std::uint8_t *> *values) + const { DEBUG_ASSERT(this->key_types_.size() == 1); - DEBUG_ASSERT(key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); + DEBUG_ASSERT( + key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); const std::size_t hash_code = key.getHash(); - std::size_t bucket_ref = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + std::size_t bucket_ref = + slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); while (bucket_ref != 0) { DEBUG_ASSERT(bucket_ref != std::numeric_limits<std::size_t>::max()); - const char *bucket = static_cast<const char*>(buckets_) + (bucket_ref - 1) * bucket_size_; - const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + const char *bucket = + static_cast<const char *>(buckets_) + (bucket_ref - 1) * bucket_size_; + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t *>( bucket + sizeof(std::atomic<std::size_t>)); - if ((bucket_hash == hash_code) && key_manager_.scalarKeyCollisionCheck(key, bucket)) { + if ((bucket_hash == hash_code) && + key_manager_.scalarKeyCollisionCheck(key, bucket)) { // Match located. - values->push_back(reinterpret_cast<const uint8_t*>(bucket + kValueOffset)); + values->push_back( + reinterpret_cast<const std::uint8_t *>(bucket + kValueOffset)); if (!allow_duplicate_keys) { return; } } - bucket_ref = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + bucket_ref = + reinterpret_cast<const std::atomic<std::size_t> *>(bucket)->load( + std::memory_order_relaxed); } } @@ -679,25 +754,35 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::getAllCompositeKey(const std::vector<TypedValue> &key, std::vector<const uint8_t*> *values) const { +void FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + getAllCompositeKey(const std::vector<TypedValue> &key, + std::vector<const std::uint8_t *> *values) const { DEBUG_ASSERT(this->key_types_.size() == key.size()); const std::size_t hash_code = this->hashCompositeKey(key); - std::size_t bucket_ref = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + std::size_t bucket_ref = + slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); while (bucket_ref != 0) { DEBUG_ASSERT(bucket_ref != std::numeric_limits<std::size_t>::max()); - const char *bucket = static_cast<const char*>(buckets_) + (bucket_ref - 1) * bucket_size_; - const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + const char *bucket = + static_cast<const char *>(buckets_) + (bucket_ref - 1) * bucket_size_; + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t *>( bucket + sizeof(std::atomic<std::size_t>)); - if ((bucket_hash == hash_code) && key_manager_.compositeKeyCollisionCheck(key, bucket)) { + if ((bucket_hash == hash_code) && + key_manager_.compositeKeyCollisionCheck(key, bucket)) { // Match located. - values->push_back(reinterpret_cast<const uint8_t*>(bucket + kValueOffset)); + values->push_back( + reinterpret_cast<const std::uint8_t *>(bucket + kValueOffset)); if (!allow_duplicate_keys) { return; } } - bucket_ref = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + bucket_ref = + reinterpret_cast<const std::atomic<std::size_t> *>(bucket)->load( + std::memory_order_relaxed); } } @@ -705,18 +790,22 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -HashTablePutResult - FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::putInternal(const TypedValue &key, - const std::size_t variable_key_size, - const uint8_t &value, - HashTablePreallocationState *prealloc_state) { +HashTablePutResult FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + putInternal(const TypedValue &key, + const std::size_t variable_key_size, + const std::uint8_t &value, + HashTablePreallocationState *prealloc_state) { DEBUG_ASSERT(this->key_types_.size() == 1); - DEBUG_ASSERT(key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); + DEBUG_ASSERT( + key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); if (prealloc_state == nullptr) { // Early check for a free bucket. - if (header_->buckets_allocated.load(std::memory_order_relaxed) >= header_->num_buckets) { + if (header_->buckets_allocated.load(std::memory_order_relaxed) >= + header_->num_buckets) { return HashTablePutResult::kOutOfSpace; } @@ -763,10 +852,11 @@ HashTablePutResult writeScalarKeyToBucket(key, hash_code, bucket, prealloc_state); // Store the value by using placement new with ValueT's copy constructor. - new(static_cast<char*>(bucket) + kValueOffset) uint8_t(value); + new (static_cast<char *>(bucket) + kValueOffset) std::uint8_t(value); // Update the previous chain pointer to point to the new bucket. - pending_chain_ptr->store(pending_chain_ptr_finish_value, std::memory_order_release); + pending_chain_ptr->store(pending_chain_ptr_finish_value, + std::memory_order_release); // We're all done. return HashTablePutResult::kOK; @@ -776,17 +866,20 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -HashTablePutResult - FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::putCompositeKeyInternalFast(const std::vector<TypedValue> &key, - const std::size_t variable_key_size, - const uint8_t *init_value_ptr, - HashTablePreallocationState *prealloc_state) { +HashTablePutResult FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + putCompositeKeyInternalFast(const std::vector<TypedValue> &key, + const std::size_t variable_key_size, + const std::uint8_t *init_value_ptr, + HashTablePreallocationState *prealloc_state) { DEBUG_ASSERT(this->key_types_.size() == key.size()); if (prealloc_state == nullptr) { // Early check for a free bucket. - if (header_->buckets_allocated.load(std::memory_order_relaxed) >= header_->num_buckets) { + if (header_->buckets_allocated.load(std::memory_order_relaxed) >= + header_->num_buckets) { return HashTablePutResult::kOutOfSpace; } @@ -832,12 +925,11 @@ HashTablePutResult // Write the key and hash. writeCompositeKeyToBucket(key, hash_code, bucket, prealloc_state); - // Store the value by using placement new with ValueT's copy constructor. -// new(static_cast<char*>(bucket) + kValueOffset) uint8_t(value); - uint8_t *value = static_cast<uint8_t*>(bucket) + kValueOffset; - memcpy(value, init_value_ptr, this->total_payload_size_); + std::uint8_t *value = static_cast<std::uint8_t *>(bucket) + kValueOffset; + memcpy(value, init_value_ptr, this->total_payload_size_); // Update the previous chain pointer to point to the new bucket. - pending_chain_ptr->store(pending_chain_ptr_finish_value, std::memory_order_release); + pending_chain_ptr->store(pending_chain_ptr_finish_value, + std::memory_order_release); // We're all done. return HashTablePutResult::kOK; @@ -847,13 +939,17 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::upsertInternalFast(const TypedValue &key, - const std::size_t variable_key_size, - const std::uint8_t *init_value_ptr) { +std::uint8_t* FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + upsertInternalFast(const TypedValue &key, + const std::size_t variable_key_size, + const std::uint8_t *init_value_ptr) { DEBUG_ASSERT(!allow_duplicate_keys); DEBUG_ASSERT(this->key_types_.size() == 1); - DEBUG_ASSERT(key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); + DEBUG_ASSERT( + key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); if (variable_key_size > 0) { // Don't allocate yet, since the key may already be present. However, we @@ -861,9 +957,11 @@ uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, // space is big enough to hold the key (at least one must be true: either // the key is already present and allocated, or we need to be able to // allocate enough space for it). - std::size_t allocated_bytes = header_->variable_length_bytes_allocated.load(std::memory_order_relaxed); - if ((allocated_bytes < variable_key_size) - && (allocated_bytes + variable_key_size > key_manager_.getVariableLengthKeyStorageSize())) { + std::size_t allocated_bytes = header_->variable_length_bytes_allocated.load( + std::memory_order_relaxed); + if ((allocated_bytes < variable_key_size) && + (allocated_bytes + variable_key_size > + key_manager_.getVariableLengthKeyStorageSize())) { return nullptr; } } @@ -886,7 +984,8 @@ uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, return nullptr; } else if (key_manager_.scalarKeyCollisionCheck(key, bucket)) { // Found an already-existing entry for this key. - return reinterpret_cast<uint8_t*>(static_cast<char*>(bucket) + kValueOffset); + return reinterpret_cast<std::uint8_t *>(static_cast<char *>(bucket) + + kValueOffset); } } @@ -895,16 +994,15 @@ uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, writeScalarKeyToBucket(key, hash_code, bucket, nullptr); // Copy the supplied 'initial_value' into place. -// uint8_t *value = new(static_cast<char*>(bucket) + kValueOffset) uint8_t(initial_value); - - uint8_t *value = static_cast<unsigned char*>(bucket) + kValueOffset; - if (init_value_ptr == nullptr) - memcpy(value, init_payload_, this->total_payload_size_); - else - memcpy(value, init_value_ptr, this->total_payload_size_); + std::uint8_t *value = static_cast<unsigned char *>(bucket) + kValueOffset; + if (init_value_ptr == nullptr) + memcpy(value, init_payload_, this->total_payload_size_); + else + memcpy(value, init_value_ptr, this->total_payload_size_); // Update the previous chain pointer to point to the new bucket. - pending_chain_ptr->store(pending_chain_ptr_finish_value, std::memory_order_release); + pending_chain_ptr->store(pending_chain_ptr_finish_value, + std::memory_order_release); // Return the value. return value; @@ -914,10 +1012,13 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::upsertCompositeKeyInternalFast(const std::vector<TypedValue> &key, - const std::uint8_t *init_value_ptr, - const std::size_t variable_key_size) { +std::uint8_t* FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + upsertCompositeKeyInternalFast(const std::vector<TypedValue> &key, + const std::uint8_t *init_value_ptr, + const std::size_t variable_key_size) { DEBUG_ASSERT(!allow_duplicate_keys); DEBUG_ASSERT(this->key_types_.size() == key.size()); @@ -927,9 +1028,11 @@ uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, // space is big enough to hold the key (at least one must be true: either // the key is already present and allocated, or we need to be able to // allocate enough space for it). - std::size_t allocated_bytes = header_->variable_length_bytes_allocated.load(std::memory_order_relaxed); - if ((allocated_bytes < variable_key_size) - && (allocated_bytes + variable_key_size > key_manager_.getVariableLengthKeyStorageSize())) { + std::size_t allocated_bytes = header_->variable_length_bytes_allocated.load( + std::memory_order_relaxed); + if ((allocated_bytes < variable_key_size) && + (allocated_bytes + variable_key_size > + key_manager_.getVariableLengthKeyStorageSize())) { return nullptr; } } @@ -952,7 +1055,8 @@ uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, return nullptr; } else if (key_manager_.compositeKeyCollisionCheck(key, bucket)) { // Found an already-existing entry for this key. - return reinterpret_cast<uint8_t*>(static_cast<char*>(bucket) + kValueOffset); + return reinterpret_cast<std::uint8_t *>(static_cast<char *>(bucket) + + kValueOffset); } } @@ -960,17 +1064,16 @@ uint8_t* FastSeparateChainingHashTable<resizable, serializable, force_key_copy, // Write the key and hash. writeCompositeKeyToBucket(key, hash_code, bucket, nullptr); -// uint8_t *value; -// value = static_cast<unsigned char*>(bucket) + kValueOffset; - uint8_t *value = static_cast<unsigned char*>(bucket) + kValueOffset; - if (init_value_ptr == nullptr) { - memcpy(value, init_payload_, this->total_payload_size_); - } else { - memcpy(value, init_value_ptr, this->total_payload_size_); - } + std::uint8_t *value = static_cast<unsigned char *>(bucket) + kValueOffset; + if (init_value_ptr == nullptr) { + memcpy(value, init_payload_, this->total_payload_size_); + } else { + memcpy(value, init_value_ptr, this->total_payload_size_); + } // Update the previous chaing pointer to point to the new bucket. - pending_chain_ptr->store(pending_chain_ptr_finish_value, std::memory_order_release); + pending_chain_ptr->store(pending_chain_ptr_finish_value, + std::memory_order_release); // Return the value. return value; @@ -980,13 +1083,19 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -bool FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::getNextEntry(TypedValue *key, const uint8_t **value, std::size_t *entry_num) const { +bool FastSeparateChainingHashTable< + resizable, + serializable, + force_key_copy, + allow_duplicate_keys>::getNextEntry(TypedValue *key, + const std::uint8_t **value, + std::size_t *entry_num) const { DEBUG_ASSERT(this->key_types_.size() == 1); if (*entry_num < header_->buckets_allocated.load(std::memory_order_relaxed)) { - const char *bucket = static_cast<const char*>(buckets_) + (*entry_num) * bucket_size_; + const char *bucket = + static_cast<const char *>(buckets_) + (*entry_num) * bucket_size_; *key = key_manager_.getKeyComponentTyped(bucket, 0); - *value = reinterpret_cast<const uint8_t*>(bucket + kValueOffset); + *value = reinterpret_cast<const std::uint8_t *>(bucket + kValueOffset); ++(*entry_num); return true; } else { @@ -998,18 +1107,22 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -bool FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::getNextEntryCompositeKey(std::vector<TypedValue> *key, - const uint8_t **value, - std::size_t *entry_num) const { +bool FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + getNextEntryCompositeKey(std::vector<TypedValue> *key, + const std::uint8_t **value, + std::size_t *entry_num) const { if (*entry_num < header_->buckets_allocated.load(std::memory_order_relaxed)) { - const char *bucket = static_cast<const char*>(buckets_) + (*entry_num) * bucket_size_; - for (std::vector<const Type*>::size_type key_idx = 0; + const char *bucket = + static_cast<const char *>(buckets_) + (*entry_num) * bucket_size_; + for (std::vector<const Type *>::size_type key_idx = 0; key_idx < this->key_types_.size(); ++key_idx) { key->emplace_back(key_manager_.getKeyComponentTyped(bucket, key_idx)); } - *value = reinterpret_cast<const uint8_t*>(bucket + kValueOffset); + *value = reinterpret_cast<const std::uint8_t *>(bucket + kValueOffset); ++(*entry_num); return true; } else { @@ -1021,29 +1134,38 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -bool FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::getNextEntryForKey(const TypedValue &key, - const std::size_t hash_code, - const uint8_t **value, - std::size_t *entry_num) const { +bool FastSeparateChainingHashTable< + resizable, + serializable, + force_key_copy, + allow_duplicate_keys>::getNextEntryForKey(const TypedValue &key, + const std::size_t hash_code, + const std::uint8_t **value, + std::size_t *entry_num) const { DEBUG_ASSERT(this->key_types_.size() == 1); - DEBUG_ASSERT(key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); + DEBUG_ASSERT( + key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); if (*entry_num == 0) { - *entry_num = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + *entry_num = + slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); } else if (*entry_num == std::numeric_limits<std::size_t>::max()) { return false; } while (*entry_num != 0) { DEBUG_ASSERT(*entry_num != std::numeric_limits<std::size_t>::max()); - const char *bucket = static_cast<const char*>(buckets_) + (*entry_num - 1) * bucket_size_; - *entry_num = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); - const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + const char *bucket = + static_cast<const char *>(buckets_) + (*entry_num - 1) * bucket_size_; + *entry_num = + reinterpret_cast<const std::atomic<std::size_t> *>(bucket)->load( + std::memory_order_relaxed); + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t *>( bucket + sizeof(std::atomic<std::size_t>)); - if ((bucket_hash == hash_code) && key_manager_.scalarKeyCollisionCheck(key, bucket)) { + if ((bucket_hash == hash_code) && + key_manager_.scalarKeyCollisionCheck(key, bucket)) { // Match located. - *value = reinterpret_cast<const uint8_t*>(bucket + kValueOffset); + *value = reinterpret_cast<const std::uint8_t *>(bucket + kValueOffset); if (*entry_num == 0) { // If this is the last bucket in the chain, prevent the next call from // starting over again. @@ -1061,28 +1183,36 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -bool FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::getNextEntryForCompositeKey(const std::vector<TypedValue> &key, - const std::size_t hash_code, - const uint8_t **value, - std::size_t *entry_num) const { +bool FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + getNextEntryForCompositeKey(const std::vector<TypedValue> &key, + const std::size_t hash_code, + const std::uint8_t **value, + std::size_t *entry_num) const { DEBUG_ASSERT(this->key_types_.size() == key.size()); if (*entry_num == 0) { - *entry_num = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + *entry_num = + slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); } else if (*entry_num == std::numeric_limits<std::size_t>::max()) { return false; } while (*entry_num != 0) { DEBUG_ASSERT(*entry_num != std::numeric_limits<std::size_t>::max()); - const char *bucket = static_cast<const char*>(buckets_) + (*entry_num - 1) * bucket_size_; - *entry_num = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); - const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + const char *bucket = + static_cast<const char *>(buckets_) + (*entry_num - 1) * bucket_size_; + *entry_num = + reinterpret_cast<const std::atomic<std::size_t> *>(bucket)->load( + std::memory_order_relaxed); + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t *>( bucket + sizeof(std::atomic<std::size_t>)); - if ((bucket_hash == hash_code) && key_manager_.compositeKeyCollisionCheck(key, bucket)) { + if ((bucket_hash == hash_code) && + key_manager_.compositeKeyCollisionCheck(key, bucket)) { // Match located. - *value = reinterpret_cast<const uint8_t*>(bucket + kValueOffset); + *value = reinterpret_cast<const std::uint8_t *>(bucket + kValueOffset); if (*entry_num == 0) { // If this is the last bucket in the chain, prevent the next call from // starting over again. @@ -1100,23 +1230,32 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -bool FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::hasKey(const TypedValue &key) const { +bool FastSeparateChainingHashTable< + resizable, + serializable, + force_key_copy, + allow_duplicate_keys>::hasKey(const TypedValue &key) const { DEBUG_ASSERT(this->key_types_.size() == 1); - DEBUG_ASSERT(key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); + DEBUG_ASSERT( + key.isPlausibleInstanceOf(this->key_types_.front()->getSignature())); const std::size_t hash_code = key.getHash(); - std::size_t bucket_ref = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + std::size_t bucket_ref = + slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); while (bucket_ref != 0) { DEBUG_ASSERT(bucket_ref != std::numeric_limits<std::size_t>::max()); - const char *bucket = static_cast<const char*>(buckets_) + (bucket_ref - 1) * bucket_size_; - const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + const char *bucket = + static_cast<const char *>(buckets_) + (bucket_ref - 1) * bucket_size_; + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t *>( bucket + sizeof(std::atomic<std::size_t>)); - if ((bucket_hash == hash_code) && key_manager_.scalarKeyCollisionCheck(key, bucket)) { + if ((bucket_hash == hash_code) && + key_manager_.scalarKeyCollisionCheck(key, bucket)) { // Find a match. return true; } - bucket_ref = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + bucket_ref = + reinterpret_cast<const std::atomic<std::size_t> *>(bucket)->load( + std::memory_order_relaxed); } return false; } @@ -1125,22 +1264,31 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -bool FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::hasCompositeKey(const std::vector<TypedValue> &key) const { +bool FastSeparateChainingHashTable< + resizable, + serializable, + force_key_copy, + allow_duplicate_keys>::hasCompositeKey(const std::vector<TypedValue> &key) + const { DEBUG_ASSERT(this->key_types_.size() == key.size()); const std::size_t hash_code = this->hashCompositeKey(key); - std::size_t bucket_ref = slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); + std::size_t bucket_ref = + slots_[hash_code % header_->num_slots].load(std::memory_order_relaxed); while (bucket_ref != 0) { DEBUG_ASSERT(bucket_ref != std::numeric_limits<std::size_t>::max()); - const char *bucket = static_cast<const char*>(buckets_) + (bucket_ref - 1) * bucket_size_; - const std::size_t bucket_hash = *reinterpret_cast<const std::size_t*>( + const char *bucket = + static_cast<const char *>(buckets_) + (bucket_ref - 1) * bucket_size_; + const std::size_t bucket_hash = *reinterpret_cast<const std::size_t *>( bucket + sizeof(std::atomic<std::size_t>)); - if ((bucket_hash == hash_code) && key_manager_.compositeKeyCollisionCheck(key, bucket)) { + if ((bucket_hash == hash_code) && + key_manager_.compositeKeyCollisionCheck(key, bucket)) { // Find a match. return true; } - bucket_ref = reinterpret_cast<const std::atomic<std::size_t>*>(bucket)->load(std::memory_order_relaxed); + bucket_ref = + reinterpret_cast<const std::atomic<std::size_t> *>(bucket)->load( + std::memory_order_relaxed); } return false; } @@ -1149,10 +1297,13 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::resize(const std::size_t extra_buckets, - const std::size_t extra_variable_storage, - const std::size_t retry_num) { +void FastSeparateChainingHashTable< + resizable, + serializable, + force_key_copy, + allow_duplicate_keys>::resize(const std::size_t extra_buckets, + const std::size_t extra_variable_storage, + const std::size_t retry_num) { DEBUG_ASSERT(resizable); // A retry should never be necessary with this implementation of HashTable. @@ -1178,33 +1329,36 @@ void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allo // account kHashTableLoadFactor. std::size_t resized_num_slots = get_next_prime_number( (header_->num_buckets + extra_buckets / 2) * kHashTableLoadFactor * 2); - std::size_t variable_storage_required - = (resized_num_slots / kHashTableLoadFactor) * key_manager_.getEstimatedVariableKeySize(); - const std::size_t original_variable_storage_used - = header_->variable_length_bytes_allocated.load(std::memory_order_relaxed); + std::size_t variable_storage_required = + (resized_num_slots / kHashTableLoadFactor) * + key_manager_.getEstimatedVariableKeySize(); + const std::size_t original_variable_storage_used = + header_->variable_length_bytes_allocated.load(std::memory_order_relaxed); // If this resize was triggered by a too-large variable-length key, bump up // the variable-length storage requirement. - if ((extra_variable_storage > 0) - && (extra_variable_storage + original_variable_storage_used - > key_manager_.getVariableLengthKeyStorageSize())) { + if ((extra_variable_storage > 0) && + (extra_variable_storage + original_variable_storage_used > + key_manager_.getVariableLengthKeyStorageSize())) { variable_storage_required += extra_variable_storage; } - const std::size_t resized_memory_required - = sizeof(Header) - + resized_num_slots * sizeof(std::atomic<std::size_t>) - + (resized_num_slots / kHashTableLoadFactor) * bucket_size_ - + variable_storage_required; - const std::size_t resized_storage_slots - = this->storage_manager_->SlotsNeededForBytes(resized_memory_required); + const std::size_t resized_memory_required = + sizeof(Header) + resized_num_slots * sizeof(std::atomic<std::size_t>) + + (resized_num_slots / kHashTableLoadFactor) * bucket_size_ + + variable_storage_required; + const std::size_t resized_storage_slots = + this->storage_manager_->SlotsNeededForBytes(resized_memory_required); if (resized_storage_slots == 0) { - FATAL_ERROR("Storage requirement for resized SeparateChainingHashTable " - "exceeds maximum allocation size."); + FATAL_ERROR( + "Storage requirement for resized SeparateChainingHashTable " + "exceeds maximum allocation size."); } // Get a new StorageBlob to hold the resized hash table. - const block_id resized_blob_id = this->storage_manager_->createBlob(resized_storage_slots); - MutableBlobReference resized_blob = this->storage_manager_->getBlobMutable(resized_blob_id); + const block_id resized_blob_id = + this->storage_manager_->createBlob(resized_storage_slots); + MutableBlobReference resized_blob = + this->storage_manager_->getBlobMutable(resized_blob_id); // Locate data structures inside the new StorageBlob. void *aligned_memory_start = resized_blob->getMemoryMutable(); @@ -1212,12 +1366,12 @@ void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allo if (align(alignof(Header), sizeof(Header), aligned_memory_start, - available_memory) - == nullptr) { + available_memory) == nullptr) { // Should be impossible, as noted in constructor. - FATAL_ERROR("StorageBlob used to hold resized SeparateChainingHashTable " - "is too small to meet alignment requirements of " - "LinearOpenAddressingHashTable::Header."); + FATAL_ERROR( + "StorageBlob used to hold resized SeparateChainingHashTable " + "is too small to meet alignment requirements of " + "LinearOpenAddressingHashTable::Header."); } else if (aligned_memory_start != resized_blob->getMemoryMutable()) { // Again, should be impossible. DEV_WARNING("In SeparateChainingHashTable::resize(), StorageBlob " @@ -1227,59 +1381,63 @@ void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allo << "LinearOpenAddressingHashTable::Header."); } - Header *resized_header = static_cast<Header*>(aligned_memory_start); - aligned_memory_start = static_cast<char*>(aligned_memory_start) + sizeof(Header); + Header *resized_header = static_cast<Header *>(aligned_memory_start); + aligned_memory_start = + static_cast<char *>(aligned_memory_start) + sizeof(Header); available_memory -= sizeof(Header); // As in constructor, recompute the number of slots and buckets using the // actual available memory. - std::size_t resized_num_buckets - = (available_memory - extra_variable_storage) - / (kHashTableLoadFactor * sizeof(std::atomic<std::size_t>) - + bucket_size_ - + key_manager_.getEstimatedVariableKeySize()); - resized_num_slots = get_previous_prime_number(resized_num_buckets * kHashTableLoadFactor); + std::size_t resized_num_buckets = + (available_memory - extra_variable_storage) / + (kHashTableLoadFactor * sizeof(std::atomic<std::size_t>) + bucket_size_ + + key_manager_.getEstimatedVariableKeySize()); + resized_num_slots = + get_previous_prime_number(resized_num_buckets * kHashTableLoadFactor); resized_num_buckets = resized_num_slots / kHashTableLoadFactor; // Locate slot array. - std::atomic<std::size_t> *resized_slots = static_cast<std::atomic<std::size_t>*>(aligned_memory_start); - aligned_memory_start = static_cast<char*>(aligned_memory_start) - + sizeof(std::atomic<std::size_t>) * resized_num_slots; + std::atomic<std::size_t> *resized_slots = + static_cast<std::atomic<std::size_t> *>(aligned_memory_start); + aligned_memory_start = static_cast<char *>(aligned_memory_start) + + sizeof(std::atomic<std::size_t>) * resized_num_slots; available_memory -= sizeof(std::atomic<std::size_t>) * resized_num_slots; // As in constructor, we will be extra paranoid and use align() to locate the // start of the array of buckets, as well. void *resized_buckets = aligned_memory_start; - if (align(kBucketAlignment, - bucket_size_, - resized_buckets, - available_memory) - == nullptr) { - FATAL_ERROR("StorageBlob used to hold resized SeparateChainingHashTable " - "is too small to meet alignment requirements of buckets."); + if (align( + kBucketAlignment, bucket_size_, resized_buckets, available_memory) == + nullptr) { + FATAL_ERROR( + "StorageBlob used to hold resized SeparateChainingHashTable " + "is too small to meet alignment requirements of buckets."); } else if (resized_buckets != aligned_memory_start) { - DEV_WARNING("Bucket array start position adjusted to meet alignment " - "requirement for SeparateChainingHashTable's value type."); - if (resized_num_buckets * bucket_size_ + variable_storage_required > available_memory) { + DEV_WARNING( + "Bucket array start position adjusted to meet alignment " + "requirement for SeparateChainingHashTable's value type."); + if (resized_num_buckets * bucket_size_ + variable_storage_required > + available_memory) { --resized_num_buckets; } } - aligned_memory_start = static_cast<char*>(aligned_memory_start) - + resized_num_buckets * bucket_size_; + aligned_memory_start = static_cast<char *>(aligned_memory_start) + + resized_num_buckets * bucket_size_; available_memory -= resized_num_buckets * bucket_size_; void *resized_variable_length_key_storage = aligned_memory_start; const std::size_t resized_variable_length_key_storage_size = available_memory; - const std::size_t original_buckets_used = header_->buckets_allocated.load(std::memory_order_relaxed); + const std::size_t original_buckets_used = + header_->buckets_allocated.load(std::memory_order_relaxed); // Initialize the header. resized_header->num_slots = resized_num_slots; resized_header->num_buckets = resized_num_buckets; - resized_header->buckets_allocated.store(original_buckets_used, std::memory_order_relaxed); + resized_header->buckets_allocated.store(original_buckets_used, + std::memory_order_relaxed); resized_header->variable_length_bytes_allocated.store( - original_variable_storage_used, - std::memory_order_relaxed); + original_variable_storage_used, std::memory_order_relaxed); // Bulk-copy buckets. This is safe because: // 1. The "next" pointers will be adjusted when rebuilding chains below. @@ -1298,30 +1456,34 @@ void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allo // GCC 4.8.3, so we assume we need to invoke ValueT's copy or move // constructor, even though the plain memcpy above could suffice for many // possible ValueTs. - void *current_value_original = static_cast<char*>(buckets_) + kValueOffset; - void *current_value_resized = static_cast<char*>(resized_buckets) + kValueOffset; - for (std::size_t bucket_num = 0; bucket_num < original_buckets_used; ++bucket_num) { + void *current_value_original = static_cast<char *>(buckets_) + kValueOffset; + void *current_value_resized = + static_cast<char *>(resized_buckets) + kValueOffset; + for (std::size_t bucket_num = 0; bucket_num < original_buckets_used; + ++bucket_num) { // Use a move constructor if available to avoid a deep-copy, since resizes // always succeed. - new (current_value_resized) uint8_t(std::move(*static_cast<uint8_t*>(current_value_original))); - current_value_original = static_cast<char*>(current_value_original) + bucket_size_; - current_value_resized = static_cast<char*>(current_value_resized) + bucket_size_; + new (current_value_resized) std::uint8_t( + std::move(*static_cast<std::uint8_t *>(current_value_original))); + current_value_original = + static_cast<char *>(current_value_original) + bucket_size_; + current_value_resized = + static_cast<char *>(current_value_resized) + bucket_size_; } // Copy over variable-length key components, if any. if (original_variable_storage_used > 0) { - DEBUG_ASSERT(original_variable_storage_used - == key_manager_.getNextVariableLengthKeyOffset()); - DEBUG_ASSERT(original_variable_storage_used <= resized_variable_length_key_storage_size); + DEBUG_ASSERT(original_variable_storage_used == + key_manager_.getNextVariableLengthKeyOffset()); + DEBUG_ASSERT(original_variable_storage_used <= + resized_variable_length_key_storage_size); std::memcpy(resized_variable_length_key_storage, key_manager_.getVariableLengthKeyStorage(), original_variable_storage_used); } // Destroy values in the original hash table, if neccesary, - DestroyValues(buckets_, - original_buckets_used, - bucket_size_); + DestroyValues(buckets_, original_buckets_used, bucket_size_); // Make resized structures active. std::swap(this->blob_, resized_blob); @@ -1340,17 +1502,18 @@ void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allo // Rebuild chains. void *current_bucket = buckets_; - for (std::size_t bucket_num = 0; bucket_num < original_buckets_used; ++bucket_num) { - std::atomic<std::size_t> *next_ptr - = static_cast<std::atomic<std::size_t>*>(current_bucket); - const std::size_t hash_code = *reinterpret_cast<const std::size_t*>( - static_cast<const char*>(current_bucket) + sizeof(std::atomic<std::size_t>)); + for (std::size_t bucket_num = 0; bucket_num < original_buckets_used; + ++bucket_num) { + std::atomic<std::size_t> *next_ptr = + static_cast<std::atomic<std::size_t> *>(current_bucket); + const std::size_t hash_code = *reinterpret_cast<const std::size_t *>( + static_cast<const char *>(current_bucket) + + sizeof(std::atomic<std::size_t>)); const std::size_t slot_number = hash_code % header_->num_slots; std::size_t slot_ptr_value = 0; - if (slots_[slot_number].compare_exchange_strong(slot_ptr_value, - bucket_num + 1, - std::memory_order_relaxed)) { + if (slots_[slot_number].compare_exchange_strong( + slot_ptr_value, bucket_num + 1, std::memory_order_relaxed)) { // This bucket is the first in the chain for this block, so reset its // next pointer to 0. next_ptr->store(0, std::memory_order_relaxed); @@ -1360,7 +1523,7 @@ void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allo next_ptr->store(slot_ptr_value, std::memory_order_relaxed); slots_[slot_number].store(bucket_num + 1, std::memory_order_relaxed); } - current_bucket = static_cast<char*>(current_bucket) + bucket_size_; + current_bucket = static_cast<char *>(current_bucket) + bucket_size_; } } @@ -1368,10 +1531,13 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -bool FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::preallocateForBulkInsert(const std::size_t total_entries, - const std::size_t total_variable_key_size, - HashTablePreallocationState *prealloc_state) { +bool FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + preallocateForBulkInsert(const std::size_t total_entries, + const std::size_t total_variable_key_size, + HashTablePreallocationState *prealloc_state) { DEBUG_ASSERT(allow_duplicate_keys); if (!key_manager_.allocateVariableLengthKeyStorage(total_variable_key_size)) { return false; @@ -1382,12 +1548,15 @@ bool FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allo // than one bucket and exceed 'header_->num_buckets', their respective // rollbacks might happen in such an order that some bucket ranges get // skipped, while others might get double-allocated later. - std::size_t original_buckets_allocated = header_->buckets_allocated.load(std::memory_order_relaxed); - std::size_t buckets_post_allocation = original_buckets_allocated + total_entries; - while ((buckets_post_allocation <= header_->num_buckets) - && !header_->buckets_allocated.compare_exchange_weak(original_buckets_allocated, - buckets_post_allocation, - std::memory_order_relaxed)) { + std::size_t original_buckets_allocated = + header_->buckets_allocated.load(std::memory_order_relaxed); + std::size_t buckets_post_allocation = + original_buckets_allocated + total_entries; + while ((buckets_post_allocation <= header_->num_buckets) && + !header_->buckets_allocated.compare_exchange_weak( + original_buckets_allocated, + buckets_post_allocation, + std::memory_order_relaxed)) { buckets_post_allocation = original_buckets_allocated + total_entries; } @@ -1398,8 +1567,9 @@ bool FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allo prealloc_state->bucket_position = original_buckets_allocated; if (total_variable_key_size != 0) { - prealloc_state->variable_length_key_position - = key_manager_.incrementNextVariableLengthKeyOffset(total_variable_key_size); + prealloc_state->variable_length_key_position = + key_manager_.incrementNextVariableLengthKeyOffset( + total_variable_key_size); } return true; } @@ -1408,17 +1578,18 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -void FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::DestroyValues(void *hash_buckets, - const std::size_t num_buckets, - const std::size_t bucket_size) { - if (!std::is_trivially_destructible<uint8_t>::value) { - void *value_ptr = static_cast<char*>(hash_buckets) + kValueOffset; - for (std::size_t bucket_num = 0; - bucket_num < num_buckets; - ++bucket_num) { - static_cast<uint8_t*>(value_ptr)->~uint8_t(); - value_ptr = static_cast<char*>(value_ptr) + bucket_size; +void FastSeparateChainingHashTable< + resizable, + serializable, + force_key_copy, + allow_duplicate_keys>::DestroyValues(void *hash_buckets, + const std::size_t num_buckets, + const std::size_t bucket_size) { + if (!std::is_trivially_destructible<std::uint8_t>::value) { + void *value_ptr = static_cast<char *>(hash_buckets) + kValueOffset; + for (std::size_t bucket_num = 0; bucket_num < num_buckets; ++bucket_num) { + static_cast<std::uint8_t *>(value_ptr)->~uint8_t(); + value_ptr = static_cast<char *>(value_ptr) + bucket_size; } } } @@ -1427,39 +1598,45 @@ template <bool resizable, bool serializable, bool force_key_copy, bool allow_duplicate_keys> -inline bool FastSeparateChainingHashTable<resizable, serializable, force_key_copy, allow_duplicate_keys> - ::locateBucketForInsertion(const std::size_t hash_code, - const std::size_t variable_key_allocation_required, - void **bucket, - std::atomic<std::size_t> **pending_chain_ptr, - std::size_t *pending_chain_ptr_finish_value, - HashTablePreallocationState *prealloc_state) { +inline bool FastSeparateChainingHashTable<resizable, + serializable, + force_key_copy, + allow_duplicate_keys>:: + locateBucketForInsertion(const std::size_t hash_code, + const std::size_t variable_key_allocation_required, + void **bucket, + std::atomic<std::size_t> **pending_chain_ptr, + std::size_t *pending_chain_ptr_finish_value, + HashTablePreallocationState *prealloc_state) { DEBUG_ASSERT((prealloc_state == nullptr) || allow_duplicate_keys); if (*bucket == nullptr) { *pending_chain_ptr = &(slots_[hash_code % header_->num_slots]); } else { - *pending_chain_ptr = static_cast<std::atomic<std::size_t>*>(*bucket); + *pending_chain_ptr = static_cast<std::atomic<std::size_t> *>(*bucket); } for (;;) { std::size_t existing_chain_ptr = 0; - if ((*pending_chain_ptr)->compare_exchange_strong(existing_chain_ptr, -
<TRUNCATED>