Lumiera  0.pre.03
»edit your freedom«
linked-elements-test.cpp
Go to the documentation of this file.
1 /*
2  LinkedElements(Test) - verify the intrusive single linked list template
3 
4  Copyright (C) Lumiera.org
5  2012, Hermann Vosseler <Ichthyostega@web.de>
6 
7  This program is free software; you can redistribute it and/or
8  modify it under the terms of the GNU General Public License as
9  published by the Free Software Foundation; either version 2 of
10  the License, or (at your option) any later version.
11 
12  This program is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU General Public License for more details.
16 
17  You should have received a copy of the GNU General Public License
18  along with this program; if not, write to the Free Software
19  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 
21 * *****************************************************/
22 
29 #include "lib/test/run.hpp"
30 #include "lib/test/test-helper.hpp"
31 #include "lib/util.hpp"
32 
34 #include "lib/linked-elements.hpp"
35 #include "lib/test/testdummy.hpp"
36 #include "lib/iter-source.hpp"
37 
38 #include <memory>
39 
40 
41 
42 namespace lib {
43 namespace test{
44 
45  namespace error = lumiera::error;
46 
47  using util::isnil;
48  using util::isSameObject;
49  using LERR_(ITER_EXHAUST);
50 
51 
52  namespace { // test data...
53 
54  LUMIERA_ERROR_DEFINE(PROVOKED_FAILURE, "provoked failure");
55 
56  const uint NUM_ELEMENTS = 500;
57  int exception_trigger = -1;
58 
59  inline void __triggerErrorAt(int i) { exception_trigger = i; }
60  inline void __triggerError_reset() { exception_trigger =-1; }
61 
62 
67  struct Nummy
68  : Dummy
69  {
70  Nummy* next;
71 
72  Nummy()
73  : Dummy()
74  , next{0}
75  { }
76 
77  explicit
78  Nummy (int i)
79  : Dummy{i}
80  , next{0}
81  {
82  if (i == exception_trigger)
83  throw error::Fatal("simulated error", LUMIERA_ERROR_PROVOKED_FAILURE);
84  }
85  };
86 
87 
91  template<uint I>
92  struct Num
93  : Nummy
94  {
95  void* storage[I]; // note size depends on template parameter
96 
97  Num (int i=0, int j=0, int k=0)
98  : Nummy(I+i+j+k)
99  { }
100  };
101 
102 
103 
113  : public IterSource<Nummy>
114  {
115  uint maxNum_;
116 
117  virtual Pos
119  {
120  return new Nummy(1);
121  }
122 
123  virtual void
124  nextResult(Pos& num)
125  {
126  uint current = num->getVal();
127  if (maxNum_ <= current)
128  num = 0;
129  else
130  num = new Nummy(current+1);
131  }
132 
133  public:
134  NummyGenerator (uint maxElms)
135  : maxNum_(maxElms)
136  { }
137  };
138 
140  class Populator
141  : public NummyGenerator::iterator
142  {
143  public:
144  explicit
145  Populator (uint numElms)
146  : NummyGenerator::iterator (
147  NummyGenerator::build (new NummyGenerator(numElms)))
148  { }
149  };
150 
151 
152 
153 
154  inline uint
155  sum (uint n)
156  {
157  return n*(n+1) / 2;
158  }
159 
160  }//(End) subversive test data
161 
162 
163 
164 
165 
168 
171 
174 
175 
176 
177  /****************************************************************/
182  class LinkedElements_test : public Test
183  {
184 
185  virtual void
186  run (Arg)
187  {
188  simpleUsage();
189  iterating();
190  reverseList();
191 
192  verify_nonOwnership();
193  verify_ExceptionSafety();
194  populate_by_iterator();
195  verify_RAII_safety();
196  verify_customAllocator();
197  }
198 
199 
200  void
201  simpleUsage()
202  {
203  CHECK (0 == Dummy::checksum());
204  {
205  List elements;
206  CHECK (isnil (elements));
207  CHECK (0 == elements.size());
208  CHECK (0 == Dummy::checksum());
209 
210  elements.emplace<Nummy>(1);
211  elements.emplace<Nummy>(2);
212  elements.emplace<Nummy>(3);
213  elements.emplace<Nummy>(4);
214  elements.emplace<Nummy>(5);
215  CHECK (!isnil (elements));
216  CHECK (5 == elements.size());
217  CHECK (0 != Dummy::checksum());
218 
219  CHECK (Dummy::checksum() == elements[0].getVal()
220  + elements[1].getVal()
221  + elements[2].getVal()
222  + elements[3].getVal()
223  + elements[4].getVal());
224 
225  elements.clear();
226  CHECK (isnil (elements));
227  CHECK (0 == elements.size());
228  CHECK (0 == Dummy::checksum());
229 
230  elements.emplace<Nummy>();
231  elements.emplace<Nummy>();
232  elements.emplace<Nummy>();
233 
234  CHECK (3 == elements.size());
235  CHECK (0 != Dummy::checksum());
236  }
237  CHECK (0 == Dummy::checksum());
238  }
239 
240 
241  void
242  iterating()
243  {
244  CHECK (0 == Dummy::checksum());
245  {
246  List elements;
247  for (uint i=1; i<=NUM_ELEMENTS; ++i)
248  elements.emplace<Nummy>(i);
249 
250  // since elements where pushed,
251  // they should appear in reversed order
252  int check=NUM_ELEMENTS;
253  List::iterator ii = elements.begin();
254  while (ii)
255  {
256  CHECK (check == ii->getVal());
257  CHECK (check == ii->acc(+5) - 5);
258  --check;
259  ++ii;
260  }
261  CHECK (0 == check);
262 
263 
264  // Test the const iterator
265  List const& const_elm (elements);
266  check = NUM_ELEMENTS;
267  List::const_iterator cii = const_elm.begin();
268  while (cii)
269  {
270  CHECK (check == cii->getVal());
271  --check;
272  ++cii;
273  }
274  CHECK (0 == check);
275 
276 
277  // Verify correct behaviour of iteration end
278  CHECK (! (elements.end()));
279  CHECK (isnil (elements.end()));
280 
281  VERIFY_ERROR (ITER_EXHAUST, *elements.end() );
282  VERIFY_ERROR (ITER_EXHAUST, ++elements.end() );
283 
284  CHECK (ii == elements.end());
285  CHECK (ii == List::iterator());
286  CHECK (cii == elements.end());
287  CHECK (cii == List::const_iterator());
288  VERIFY_ERROR (ITER_EXHAUST, ++ii );
289  VERIFY_ERROR (ITER_EXHAUST, ++cii );
290 
291  }
292  CHECK (0 == Dummy::checksum());
293  }
294 
295 
296  void
297  reverseList()
298  {
299  CHECK (0 == Dummy::checksum());
300  {
301  List list;
302  CHECK (isnil (list));
303  list.reverse();
304  CHECK (isnil (list));
305  CHECK (0 == Dummy::checksum());
306 
307  list.emplace<Nummy>(1);
308  CHECK (not isnil (list));
309  CHECK (1 == list[0].getVal());
310  CHECK (1 == Dummy::checksum());
311  list.reverse();
312  CHECK (1 == Dummy::checksum());
313  CHECK (1 == list[0].getVal());
314  CHECK (not isnil (list));
315 
316  list.emplace<Nummy>(2);
317  CHECK (not isnil (list));
318  CHECK (2 == list.size());
319  CHECK (2 == list[0].getVal());
320  CHECK (2+1 == Dummy::checksum());
321  list.reverse();
322  CHECK (1+2 == Dummy::checksum());
323  CHECK (1 == list[0].getVal());
324  CHECK (2 == list.size());
325 
326  list.emplace<Nummy>(3);
327  CHECK (3 == list.size());
328  CHECK (3 == list.top().getVal());
329  CHECK (3+1+2 == Dummy::checksum());
330  list.reverse();
331  CHECK (2 == list[0].getVal());
332  CHECK (1 == list[1].getVal());
333  CHECK (3 == list[2].getVal());
334  List::iterator ii = list.begin();
335  CHECK (2 == ii->getVal());
336  ++ii;
337  CHECK (1 == ii->getVal());
338  ++ii;
339  CHECK (3 == ii->getVal());
340  ++ii;
341  CHECK (isnil (ii));
342  CHECK (2+1+3 == Dummy::checksum());
343 
344  list.emplace<Nummy>(4);
345  CHECK (4 == list.top().getVal());
346  CHECK (3 == list[3].getVal());
347  list.reverse();
348  CHECK (3 == list[0].getVal());
349  CHECK (1 == list[1].getVal());
350  CHECK (2 == list[2].getVal());
351  CHECK (4 == list[3].getVal());
352  CHECK (3+1+2+4 == Dummy::checksum());
353  }
354  CHECK (0 == Dummy::checksum());
355  }
356 
357 
366  void
368  {
369  CHECK (0 == Dummy::checksum());
370  {
372  CHECK (isnil (elements));
373 
374  Num<22> n2;
375  Num<44> n4;
376  Num<66> n6;
377  CHECK (22+44+66 == Dummy::checksum());
378 
379  elements.push(n2);
380  elements.push(n4);
381  elements.push(n6);
382  CHECK (!isnil (elements));
383  CHECK (3 == elements.size());
384  CHECK (22+44+66 == Dummy::checksum()); // not altered: we're referring the originals
385 
386  CHECK (66 == elements[0].getVal());
387  CHECK (44 == elements[1].getVal());
388  CHECK (22 == elements[2].getVal());
389  CHECK (isSameObject(n2, elements[2]));
390  CHECK (isSameObject(n4, elements[1]));
391  CHECK (isSameObject(n6, elements[0]));
392 
393  elements.clear();
394  CHECK (isnil (elements));
395  CHECK (22+44+66 == Dummy::checksum()); // referred elements unaffected
396  }
397  CHECK (0 == Dummy::checksum());
398  }
399 
400 
401  void
402  verify_ExceptionSafety()
403  {
404  CHECK (0 == Dummy::checksum());
405  {
406  List elements;
407  CHECK (isnil (elements));
408 
409  __triggerErrorAt(3);
410 
411  elements.emplace<Nummy>(1);
412  elements.emplace<Nummy>(2);
413  CHECK (1+2 == Dummy::checksum());
414 
415  VERIFY_ERROR (PROVOKED_FAILURE, elements.emplace<Nummy>(3) );
416  CHECK (1+2 == Dummy::checksum());
417  CHECK (2 == elements.size());
418 
419  CHECK (2 == elements[0].getVal());
420  CHECK (1 == elements[1].getVal());
421 
422  elements.clear();
423  CHECK (0 == Dummy::checksum());
424  __triggerError_reset();
425  }
426  CHECK (0 == Dummy::checksum());
427  }
428 
429 
430  void
431  populate_by_iterator()
432  {
433  CHECK (0 == Dummy::checksum());
434  {
435  Populator yieldSomeElements(NUM_ELEMENTS);
436  List elements (yieldSomeElements);
437 
438  CHECK (!isnil (elements));
439  CHECK (NUM_ELEMENTS == elements.size());
440  CHECK (sum(NUM_ELEMENTS) == Dummy::checksum());
441 
442  int check=NUM_ELEMENTS;
443  List::iterator ii = elements.begin();
444  while (ii)
445  {
446  CHECK (check == ii->getVal());
447  --check;
448  ++ii;
449  }
450  CHECK (0 == check);
451  }
452  CHECK (0 == Dummy::checksum());
453  }
454 
455 
462  void
464  {
465  CHECK (0 == Dummy::checksum());
466 
467  __triggerErrorAt(3);
468  Populator yieldSomeElements(NUM_ELEMENTS);
469  VERIFY_ERROR (PROVOKED_FAILURE, List elements(yieldSomeElements) );
470 
471  CHECK (0 == Dummy::checksum());
472  __triggerError_reset();
473  }
474 
475 
476  void
477  verify_customAllocator()
478  {
479  CHECK (0 == Dummy::checksum());
480  {
481  AllocationCluster allocator;
482 
483  ListCustomAllocated elements(allocator);
484 
485  elements.emplace<Num<1>> (2);
486  elements.emplace<Num<3>> (4,5);
487  elements.emplace<Num<6>> (7,8,9);
488 
489  CHECK (sum(9) == Dummy::checksum());
490  CHECK (3 == allocator.size());
491  CHECK (1 == allocator.count<Num<1>>());
492  CHECK (1 == allocator.count<Num<3>>());
493  CHECK (1 == allocator.count<Num<6>>());
494 
495  CHECK (3 == elements.size());
496  CHECK (1+2 == elements[2].getVal());
497  CHECK (3+4+5 == elements[1].getVal());
498  CHECK (6+7+8+9 == elements[0].getVal());
499 
500  elements.clear();
501  CHECK (3 == allocator.size());
502  CHECK (sum(9) == Dummy::checksum());
503  // note: elements won't be discarded unless
504  // the AllocationCluster goes out of scope
505  }
506  CHECK (0 == Dummy::checksum());
507  }
508  };
509 
510 
511 
512  LAUNCHER (LinkedElements_test, "unit common");
513 
514 
515 }} // namespace lib::test
LinkedElements & reverse()
Mutate the complete list to change the order of elements.
IterQueue< T > elements(T const &elm)
convenience free function to build an iterable sequence
Definition: iter-stack.hpp:301
TY & emplace(ARGS &&...args)
prepend object of type TY, forwarding ctor args
size_t count() const
helper for diagnostics
Definition: run.hpp:49
Memory management for the low-level model (render nodes network).
Intrusive single linked list, possibly taking ownership of node elements.
#define VERIFY_ERROR(ERROR_ID, ERRONEOUS_STATEMENT)
Macro to verify that a statement indeed raises an exception.
Iterator-Frontend to generate this series of objects.
Implementation namespace for support and library code.
unittest helper code: test dummy objects to track instances.
Derived specific exceptions within Lumiera&#39;s exception hierarchy.
Definition: error.hpp:199
Iteration source interface to abstract a data source, which then can be accessed through IterAdapter ...
Definition: iter-source.hpp:88
Simple test class runner.
Another Lumiera Forward Iterator building block, based on incorporating a state type right into the i...
Tiny helper functions and shortcuts to be used everywhere Consider this header to be effectively incl...
Helper to produce a pre-determined series of objects to populate a LinkedElements list...
A collection of frequently used helper functions to support unit testing.
Intrusive single linked list with optional ownership.
A Dummy object for tests.
Definition: testdummy.hpp:50
TY & push(TY &elm)
accept the given element and prepend it to the list of elements; depending on the allocation policy...
A pile of objects sharing common allocation and lifecycle.
virtual Pos firstResult()
iteration start: prepare the first element.
virtual void nextResult(Pos &num)
iteration step: switch on to the next element.
Extension module to build an opaque data source, accessible as Lumiera Forward Iterator.
Test-Element, supporting intrusive linked list storage.
#define LUMIERA_ERROR_DEFINE(err, msg)
Definition and initialisation of an error constant.
Definition: error.h:80
bool isSameObject(A const &a, B const &b)
compare plain object identity, bypassing any custom comparison operators.
Definition: util.hpp:372