12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file. 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_ 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_ 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <string> 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/basictypes.h" 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "sync/base/sync_export.h" 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace sync_pb { 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class UniquePosition; 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace syncer { 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// A class to represent positions. 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Valid UniquePosition objects have the following properties: 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// - a < b and b < c implies a < c (transitivity); 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// - exactly one of a < b, b < a and a = b holds (trichotomy); 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// - if a < b, there is a UniquePosition such that a < x < b (density); 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// - there are UniquePositions x and y such that x < a < y (unboundedness); 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// - if a and b were constructed with different unique suffixes, then a != b. 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// As long as all UniquePositions used to sort a list were created with unique 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// suffixes, then if any item changes its position in the list, only its 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// UniquePosition value has to change to represent the new order, and all other 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// values can stay the same. 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Note that the unique suffixes must be exactly |kSuffixLength| bytes long. 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The cost for all these features is potentially unbounded space usage. In 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// practice, however, most ordinals should be not much longer than the suffix. 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This class currently has several bookmarks-related assumptions built in, 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// though it could be adapted to be more generally useful. 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class SYNC_EXPORT_PRIVATE UniquePosition { 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static const size_t kSuffixLength; 44c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) static const size_t kCompressBytesThreshold; 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static bool IsValidSuffix(const std::string& suffix); 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static bool IsValidBytes(const std::string& bytes); 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 49cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) // Returns a valid, but mostly random suffix. 50cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) // Avoid using this; it can lead to inconsistent sort orderings if misused. 51cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) static std::string RandomSuffix(); 52cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns an invalid position. 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static UniquePosition CreateInvalid(); 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Converts from a 'sync_pb::UniquePosition' protobuf to a UniquePosition. 57c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // This may return an invalid position if the parsing fails. 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static UniquePosition FromProto(const sync_pb::UniquePosition& proto); 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Creates a position with the given suffix. Ordering among positions created 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // from this function is the same as that of the integer parameters that were 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // passed in. 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static UniquePosition FromInt64(int64 i, const std::string& suffix); 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns a valid position. Its ordering is not defined. 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static UniquePosition InitialPosition(const std::string& suffix); 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns positions compare smaller than, greater than, or between the input 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // positions. 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static UniquePosition Before(const UniquePosition& x, 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix); 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static UniquePosition After(const UniquePosition& x, 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix); 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static UniquePosition Between(const UniquePosition& before, 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition& after, 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix); 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // This constructor creates an invalid value. 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition(); 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool LessThan(const UniquePosition& other) const; 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool Equals(const UniquePosition& other) const; 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Serializes the position's internal state to a protobuf. 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void ToProto(sync_pb::UniquePosition* proto) const; 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 87c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Serializes the protobuf representation of this object as a string. 88c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) void SerializeToString(std::string* blob) const; 89c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns a human-readable representation of this item's internal state. 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string ToDebugString() const; 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns the suffix. 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string GetSuffixForTest() const; 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Performs a lossy conversion to an int64 position. Positions converted to 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // and from int64s using this and the FromInt64 function should maintain their 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // relative orderings unless the int64 values conflict. 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64 ToInt64() const; 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool IsValid() const; 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class UniquePositionTest; 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns a string X such that (X ++ |suffix|) < |str|. 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // |str| must be a trailing substring of a valid ordinal. 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // |suffix| must be a valid unique suffix. 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static std::string FindSmallerWithSuffix(const std::string& str, 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix); 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns a string X such that (X ++ |suffix|) > |str|. 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // |str| must be a trailing substring of a valid ordinal. 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // |suffix| must be a valid unique suffix. 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static std::string FindGreaterWithSuffix(const std::string& str, 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix); 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns a string X such that |before| < (X ++ |suffix|) < |after|. 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // |before| and after must be a trailing substrings of valid ordinals. 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // |suffix| must be a valid unique suffix. 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static std::string FindBetweenWithSuffix(const std::string& before, 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& after, 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix); 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1237dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // Expects a run-length compressed string as input. For internal use only. 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) explicit UniquePosition(const std::string& internal_rep); 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1267dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // Expects an uncompressed prefix and suffix as input. The |suffix| parameter 1277dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // must be a suffix of |uncompressed|. For internal use only. 1287dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch UniquePosition(const std::string& uncompressed, const std::string& suffix); 1297dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 1307dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // Implementation of an order-preserving run-length compression scheme. 1317dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch static std::string Compress(const std::string& input); 1327dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch static std::string CompressImpl(const std::string& input); 1337dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch static std::string Uncompress(const std::string& compressed); 1347dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch static bool IsValidCompressed(const std::string& str); 1357dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 1367dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // The position value after it has been run through the custom compression 1377dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // algorithm. See Compress() and Uncompress() functions above. 1387dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch std::string compressed_; 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool is_valid_; 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 1412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // namespace syncer; 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_ 145