LListTest.cpp 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327
  1. /*
  2. * Copyright 2012 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "include/utils/SkRandom.h"
  8. #include "src/core/SkTInternalLList.h"
  9. #include "src/core/SkTLList.h"
  10. #include "tests/Test.h"
  11. class ListElement {
  12. public:
  13. ListElement(int id) : fID(id) {
  14. }
  15. bool operator== (const ListElement& other) { return fID == other.fID; }
  16. int fID;
  17. private:
  18. SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement);
  19. };
  20. static void check_list(const SkTInternalLList<ListElement>& list,
  21. skiatest::Reporter* reporter,
  22. bool empty,
  23. int numElements,
  24. bool in0, bool in1, bool in2, bool in3,
  25. ListElement elements[4]) {
  26. REPORTER_ASSERT(reporter, empty == list.isEmpty());
  27. #ifdef SK_DEBUG
  28. list.validate();
  29. REPORTER_ASSERT(reporter, numElements == list.countEntries());
  30. REPORTER_ASSERT(reporter, in0 == list.isInList(&elements[0]));
  31. REPORTER_ASSERT(reporter, in1 == list.isInList(&elements[1]));
  32. REPORTER_ASSERT(reporter, in2 == list.isInList(&elements[2]));
  33. REPORTER_ASSERT(reporter, in3 == list.isInList(&elements[3]));
  34. #endif
  35. }
  36. static void test_tinternallist(skiatest::Reporter* reporter) {
  37. SkTInternalLList<ListElement> list;
  38. ListElement elements[4] = {
  39. ListElement(0),
  40. ListElement(1),
  41. ListElement(2),
  42. ListElement(3),
  43. };
  44. // list should be empty to start with
  45. check_list(list, reporter, true, 0, false, false, false, false, elements);
  46. list.addToHead(&elements[0]);
  47. check_list(list, reporter, false, 1, true, false, false, false, elements);
  48. list.addToHead(&elements[1]);
  49. list.addToHead(&elements[2]);
  50. list.addToHead(&elements[3]);
  51. check_list(list, reporter, false, 4, true, true, true, true, elements);
  52. // test out iterators
  53. typedef SkTInternalLList<ListElement>::Iter Iter;
  54. Iter iter;
  55. ListElement* cur = iter.init(list, Iter::kHead_IterStart);
  56. for (int i = 0; cur; ++i, cur = iter.next()) {
  57. REPORTER_ASSERT(reporter, cur->fID == 3-i);
  58. }
  59. cur = iter.init(list, Iter::kTail_IterStart);
  60. for (int i = 0; cur; ++i, cur = iter.prev()) {
  61. REPORTER_ASSERT(reporter, cur->fID == i);
  62. }
  63. // remove middle, frontmost then backmost
  64. list.remove(&elements[1]);
  65. list.remove(&elements[3]);
  66. list.remove(&elements[0]);
  67. check_list(list, reporter, false, 1, false, false, true, false, elements);
  68. // remove last element
  69. list.remove(&elements[2]);
  70. // list should be empty again
  71. check_list(list, reporter, true, 0, false, false, false, false, elements);
  72. // test out methods that add to the middle of the list.
  73. list.addAfter(&elements[1], nullptr);
  74. check_list(list, reporter, false, 1, false, true, false, false, elements);
  75. list.remove(&elements[1]);
  76. list.addBefore(&elements[1], nullptr);
  77. check_list(list, reporter, false, 1, false, true, false, false, elements);
  78. list.addBefore(&elements[0], &elements[1]);
  79. check_list(list, reporter, false, 2, true, true, false, false, elements);
  80. list.addAfter(&elements[3], &elements[1]);
  81. check_list(list, reporter, false, 3, true, true, false, true, elements);
  82. list.addBefore(&elements[2], &elements[3]);
  83. check_list(list, reporter, false, 4, true, true, true, true, elements);
  84. cur = iter.init(list, Iter::kHead_IterStart);
  85. for (int i = 0; cur; ++i, cur = iter.next()) {
  86. REPORTER_ASSERT(reporter, cur->fID == i);
  87. }
  88. while (!list.isEmpty()) {
  89. list.remove(list.tail());
  90. }
  91. // test concat.
  92. SkTInternalLList<ListElement> listA, listB;
  93. listA.concat(std::move(listB));
  94. check_list(listA, reporter, true, 0, false, false, false, false, elements);
  95. // NOLINTNEXTLINE(bugprone-use-after-move)
  96. check_list(listB, reporter, true, 0, false, false, false, false, elements);
  97. listB.addToTail(&elements[0]);
  98. listA.concat(std::move(listB));
  99. check_list(listA, reporter, false, 1, true, false, false, false, elements);
  100. // NOLINTNEXTLINE(bugprone-use-after-move)
  101. check_list(listB, reporter, true, 0, false, false, false, false, elements);
  102. listB.addToTail(&elements[1]);
  103. listA.concat(std::move(listB));
  104. check_list(listA, reporter, false, 2, true, true, false, false, elements);
  105. // NOLINTNEXTLINE(bugprone-use-after-move)
  106. check_list(listB, reporter, true, 0, false, false, false, false, elements);
  107. listA.concat(std::move(listB));
  108. check_list(listA, reporter, false, 2, true, true, false, false, elements);
  109. // NOLINTNEXTLINE(bugprone-use-after-move)
  110. check_list(listB, reporter, true, 0, false, false, false, false, elements);
  111. listB.addToTail(&elements[2]);
  112. listB.addToTail(&elements[3]);
  113. listA.concat(std::move(listB));
  114. check_list(listA, reporter, false, 4, true, true, true, true, elements);
  115. // NOLINTNEXTLINE(bugprone-use-after-move)
  116. check_list(listB, reporter, true, 0, false, false, false, false, elements);
  117. cur = iter.init(listA, Iter::kHead_IterStart);
  118. for (int i = 0; cur; ++i, cur = iter.next()) {
  119. REPORTER_ASSERT(reporter, cur->fID == i);
  120. }
  121. }
  122. template <unsigned int N> static void test_tllist(skiatest::Reporter* reporter) {
  123. typedef SkTLList<ListElement, N> ElList;
  124. typedef typename ElList::Iter Iter;
  125. SkRandom random;
  126. ElList list1;
  127. ElList list2;
  128. Iter iter1;
  129. Iter iter2;
  130. Iter iter3;
  131. Iter iter4;
  132. REPORTER_ASSERT(reporter, list1.isEmpty());
  133. REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kHead_IterStart));
  134. REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kTail_IterStart));
  135. // Try popping an empty list
  136. list1.popHead();
  137. list1.popTail();
  138. REPORTER_ASSERT(reporter, list1.isEmpty());
  139. REPORTER_ASSERT(reporter, list1 == list2);
  140. // Create two identical lists, one by appending to head and the other to the tail.
  141. list1.addToHead(ListElement(1));
  142. list2.addToTail(ListElement(1));
  143. iter1.init(list1, Iter::kHead_IterStart);
  144. iter2.init(list1, Iter::kTail_IterStart);
  145. REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID);
  146. iter3.init(list2, Iter::kHead_IterStart);
  147. iter4.init(list2, Iter::kTail_IterStart);
  148. REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
  149. REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
  150. REPORTER_ASSERT(reporter, list1 == list2);
  151. list2.reset();
  152. // use both before/after in-place construction on an empty list
  153. list2.addBefore(list2.headIter(), 1);
  154. REPORTER_ASSERT(reporter, list2 == list1);
  155. list2.reset();
  156. list2.addAfter(list2.tailIter(), 1);
  157. REPORTER_ASSERT(reporter, list2 == list1);
  158. // add an element to the second list, check that iters are still valid
  159. iter3.init(list2, Iter::kHead_IterStart);
  160. iter4.init(list2, Iter::kTail_IterStart);
  161. list2.addToHead(ListElement(2));
  162. REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
  163. REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
  164. REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID);
  165. REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID);
  166. REPORTER_ASSERT(reporter, list1 != list2);
  167. list1.addToHead(ListElement(2));
  168. REPORTER_ASSERT(reporter, list1 == list2);
  169. REPORTER_ASSERT(reporter, !list1.isEmpty());
  170. list1.reset();
  171. list2.reset();
  172. REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty());
  173. // randomly perform insertions and deletions on a list and perform tests
  174. int count = 0;
  175. for (int j = 0; j < 100; ++j) {
  176. if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) {
  177. int id = j;
  178. // Choose one of three ways to insert a new element: at the head, at the tail,
  179. // before a random element, after a random element
  180. int numValidMethods = 0 == count ? 2 : 4;
  181. int insertionMethod = random.nextULessThan(numValidMethods);
  182. switch (insertionMethod) {
  183. case 0:
  184. list1.addToHead(ListElement(id));
  185. break;
  186. case 1:
  187. list1.addToTail(ListElement(id));
  188. break;
  189. case 2: // fallthru to share code that picks random element.
  190. case 3: {
  191. int n = random.nextULessThan(list1.count());
  192. Iter iter = list1.headIter();
  193. // remember the elements before/after the insertion point.
  194. while (n--) {
  195. iter.next();
  196. }
  197. Iter prev(iter);
  198. Iter next(iter);
  199. next.next();
  200. prev.prev();
  201. SkASSERT(iter.get());
  202. // insert either before or after the iterator, then check that the
  203. // surrounding sequence is correct.
  204. if (2 == insertionMethod) {
  205. list1.addBefore(iter, id);
  206. Iter newItem(iter);
  207. newItem.prev();
  208. REPORTER_ASSERT(reporter, newItem.get()->fID == id);
  209. if (next.get()) {
  210. REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID);
  211. }
  212. if (prev.get()) {
  213. REPORTER_ASSERT(reporter, prev.next()->fID == id);
  214. }
  215. } else {
  216. list1.addAfter(iter, id);
  217. Iter newItem(iter);
  218. newItem.next();
  219. REPORTER_ASSERT(reporter, newItem.get()->fID == id);
  220. if (next.get()) {
  221. REPORTER_ASSERT(reporter, next.prev()->fID == id);
  222. }
  223. if (prev.get()) {
  224. REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID);
  225. }
  226. }
  227. }
  228. }
  229. ++count;
  230. } else {
  231. // walk to a random place either forward or backwards and remove.
  232. int n = random.nextULessThan(list1.count());
  233. typename Iter::IterStart start;
  234. ListElement* (Iter::*incrFunc)();
  235. if (random.nextBool()) {
  236. start = Iter::kHead_IterStart;
  237. incrFunc = &Iter::next;
  238. } else {
  239. start = Iter::kTail_IterStart;
  240. incrFunc = &Iter::prev;
  241. }
  242. // find the element
  243. Iter iter(list1, start);
  244. while (n--) {
  245. REPORTER_ASSERT(reporter, iter.get());
  246. (iter.*incrFunc)();
  247. }
  248. REPORTER_ASSERT(reporter, iter.get());
  249. // remember the prev and next elements from the element to be removed
  250. Iter prev = iter;
  251. Iter next = iter;
  252. prev.prev();
  253. next.next();
  254. list1.remove(iter.get());
  255. // make sure the remembered next/prev iters still work
  256. Iter pn = prev; pn.next();
  257. Iter np = next; np.prev();
  258. // pn should match next unless the target node was the head, in which case prev
  259. // walked off the list.
  260. REPORTER_ASSERT(reporter, pn.get() == next.get() || nullptr == prev.get());
  261. // Similarly, np should match prev unless next originally walked off the tail.
  262. REPORTER_ASSERT(reporter, np.get() == prev.get() || nullptr == next.get());
  263. --count;
  264. }
  265. REPORTER_ASSERT(reporter, count == list1.count());
  266. }
  267. }
  268. DEF_TEST(LList, reporter) {
  269. test_tinternallist(reporter);
  270. test_tllist<1>(reporter);
  271. test_tllist<3>(reporter);
  272. test_tllist<8>(reporter);
  273. test_tllist<10>(reporter);
  274. test_tllist<16>(reporter);
  275. }