string_ordinal.cc 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278
  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. #include "components/sync/model/string_ordinal.h"
  5. #include <algorithm>
  6. #include "base/check.h"
  7. #include "base/check_op.h"
  8. #include "base/json/string_escape.h"
  9. namespace syncer {
  10. const uint8_t StringOrdinal::kZeroDigit;
  11. const uint8_t StringOrdinal::kMaxDigit;
  12. const size_t StringOrdinal::kMinLength;
  13. const uint8_t StringOrdinal::kOneDigit;
  14. const uint8_t StringOrdinal::kMidDigit;
  15. const unsigned int StringOrdinal::kMidDigitValue;
  16. const unsigned int StringOrdinal::kMaxDigitValue;
  17. const unsigned int StringOrdinal::kRadix;
  18. StringOrdinal::LessThanFn::LessThanFn() = default;
  19. bool StringOrdinal::LessThanFn::operator()(const StringOrdinal& lhs,
  20. const StringOrdinal& rhs) const {
  21. return lhs.LessThan(rhs);
  22. }
  23. StringOrdinal::EqualsFn::EqualsFn() = default;
  24. bool StringOrdinal::EqualsFn::operator()(const StringOrdinal& lhs,
  25. const StringOrdinal& rhs) const {
  26. return lhs.Equals(rhs);
  27. }
  28. bool operator==(const StringOrdinal& lhs, const StringOrdinal& rhs) {
  29. return lhs.EqualsOrBothInvalid(rhs);
  30. }
  31. bool operator!=(const StringOrdinal& lhs, const StringOrdinal& rhs) {
  32. return !(lhs == rhs);
  33. }
  34. StringOrdinal::StringOrdinal(const std::string& bytes)
  35. : bytes_(bytes), is_valid_(IsValidOrdinalBytes(bytes_)) {}
  36. StringOrdinal::StringOrdinal() : is_valid_(false) {}
  37. StringOrdinal StringOrdinal::CreateInitialOrdinal() {
  38. std::string bytes(kMinLength, kZeroDigit);
  39. bytes[0] = kMidDigit;
  40. return StringOrdinal(bytes);
  41. }
  42. bool StringOrdinal::IsValid() const {
  43. DCHECK_EQ(IsValidOrdinalBytes(bytes_), is_valid_);
  44. return is_valid_;
  45. }
  46. bool StringOrdinal::EqualsOrBothInvalid(const StringOrdinal& other) const {
  47. if (!IsValid() && !other.IsValid())
  48. return true;
  49. if (!IsValid() || !other.IsValid())
  50. return false;
  51. return Equals(other);
  52. }
  53. std::string StringOrdinal::ToDebugString() const {
  54. std::string debug_string =
  55. base::EscapeBytesAsInvalidJSONString(bytes_, false /* put_in_quotes */);
  56. if (!is_valid_) {
  57. debug_string = "INVALID[" + debug_string + "]";
  58. }
  59. return debug_string;
  60. }
  61. bool StringOrdinal::LessThan(const StringOrdinal& other) const {
  62. CHECK(IsValid());
  63. CHECK(other.IsValid());
  64. return bytes_ < other.bytes_;
  65. }
  66. bool StringOrdinal::GreaterThan(const StringOrdinal& other) const {
  67. CHECK(IsValid());
  68. CHECK(other.IsValid());
  69. return bytes_ > other.bytes_;
  70. }
  71. bool StringOrdinal::Equals(const StringOrdinal& other) const {
  72. CHECK(IsValid());
  73. CHECK(other.IsValid());
  74. return bytes_ == other.bytes_;
  75. }
  76. StringOrdinal StringOrdinal::CreateBetween(const StringOrdinal& other) const {
  77. CHECK(IsValid());
  78. CHECK(other.IsValid());
  79. CHECK(!Equals(other));
  80. if (LessThan(other)) {
  81. return CreateOrdinalBetween(*this, other);
  82. } else {
  83. return CreateOrdinalBetween(other, *this);
  84. }
  85. }
  86. StringOrdinal StringOrdinal::CreateBefore() const {
  87. CHECK(IsValid());
  88. // Create the smallest valid StringOrdinal of the appropriate length
  89. // to be the minimum boundary.
  90. const size_t length = bytes_.length();
  91. std::string start(length, kZeroDigit);
  92. start[length - 1] = kOneDigit;
  93. if (start == bytes_) {
  94. start[length - 1] = kZeroDigit;
  95. start += kOneDigit;
  96. }
  97. // Even though |start| is already a valid StringOrdinal that is less
  98. // than |*this|, we don't return it because we wouldn't have much space in
  99. // front of it to insert potential future values.
  100. return CreateBetween(StringOrdinal(start));
  101. }
  102. StringOrdinal StringOrdinal::CreateAfter() const {
  103. CHECK(IsValid());
  104. // Create the largest valid StringOrdinal of the appropriate length to be
  105. // the maximum boundary.
  106. std::string end(bytes_.length(), kMaxDigit);
  107. if (end == bytes_)
  108. end += kMaxDigit;
  109. // Even though |end| is already a valid StringOrdinal that is greater than
  110. // |*this|, we don't return it because we wouldn't have much space after
  111. // it to insert potential future values.
  112. return CreateBetween(StringOrdinal(end));
  113. }
  114. std::string StringOrdinal::ToInternalValue() const {
  115. CHECK(IsValid());
  116. return bytes_;
  117. }
  118. bool StringOrdinal::IsValidOrdinalBytes(const std::string& bytes) {
  119. const size_t length = bytes.length();
  120. if (length < kMinLength)
  121. return false;
  122. bool found_non_zero = false;
  123. for (size_t i = 0; i < length; ++i) {
  124. const uint8_t byte = bytes[i];
  125. if (byte < kZeroDigit || byte > kMaxDigit)
  126. return false;
  127. if (byte > kZeroDigit)
  128. found_non_zero = true;
  129. }
  130. if (!found_non_zero)
  131. return false;
  132. if (length > kMinLength) {
  133. const uint8_t last_byte = bytes[length - 1];
  134. if (last_byte == kZeroDigit)
  135. return false;
  136. }
  137. return true;
  138. }
  139. size_t StringOrdinal::GetLengthWithoutTrailingZeroDigits(
  140. const std::string& bytes,
  141. size_t length) {
  142. DCHECK(!bytes.empty());
  143. DCHECK_GT(length, 0U);
  144. size_t end_position =
  145. bytes.find_last_not_of(static_cast<char>(kZeroDigit), length - 1);
  146. // If no non kZeroDigit is found then the string is a string of all zeros
  147. // digits so we return 0 as the correct length.
  148. if (end_position == std::string::npos)
  149. return 0;
  150. return end_position + 1;
  151. }
  152. uint8_t StringOrdinal::GetDigit(const std::string& bytes, size_t i) {
  153. return (i < bytes.length()) ? bytes[i] : kZeroDigit;
  154. }
  155. int StringOrdinal::GetDigitValue(const std::string& bytes, size_t i) {
  156. return GetDigit(bytes, i) - kZeroDigit;
  157. }
  158. int StringOrdinal::AddDigitValue(std::string* bytes,
  159. size_t i,
  160. int digit_value) {
  161. DCHECK_LT(i, bytes->length());
  162. for (int j = static_cast<int>(i); j >= 0 && digit_value > 0; --j) {
  163. int byte_j_value = GetDigitValue(*bytes, j) + digit_value;
  164. digit_value = byte_j_value / kRadix;
  165. DCHECK_LE(digit_value, 1);
  166. byte_j_value %= kRadix;
  167. (*bytes)[j] = static_cast<char>(kZeroDigit + byte_j_value);
  168. }
  169. return digit_value;
  170. }
  171. size_t StringOrdinal::GetProperLength(const std::string& lower_bound,
  172. const std::string& bytes) {
  173. CHECK_GT(bytes, lower_bound);
  174. size_t drop_length =
  175. GetLengthWithoutTrailingZeroDigits(bytes, bytes.length());
  176. // See if the |ordinal| can be truncated after its last non-zero
  177. // digit without affecting the ordering.
  178. if (drop_length > kMinLength) {
  179. size_t truncated_length =
  180. GetLengthWithoutTrailingZeroDigits(bytes, drop_length - 1);
  181. if (truncated_length > 0 &&
  182. bytes.compare(0, truncated_length, lower_bound) > 0)
  183. drop_length = truncated_length;
  184. }
  185. return std::max(drop_length, kMinLength);
  186. }
  187. std::string StringOrdinal::ComputeMidpoint(const std::string& start,
  188. const std::string& end) {
  189. size_t max_size = std::max(start.length(), end.length()) + 1;
  190. std::string midpoint(max_size, kZeroDigit);
  191. // Perform the operation (start + end) / 2 left-to-right by
  192. // maintaining a "forward carry" which is either 0 or
  193. // kMidDigitValue. AddDigitValue() is in general O(n), but this
  194. // operation is still O(n) despite that; calls to AddDigitValue()
  195. // will overflow at most to the last position where AddDigitValue()
  196. // last overflowed.
  197. int forward_carry = 0;
  198. for (size_t i = 0; i < max_size; ++i) {
  199. const int sum_value = GetDigitValue(start, i) + GetDigitValue(end, i);
  200. const int digit_value = sum_value / 2 + forward_carry;
  201. // AddDigitValue returning a non-zero carry would imply that
  202. // midpoint[0] >= kMaxDigit, which one can show is impossible.
  203. CHECK_EQ(AddDigitValue(&midpoint, i, digit_value), 0);
  204. forward_carry = (sum_value % 2 == 1) ? kMidDigitValue : 0;
  205. }
  206. DCHECK_EQ(forward_carry, 0);
  207. return midpoint;
  208. }
  209. StringOrdinal StringOrdinal::CreateOrdinalBetween(const StringOrdinal& start,
  210. const StringOrdinal& end) {
  211. CHECK(start.IsValid());
  212. CHECK(end.IsValid());
  213. CHECK(start.LessThan(end));
  214. const std::string& start_bytes = start.ToInternalValue();
  215. const std::string& end_bytes = end.ToInternalValue();
  216. DCHECK_LT(start_bytes, end_bytes);
  217. std::string midpoint = ComputeMidpoint(start_bytes, end_bytes);
  218. const size_t proper_length = GetProperLength(start_bytes, midpoint);
  219. midpoint.resize(proper_length, kZeroDigit);
  220. DCHECK_GT(midpoint, start_bytes);
  221. DCHECK_LT(midpoint, end_bytes);
  222. StringOrdinal midpoint_ordinal(midpoint);
  223. DCHECK(midpoint_ordinal.IsValid());
  224. return midpoint_ordinal;
  225. }
  226. } // namespace syncer