OLD | NEW |
| (Empty) |
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 | |
3 // found in the LICENSE file. | |
4 | |
5 #ifndef SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_ | |
6 #define SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_ | |
7 | |
8 #include <stdint.h> | |
9 | |
10 #include <algorithm> | |
11 #include <cstddef> | |
12 #include <string> | |
13 | |
14 #include "base/json/string_escape.h" | |
15 #include "base/logging.h" | |
16 | |
17 namespace syncer { | |
18 | |
19 // An Ordinal<T> is an object that can be used for ordering. The | |
20 // Ordinal<T> class has an unbounded dense strict total order, which | |
21 // mean for any Ordinal<T>s a, b and c: | |
22 // | |
23 // - a < b and b < c implies a < c (transitivity); | |
24 // - exactly one of a < b, b < a and a = b holds (trichotomy); | |
25 // - if a < b, there is a Ordinal<T> x such that a < x < b (density); | |
26 // - there are Ordinals<T> x and y such that x < a < y (unboundedness). | |
27 // | |
28 // This means that when Ordinal<T> is used for sorting a list, if any | |
29 // item changes its position in the list, only its Ordinal<T> value | |
30 // has to change to represent the new order, and all the other values | |
31 // can stay the same. | |
32 // | |
33 // An Ordinal<T> is internally represented as an array of bytes, so it | |
34 // can be serialized to and deserialized from disk. | |
35 // | |
36 // The Traits class should look like the following: | |
37 // | |
38 // // Don't forget to #include <stdint.h> and <stddef.h>. | |
39 // struct MyOrdinalTraits { | |
40 // // There must be at least two distinct values greater than kZeroDigit | |
41 // // and less than kMaxDigit. | |
42 // static const uint8_t kZeroDigit = '0'; | |
43 // static const uint8_t kMaxDigit = '9'; | |
44 // // kMinLength must be positive. | |
45 // static const size_t kMinLength = 1; | |
46 // }; | |
47 // | |
48 // An Ordinal<T> is valid iff its corresponding string has at least | |
49 // kMinLength characters, does not contain any characters less than | |
50 // kZeroDigit or greater than kMaxDigit, is not all zero digits, and | |
51 // does not have any unnecessary trailing zero digits. | |
52 // | |
53 // Note that even if the native char type is signed, strings still | |
54 // compare as if their they are unsigned. (This is explicitly in | |
55 // C++11 but not in C++98, even though all implementations do so | |
56 // anyway in practice.) Thus, it is safe to use any byte range for | |
57 // Ordinal<T>s. | |
58 template <typename Traits> | |
59 class Ordinal { | |
60 public: | |
61 // Functors for use with STL algorithms and containers. | |
62 class LessThanFn { | |
63 public: | |
64 LessThanFn(); | |
65 | |
66 bool operator()(const Ordinal<Traits>& lhs, | |
67 const Ordinal<Traits>& rhs) const; | |
68 }; | |
69 | |
70 class EqualsFn { | |
71 public: | |
72 EqualsFn(); | |
73 | |
74 bool operator()(const Ordinal<Traits>& lhs, | |
75 const Ordinal<Traits>& rhs) const; | |
76 }; | |
77 | |
78 // Creates an Ordinal from the given string of bytes. The Ordinal | |
79 // may be valid or invalid. | |
80 explicit Ordinal(const std::string& bytes); | |
81 | |
82 // Creates an invalid Ordinal. | |
83 Ordinal(); | |
84 | |
85 // Creates a valid initial Ordinal. This is called to create the first | |
86 // element of Ordinal list (i.e. before we have any other values we can | |
87 // generate from). | |
88 static Ordinal CreateInitialOrdinal(); | |
89 | |
90 // Returns true iff this Ordinal is valid. This takes constant | |
91 // time. | |
92 bool IsValid() const; | |
93 | |
94 // Returns true iff |*this| == |other| or |*this| and |other| | |
95 // are both invalid. | |
96 bool EqualsOrBothInvalid(const Ordinal& other) const; | |
97 | |
98 // Returns a printable string representation of the Ordinal suitable | |
99 // for logging. | |
100 std::string ToDebugString() const; | |
101 | |
102 // All remaining functions can only be called if IsValid() holds. | |
103 // It is an error to call them if IsValid() is false. | |
104 | |
105 // Order-related functions. | |
106 | |
107 // Returns true iff |*this| < |other|. | |
108 bool LessThan(const Ordinal& other) const; | |
109 | |
110 // Returns true iff |*this| > |other|. | |
111 bool GreaterThan(const Ordinal& other) const; | |
112 | |
113 // Returns true iff |*this| == |other| (i.e. |*this| < |other| and | |
114 // |other| < |*this| are both false). | |
115 bool Equals(const Ordinal& other) const; | |
116 | |
117 // Given |*this| != |other|, returns a Ordinal x such that | |
118 // min(|*this|, |other|) < x < max(|*this|, |other|). It is an error | |
119 // to call this function when |*this| == |other|. | |
120 Ordinal CreateBetween(const Ordinal& other) const; | |
121 | |
122 // Returns a Ordinal |x| such that |x| < |*this|. | |
123 Ordinal CreateBefore() const; | |
124 | |
125 // Returns a Ordinal |x| such that |*this| < |x|. | |
126 Ordinal CreateAfter() const; | |
127 | |
128 // Returns the string of bytes representing the Ordinal. It is | |
129 // guaranteed that an Ordinal constructed from the returned string | |
130 // will be valid. | |
131 std::string ToInternalValue() const; | |
132 | |
133 // Use of copy constructor and default assignment for this class is allowed. | |
134 | |
135 // Constants for Ordinal digits. | |
136 static const uint8_t kZeroDigit = Traits::kZeroDigit; | |
137 static const uint8_t kMaxDigit = Traits::kMaxDigit; | |
138 static const size_t kMinLength = Traits::kMinLength; | |
139 static const uint8_t kOneDigit = kZeroDigit + 1; | |
140 static const uint8_t kMidDigit = kOneDigit + (kMaxDigit - kOneDigit) / 2; | |
141 static const unsigned int kMidDigitValue = kMidDigit - kZeroDigit; | |
142 static const unsigned int kMaxDigitValue = kMaxDigit - kZeroDigit; | |
143 static const unsigned int kRadix = kMaxDigitValue + 1; | |
144 | |
145 static_assert(kOneDigit > kZeroDigit, "incorrect ordinal one digit"); | |
146 static_assert(kMidDigit > kOneDigit, "incorrect ordinal mid digit"); | |
147 static_assert(kMaxDigit > kMidDigit, "incorrect ordinal max digit"); | |
148 static_assert(kMinLength > 0, "incorrect ordinal min length"); | |
149 static_assert(kMidDigitValue > 1, "incorrect ordinal mid digit"); | |
150 static_assert(kMaxDigitValue > kMidDigitValue, "incorrect ordinal max digit"); | |
151 static_assert(kRadix == kMaxDigitValue + 1, "incorrect ordinal radix"); | |
152 | |
153 private: | |
154 // Returns true iff the given byte string satisfies the criteria for | |
155 // a valid Ordinal. | |
156 static bool IsValidOrdinalBytes(const std::string& bytes); | |
157 | |
158 // Returns the length that bytes.substr(0, length) would be with | |
159 // trailing zero digits removed. | |
160 static size_t GetLengthWithoutTrailingZeroDigits( | |
161 const std::string& bytes, | |
162 size_t length); | |
163 | |
164 // Returns the digit at position i, padding with zero digits if | |
165 // required. | |
166 static uint8_t GetDigit(const std::string& bytes, size_t i); | |
167 | |
168 // Returns the digit value at position i, padding with 0 if required. | |
169 static int GetDigitValue(const std::string& bytes, size_t i); | |
170 | |
171 // Adds the given value to |bytes| at position i, carrying when | |
172 // necessary. Returns the left-most carry. | |
173 static int AddDigitValue(std::string* bytes, size_t i, int digit_value); | |
174 | |
175 // Returns the proper length |bytes| should be resized to, i.e. the | |
176 // smallest length such that |bytes| is still greater than | |
177 // |lower_bound| and is still valid. |bytes| should be greater than | |
178 // |lower_bound|. | |
179 static size_t GetProperLength(const std::string& lower_bound, | |
180 const std::string& bytes); | |
181 | |
182 // Compute the midpoint ordinal byte string that is between |start| | |
183 // and |end|. | |
184 static std::string ComputeMidpoint(const std::string& start, | |
185 const std::string& end); | |
186 | |
187 // Create a Ordinal that is lexigraphically greater than |start| and | |
188 // lexigraphically less than |end|. The returned Ordinal will be roughly | |
189 // between |start| and |end|. | |
190 static Ordinal<Traits> CreateOrdinalBetween(const Ordinal<Traits>& start, | |
191 const Ordinal<Traits>& end); | |
192 | |
193 // The internal byte string representation of the Ordinal. Never | |
194 // changes after construction except for assignment. | |
195 std::string bytes_; | |
196 | |
197 // A cache of the result of IsValidOrdinalBytes(bytes_). | |
198 bool is_valid_; | |
199 }; | |
200 | |
201 template <typename Traits> | |
202 const uint8_t Ordinal<Traits>::kZeroDigit; | |
203 template <typename Traits> | |
204 const uint8_t Ordinal<Traits>::kMaxDigit; | |
205 template <typename Traits> const size_t Ordinal<Traits>::kMinLength; | |
206 template <typename Traits> | |
207 const uint8_t Ordinal<Traits>::kOneDigit; | |
208 template <typename Traits> | |
209 const uint8_t Ordinal<Traits>::kMidDigit; | |
210 template <typename Traits> const unsigned int Ordinal<Traits>::kMidDigitValue; | |
211 template <typename Traits> const unsigned int Ordinal<Traits>::kMaxDigitValue; | |
212 template <typename Traits> const unsigned int Ordinal<Traits>::kRadix; | |
213 | |
214 template <typename Traits> | |
215 Ordinal<Traits>::LessThanFn::LessThanFn() {} | |
216 | |
217 template <typename Traits> | |
218 bool Ordinal<Traits>::LessThanFn::operator()(const Ordinal<Traits>& lhs, | |
219 const Ordinal<Traits>& rhs) const { | |
220 return lhs.LessThan(rhs); | |
221 } | |
222 | |
223 template <typename Traits> | |
224 Ordinal<Traits>::EqualsFn::EqualsFn() {} | |
225 | |
226 template <typename Traits> | |
227 bool Ordinal<Traits>::EqualsFn::operator()(const Ordinal<Traits>& lhs, | |
228 const Ordinal<Traits>& rhs) const { | |
229 return lhs.Equals(rhs); | |
230 } | |
231 | |
232 template <typename Traits> | |
233 Ordinal<Traits>::Ordinal(const std::string& bytes) | |
234 : bytes_(bytes), | |
235 is_valid_(IsValidOrdinalBytes(bytes_)) {} | |
236 | |
237 template <typename Traits> | |
238 Ordinal<Traits>::Ordinal() : is_valid_(false) {} | |
239 | |
240 template <typename Traits> | |
241 Ordinal<Traits> Ordinal<Traits>::CreateInitialOrdinal() { | |
242 std::string bytes(Traits::kMinLength, kZeroDigit); | |
243 bytes[0] = kMidDigit; | |
244 return Ordinal(bytes); | |
245 } | |
246 | |
247 template <typename Traits> | |
248 bool Ordinal<Traits>::IsValid() const { | |
249 DCHECK_EQ(IsValidOrdinalBytes(bytes_), is_valid_); | |
250 return is_valid_; | |
251 } | |
252 | |
253 template <typename Traits> | |
254 bool Ordinal<Traits>::EqualsOrBothInvalid(const Ordinal& other) const { | |
255 if (!IsValid() && !other.IsValid()) | |
256 return true; | |
257 | |
258 if (!IsValid() || !other.IsValid()) | |
259 return false; | |
260 | |
261 return Equals(other); | |
262 } | |
263 | |
264 template <typename Traits> | |
265 std::string Ordinal<Traits>::ToDebugString() const { | |
266 std::string debug_string = | |
267 base::EscapeBytesAsInvalidJSONString(bytes_, false /* put_in_quotes */); | |
268 if (!is_valid_) { | |
269 debug_string = "INVALID[" + debug_string + "]"; | |
270 } | |
271 return debug_string; | |
272 } | |
273 | |
274 template <typename Traits> | |
275 bool Ordinal<Traits>::LessThan(const Ordinal& other) const { | |
276 CHECK(IsValid()); | |
277 CHECK(other.IsValid()); | |
278 return bytes_ < other.bytes_; | |
279 } | |
280 | |
281 template <typename Traits> | |
282 bool Ordinal<Traits>::GreaterThan(const Ordinal& other) const { | |
283 CHECK(IsValid()); | |
284 CHECK(other.IsValid()); | |
285 return bytes_ > other.bytes_; | |
286 } | |
287 | |
288 template <typename Traits> | |
289 bool Ordinal<Traits>::Equals(const Ordinal& other) const { | |
290 CHECK(IsValid()); | |
291 CHECK(other.IsValid()); | |
292 return bytes_ == other.bytes_; | |
293 } | |
294 | |
295 template <typename Traits> | |
296 Ordinal<Traits> Ordinal<Traits>::CreateBetween(const Ordinal& other) const { | |
297 CHECK(IsValid()); | |
298 CHECK(other.IsValid()); | |
299 CHECK(!Equals(other)); | |
300 | |
301 if (LessThan(other)) { | |
302 return CreateOrdinalBetween(*this, other); | |
303 } else { | |
304 return CreateOrdinalBetween(other, *this); | |
305 } | |
306 } | |
307 | |
308 template <typename Traits> | |
309 Ordinal<Traits> Ordinal<Traits>::CreateBefore() const { | |
310 CHECK(IsValid()); | |
311 // Create the smallest valid Ordinal of the appropriate length | |
312 // to be the minimum boundary. | |
313 const size_t length = bytes_.length(); | |
314 std::string start(length, kZeroDigit); | |
315 start[length - 1] = kOneDigit; | |
316 if (start == bytes_) { | |
317 start[length - 1] = kZeroDigit; | |
318 start += kOneDigit; | |
319 } | |
320 | |
321 // Even though |start| is already a valid Ordinal that is less | |
322 // than |*this|, we don't return it because we wouldn't have much space in | |
323 // front of it to insert potential future values. | |
324 return CreateBetween(Ordinal(start)); | |
325 } | |
326 | |
327 template <typename Traits> | |
328 Ordinal<Traits> Ordinal<Traits>::CreateAfter() const { | |
329 CHECK(IsValid()); | |
330 // Create the largest valid Ordinal of the appropriate length to be | |
331 // the maximum boundary. | |
332 std::string end(bytes_.length(), kMaxDigit); | |
333 if (end == bytes_) | |
334 end += kMaxDigit; | |
335 | |
336 // Even though |end| is already a valid Ordinal that is greater than | |
337 // |*this|, we don't return it because we wouldn't have much space after | |
338 // it to insert potential future values. | |
339 return CreateBetween(Ordinal(end)); | |
340 } | |
341 | |
342 template <typename Traits> | |
343 std::string Ordinal<Traits>::ToInternalValue() const { | |
344 CHECK(IsValid()); | |
345 return bytes_; | |
346 } | |
347 | |
348 template <typename Traits> | |
349 bool Ordinal<Traits>::IsValidOrdinalBytes(const std::string& bytes) { | |
350 const size_t length = bytes.length(); | |
351 if (length < kMinLength) | |
352 return false; | |
353 | |
354 bool found_non_zero = false; | |
355 for (size_t i = 0; i < length; ++i) { | |
356 const uint8_t byte = bytes[i]; | |
357 if (byte < kZeroDigit || byte > kMaxDigit) | |
358 return false; | |
359 if (byte > kZeroDigit) | |
360 found_non_zero = true; | |
361 } | |
362 if (!found_non_zero) | |
363 return false; | |
364 | |
365 if (length > kMinLength) { | |
366 const uint8_t last_byte = bytes[length - 1]; | |
367 if (last_byte == kZeroDigit) | |
368 return false; | |
369 } | |
370 | |
371 return true; | |
372 } | |
373 | |
374 template <typename Traits> | |
375 size_t Ordinal<Traits>::GetLengthWithoutTrailingZeroDigits( | |
376 const std::string& bytes, size_t length) { | |
377 DCHECK(!bytes.empty()); | |
378 DCHECK_GT(length, 0U); | |
379 | |
380 size_t end_position = | |
381 bytes.find_last_not_of(static_cast<char>(kZeroDigit), length - 1); | |
382 | |
383 // If no non kZeroDigit is found then the string is a string of all zeros | |
384 // digits so we return 0 as the correct length. | |
385 if (end_position == std::string::npos) | |
386 return 0; | |
387 | |
388 return end_position + 1; | |
389 } | |
390 | |
391 template <typename Traits> | |
392 uint8_t Ordinal<Traits>::GetDigit(const std::string& bytes, size_t i) { | |
393 return (i < bytes.length()) ? bytes[i] : kZeroDigit; | |
394 } | |
395 | |
396 template <typename Traits> | |
397 int Ordinal<Traits>::GetDigitValue(const std::string& bytes, size_t i) { | |
398 return GetDigit(bytes, i) - kZeroDigit; | |
399 } | |
400 | |
401 template <typename Traits> | |
402 int Ordinal<Traits>::AddDigitValue(std::string* bytes, | |
403 size_t i, int digit_value) { | |
404 DCHECK_GE(i, 0U); | |
405 DCHECK_LT(i, bytes->length()); | |
406 | |
407 for (int j = static_cast<int>(i); j >= 0 && digit_value > 0; --j) { | |
408 int byte_j_value = GetDigitValue(*bytes, j) + digit_value; | |
409 digit_value = byte_j_value / kRadix; | |
410 DCHECK_LE(digit_value, 1); | |
411 byte_j_value %= kRadix; | |
412 (*bytes)[j] = static_cast<char>(kZeroDigit + byte_j_value); | |
413 } | |
414 return digit_value; | |
415 } | |
416 | |
417 template <typename Traits> | |
418 size_t Ordinal<Traits>::GetProperLength(const std::string& lower_bound, | |
419 const std::string& bytes) { | |
420 CHECK_GT(bytes, lower_bound); | |
421 | |
422 size_t drop_length = | |
423 GetLengthWithoutTrailingZeroDigits(bytes, bytes.length()); | |
424 // See if the |ordinal| can be truncated after its last non-zero | |
425 // digit without affecting the ordering. | |
426 if (drop_length > kMinLength) { | |
427 size_t truncated_length = | |
428 GetLengthWithoutTrailingZeroDigits(bytes, drop_length - 1); | |
429 | |
430 if (truncated_length > 0 && | |
431 bytes.compare(0, truncated_length, lower_bound) > 0) | |
432 drop_length = truncated_length; | |
433 } | |
434 return std::max(drop_length, kMinLength); | |
435 } | |
436 | |
437 template <typename Traits> | |
438 std::string Ordinal<Traits>::ComputeMidpoint( | |
439 const std::string& start, | |
440 const std::string& end) { | |
441 size_t max_size = std::max(start.length(), end.length()) + 1; | |
442 std::string midpoint(max_size, kZeroDigit); | |
443 | |
444 // Perform the operation (start + end) / 2 left-to-right by | |
445 // maintaining a "forward carry" which is either 0 or | |
446 // kMidDigitValue. AddDigitValue() is in general O(n), but this | |
447 // operation is still O(n) despite that; calls to AddDigitValue() | |
448 // will overflow at most to the last position where AddDigitValue() | |
449 // last overflowed. | |
450 int forward_carry = 0; | |
451 for (size_t i = 0; i < max_size; ++i) { | |
452 const int sum_value = GetDigitValue(start, i) + GetDigitValue(end, i); | |
453 const int digit_value = sum_value / 2 + forward_carry; | |
454 // AddDigitValue returning a non-zero carry would imply that | |
455 // midpoint[0] >= kMaxDigit, which one can show is impossible. | |
456 CHECK_EQ(AddDigitValue(&midpoint, i, digit_value), 0); | |
457 forward_carry = (sum_value % 2 == 1) ? kMidDigitValue : 0; | |
458 } | |
459 DCHECK_EQ(forward_carry, 0); | |
460 | |
461 return midpoint; | |
462 } | |
463 | |
464 template <typename Traits> | |
465 Ordinal<Traits> Ordinal<Traits>::CreateOrdinalBetween( | |
466 const Ordinal<Traits>& start, | |
467 const Ordinal<Traits>& end) { | |
468 CHECK(start.IsValid()); | |
469 CHECK(end.IsValid()); | |
470 CHECK(start.LessThan(end)); | |
471 const std::string& start_bytes = start.ToInternalValue(); | |
472 const std::string& end_bytes = end.ToInternalValue(); | |
473 DCHECK_LT(start_bytes, end_bytes); | |
474 | |
475 std::string midpoint = ComputeMidpoint(start_bytes, end_bytes); | |
476 const size_t proper_length = GetProperLength(start_bytes, midpoint); | |
477 midpoint.resize(proper_length, kZeroDigit); | |
478 | |
479 DCHECK_GT(midpoint, start_bytes); | |
480 DCHECK_LT(midpoint, end_bytes); | |
481 | |
482 Ordinal<Traits> midpoint_ordinal(midpoint); | |
483 DCHECK(midpoint_ordinal.IsValid()); | |
484 return midpoint_ordinal; | |
485 } | |
486 | |
487 } // namespace syncer | |
488 | |
489 #endif // SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_ | |
OLD | NEW |