quickstep-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jianq...@apache.org
Subject [1/2] incubator-quickstep git commit: Improvements and bug fixes
Date Mon, 18 Dec 2017 01:41:57 GMT
Repository: incubator-quickstep
Updated Branches:
  refs/heads/trace aec7623aa -> 7e8b33f8a


http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/7e8b33f8/storage/CompactKeySeparateChainingHashTable.hpp
----------------------------------------------------------------------
diff --git a/storage/CompactKeySeparateChainingHashTable.hpp b/storage/CompactKeySeparateChainingHashTable.hpp
new file mode 100644
index 0000000..0d057e4
--- /dev/null
+++ b/storage/CompactKeySeparateChainingHashTable.hpp
@@ -0,0 +1,234 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ **/
+
+#ifndef QUICKSTEP_STORAGE_COMPACT_KEY_SEPARATE_CHAINING_HASH_TABLE_HPP_
+#define QUICKSTEP_STORAGE_COMPACT_KEY_SEPARATE_CHAINING_HASH_TABLE_HPP_
+
+#include <atomic>
+#include <cstdint>
+#include <memory>
+#include <vector>
+
+#include "catalog/CatalogTypedefs.hpp"
+#include "cli/Flags.hpp"
+#include "storage/HashTableBase.hpp"
+#include "storage/StorageConstants.hpp"
+#include "types/Type.hpp"
+#include "types/TypeID.hpp"
+#include "utility/Macros.hpp"
+#include "utility/Range.hpp"
+#include "utility/ScopedArray.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+class AggregationHandle;
+class ColumnVectorsValueAccessor;
+class StorageManager;
+
+class CompactKeySeparateChainingHashTable : public AggregationStateHashTableBase {
+ public:
+  CompactKeySeparateChainingHashTable(
+      const std::vector<const Type*> &key_types,
+      const std::size_t num_entries,
+      const std::vector<AggregationHandle *> &handles,
+      StorageManager *storage_manager);
+
+  bool upsertValueAccessorCompositeKey(
+      const std::vector<std::vector<MultiSourceAttributeId>> &argument_ids,
+      const std::vector<MultiSourceAttributeId> &key_attr_ids,
+      const ValueAccessorMultiplexer &accessor_mux) override;
+
+  void destroyPayload() override {}
+
+  HashTableImplType getImplType() const override {
+    return HashTableImplType::kCompactKeySeparateChaining;
+  }
+
+  std::size_t getMemoryConsumptionBytes() const override {
+    return kSlotDataSize * num_slots_ + kKeyBucketDataSize * num_key_buckets_;
+  }
+
+  inline std::size_t getNumInitializationPartitions() const {
+    return slots_init_splitter_->getNumPartitions();
+  }
+
+  inline std::size_t getNumFinalizationPartitions() const {
+    if (final_splitter_ == nullptr) {
+      final_splitter_ = std::make_unique<RangeSplitter>(
+          RangeSplitter::CreateWithPartitionLength(
+              0, buckets_allocated_.load(std::memory_order_relaxed),
+              kFinalMinPartitionLength, FLAGS_num_workers * 2));
+    }
+    return final_splitter_->getNumPartitions();
+  }
+
+  void initialize(const std::size_t partition_id) {
+    const Range slots_range = slots_init_splitter_->getPartition(partition_id);
+    std::memset(slots_.get() + slots_range.begin(),
+                0,
+                slots_range.size() * kSlotDataSize);
+
+    const Range key_buckets_range =
+        key_buckets_init_splitter_->getPartition(partition_id);
+    std::memset(key_buckets_.get() + key_buckets_range.begin(),
+                0,
+                key_buckets_range.size() * kKeyBucketDataSize);
+  }
+
+  void finalizeKeys(const std::size_t partition_id,
+                    ColumnVectorsValueAccessor *output) const;
+
+ private:
+  inline static std::size_t CacheLineAlignedBytes(const std::size_t actual_bytes) {
+    return (actual_bytes + kCacheLineBytes - 1) / kCacheLineBytes * kCacheLineBytes;
+  }
+
+  inline static std::size_t CalculateNumInitializationPartitions(
+      const std::size_t memory_size) {
+    // Set initialization memory block size as 4MB.
+    constexpr std::size_t kInitBlockSize = 4uL * 1024u * 1024u;
+
+    // At least 1 partition, at most 80 partitions.
+    return std::max(1uL, std::min(memory_size / kInitBlockSize, 80uL));
+  }
+
+  inline static std::size_t CalculateNumFinalizationPartitions(
+      const std::size_t num_entries) {
+    // Set finalization segment size as 4096 entries.
+    constexpr std::size_t kFinalizeSegmentSize = 4uL * 1024L;
+
+    // At least 1 partition, at most 80 partitions.
+    return std::max(1uL, std::min(num_entries / kFinalizeSegmentSize, 80uL));
+  }
+
+  using KeyCode = std::uint64_t;
+  using BucketIndex = std::uint32_t;
+
+  inline BucketIndex locateBucketInternal(const KeyCode key_code);
+
+  template <typename ValueAccessorT>
+  inline void constructCompactKeyCodeComponent(const std::size_t num_tuples,
+                                               const std::size_t offset,
+                                               const std::size_t key_size,
+                                               ValueAccessorT *accessor,
+                                               const attribute_id attr,
+                                               KeyCode *key_codes);
+
+  static constexpr std::size_t kInitMinPartitionLength = 1024uL * 256uL;
+  static constexpr std::size_t kFinalMinPartitionLength = 1024uL * 4uL;
+
+  struct KeyBucket {
+    KeyCode key_code;
+    std::atomic<BucketIndex> next;
+  };
+
+  static constexpr std::size_t kSlotDataSize = sizeof(std::atomic<BucketIndex>);
+  static constexpr std::size_t kKeyBucketDataSize = sizeof(KeyBucket);
+  static constexpr BucketIndex kExclusiveState = std::numeric_limits<BucketIndex>::max();
+
+  const std::vector<const Type*> key_types_;
+  std::vector<std::size_t> key_sizes_;
+
+  ScopedArray<std::atomic<BucketIndex>> slots_;
+  ScopedArray<KeyBucket> key_buckets_;
+
+  std::size_t num_slots_;
+  std::size_t num_key_buckets_;
+  std::atomic<std::size_t> buckets_allocated_;
+
+  std::unique_ptr<RangeSplitter> slots_init_splitter_;
+  std::unique_ptr<RangeSplitter> key_buckets_init_splitter_;
+  mutable std::unique_ptr<RangeSplitter> final_splitter_;
+
+  DISALLOW_COPY_AND_ASSIGN(CompactKeySeparateChainingHashTable);
+};
+
+// ----------------------------------------------------------------------------
+// Implementations of class methods follow.
+
+inline CompactKeySeparateChainingHashTable::BucketIndex
+    CompactKeySeparateChainingHashTable::locateBucketInternal(const KeyCode key_code) {
+  std::atomic<BucketIndex> *pending_chain = &slots_[key_code % num_slots_];
+
+  for (;;) {
+    BucketIndex existing_chain = 0;
+
+    // Check if current node is the end of the chain.
+    if (pending_chain->compare_exchange_strong(existing_chain,
+                                               kExclusiveState,
+                                               std::memory_order_acq_rel)) {
+      const BucketIndex bucket_index =
+          buckets_allocated_.fetch_add(1, std::memory_order_relaxed);
+
+      // TODO(jianqiao): Resize.
+      if (bucket_index > num_key_buckets_) {
+        LOG(FATAL) << "Need resize, not handled";
+      }
+
+      // Store key code into key bucket.
+      key_buckets_[bucket_index].key_code = key_code;
+
+      // Update the chaing pointer to point to the new node.
+      pending_chain->store(bucket_index + 1, std::memory_order_release);
+
+      return bucket_index;
+    }
+
+    // Spin until the pointer is available.
+    while (existing_chain == kExclusiveState) {
+      existing_chain = pending_chain->load(std::memory_order_acquire);
+    }
+
+    if (existing_chain == 0) {
+      // Other thread had to roll back, so try again.
+      continue;
+    }
+
+    const BucketIndex bucket_index = existing_chain - 1;
+    KeyBucket &key_bucket = key_buckets_[bucket_index];
+    if (key_bucket.key_code == key_code) {
+      return bucket_index;
+    } else {
+      pending_chain = &key_bucket.next;
+    }
+  }
+}
+
+template <typename ValueAccessorT>
+inline void CompactKeySeparateChainingHashTable
+    ::constructCompactKeyCodeComponent(const std::size_t num_tuples,
+                                       const std::size_t offset,
+                                       const std::size_t key_size,
+                                       ValueAccessorT *accessor,
+                                       const attribute_id attr,
+                                       KeyCode *key_codes) {
+  accessor->beginIteration();
+  for (std::size_t i = 0; i < num_tuples; ++i) {
+    accessor->next();
+    std::memcpy(reinterpret_cast<char*>(key_codes + i) + offset,
+                accessor->template getUntypedValue<false>(attr),
+                key_size);
+  }
+}
+
+}  // namespace quickstep
+
+#endif  // QUICKSTEP_STORAGE_COMPACT_KEY_SEPARATE_CHAINING_HASH_TABLE_HPP_

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/7e8b33f8/storage/Flags.hpp
----------------------------------------------------------------------
diff --git a/storage/Flags.hpp b/storage/Flags.hpp
index 1d5527c..87f7da4 100644
--- a/storage/Flags.hpp
+++ b/storage/Flags.hpp
@@ -41,7 +41,6 @@ DECLARE_bool(use_hdfs);
 DECLARE_string(hdfs_namenode_host);
 DECLARE_int32(hdfs_namenode_port);
 DECLARE_int32(hdfs_num_replications);
