id_map_unittest.cc 9.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397
  1. // Copyright (c) 2011 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/id_map.h"
  5. #include <stdint.h>
  6. #include <memory>
  7. #include "base/test/gtest_util.h"
  8. #include "testing/gtest/include/gtest/gtest.h"
  9. namespace base {
  10. namespace {
  11. class TestObject {
  12. };
  13. class DestructorCounter {
  14. public:
  15. explicit DestructorCounter(int* counter) : counter_(counter) {}
  16. ~DestructorCounter() { ++(*counter_); }
  17. private:
  18. int* counter_;
  19. };
  20. } // namespace
  21. TEST(IDMapTest, Basic) {
  22. IDMap<TestObject*> map;
  23. EXPECT_TRUE(map.IsEmpty());
  24. EXPECT_EQ(0U, map.size());
  25. TestObject obj1;
  26. TestObject obj2;
  27. int32_t id1 = map.Add(&obj1);
  28. EXPECT_FALSE(map.IsEmpty());
  29. EXPECT_EQ(1U, map.size());
  30. EXPECT_EQ(&obj1, map.Lookup(id1));
  31. int32_t id2 = map.Add(&obj2);
  32. EXPECT_FALSE(map.IsEmpty());
  33. EXPECT_EQ(2U, map.size());
  34. EXPECT_EQ(&obj1, map.Lookup(id1));
  35. EXPECT_EQ(&obj2, map.Lookup(id2));
  36. map.Remove(id1);
  37. EXPECT_FALSE(map.IsEmpty());
  38. EXPECT_EQ(1U, map.size());
  39. map.Remove(id2);
  40. EXPECT_TRUE(map.IsEmpty());
  41. EXPECT_EQ(0U, map.size());
  42. map.AddWithID(&obj1, 1);
  43. map.AddWithID(&obj2, 2);
  44. EXPECT_EQ(&obj1, map.Lookup(1));
  45. EXPECT_EQ(&obj2, map.Lookup(2));
  46. EXPECT_EQ(&obj2, map.Replace(2, &obj1));
  47. EXPECT_EQ(&obj1, map.Lookup(2));
  48. EXPECT_EQ(0, map.iteration_depth());
  49. }
  50. TEST(IDMapTest, IteratorRemainsValidWhenRemovingCurrentElement) {
  51. IDMap<TestObject*> map;
  52. TestObject obj1;
  53. TestObject obj2;
  54. TestObject obj3;
  55. map.Add(&obj1);
  56. map.Add(&obj2);
  57. map.Add(&obj3);
  58. {
  59. IDMap<TestObject*>::const_iterator iter(&map);
  60. EXPECT_EQ(1, map.iteration_depth());
  61. while (!iter.IsAtEnd()) {
  62. map.Remove(iter.GetCurrentKey());
  63. iter.Advance();
  64. }
  65. // Test that while an iterator is still in scope, we get the map emptiness
  66. // right (http://crbug.com/35571).
  67. EXPECT_TRUE(map.IsEmpty());
  68. EXPECT_EQ(0U, map.size());
  69. }
  70. EXPECT_TRUE(map.IsEmpty());
  71. EXPECT_EQ(0U, map.size());
  72. EXPECT_EQ(0, map.iteration_depth());
  73. }
  74. TEST(IDMapTest, IteratorRemainsValidWhenRemovingOtherElements) {
  75. IDMap<TestObject*> map;
  76. const int kCount = 5;
  77. TestObject obj[kCount];
  78. for (auto& i : obj)
  79. map.Add(&i);
  80. // IDMap has no predictable iteration order.
  81. int32_t ids_in_iteration_order[kCount];
  82. const TestObject* objs_in_iteration_order[kCount];
  83. int counter = 0;
  84. for (IDMap<TestObject*>::const_iterator iter(&map); !iter.IsAtEnd();
  85. iter.Advance()) {
  86. ids_in_iteration_order[counter] = iter.GetCurrentKey();
  87. objs_in_iteration_order[counter] = iter.GetCurrentValue();
  88. counter++;
  89. }
  90. counter = 0;
  91. for (IDMap<TestObject*>::const_iterator iter(&map); !iter.IsAtEnd();
  92. iter.Advance()) {
  93. EXPECT_EQ(1, map.iteration_depth());
  94. switch (counter) {
  95. case 0:
  96. EXPECT_EQ(ids_in_iteration_order[0], iter.GetCurrentKey());
  97. EXPECT_EQ(objs_in_iteration_order[0], iter.GetCurrentValue());
  98. map.Remove(ids_in_iteration_order[1]);
  99. break;
  100. case 1:
  101. EXPECT_EQ(ids_in_iteration_order[2], iter.GetCurrentKey());
  102. EXPECT_EQ(objs_in_iteration_order[2], iter.GetCurrentValue());
  103. map.Remove(ids_in_iteration_order[3]);
  104. break;
  105. case 2:
  106. EXPECT_EQ(ids_in_iteration_order[4], iter.GetCurrentKey());
  107. EXPECT_EQ(objs_in_iteration_order[4], iter.GetCurrentValue());
  108. map.Remove(ids_in_iteration_order[0]);
  109. break;
  110. default:
  111. FAIL() << "should not have that many elements";
  112. }
  113. counter++;
  114. }
  115. EXPECT_EQ(0, map.iteration_depth());
  116. }
  117. TEST(IDMapTest, CopyIterator) {
  118. IDMap<TestObject*> map;
  119. TestObject obj1;
  120. TestObject obj2;
  121. TestObject obj3;
  122. map.Add(&obj1);
  123. map.Add(&obj2);
  124. map.Add(&obj3);
  125. EXPECT_EQ(0, map.iteration_depth());
  126. {
  127. IDMap<TestObject*>::const_iterator iter1(&map);
  128. EXPECT_EQ(1, map.iteration_depth());
  129. // Make sure that copying the iterator correctly increments
  130. // map's iteration depth.
  131. IDMap<TestObject*>::const_iterator iter2(iter1);
  132. EXPECT_EQ(2, map.iteration_depth());
  133. }
  134. // Make sure after destroying all iterators the map's iteration depth
  135. // returns to initial state.
  136. EXPECT_EQ(0, map.iteration_depth());
  137. }
  138. TEST(IDMapTest, AssignIterator) {
  139. IDMap<TestObject*> map;
  140. TestObject obj1;
  141. TestObject obj2;
  142. TestObject obj3;
  143. map.Add(&obj1);
  144. map.Add(&obj2);
  145. map.Add(&obj3);
  146. EXPECT_EQ(0, map.iteration_depth());
  147. {
  148. IDMap<TestObject*>::const_iterator iter1(&map);
  149. EXPECT_EQ(1, map.iteration_depth());
  150. IDMap<TestObject*>::const_iterator iter2(&map);
  151. EXPECT_EQ(2, map.iteration_depth());
  152. // Make sure that assigning the iterator correctly updates
  153. // map's iteration depth (-1 for destruction, +1 for assignment).
  154. EXPECT_EQ(2, map.iteration_depth());
  155. }
  156. // Make sure after destroying all iterators the map's iteration depth
  157. // returns to initial state.
  158. EXPECT_EQ(0, map.iteration_depth());
  159. }
  160. TEST(IDMapTest, IteratorRemainsValidWhenClearing) {
  161. IDMap<TestObject*> map;
  162. const int kCount = 5;
  163. TestObject obj[kCount];
  164. for (auto& i : obj)
  165. map.Add(&i);
  166. // IDMap has no predictable iteration order.
  167. int32_t ids_in_iteration_order[kCount];
  168. const TestObject* objs_in_iteration_order[kCount];
  169. int counter = 0;
  170. for (IDMap<TestObject*>::const_iterator iter(&map); !iter.IsAtEnd();
  171. iter.Advance()) {
  172. ids_in_iteration_order[counter] = iter.GetCurrentKey();
  173. objs_in_iteration_order[counter] = iter.GetCurrentValue();
  174. counter++;
  175. }
  176. counter = 0;
  177. for (IDMap<TestObject*>::const_iterator iter(&map); !iter.IsAtEnd();
  178. iter.Advance()) {
  179. switch (counter) {
  180. case 0:
  181. EXPECT_EQ(ids_in_iteration_order[0], iter.GetCurrentKey());
  182. EXPECT_EQ(objs_in_iteration_order[0], iter.GetCurrentValue());
  183. break;
  184. case 1:
  185. EXPECT_EQ(ids_in_iteration_order[1], iter.GetCurrentKey());
  186. EXPECT_EQ(objs_in_iteration_order[1], iter.GetCurrentValue());
  187. map.Clear();
  188. EXPECT_TRUE(map.IsEmpty());
  189. EXPECT_EQ(0U, map.size());
  190. break;
  191. default:
  192. FAIL() << "should not have that many elements";
  193. }
  194. counter++;
  195. }
  196. EXPECT_TRUE(map.IsEmpty());
  197. EXPECT_EQ(0U, map.size());
  198. }
  199. TEST(IDMapTest, OwningPointersDeletesThemOnRemove) {
  200. const int kCount = 3;
  201. int external_del_count = 0;
  202. DestructorCounter* external_obj[kCount];
  203. int map_external_ids[kCount];
  204. int owned_del_count = 0;
  205. int map_owned_ids[kCount];
  206. IDMap<DestructorCounter*> map_external;
  207. IDMap<std::unique_ptr<DestructorCounter>> map_owned;
  208. for (int i = 0; i < kCount; ++i) {
  209. external_obj[i] = new DestructorCounter(&external_del_count);
  210. map_external_ids[i] = map_external.Add(external_obj[i]);
  211. map_owned_ids[i] =
  212. map_owned.Add(std::make_unique<DestructorCounter>(&owned_del_count));
  213. }
  214. for (int i = 0; i < kCount; ++i) {
  215. EXPECT_EQ(external_del_count, 0);
  216. EXPECT_EQ(owned_del_count, i);
  217. map_external.Remove(map_external_ids[i]);
  218. map_owned.Remove(map_owned_ids[i]);
  219. }
  220. for (auto* i : external_obj) {
  221. delete i;
  222. }
  223. EXPECT_EQ(external_del_count, kCount);
  224. EXPECT_EQ(owned_del_count, kCount);
  225. }
  226. TEST(IDMapTest, OwningPointersDeletesThemOnClear) {
  227. const int kCount = 3;
  228. int external_del_count = 0;
  229. DestructorCounter* external_obj[kCount];
  230. int owned_del_count = 0;
  231. IDMap<DestructorCounter*> map_external;
  232. IDMap<std::unique_ptr<DestructorCounter>> map_owned;
  233. for (auto*& i : external_obj) {
  234. i = new DestructorCounter(&external_del_count);
  235. map_external.Add(i);
  236. map_owned.Add(std::make_unique<DestructorCounter>(&owned_del_count));
  237. }
  238. EXPECT_EQ(external_del_count, 0);
  239. EXPECT_EQ(owned_del_count, 0);
  240. map_external.Clear();
  241. map_owned.Clear();
  242. EXPECT_EQ(external_del_count, 0);
  243. EXPECT_EQ(owned_del_count, kCount);
  244. for (auto* i : external_obj) {
  245. delete i;
  246. }
  247. EXPECT_EQ(external_del_count, kCount);
  248. EXPECT_EQ(owned_del_count, kCount);
  249. }
  250. TEST(IDMapTest, OwningPointersDeletesThemOnDestruct) {
  251. const int kCount = 3;
  252. int external_del_count = 0;
  253. DestructorCounter* external_obj[kCount];
  254. int owned_del_count = 0;
  255. {
  256. IDMap<DestructorCounter*> map_external;
  257. IDMap<std::unique_ptr<DestructorCounter>> map_owned;
  258. for (auto*& i : external_obj) {
  259. i = new DestructorCounter(&external_del_count);
  260. map_external.Add(i);
  261. map_owned.Add(std::make_unique<DestructorCounter>(&owned_del_count));
  262. }
  263. }
  264. EXPECT_EQ(external_del_count, 0);
  265. for (auto* i : external_obj) {
  266. delete i;
  267. }
  268. EXPECT_EQ(external_del_count, kCount);
  269. EXPECT_EQ(owned_del_count, kCount);
  270. }
  271. TEST(IDMapTest, Int64KeyType) {
  272. IDMap<TestObject*, int64_t> map;
  273. TestObject obj1;
  274. const int64_t kId1 = 999999999999999999;
  275. map.AddWithID(&obj1, kId1);
  276. EXPECT_EQ(&obj1, map.Lookup(kId1));
  277. IDMap<TestObject*, int64_t>::const_iterator iter(&map);
  278. ASSERT_FALSE(iter.IsAtEnd());
  279. EXPECT_EQ(kId1, iter.GetCurrentKey());
  280. EXPECT_EQ(&obj1, iter.GetCurrentValue());
  281. iter.Advance();
  282. ASSERT_TRUE(iter.IsAtEnd());
  283. map.Remove(kId1);
  284. EXPECT_TRUE(map.IsEmpty());
  285. }
  286. TEST(IDMapTest, RemovedValueHandling) {
  287. TestObject obj;
  288. IDMap<TestObject*> map;
  289. int key = map.Add(&obj);
  290. IDMap<TestObject*>::iterator itr(&map);
  291. map.Clear();
  292. EXPECT_DCHECK_DEATH(map.Remove(key));
  293. EXPECT_DCHECK_DEATH(map.Replace(key, &obj));
  294. EXPECT_FALSE(map.Lookup(key));
  295. EXPECT_FALSE(itr.IsAtEnd());
  296. EXPECT_FALSE(itr.GetCurrentValue());
  297. EXPECT_TRUE(map.IsEmpty());
  298. map.AddWithID(&obj, key);
  299. EXPECT_EQ(1u, map.size());
  300. }
  301. } // namespace base