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 #include "base/basictypes.h"
6 #include "sync/internal_api/public/base/node_ordinal.h"
7 #include "testing/gtest/include/gtest/gtest.h"
8
9 #include <algorithm>
10 #include <cstddef>
11
12 namespace syncer {
13
14 namespace {
15
16 const int64 kTestValues[] = {
17 0LL,
18 1LL, -1LL,
19 2LL, -2LL,
20 3LL, -3LL,
21 0x79LL, -0x79LL,
22 0x80LL, -0x80LL,
23 0x81LL, -0x81LL,
24 0xFELL, -0xFELL,
25 0xFFLL, -0xFFLL,
26 0x100LL, -0x100LL,
27 0x101LL, -0x101LL,
28 0xFA1AFELL, -0xFA1AFELL,
29 0xFFFFFFFELL, -0xFFFFFFFELL,
30 0xFFFFFFFFLL, -0xFFFFFFFFLL,
31 0x100000000LL, -0x100000000LL,
32 0x100000001LL, -0x100000001LL,
33 0xFFFFFFFFFFLL, -0xFFFFFFFFFFLL,
34 0x112358132134LL, -0x112358132134LL,
35 0xFEFFBEEFABC1234LL, -0xFEFFBEEFABC1234LL,
36 kint64max,
37 kint64min,
38 kint64min + 1,
39 kint64max - 1
40 };
41
42 const size_t kNumTestValues = arraysize(kTestValues);
43
44 // Convert each test value to an ordinal. All ordinals should be
45 // valid.
TEST(NodeOrdinalTest,IsValid)46 TEST(NodeOrdinalTest, IsValid) {
47 for (size_t i = 0; i < kNumTestValues; ++i) {
48 const NodeOrdinal ordinal = Int64ToNodeOrdinal(kTestValues[i]);
49 EXPECT_TRUE(ordinal.IsValid()) << "i = " << i;
50 }
51 }
52
53 // Convert each test value to an ordinal. All ordinals should have
54 // 8-byte strings, except for kint64min, which should have a 9-byte
55 // string.
TEST(NodeOrdinalTest,Size)56 TEST(NodeOrdinalTest, Size) {
57 EXPECT_EQ(9U, Int64ToNodeOrdinal(kint64min).ToInternalValue().size());
58
59 for (size_t i = 0; i < kNumTestValues; ++i) {
60 if (kTestValues[i] == kint64min) {
61 continue;
62 }
63 const NodeOrdinal ordinal = Int64ToNodeOrdinal(kTestValues[i]);
64 EXPECT_EQ(8U, ordinal.ToInternalValue().size()) << "i = " << i;
65 }
66 }
67
68 // Convert each test value to an ordinal and back. That resulting
69 // value should be equal to the original value.
TEST(NodeOrdinalTest,PositionToOrdinalToPosition)70 TEST(NodeOrdinalTest, PositionToOrdinalToPosition) {
71 for (size_t i = 0; i < kNumTestValues; ++i) {
72 const int64 expected_value = kTestValues[i];
73 const NodeOrdinal ordinal = Int64ToNodeOrdinal(expected_value);
74 const int64 value = NodeOrdinalToInt64(ordinal);
75 EXPECT_EQ(expected_value, value) << "i = " << i;
76 }
77 }
78
79 template <typename T, typename LessThan = std::less<T> >
80 class IndexedLessThan {
81 public:
IndexedLessThan(const T * values)82 IndexedLessThan(const T* values) : values_(values) {}
83
operator ()(int i1,int i2)84 bool operator()(int i1, int i2) {
85 return less_than_(values_[i1], values_[i2]);
86 }
87
88 private:
89 const T* values_;
90 LessThan less_than_;
91 };
92
93 // Sort kTestValues by int64 value and then sort it by NodeOrdinal
94 // value. kTestValues should not already be sorted (by either
95 // comparator) and the two orderings should be the same.
TEST(NodeOrdinalTest,ConsistentOrdering)96 TEST(NodeOrdinalTest, ConsistentOrdering) {
97 NodeOrdinal ordinals[kNumTestValues];
98 std::vector<int> original_ordering(kNumTestValues);
99 std::vector<int> int64_ordering(kNumTestValues);
100 std::vector<int> ordinal_ordering(kNumTestValues);
101 for (size_t i = 0; i < kNumTestValues; ++i) {
102 ordinals[i] = Int64ToNodeOrdinal(kTestValues[i]);
103 original_ordering[i] = int64_ordering[i] = ordinal_ordering[i] = i;
104 }
105
106 std::sort(int64_ordering.begin(), int64_ordering.end(),
107 IndexedLessThan<int64>(kTestValues));
108 std::sort(ordinal_ordering.begin(), ordinal_ordering.end(),
109 IndexedLessThan<NodeOrdinal, NodeOrdinal::LessThanFn>(ordinals));
110 EXPECT_NE(original_ordering, int64_ordering);
111 EXPECT_EQ(int64_ordering, ordinal_ordering);
112 }
113
114 // Create two NodeOrdinals and create another one between them. It
115 // should lie halfway between them.
TEST(NodeOrdinalTest,CreateBetween)116 TEST(NodeOrdinalTest, CreateBetween) {
117 const NodeOrdinal ordinal1("\1\1\1\1\1\1\1\1");
118 const NodeOrdinal ordinal2("\1\1\1\1\1\1\1\3");
119 EXPECT_EQ("\1\1\1\1\1\1\1\2",
120 ordinal1.CreateBetween(ordinal2).ToInternalValue());
121 }
122
123 } // namespace
124
125 } // namespace syncer
126