Micro template library A library for building device drivers
Vous ne pouvez pas sélectionner plus de 25 sujets Les noms de sujets doivent commencer par une lettre ou un nombre, peuvent contenir des tirets ('-') et peuvent comporter jusqu'à 35 caractères.
 
 
 
 

470 lignes
14 KiB

  1. /*!
  2. * \file deque.cpp
  3. * \brief
  4. * Unit tests for deque
  5. *
  6. * \copyright Copyright (C) 2020 Christos Choutouridis <christos@choutouridis.net>
  7. *
  8. * <dl class=\"section copyright\"><dt>License</dt><dd>
  9. * The MIT License (MIT)
  10. *
  11. * Permission is hereby granted, free of charge, to any person obtaining a copy
  12. * of this software and associated documentation files (the "Software"), to deal
  13. * in the Software without restriction, including without limitation the rights
  14. * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  15. * copies of the Software, and to permit persons to whom the Software is
  16. * furnished to do so, subject to the following conditions:
  17. *
  18. * The above copyright notice and this permission notice shall be included in all
  19. * copies or substantial portions of the Software.
  20. *
  21. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  22. * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  23. * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  24. * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  25. * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  26. * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  27. * SOFTWARE.
  28. * </dd></dl>
  29. *
  30. */
  31. #include <utl/container/deque.h>
  32. //#include <utl/container/span.h>
  33. #include <gtest/gtest.h>
  34. #include <array>
  35. #include <type_traits>
  36. #include <cstring>
  37. #ifndef WIN_TRHEADS
  38. #include <mutex>
  39. #include <thread>
  40. #else
  41. #include <mingw.thread.h>
  42. #include <mingw.mutex.h>
  43. #endif
  44. namespace Tdeque {
  45. using namespace utl;
  46. // template <typename>
  47. // struct is_span : std::false_type {};
  48. //
  49. // template <typename T, std::size_t S>
  50. // struct is_span<tbx::span<T, S>> : std::true_type {};
  51. template <typename>
  52. struct is_std_array : std::false_type {};
  53. template <typename T, std::size_t N>
  54. struct is_std_array<std::array<T, N>> : std::true_type {};
  55. template <typename, typename = void>
  56. struct has_size_and_data : std::false_type {};
  57. template <typename T>
  58. struct has_size_and_data<T, std::void_t<decltype(std::declval<T>().size()),
  59. decltype(std::declval<T>().data())>>
  60. : std::true_type {};
  61. // Concept
  62. TEST(Tdeque, concept) {
  63. using deque_t = deque<int, 8>;
  64. EXPECT_EQ ( std::is_default_constructible<deque_t>::value, true);
  65. EXPECT_EQ ( std::is_nothrow_default_constructible<deque_t>::value, true);
  66. EXPECT_EQ (!std::is_copy_constructible<deque_t>::value, true);
  67. EXPECT_EQ (!std::is_copy_assignable<deque_t>::value, true);
  68. // EXPECT_EQ (true, !is_span<deque_t>::value);
  69. EXPECT_EQ (true, !is_std_array<deque_t>::value);
  70. EXPECT_EQ (true, !std::is_array<deque_t>::value);
  71. EXPECT_EQ (true, has_size_and_data<deque_t>::value);
  72. }
  73. // Test construction
  74. TEST(Tdeque, contruct) {
  75. deque<int, 8> q1;
  76. deque<int, 8> q2{1, 2, 3, 4, 5, 6, 7, 8};
  77. deque<int, 8> q3{1, 2, 3, 4, 5};
  78. EXPECT_EQ (8UL, q1.capacity());
  79. EXPECT_EQ (0UL, q1.size());
  80. EXPECT_EQ (8UL, q2.capacity());
  81. EXPECT_EQ (8UL, q2.size());
  82. EXPECT_EQ (8UL, q3.capacity());
  83. EXPECT_EQ (5UL, q3.size());
  84. }
  85. // simple push-pop functionality
  86. TEST(Tdeque, push_pop) {
  87. deque<int, 8> q1;
  88. deque<int, 8> q2{1, 2, 3, 4, 5, 6, 7, 8};
  89. q1.push_front(1);
  90. q1.push_front(2);
  91. EXPECT_EQ (1, q1.pop_back());
  92. EXPECT_EQ (2, q1.pop_back());
  93. q1.push_back(1);
  94. q1.push_back(2);
  95. EXPECT_EQ (1, q1.pop_front());
  96. EXPECT_EQ (2, q1.pop_front());
  97. q1.push_front(2);
  98. q1.push_back(3);
  99. q1.push_front(1);
  100. q1.push_back(4);
  101. for (int i=1 ; i<= 4 ; ++i)
  102. EXPECT_EQ ((int)i, q1.pop_front());
  103. }
  104. // front-back
  105. TEST(Tdeque, front_back) {
  106. deque<int, 8> q1;
  107. deque<int, 8> q2{1, 2, 3, 4, 5, 6, 7, 8};
  108. q1.push_front(2);
  109. q1.push_front(1);
  110. q1.push_back(3);
  111. q1.push_back(4);
  112. EXPECT_EQ (1, q1.front());
  113. EXPECT_EQ (4, q1.back());
  114. EXPECT_EQ (1, q2.front());
  115. EXPECT_EQ (8, q2.back());
  116. }
  117. // capacity
  118. TEST(Tdeque, capacity) {
  119. deque<int, 8> q1;
  120. deque<int, 8> q2{1, 2, 3, 4, 5, 6, 7, 8};
  121. q1.push_back(1);
  122. q1.clear();
  123. EXPECT_EQ (true, q1.empty());
  124. EXPECT_EQ (true, q2.full());
  125. EXPECT_EQ (8UL, q1.capacity());
  126. EXPECT_EQ (8UL, q2.capacity());
  127. EXPECT_EQ (0UL, q1.size());
  128. EXPECT_EQ (8UL, q2.size());
  129. q1.push_back(2);
  130. EXPECT_EQ (1UL, q1.size());
  131. q1.push_front(1);
  132. EXPECT_EQ (2UL, q1.size());
  133. q1.pop_back();
  134. EXPECT_EQ (1UL, q1.size());
  135. q1.pop_front();
  136. EXPECT_EQ (0UL, q1.size());
  137. }
  138. // push-pop limits
  139. TEST (Tdeque, push_pop_limits) {
  140. deque<int, 8> q1;
  141. deque<int, 8> q2{1, 2, 3, 4, 5, 6, 7, 8};
  142. EXPECT_EQ (int{}, q1.pop_back());
  143. EXPECT_EQ (0UL, q1.size());
  144. EXPECT_EQ (true, q1.empty());
  145. EXPECT_EQ (false, q1.full());
  146. EXPECT_EQ (int{}, q1.pop_front());
  147. EXPECT_EQ (0UL, q1.size());
  148. EXPECT_EQ (true, q1.empty());
  149. EXPECT_EQ (false, q1.full());
  150. q2.push_front(0);
  151. EXPECT_EQ (1, q2.front());
  152. EXPECT_EQ (8, q2.back());
  153. EXPECT_EQ (8UL, q2.size());
  154. EXPECT_EQ (false, q2.empty());
  155. EXPECT_EQ (true, q2.full());
  156. q2.push_back(9);
  157. EXPECT_EQ (1, q2.front());
  158. EXPECT_EQ (8, q2.back());
  159. EXPECT_EQ (8UL, q2.size());
  160. EXPECT_EQ (false, q2.empty());
  161. EXPECT_EQ (true, q2.full());
  162. }
  163. // iterators
  164. TEST (Tdeque, iterators) {
  165. deque<int, 8> q1{1, 2, 3, 4, 5, 6, 7, 8};
  166. int check_it=1;
  167. EXPECT_EQ (q1.begin().base(), q1.end().base());
  168. EXPECT_NE (q1.begin().iter(), q1.end().iter());
  169. EXPECT_EQ (1, *q1.begin());
  170. EXPECT_EQ (true, (q1.begin() == ++q1.end())); // loop edge iterators
  171. for (auto it = q1.begin() ; it != q1.end() ; ++it)
  172. EXPECT_EQ(*it, check_it++);
  173. EXPECT_EQ(9, check_it); // run through all
  174. EXPECT_EQ (1, q1.front()); // queue stays intact
  175. EXPECT_EQ (8, q1.back());
  176. EXPECT_EQ (8UL, q1.size());
  177. EXPECT_EQ (false, q1.empty());
  178. EXPECT_EQ (true, q1.full());
  179. q1.pop_front();
  180. q1.pop_back();
  181. check_it=2;
  182. for (auto& it : q1)
  183. EXPECT_EQ(it, check_it++);
  184. EXPECT_EQ(8, check_it); // run through all
  185. EXPECT_EQ (2, q1.front()); // queue stays intact
  186. EXPECT_EQ (7, q1.back());
  187. EXPECT_EQ (6UL, q1.size());
  188. EXPECT_EQ (false, q1.empty());
  189. EXPECT_EQ (false, q1.full());
  190. deque<int, 8> q2;
  191. q2.push_front(2);
  192. q2.push_front(1);
  193. q2.push_back(3);
  194. q2.push_back(4);
  195. q2.push_back(5);
  196. check_it =1;
  197. for (auto& it : q2)
  198. EXPECT_EQ(it, check_it++);
  199. EXPECT_EQ(6, check_it); // run through all
  200. }
  201. TEST (Tdeque, range) {
  202. deque<int, 8> q1{1, 2, 3, 4, 5, 6, 7, 8};
  203. int check_it=1;
  204. for (auto& it : q1.contents())
  205. EXPECT_EQ(it, check_it++);
  206. EXPECT_EQ(9, check_it); // run through all
  207. }
  208. // Concept
  209. TEST(Tdeque, concept_atomic) {
  210. using deque_t = deque<int, 8, true>;
  211. // EXPECT_EQ (true, !is_span<deque_t>::value);
  212. EXPECT_EQ (true, !is_std_array<deque_t>::value);
  213. EXPECT_EQ (true, !std::is_array<deque_t>::value);
  214. EXPECT_EQ (true, has_size_and_data<deque_t>::value);
  215. }
  216. // Test construction
  217. TEST(Tdeque, contruct_atomic) {
  218. deque<int, 8, true> q1;
  219. deque<int, 8, true> q2{1, 2, 3, 4, 5, 6, 7, 8};
  220. deque<int, 8, true> q3{1, 2, 3, 4, 5};
  221. EXPECT_EQ (8UL, q1.capacity());
  222. EXPECT_EQ (0UL, q1.size());
  223. EXPECT_EQ (8UL, q2.capacity());
  224. EXPECT_EQ (8UL, q2.size());
  225. EXPECT_EQ (8UL, q3.capacity());
  226. EXPECT_EQ (5UL, q3.size());
  227. }
  228. // simple push-pop functionality
  229. TEST(Tdeque, push_pop_atomic) {
  230. deque<int, 8, true> q1;
  231. deque<int, 8, true> q2{1, 2, 3, 4, 5, 6, 7, 8};
  232. q1.push_front(1);
  233. q1.push_front(2);
  234. EXPECT_EQ (1, q1.pop_back());
  235. EXPECT_EQ (2, q1.pop_back());
  236. q1.push_back(1);
  237. q1.push_back(2);
  238. EXPECT_EQ (1, q1.pop_front());
  239. EXPECT_EQ (2, q1.pop_front());
  240. q1.push_front(2);
  241. q1.push_back(3);
  242. q1.push_front(1);
  243. q1.push_back(4);
  244. for (int i=1 ; i<= 4 ; ++i)
  245. EXPECT_EQ ((int)i, q1.pop_front());
  246. }
  247. // front-back
  248. TEST(Tdeque, front_back_atomic) {
  249. deque<int, 8, true> q1;
  250. deque<int, 8, true> q2{1, 2, 3, 4, 5, 6, 7, 8};
  251. q1.push_front(2);
  252. q1.push_front(1);
  253. q1.push_back(3);
  254. q1.push_back(4);
  255. EXPECT_EQ (1, q1.front());
  256. EXPECT_EQ (4, q1.back());
  257. EXPECT_EQ (1, q2.front());
  258. EXPECT_EQ (8, q2.back());
  259. }
  260. // capacity
  261. TEST(Tdeque, capacity_atomic) {
  262. deque<int, 8, true> q1;
  263. deque<int, 8, true> q2{1, 2, 3, 4, 5, 6, 7, 8};
  264. q1.push_back(1);
  265. q1.clear();
  266. EXPECT_EQ (true, q1.empty());
  267. EXPECT_EQ (true, q2.full());
  268. EXPECT_EQ (8UL, q1.capacity());
  269. EXPECT_EQ (8UL, q2.capacity());
  270. EXPECT_EQ (0UL, q1.size());
  271. EXPECT_EQ (8UL, q2.size());
  272. q1.push_back(2);
  273. EXPECT_EQ (1UL, q1.size());
  274. q1.push_front(1);
  275. EXPECT_EQ (2UL, q1.size());
  276. q1.pop_back();
  277. EXPECT_EQ (1UL, q1.size());
  278. q1.pop_front();
  279. EXPECT_EQ (0UL, q1.size());
  280. }
  281. // push-pop limits
  282. TEST (Tdeque, push_pop_limits_atomic) {
  283. deque<int, 8, true> q1;
  284. deque<int, 8, true> q2{1, 2, 3, 4, 5, 6, 7, 8};
  285. EXPECT_EQ (int{}, q1.pop_back());
  286. EXPECT_EQ (0UL, q1.size());
  287. EXPECT_EQ (true, q1.empty());
  288. EXPECT_EQ (false, q1.full());
  289. EXPECT_EQ (int{}, q1.pop_front());
  290. EXPECT_EQ (0UL, q1.size());
  291. EXPECT_EQ (true, q1.empty());
  292. EXPECT_EQ (false, q1.full());
  293. q2.push_front(0);
  294. EXPECT_EQ (1, q2.front());
  295. EXPECT_EQ (8, q2.back());
  296. EXPECT_EQ (8UL, q2.size());
  297. EXPECT_EQ (false, q2.empty());
  298. EXPECT_EQ (true, q2.full());
  299. q2.push_back(9);
  300. EXPECT_EQ (1, q2.front());
  301. EXPECT_EQ (8, q2.back());
  302. EXPECT_EQ (8UL, q2.size());
  303. EXPECT_EQ (false, q2.empty());
  304. EXPECT_EQ (true, q2.full());
  305. }
  306. // iterators
  307. TEST (Tdeque, iterators_atomic) {
  308. deque<int, 8, true> q1{1, 2, 3, 4, 5, 6, 7, 8};
  309. int check_it=1;
  310. EXPECT_EQ (q1.begin().base(), q1.end().base());
  311. EXPECT_NE (q1.begin().iter(), q1.end().iter());
  312. EXPECT_EQ (1, *q1.begin());
  313. EXPECT_EQ (true, (q1.begin() == ++q1.end())); // loop edge iterators
  314. for (auto it = q1.begin() ; it != q1.end() ; ++it)
  315. EXPECT_EQ(*it, check_it++);
  316. EXPECT_EQ(9, check_it); // run through all
  317. EXPECT_EQ (1, q1.front()); // queue stays intact
  318. EXPECT_EQ (8, q1.back());
  319. EXPECT_EQ (8UL, q1.size());
  320. EXPECT_EQ (false, q1.empty());
  321. EXPECT_EQ (true, q1.full());
  322. q1.pop_front();
  323. q1.pop_back();
  324. check_it=2;
  325. for (auto& it : q1)
  326. EXPECT_EQ(it, check_it++);
  327. EXPECT_EQ(8, check_it); // run through all
  328. EXPECT_EQ (2, q1.front()); // queue stays intact
  329. EXPECT_EQ (7, q1.back());
  330. EXPECT_EQ (6UL, q1.size());
  331. EXPECT_EQ (false, q1.empty());
  332. EXPECT_EQ (false, q1.full());
  333. deque<int, 8, true> q2;
  334. q2.push_front(2);
  335. q2.push_front(1);
  336. q2.push_back(3);
  337. q2.push_back(4);
  338. q2.push_back(5);
  339. check_it =1;
  340. for (auto& it : q2)
  341. EXPECT_EQ(it, check_it++);
  342. EXPECT_EQ(6, check_it); // run through all
  343. }
  344. TEST (Tdeque, range_atomic) {
  345. deque<int, 8, true> q1{1, 2, 3, 4, 5, 6, 7, 8};
  346. int check_it=1;
  347. for (auto& it : q1.contents())
  348. EXPECT_EQ(it, check_it++);
  349. EXPECT_EQ(9, check_it); // run through all
  350. }
  351. TEST(Tdeque, race) {
  352. constexpr size_t N = 1000000;
  353. deque<int, N, true> q;
  354. int result[N];
  355. auto push_front = [&](){
  356. for (size_t i=1 ; i<=N ; ++i) q.push_front(i);
  357. };
  358. auto push_back = [&](){
  359. for (size_t i=1 ; i<=N ; ++i) q.push_back(i);
  360. };
  361. auto pop_front = [&](){
  362. for (size_t i=0 ; i<N ; ) {
  363. result[i] = q.pop_front();
  364. if (result[i] != int{})
  365. ++i;
  366. }
  367. };
  368. auto pop_back = [&](){
  369. for (size_t i=0 ; i<N ; ) {
  370. result[i] = q.pop_back();
  371. if (result[i] != int{})
  372. ++i;
  373. }
  374. };
  375. std::memset(result, 0, sizeof result);
  376. std::thread th1 (push_front);
  377. std::thread th2 (pop_back);
  378. th1.join();
  379. th2.join();
  380. for (size_t i=0 ; i<N ; ++i)
  381. EXPECT_EQ (result[i], (int)i+1);
  382. std::memset(result, 0, sizeof result);
  383. std::thread th3 (push_back);
  384. std::thread th4 (pop_front);
  385. th3.join();
  386. th4.join();
  387. for (size_t i=0 ; i<N ; ++i)
  388. EXPECT_EQ (result[i], (int)i+1);
  389. }
  390. }