sync/internal_api/public/base/ordinal.h

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