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