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