DequeTest.cpp 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169
  1. /*
  2. * Copyright 2011 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/core/SkDeque.h"
  8. #include "tests/Test.h"
  9. static void assert_count(skiatest::Reporter* reporter, const SkDeque& deq, int count) {
  10. if (0 == count) {
  11. REPORTER_ASSERT(reporter, deq.empty());
  12. REPORTER_ASSERT(reporter, 0 == deq.count());
  13. REPORTER_ASSERT(reporter, sizeof(int) == deq.elemSize());
  14. REPORTER_ASSERT(reporter, nullptr == deq.front());
  15. REPORTER_ASSERT(reporter, nullptr == deq.back());
  16. } else {
  17. REPORTER_ASSERT(reporter, !deq.empty());
  18. REPORTER_ASSERT(reporter, count == deq.count());
  19. REPORTER_ASSERT(reporter, sizeof(int) == deq.elemSize());
  20. REPORTER_ASSERT(reporter, deq.front());
  21. REPORTER_ASSERT(reporter, deq.back());
  22. if (1 == count) {
  23. REPORTER_ASSERT(reporter, deq.back() == deq.front());
  24. } else {
  25. REPORTER_ASSERT(reporter, deq.back() != deq.front());
  26. }
  27. }
  28. }
  29. static void assert_iter(skiatest::Reporter* reporter, const SkDeque& deq,
  30. int max, int min) {
  31. // test forward iteration
  32. SkDeque::Iter iter(deq, SkDeque::Iter::kFront_IterStart);
  33. void* ptr;
  34. int value = max;
  35. while ((ptr = iter.next())) {
  36. REPORTER_ASSERT(reporter, value == *(int*)ptr);
  37. value -= 1;
  38. }
  39. REPORTER_ASSERT(reporter, value+1 == min);
  40. // test reverse iteration
  41. iter.reset(deq, SkDeque::Iter::kBack_IterStart);
  42. value = min;
  43. while ((ptr = iter.prev())) {
  44. REPORTER_ASSERT(reporter, value == *(int*)ptr);
  45. value += 1;
  46. }
  47. REPORTER_ASSERT(reporter, value-1 == max);
  48. // test mixed iteration
  49. iter.reset(deq, SkDeque::Iter::kFront_IterStart);
  50. value = max;
  51. // forward iteration half-way
  52. for (int i = 0; i < deq.count()/2 && (ptr = iter.next()); i++) {
  53. REPORTER_ASSERT(reporter, value == *(int*)ptr);
  54. value -= 1;
  55. }
  56. // then back down w/ reverse iteration
  57. while ((ptr = iter.prev())) {
  58. REPORTER_ASSERT(reporter, value == *(int*)ptr);
  59. value += 1;
  60. }
  61. REPORTER_ASSERT(reporter, value-1 == max);
  62. }
  63. // This helper is intended to only give the unit test access to SkDeque's
  64. // private numBlocksAllocated method
  65. class DequeUnitTestHelper {
  66. public:
  67. int fNumBlocksAllocated;
  68. DequeUnitTestHelper(const SkDeque& deq) {
  69. fNumBlocksAllocated = deq.numBlocksAllocated();
  70. }
  71. };
  72. static void assert_blocks(skiatest::Reporter* reporter,
  73. const SkDeque& deq,
  74. int allocCount) {
  75. DequeUnitTestHelper helper(deq);
  76. if (0 == deq.count()) {
  77. REPORTER_ASSERT(reporter, 1 == helper.fNumBlocksAllocated);
  78. } else {
  79. int expected = (deq.count() + allocCount - 1) / allocCount;
  80. // A block isn't freed in the deque when it first becomes empty so
  81. // sometimes an extra block lingers around
  82. REPORTER_ASSERT(reporter,
  83. expected == helper.fNumBlocksAllocated ||
  84. expected+1 == helper.fNumBlocksAllocated);
  85. }
  86. }
  87. static void TestSub(skiatest::Reporter* reporter, int allocCount) {
  88. SkDeque deq(sizeof(int), allocCount);
  89. int i;
  90. // test pushing on the front
  91. assert_count(reporter, deq, 0);
  92. for (i = 1; i <= 10; i++) {
  93. *(int*)deq.push_front() = i;
  94. }
  95. assert_count(reporter, deq, 10);
  96. assert_iter(reporter, deq, 10, 1);
  97. assert_blocks(reporter, deq, allocCount);
  98. for (i = 0; i < 5; i++) {
  99. deq.pop_front();
  100. }
  101. assert_count(reporter, deq, 5);
  102. assert_iter(reporter, deq, 5, 1);
  103. assert_blocks(reporter, deq, allocCount);
  104. for (i = 0; i < 5; i++) {
  105. deq.pop_front();
  106. }
  107. assert_count(reporter, deq, 0);
  108. assert_blocks(reporter, deq, allocCount);
  109. // now test pushing on the back
  110. for (i = 10; i >= 1; --i) {
  111. *(int*)deq.push_back() = i;
  112. }
  113. assert_count(reporter, deq, 10);
  114. assert_iter(reporter, deq, 10, 1);
  115. assert_blocks(reporter, deq, allocCount);
  116. for (i = 0; i < 5; i++) {
  117. deq.pop_back();
  118. }
  119. assert_count(reporter, deq, 5);
  120. assert_iter(reporter, deq, 10, 6);
  121. assert_blocks(reporter, deq, allocCount);
  122. for (i = 0; i < 5; i++) {
  123. deq.pop_back();
  124. }
  125. assert_count(reporter, deq, 0);
  126. assert_blocks(reporter, deq, allocCount);
  127. // now test pushing/popping on both ends
  128. *(int*)deq.push_front() = 5;
  129. *(int*)deq.push_back() = 4;
  130. *(int*)deq.push_front() = 6;
  131. *(int*)deq.push_back() = 3;
  132. *(int*)deq.push_front() = 7;
  133. *(int*)deq.push_back() = 2;
  134. *(int*)deq.push_front() = 8;
  135. *(int*)deq.push_back() = 1;
  136. assert_count(reporter, deq, 8);
  137. assert_iter(reporter, deq, 8, 1);
  138. assert_blocks(reporter, deq, allocCount);
  139. }
  140. DEF_TEST(Deque, reporter) {
  141. // test it once with the default allocation count
  142. TestSub(reporter, 1);
  143. // test it again with a generous allocation count
  144. TestSub(reporter, 10);
  145. }