123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278 |
- // Copyright (c) 2012 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "components/sync/model/string_ordinal.h"
- #include <algorithm>
- #include "base/check.h"
- #include "base/check_op.h"
- #include "base/json/string_escape.h"
- namespace syncer {
- const uint8_t StringOrdinal::kZeroDigit;
- const uint8_t StringOrdinal::kMaxDigit;
- const size_t StringOrdinal::kMinLength;
- const uint8_t StringOrdinal::kOneDigit;
- const uint8_t StringOrdinal::kMidDigit;
- const unsigned int StringOrdinal::kMidDigitValue;
- const unsigned int StringOrdinal::kMaxDigitValue;
- const unsigned int StringOrdinal::kRadix;
- StringOrdinal::LessThanFn::LessThanFn() = default;
- bool StringOrdinal::LessThanFn::operator()(const StringOrdinal& lhs,
- const StringOrdinal& rhs) const {
- return lhs.LessThan(rhs);
- }
- StringOrdinal::EqualsFn::EqualsFn() = default;
- bool StringOrdinal::EqualsFn::operator()(const StringOrdinal& lhs,
- const StringOrdinal& rhs) const {
- return lhs.Equals(rhs);
- }
- bool operator==(const StringOrdinal& lhs, const StringOrdinal& rhs) {
- return lhs.EqualsOrBothInvalid(rhs);
- }
- bool operator!=(const StringOrdinal& lhs, const StringOrdinal& rhs) {
- return !(lhs == rhs);
- }
- StringOrdinal::StringOrdinal(const std::string& bytes)
- : bytes_(bytes), is_valid_(IsValidOrdinalBytes(bytes_)) {}
- StringOrdinal::StringOrdinal() : is_valid_(false) {}
- StringOrdinal StringOrdinal::CreateInitialOrdinal() {
- std::string bytes(kMinLength, kZeroDigit);
- bytes[0] = kMidDigit;
- return StringOrdinal(bytes);
- }
- bool StringOrdinal::IsValid() const {
- DCHECK_EQ(IsValidOrdinalBytes(bytes_), is_valid_);
- return is_valid_;
- }
- bool StringOrdinal::EqualsOrBothInvalid(const StringOrdinal& other) const {
- if (!IsValid() && !other.IsValid())
- return true;
- if (!IsValid() || !other.IsValid())
- return false;
- return Equals(other);
- }
- std::string StringOrdinal::ToDebugString() const {
- std::string debug_string =
- base::EscapeBytesAsInvalidJSONString(bytes_, false /* put_in_quotes */);
- if (!is_valid_) {
- debug_string = "INVALID[" + debug_string + "]";
- }
- return debug_string;
- }
- bool StringOrdinal::LessThan(const StringOrdinal& other) const {
- CHECK(IsValid());
- CHECK(other.IsValid());
- return bytes_ < other.bytes_;
- }
- bool StringOrdinal::GreaterThan(const StringOrdinal& other) const {
- CHECK(IsValid());
- CHECK(other.IsValid());
- return bytes_ > other.bytes_;
- }
- bool StringOrdinal::Equals(const StringOrdinal& other) const {
- CHECK(IsValid());
- CHECK(other.IsValid());
- return bytes_ == other.bytes_;
- }
- StringOrdinal StringOrdinal::CreateBetween(const StringOrdinal& other) const {
- CHECK(IsValid());
- CHECK(other.IsValid());
- CHECK(!Equals(other));
- if (LessThan(other)) {
- return CreateOrdinalBetween(*this, other);
- } else {
- return CreateOrdinalBetween(other, *this);
- }
- }
- StringOrdinal StringOrdinal::CreateBefore() const {
- CHECK(IsValid());
- // Create the smallest valid StringOrdinal of the appropriate length
- // to be the minimum boundary.
- const size_t length = bytes_.length();
- std::string start(length, kZeroDigit);
- start[length - 1] = kOneDigit;
- if (start == bytes_) {
- start[length - 1] = kZeroDigit;
- start += kOneDigit;
- }
- // Even though |start| is already a valid StringOrdinal that is less
- // than |*this|, we don't return it because we wouldn't have much space in
- // front of it to insert potential future values.
- return CreateBetween(StringOrdinal(start));
- }
- StringOrdinal StringOrdinal::CreateAfter() const {
- CHECK(IsValid());
- // Create the largest valid StringOrdinal of the appropriate length to be
- // the maximum boundary.
- std::string end(bytes_.length(), kMaxDigit);
- if (end == bytes_)
- end += kMaxDigit;
- // Even though |end| is already a valid StringOrdinal that is greater than
- // |*this|, we don't return it because we wouldn't have much space after
- // it to insert potential future values.
- return CreateBetween(StringOrdinal(end));
- }
- std::string StringOrdinal::ToInternalValue() const {
- CHECK(IsValid());
- return bytes_;
- }
- bool StringOrdinal::IsValidOrdinalBytes(const std::string& bytes) {
- const size_t length = bytes.length();
- if (length < kMinLength)
- return false;
- bool found_non_zero = false;
- for (size_t i = 0; i < length; ++i) {
- const uint8_t byte = bytes[i];
- if (byte < kZeroDigit || byte > kMaxDigit)
- return false;
- if (byte > kZeroDigit)
- found_non_zero = true;
- }
- if (!found_non_zero)
- return false;
- if (length > kMinLength) {
- const uint8_t last_byte = bytes[length - 1];
- if (last_byte == kZeroDigit)
- return false;
- }
- return true;
- }
- size_t StringOrdinal::GetLengthWithoutTrailingZeroDigits(
- const std::string& bytes,
- size_t length) {
- DCHECK(!bytes.empty());
- DCHECK_GT(length, 0U);
- size_t end_position =
- bytes.find_last_not_of(static_cast<char>(kZeroDigit), length - 1);
- // If no non kZeroDigit is found then the string is a string of all zeros
- // digits so we return 0 as the correct length.
- if (end_position == std::string::npos)
- return 0;
- return end_position + 1;
- }
- uint8_t StringOrdinal::GetDigit(const std::string& bytes, size_t i) {
- return (i < bytes.length()) ? bytes[i] : kZeroDigit;
- }
- int StringOrdinal::GetDigitValue(const std::string& bytes, size_t i) {
- return GetDigit(bytes, i) - kZeroDigit;
- }
- int StringOrdinal::AddDigitValue(std::string* bytes,
- size_t i,
- int digit_value) {
- DCHECK_LT(i, bytes->length());
- for (int j = static_cast<int>(i); j >= 0 && digit_value > 0; --j) {
- int byte_j_value = GetDigitValue(*bytes, j) + digit_value;
- digit_value = byte_j_value / kRadix;
- DCHECK_LE(digit_value, 1);
- byte_j_value %= kRadix;
- (*bytes)[j] = static_cast<char>(kZeroDigit + byte_j_value);
- }
- return digit_value;
- }
- size_t StringOrdinal::GetProperLength(const std::string& lower_bound,
- const std::string& bytes) {
- CHECK_GT(bytes, lower_bound);
- size_t drop_length =
- GetLengthWithoutTrailingZeroDigits(bytes, bytes.length());
- // See if the |ordinal| can be truncated after its last non-zero
- // digit without affecting the ordering.
- if (drop_length > kMinLength) {
- size_t truncated_length =
- GetLengthWithoutTrailingZeroDigits(bytes, drop_length - 1);
- if (truncated_length > 0 &&
- bytes.compare(0, truncated_length, lower_bound) > 0)
- drop_length = truncated_length;
- }
- return std::max(drop_length, kMinLength);
- }
- std::string StringOrdinal::ComputeMidpoint(const std::string& start,
- const std::string& end) {
- size_t max_size = std::max(start.length(), end.length()) + 1;
- std::string midpoint(max_size, kZeroDigit);
- // Perform the operation (start + end) / 2 left-to-right by
- // maintaining a "forward carry" which is either 0 or
- // kMidDigitValue. AddDigitValue() is in general O(n), but this
- // operation is still O(n) despite that; calls to AddDigitValue()
- // will overflow at most to the last position where AddDigitValue()
- // last overflowed.
- int forward_carry = 0;
- for (size_t i = 0; i < max_size; ++i) {
- const int sum_value = GetDigitValue(start, i) + GetDigitValue(end, i);
- const int digit_value = sum_value / 2 + forward_carry;
- // AddDigitValue returning a non-zero carry would imply that
- // midpoint[0] >= kMaxDigit, which one can show is impossible.
- CHECK_EQ(AddDigitValue(&midpoint, i, digit_value), 0);
- forward_carry = (sum_value % 2 == 1) ? kMidDigitValue : 0;
- }
- DCHECK_EQ(forward_carry, 0);
- return midpoint;
- }
- StringOrdinal StringOrdinal::CreateOrdinalBetween(const StringOrdinal& start,
- const StringOrdinal& end) {
- CHECK(start.IsValid());
- CHECK(end.IsValid());
- CHECK(start.LessThan(end));
- const std::string& start_bytes = start.ToInternalValue();
- const std::string& end_bytes = end.ToInternalValue();
- DCHECK_LT(start_bytes, end_bytes);
- std::string midpoint = ComputeMidpoint(start_bytes, end_bytes);
- const size_t proper_length = GetProperLength(start_bytes, midpoint);
- midpoint.resize(proper_length, kZeroDigit);
- DCHECK_GT(midpoint, start_bytes);
- DCHECK_LT(midpoint, end_bytes);
- StringOrdinal midpoint_ordinal(midpoint);
- DCHECK(midpoint_ordinal.IsValid());
- return midpoint_ordinal;
- }
- } // namespace syncer
|