1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. 2 // This source code is licensed under both the GPLv2 (found in the 3 // COPYING file in the root directory) and Apache 2.0 License 4 // (found in the LICENSE.Apache file in the root directory). 5 #include "utilities/merge_operators/sortlist.h" 6 #include "rocksdb/merge_operator.h" 7 #include "rocksdb/slice.h" 8 #include "utilities/merge_operators.h" 9 10 using ROCKSDB_NAMESPACE::Logger; 11 using ROCKSDB_NAMESPACE::MergeOperator; 12 using ROCKSDB_NAMESPACE::Slice; 13 14 namespace ROCKSDB_NAMESPACE { 15 16 bool SortList::FullMergeV2(const MergeOperationInput& merge_in, 17 MergeOperationOutput* merge_out) const { 18 std::vector<int> left; 19 for (Slice slice : merge_in.operand_list) { 20 std::vector<int> right; 21 MakeVector(right, slice); 22 left = Merge(left, right); 23 } 24 for (int i = 0; i < static_cast<int>(left.size()) - 1; i++) { 25 merge_out->new_value.append(std::to_string(left[i])).append(","); 26 } 27 merge_out->new_value.append(std::to_string(left.back())); 28 return true; 29 } 30 31 bool SortList::PartialMerge(const Slice& /*key*/, const Slice& left_operand, 32 const Slice& right_operand, std::string* new_value, 33 Logger* /*logger*/) const { 34 std::vector<int> left; 35 std::vector<int> right; 36 MakeVector(left, left_operand); 37 MakeVector(right, right_operand); 38 left = Merge(left, right); 39 for (int i = 0; i < static_cast<int>(left.size()) - 1; i++) { 40 new_value->append(std::to_string(left[i])).append(","); 41 } 42 new_value->append(std::to_string(left.back())); 43 return true; 44 } 45 46 bool SortList::PartialMergeMulti(const Slice& /*key*/, 47 const std::deque<Slice>& operand_list, 48 std::string* new_value, 49 Logger* /*logger*/) const { 50 (void)operand_list; 51 (void)new_value; 52 return true; 53 } 54 55 const char* SortList::Name() const { return "MergeSortOperator"; } 56 57 void SortList::MakeVector(std::vector<int>& operand, Slice slice) const { 58 do { 59 const char* begin = slice.data_; 60 while (*slice.data_ != ',' && *slice.data_) slice.data_++; 61 operand.push_back(std::stoi(std::string(begin, slice.data_))); 62 } while (0 != *slice.data_++); 63 } 64 65 std::vector<int> SortList::Merge(std::vector<int>& left, 66 std::vector<int>& right) const { 67 // Fill the resultant vector with sorted results from both vectors 68 std::vector<int> result; 69 unsigned left_it = 0, right_it = 0; 70 71 while (left_it < left.size() && right_it < right.size()) { 72 // If the left value is smaller than the right it goes next 73 // into the resultant vector 74 if (left[left_it] < right[right_it]) { 75 result.push_back(left[left_it]); 76 left_it++; 77 } else { 78 result.push_back(right[right_it]); 79 right_it++; 80 } 81 } 82 83 // Push the remaining data from both vectors onto the resultant 84 while (left_it < left.size()) { 85 result.push_back(left[left_it]); 86 left_it++; 87 } 88 89 while (right_it < right.size()) { 90 result.push_back(right[right_it]); 91 right_it++; 92 } 93 94 return result; 95 } 96 97 std::shared_ptr<MergeOperator> MergeOperators::CreateSortOperator() { 98 return std::make_shared<SortList>(); 99 } 100 } // namespace ROCKSDB_NAMESPACE 101