1// Copyright 2013 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 <string>
6#include <utility>
7#include <vector>
8#include "chrome/common/instant_restricted_id_cache.h"
9#include "testing/gtest/include/gtest/gtest.h"
10
11namespace {
12
13struct TestData {
14  TestData() {}
15  explicit TestData(const std::string& i_value) : value(i_value) {}
16
17  bool operator==(const TestData& rhs) const {
18    return rhs.value == value;
19  }
20
21  std::string value;
22};
23
24// For printing failures nicely.
25void PrintTo(const TestData& data, std::ostream* os) {
26  *os << data.value;
27}
28
29}  // namespace
30
31typedef testing::Test InstantRestrictedIDCacheTest;
32typedef InstantRestrictedIDCache<TestData>::ItemIDPair ItemIDPair;
33
34TEST_F(InstantRestrictedIDCacheTest, AutoIDGeneration) {
35  InstantRestrictedIDCache<TestData> cache(7);
36  EXPECT_EQ(0u, cache.cache_.size());
37  EXPECT_EQ(0, cache.last_restricted_id_);
38
39  // Check first addition.
40  std::vector<TestData> input1;
41  input1.push_back(TestData("A"));
42  input1.push_back(TestData("B"));
43  input1.push_back(TestData("C"));
44  cache.AddItems(input1);
45  EXPECT_EQ(3u, cache.cache_.size());
46  EXPECT_EQ(3, cache.last_restricted_id_);
47
48  std::vector<ItemIDPair> output;
49  cache.GetCurrentItems(&output);
50  EXPECT_EQ(3u, output.size());
51  for (int i = 0; i < 3; ++i) {
52    EXPECT_EQ(i + 1, output[i].first);
53    EXPECT_EQ(input1[i], output[i].second);
54  }
55
56  TestData t;
57  EXPECT_FALSE(cache.GetItemWithRestrictedID(4, &t));
58  EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t));
59  EXPECT_EQ(input1[2], t);
60
61  // Add more items, no overflow.
62  std::vector<TestData> input2;
63  input2.push_back(TestData("D"));
64  input2.push_back(TestData("E"));
65  cache.AddItems(input2);
66  EXPECT_EQ(5u, cache.cache_.size());
67  EXPECT_EQ(5, cache.last_restricted_id_);
68
69  output.clear();
70  cache.GetCurrentItems(&output);
71  EXPECT_EQ(2u, output.size());
72  for (int i = 0; i < 2; ++i) {
73    EXPECT_EQ(i + 4, output[i].first);
74    EXPECT_EQ(input2[i], output[i].second);
75  }
76
77  EXPECT_FALSE(cache.GetItemWithRestrictedID(6, &t));
78  EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t));
79  EXPECT_EQ(input1[2], t);
80  EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
81  EXPECT_EQ(input2[1], t);
82
83  // Add another set, overflows.
84  std::vector<TestData> input3;
85  input3.push_back(TestData("F"));
86  input3.push_back(TestData("G"));
87  input3.push_back(TestData("H"));
88  input3.push_back(TestData("I"));
89  cache.AddItems(input3);
90  EXPECT_EQ(7u, cache.cache_.size());
91  EXPECT_EQ(9, cache.last_restricted_id_);
92
93  output.clear();
94  cache.GetCurrentItems(&output);
95  EXPECT_EQ(4u, output.size());
96  for (int i = 0; i < 3; ++i) {
97    EXPECT_EQ(i + 6, output[i].first);
98    EXPECT_EQ(input3[i], output[i].second);
99  }
100
101  EXPECT_FALSE(cache.GetItemWithRestrictedID(1, &t));
102  EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t));
103  EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t));
104  EXPECT_EQ(input1[2], t);
105  EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
106  EXPECT_EQ(input2[1], t);
107  EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
108  EXPECT_EQ(input3[1], t);
109}
110
111TEST_F(InstantRestrictedIDCacheTest, ManualIDGeneration) {
112  InstantRestrictedIDCache<TestData> cache(5);
113  EXPECT_EQ(0u, cache.cache_.size());
114  EXPECT_EQ(0, cache.last_restricted_id_);
115
116  // Check first addition.
117  std::vector<ItemIDPair> input1;
118  input1.push_back(std::make_pair(1, TestData("A")));
119  input1.push_back(std::make_pair(2, TestData("B")));
120  input1.push_back(std::make_pair(4, TestData("C")));
121  cache.AddItemsWithRestrictedID(input1);
122  EXPECT_EQ(3u, cache.cache_.size());
123  EXPECT_EQ(4, cache.last_restricted_id_);
124
125  std::vector<ItemIDPair> output;
126  cache.GetCurrentItems(&output);
127  EXPECT_EQ(3u, output.size());
128  for (int i = 0; i < 3; ++i) {
129    EXPECT_EQ(input1[i].first, output[i].first);
130    EXPECT_EQ(input1[i].second, output[i].second);
131  }
132
133  TestData t;
134  EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
135  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
136  EXPECT_EQ(input1[2].second, t);
137
138
139  // Add more items, one with same rid, no overflow.
140  std::vector<ItemIDPair> input2;
141  input2.push_back(std::make_pair(4, TestData("D")));
142  input2.push_back(std::make_pair(7, TestData("E")));
143  cache.AddItemsWithRestrictedID(input2);
144  EXPECT_EQ(4u, cache.cache_.size());
145  EXPECT_EQ(7, cache.last_restricted_id_);
146
147  output.clear();
148  cache.GetCurrentItems(&output);
149  EXPECT_EQ(2u, output.size());
150  for (int i = 0; i < 2; ++i) {
151    EXPECT_EQ(input2[i].first, output[i].first);
152    EXPECT_EQ(input2[i].second, output[i].second);
153  }
154
155  EXPECT_FALSE(cache.GetItemWithRestrictedID(6, &t));
156  EXPECT_TRUE(cache.GetItemWithRestrictedID(2, &t));
157  EXPECT_EQ(input1[1].second, t);
158  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
159  EXPECT_EQ(input2[0].second, t);
160  EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
161  EXPECT_EQ(input2[1].second, t);
162
163  // Add another set, duplicate rids, overflows.
164  std::vector<ItemIDPair> input3;
165  input3.push_back(std::make_pair(1, TestData("F")));
166  input3.push_back(std::make_pair(6, TestData("G")));
167  input3.push_back(std::make_pair(9, TestData("H")));
168  cache.AddItemsWithRestrictedID(input3);
169  EXPECT_EQ(5u, cache.cache_.size());
170  EXPECT_EQ(9, cache.last_restricted_id_);
171
172  output.clear();
173  cache.GetCurrentItems(&output);
174  EXPECT_EQ(3u, output.size());
175  for (int i = 0; i < 3; ++i) {
176    EXPECT_EQ(input3[i].first, output[i].first);
177    EXPECT_EQ(input3[i].second, output[i].second);
178  }
179
180  EXPECT_TRUE(cache.GetItemWithRestrictedID(1, &t));
181  EXPECT_EQ(input3[0].second, t);
182  EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t));
183  EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
184  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
185  EXPECT_EQ(input2[0].second, t);
186  EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
187  EXPECT_EQ(input2[1].second, t);
188  EXPECT_FALSE(cache.GetItemWithRestrictedID(8, &t));
189  EXPECT_TRUE(cache.GetItemWithRestrictedID(9, &t));
190  EXPECT_EQ(input3[2].second, t);
191}
192
193TEST_F(InstantRestrictedIDCacheTest, CrazyIDGeneration) {
194  InstantRestrictedIDCache<TestData> cache(4);
195  EXPECT_EQ(0u, cache.cache_.size());
196  EXPECT_EQ(0, cache.last_restricted_id_);
197
198  // Check first addition.
199  std::vector<ItemIDPair> input1;
200  input1.push_back(std::make_pair(0, TestData("A")));
201  input1.push_back(std::make_pair(kint32max, TestData("B")));
202  input1.push_back(std::make_pair(-100, TestData("C")));
203  cache.AddItemsWithRestrictedID(input1);
204  EXPECT_EQ(3u, cache.cache_.size());
205  EXPECT_EQ(kint32max, cache.last_restricted_id_);
206
207  std::vector<ItemIDPair> output;
208  cache.GetCurrentItems(&output);
209  EXPECT_EQ(3u, output.size());
210  for (int i = 0; i < 3; ++i) {
211    EXPECT_EQ(input1[i].first, output[i].first);
212    EXPECT_EQ(input1[i].second, output[i].second);
213  }
214
215  TestData t;
216  EXPECT_FALSE(cache.GetItemWithRestrictedID(1, &t));
217  EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32max, &t));
218  EXPECT_EQ(input1[1].second, t);
219  EXPECT_TRUE(cache.GetItemWithRestrictedID(-100, &t));
220  EXPECT_EQ(input1[2].second, t);
221
222  // Add more items, one with same rid, no overflow.
223  std::vector<ItemIDPair> input2;
224  input2.push_back(std::make_pair(kint32min, TestData("D")));
225  input2.push_back(std::make_pair(7, TestData("E")));
226  cache.AddItemsWithRestrictedID(input2);
227  EXPECT_EQ(4u, cache.cache_.size());
228  EXPECT_EQ(kint32max, cache.last_restricted_id_);
229
230  output.clear();
231  cache.GetCurrentItems(&output);
232  EXPECT_EQ(2u, output.size());
233  for (int i = 0; i < 2; ++i) {
234    EXPECT_EQ(input2[i].first, output[i].first);
235    EXPECT_EQ(input2[i].second, output[i].second);
236  }
237
238  EXPECT_FALSE(cache.GetItemWithRestrictedID(0, &t));
239  EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32max, &t));
240  EXPECT_EQ(input1[1].second, t);
241  EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32min, &t));
242  EXPECT_EQ(input2[0].second, t);
243  EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
244  EXPECT_EQ(input2[1].second, t);
245
246  // Add an item without RID. last_restricted_id_ will overflow.
247  std::vector<TestData> input3;
248  input3.push_back(TestData("F"));
249  input3.push_back(TestData("G"));
250  cache.AddItems(input3);
251  EXPECT_EQ(4u, cache.cache_.size());
252  EXPECT_EQ(kint32min + 1, cache.last_restricted_id_);
253
254  output.clear();
255  cache.GetCurrentItems(&output);
256  EXPECT_EQ(2u, output.size());
257  for (int i = 0; i < 2; ++i) {
258    EXPECT_EQ(kint32min + i, output[i].first);
259    EXPECT_EQ(input3[i], output[i].second);
260  }
261
262  EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32min, &t));
263  EXPECT_EQ(input3[0], t);
264}
265
266TEST_F(InstantRestrictedIDCacheTest, MixIDGeneration) {
267  InstantRestrictedIDCache<TestData> cache(5);
268  EXPECT_EQ(0u, cache.cache_.size());
269  EXPECT_EQ(0, cache.last_restricted_id_);
270
271  // Add some items with manually assigned ids.
272  std::vector<ItemIDPair> input1;
273  input1.push_back(std::make_pair(1, TestData("A")));
274  input1.push_back(std::make_pair(2, TestData("B")));
275  input1.push_back(std::make_pair(4, TestData("C")));
276  cache.AddItemsWithRestrictedID(input1);
277  EXPECT_EQ(3u, cache.cache_.size());
278  EXPECT_EQ(4, cache.last_restricted_id_);
279
280  std::vector<ItemIDPair> output;
281  cache.GetCurrentItems(&output);
282  EXPECT_EQ(3u, output.size());
283  for (int i = 0; i < 3; ++i) {
284    EXPECT_EQ(input1[i].first, output[i].first);
285    EXPECT_EQ(input1[i].second, output[i].second);
286  }
287
288  TestData t;
289  EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
290  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
291  EXPECT_EQ(input1[2].second, t);
292
293  // Add items with auto id generation.
294  std::vector<TestData> input2;
295  input2.push_back(TestData("D"));
296  input2.push_back(TestData("E"));
297  cache.AddItems(input2);
298  EXPECT_EQ(5u, cache.cache_.size());
299  EXPECT_EQ(6, cache.last_restricted_id_);
300
301  output.clear();
302  cache.GetCurrentItems(&output);
303  EXPECT_EQ(2u, output.size());
304  for (int i = 0; i < 2; ++i) {
305    EXPECT_EQ(i + 5, output[i].first);
306    EXPECT_EQ(input2[i], output[i].second);
307  }
308
309  EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
310  EXPECT_TRUE(cache.GetItemWithRestrictedID(2, &t));
311  EXPECT_EQ(input1[1].second, t);
312  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
313  EXPECT_EQ(input1[2].second, t);
314  EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
315  EXPECT_EQ(input2[0], t);
316  EXPECT_TRUE(cache.GetItemWithRestrictedID(6, &t));
317  EXPECT_EQ(input2[1], t);
318  EXPECT_FALSE(cache.GetItemWithRestrictedID(7, &t));
319
320  // Add manually assigned ids again.
321  std::vector<ItemIDPair> input3;
322  input3.push_back(std::make_pair(1, TestData("F")));
323  input3.push_back(std::make_pair(5, TestData("G")));
324  input3.push_back(std::make_pair(7, TestData("H")));
325  cache.AddItemsWithRestrictedID(input3);
326  EXPECT_EQ(5u, cache.cache_.size());
327  EXPECT_EQ(7, cache.last_restricted_id_);
328
329  output.clear();
330  cache.GetCurrentItems(&output);
331  EXPECT_EQ(3u, output.size());
332  for (int i = 0; i < 2; ++i) {
333    EXPECT_EQ(input3[i].first, output[i].first);
334    EXPECT_EQ(input3[i].second, output[i].second);
335  }
336
337  EXPECT_TRUE(cache.GetItemWithRestrictedID(1, &t));
338  EXPECT_EQ(input3[0].second, t);
339  EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t));
340  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
341  EXPECT_EQ(input1[2].second, t);
342  EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
343  EXPECT_EQ(input3[1].second, t);
344  EXPECT_TRUE(cache.GetItemWithRestrictedID(6, &t));
345  EXPECT_EQ(input2[1], t);
346  EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
347  EXPECT_EQ(input3[2].second, t);
348}
349
350TEST_F(InstantRestrictedIDCacheTest, AddEmptySet) {
351  InstantRestrictedIDCache<TestData> cache(9);
352  EXPECT_EQ(0u, cache.cache_.size());
353  EXPECT_EQ(0, cache.last_restricted_id_);
354
355  // Add a non-empty set of items.
356  std::vector<TestData> input1;
357  input1.push_back(TestData("A"));
358  input1.push_back(TestData("B"));
359  input1.push_back(TestData("C"));
360  cache.AddItems(input1);
361  EXPECT_EQ(3u, cache.cache_.size());
362  EXPECT_EQ(3, cache.last_restricted_id_);
363
364  std::vector<ItemIDPair> output;
365  cache.GetCurrentItems(&output);
366  EXPECT_EQ(3u, output.size());
367
368  // Add an empty set.
369  cache.AddItems(std::vector<TestData>());
370  EXPECT_EQ(3u, cache.cache_.size());
371  EXPECT_EQ(3, cache.last_restricted_id_);
372
373  cache.GetCurrentItems(&output);
374  EXPECT_TRUE(output.empty());
375
376  // Manual IDs.
377  std::vector<ItemIDPair> input2;
378  input2.push_back(std::make_pair(10, TestData("A")));
379  input2.push_back(std::make_pair(11, TestData("B")));
380  input2.push_back(std::make_pair(12, TestData("C")));
381  cache.AddItemsWithRestrictedID(input2);
382  EXPECT_EQ(6u, cache.cache_.size());
383  EXPECT_EQ(12, cache.last_restricted_id_);
384
385  cache.GetCurrentItems(&output);
386  EXPECT_EQ(3u, output.size());
387
388  cache.AddItemsWithRestrictedID(std::vector<ItemIDPair>());
389  EXPECT_EQ(6u, cache.cache_.size());
390  EXPECT_EQ(12, cache.last_restricted_id_);
391
392  cache.GetCurrentItems(&output);
393  EXPECT_TRUE(output.empty());
394}
395
396TEST_F(InstantRestrictedIDCacheTest, AddItemsWithRestrictedID) {
397  InstantRestrictedIDCache<TestData> cache(29);
398  EXPECT_EQ(0u, cache.cache_.size());
399  EXPECT_EQ(0, cache.last_restricted_id_);
400
401  std::vector<ItemIDPair> input1;
402  input1.push_back(std::make_pair(10, TestData("A")));
403  input1.push_back(std::make_pair(11, TestData("B")));
404  input1.push_back(std::make_pair(12, TestData("C")));
405  cache.AddItemsWithRestrictedID(input1);
406  EXPECT_EQ(3u, cache.cache_.size());
407  EXPECT_EQ(12, cache.last_restricted_id_);
408  EXPECT_EQ(10, cache.last_add_start_->first);
409
410  std::vector<ItemIDPair> output;
411  cache.GetCurrentItems(&output);
412  EXPECT_EQ(3u, output.size());
413
414  // Add the same items again.
415  cache.AddItemsWithRestrictedID(input1);
416
417  // Make sure |cache.last_add_start_| is still valid.
418  cache.GetCurrentItems(&output);
419  EXPECT_EQ(3u, output.size());
420  EXPECT_EQ(3u, cache.cache_.size());
421  EXPECT_EQ(12, cache.last_restricted_id_);
422  EXPECT_EQ(10, cache.last_add_start_->first);
423}
424