ceph/src/arrow/cpp/src/arrow/util/key_value_metadata.cc

   1 // Licensed to the Apache Software Foundation (ASF) under one
   2 // or more contributor license agreements.  See the NOTICE file
   3 // distributed with this work for additional information
   4 // regarding copyright ownership.  The ASF licenses this file
   5 // to you under the Apache License, Version 2.0 (the
   6 // "License"); you may not use this file except in compliance
   7 // with the License.  You may obtain a copy of the License at
   8 //
   9 //   http://www.apache.org/licenses/LICENSE-2.0
  10 //
  11 // Unless required by applicable law or agreed to in writing,
  12 // software distributed under the License is distributed on an
  13 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  14 // KIND, either express or implied.  See the License for the
  15 // specific language governing permissions and limitations
  16 // under the License.
  17
  18 #include <algorithm>
  19 #include <cstddef>
  20 #include <cstdint>
  21 #include <memory>
  22 #include <sstream>
  23 #include <string>
  24 #include <unordered_map>
  25 #include <unordered_set>
  26 #include <utility>
  27 #include <vector>
  28
  29 #include "arrow/result.h"
  30 #include "arrow/status.h"
  31 #include "arrow/util/key_value_metadata.h"
  32 #include "arrow/util/logging.h"
  33 #include "arrow/util/sort.h"
  34
  35 using std::size_t;
  36
  37 namespace arrow {
  38
  39 static std::vector<std::string> UnorderedMapKeys(
  40     const std::unordered_map<std::string, std::string>& map) {
  41   std::vector<std::string> keys;
  42   keys.reserve(map.size());
  43   for (const auto& pair : map) {
  44     keys.push_back(pair.first);
  45   }
  46   return keys;
  47 }
  48
  49 static std::vector<std::string> UnorderedMapValues(
  50     const std::unordered_map<std::string, std::string>& map) {
  51   std::vector<std::string> values;
  52   values.reserve(map.size());
  53   for (const auto& pair : map) {
  54     values.push_back(pair.second);
  55   }
  56   return values;
  57 }
  58
  59 KeyValueMetadata::KeyValueMetadata() {}
  60
  61 KeyValueMetadata::KeyValueMetadata(
  62     const std::unordered_map<std::string, std::string>& map)
  63     : keys_(UnorderedMapKeys(map)), values_(UnorderedMapValues(map)) {
  64   ARROW_CHECK_EQ(keys_.size(), values_.size());
  65 }
  66
  67 KeyValueMetadata::KeyValueMetadata(std::vector<std::string> keys,
  68                                    std::vector<std::string> values)
  69     : keys_(std::move(keys)), values_(std::move(values)) {
  70   ARROW_CHECK_EQ(keys.size(), values.size());
  71 }
  72
  73 std::shared_ptr<KeyValueMetadata> KeyValueMetadata::Make(
  74     std::vector<std::string> keys, std::vector<std::string> values) {
  75   return std::make_shared<KeyValueMetadata>(std::move(keys), std::move(values));
  76 }
  77
  78 void KeyValueMetadata::ToUnorderedMap(
  79     std::unordered_map<std::string, std::string>* out) const {
  80   DCHECK_NE(out, nullptr);
  81   const int64_t n = size();
  82   out->reserve(n);
  83   for (int64_t i = 0; i < n; ++i) {
  84     out->insert(std::make_pair(key(i), value(i)));
  85   }
  86 }
  87
  88 void KeyValueMetadata::Append(std::string key, std::string value) {
  89   keys_.push_back(std::move(key));
  90   values_.push_back(std::move(value));
  91 }
  92
  93 Result<std::string> KeyValueMetadata::Get(const std::string& key) const {
  94   auto index = FindKey(key);
  95   if (index < 0) {
  96     return Status::KeyError(key);
  97   } else {
  98     return value(index);
  99   }
 100 }
 101
 102 Status KeyValueMetadata::Delete(int64_t index) {
 103   keys_.erase(keys_.begin() + index);
 104   values_.erase(values_.begin() + index);
 105   return Status::OK();
 106 }
 107
 108 Status KeyValueMetadata::DeleteMany(std::vector<int64_t> indices) {
 109   std::sort(indices.begin(), indices.end());
 110   const int64_t size = static_cast<int64_t>(keys_.size());
 111   indices.push_back(size);
 112
 113   int64_t shift = 0;
 114   for (int64_t i = 0; i < static_cast<int64_t>(indices.size() - 1); ++i) {
 115     ++shift;
 116     const auto start = indices[i] + 1;
 117     const auto stop = indices[i + 1];
 118     DCHECK_GE(start, 0);
 119     DCHECK_LE(start, size);
 120     DCHECK_GE(stop, 0);
 121     DCHECK_LE(stop, size);
 122     for (int64_t index = start; index < stop; ++index) {
 123       keys_[index - shift] = std::move(keys_[index]);
 124       values_[index - shift] = std::move(values_[index]);
 125     }
 126   }
 127   keys_.resize(size - shift);
 128   values_.resize(size - shift);
 129   return Status::OK();
 130 }
 131
 132 Status KeyValueMetadata::Delete(const std::string& key) {
 133   auto index = FindKey(key);
 134   if (index < 0) {
 135     return Status::KeyError(key);
 136   } else {
 137     return Delete(index);
 138   }
 139 }
 140
 141 Status KeyValueMetadata::Set(const std::string& key, const std::string& value) {
 142   auto index = FindKey(key);
 143   if (index < 0) {
 144     Append(key, value);
 145   } else {
 146     keys_[index] = key;
 147     values_[index] = value;
 148   }
 149   return Status::OK();
 150 }
 151
 152 bool KeyValueMetadata::Contains(const std::string& key) const {
 153   return FindKey(key) >= 0;
 154 }
 155
 156 void KeyValueMetadata::reserve(int64_t n) {
 157   DCHECK_GE(n, 0);
 158   const auto m = static_cast<size_t>(n);
 159   keys_.reserve(m);
 160   values_.reserve(m);
 161 }
 162
 163 int64_t KeyValueMetadata::size() const {
 164   DCHECK_EQ(keys_.size(), values_.size());
 165   return static_cast<int64_t>(keys_.size());
 166 }
 167
 168 const std::string& KeyValueMetadata::key(int64_t i) const {
 169   DCHECK_GE(i, 0);
 170   DCHECK_LT(static_cast<size_t>(i), keys_.size());
 171   return keys_[i];
 172 }
 173
 174 const std::string& KeyValueMetadata::value(int64_t i) const {
 175   DCHECK_GE(i, 0);
 176   DCHECK_LT(static_cast<size_t>(i), values_.size());
 177   return values_[i];
 178 }
 179
 180 std::vector<std::pair<std::string, std::string>> KeyValueMetadata::sorted_pairs() const {
 181   std::vector<std::pair<std::string, std::string>> pairs;
 182   pairs.reserve(size());
 183
 184   auto indices = internal::ArgSort(keys_);
 185   for (const auto i : indices) {
 186     pairs.emplace_back(keys_[i], values_[i]);
 187   }
 188   return pairs;
 189 }
 190
 191 int KeyValueMetadata::FindKey(const std::string& key) const {
 192   for (size_t i = 0; i < keys_.size(); ++i) {
 193     if (keys_[i] == key) {
 194       return static_cast<int>(i);
 195     }
 196   }
 197   return -1;
 198 }
 199
 200 std::shared_ptr<KeyValueMetadata> KeyValueMetadata::Copy() const {
 201   return std::make_shared<KeyValueMetadata>(keys_, values_);
 202 }
 203
 204 std::shared_ptr<KeyValueMetadata> KeyValueMetadata::Merge(
 205     const KeyValueMetadata& other) const {
 206   std::unordered_set<std::string> observed_keys;
 207   std::vector<std::string> result_keys;
 208   std::vector<std::string> result_values;
 209
 210   result_keys.reserve(keys_.size());
 211   result_values.reserve(keys_.size());
 212
 213   for (int64_t i = 0; i < other.size(); ++i) {
 214     const auto& key = other.key(i);
 215     auto it = observed_keys.find(key);
 216     if (it == observed_keys.end()) {
 217       result_keys.push_back(key);
 218       result_values.push_back(other.value(i));
 219       observed_keys.insert(key);
 220     }
 221   }
 222   for (size_t i = 0; i < keys_.size(); ++i) {
 223     auto it = observed_keys.find(keys_[i]);
 224     if (it == observed_keys.end()) {
 225       result_keys.push_back(keys_[i]);
 226       result_values.push_back(values_[i]);
 227       observed_keys.insert(keys_[i]);
 228     }
 229   }
 230
 231   return std::make_shared<KeyValueMetadata>(std::move(result_keys),
 232                                             std::move(result_values));
 233 }
 234
 235 bool KeyValueMetadata::Equals(const KeyValueMetadata& other) const {
 236   if (size() != other.size()) {
 237     return false;
 238   }
 239
 240   auto indices = internal::ArgSort(keys_);
 241   auto other_indices = internal::ArgSort(other.keys_);
 242
 243   for (int64_t i = 0; i < size(); ++i) {
 244     auto j = indices[i];
 245     auto k = other_indices[i];
 246     if (keys_[j] != other.keys_[k] || values_[j] != other.values_[k]) {
 247       return false;
 248     }
 249   }
 250   return true;
 251 }
 252
 253 std::string KeyValueMetadata::ToString() const {
 254   std::stringstream buffer;
 255
 256   buffer << "\n-- metadata --";
 257   for (int64_t i = 0; i < size(); ++i) {
 258     buffer << "\n" << keys_[i] << ": " << values_[i];
 259   }
 260
 261   return buffer.str();
 262 }
 263
 264 std::shared_ptr<KeyValueMetadata> key_value_metadata(
 265     const std::unordered_map<std::string, std::string>& pairs) {
 266   return std::make_shared<KeyValueMetadata>(pairs);
 267 }
 268
 269 std::shared_ptr<KeyValueMetadata> key_value_metadata(std::vector<std::string> keys,
 270                                                      std::vector<std::string> values) {
 271   return std::make_shared<KeyValueMetadata>(std::move(keys), std::move(values));
 272 }
 273
 274 }  // namespace arrow