1 // This file is part of CAF, the C++ Actor Framework. See the file LICENSE in
2 // the main distribution directory for license terms and copyright or visit
3 // https://github.com/actor-framework/actor-framework/blob/master/LICENSE.
4 
5 #define CAF_SUITE intrusive.drr_cached_queue
6 
7 #include "caf/intrusive/drr_cached_queue.hpp"
8 
9 #include "caf/test/unit_test.hpp"
10 
11 #include <memory>
12 
13 #include "caf/intrusive/singly_linked.hpp"
14 
15 using namespace caf;
16 using namespace caf::intrusive;
17 
18 namespace {
19 
20 struct inode : singly_linked<inode> {
21   int value;
inode__anon66a0746f0111::inode22   inode(int x = 0) : value(x) {
23     // nop
24   }
25 };
26 
to_string(const inode & x)27 std::string to_string(const inode& x) {
28   return std::to_string(x.value);
29 }
30 
31 struct inode_policy {
32   using mapped_type = inode;
33 
34   using task_size_type = int;
35 
36   using deficit_type = int;
37 
38   using deleter_type = std::default_delete<mapped_type>;
39 
40   using unique_pointer = std::unique_ptr<mapped_type, deleter_type>;
41 
task_size__anon66a0746f0111::inode_policy42   static inline task_size_type task_size(const mapped_type&) noexcept {
43     return 1;
44   }
45 };
46 
47 using queue_type = drr_cached_queue<inode_policy>;
48 
49 struct fixture {
50   inode_policy policy;
51   queue_type queue{policy};
52 
53   template <class Queue>
fill__anon66a0746f0111::fixture54   void fill(Queue&) {
55     // nop
56   }
57 
58   template <class Queue, class T, class... Ts>
fill__anon66a0746f0111::fixture59   void fill(Queue& q, T x, Ts... xs) {
60     q.emplace_back(x);
61     fill(q, xs...);
62   }
63 };
64 
make_new_round_result(size_t consumed_items,bool stop_all)65 auto make_new_round_result(size_t consumed_items, bool stop_all) {
66   return new_round_result{consumed_items, stop_all};
67 }
68 
69 } // namespace
70 
CAF_TEST_FIXTURE_SCOPE(drr_cached_queue_tests,fixture)71 CAF_TEST_FIXTURE_SCOPE(drr_cached_queue_tests, fixture)
72 
73 CAF_TEST(default_constructed) {
74   CAF_REQUIRE_EQUAL(queue.empty(), true);
75   CAF_REQUIRE_EQUAL(queue.deficit(), 0);
76   CAF_REQUIRE_EQUAL(queue.total_task_size(), 0);
77   CAF_REQUIRE_EQUAL(queue.peek(), nullptr);
78 }
79 
CAF_TEST(new_round)80 CAF_TEST(new_round) {
81   // Define a function object for consuming even numbers.
82   std::string fseq;
83   auto f = [&](inode& x) -> task_result {
84     if ((x.value & 0x01) == 1)
85       return task_result::skip;
86     fseq += to_string(x);
87     return task_result::resume;
88   };
89   // Define a function object for consuming odd numbers.
90   std::string gseq;
91   auto g = [&](inode& x) -> task_result {
92     if ((x.value & 0x01) == 0)
93       return task_result::skip;
94     gseq += to_string(x);
95     return task_result::resume;
96   };
97   fill(queue, 1, 2, 3, 4, 5, 6, 7, 8, 9);
98   // Allow f to consume 2, 4, and 6.
99   auto round_result = queue.new_round(3, f);
100   CAF_CHECK_EQUAL(round_result, make_new_round_result(3, false));
101   CAF_CHECK_EQUAL(fseq, "246");
102   CAF_CHECK_EQUAL(queue.deficit(), 0);
103   // Allow g to consume 1, 3, 5, and 7.
104   round_result = queue.new_round(4, g);
105   CAF_CHECK_EQUAL(round_result, make_new_round_result(4, false));
106   CAF_CHECK_EQUAL(gseq, "1357");
107   CAF_CHECK_EQUAL(queue.deficit(), 0);
108 }
109 
CAF_TEST(skipping)110 CAF_TEST(skipping) {
111   // Define a function object for consuming even numbers.
112   std::string seq;
113   auto f = [&](inode& x) -> task_result {
114     if ((x.value & 0x01) == 1)
115       return task_result::skip;
116     seq += to_string(x);
117     return task_result::resume;
118   };
119   CAF_MESSAGE("make a round on an empty queue");
120   CAF_CHECK_EQUAL(queue.new_round(10, f), make_new_round_result(0, false));
121   CAF_MESSAGE("make a round on a queue with only odd numbers (skip all)");
122   fill(queue, 1, 3, 5);
123   CAF_CHECK_EQUAL(queue.new_round(10, f), make_new_round_result(0, false));
124   CAF_MESSAGE("make a round on a queue with an even number at the front");
125   fill(queue, 2);
126   CAF_CHECK_EQUAL(queue.new_round(10, f), make_new_round_result(1, false));
127   CAF_CHECK_EQUAL(seq, "2");
128   CAF_MESSAGE("make a round on a queue with an even number in between");
129   fill(queue, 7, 9, 4, 11, 13);
130   CAF_CHECK_EQUAL(queue.new_round(10, f), make_new_round_result(1, false));
131   CAF_CHECK_EQUAL(seq, "24");
132   CAF_MESSAGE("make a round on a queue with an even number at the back");
133   fill(queue, 15, 17, 6);
134   CAF_CHECK_EQUAL(queue.new_round(10, f), make_new_round_result(1, false));
135   CAF_CHECK_EQUAL(seq, "246");
136 }
137 
CAF_TEST(take_front)138 CAF_TEST(take_front) {
139   std::string seq;
140   fill(queue, 1, 2, 3, 4, 5, 6);
141   auto f = [&](inode& x) {
142     seq += to_string(x);
143     return task_result::resume;
144   };
145   CAF_CHECK_EQUAL(queue.deficit(), 0);
146   while (!queue.empty()) {
147     auto ptr = queue.take_front();
148     f(*ptr);
149   }
150   CAF_CHECK_EQUAL(seq, "123456");
151   fill(queue, 5, 4, 3, 2, 1);
152   while (!queue.empty()) {
153     auto ptr = queue.take_front();
154     f(*ptr);
155   }
156   CAF_CHECK_EQUAL(seq, "12345654321");
157   CAF_CHECK_EQUAL(queue.deficit(), 0);
158 }
159 
CAF_TEST(alternating_consumer)160 CAF_TEST(alternating_consumer) {
161   using fun_type = std::function<task_result(inode&)>;
162   fun_type f;
163   fun_type g;
164   fun_type* selected = &f;
165   // Define a function object for consuming even numbers.
166   std::string seq;
167   f = [&](inode& x) -> task_result {
168     if ((x.value & 0x01) == 1)
169       return task_result::skip;
170     seq += to_string(x);
171     selected = &g;
172     return task_result::resume;
173   };
174   // Define a function object for consuming odd numbers.
175   g = [&](inode& x) -> task_result {
176     if ((x.value & 0x01) == 0)
177       return task_result::skip;
178     seq += to_string(x);
179     selected = &f;
180     return task_result::resume;
181   };
182   /// Define a function object that alternates between f and g.
183   auto h = [&](inode& x) { return (*selected)(x); };
184   // Fill and consume queue, h leaves 9 in the cache since it reads (odd, even)
185   // sequences and no odd value to read after 7 is available.
186   fill(queue, 1, 2, 3, 4, 5, 6, 7, 8, 9);
187   auto round_result = queue.new_round(1000, h);
188   CAF_CHECK_EQUAL(round_result, make_new_round_result(8, false));
189   CAF_CHECK_EQUAL(seq, "21436587");
190   CAF_CHECK_EQUAL(queue.deficit(), 0);
191   CAF_CHECK_EQUAL(deep_to_string(queue.cache()), "[9]");
192 }
193 
CAF_TEST(peek_all)194 CAF_TEST(peek_all) {
195   auto queue_to_string = [&] {
196     std::string str;
197     auto peek_fun = [&](const inode& x) {
198       if (!str.empty())
199         str += ", ";
200       str += std::to_string(x.value);
201     };
202     queue.peek_all(peek_fun);
203     return str;
204   };
205   CAF_CHECK_EQUAL(queue_to_string(), "");
206   queue.emplace_back(2);
207   CAF_CHECK_EQUAL(queue_to_string(), "2");
208   queue.cache().emplace_back(1);
209   CAF_CHECK_EQUAL(queue_to_string(), "2");
210   queue.emplace_back(3);
211   CAF_CHECK_EQUAL(queue_to_string(), "2, 3");
212   queue.flush_cache();
213   CAF_CHECK_EQUAL(queue_to_string(), "1, 2, 3");
214 }
215 
CAF_TEST(to_string)216 CAF_TEST(to_string) {
217   CAF_CHECK_EQUAL(deep_to_string(queue.items()), "[]");
218   fill(queue, 3, 4);
219   CAF_CHECK_EQUAL(deep_to_string(queue.items()), "[3, 4]");
220   fill(queue.cache(), 1, 2);
221   CAF_CHECK_EQUAL(deep_to_string(queue.items()), "[3, 4]");
222   queue.flush_cache();
223   CAF_CHECK_EQUAL(deep_to_string(queue.items()), "[1, 2, 3, 4]");
224 }
225 
226 CAF_TEST_FIXTURE_SCOPE_END()
227