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
141
142
143
144
145
146
147
148
149
150
151
|
// Copyright 2012 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_
#define COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_
#include <stddef.h>
#include <stdint.h>
#include <array>
#include <string>
namespace sync_pb {
class UniquePosition;
}
namespace syncer {
class ClientTagHash;
// 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.
class UniquePosition {
public:
// The suffix must be exactly the specified length, otherwise unique suffixes
// are not sufficient to guarantee unique positions (because prefix + suffix
// == p + refixsuffix).
static constexpr size_t kSuffixLength = 28;
static constexpr size_t kCompressBytesThreshold = 128;
using Suffix = std::array<uint8_t, kSuffixLength>;
static bool IsValidSuffix(const Suffix& suffix);
static bool IsValidBytes(const std::string& bytes);
// Returns a valid, but mostly random suffix.
// Avoid using this; it can lead to inconsistent sort orderings if misused.
static Suffix RandomSuffix();
// Returns a valid suffix based on the given client tag hash.
static Suffix GenerateSuffix(const ClientTagHash& client_tag_hash);
// 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. `suffix` must be a valid suffix with length `kSuffixLength`.
static UniquePosition FromInt64(int64_t i, const Suffix& suffix);
// Returns a valid position. Its ordering is not defined. `suffix` must be a
// valid suffix with length `kSuffixLength`.
static UniquePosition InitialPosition(const Suffix& suffix);
// Returns positions compare smaller than, greater than, or between the input
// positions. `suffix` must be a valid suffix with length `kSuffixLength`.
static UniquePosition Before(const UniquePosition& x, const Suffix& suffix);
static UniquePosition After(const UniquePosition& x, const Suffix& suffix);
static UniquePosition Between(const UniquePosition& before,
const UniquePosition& after,
const Suffix& suffix);
// Creates an empty, invalid value.
UniquePosition();
// Type is copyable and movable.
UniquePosition(const UniquePosition&) = default;
UniquePosition(UniquePosition&&) = default;
UniquePosition& operator=(const UniquePosition&) = default;
UniquePosition& operator=(UniquePosition&&) = default;
bool LessThan(const UniquePosition& other) const;
bool Equals(const UniquePosition& other) const;
// Serializes the position's internal state to a protobuf.
sync_pb::UniquePosition ToProto() 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.
Suffix GetSuffixForTest() const;
bool IsValid() const;
// Returns memory usage estimate.
size_t EstimateMemoryUsage() 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 Suffix& 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 Suffix& 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 Suffix& suffix);
// Expects a run-length compressed string as input. For internal use only.
explicit UniquePosition(const std::string& compressed);
// 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 Suffix& 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_;
};
} // namespace syncer
#endif // COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_
|
