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