Repository: incubator-quickstep Updated Branches: refs/heads/chaining b624413b9 -> e1828be90
Added simple version. Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/e1828be9 Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/e1828be9 Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/e1828be9 Branch: refs/heads/chaining Commit: e1828be90bda67476b3bd6d91e74751a13faf105 Parents: b624413 Author: Hakan Memisoglu <hakanmemiso...@apache.org> Authored: Fri Oct 14 11:51:31 2016 -0500 Committer: Hakan Memisoglu <hakanmemiso...@apache.org> Committed: Fri Oct 14 11:51:31 2016 -0500 ---------------------------------------------------------------------- storage/SeparateChainingHashTable.hpp | 3 +- .../SimpleScalarSeparateChainingHashTable.hpp | 52 ++++++++++---------- 2 files changed, 29 insertions(+), 26 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e1828be9/storage/SeparateChainingHashTable.hpp ---------------------------------------------------------------------- diff --git a/storage/SeparateChainingHashTable.hpp b/storage/SeparateChainingHashTable.hpp index b8f62dd..3de4c65 100644 --- a/storage/SeparateChainingHashTable.hpp +++ b/storage/SeparateChainingHashTable.hpp @@ -713,7 +713,8 @@ HashTablePutResult writeScalarKeyToBucket(key, hash_code, bucket, prealloc_state); new(static_cast<char*>(bucket) + kValueOffset) ValueT(value); - std::atomic<std::size_t>* buckets_next_ptr = static_cast<std::atomic<std::size_t>*>(bucket); + std::atomic<std::size_t> *buckets_next_ptr + = static_cast<std::atomic<std::size_t>*>(bucket); pending_chain_ptr = &(slots_[hash_code % header_->num_slots]); for (;;) { http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/e1828be9/storage/SimpleScalarSeparateChainingHashTable.hpp ---------------------------------------------------------------------- diff --git a/storage/SimpleScalarSeparateChainingHashTable.hpp b/storage/SimpleScalarSeparateChainingHashTable.hpp index 8448896..50c3929 100644 --- a/storage/SimpleScalarSeparateChainingHashTable.hpp +++ b/storage/SimpleScalarSeparateChainingHashTable.hpp @@ -634,34 +634,36 @@ HashTablePutResult const std::size_t hash_code = key.getHashScalarLiteral(); Bucket *bucket = nullptr; std::atomic<std::size_t> *pending_chain_ptr; - std::size_t pending_chain_ptr_finish_value; - if (locateBucketForInsertion(hash_code, - &bucket, - &pending_chain_ptr, - &pending_chain_ptr_finish_value, - prealloc_state)) { - // Found an empty bucket. - // Write the hash, which can be reversed to recover the key. - bucket->hash = hash_code; - - // Store the value by using placement new with ValueT's copy constructor. - new(&(bucket->value)) ValueT(value); + + const std::size_t allocated_bucket_num + = (prealloc_state == nullptr) + ? header_->buckets_allocated.fetch_add(1, std::memory_order_relaxed) + : (prealloc_state->bucket_position)++; + + if (allocated_bucket_num >= header_->num_buckets) { + header_->buckets_allocated.fetch_sub(1, std::memory_order_relaxed); + return HashTablePutResult::kOutOfSpace; + } + + bucket = buckets_ + allocated_bucket_num; + bucket->hash = hash_code; + new(&(bucket->value)) ValueT(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); + std::atomic<std::size_t> *buckets_next_ptr = &(bucket->next); - // We're all done. - return HashTablePutResult::kOK; - } else if (bucket == nullptr) { - // Ran out of buckets. - DCHECK(prealloc_state == nullptr); - return HashTablePutResult::kOutOfSpace; - } else { - // Collision found, and duplicates aren't allowed. - DCHECK(!allow_duplicate_keys); - DCHECK(prealloc_state == nullptr); - return HashTablePutResult::kDuplicateKey; + pending_chain_ptr = &(slots_[hash_code % header_->num_slots]); + for (;;) { + // Save the old address; + std::size_t existing_chain_ptr = pending_chain_ptr->load(std::memory_order_release); + + if (pending_chain_ptr->compare_exchange_strong(existing_chain_ptr, + allocated_bucket_num + 1, + std::memory_order_acq_rel)) { + buckets_next_ptr->store(existing_chain_ptr, std::memory_order_release); + break; + } } + return HashTablePutResult::kOK; } template <typename ValueT,