quickstep-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hakanmemiso...@apache.org
Subject incubator-quickstep git commit: Changed hash table insertion method to add new bucket to the beginning of the chain.
Date Tue, 11 Oct 2016 23:54:26 GMT
Repository: incubator-quickstep
Updated Branches:
  refs/heads/chaining [created] 8729df822


Changed hash table insertion method to add new bucket to the beginning of the chain.


Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/8729df82
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/8729df82
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/8729df82

Branch: refs/heads/chaining
Commit: 8729df8226eef10345d366fc050c3c1b8fe87077
Parents: 80af233
Author: Hakan Memisoglu <hakanmemisoglu@apache.org>
Authored: Tue Oct 11 18:53:57 2016 -0500
Committer: Hakan Memisoglu <hakanmemisoglu@apache.org>
Committed: Tue Oct 11 18:53:57 2016 -0500

----------------------------------------------------------------------
 storage/SeparateChainingHashTable.hpp | 101 +++++++++++++++++++----------
 1 file changed, 68 insertions(+), 33 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/8729df82/storage/SeparateChainingHashTable.hpp
----------------------------------------------------------------------
diff --git a/storage/SeparateChainingHashTable.hpp b/storage/SeparateChainingHashTable.hpp
index 3ca060d..4b46e30 100644
--- a/storage/SeparateChainingHashTable.hpp
+++ b/storage/SeparateChainingHashTable.hpp
@@ -695,45 +695,80 @@ HashTablePutResult
   const std::size_t hash_code = key.getHash();
   void *bucket = nullptr;
   std::atomic<std::size_t> *pending_chain_ptr;
-  std::size_t pending_chain_ptr_finish_value;
-  for (;;) {
-    if (locateBucketForInsertion(hash_code,
-                                 0,
-                                 &bucket,
-                                 &pending_chain_ptr,
-                                 &pending_chain_ptr_finish_value,
-                                 prealloc_state)) {
-      // Found an empty bucket.
-      break;
-    } else if (bucket == nullptr) {
-      // Ran out of buckets. Deallocate any variable space that we were unable
-      // to use.
-      DEBUG_ASSERT(prealloc_state == nullptr);
-      key_manager_.deallocateVariableLengthKeyStorage(variable_key_size);
-      return HashTablePutResult::kOutOfSpace;
-    } else {
-      // Hash collision found, and duplicates aren't allowed.
-      DEBUG_ASSERT(!allow_duplicate_keys);
-      DEBUG_ASSERT(prealloc_state == nullptr);
-      if (key_manager_.scalarKeyCollisionCheck(key, bucket)) {
-        // Duplicate key. Deallocate any variable storage space and return.
-        key_manager_.deallocateVariableLengthKeyStorage(variable_key_size);
-        return HashTablePutResult::kDuplicateKey;
-      }
-    }
+  //std::size_t pending_chain_ptr_finish_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);
+    key_manager_.deallocateVariableLengthKeyStorage(variable_key_size);
+    return HashTablePutResult::kOutOfSpace;
   }
-
-  // Write the key and hash.
+  bucket = static_cast<char*>(buckets_) + allocated_bucket_num * bucket_size_;
+  
+  // Why is prealloc taken as an argument?
   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) ValueT(value);
+  
+  std::atomic<std::size_t>* buckets_next_ptr = static_cast<std::atomic<std::size_t>*>(bucket);
 
-  // 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 = &(slots_[hash_code % header_->num_slots]);
+  for (;;) {
+    // Save the address;
+    std::size_t existing_chain_ptr = pending_chain_ptr->load(std::memory_order_release);
+
+    // Make bucket's (new head) ptr to hold address of old head.
+    buckets_next_ptr->store(existing_chain_ptr, std::memory_order_release);
+    if (pending_chain_ptr->compare_exchange_strong(existing_chain_ptr,
+						   allocated_bucket_num + 1,
+						   std::memory_order_acq_rel)) {
+      break;
+    }
+  }
+  return HashTablePutResult::kOK;
+  
+  // OLD CODE
+  // for (;;) {
+  //   if (locateBucketForInsertion(hash_code,
+  //                                0,
+  //                                &bucket,
+  //                                &pending_chain_ptr,
+  //                                &pending_chain_ptr_finish_value,
+  //                                prealloc_state)) {
+  //     // Found an empty bucket.
+  //     break;
+  //   } else if (bucket == nullptr) {
+  //     // Ran out of buckets. Deallocate any variable space that we were unable
+  //     // to use.
+  //     DEBUG_ASSERT(prealloc_state == nullptr);
+  //     key_manager_.deallocateVariableLengthKeyStorage(variable_key_size);
+  //     return HashTablePutResult::kOutOfSpace;
+  //   } else {
+  //     // Hash collision found, and duplicates aren't allowed.
+  //     DEBUG_ASSERT(!allow_duplicate_keys);
+  //     DEBUG_ASSERT(prealloc_state == nullptr);
+  //     if (key_manager_.scalarKeyCollisionCheck(key, bucket)) {
+  //       // Duplicate key. Deallocate any variable storage space and return.
+  //       key_manager_.deallocateVariableLengthKeyStorage(variable_key_size);
+  //       return HashTablePutResult::kDuplicateKey;
+  //     }
+  //   }
+  // }
+
+  // // Write the key and hash.
+  // 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) 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);
 
   // We're all done.
-  return HashTablePutResult::kOK;
+  //return HashTablePutResult::kOK;
 }
 
 template <typename ValueT,


Mime
View raw message