Home | History | Annotate | Download | only in base
      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   COMPILE_ASSERT(kOneDigit > kZeroDigit, OrdinalOneDigitGreaterThanMinDigit);
    145   COMPILE_ASSERT(kMidDigit > kOneDigit, OrdinalMidDigitGreaterThanOneDigit);
    146   COMPILE_ASSERT(kMaxDigit > kMidDigit, OrdinalMaxDigitGreaterThanMidDigit);
    147   COMPILE_ASSERT(kMinLength > 0, OrdinalMinLengthIsPositive);
    148   COMPILE_ASSERT(kMidDigitValue > 1, OrdinalMidDigitValueGreaterThanOne);
    149   COMPILE_ASSERT(kMaxDigitValue > kMidDigitValue,
    150                  OrdinalMaxDigitValueGreaterThanMidDigitValue);
    151   COMPILE_ASSERT(kRadix == kMaxDigitValue + 1,
    152                  OrdinalRadixIsMaxDigitValuePlusOne);
    153 
    154  private:
    155   // Returns true iff the given byte string satisfies the criteria for
    156   // a valid Ordinal.
    157   static bool IsValidOrdinalBytes(const std::string& bytes);
    158 
    159   // Returns the length that bytes.substr(0, length) would be with
    160   // trailing zero digits removed.
    161   static size_t GetLengthWithoutTrailingZeroDigits(
    162       const std::string& bytes,
    163       size_t length);
    164 
    165   // Returns the digit at position i, padding with zero digits if
    166   // required.
    167   static uint8 GetDigit(const std::string& bytes, size_t i);
    168 
    169   // Returns the digit value at position i, padding with 0 if required.
    170   static int GetDigitValue(const std::string& bytes, size_t i);
    171 
    172   // Adds the given value to |bytes| at position i, carrying when
    173   // necessary.  Returns the left-most carry.
    174   static int AddDigitValue(std::string* bytes, size_t i, int digit_value);
    175 
    176   // Returns the proper length |bytes| should be resized to, i.e. the
    177   // smallest length such that |bytes| is still greater than
    178   // |lower_bound| and is still valid.  |bytes| should be greater than
    179   // |lower_bound|.
    180   static size_t GetProperLength(const std::string& lower_bound,
    181                                 const std::string& bytes);
    182 
    183   // Compute the midpoint ordinal byte string that is between |start|
    184   // and |end|.
    185   static std::string ComputeMidpoint(const std::string& start,
    186                                      const std::string& end);
    187 
    188   // Create a Ordinal that is lexigraphically greater than |start| and
    189   // lexigraphically less than |end|. The returned Ordinal will be roughly
    190   // between |start| and |end|.
    191   static Ordinal<Traits> CreateOrdinalBetween(const Ordinal<Traits>& start,
    192                                               const Ordinal<Traits>& end);
    193 
    194   // The internal byte string representation of the Ordinal.  Never
    195   // changes after construction except for assignment.
    196   std::string bytes_;
    197 
    198   // A cache of the result of IsValidOrdinalBytes(bytes_).
    199   bool is_valid_;
    200 };
    201 
    202 template <typename Traits> const uint8 Ordinal<Traits>::kZeroDigit;
    203 template <typename Traits> const uint8 Ordinal<Traits>::kMaxDigit;
    204 template <typename Traits> const size_t Ordinal<Traits>::kMinLength;
    205 template <typename Traits> const uint8 Ordinal<Traits>::kOneDigit;
    206 template <typename Traits> const uint8 Ordinal<Traits>::kMidDigit;
    207 template <typename Traits> const unsigned int Ordinal<Traits>::kMidDigitValue;
    208 template <typename Traits> const unsigned int Ordinal<Traits>::kMaxDigitValue;
    209 template <typename Traits> const unsigned int Ordinal<Traits>::kRadix;
    210 
    211 template <typename Traits>
    212 Ordinal<Traits>::LessThanFn::LessThanFn() {}
    213 
    214 template <typename Traits>
    215 bool Ordinal<Traits>::LessThanFn::operator()(const Ordinal<Traits>& lhs,
    216                                              const Ordinal<Traits>& rhs) const {
    217   return lhs.LessThan(rhs);
    218 }
    219 
    220 template <typename Traits>
    221 Ordinal<Traits>::EqualsFn::EqualsFn() {}
    222 
    223 template <typename Traits>
    224 bool Ordinal<Traits>::EqualsFn::operator()(const Ordinal<Traits>& lhs,
    225                                            const Ordinal<Traits>& rhs) const {
    226   return lhs.Equals(rhs);
    227 }
    228 
    229 template <typename Traits>
    230 Ordinal<Traits>::Ordinal(const std::string& bytes)
    231     : bytes_(bytes),
    232       is_valid_(IsValidOrdinalBytes(bytes_)) {}
    233 
    234 template <typename Traits>
    235 Ordinal<Traits>::Ordinal() : is_valid_(false) {}
    236 
    237 template <typename Traits>
    238 Ordinal<Traits> Ordinal<Traits>::CreateInitialOrdinal() {
    239   std::string bytes(Traits::kMinLength, kZeroDigit);
    240   bytes[0] = kMidDigit;
    241   return Ordinal(bytes);
    242 }
    243 
    244 template <typename Traits>
    245 bool Ordinal<Traits>::IsValid() const {
    246   DCHECK_EQ(IsValidOrdinalBytes(bytes_), is_valid_);
    247   return is_valid_;
    248 }
    249 
    250 template <typename Traits>
    251 bool Ordinal<Traits>::EqualsOrBothInvalid(const Ordinal& other) const {
    252   if (!IsValid() && !other.IsValid())
    253     return true;
    254 
    255   if (!IsValid() || !other.IsValid())
    256     return false;
    257 
    258   return Equals(other);
    259 }
    260 
    261 template <typename Traits>
    262 std::string Ordinal<Traits>::ToDebugString() const {
    263   std::string debug_string;
    264   base::JsonDoubleQuote(bytes_, false /* put_in_quotes */, &debug_string);
    265   if (!is_valid_) {
    266     debug_string = "INVALID[" + debug_string + "]";
    267   }
    268   return debug_string;
    269 }
    270 
    271 template <typename Traits>
    272 bool Ordinal<Traits>::LessThan(const Ordinal& other) const {
    273   CHECK(IsValid());
    274   CHECK(other.IsValid());
    275   return bytes_ < other.bytes_;
    276 }
    277 
    278 template <typename Traits>
    279 bool Ordinal<Traits>::GreaterThan(const Ordinal& other) const {
    280   CHECK(IsValid());
    281   CHECK(other.IsValid());
    282   return bytes_ > other.bytes_;
    283 }
    284 
    285 template <typename Traits>
    286 bool Ordinal<Traits>::Equals(const Ordinal& other) const {
    287   CHECK(IsValid());
    288   CHECK(other.IsValid());
    289   return bytes_ == other.bytes_;
    290 }
    291 
    292 template <typename Traits>
    293 Ordinal<Traits> Ordinal<Traits>::CreateBetween(const Ordinal& other) const {
    294   CHECK(IsValid());
    295   CHECK(other.IsValid());
    296   CHECK(!Equals(other));
    297 
    298   if (LessThan(other)) {
    299     return CreateOrdinalBetween(*this, other);
    300   } else {
    301     return CreateOrdinalBetween(other, *this);
    302   }
    303 }
    304 
    305 template <typename Traits>
    306 Ordinal<Traits> Ordinal<Traits>::CreateBefore() const {
    307   CHECK(IsValid());
    308   // Create the smallest valid Ordinal of the appropriate length
    309   // to be the minimum boundary.
    310   const size_t length = bytes_.length();
    311   std::string start(length, kZeroDigit);
    312   start[length - 1] = kOneDigit;
    313   if (start == bytes_) {
    314     start[length - 1] = kZeroDigit;
    315     start += kOneDigit;
    316   }
    317 
    318   // Even though |start| is already a valid Ordinal that is less
    319   // than |*this|, we don't return it because we wouldn't have much space in
    320   // front of it to insert potential future values.
    321   return CreateBetween(Ordinal(start));
    322 }
    323 
    324 template <typename Traits>
    325 Ordinal<Traits> Ordinal<Traits>::CreateAfter() const {
    326   CHECK(IsValid());
    327   // Create the largest valid Ordinal of the appropriate length to be
    328   // the maximum boundary.
    329   std::string end(bytes_.length(), kMaxDigit);
    330   if (end == bytes_)
    331     end += kMaxDigit;
    332 
    333   // Even though |end| is already a valid Ordinal that is greater than
    334   // |*this|, we don't return it because we wouldn't have much space after
    335   // it to insert potential future values.
    336   return CreateBetween(Ordinal(end));
    337 }
    338 
    339 template <typename Traits>
    340 std::string Ordinal<Traits>::ToInternalValue() const {
    341   CHECK(IsValid());
    342   return bytes_;
    343 }
    344 
    345 template <typename Traits>
    346 bool Ordinal<Traits>::IsValidOrdinalBytes(const std::string& bytes) {
    347   const size_t length = bytes.length();
    348   if (length < kMinLength)
    349     return false;
    350 
    351   bool found_non_zero = false;
    352   for (size_t i = 0; i < length; ++i) {
    353     const uint8 byte = bytes[i];
    354     if (byte < kZeroDigit || byte > kMaxDigit)
    355       return false;
    356     if (byte > kZeroDigit)
    357       found_non_zero = true;
    358   }
    359   if (!found_non_zero)
    360     return false;
    361 
    362   if (length > kMinLength) {
    363     const uint8 last_byte = bytes[length - 1];
    364     if (last_byte == kZeroDigit)
    365       return false;
    366   }
    367 
    368   return true;
    369 }
    370 
    371 template <typename Traits>
    372 size_t Ordinal<Traits>::GetLengthWithoutTrailingZeroDigits(
    373     const std::string& bytes, size_t length) {
    374   DCHECK(!bytes.empty());
    375   DCHECK_GT(length, 0U);
    376 
    377   size_t end_position =
    378       bytes.find_last_not_of(static_cast<char>(kZeroDigit), length - 1);
    379 
    380   // If no non kZeroDigit is found then the string is a string of all zeros
    381   // digits so we return 0 as the correct length.
    382   if (end_position == std::string::npos)
    383     return 0;
    384 
    385   return end_position + 1;
    386 }
    387 
    388 template <typename Traits>
    389 uint8 Ordinal<Traits>::GetDigit(const std::string& bytes, size_t i) {
    390   return (i < bytes.length()) ? bytes[i] : kZeroDigit;
    391 }
    392 
    393 template <typename Traits>
    394 int Ordinal<Traits>::GetDigitValue(const std::string& bytes, size_t i) {
    395   return GetDigit(bytes, i) - kZeroDigit;
    396 }
    397 
    398 template <typename Traits>
    399 int Ordinal<Traits>::AddDigitValue(std::string* bytes,
    400                                    size_t i, int digit_value) {
    401   DCHECK_GE(i, 0U);
    402   DCHECK_LT(i, bytes->length());
    403 
    404   for (int j = i; j >= 0 && digit_value > 0; --j) {
    405     int byte_j_value = GetDigitValue(*bytes, j) + digit_value;
    406     digit_value = byte_j_value / kRadix;
    407     DCHECK_LE(digit_value, 1);
    408     byte_j_value %= kRadix;
    409     (*bytes)[j] = static_cast<char>(kZeroDigit + byte_j_value);
    410   }
    411   return digit_value;
    412 }
    413 
    414 template <typename Traits>
    415 size_t Ordinal<Traits>::GetProperLength(const std::string& lower_bound,
    416                                         const std::string& bytes) {
    417   CHECK_GT(bytes, lower_bound);
    418 
    419   size_t drop_length =
    420       GetLengthWithoutTrailingZeroDigits(bytes, bytes.length());
    421   // See if the |ordinal| can be truncated after its last non-zero
    422   // digit without affecting the ordering.
    423   if (drop_length > kMinLength) {
    424     size_t truncated_length =
    425         GetLengthWithoutTrailingZeroDigits(bytes, drop_length - 1);
    426 
    427     if (truncated_length > 0 &&
    428         bytes.compare(0, truncated_length, lower_bound) > 0)
    429       drop_length = truncated_length;
    430   }
    431   return std::max(drop_length, kMinLength);
    432 }
    433 
    434 template <typename Traits>
    435 std::string Ordinal<Traits>::ComputeMidpoint(
    436     const std::string& start,
    437     const std::string& end) {
    438   size_t max_size = std::max(start.length(), end.length()) + 1;
    439   std::string midpoint(max_size, kZeroDigit);
    440 
    441   // Perform the operation (start + end) / 2 left-to-right by
    442   // maintaining a "forward carry" which is either 0 or
    443   // kMidDigitValue.  AddDigitValue() is in general O(n), but this
    444   // operation is still O(n) despite that; calls to AddDigitValue()
    445   // will overflow at most to the last position where AddDigitValue()
    446   // last overflowed.
    447   int forward_carry = 0;
    448   for (size_t i = 0; i < max_size; ++i) {
    449     const int sum_value = GetDigitValue(start, i) + GetDigitValue(end, i);
    450     const int digit_value = sum_value / 2 + forward_carry;
    451     // AddDigitValue returning a non-zero carry would imply that
    452     // midpoint[0] >= kMaxDigit, which one can show is impossible.
    453     CHECK_EQ(AddDigitValue(&midpoint, i, digit_value), 0);
    454     forward_carry = (sum_value % 2 == 1) ? kMidDigitValue : 0;
    455   }
    456   DCHECK_EQ(forward_carry, 0);
    457 
    458   return midpoint;
    459 }
    460 
    461 template <typename Traits>
    462 Ordinal<Traits> Ordinal<Traits>::CreateOrdinalBetween(
    463     const Ordinal<Traits>& start,
    464     const Ordinal<Traits>& end) {
    465   CHECK(start.IsValid());
    466   CHECK(end.IsValid());
    467   CHECK(start.LessThan(end));
    468   const std::string& start_bytes = start.ToInternalValue();
    469   const std::string& end_bytes = end.ToInternalValue();
    470   DCHECK_LT(start_bytes, end_bytes);
    471 
    472   std::string midpoint = ComputeMidpoint(start_bytes, end_bytes);
    473   const size_t proper_length = GetProperLength(start_bytes, midpoint);
    474   midpoint.resize(proper_length, kZeroDigit);
    475 
    476   DCHECK_GT(midpoint, start_bytes);
    477   DCHECK_LT(midpoint, end_bytes);
    478 
    479   Ordinal<Traits> midpoint_ordinal(midpoint);
    480   DCHECK(midpoint_ordinal.IsValid());
    481   return midpoint_ordinal;
    482 }
    483 
    484 }  // namespace syncer
    485 
    486 #endif  // SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_
    487