-
 #endif
 
 /** @} */

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/7e8b33f8/storage/HashTable.proto
----------------------------------------------------------------------
diff --git a/storage/HashTable.proto b/storage/HashTable.proto
index d489b9f..40c8e32 100644
--- a/storage/HashTable.proto
+++ b/storage/HashTable.proto
@@ -23,16 +23,11 @@ import "types/Type.proto";
 
 enum HashTableImplType {
   COLLISION_FREE_VECTOR = 0;
-  LINEAR_OPEN_ADDRESSING = 1;
-  SEPARATE_CHAINING = 2;
-  SIMPLE_SCALAR_SEPARATE_CHAINING = 3;
-  THREAD_PRIVATE_COMPACT_KEY = 4;
-}
-
-message CollisionFreeVectorInfo {
-  required uint64 memory_size = 1;
-  required uint64 num_init_partitions = 2;
-  repeated uint64 state_offsets = 3;
+  COMPACT_KEY_SEPARATE_CHAINING = 1;
+  LINEAR_OPEN_ADDRESSING = 2;
+  SEPARATE_CHAINING = 3;
+  SIMPLE_SCALAR_SEPARATE_CHAINING = 4;
+  THREAD_PRIVATE_COMPACT_KEY = 5;
 }
 
 // NOTE(chasseur): This proto describes the run-time parameters for a resizable

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/7e8b33f8/storage/HashTableBase.hpp
----------------------------------------------------------------------
diff --git a/storage/HashTableBase.hpp b/storage/HashTableBase.hpp
index 4d9310c..2e89554 100644
--- a/storage/HashTableBase.hpp
+++ b/storage/HashTableBase.hpp
@@ -42,6 +42,7 @@ class ValueAccessor;
  **/
 enum class HashTableImplType {
   kCollisionFreeVector,
+  kCompactKeySeparateChaining,
   kLinearOpenAddressing,
   kSeparateChaining,
   kSimpleScalarSeparateChaining,

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/7e8b33f8/storage/HashTableFactory.hpp
----------------------------------------------------------------------
diff --git a/storage/HashTableFactory.hpp b/storage/HashTableFactory.hpp
index 732920f..df71100 100644
--- a/storage/HashTableFactory.hpp
+++ b/storage/HashTableFactory.hpp
@@ -25,6 +25,7 @@
 #include <vector>
 
 #include "storage/CollisionFreeVectorTable.hpp"
+#include "storage/CompactKeySeparateChainingHashTable.hpp"
 #include "storage/HashTable.hpp"
 #include "storage/HashTableBase.hpp"
 #include "storage/HashTable.pb.h"
@@ -118,6 +119,8 @@ inline HashTableImplType HashTableImplTypeFromProto(
   switch (proto_type) {
     case serialization::HashTableImplType::COLLISION_FREE_VECTOR:
       return HashTableImplType::kCollisionFreeVector;
+    case serialization::HashTableImplType::COMPACT_KEY_SEPARATE_CHAINING:
+      return HashTableImplType::kCompactKeySeparateChaining;
     case serialization::HashTableImplType::LINEAR_OPEN_ADDRESSING:
       return HashTableImplType::kLinearOpenAddressing;
     case serialization::HashTableImplType::SEPARATE_CHAINING:
@@ -356,14 +359,6 @@ class AggregationStateHashTableFactory {
    * @param storage_manager The StorageManager to use (a StorageBlob will be
    *        allocated to hold the hash table's contents). Forwarded as-is to the
    *        hash table constructor.
-   * @param num_partitions The number of partitions of this aggregation state
-   *        hash table.
-   * @param collision_free_vector_memory_size For CollisionFreeVectorTable,
-   *        the memory size.
-   * @param collision_free_vector_num_init_partitions For
-   *        CollisionFreeVectorTable, the number of partitions to initialize.
-   * @param collision_free_vector_state_offsets For CollisionFreeVectorTable,
-   *        the offsets for each state.
    * @return A new aggregation state hash table.
    **/
   static AggregationStateHashTableBase* CreateResizable(
@@ -371,18 +366,15 @@ class AggregationStateHashTableFactory {
       const std::vector<const Type*> &key_types,
       const std::size_t num_entries,
       const std::vector<AggregationHandle *> &handles,
-      StorageManager *storage_manager,
-      const std::size_t num_partitions = 1u,
-      const std::size_t collision_free_vector_memory_size = 0,
-      const std::size_t collision_free_vector_num_init_partitions = 0,
-      const std::vector<std::size_t> &collision_free_vector_state_offsets = std::vector<std::size_t>())
{
+      StorageManager *storage_manager) {
     switch (hash_table_type) {
       case HashTableImplType::kCollisionFreeVector:
         DCHECK_EQ(1u, key_types.size());
         return new CollisionFreeVectorTable(
-            key_types.front(), num_entries, collision_free_vector_memory_size,
-            collision_free_vector_num_init_partitions, num_partitions,
-            collision_free_vector_state_offsets, handles, storage_manager);
+            key_types.front(), num_entries, handles, storage_manager);
+      case HashTableImplType::kCompactKeySeparateChaining:
+        return new CompactKeySeparateChainingHashTable(
+            key_types, num_entries, handles, storage_manager);
       case HashTableImplType::kSeparateChaining:
         return new PackedPayloadHashTable(
             key_types, num_entries, handles, storage_manager);

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/7e8b33f8/utility/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/utility/CMakeLists.txt b/utility/CMakeLists.txt
index c5c9dd8..c78ec59 100644
--- a/utility/CMakeLists.txt
+++ b/utility/CMakeLists.txt
@@ -194,6 +194,8 @@ add_library(quickstep_utility_PrimeNumber PrimeNumber.cpp PrimeNumber.hpp)
 add_library(quickstep_utility_PtrList ../empty_src.cpp PtrList.hpp)
 add_library(quickstep_utility_PtrMap ../empty_src.cpp PtrMap.hpp)
 add_library(quickstep_utility_PtrVector ../empty_src.cpp PtrVector.hpp)
+add_library(quickstep_utility_Range ../empty_src.cpp Range.hpp)
+add_library(quickstep_utility_ScopedArray ../empty_src.cpp ScopedArray.hpp)
 add_library(quickstep_utility_ScopedBuffer ../empty_src.cpp ScopedBuffer.hpp)
 add_library(quickstep_utility_ScopedDeleter ../empty_src.cpp ScopedDeleter.hpp)
 add_library(quickstep_utility_ScopedReassignment ../empty_src.cpp ScopedReassignment.hpp)
@@ -308,6 +310,12 @@ target_link_libraries(quickstep_utility_PtrMap
 target_link_libraries(quickstep_utility_PtrVector
                       glog
                       quickstep_utility_Macros)
+target_link_libraries(quickstep_utility_Range
+                      glog
+                      quickstep_utility_Macros)
+target_link_libraries(quickstep_utility_ScopedArray
+                      quickstep_utility_ScopedBuffer
+                      quickstep_utility_Macros)
 target_link_libraries(quickstep_utility_ScopedBuffer
                       glog
                       quickstep_utility_Alignment
@@ -380,6 +388,8 @@ target_link_libraries(quickstep_utility
                       quickstep_utility_PtrList
                       quickstep_utility_PtrMap
                       quickstep_utility_PtrVector
+                      quickstep_utility_Range
+                      quickstep_utility_ScopedArray
                       quickstep_utility_ScopedBuffer
                       quickstep_utility_ScopedDeleter
                       quickstep_utility_ScopedReassignment

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/7e8b33f8/utility/ExecutionDAGVisualizer.cpp
----------------------------------------------------------------------
diff --git a/utility/ExecutionDAGVisualizer.cpp b/utility/ExecutionDAGVisualizer.cpp
index f009a72..bb8fe8f 100644
--- a/utility/ExecutionDAGVisualizer.cpp
+++ b/utility/ExecutionDAGVisualizer.cpp
@@ -234,6 +234,9 @@ void ExecutionDAGVisualizer::bindProfilingStats(
         std::max(time_end[relop_index], workorder_end_time);
     time_elapsed[relop_index] += (workorder_end_time - workorder_start_time);
 
+    if (workorders_count.find(relop_index) == workorders_count.end()) {
+      workorders_count[relop_index] = 0;
+    }
     ++workorders_count[relop_index];
     if (mean_time_per_workorder.find(relop_index) ==
         mean_time_per_workorder.end()) {
@@ -289,6 +292,7 @@ void ExecutionDAGVisualizer::bindProfilingStats(
       node_info.labels.emplace_back(
           "effective concurrency: " + FormatDigits(concurrency, 2));
 
+      DCHECK(workorders_count.find(node_index) != workorders_count.end());
       const std::size_t workorders_count_for_node = workorders_count[node_index];
       if (workorders_count_for_node > 0) {
         mean_time_per_workorder[node_index] =

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/7e8b33f8/utility/Range.hpp
----------------------------------------------------------------------
diff --git a/utility/Range.hpp b/utility/Range.hpp
new file mode 100644
index 0000000..4fb55be
--- /dev/null
+++ b/utility/Range.hpp
@@ -0,0 +1,188 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ **/
+
+#ifndef QUICKSTEP_UTILITY_RANGE_HPP_
+#define QUICKSTEP_UTILITY_RANGE_HPP_
+
+#include <algorithm>
+#include <cstddef>
+#include <limits>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+class Range {
+ public:
+  Range(const std::size_t begin, const std::size_t end)
+      : begin_(begin), end_(end) {
+    DCHECK_LE(begin_, end_);
+  }
+
+  Range(const Range &range)
+      : begin_(range.begin_), end_(range.end_) {
+    DCHECK_LE(begin_, end_);
+  }
+
+  inline std::size_t begin() const {
+    return begin_;
+  }
+
+  inline std::size_t end() const {
+    return end_;
+  }
+
+  inline std::size_t size() const {
+    return end_ - begin_;
+  }
+
+ private:
+  const std::size_t begin_;
+  const std::size_t end_;
+};
+
+class RangeSplitter {
+ public:
+  static RangeSplitter CreateWithPartitionLength(
+      const std::size_t begin,
+      const std::size_t end,
+      const std::size_t min_partition_length,
+      const std::size_t max_num_partitions = kMaxNumPartitions) {
+    DCHECK_LE(begin, end);
+    DCHECK_GT(min_partition_length, 0u);
+    DCHECK_GT(max_num_partitions, 0u);
+
+    const std::size_t range_length = end - begin;
+    const std::size_t est_num_partitions = range_length / min_partition_length;
+
+    const std::size_t num_partitions =
+        std::max(1uL, std::min(est_num_partitions, max_num_partitions));
+    const std::size_t partition_length = range_length / num_partitions;
+    return RangeSplitter(begin, end, num_partitions, partition_length);
+  }
+
+  static RangeSplitter CreateWithPartitionLength(
+      const Range &range,
+      const std::size_t min_partition_length,
+      const std::size_t max_num_partitions = kMaxNumPartitions) {
+    return CreateWithPartitionLength(
+        range.begin(), range.end(), min_partition_length, max_num_partitions);
+  }
+
+  static RangeSplitter CreateWithMinMaxPartitionLength(
+      const std::size_t begin,
+      const std::size_t end,
+      const std::size_t min_partition_length,
+      const std::size_t max_partition_length,
+      const std::size_t ept_num_partitions) {
+    DCHECK_LE(begin, end);
+    DCHECK_LE(min_partition_length, max_partition_length);
+    DCHECK_GT(min_partition_length, 0u);
+    DCHECK_GT(max_partition_length, 0u);
+
+    const std::size_t range_length = end - begin;
+    const std::size_t ept_partition_length = range_length / ept_num_partitions;
+
+    std::size_t partition_length;
+    if (ept_partition_length < min_partition_length) {
+      partition_length = min_partition_length;
+    } else if (ept_partition_length > max_partition_length) {
+      partition_length = max_partition_length;
+    } else {
+      partition_length = ept_partition_length;
+    }
+
+    const std::size_t num_partitions =
+        std::max(1uL, range_length / partition_length);
+    return RangeSplitter(begin, end, num_partitions, partition_length);
+  }
+
+  static RangeSplitter CreateWithMinMaxPartitionLength(
+      const Range &range,
+      const std::size_t min_partition_length,
+      const std::size_t max_partition_length,
+      const std::size_t ept_num_partitions) {
+    return CreateWithMinMaxPartitionLength(
+        range.begin(), range.end(),
+        min_partition_length, max_partition_length,
+        ept_num_partitions);
+  }
+
+  static RangeSplitter CreateWithNumPartitions(
+      const std::size_t begin,
+      const std::size_t end,
+      const std::size_t num_partitions) {
+    DCHECK_LE(begin, end);
+    DCHECK_GT(num_partitions, 0u);
+
+    const std::size_t partition_length = (end - begin) / num_partitions;
+    return RangeSplitter(begin, end, num_partitions, partition_length);
+  }
+
+  static RangeSplitter CreateWithNumPartitions(
+      const Range &range,
+      const std::size_t num_partitions) {
+    return CreateWithNumPartitions(range.begin(), range.end(), num_partitions);
+  }
+
+  RangeSplitter(const RangeSplitter &other)
+      : begin_(other.begin_), end_(other.end_),
+        num_partitions_(other.num_partitions_),
+        partition_length_(other.partition_length_) {}
+
+  inline std::size_t getNumPartitions() const {
+    return num_partitions_;
+  }
+
+  inline Range getPartition(const std::size_t partition_id) const {
+    DCHECK_LT(partition_id, num_partitions_);
+    const std::size_t begin = begin_ + partition_length_ * partition_id;
+    const std::size_t end =
+        partition_id == num_partitions_ - 1
+            ? end_
+            : begin + partition_length_;
+    return Range(begin, end);
+  }
+
+ private:
+  RangeSplitter(const std::size_t begin,
+                const std::size_t end,
+                const std::size_t num_partitions,
+                const std::size_t partition_length)
+      : begin_(begin),
+        end_(end),
+        num_partitions_(num_partitions),
+        partition_length_(partition_length) {
+    DCHECK_LE(num_partitions_ * partition_length_, end_);
+  }
+
+  static constexpr std::size_t kMaxNumPartitions =
+      std::numeric_limits<std::size_t>::max();
+
+  const std::size_t begin_;
+  const std::size_t end_;
+  const std::size_t num_partitions_;
+  const std::size_t partition_length_;
+};
+
+}  // namespace quickstep
+
+#endif  // QUICKSTEP_UTILITY_RANGE_HPP_

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/7e8b33f8/utility/ScopedArray.hpp
----------------------------------------------------------------------
diff --git a/utility/ScopedArray.hpp b/utility/ScopedArray.hpp
new file mode 100644
index 0000000..c464ba9
--- /dev/null
+++ b/utility/ScopedArray.hpp
@@ -0,0 +1,78 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ **/
+
+#ifndef QUICKSTEP_UTILITY_SCOPED_ARRAY_HPP_
+#define QUICKSTEP_UTILITY_SCOPED_ARRAY_HPP_
+
+#include <cstddef>
+#include <utility>
+
+#include "utility/ScopedBuffer.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+
+template <typename T>
+class ScopedArray {
+ public:
+  explicit ScopedArray(const std::size_t length, const bool initialize = false)
+      : buffer_(length * sizeof(T), initialize) {}
+
+  explicit ScopedArray(T *data = nullptr)
+      : buffer_(data) {}
+
+  explicit ScopedArray(ScopedArray &&orig)
+      : buffer_(std::move(orig.buffer_)) {}
+
+  inline void reset(const std::size_t length, const bool initialize = false) {
+    buffer_.reset(length * sizeof(T), initialize);
+  }
+
+  inline void reset(T *data = nullptr) {
+    buffer_.reset(data);
+  }
+
+  inline ScopedArray& operator=(ScopedArray &&rhs) {
+    buffer_ = std::move(rhs.buffer_);
+    return *this;
+  }
+
+  inline T* get() const {
+    return static_cast<T*>(buffer_.get());
+  }
+
+  inline T* release() {
+    return static_cast<T*>(buffer_.release());
+  }
+
+  inline T* operator->() const {
+    return get();
+  }
+
+  inline T& operator[](const std::size_t index) const {
+    return get()[index];
+  }
+
+ private:
+  ScopedBuffer buffer_;
+};
+
+}  // namespace quickstep
+
+#endif  // QUICKSTEP_UTILITY_SCOPED_ARRAY_HPP_


Mime
View raw message