| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #ifndef SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_ | |
| 6 #define SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_ | |
| 7 | |
| 8 #include <stdint.h> | |
| 9 | |
| 10 #include <algorithm> | |
| 11 #include <cstddef> | |
| 12 #include <string> | |
| 13 | |
| 14 #include "base/json/string_escape.h" | |
| 15 #include "base/logging.h" | |
| 16 | |
| 17 namespace syncer { | |
| 18 | |
| 19 // An Ordinal<T> is an object that can be used for ordering. The | |
| 20 // Ordinal<T> class has an unbounded dense strict total order, which | |
| 21 // mean for any Ordinal<T>s a, b and c: | |
| 22 // | |
| 23 // - a < b and b < c implies a < c (transitivity); | |
| 24 // - exactly one of a < b, b < a and a = b holds (trichotomy); | |
| 25 // - if a < b, there is a Ordinal<T> x such that a < x < b (density); | |
| 26 // - there are Ordinals<T> x and y such that x < a < y (unboundedness). | |
| 27 // | |
| 28 // This means that when Ordinal<T> is used for sorting a list, if any | |
| 29 // item changes its position in the list, only its Ordinal<T> value | |
| 30 // has to change to represent the new order, and all the other values | |
| 31 // can stay the same. | |
| 32 // | |
| 33 // An Ordinal<T> is internally represented as an array of bytes, so it | |
| 34 // can be serialized to and deserialized from disk. | |
| 35 // | |
| 36 // The Traits class should look like the following: | |
| 37 // | |
| 38 // // Don't forget to #include <stdint.h> and <stddef.h>. | |
| 39 // struct MyOrdinalTraits { | |
| 40 // // There must be at least two distinct values greater than kZeroDigit | |
| 41 // // and less than kMaxDigit. | |
| 42 // static const uint8_t kZeroDigit = '0'; | |
| 43 // static const uint8_t kMaxDigit = '9'; | |
| 44 // // kMinLength must be positive. | |
| 45 // static const size_t kMinLength = 1; | |
| 46 // }; | |
| 47 // | |
| 48 // An Ordinal<T> is valid iff its corresponding string has at least | |
| 49 // kMinLength characters, does not contain any characters less than | |
| 50 // kZeroDigit or greater than kMaxDigit, is not all zero digits, and | |
| 51 // does not have any unnecessary trailing zero digits. | |
| 52 // | |
| 53 // Note that even if the native char type is signed, strings still | |
| 54 // compare as if their they are unsigned. (This is explicitly in | |
| 55 // C++11 but not in C++98, even though all implementations do so | |
| 56 // anyway in practice.) Thus, it is safe to use any byte range for | |
| 57 // Ordinal<T>s. | |
| 58 template <typename Traits> | |
| 59 class Ordinal { | |
| 60 public: | |
| 61 // Functors for use with STL algorithms and containers. | |
| 62 class LessThanFn { | |
| 63 public: | |
| 64 LessThanFn(); | |
| 65 | |
| 66 bool operator()(const Ordinal<Traits>& lhs, | |
| 67 const Ordinal<Traits>& rhs) const; | |
| 68 }; | |
| 69 | |
| 70 class EqualsFn { | |
| 71 public: | |
| 72 EqualsFn(); | |
| 73 | |
| 74 bool operator()(const Ordinal<Traits>& lhs, | |
| 75 const Ordinal<Traits>& rhs) const; | |
| 76 }; | |
| 77 | |
| 78 // Creates an Ordinal from the given string of bytes. The Ordinal | |
| 79 // may be valid or invalid. | |
| 80 explicit Ordinal(const std::string& bytes); | |
| 81 | |
| 82 // Creates an invalid Ordinal. | |
| 83 Ordinal(); | |
| 84 | |
| 85 // Creates a valid initial Ordinal. This is called to create the first | |
| 86 // element of Ordinal list (i.e. before we have any other values we can | |
| 87 // generate from). | |
| 88 static Ordinal CreateInitialOrdinal(); | |
| 89 | |
| 90 // Returns true iff this Ordinal is valid. This takes constant | |
| 91 // time. | |
| 92 bool IsValid() const; | |
| 93 | |
| 94 // Returns true iff |*this| == |other| or |*this| and |other| | |
| 95 // are both invalid. | |
| 96 bool EqualsOrBothInvalid(const Ordinal& other) const; | |
| 97 | |
| 98 // Returns a printable string representation of the Ordinal suitable | |
| 99 // for logging. | |
| 100 std::string ToDebugString() const; | |
| 101 | |
| 102 // All remaining functions can only be called if IsValid() holds. | |
| 103 // It is an error to call them if IsValid() is false. | |
| 104 | |
| 105 // Order-related functions. | |
| 106 | |
| 107 // Returns true iff |*this| < |other|. | |
| 108 bool LessThan(const Ordinal& other) const; | |
| 109 | |
| 110 // Returns true iff |*this| > |other|. | |
| 111 bool GreaterThan(const Ordinal& other) const; | |
| 112 | |
| 113 // Returns true iff |*this| == |other| (i.e. |*this| < |other| and | |
| 114 // |other| < |*this| are both false). | |
| 115 bool Equals(const Ordinal& other) const; | |
| 116 | |
| 117 // Given |*this| != |other|, returns a Ordinal x such that | |
| 118 // min(|*this|, |other|) < x < max(|*this|, |other|). It is an error | |
| 119 // to call this function when |*this| == |other|. | |
| 120 Ordinal CreateBetween(const Ordinal& other) const; | |
| 121 | |
| 122 // Returns a Ordinal |x| such that |x| < |*this|. | |
| 123 Ordinal CreateBefore() const; | |
| 124 | |
| 125 // Returns a Ordinal |x| such that |*this| < |x|. | |
| 126 Ordinal CreateAfter() const; | |
| 127 | |
| 128 // Returns the string of bytes representing the Ordinal. It is | |
| 129 // guaranteed that an Ordinal constructed from the returned string | |
| 130 // will be valid. | |
| 131 std::string ToInternalValue() const; | |
| 132 | |
| 133 // Use of copy constructor and default assignment for this class is allowed. | |
| 134 | |
| 135 // Constants for Ordinal digits. | |
| 136 static const uint8_t kZeroDigit = Traits::kZeroDigit; | |
| 137 static const uint8_t kMaxDigit = Traits::kMaxDigit; | |
| 138 static const size_t kMinLength = Traits::kMinLength; | |
| 139 static const uint8_t kOneDigit = kZeroDigit + 1; | |
| 140 static const uint8_t kMidDigit = kOneDigit + (kMaxDigit - kOneDigit) / 2; | |
| 141 static const unsigned int kMidDigitValue = kMidDigit - kZeroDigit; | |
| 142 static const unsigned int kMaxDigitValue = kMaxDigit - kZeroDigit; | |
| 143 static const unsigned int kRadix = kMaxDigitValue + 1; | |
| 144 | |
| 145 static_assert(kOneDigit > kZeroDigit, "incorrect ordinal one digit"); | |
| 146 static_assert(kMidDigit > kOneDigit, "incorrect ordinal mid digit"); | |
| 147 static_assert(kMaxDigit > kMidDigit, "incorrect ordinal max digit"); | |
| 148 static_assert(kMinLength > 0, "incorrect ordinal min length"); | |
| 149 static_assert(kMidDigitValue > 1, "incorrect ordinal mid digit"); | |
| 150 static_assert(kMaxDigitValue > kMidDigitValue, "incorrect ordinal max digit"); | |
| 151 static_assert(kRadix == kMaxDigitValue + 1, "incorrect ordinal radix"); | |
| 152 | |
| 153 private: | |
| 154 // Returns true iff the given byte string satisfies the criteria for | |
| 155 // a valid Ordinal. | |
| 156 static bool IsValidOrdinalBytes(const std::string& bytes); | |
| 157 | |
| 158 // Returns the length that bytes.substr(0, length) would be with | |
| 159 // trailing zero digits removed. | |
| 160 static size_t GetLengthWithoutTrailingZeroDigits( | |
| 161 const std::string& bytes, | |
| 162 size_t length); | |
| 163 | |
| 164 // Returns the digit at position i, padding with zero digits if | |
| 165 // required. | |
| 166 static uint8_t GetDigit(const std::string& bytes, size_t i); | |
| 167 | |
| 168 // Returns the digit value at position i, padding with 0 if required. | |
| 169 static int GetDigitValue(const std::string& bytes, size_t i); | |
| 170 | |
| 171 // Adds the given value to |bytes| at position i, carrying when | |
| 172 // necessary. Returns the left-most carry. | |
| 173 static int AddDigitValue(std::string* bytes, size_t i, int digit_value); | |
| 174 | |
| 175 // Returns the proper length |bytes| should be resized to, i.e. the | |
| 176 // smallest length such that |bytes| is still greater than | |
| 177 // |lower_bound| and is still valid. |bytes| should be greater than | |
| 178 // |lower_bound|. | |
| 179 static size_t GetProperLength(const std::string& lower_bound, | |
| 180 const std::string& bytes); | |
| 181 | |
| 182 // Compute the midpoint ordinal byte string that is between |start| | |
| 183 // and |end|. | |
| 184 static std::string ComputeMidpoint(const std::string& start, | |
| 185 const std::string& end); | |
| 186 | |
| 187 // Create a Ordinal that is lexigraphically greater than |start| and | |
| 188 // lexigraphically less than |end|. The returned Ordinal will be roughly | |
| 189 // between |start| and |end|. | |
| 190 static Ordinal<Traits> CreateOrdinalBetween(const Ordinal<Traits>& start, | |
| 191 const Ordinal<Traits>& end); | |
| 192 | |
| 193 // The internal byte string representation of the Ordinal. Never | |
| 194 // changes after construction except for assignment. | |
| 195 std::string bytes_; | |
| 196 | |
| 197 // A cache of the result of IsValidOrdinalBytes(bytes_). | |
| 198 bool is_valid_; | |
| 199 }; | |
| 200 | |
| 201 template <typename Traits> | |
| 202 const uint8_t Ordinal<Traits>::kZeroDigit; | |
| 203 template <typename Traits> | |
| 204 const uint8_t Ordinal<Traits>::kMaxDigit; | |
| 205 template <typename Traits> const size_t Ordinal<Traits>::kMinLength; | |
| 206 template <typename Traits> | |
| 207 const uint8_t Ordinal<Traits>::kOneDigit; | |
| 208 template <typename Traits> | |
| 209 const uint8_t Ordinal<Traits>::kMidDigit; | |
| 210 template <typename Traits> const unsigned int Ordinal<Traits>::kMidDigitValue; | |
| 211 template <typename Traits> const unsigned int Ordinal<Traits>::kMaxDigitValue; | |
| 212 template <typename Traits> const unsigned int Ordinal<Traits>::kRadix; | |
| 213 | |
| 214 template <typename Traits> | |
| 215 Ordinal<Traits>::LessThanFn::LessThanFn() {} | |
| 216 | |
| 217 template <typename Traits> | |
| 218 bool Ordinal<Traits>::LessThanFn::operator()(const Ordinal<Traits>& lhs, | |
| 219 const Ordinal<Traits>& rhs) const { | |
| 220 return lhs.LessThan(rhs); | |
| 221 } | |
| 222 | |
| 223 template <typename Traits> | |
| 224 Ordinal<Traits>::EqualsFn::EqualsFn() {} | |
| 225 | |
| 226 template <typename Traits> | |
| 227 bool Ordinal<Traits>::EqualsFn::operator()(const Ordinal<Traits>& lhs, | |
| 228 const Ordinal<Traits>& rhs) const { | |
| 229 return lhs.Equals(rhs); | |
| 230 } | |
| 231 | |
| 232 template <typename Traits> | |
| 233 Ordinal<Traits>::Ordinal(const std::string& bytes) | |
| 234 : bytes_(bytes), | |
| 235 is_valid_(IsValidOrdinalBytes(bytes_)) {} | |
| 236 | |
| 237 template <typename Traits> | |
| 238 Ordinal<Traits>::Ordinal() : is_valid_(false) {} | |
| 239 | |
| 240 template <typename Traits> | |
| 241 Ordinal<Traits> Ordinal<Traits>::CreateInitialOrdinal() { | |
| 242 std::string bytes(Traits::kMinLength, kZeroDigit); | |
| 243 bytes[0] = kMidDigit; | |
| 244 return Ordinal(bytes); | |
| 245 } | |
| 246 | |
| 247 template <typename Traits> | |
| 248 bool Ordinal<Traits>::IsValid() const { | |
| 249 DCHECK_EQ(IsValidOrdinalBytes(bytes_), is_valid_); | |
| 250 return is_valid_; | |
| 251 } | |
| 252 | |
| 253 template <typename Traits> | |
| 254 bool Ordinal<Traits>::EqualsOrBothInvalid(const Ordinal& other) const { | |
| 255 if (!IsValid() && !other.IsValid()) | |
| 256 return true; | |
| 257 | |
| 258 if (!IsValid() || !other.IsValid()) | |
| 259 return false; | |
| 260 | |
| 261 return Equals(other); | |
| 262 } | |
| 263 | |
| 264 template <typename Traits> | |
| 265 std::string Ordinal<Traits>::ToDebugString() const { | |
| 266 std::string debug_string = | |
| 267 base::EscapeBytesAsInvalidJSONString(bytes_, false /* put_in_quotes */); | |
| 268 if (!is_valid_) { | |
| 269 debug_string = "INVALID[" + debug_string + "]"; | |
| 270 } | |
| 271 return debug_string; | |
| 272 } | |
| 273 | |
| 274 template <typename Traits> | |
| 275 bool Ordinal<Traits>::LessThan(const Ordinal& other) const { | |
| 276 CHECK(IsValid()); | |
| 277 CHECK(other.IsValid()); | |
| 278 return bytes_ < other.bytes_; | |
| 279 } | |
| 280 | |
| 281 template <typename Traits> | |
| 282 bool Ordinal<Traits>::GreaterThan(const Ordinal& other) const { | |
| 283 CHECK(IsValid()); | |
| 284 CHECK(other.IsValid()); | |
| 285 return bytes_ > other.bytes_; | |
| 286 } | |
| 287 | |
| 288 template <typename Traits> | |
| 289 bool Ordinal<Traits>::Equals(const Ordinal& other) const { | |
| 290 CHECK(IsValid()); | |
| 291 CHECK(other.IsValid()); | |
| 292 return bytes_ == other.bytes_; | |
| 293 } | |
| 294 | |
| 295 template <typename Traits> | |
| 296 Ordinal<Traits> Ordinal<Traits>::CreateBetween(const Ordinal& other) const { | |
| 297 CHECK(IsValid()); | |
| 298 CHECK(other.IsValid()); | |
| 299 CHECK(!Equals(other)); | |
| 300 | |
| 301 if (LessThan(other)) { | |
| 302 return CreateOrdinalBetween(*this, other); | |
| 303 } else { | |
| 304 return CreateOrdinalBetween(other, *this); | |
| 305 } | |
| 306 } | |
| 307 | |
| 308 template <typename Traits> | |
| 309 Ordinal<Traits> Ordinal<Traits>::CreateBefore() const { | |
| 310 CHECK(IsValid()); | |
| 311 // Create the smallest valid Ordinal of the appropriate length | |
| 312 // to be the minimum boundary. | |
| 313 const size_t length = bytes_.length(); | |
| 314 std::string start(length, kZeroDigit); | |
| 315 start[length - 1] = kOneDigit; | |
| 316 if (start == bytes_) { | |
| 317 start[length - 1] = kZeroDigit; | |
| 318 start += kOneDigit; | |
| 319 } | |
| 320 | |
| 321 // Even though |start| is already a valid Ordinal that is less | |
| 322 // than |*this|, we don't return it because we wouldn't have much space in | |
| 323 // front of it to insert potential future values. | |
| 324 return CreateBetween(Ordinal(start)); | |
| 325 } | |
| 326 | |
| 327 template <typename Traits> | |
| 328 Ordinal<Traits> Ordinal<Traits>::CreateAfter() const { | |
| 329 CHECK(IsValid()); | |
| 330 // Create the largest valid Ordinal of the appropriate length to be | |
| 331 // the maximum boundary. | |
| 332 std::string end(bytes_.length(), kMaxDigit); | |
| 333 if (end == bytes_) | |
| 334 end += kMaxDigit; | |
| 335 | |
| 336 // Even though |end| is already a valid Ordinal that is greater than | |
| 337 // |*this|, we don't return it because we wouldn't have much space after | |
| 338 // it to insert potential future values. | |
| 339 return CreateBetween(Ordinal(end)); | |
| 340 } | |
| 341 | |
| 342 template <typename Traits> | |
| 343 std::string Ordinal<Traits>::ToInternalValue() const { | |
| 344 CHECK(IsValid()); | |
| 345 return bytes_; | |
| 346 } | |
| 347 | |
| 348 template <typename Traits> | |
| 349 bool Ordinal<Traits>::IsValidOrdinalBytes(const std::string& bytes) { | |
| 350 const size_t length = bytes.length(); | |
| 351 if (length < kMinLength) | |
| 352 return false; | |
| 353 | |
| 354 bool found_non_zero = false; | |
| 355 for (size_t i = 0; i < length; ++i) { | |
| 356 const uint8_t byte = bytes[i]; | |
| 357 if (byte < kZeroDigit || byte > kMaxDigit) | |
| 358 return false; | |
| 359 if (byte > kZeroDigit) | |
| 360 found_non_zero = true; | |
| 361 } | |
| 362 if (!found_non_zero) | |
| 363 return false; | |
| 364 | |
| 365 if (length > kMinLength) { | |
| 366 const uint8_t last_byte = bytes[length - 1]; | |
| 367 if (last_byte == kZeroDigit) | |
| 368 return false; | |
| 369 } | |
| 370 | |
| 371 return true; | |
| 372 } | |
| 373 | |
| 374 template <typename Traits> | |
| 375 size_t Ordinal<Traits>::GetLengthWithoutTrailingZeroDigits( | |
| 376 const std::string& bytes, size_t length) { | |
| 377 DCHECK(!bytes.empty()); | |
| 378 DCHECK_GT(length, 0U); | |
| 379 | |
| 380 size_t end_position = | |
| 381 bytes.find_last_not_of(static_cast<char>(kZeroDigit), length - 1); | |
| 382 | |
| 383 // If no non kZeroDigit is found then the string is a string of all zeros | |
| 384 // digits so we return 0 as the correct length. | |
| 385 if (end_position == std::string::npos) | |
| 386 return 0; | |
| 387 | |
| 388 return end_position + 1; | |
| 389 } | |
| 390 | |
| 391 template <typename Traits> | |
| 392 uint8_t Ordinal<Traits>::GetDigit(const std::string& bytes, size_t i) { | |
| 393 return (i < bytes.length()) ? bytes[i] : kZeroDigit; | |
| 394 } | |
| 395 | |
| 396 template <typename Traits> | |
| 397 int Ordinal<Traits>::GetDigitValue(const std::string& bytes, size_t i) { | |
| 398 return GetDigit(bytes, i) - kZeroDigit; | |
| 399 } | |
| 400 | |
| 401 template <typename Traits> | |
| 402 int Ordinal<Traits>::AddDigitValue(std::string* bytes, | |
| 403 size_t i, int digit_value) { | |
| 404 DCHECK_GE(i, 0U); | |
| 405 DCHECK_LT(i, bytes->length()); | |
| 406 | |
| 407 for (int j = static_cast<int>(i); j >= 0 && digit_value > 0; --j) { | |
| 408 int byte_j_value = GetDigitValue(*bytes, j) + digit_value; | |
| 409 digit_value = byte_j_value / kRadix; | |
| 410 DCHECK_LE(digit_value, 1); | |
| 411 byte_j_value %= kRadix; | |
| 412 (*bytes)[j] = static_cast<char>(kZeroDigit + byte_j_value); | |
| 413 } | |
| 414 return digit_value; | |
| 415 } | |
| 416 | |
| 417 template <typename Traits> | |
| 418 size_t Ordinal<Traits>::GetProperLength(const std::string& lower_bound, | |
| 419 const std::string& bytes) { | |
| 420 CHECK_GT(bytes, lower_bound); | |
| 421 | |
| 422 size_t drop_length = | |
| 423 GetLengthWithoutTrailingZeroDigits(bytes, bytes.length()); | |
| 424 // See if the |ordinal| can be truncated after its last non-zero | |
| 425 // digit without affecting the ordering. | |
| 426 if (drop_length > kMinLength) { | |
| 427 size_t truncated_length = | |
| 428 GetLengthWithoutTrailingZeroDigits(bytes, drop_length - 1); | |
| 429 | |
| 430 if (truncated_length > 0 && | |
| 431 bytes.compare(0, truncated_length, lower_bound) > 0) | |
| 432 drop_length = truncated_length; | |
| 433 } | |
| 434 return std::max(drop_length, kMinLength); | |
| 435 } | |
| 436 | |
| 437 template <typename Traits> | |
| 438 std::string Ordinal<Traits>::ComputeMidpoint( | |
| 439 const std::string& start, | |
| 440 const std::string& end) { | |
| 441 size_t max_size = std::max(start.length(), end.length()) + 1; | |
| 442 std::string midpoint(max_size, kZeroDigit); | |
| 443 | |
| 444 // Perform the operation (start + end) / 2 left-to-right by | |
| 445 // maintaining a "forward carry" which is either 0 or | |
| 446 // kMidDigitValue. AddDigitValue() is in general O(n), but this | |
| 447 // operation is still O(n) despite that; calls to AddDigitValue() | |
| 448 // will overflow at most to the last position where AddDigitValue() | |
| 449 // last overflowed. | |
| 450 int forward_carry = 0; | |
| 451 for (size_t i = 0; i < max_size; ++i) { | |
| 452 const int sum_value = GetDigitValue(start, i) + GetDigitValue(end, i); | |
| 453 const int digit_value = sum_value / 2 + forward_carry; | |
| 454 // AddDigitValue returning a non-zero carry would imply that | |
| 455 // midpoint[0] >= kMaxDigit, which one can show is impossible. | |
| 456 CHECK_EQ(AddDigitValue(&midpoint, i, digit_value), 0); | |
| 457 forward_carry = (sum_value % 2 == 1) ? kMidDigitValue : 0; | |
| 458 } | |
| 459 DCHECK_EQ(forward_carry, 0); | |
| 460 | |
| 461 return midpoint; | |
| 462 } | |
| 463 | |
| 464 template <typename Traits> | |
| 465 Ordinal<Traits> Ordinal<Traits>::CreateOrdinalBetween( | |
| 466 const Ordinal<Traits>& start, | |
| 467 const Ordinal<Traits>& end) { | |
| 468 CHECK(start.IsValid()); | |
| 469 CHECK(end.IsValid()); | |
| 470 CHECK(start.LessThan(end)); | |
| 471 const std::string& start_bytes = start.ToInternalValue(); | |
| 472 const std::string& end_bytes = end.ToInternalValue(); | |
| 473 DCHECK_LT(start_bytes, end_bytes); | |
| 474 | |
| 475 std::string midpoint = ComputeMidpoint(start_bytes, end_bytes); | |
| 476 const size_t proper_length = GetProperLength(start_bytes, midpoint); | |
| 477 midpoint.resize(proper_length, kZeroDigit); | |
| 478 | |
| 479 DCHECK_GT(midpoint, start_bytes); | |
| 480 DCHECK_LT(midpoint, end_bytes); | |
| 481 | |
| 482 Ordinal<Traits> midpoint_ordinal(midpoint); | |
| 483 DCHECK(midpoint_ordinal.IsValid()); | |
| 484 return midpoint_ordinal; | |
| 485 } | |
| 486 | |
| 487 } // namespace syncer | |
| 488 | |
| 489 #endif // SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2130453004:
[Sync] Move //sync to //components/sync. (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master