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