OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_ | 5 #ifndef COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_ |
6 #define COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_ | 6 #define COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_ |
7 | 7 |
8 #include <stddef.h> | 8 #include <stddef.h> |
9 #include <stdint.h> | 9 #include <stdint.h> |
10 | 10 |
11 #include <string> | 11 #include <string> |
12 | 12 |
13 #include "components/sync/base/sync_export.h" | |
14 | |
15 namespace sync_pb { | 13 namespace sync_pb { |
16 class UniquePosition; | 14 class UniquePosition; |
17 } | 15 } |
18 | 16 |
19 namespace syncer { | 17 namespace syncer { |
20 | 18 |
21 // A class to represent positions. | 19 // A class to represent positions. |
22 // | 20 // |
23 // Valid UniquePosition objects have the following properties: | 21 // Valid UniquePosition objects have the following properties: |
24 // | 22 // |
25 // - a < b and b < c implies a < c (transitivity); | 23 // - a < b and b < c implies a < c (transitivity); |
26 // - exactly one of a < b, b < a and a = b holds (trichotomy); | 24 // - 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); | 25 // - 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); | 26 // - 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. | 27 // - if a and b were constructed with different unique suffixes, then a != b. |
30 // | 28 // |
31 // As long as all UniquePositions used to sort a list were created with unique | 29 // 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 | 30 // 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 | 31 // UniquePosition value has to change to represent the new order, and all other |
34 // values can stay the same. | 32 // values can stay the same. |
35 // | 33 // |
36 // Note that the unique suffixes must be exactly |kSuffixLength| bytes long. | 34 // Note that the unique suffixes must be exactly |kSuffixLength| bytes long. |
37 // | 35 // |
38 // The cost for all these features is potentially unbounded space usage. In | 36 // 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. | 37 // practice, however, most ordinals should be not much longer than the suffix. |
40 // | 38 // |
41 // This class currently has several bookmarks-related assumptions built in, | 39 // This class currently has several bookmarks-related assumptions built in, |
42 // though it could be adapted to be more generally useful. | 40 // though it could be adapted to be more generally useful. |
43 class SYNC_EXPORT UniquePosition { | 41 class UniquePosition { |
44 public: | 42 public: |
45 static const size_t kSuffixLength; | 43 static const size_t kSuffixLength; |
46 static const size_t kCompressBytesThreshold; | 44 static const size_t kCompressBytesThreshold; |
47 | 45 |
48 static bool IsValidSuffix(const std::string& suffix); | 46 static bool IsValidSuffix(const std::string& suffix); |
49 static bool IsValidBytes(const std::string& bytes); | 47 static bool IsValidBytes(const std::string& bytes); |
50 | 48 |
51 // Returns a valid, but mostly random suffix. | 49 // Returns a valid, but mostly random suffix. |
52 // Avoid using this; it can lead to inconsistent sort orderings if misused. | 50 // Avoid using this; it can lead to inconsistent sort orderings if misused. |
53 static std::string RandomSuffix(); | 51 static std::string RandomSuffix(); |
(...skipping 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
138 | 136 |
139 // The position value after it has been run through the custom compression | 137 // The position value after it has been run through the custom compression |
140 // algorithm. See Compress() and Uncompress() functions above. | 138 // algorithm. See Compress() and Uncompress() functions above. |
141 std::string compressed_; | 139 std::string compressed_; |
142 bool is_valid_; | 140 bool is_valid_; |
143 }; | 141 }; |
144 | 142 |
145 } // namespace syncer | 143 } // namespace syncer |
146 | 144 |
147 #endif // COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_ | 145 #endif // COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_ |
OLD | NEW |