| 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 SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_ | 5 #ifndef SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_ |
| 6 #define SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_ | 6 #define SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_ |
| 7 | 7 |
| 8 #include <string> | 8 #include <string> |
| 9 | 9 |
| 10 #include "base/basictypes.h" | 10 #include "base/basictypes.h" |
| 11 #include "sync/base/sync_export.h" |
| 11 | 12 |
| 12 namespace sync_pb { | 13 namespace sync_pb { |
| 13 class UniquePosition; | 14 class UniquePosition; |
| 14 } | 15 } |
| 15 | 16 |
| 16 namespace syncer { | 17 namespace syncer { |
| 17 | 18 |
| 18 // A class to represent positions. | 19 // A class to represent positions. |
| 19 // | 20 // |
| 20 // Valid UniquePosition objects have the following properties: | 21 // Valid UniquePosition objects have the following properties: |
| 21 // | 22 // |
| 22 // - a < b and b < c implies a < c (transitivity); | 23 // - a < b and b < c implies a < c (transitivity); |
| 23 // - 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); |
| 24 // - 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); |
| 25 // - 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); |
| 26 // - 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. |
| 27 // | 28 // |
| 28 // 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 |
| 29 // 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 |
| 30 // 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 |
| 31 // values can stay the same. | 32 // values can stay the same. |
| 32 // | 33 // |
| 33 // Note that the unique suffixes must be exactly |kSuffixLength| bytes long. | 34 // Note that the unique suffixes must be exactly |kSuffixLength| bytes long. |
| 34 // | 35 // |
| 35 // 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 |
| 36 // 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. |
| 37 // | 38 // |
| 38 // This class currently has several bookmarks-related assumptions built in, | 39 // This class currently has several bookmarks-related assumptions built in, |
| 39 // though it could be adapted to be more generally useful. | 40 // though it could be adapted to be more generally useful. |
| 40 class UniquePosition { | 41 class SYNC_EXPORT_PRIVATE UniquePosition { |
| 41 public: | 42 public: |
| 42 static const size_t kSuffixLength; | 43 static const size_t kSuffixLength; |
| 43 | 44 |
| 44 static bool IsValidSuffix(const std::string& suffix); | 45 static bool IsValidSuffix(const std::string& suffix); |
| 45 static bool IsValidBytes(const std::string& bytes); | 46 static bool IsValidBytes(const std::string& bytes); |
| 46 | 47 |
| 47 // Returns an invalid position. | 48 // Returns an invalid position. |
| 48 static UniquePosition CreateInvalid(); | 49 static UniquePosition CreateInvalid(); |
| 49 | 50 |
| 50 // Converts from a 'sync_pb::UniquePosition' protobuf to a UniquePosition. | 51 // Converts from a 'sync_pb::UniquePosition' protobuf to a UniquePosition. |
| (...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 113 explicit UniquePosition(const std::string& internal_rep); | 114 explicit UniquePosition(const std::string& internal_rep); |
| 114 UniquePosition(const std::string& prefix, const std::string& suffix); | 115 UniquePosition(const std::string& prefix, const std::string& suffix); |
| 115 | 116 |
| 116 std::string bytes_; | 117 std::string bytes_; |
| 117 bool is_valid_; | 118 bool is_valid_; |
| 118 }; | 119 }; |
| 119 | 120 |
| 120 } // namespace syncer; | 121 } // namespace syncer; |
| 121 | 122 |
| 122 #endif // SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_ | 123 #endif // SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_ |
| OLD | NEW |