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