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
12namespace syncer {
13
14namespace {
15
16const 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
42const size_t kNumTestValues = arraysize(kTestValues);
43
44// Convert each test value to an ordinal.  All ordinals should be
45// valid.
46TEST(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.
56TEST(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.
70TEST(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
79template <typename T, typename LessThan = std::less<T> >
80class IndexedLessThan {
81 public:
82  IndexedLessThan(const T* values) : values_(values) {}
83
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.
96TEST(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.
116TEST(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