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)#include "sync/internal_api/public/base/unique_position.h" 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <algorithm> 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <string> 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/base64.h" 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/basictypes.h" 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/logging.h" 137dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch#include "base/memory/scoped_ptr.h" 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/sha1.h" 15868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/strings/string_number_conversions.h" 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "sync/protocol/unique_position.pb.h" 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "testing/gtest/include/gtest/gtest.h" 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace syncer { 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace { 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class UniquePositionTest : public ::testing::Test { 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) protected: 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Accessor to fetch the length of the position's internal representation 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // We try to avoid having any test expectations on it because this is an 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // implementation detail. 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // If you run the tests with --v=1, we'll print out some of the lengths 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // so you can see how well the algorithm performs in various insertion 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // scenarios. 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t GetLength(const UniquePosition& pos) { 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) sync_pb::UniquePosition proto; 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pos.ToProto(&proto); 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return proto.ByteSize(); 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This function exploits internal knowledge of how the protobufs are serialized 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// to help us build UniquePositions from strings described in this file. 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static UniquePosition FromBytes(const std::string& bytes) { 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) sync_pb::UniquePosition proto; 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) proto.set_value(bytes); 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return UniquePosition::FromProto(proto); 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const size_t kMinLength = UniquePosition::kSuffixLength; 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const size_t kGenericPredecessorLength = kMinLength + 2; 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const size_t kGenericSuccessorLength = kMinLength + 1; 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const size_t kBigPositionLength = kMinLength; 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const size_t kSmallPositionLength = kMinLength; 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Be careful when adding more prefixes to this list. 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// We have to manually ensure each has a unique suffix. 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const UniquePosition kGenericPredecessor = FromBytes( 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (std::string(kGenericPredecessorLength, '\x23') + '\xFF')); 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const UniquePosition kGenericSuccessor = FromBytes( 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string(kGenericSuccessorLength, '\xAB') + '\xFF'); 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const UniquePosition kBigPosition = FromBytes( 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string(kBigPositionLength - 1, '\xFF') + '\xFE' + '\xFF'); 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const UniquePosition kBigPositionLessTwo = FromBytes( 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string(kBigPositionLength - 1, '\xFF') + '\xFC' + '\xFF'); 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const UniquePosition kBiggerPosition = FromBytes( 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string(kBigPositionLength, '\xFF') + '\xFF'); 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const UniquePosition kSmallPosition = FromBytes( 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string(kSmallPositionLength - 1, '\x00') + '\x01' + '\xFF'); 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const UniquePosition kSmallPositionPlusOne = FromBytes( 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string(kSmallPositionLength - 1, '\x00') + '\x02' + '\xFF'); 69c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)const UniquePosition kHugePosition = FromBytes( 70c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) std::string(UniquePosition::kCompressBytesThreshold, '\xFF') + '\xAB'); 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const std::string kMinSuffix = 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string(UniquePosition::kSuffixLength - 1, '\x00') + '\x01'; 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const std::string kMaxSuffix(UniquePosition::kSuffixLength, '\xFF'); 75c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)const std::string kNormalSuffix( 76c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) "\x68\x44\x6C\x6B\x32\x58\x78\x34\x69\x70\x46\x34\x79\x49" 77c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) "\x44\x4F\x66\x4C\x58\x41\x31\x34\x68\x59\x56\x43\x6F\x3D"); 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)::testing::AssertionResult LessThan(const char* m_expr, 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const char* n_expr, 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition &m, 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition &n) { 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (m.LessThan(n)) 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return ::testing::AssertionSuccess(); 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return ::testing::AssertionFailure() 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << m_expr << " is not less than " << n_expr 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << " (" << m.ToDebugString() << " and " << n.ToDebugString() << ")"; 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 91c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)::testing::AssertionResult Equals(const char* m_expr, 92c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const char* n_expr, 93c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const UniquePosition &m, 94c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const UniquePosition &n) { 95c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (m.Equals(n)) 96c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return ::testing::AssertionSuccess(); 97c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 98c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return ::testing::AssertionFailure() 99c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) << m_expr << " is not equal to " << n_expr 100c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) << " (" << m.ToDebugString() << " != " << n.ToDebugString() << ")"; 101c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 102c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 1037dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch// Test that the code can read the uncompressed serialization format. 1047dbb3d5cf0c15f500944d211057644d6a2f37371Ben MurdochTEST_F(UniquePositionTest, DeserializeObsoleteUncompressedPosition) { 1057dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // We no longer support the encoding data in this format. This hard-coded 1067dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // input is a serialization of kGenericPredecessor created by an older version 1077dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // of this code. 1087dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch const char kSerializedCstr[] = { 1097dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch '\x0a', '\x1f', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', 1107dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', 1117dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', 1127dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch '\x23', '\x23', '\x23', '\x23', '\x23', '\xff' }; 1137dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch const std::string serialized(kSerializedCstr, sizeof(kSerializedCstr)); 114c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 1157dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch sync_pb::UniquePosition proto; 1167dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch proto.ParseFromString(serialized); 117c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 118c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Double-check that this test is testing what we think it tests. 1197dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch EXPECT_TRUE(proto.has_value()); 1207dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch EXPECT_FALSE(proto.has_compressed_value()); 1217dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch EXPECT_FALSE(proto.has_uncompressed_length()); 122c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 1237dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch UniquePosition pos = UniquePosition::FromProto(proto); 1247dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch EXPECT_PRED_FORMAT2(Equals, kGenericPredecessor, pos); 125c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 126c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 1277dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch// Test that the code can read the gzip serialization format. 1287dbb3d5cf0c15f500944d211057644d6a2f37371Ben MurdochTEST_F(UniquePositionTest, DeserializeObsoleteGzippedPosition) { 1297dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // We no longer support the encoding data in this format. This hard-coded 1307dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // input is a serialization of kHugePosition created by an older version of 1317dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // this code. 1327dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch const char kSerializedCstr[] = { 1337dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch '\x12', '\x0d', '\x78', '\x9c', '\xfb', '\xff', '\x7f', '\x60', '\xc1', 1347dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch '\x6a', '\x00', '\xa2', '\x4c', '\x80', '\x2c', '\x18', '\x81', '\x01' }; 1357dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch const std::string serialized(kSerializedCstr, sizeof(kSerializedCstr)); 136c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 1377dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch sync_pb::UniquePosition proto; 1387dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch proto.ParseFromString(serialized); 139c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 140c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Double-check that this test is testing what we think it tests. 1417dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch EXPECT_FALSE(proto.has_value()); 1427dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch EXPECT_TRUE(proto.has_compressed_value()); 1437dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch EXPECT_TRUE(proto.has_uncompressed_length()); 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1457dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch UniquePosition pos = UniquePosition::FromProto(proto); 1467dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch EXPECT_PRED_FORMAT2(Equals, kHugePosition, pos); 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class RelativePositioningTest : public UniquePositionTest { }; 1502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const UniquePosition kPositionArray[] = { 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kGenericPredecessor, 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kGenericSuccessor, 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kBigPosition, 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kBigPositionLessTwo, 1562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kBiggerPosition, 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kSmallPosition, 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kSmallPositionPlusOne, 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const UniquePosition kSortedPositionArray[] = { 1622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kSmallPosition, 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kSmallPositionPlusOne, 1642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kGenericPredecessor, 1652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kGenericSuccessor, 1662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kBigPositionLessTwo, 1672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kBigPosition, 1682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kBiggerPosition, 1692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static const size_t kNumPositions = arraysize(kPositionArray); 1722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static const size_t kNumSortedPositions = arraysize(kSortedPositionArray); 1732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)struct PositionLessThan { 1752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool operator()(const UniquePosition& a, const UniquePosition& b) { 1762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return a.LessThan(b); 1772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 1792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Returns true iff the given position's suffix matches the input parameter. 1812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static bool IsSuffixInUse( 1822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition& pos, const std::string& suffix) { 1832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return pos.GetSuffixForTest() == suffix; 1842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Test some basic properties of comparison and equality. 1872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_F(RelativePositioningTest, ComparisonSanityTest1) { 1882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition& a = kPositionArray[0]; 1892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_TRUE(a.IsValid()); 1902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Necessarily true for any non-invalid positions. 1922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_TRUE(a.Equals(a)); 1932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_FALSE(a.LessThan(a)); 1942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Test some more properties of comparison and equality. 1972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_F(RelativePositioningTest, ComparisonSanityTest2) { 1982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition& a = kPositionArray[0]; 1992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition& b = kPositionArray[1]; 2002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // These should pass for the specific a and b we have chosen (a < b). 2022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_FALSE(a.Equals(b)); 2032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_TRUE(a.LessThan(b)); 2042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_FALSE(b.LessThan(a)); 2052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Exercise comparision functions by sorting and re-sorting the list. 2082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_F(RelativePositioningTest, SortPositions) { 2092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_EQ(kNumPositions, kNumSortedPositions); 2102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition positions[arraysize(kPositionArray)]; 2112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < kNumPositions; ++i) { 2122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) positions[i] = kPositionArray[i]; 2132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::sort(&positions[0], &positions[kNumPositions], PositionLessThan()); 2162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < kNumPositions; ++i) { 2172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_TRUE(positions[i].Equals(kSortedPositionArray[i])) 2182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << "i: " << i << ", " 2192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << positions[i].ToDebugString() << " != " 2202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << kSortedPositionArray[i].ToDebugString(); 2212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Some more exercise for the comparison function. 2262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_F(RelativePositioningTest, ReverseSortPositions) { 2272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_EQ(kNumPositions, kNumSortedPositions); 2282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition positions[arraysize(kPositionArray)]; 2292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < kNumPositions; ++i) { 2302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) positions[i] = kPositionArray[i]; 2312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::reverse(&positions[0], &positions[kNumPositions]); 2342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::sort(&positions[0], &positions[kNumPositions], PositionLessThan()); 2352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < kNumPositions; ++i) { 2362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_TRUE(positions[i].Equals(kSortedPositionArray[i])) 2372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << "i: " << i << ", " 2382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << positions[i].ToDebugString() << " != " 2392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << kSortedPositionArray[i].ToDebugString(); 2402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class PositionInsertTest : 2442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public RelativePositioningTest, 2452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public ::testing::WithParamInterface<std::string> { }; 2462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Exercise InsertBetween with various insertion operations. 2482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_P(PositionInsertTest, InsertBetween) { 2492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string suffix = GetParam(); 2502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_TRUE(UniquePosition::IsValidSuffix(suffix)); 2512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < kNumSortedPositions; ++i) { 2532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition& predecessor = kSortedPositionArray[i]; 2542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Verify our suffixes are unique before we continue. 2552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (IsSuffixInUse(predecessor, suffix)) 2562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) continue; 2572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t j = i + 1; j < kNumSortedPositions; ++j) { 2592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition& successor = kSortedPositionArray[j]; 2602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Another guard against non-unique suffixes. 2622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (IsSuffixInUse(successor, suffix)) 2632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) continue; 2642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition midpoint = 2662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition::Between(predecessor, successor, suffix); 2672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_PRED_FORMAT2(LessThan, predecessor, midpoint); 2692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_PRED_FORMAT2(LessThan, midpoint, successor); 2702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_P(PositionInsertTest, InsertBefore) { 2752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string suffix = GetParam(); 2762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < kNumSortedPositions; ++i) { 2772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition& successor = kSortedPositionArray[i]; 2782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Verify our suffixes are unique before we continue. 2792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (IsSuffixInUse(successor, suffix)) 2802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) continue; 2812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition before = UniquePosition::Before(successor, suffix); 2832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_PRED_FORMAT2(LessThan, before, successor); 2852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_P(PositionInsertTest, InsertAfter) { 2892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string suffix = GetParam(); 2902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < kNumSortedPositions; ++i) { 2912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition& predecessor = kSortedPositionArray[i]; 2922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Verify our suffixes are unique before we continue. 2932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (IsSuffixInUse(predecessor, suffix)) 2942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) continue; 2952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition after = UniquePosition::After(predecessor, suffix); 2972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_PRED_FORMAT2(LessThan, predecessor, after); 2992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_P(PositionInsertTest, StressInsertAfter) { 3032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Use two different suffixes to not violate our suffix uniqueness guarantee. 3042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix_a = GetParam(); 3052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string suffix_b = suffix_a; 3062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) suffix_b[10] = suffix_b[10] ^ 0xff; 3072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition pos = UniquePosition::InitialPosition(suffix_a); 3092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int i = 0; i < 1024; i++) { 3102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a; 3112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition next_pos = UniquePosition::After(pos, suffix); 3122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_PRED_FORMAT2(LessThan, pos, next_pos); 3132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pos = next_pos; 3142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VLOG(1) << "Length: " << GetLength(pos); 3172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_P(PositionInsertTest, StressInsertBefore) { 3202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Use two different suffixes to not violate our suffix uniqueness guarantee. 3212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix_a = GetParam(); 3222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string suffix_b = suffix_a; 3232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) suffix_b[10] = suffix_b[10] ^ 0xff; 3242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition pos = UniquePosition::InitialPosition(suffix_a); 3262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int i = 0; i < 1024; i++) { 3272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a; 3282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition prev_pos = UniquePosition::Before(pos, suffix); 3292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_PRED_FORMAT2(LessThan, prev_pos, pos); 3302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pos = prev_pos; 3312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VLOG(1) << "Length: " << GetLength(pos); 3342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_P(PositionInsertTest, StressLeftInsertBetween) { 3372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Use different suffixes to not violate our suffix uniqueness guarantee. 3382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix_a = GetParam(); 3392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string suffix_b = suffix_a; 3402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) suffix_b[10] = suffix_b[10] ^ 0xff; 3412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string suffix_c = suffix_a; 3422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) suffix_c[10] = suffix_c[10] ^ 0xf0; 3432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition right_pos = UniquePosition::InitialPosition(suffix_c); 3452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition left_pos = UniquePosition::Before(right_pos, suffix_a); 3462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int i = 0; i < 1024; i++) { 3472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a; 3482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition new_pos = 3492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition::Between(left_pos, right_pos, suffix); 3502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_PRED_FORMAT2(LessThan, left_pos, new_pos); 3512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_PRED_FORMAT2(LessThan, new_pos, right_pos); 3522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) left_pos = new_pos; 3532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VLOG(1) << "Lengths: " << GetLength(left_pos) << ", " << GetLength(right_pos); 3562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_P(PositionInsertTest, StressRightInsertBetween) { 3592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Use different suffixes to not violate our suffix uniqueness guarantee. 3602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix_a = GetParam(); 3612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string suffix_b = suffix_a; 3622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) suffix_b[10] = suffix_b[10] ^ 0xff; 3632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string suffix_c = suffix_a; 3642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) suffix_c[10] = suffix_c[10] ^ 0xf0; 3652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition right_pos = UniquePosition::InitialPosition(suffix_a); 3672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition left_pos = UniquePosition::Before(right_pos, suffix_c); 3682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int i = 0; i < 1024; i++) { 3692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a; 3702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition new_pos = 3712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition::Between(left_pos, right_pos, suffix); 3722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_PRED_FORMAT2(LessThan, left_pos, new_pos); 3732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_PRED_FORMAT2(LessThan, new_pos, right_pos); 3742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) right_pos = new_pos; 3752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VLOG(1) << "Lengths: " << GetLength(left_pos) << ", " << GetLength(right_pos); 3782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Generates suffixes similar to those generated by the directory. 3812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This may become obsolete if the suffix generation code is modified. 3822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class SuffixGenerator { 3832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 3842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) explicit SuffixGenerator(const std::string& cache_guid) 3852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : cache_guid_(cache_guid), 3862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) next_id_(-65535) { 3872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string NextSuffix() { 3902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // This is not entirely realistic, but that should be OK. The current 3912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // suffix format is a base64'ed SHA1 hash, which should be fairly close to 3922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // random anyway. 3932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string input = cache_guid_ + base::Int64ToString(next_id_--); 3942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string output; 395a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) base::Base64Encode(base::SHA1HashString(input), &output); 3962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return output; 3972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 4002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string cache_guid_; 4012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64 next_id_; 4022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 4032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Cache guids generated in the same style as real clients. 4052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static const char kCacheGuidStr1[] = "tuiWdG8hV+8y4RT9N5Aikg=="; 4062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static const char kCacheGuidStr2[] = "yaKb7zHtY06aue9a0vlZgw=="; 4072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class PositionScenariosTest : public UniquePositionTest { 4092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 4102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PositionScenariosTest() 4112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : generator1_(std::string(kCacheGuidStr1, arraysize(kCacheGuidStr1)-1)), 4122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) generator2_(std::string(kCacheGuidStr2, arraysize(kCacheGuidStr2)-1)) { 4132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string NextClient1Suffix() { 4162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return generator1_.NextSuffix(); 4172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string NextClient2Suffix() { 4202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return generator2_.NextSuffix(); 4212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 4242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SuffixGenerator generator1_; 4252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SuffixGenerator generator2_; 4262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 4272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// One client creating new bookmarks, always inserting at the end. 4292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_F(PositionScenariosTest, OneClientInsertAtEnd) { 4302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition pos = 4312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition::InitialPosition(NextClient1Suffix()); 4322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int i = 0; i < 1024; i++) { 4332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::string suffix = NextClient1Suffix(); 4342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition new_pos = UniquePosition::After(pos, suffix); 4352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_PRED_FORMAT2(LessThan, pos, new_pos); 4362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pos = new_pos; 4372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VLOG(1) << "Length: " << GetLength(pos); 4402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Normally we wouldn't want to make an assertion about the internal 4422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // representation of our data, but we make an exception for this case. 4432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // If this scenario causes lengths to explode, we have a big problem. 4442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_LT(GetLength(pos), 500U); 4452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Two clients alternately inserting entries at the end, with a strong 4482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// bias towards insertions by the first client. 4492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_F(PositionScenariosTest, TwoClientsInsertAtEnd_A) { 4502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition pos = 4512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition::InitialPosition(NextClient1Suffix()); 4522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int i = 0; i < 1024; i++) { 4532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string suffix; 4542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (i % 5 == 0) { 4552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) suffix = NextClient2Suffix(); 4562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else { 4572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) suffix = NextClient1Suffix(); 4582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition new_pos = UniquePosition::After(pos, suffix); 4612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_PRED_FORMAT2(LessThan, pos, new_pos); 4622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pos = new_pos; 4632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VLOG(1) << "Length: " << GetLength(pos); 4662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_LT(GetLength(pos), 500U); 4672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Two clients alternately inserting entries at the end. 4702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_F(PositionScenariosTest, TwoClientsInsertAtEnd_B) { 4712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition pos = 4722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition::InitialPosition(NextClient1Suffix()); 4732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int i = 0; i < 1024; i++) { 4742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string suffix; 4752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (i % 2 == 0) { 4762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) suffix = NextClient1Suffix(); 4772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else { 4782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) suffix = NextClient2Suffix(); 4792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition new_pos = UniquePosition::After(pos, suffix); 4822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ASSERT_PRED_FORMAT2(LessThan, pos, new_pos); 4832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pos = new_pos; 4842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) VLOG(1) << "Length: " << GetLength(pos); 4872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_LT(GetLength(pos), 500U); 4882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)INSTANTIATE_TEST_CASE_P(MinSuffix, PositionInsertTest, 4912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ::testing::Values(kMinSuffix)); 4922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)INSTANTIATE_TEST_CASE_P(MaxSuffix, PositionInsertTest, 4932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ::testing::Values(kMaxSuffix)); 4942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)INSTANTIATE_TEST_CASE_P(NormalSuffix, PositionInsertTest, 4952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ::testing::Values(kNormalSuffix)); 4962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class PositionFromIntTest : public UniquePositionTest { 4982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 4992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PositionFromIntTest() 5002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : generator_(std::string(kCacheGuidStr1, arraysize(kCacheGuidStr1)-1)) { 5012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) protected: 5047dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch static const int64 kTestValues[]; 5057dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch static const size_t kNumTestValues; 5067dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 5072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string NextSuffix() { 5082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return generator_.NextSuffix(); 5092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 5122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SuffixGenerator generator_; 5132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 5142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5157dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdochconst int64 PositionFromIntTest::kTestValues[] = { 5162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0LL, 5172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1LL, -1LL, 5182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2LL, -2LL, 5192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3LL, -3LL, 5202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0x79LL, -0x79LL, 5212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0x80LL, -0x80LL, 5222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0x81LL, -0x81LL, 5232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0xFELL, -0xFELL, 5242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0xFFLL, -0xFFLL, 5252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0x100LL, -0x100LL, 5262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0x101LL, -0x101LL, 5272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0xFA1AFELL, -0xFA1AFELL, 5282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0xFFFFFFFELL, -0xFFFFFFFELL, 5292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0xFFFFFFFFLL, -0xFFFFFFFFLL, 5302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0x100000000LL, -0x100000000LL, 5312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0x100000001LL, -0x100000001LL, 5322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0xFFFFFFFFFFLL, -0xFFFFFFFFFFLL, 5332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0x112358132134LL, -0x112358132134LL, 5342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 0xFEFFBEEFABC1234LL, -0xFEFFBEEFABC1234LL, 5352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kint64max, 5362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kint64min, 5372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kint64min + 1, 5382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kint64max - 1 5392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 5402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5417dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdochconst size_t PositionFromIntTest::kNumTestValues = 5427dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdocharraysize(PositionFromIntTest::kTestValues); 5432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_F(PositionFromIntTest, IsValid) { 5452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < kNumTestValues; ++i) { 5462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition pos = 5472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition::FromInt64(kTestValues[i], NextSuffix()); 5482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_TRUE(pos.IsValid()) << "i = " << i << "; " << pos.ToDebugString(); 5492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 5512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_F(PositionFromIntTest, RoundTripConversion) { 5532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < kNumTestValues; ++i) { 5542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const int64 expected_value = kTestValues[i]; 5552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const UniquePosition pos = 5562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition::FromInt64(kTestValues[i], NextSuffix()); 5572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const int64 value = pos.ToInt64(); 5582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_EQ(expected_value, value) << "i = " << i; 5592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 5612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <typename T, typename LessThan = std::less<T> > 5632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class IndexedLessThan { 5642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 5652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) IndexedLessThan(const T* values) : values_(values) {} 5662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool operator()(int i1, int i2) { 5682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return less_than_(values_[i1], values_[i2]); 5692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 5722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const T* values_; 5732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LessThan less_than_; 5742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 5752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)TEST_F(PositionFromIntTest, ConsistentOrdering) { 5772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UniquePosition positions[kNumTestValues]; 5782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<int> original_ordering(kNumTestValues); 5792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<int> int64_ordering(kNumTestValues); 5802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<int> position_ordering(kNumTestValues); 5812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < kNumTestValues; ++i) { 5822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) positions[i] = UniquePosition::FromInt64( 5832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kTestValues[i], NextSuffix()); 5842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) original_ordering[i] = int64_ordering[i] = position_ordering[i] = i; 5852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::sort(int64_ordering.begin(), int64_ordering.end(), 5882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) IndexedLessThan<int64>(kTestValues)); 5892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::sort(position_ordering.begin(), position_ordering.end(), 5902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) IndexedLessThan<UniquePosition, PositionLessThan>(positions)); 5912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_NE(original_ordering, int64_ordering); 5922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EXPECT_EQ(int64_ordering, position_ordering); 5932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 5942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5957dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdochclass CompressedPositionTest : public UniquePositionTest { 5967dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch public: 5977dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch CompressedPositionTest() { 5987dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch positions_.push_back( 5997dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch MakePosition( // Prefix starts with 256 0x00s 6007dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch std::string("\x00\x00\x00\x00\xFF\xFF\xFE\xFF" "\x01", 9), 6017dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch MakeSuffix('\x04'))); 6027dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch positions_.push_back( 6037dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch MakePosition( // Prefix starts with four 0x00s 6047dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch std::string("\x00\x00\x00\x00\xFF\xFF\xFF\xFB" "\x01", 9), 6057dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch MakeSuffix('\x03'))); 6067dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch positions_.push_back( 6077dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch MakePosition( // Prefix starts with four 0xFFs 6087dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch std::string("\xFF\xFF\xFF\xFF\x00\x00\x00\x04" "\x01", 9), 6097dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch MakeSuffix('\x01'))); 6107dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch positions_.push_back( 6117dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch MakePosition( // Prefix starts with 256 0xFFs 6127dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch std::string("\xFF\xFF\xFF\xFF\x00\x00\x01\x00" "\x01", 9), 6137dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch MakeSuffix('\x02'))); 6147dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch } 6157dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 6167dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch private: 6177dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch UniquePosition MakePosition(const std::string& compressed_prefix, 6187dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch const std::string& compressed_suffix); 6197dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch std::string MakeSuffix(char unique_value); 6207dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 6217dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch protected: 6227dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch std::vector<UniquePosition> positions_; 6237dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch}; 6247dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 6257dbb3d5cf0c15f500944d211057644d6a2f37371Ben MurdochUniquePosition CompressedPositionTest::MakePosition( 6267dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch const std::string& compressed_prefix, 6277dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch const std::string& compressed_suffix) { 6287dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch sync_pb::UniquePosition proto; 6297dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch proto.set_custom_compressed_v1( 6307dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch std::string(compressed_prefix + compressed_suffix)); 6317dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch return UniquePosition::FromProto(proto); 6327dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch} 6337dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 6347dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdochstd::string CompressedPositionTest::MakeSuffix(char unique_value) { 6357dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // We're dealing in compressed positions in this test. That means the 6367dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // suffix should be compressed, too. To avoid complication, we use suffixes 6377dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // that don't have any repeating digits, and therefore are identical in 6387dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch // compressed and uncompressed form. 6397dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch std::string suffix; 6407dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch for (size_t i = 0; i < UniquePosition::kSuffixLength; ++i) { 6417dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch suffix.push_back(static_cast<char>(i)); 6427dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch } 6437dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch suffix[UniquePosition::kSuffixLength-1] = unique_value; 6447dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch return suffix; 6457dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch} 6467dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 6477dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch// Make sure that serialization and deserialization routines are correct. 6487dbb3d5cf0c15f500944d211057644d6a2f37371Ben MurdochTEST_F(CompressedPositionTest, SerializeAndDeserialize) { 6497dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch for (std::vector<UniquePosition>::const_iterator it = positions_.begin(); 6507dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch it != positions_.end(); ++it) { 6517dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch SCOPED_TRACE("iteration: " + it->ToDebugString()); 6527dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 6537dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch sync_pb::UniquePosition proto; 6547dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch it->ToProto(&proto); 6557dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch UniquePosition deserialized = UniquePosition::FromProto(proto); 6567dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 6577dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch EXPECT_PRED_FORMAT2(Equals, *it, deserialized); 6587dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch } 6597dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch} 6607dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 661f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)// Test that deserialization failures of protobufs where we know none of its 662f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)// fields is not catastrophic. This may happen if all the fields currently 663f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)// known to this client become deprecated in the future. 664f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)TEST_F(CompressedPositionTest, DeserializeProtobufFromTheFuture) { 665f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) sync_pb::UniquePosition proto; 666f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) UniquePosition deserialized = UniquePosition::FromProto(proto); 667f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) EXPECT_FALSE(deserialized.IsValid()); 6687dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch} 6697dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 6707dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch// Make sure the comparison functions are working correctly. 6717dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch// This requires values in the test harness to be hard-coded in ascending order. 6727dbb3d5cf0c15f500944d211057644d6a2f37371Ben MurdochTEST_F(CompressedPositionTest, OrderingTest) { 6737dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch for (size_t i = 0; i < positions_.size()-1; ++i) { 6747dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch EXPECT_PRED_FORMAT2(LessThan, positions_[i], positions_[i+1]); 6757dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch } 6767dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch} 6777dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch 6782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // namespace 6792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // namespace syncer 681