You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by ha...@apache.org on 2016/10/14 16:51:48 UTC
incubator-quickstep git commit: Added simple version.
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 <ha...@apache.org>
Authored: Fri Oct 14 11:51:31 2016 -0500
Committer: Hakan Memisoglu <ha...@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,