1 /** @file
2 
3     IntrusiveDList unit tests.
4 
5     @section license License
6 
7     Licensed to the Apache Software Foundation (ASF) under one or more contributor license
8     agreements.  See the NOTICE file distributed with this work for additional information regarding
9     copyright ownership.  The ASF licenses this file to you under the Apache License, Version 2.0
10     (the "License"); you may not use this file except in compliance with the License.  You may
11     obtain a copy of the License at
12 
13     http://www.apache.org/licenses/LICENSE-2.0
14 
15     Unless required by applicable law or agreed to in writing, software distributed under the
16     License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
17     express or implied. See the License for the specific language governing permissions and
18     limitations under the License.
19 */
20 
21 #include <iostream>
22 #include <string_view>
23 #include <string>
24 #include <algorithm>
25 
26 #include "tscpp/util/IntrusiveDList.h"
27 #include "tscpp/util/bwf_base.h"
28 
29 #include "catch.hpp"
30 
31 using ts::IntrusiveDList;
32 
33 // --------------------
34 // Code for documentation - placed here to guarantee the examples at least compile.
35 // First so that additional tests do not require updating the documentation source links.
36 
37 class Message
38 {
39   using self_type = Message; ///< Self reference type.
40 
41 public:
42   // Message severity level.
43   enum Severity { LVL_DEBUG, LVL_INFO, LVL_WARN, LVL_ERROR };
44 
45 protected:
46   std::string _text; // Text of the message.
47   Severity _severity{LVL_DEBUG};
48   int _indent{0}; // indentation level for display.
49 
50   // Intrusive list support.
51   struct Linkage {
52     static self_type *&next_ptr(self_type *); // Link accessor.
53     static self_type *&prev_ptr(self_type *); // Link accessor.
54 
55     self_type *_next{nullptr}; // Forward link.
56     self_type *_prev{nullptr}; // Backward link.
57   } _link;
58 
59   bool is_in_list() const;
60 
61   friend class Container;
62 };
63 
64 auto
next_ptr(self_type * that)65 Message::Linkage::next_ptr(self_type *that) -> self_type *&
66 {
67   return that->_link._next;
68 }
69 auto
prev_ptr(self_type * that)70 Message::Linkage::prev_ptr(self_type *that) -> self_type *&
71 {
72   return that->_link._prev;
73 }
74 
75 bool
is_in_list() const76 Message::is_in_list() const
77 {
78   return _link._next || _link._prev;
79 }
80 
81 class Container
82 {
83   using self_type   = Container;
84   using MessageList = ts::IntrusiveDList<Message::Linkage>;
85 
86 public:
87   ~Container();
88 
89   template <typename... Args> self_type &debug(std::string_view fmt, Args &&... args);
90 
91   size_t count() const;
92   self_type &clear();
93   Message::Severity max_severity() const;
94   void print() const;
95 
96 protected:
97   MessageList _msgs;
98 };
99 
~Container()100 Container::~Container()
101 {
102   this->clear(); // clean up memory.
103 }
104 
105 auto
clear()106 Container::clear() -> self_type &
107 {
108   Message *msg;
109   while (nullptr != (msg = _msgs.take_head())) {
110     delete msg;
111   }
112   _msgs.clear();
113   return *this;
114 }
115 
116 size_t
count() const117 Container::count() const
118 {
119   return _msgs.count();
120 }
121 
122 template <typename... Args>
123 auto
debug(std::string_view fmt,Args &&...args)124 Container::debug(std::string_view fmt, Args &&... args) -> self_type &
125 {
126   Message *msg = new Message;
127   ts::bwprintv(msg->_text, fmt, std::forward_as_tuple(args...));
128   msg->_severity = Message::LVL_DEBUG;
129   _msgs.append(msg);
130   return *this;
131 }
132 
133 Message::Severity
max_severity() const134 Container::max_severity() const
135 {
136   auto spot = std::max_element(_msgs.begin(), _msgs.end(),
137                                [](Message const &lhs, Message const &rhs) { return lhs._severity < rhs._severity; });
138   return spot == _msgs.end() ? Message::Severity::LVL_DEBUG : spot->_severity;
139 }
140 
141 void
print() const142 Container::print() const
143 {
144   for (auto &&elt : _msgs) {
145     std::cout << static_cast<unsigned int>(elt._severity) << ": " << elt._text << std::endl;
146   }
147 }
148 
149 TEST_CASE("IntrusiveDList Example", "[libtscpputil][IntrusiveDList]")
150 {
151   Container container;
152 
153   container.debug("This is message {}", 1);
154   REQUIRE(container.count() == 1);
155   // Destructor is checked for non-crashing as container goes out of scope.
156 }
157 
158 struct Thing {
159   Thing *_next{nullptr};
160   Thing *_prev{nullptr};
161   std::string _payload;
162 
ThingThing163   Thing(std::string_view text) : _payload(text) {}
164 
165   struct Linkage {
166     static Thing *&
next_ptrThing::Linkage167     next_ptr(Thing *t)
168     {
169       return t->_next;
170     }
171     static Thing *&
prev_ptrThing::Linkage172     prev_ptr(Thing *t)
173     {
174       return t->_prev;
175     }
176   };
177 };
178 
179 // Just for you, @maskit ! Demonstrating non-public links and subclassing.
180 class PrivateThing : protected Thing
181 {
182   using self_type  = PrivateThing;
183   using super_type = Thing;
184 
185 public:
PrivateThing(std::string_view text)186   PrivateThing(std::string_view text) : super_type(text) {}
187 
188   struct Linkage {
189     static self_type *&
next_ptrPrivateThing::Linkage190     next_ptr(self_type *t)
191     {
192       return ts::ptr_ref_cast<self_type>(t->_next);
193     }
194     static self_type *&
prev_ptrPrivateThing::Linkage195     prev_ptr(self_type *t)
196     {
197       return ts::ptr_ref_cast<self_type>(t->_prev);
198     }
199   };
200 
201   std::string const &
payload() const202   payload() const
203   {
204     return _payload;
205   }
206 };
207 
208 // End of documentation example code.
209 // If any lines above here are changed, the documentation must be updated.
210 // --------------------
211 
212 using ThingList        = ts::IntrusiveDList<Thing::Linkage>;
213 using PrivateThingList = ts::IntrusiveDList<PrivateThing::Linkage>;
214 
215 TEST_CASE("IntrusiveDList", "[libtscpputil][IntrusiveDList]")
216 {
217   ThingList list;
218   int n;
219 
220   REQUIRE(list.count() == 0);
221   REQUIRE(list.head() == nullptr);
222   REQUIRE(list.tail() == nullptr);
223   REQUIRE(list.begin() == list.end());
224   REQUIRE(list.empty());
225 
226   n = 0;
227   for ([[maybe_unused]] auto &thing : list)
228     ++n;
229   REQUIRE(n == 0);
230   // Check const iteration (mostly compile checks here).
231   for ([[maybe_unused]] auto &thing : static_cast<ThingList const &>(list))
232     ++n;
233   REQUIRE(n == 0);
234 
235   list.append(new Thing("one"));
236   REQUIRE(list.begin() != list.end());
237   REQUIRE(list.tail() == list.head());
238 
239   list.prepend(new Thing("two"));
240   REQUIRE(list.count() == 2);
241   REQUIRE(list.head()->_payload == "two");
242   REQUIRE(list.tail()->_payload == "one");
243   list.prepend(list.take_tail());
244   REQUIRE(list.head()->_payload == "one");
245   REQUIRE(list.tail()->_payload == "two");
246   list.insert_after(list.head(), new Thing("middle"));
247   list.insert_before(list.tail(), new Thing("muddle"));
248   REQUIRE(list.count() == 4);
249   auto spot = list.begin();
250   REQUIRE((*spot++)._payload == "one");
251   REQUIRE((*spot++)._payload == "middle");
252   REQUIRE((*spot++)._payload == "muddle");
253   REQUIRE((*spot++)._payload == "two");
254   REQUIRE(spot == list.end());
255 
256   Thing *thing = list.take_head();
257   REQUIRE(thing->_payload == "one");
258   REQUIRE(list.count() == 3);
259   REQUIRE(list.head() != nullptr);
260   REQUIRE(list.head()->_payload == "middle");
261 
262   list.prepend(thing);
263   list.erase(list.head());
264   REQUIRE(list.count() == 3);
265   REQUIRE(list.head() != nullptr);
266   REQUIRE(list.head()->_payload == "middle");
267   list.prepend(thing);
268 
269   thing = list.take_tail();
270   REQUIRE(thing->_payload == "two");
271   REQUIRE(list.count() == 3);
272   REQUIRE(list.tail() != nullptr);
273   REQUIRE(list.tail()->_payload == "muddle");
274 
275   list.append(thing);
276   list.erase(list.tail());
277   REQUIRE(list.count() == 3);
278   REQUIRE(list.tail() != nullptr);
279   REQUIRE(list.tail()->_payload == "muddle");
280   REQUIRE(list.head()->_payload == "one");
281 
282   list.insert_before(list.end(), new Thing("trailer"));
283   REQUIRE(list.count() == 4);
284   REQUIRE(list.tail()->_payload == "trailer");
285 
286   PrivateThingList priv_list;
287   for (int i = 1; i <= 23; ++i) {
288     std::string name;
289     ts::bwprint(name, "Item {}", i);
290     priv_list.append(new PrivateThing(name));
291     REQUIRE(priv_list.count() == i);
292   }
293   REQUIRE(priv_list.head()->payload() == "Item 1");
294   REQUIRE(priv_list.tail()->payload() == "Item 23");
295 }
296