small_map_unittest.cc 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603
  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. #include "base/containers/small_map.h"
  5. #include <stddef.h>
  6. #include <algorithm>
  7. #include <functional>
  8. #include <map>
  9. #include <unordered_map>
  10. #include "base/logging.h"
  11. #include "testing/gtest/include/gtest/gtest.h"
  12. namespace base {
  13. TEST(SmallMap, General) {
  14. small_map<std::unordered_map<int, int>> m;
  15. EXPECT_TRUE(m.empty());
  16. m[0] = 5;
  17. EXPECT_FALSE(m.empty());
  18. EXPECT_EQ(m.size(), 1u);
  19. m[9] = 2;
  20. EXPECT_FALSE(m.empty());
  21. EXPECT_EQ(m.size(), 2u);
  22. EXPECT_EQ(m[9], 2);
  23. EXPECT_EQ(m[0], 5);
  24. EXPECT_FALSE(m.UsingFullMap());
  25. small_map<std::unordered_map<int, int>>::iterator iter(m.begin());
  26. ASSERT_TRUE(iter != m.end());
  27. EXPECT_EQ(iter->first, 0);
  28. EXPECT_EQ(iter->second, 5);
  29. ++iter;
  30. ASSERT_TRUE(iter != m.end());
  31. EXPECT_EQ((*iter).first, 9);
  32. EXPECT_EQ((*iter).second, 2);
  33. ++iter;
  34. EXPECT_TRUE(iter == m.end());
  35. m[8] = 23;
  36. m[1234] = 90;
  37. m[-5] = 6;
  38. EXPECT_EQ(m[ 9], 2);
  39. EXPECT_EQ(m[ 0], 5);
  40. EXPECT_EQ(m[1234], 90);
  41. EXPECT_EQ(m[ 8], 23);
  42. EXPECT_EQ(m[ -5], 6);
  43. EXPECT_EQ(m.size(), 5u);
  44. EXPECT_FALSE(m.empty());
  45. EXPECT_TRUE(m.UsingFullMap());
  46. iter = m.begin();
  47. for (int i = 0; i < 5; i++) {
  48. EXPECT_TRUE(iter != m.end());
  49. ++iter;
  50. }
  51. EXPECT_TRUE(iter == m.end());
  52. const small_map<std::unordered_map<int, int>>& ref = m;
  53. EXPECT_TRUE(ref.find(1234) != m.end());
  54. EXPECT_TRUE(ref.find(5678) == m.end());
  55. }
  56. TEST(SmallMap, PostFixIteratorIncrement) {
  57. small_map<std::unordered_map<int, int>> m;
  58. m[0] = 5;
  59. m[2] = 3;
  60. {
  61. small_map<std::unordered_map<int, int>>::iterator iter(m.begin());
  62. small_map<std::unordered_map<int, int>>::iterator last(iter++);
  63. ++last;
  64. EXPECT_TRUE(last == iter);
  65. }
  66. {
  67. small_map<std::unordered_map<int, int>>::const_iterator iter(m.begin());
  68. small_map<std::unordered_map<int, int>>::const_iterator last(iter++);
  69. ++last;
  70. EXPECT_TRUE(last == iter);
  71. }
  72. }
  73. // Based on the General testcase.
  74. TEST(SmallMap, CopyConstructor) {
  75. small_map<std::unordered_map<int, int>> src;
  76. {
  77. small_map<std::unordered_map<int, int>> m(src);
  78. EXPECT_TRUE(m.empty());
  79. }
  80. src[0] = 5;
  81. {
  82. small_map<std::unordered_map<int, int>> m(src);
  83. EXPECT_FALSE(m.empty());
  84. EXPECT_EQ(m.size(), 1u);
  85. }
  86. src[9] = 2;
  87. {
  88. small_map<std::unordered_map<int, int>> m(src);
  89. EXPECT_FALSE(m.empty());
  90. EXPECT_EQ(m.size(), 2u);
  91. EXPECT_EQ(m[9], 2);
  92. EXPECT_EQ(m[0], 5);
  93. EXPECT_FALSE(m.UsingFullMap());
  94. }
  95. src[8] = 23;
  96. src[1234] = 90;
  97. src[-5] = 6;
  98. {
  99. small_map<std::unordered_map<int, int>> m(src);
  100. EXPECT_EQ(m[ 9], 2);
  101. EXPECT_EQ(m[ 0], 5);
  102. EXPECT_EQ(m[1234], 90);
  103. EXPECT_EQ(m[ 8], 23);
  104. EXPECT_EQ(m[ -5], 6);
  105. EXPECT_EQ(m.size(), 5u);
  106. EXPECT_FALSE(m.empty());
  107. EXPECT_TRUE(m.UsingFullMap());
  108. }
  109. }
  110. template <class inner>
  111. static bool SmallMapIsSubset(small_map<inner> const& a,
  112. small_map<inner> const& b) {
  113. typename small_map<inner>::const_iterator it;
  114. for (it = a.begin(); it != a.end(); ++it) {
  115. typename small_map<inner>::const_iterator it_in_b = b.find(it->first);
  116. if (it_in_b == b.end() || it_in_b->second != it->second)
  117. return false;
  118. }
  119. return true;
  120. }
  121. template <class inner>
  122. static bool SmallMapEqual(small_map<inner> const& a,
  123. small_map<inner> const& b) {
  124. return SmallMapIsSubset(a, b) && SmallMapIsSubset(b, a);
  125. }
  126. TEST(SmallMap, AssignmentOperator) {
  127. small_map<std::unordered_map<int, int>> src_small;
  128. small_map<std::unordered_map<int, int>> src_large;
  129. src_small[1] = 20;
  130. src_small[2] = 21;
  131. src_small[3] = 22;
  132. EXPECT_FALSE(src_small.UsingFullMap());
  133. src_large[1] = 20;
  134. src_large[2] = 21;
  135. src_large[3] = 22;
  136. src_large[5] = 23;
  137. src_large[6] = 24;
  138. src_large[7] = 25;
  139. EXPECT_TRUE(src_large.UsingFullMap());
  140. // Assignments to empty.
  141. small_map<std::unordered_map<int, int>> dest_small;
  142. dest_small = src_small;
  143. EXPECT_TRUE(SmallMapEqual(dest_small, src_small));
  144. EXPECT_EQ(dest_small.UsingFullMap(),
  145. src_small.UsingFullMap());
  146. small_map<std::unordered_map<int, int>> dest_large;
  147. dest_large = src_large;
  148. EXPECT_TRUE(SmallMapEqual(dest_large, src_large));
  149. EXPECT_EQ(dest_large.UsingFullMap(),
  150. src_large.UsingFullMap());
  151. // Assignments which assign from full to small, and vice versa.
  152. dest_small = src_large;
  153. EXPECT_TRUE(SmallMapEqual(dest_small, src_large));
  154. EXPECT_EQ(dest_small.UsingFullMap(),
  155. src_large.UsingFullMap());
  156. dest_large = src_small;
  157. EXPECT_TRUE(SmallMapEqual(dest_large, src_small));
  158. EXPECT_EQ(dest_large.UsingFullMap(),
  159. src_small.UsingFullMap());
  160. // Double check that SmallMapEqual works:
  161. dest_large[42] = 666;
  162. EXPECT_FALSE(SmallMapEqual(dest_large, src_small));
  163. }
  164. TEST(SmallMap, Insert) {
  165. small_map<std::unordered_map<int, int>> sm;
  166. // loop through the transition from small map to map.
  167. for (int i = 1; i <= 10; ++i) {
  168. VLOG(1) << "Iteration " << i;
  169. // insert an element
  170. std::pair<small_map<std::unordered_map<int, int>>::iterator, bool> ret;
  171. ret = sm.insert(std::make_pair(i, 100*i));
  172. EXPECT_TRUE(ret.second);
  173. EXPECT_TRUE(ret.first == sm.find(i));
  174. EXPECT_EQ(ret.first->first, i);
  175. EXPECT_EQ(ret.first->second, 100*i);
  176. // try to insert it again with different value, fails, but we still get an
  177. // iterator back with the original value.
  178. ret = sm.insert(std::make_pair(i, -i));
  179. EXPECT_FALSE(ret.second);
  180. EXPECT_TRUE(ret.first == sm.find(i));
  181. EXPECT_EQ(ret.first->first, i);
  182. EXPECT_EQ(ret.first->second, 100*i);
  183. // check the state of the map.
  184. for (int j = 1; j <= i; ++j) {
  185. small_map<std::unordered_map<int, int>>::iterator it = sm.find(j);
  186. EXPECT_TRUE(it != sm.end());
  187. EXPECT_EQ(it->first, j);
  188. EXPECT_EQ(it->second, j * 100);
  189. }
  190. EXPECT_EQ(sm.size(), static_cast<size_t>(i));
  191. EXPECT_FALSE(sm.empty());
  192. }
  193. }
  194. TEST(SmallMap, InsertRange) {
  195. // loop through the transition from small map to map.
  196. for (int elements = 0; elements <= 10; ++elements) {
  197. VLOG(1) << "Elements " << elements;
  198. std::unordered_map<int, int> normal_map;
  199. for (int i = 1; i <= elements; ++i) {
  200. normal_map.insert(std::make_pair(i, 100*i));
  201. }
  202. small_map<std::unordered_map<int, int>> sm;
  203. sm.insert(normal_map.begin(), normal_map.end());
  204. EXPECT_EQ(normal_map.size(), sm.size());
  205. for (int i = 1; i <= elements; ++i) {
  206. VLOG(1) << "Iteration " << i;
  207. EXPECT_TRUE(sm.find(i) != sm.end());
  208. EXPECT_EQ(sm.find(i)->first, i);
  209. EXPECT_EQ(sm.find(i)->second, 100*i);
  210. }
  211. }
  212. }
  213. TEST(SmallMap, Erase) {
  214. small_map<std::unordered_map<std::string, int>> m;
  215. small_map<std::unordered_map<std::string, int>>::iterator iter;
  216. m["monday"] = 1;
  217. m["tuesday"] = 2;
  218. m["wednesday"] = 3;
  219. EXPECT_EQ(m["monday" ], 1);
  220. EXPECT_EQ(m["tuesday" ], 2);
  221. EXPECT_EQ(m["wednesday"], 3);
  222. EXPECT_EQ(m.count("tuesday"), 1u);
  223. EXPECT_FALSE(m.UsingFullMap());
  224. iter = m.begin();
  225. ASSERT_TRUE(iter != m.end());
  226. EXPECT_EQ(iter->first, "monday");
  227. EXPECT_EQ(iter->second, 1);
  228. ++iter;
  229. ASSERT_TRUE(iter != m.end());
  230. EXPECT_EQ(iter->first, "tuesday");
  231. EXPECT_EQ(iter->second, 2);
  232. ++iter;
  233. ASSERT_TRUE(iter != m.end());
  234. EXPECT_EQ(iter->first, "wednesday");
  235. EXPECT_EQ(iter->second, 3);
  236. ++iter;
  237. EXPECT_TRUE(iter == m.end());
  238. EXPECT_EQ(m.erase("tuesday"), 1u);
  239. EXPECT_EQ(m["monday" ], 1);
  240. EXPECT_EQ(m["wednesday"], 3);
  241. EXPECT_EQ(m.count("tuesday"), 0u);
  242. EXPECT_EQ(m.erase("tuesday"), 0u);
  243. iter = m.begin();
  244. ASSERT_TRUE(iter != m.end());
  245. EXPECT_EQ(iter->first, "monday");
  246. EXPECT_EQ(iter->second, 1);
  247. ++iter;
  248. ASSERT_TRUE(iter != m.end());
  249. EXPECT_EQ(iter->first, "wednesday");
  250. EXPECT_EQ(iter->second, 3);
  251. ++iter;
  252. EXPECT_TRUE(iter == m.end());
  253. m["thursday"] = 4;
  254. m["friday"] = 5;
  255. EXPECT_EQ(m.size(), 4u);
  256. EXPECT_FALSE(m.empty());
  257. EXPECT_FALSE(m.UsingFullMap());
  258. m["saturday"] = 6;
  259. EXPECT_TRUE(m.UsingFullMap());
  260. EXPECT_EQ(m.count("friday"), 1u);
  261. EXPECT_EQ(m.erase("friday"), 1u);
  262. EXPECT_TRUE(m.UsingFullMap());
  263. EXPECT_EQ(m.count("friday"), 0u);
  264. EXPECT_EQ(m.erase("friday"), 0u);
  265. EXPECT_EQ(m.size(), 4u);
  266. EXPECT_FALSE(m.empty());
  267. EXPECT_EQ(m.erase("monday"), 1u);
  268. EXPECT_EQ(m.size(), 3u);
  269. EXPECT_FALSE(m.empty());
  270. m.clear();
  271. EXPECT_FALSE(m.UsingFullMap());
  272. EXPECT_EQ(m.size(), 0u);
  273. EXPECT_TRUE(m.empty());
  274. }
  275. TEST(SmallMap, EraseReturnsIteratorFollowingRemovedElement) {
  276. small_map<std::unordered_map<std::string, int>> m;
  277. small_map<std::unordered_map<std::string, int>>::iterator iter;
  278. m["a"] = 0;
  279. m["b"] = 1;
  280. m["c"] = 2;
  281. // Erase first item.
  282. auto following_iter = m.erase(m.begin());
  283. EXPECT_EQ(m.begin(), following_iter);
  284. EXPECT_EQ(2u, m.size());
  285. EXPECT_EQ(m.count("a"), 0u);
  286. EXPECT_EQ(m.count("b"), 1u);
  287. EXPECT_EQ(m.count("c"), 1u);
  288. // Iterate to last item and erase it.
  289. ++following_iter;
  290. following_iter = m.erase(following_iter);
  291. ASSERT_EQ(1u, m.size());
  292. EXPECT_EQ(m.end(), following_iter);
  293. EXPECT_EQ(m.count("b"), 0u);
  294. EXPECT_EQ(m.count("c"), 1u);
  295. // Erase remaining item.
  296. following_iter = m.erase(m.begin());
  297. EXPECT_TRUE(m.empty());
  298. EXPECT_EQ(m.end(), following_iter);
  299. }
  300. TEST(SmallMap, NonHashMap) {
  301. small_map<std::map<int, int>, 4, std::equal_to<int>> m;
  302. EXPECT_TRUE(m.empty());
  303. m[9] = 2;
  304. m[0] = 5;
  305. EXPECT_EQ(m[9], 2);
  306. EXPECT_EQ(m[0], 5);
  307. EXPECT_EQ(m.size(), 2u);
  308. EXPECT_FALSE(m.empty());
  309. EXPECT_FALSE(m.UsingFullMap());
  310. small_map<std::map<int, int>, 4, std::equal_to<int>>::iterator iter(
  311. m.begin());
  312. ASSERT_TRUE(iter != m.end());
  313. EXPECT_EQ(iter->first, 9);
  314. EXPECT_EQ(iter->second, 2);
  315. ++iter;
  316. ASSERT_TRUE(iter != m.end());
  317. EXPECT_EQ(iter->first, 0);
  318. EXPECT_EQ(iter->second, 5);
  319. ++iter;
  320. EXPECT_TRUE(iter == m.end());
  321. --iter;
  322. ASSERT_TRUE(iter != m.end());
  323. EXPECT_EQ(iter->first, 0);
  324. EXPECT_EQ(iter->second, 5);
  325. m[8] = 23;
  326. m[1234] = 90;
  327. m[-5] = 6;
  328. EXPECT_EQ(m[ 9], 2);
  329. EXPECT_EQ(m[ 0], 5);
  330. EXPECT_EQ(m[1234], 90);
  331. EXPECT_EQ(m[ 8], 23);
  332. EXPECT_EQ(m[ -5], 6);
  333. EXPECT_EQ(m.size(), 5u);
  334. EXPECT_FALSE(m.empty());
  335. EXPECT_TRUE(m.UsingFullMap());
  336. iter = m.begin();
  337. ASSERT_TRUE(iter != m.end());
  338. EXPECT_EQ(iter->first, -5);
  339. EXPECT_EQ(iter->second, 6);
  340. ++iter;
  341. ASSERT_TRUE(iter != m.end());
  342. EXPECT_EQ(iter->first, 0);
  343. EXPECT_EQ(iter->second, 5);
  344. ++iter;
  345. ASSERT_TRUE(iter != m.end());
  346. EXPECT_EQ(iter->first, 8);
  347. EXPECT_EQ(iter->second, 23);
  348. ++iter;
  349. ASSERT_TRUE(iter != m.end());
  350. EXPECT_EQ(iter->first, 9);
  351. EXPECT_EQ(iter->second, 2);
  352. ++iter;
  353. ASSERT_TRUE(iter != m.end());
  354. EXPECT_EQ(iter->first, 1234);
  355. EXPECT_EQ(iter->second, 90);
  356. ++iter;
  357. EXPECT_TRUE(iter == m.end());
  358. --iter;
  359. ASSERT_TRUE(iter != m.end());
  360. EXPECT_EQ(iter->first, 1234);
  361. EXPECT_EQ(iter->second, 90);
  362. }
  363. TEST(SmallMap, DefaultEqualKeyWorks) {
  364. // If these tests compile, they pass. The EXPECT calls are only there to avoid
  365. // unused variable warnings.
  366. small_map<std::unordered_map<int, int>> hm;
  367. EXPECT_EQ(0u, hm.size());
  368. small_map<std::map<int, int>> m;
  369. EXPECT_EQ(0u, m.size());
  370. }
  371. namespace {
  372. class unordered_map_add_item : public std::unordered_map<int, int> {
  373. public:
  374. unordered_map_add_item() = default;
  375. explicit unordered_map_add_item(const std::pair<int, int>& item) {
  376. insert(item);
  377. }
  378. };
  379. void InitMap(unordered_map_add_item* map_ctor) {
  380. new (map_ctor) unordered_map_add_item(std::make_pair(0, 0));
  381. }
  382. class unordered_map_add_item_initializer {
  383. public:
  384. explicit unordered_map_add_item_initializer(int item_to_add)
  385. : item_(item_to_add) {}
  386. unordered_map_add_item_initializer() : item_(0) {}
  387. void operator()(unordered_map_add_item* map_ctor) const {
  388. new (map_ctor) unordered_map_add_item(std::make_pair(item_, item_));
  389. }
  390. int item_;
  391. };
  392. } // anonymous namespace
  393. TEST(SmallMap, SubclassInitializationWithFunctionPointer) {
  394. small_map<unordered_map_add_item, 4, std::equal_to<int>,
  395. void (&)(unordered_map_add_item*)>
  396. m(InitMap);
  397. EXPECT_TRUE(m.empty());
  398. m[1] = 1;
  399. m[2] = 2;
  400. m[3] = 3;
  401. m[4] = 4;
  402. EXPECT_EQ(4u, m.size());
  403. EXPECT_EQ(0u, m.count(0));
  404. m[5] = 5;
  405. EXPECT_EQ(6u, m.size());
  406. // Our function adds an extra item when we convert to a map.
  407. EXPECT_EQ(1u, m.count(0));
  408. }
  409. TEST(SmallMap, SubclassInitializationWithFunctionObject) {
  410. small_map<unordered_map_add_item, 4, std::equal_to<int>,
  411. unordered_map_add_item_initializer>
  412. m(unordered_map_add_item_initializer(-1));
  413. EXPECT_TRUE(m.empty());
  414. m[1] = 1;
  415. m[2] = 2;
  416. m[3] = 3;
  417. m[4] = 4;
  418. EXPECT_EQ(4u, m.size());
  419. EXPECT_EQ(0u, m.count(-1));
  420. m[5] = 5;
  421. EXPECT_EQ(6u, m.size());
  422. // Our functor adds an extra item when we convert to a map.
  423. EXPECT_EQ(1u, m.count(-1));
  424. }
  425. namespace {
  426. // This class acts as a basic implementation of a move-only type. The canonical
  427. // example of such a type is scoped_ptr/unique_ptr.
  428. template <typename V>
  429. class MoveOnlyType {
  430. public:
  431. MoveOnlyType() : value_(0) {}
  432. explicit MoveOnlyType(V value) : value_(value) {}
  433. MoveOnlyType(MoveOnlyType&& other) {
  434. *this = std::move(other);
  435. }
  436. MoveOnlyType& operator=(MoveOnlyType&& other) {
  437. value_ = other.value_;
  438. other.value_ = 0;
  439. return *this;
  440. }
  441. MoveOnlyType(const MoveOnlyType&) = delete;
  442. MoveOnlyType& operator=(const MoveOnlyType&) = delete;
  443. V value() const { return value_; }
  444. private:
  445. V value_;
  446. };
  447. } // namespace
  448. TEST(SmallMap, MoveOnlyValueType) {
  449. small_map<std::map<int, MoveOnlyType<int>>, 2> m;
  450. m[0] = MoveOnlyType<int>(1);
  451. m[1] = MoveOnlyType<int>(2);
  452. m.erase(m.begin());
  453. // small_map will move m[1] to an earlier index in the internal array.
  454. EXPECT_EQ(m.size(), 1u);
  455. EXPECT_EQ(m[1].value(), 2);
  456. m[0] = MoveOnlyType<int>(1);
  457. // small_map must move the values from the array into the internal std::map.
  458. m[2] = MoveOnlyType<int>(3);
  459. EXPECT_EQ(m.size(), 3u);
  460. EXPECT_EQ(m[0].value(), 1);
  461. EXPECT_EQ(m[1].value(), 2);
  462. EXPECT_EQ(m[2].value(), 3);
  463. m.erase(m.begin());
  464. // small_map should also let internal std::map erase with a move-only type.
  465. EXPECT_EQ(m.size(), 2u);
  466. EXPECT_EQ(m[1].value(), 2);
  467. EXPECT_EQ(m[2].value(), 3);
  468. }
  469. TEST(SmallMap, Emplace) {
  470. small_map<std::map<size_t, MoveOnlyType<size_t>>> sm;
  471. // loop through the transition from small map to map.
  472. for (size_t i = 1; i <= 10; ++i) {
  473. // insert an element
  474. auto ret = sm.emplace(i, MoveOnlyType<size_t>(100 * i));
  475. EXPECT_TRUE(ret.second);
  476. EXPECT_TRUE(ret.first == sm.find(i));
  477. EXPECT_EQ(ret.first->first, i);
  478. EXPECT_EQ(ret.first->second.value(), 100 * i);
  479. // try to insert it again with different value, fails, but we still get an
  480. // iterator back with the original value.
  481. ret = sm.emplace(i, MoveOnlyType<size_t>(i));
  482. EXPECT_FALSE(ret.second);
  483. EXPECT_TRUE(ret.first == sm.find(i));
  484. EXPECT_EQ(ret.first->first, i);
  485. EXPECT_EQ(ret.first->second.value(), 100 * i);
  486. // check the state of the map.
  487. for (size_t j = 1; j <= i; ++j) {
  488. const auto it = sm.find(j);
  489. EXPECT_TRUE(it != sm.end());
  490. EXPECT_EQ(it->first, j);
  491. EXPECT_EQ(it->second.value(), j * 100);
  492. }
  493. EXPECT_EQ(sm.size(), i);
  494. EXPECT_FALSE(sm.empty());
  495. }
  496. }
  497. } // namespace base