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_ 145