sync/internal_api/public/base/unique_position.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_UNIQUE_POSITION_H_
   6 #define SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_
   7
   8 #include <string>
   9
  10 #include "base/basictypes.h"
  11 #include "sync/base/sync_export.h"
  12
  13 namespace sync_pb {
  14 class UniquePosition;
  15 }
  16
  17 namespace syncer {
  18
  19 // A class to represent positions.
  20 //
  21 // Valid UniquePosition objects have the following properties:
  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 UniquePosition such that a < x < b (density);
  26 //  - there are UniquePositions x and y such that x < a < y (unboundedness);
  27 //  - if a and b were constructed with different unique suffixes, then a != b.
  28 //
  29 // As long as all UniquePositions used to sort a list were created with unique
  30 // suffixes, then if any item changes its position in the list, only its
  31 // UniquePosition value has to change to represent the new order, and all other
  32 // values can stay the same.
  33 //
  34 // Note that the unique suffixes must be exactly |kSuffixLength| bytes long.
  35 //
  36 // The cost for all these features is potentially unbounded space usage.  In
  37 // practice, however, most ordinals should be not much longer than the suffix.
  38 //
  39 // This class currently has several bookmarks-related assumptions built in,
  40 // though it could be adapted to be more generally useful.
  41 class SYNC_EXPORT_PRIVATE UniquePosition {
  42  public:
  43   static const size_t kSuffixLength;
  44   static const size_t kCompressBytesThreshold;
  45
  46   static bool IsValidSuffix(const std::string& suffix);
  47   static bool IsValidBytes(const std::string& bytes);
  48
  49   // Returns a valid, but mostly random suffix.
  50   // Avoid using this; it can lead to inconsistent sort orderings if misused.
  51   static std::string RandomSuffix();
  52
  53   // Returns an invalid position.
  54   static UniquePosition CreateInvalid();
  55
  56   // Converts from a 'sync_pb::UniquePosition' protobuf to a UniquePosition.
  57   // This may return an invalid position if the parsing fails.
  58   static UniquePosition FromProto(const sync_pb::UniquePosition& proto);
  59
  60   // Creates a position with the given suffix.  Ordering among positions created
  61   // from this function is the same as that of the integer parameters that were
  62   // passed in.
  63   static UniquePosition FromInt64(int64 i, const std::string& suffix);
  64
  65   // Returns a valid position.  Its ordering is not defined.
  66   static UniquePosition InitialPosition(const std::string& suffix);
  67
  68   // Returns positions compare smaller than, greater than, or between the input
  69   // positions.
  70   static UniquePosition Before(const UniquePosition& x,
  71                                const std::string& suffix);
  72   static UniquePosition After(const UniquePosition& x,
  73                               const std::string& suffix);
  74   static UniquePosition Between(const UniquePosition& before,
  75                                 const UniquePosition& after,
  76                                 const std::string& suffix);
  77
  78   // This constructor creates an invalid value.
  79   UniquePosition();
  80
  81   bool LessThan(const UniquePosition& other) const;
  82   bool Equals(const UniquePosition& other) const;
  83
  84   // Serializes the position's internal state to a protobuf.
  85   void ToProto(sync_pb::UniquePosition* proto) const;
  86
  87   // Serializes the protobuf representation of this object as a string.
  88   void SerializeToString(std::string* blob) const;
  89
  90   // Returns a human-readable representation of this item's internal state.
  91   std::string ToDebugString() const;
  92
  93   // Returns the suffix.
  94   std::string GetSuffixForTest() const;
  95
  96   // Performs a lossy conversion to an int64 position.  Positions converted to
  97   // and from int64s using this and the FromInt64 function should maintain their
  98   // relative orderings unless the int64 values conflict.
  99   int64 ToInt64() const;
 100
 101   bool IsValid() const;
 102
 103  private:
 104   friend class UniquePositionTest;
 105
 106   // Returns a string X such that (X ++ |suffix|) < |str|.
 107   // |str| must be a trailing substring of a valid ordinal.
 108   // |suffix| must be a valid unique suffix.
 109   static std::string FindSmallerWithSuffix(const std::string& str,
 110                                            const std::string& suffix);
 111   // Returns a string X such that (X ++ |suffix|) > |str|.
 112   // |str| must be a trailing substring of a valid ordinal.
 113   // |suffix| must be a valid unique suffix.
 114   static std::string FindGreaterWithSuffix(const std::string& str,
 115                                            const std::string& suffix);
 116   // Returns a string X such that |before| < (X ++ |suffix|) < |after|.
 117   // |before| and after must be a trailing substrings of valid ordinals.
 118   // |suffix| must be a valid unique suffix.
 119   static std::string FindBetweenWithSuffix(const std::string& before,
 120                                            const std::string& after,
 121                                            const std::string& suffix);
 122
 123   // Expects a run-length compressed string as input.  For internal use only.
 124   explicit UniquePosition(const std::string& internal_rep);
 125
 126   // Expects an uncompressed prefix and suffix as input.  The |suffix| parameter
 127   // must be a suffix of |uncompressed|.  For internal use only.
 128   UniquePosition(const std::string& uncompressed, const std::string& suffix);
 129
 130   // Implementation of an order-preserving run-length compression scheme.
 131   static std::string Compress(const std::string& input);
 132   static std::string CompressImpl(const std::string& input);
 133   static std::string Uncompress(const std::string& compressed);
 134   static bool IsValidCompressed(const std::string& str);
 135
 136   // The position value after it has been run through the custom compression
 137   // algorithm.  See Compress() and Uncompress() functions above.
 138   std::string compressed_;
 139   bool is_valid_;
 140 };
 141
 142 }  // namespace syncer;
 143
 144 #endif  // SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_