15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sync/internal_api/public/base/node_ordinal.h" 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "testing/gtest/include/gtest/gtest.h" 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <cstddef> 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace syncer { 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int64 kTestValues[] = { 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0LL, 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1LL, -1LL, 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2LL, -2LL, 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3LL, -3LL, 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0x79LL, -0x79LL, 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0x80LL, -0x80LL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0x81LL, -0x81LL, 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0xFELL, -0xFELL, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0xFFLL, -0xFFLL, 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0x100LL, -0x100LL, 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0x101LL, -0x101LL, 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0xFA1AFELL, -0xFA1AFELL, 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0xFFFFFFFELL, -0xFFFFFFFELL, 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0xFFFFFFFFLL, -0xFFFFFFFFLL, 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0x100000000LL, -0x100000000LL, 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0x100000001LL, -0x100000001LL, 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0xFFFFFFFFFFLL, -0xFFFFFFFFFFLL, 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0x112358132134LL, -0x112358132134LL, 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0xFEFFBEEFABC1234LL, -0xFEFFBEEFABC1234LL, 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kint64max, 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kint64min, 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kint64min + 1, 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kint64max - 1 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const size_t kNumTestValues = arraysize(kTestValues); 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Convert each test value to an ordinal. All ordinals should be 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// valid. 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(NodeOrdinalTest, IsValid) { 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < kNumTestValues; ++i) { 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const NodeOrdinal ordinal = Int64ToNodeOrdinal(kTestValues[i]); 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_TRUE(ordinal.IsValid()) << "i = " << i; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Convert each test value to an ordinal. All ordinals should have 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 8-byte strings, except for kint64min, which should have a 9-byte 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// string. 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(NodeOrdinalTest, Size) { 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(9U, Int64ToNodeOrdinal(kint64min).ToInternalValue().size()); 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < kNumTestValues; ++i) { 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (kTestValues[i] == kint64min) { 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const NodeOrdinal ordinal = Int64ToNodeOrdinal(kTestValues[i]); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(8U, ordinal.ToInternalValue().size()) << "i = " << i; 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Convert each test value to an ordinal and back. That resulting 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// value should be equal to the original value. 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(NodeOrdinalTest, PositionToOrdinalToPosition) { 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < kNumTestValues; ++i) { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int64 expected_value = kTestValues[i]; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const NodeOrdinal ordinal = Int64ToNodeOrdinal(expected_value); 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int64 value = NodeOrdinalToInt64(ordinal); 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(expected_value, value) << "i = " << i; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename T, typename LessThan = std::less<T> > 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class IndexedLessThan { 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IndexedLessThan(const T* values) : values_(values) {} 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool operator()(int i1, int i2) { 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return less_than_(values_[i1], values_[i2]); 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const T* values_; 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LessThan less_than_; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Sort kTestValues by int64 value and then sort it by NodeOrdinal 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// value. kTestValues should not already be sorted (by either 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// comparator) and the two orderings should be the same. 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(NodeOrdinalTest, ConsistentOrdering) { 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeOrdinal ordinals[kNumTestValues]; 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<int> original_ordering(kNumTestValues); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<int> int64_ordering(kNumTestValues); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<int> ordinal_ordering(kNumTestValues); 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < kNumTestValues; ++i) { 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ordinals[i] = Int64ToNodeOrdinal(kTestValues[i]); 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) original_ordering[i] = int64_ordering[i] = ordinal_ordering[i] = i; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::sort(int64_ordering.begin(), int64_ordering.end(), 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IndexedLessThan<int64>(kTestValues)); 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::sort(ordinal_ordering.begin(), ordinal_ordering.end(), 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IndexedLessThan<NodeOrdinal, NodeOrdinal::LessThanFn>(ordinals)); 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_NE(original_ordering, int64_ordering); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(int64_ordering, ordinal_ordering); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Create two NodeOrdinals and create another one between them. It 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// should lie halfway between them. 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(NodeOrdinalTest, CreateBetween) { 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const NodeOrdinal ordinal1("\1\1\1\1\1\1\1\1"); 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const NodeOrdinal ordinal2("\1\1\1\1\1\1\1\3"); 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ("\1\1\1\1\1\1\1\2", 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ordinal1.CreateBetween(ordinal2).ToInternalValue()); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace syncer 126