Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(570)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: sync/internal_api/public/base/unique_position.h

Issue 2130453004: [Sync] Move //sync to //components/sync. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Rebase. Created 4 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « sync/internal_api/public/base/stop_source.h ('k') | sync/internal_api/public/base/unique_position.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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_
OLDNEW
« no previous file with comments | « sync/internal_api/public/base/stop_source.h ('k') | sync/internal_api/public/base/unique_position.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698