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 an invalid position. 50 static UniquePosition CreateInvalid(); 51 52 // Converts from a 'sync_pb::UniquePosition' protobuf to a UniquePosition. 53 // This may return an invalid position if the parsing fails. 54 static UniquePosition FromProto(const sync_pb::UniquePosition& proto); 55 56 // Creates a position with the given suffix. Ordering among positions created 57 // from this function is the same as that of the integer parameters that were 58 // passed in. 59 static UniquePosition FromInt64(int64 i, const std::string& suffix); 60 61 // Returns a valid position. Its ordering is not defined. 62 static UniquePosition InitialPosition(const std::string& suffix); 63 64 // Returns positions compare smaller than, greater than, or between the input 65 // positions. 66 static UniquePosition Before(const UniquePosition& x, 67 const std::string& suffix); 68 static UniquePosition After(const UniquePosition& x, 69 const std::string& suffix); 70 static UniquePosition Between(const UniquePosition& before, 71 const UniquePosition& after, 72 const std::string& suffix); 73 74 // This constructor creates an invalid value. 75 UniquePosition(); 76 77 bool LessThan(const UniquePosition& other) const; 78 bool Equals(const UniquePosition& other) const; 79 80 // Serializes the position's internal state to a protobuf. 81 void ToProto(sync_pb::UniquePosition* proto) const; 82 83 // Serializes the protobuf representation of this object as a string. 84 void SerializeToString(std::string* blob) const; 85 86 // Returns a human-readable representation of this item's internal state. 87 std::string ToDebugString() const; 88 89 // Returns the suffix. 90 std::string GetSuffixForTest() const; 91 92 // Performs a lossy conversion to an int64 position. Positions converted to 93 // and from int64s using this and the FromInt64 function should maintain their 94 // relative orderings unless the int64 values conflict. 95 int64 ToInt64() const; 96 97 bool IsValid() const; 98 99 private: 100 friend class UniquePositionTest; 101 102 // Returns a string X such that (X ++ |suffix|) < |str|. 103 // |str| must be a trailing substring of a valid ordinal. 104 // |suffix| must be a valid unique suffix. 105 static std::string FindSmallerWithSuffix(const std::string& str, 106 const std::string& suffix); 107 // Returns a string X such that (X ++ |suffix|) > |str|. 108 // |str| must be a trailing substring of a valid ordinal. 109 // |suffix| must be a valid unique suffix. 110 static std::string FindGreaterWithSuffix(const std::string& str, 111 const std::string& suffix); 112 // Returns a string X such that |before| < (X ++ |suffix|) < |after|. 113 // |before| and after must be a trailing substrings of valid ordinals. 114 // |suffix| must be a valid unique suffix. 115 static std::string FindBetweenWithSuffix(const std::string& before, 116 const std::string& after, 117 const std::string& suffix); 118 119 // Expects a run-length compressed string as input. For internal use only. 120 explicit UniquePosition(const std::string& internal_rep); 121 122 // Expects an uncompressed prefix and suffix as input. The |suffix| parameter 123 // must be a suffix of |uncompressed|. For internal use only. 124 UniquePosition(const std::string& uncompressed, const std::string& suffix); 125 126 // Implementation of an order-preserving run-length compression scheme. 127 static std::string Compress(const std::string& input); 128 static std::string CompressImpl(const std::string& input); 129 static std::string Uncompress(const std::string& compressed); 130 static bool IsValidCompressed(const std::string& str); 131 132 // The position value after it has been run through the custom compression 133 // algorithm. See Compress() and Uncompress() functions above. 134 std::string compressed_; 135 bool is_valid_; 136 }; 137 138 } // namespace syncer; 139 140 #endif // SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_ 141
