GCC Code Coverage Report


Directory: codebase/
File: codebase/library/include/public/lib.LinkedList.hpp
Date: 2023-03-16 04:37:09
Exec Total Coverage
Lines: 112 114 98.2%
Functions: 27 64 42.2%
Branches: 59 73 80.8%

Line Branch Exec Source
1 /**
2 * @file lib.LinkedList.hpp
3 * @author Sergey Baigudin, sergey@baigudin.software
4 * @copyright 2014-2022, Sergey Baigudin, Baigudin Software
5 */
6 #ifndef LIB_LINKEDLIST_HPP_
7 #define LIB_LINKEDLIST_HPP_
8
9 #include "lib.AbstractList.hpp"
10
11 namespace eoos
12 {
13 namespace lib
14 {
15
16 /**
17 * @class LinkedList<T,A>
18 * @brief Doubly linked list.
19 *
20 * @tparam T Data type of container element.
21 * @tparam A Heap memory allocator class.
22 */
23 template <typename T, class A = Allocator>
24 class LinkedList : public AbstractList<T,A>
25 {
26 typedef AbstractList<T,A> Parent;
27
28 public:
29
30 using Parent::isConstructed;
31
32 /**
33 * @brief Constructor.
34 */
35 8 LinkedList()
36 8 : AbstractList<T,A>() {
37 8 }
38
39 /**
40 * @brief Constructor.
41 *
42 * @note A passed element must be copied to an internal data structure of
43 * this class by calling a copy constructor so that the element
44 * might be invalidated after the function called.
45 *
46 * @param illegal An illegal element.
47 */
48 66 LinkedList(T const& illegal)
49 66 : AbstractList<T,A>(illegal) {
50 66 }
51
52 /**
53 * @brief Destructor.
54 */
55 82 virtual ~LinkedList()
56 {
57 }
58
59 /**
60 * @copydoc eoos::api::List::getListIterator(int32_t)
61 */
62 40 virtual api::ListIterator<T>* getListIterator(int32_t const index=0)
63 {
64 40 Iterator<T,A>* it( NULLPTR );
65
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
40 if( isConstructed() )
66 {
67
3/5
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 18 times.
✗ Branch 5 not taken.
40 it = new Iterator<T,A>(index, *this);
68
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 2 times.
40 if( it != NULLPTR )
69 {
70
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 16 times.
36 if( !it->isConstructed() )
71 {
72
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
4 delete it;
73 4 it = NULLPTR;
74 }
75 }
76 }
77
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 4 times.
40 return it;
78 }
79
80 protected:
81
82 using Parent::setConstructed;
83
84 private:
85
86 /**
87 * @class Iterator
88 * @brief The list iterator.
89 *
90 * @note This class is implemented in private zone of the list class.
91 * For this reason, for fast iteration some tests are skipped.
92 * You have to use this class only if it has been constructed.
93 *
94 * @tparam TT Data type of container element.
95 * @tparam AA Heap memory allocator class.
96 */
97 template <typename TT, class AA>
98 class Iterator : public NonCopyable<AA>, public api::ListIterator<TT>
99 {
100 typedef NonCopyable<AA> Parent;
101 typedef LinkedList<TT,AA> List;
102 typedef LinkedNode<TT,AA> Node;
103
104 public:
105
106 /**
107 * @brief Constructor.
108 *
109 * @param index Position in this list.
110 * @param list Reference to self list.
111 */
112 36 Iterator(int32_t const index, List& list)
113 : NonCopyable<AA>()
114 , api::ListIterator<TT>()
115 36 , list_(list)
116 36 , count_(list.getReferenceToCount())
117 36 , last_(list.getReferenceToLast())
118 36 , illegal_(list.getReferenceToIllegal())
119 36 , curs_(NULLPTR)
120 36 , rindex_(ILLEGAL_INDEX) {
121
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
36 bool_t const isConstructed( construct(index) );
122 36 setConstructed( isConstructed );
123 }
124
125 /**
126 * @brief Destructor.
127 */
128
0/4
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
68 virtual ~Iterator(){}
129
130 /**
131 * @copydoc eoos::api::Object::isConstructed()
132 */
133 72 virtual bool_t isConstructed() const ///< SCA MISRA-C++:2008 Justified Rule 10-3-1 and Defected Rule 9-3-3
134 {
135 72 return Parent::isConstructed();
136 }
137
138 /**
139 * @copydoc eoos::api::ListIterator::add(T const&)
140 */
141 18 virtual bool_t add(TT const& element)
142 {
143
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 8 times.
18 if( isModifiedByList() )
144 {
145 2 return false;
146 }
147 16 int32_t const index( getNextIndex() );
148 16 bool_t const res( list_.add(index, element) );
149
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
16 if(res == true)
150 {
151 16 count_.self++; ///< SCA MISRA-C++:2008 Defected Rule 5-2-10
152 16 rindex_ = ILLEGAL_INDEX;
153 }
154 16 return res;
155 }
156
157 /**
158 * @copydoc eoos::api::Iterator::remove()
159 */
160 60 virtual bool_t remove()
161 {
162
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 28 times.
60 if( isModifiedByList() )
163 {
164 4 return false;
165 }
166
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 13 times.
56 if(rindex_ == ILLEGAL_INDEX)
167 {
168 30 return false;
169 }
170 26 Node* curs( curs_ );
171
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 6 times.
26 if( curs_ != NULLPTR )
172 {
173
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 4 times.
14 if(curs_->getIndex() == rindex_)
174 {
175
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
6 curs = (curs_ == last_) ? NULLPTR : curs_->getNext();
176 }
177 }
178 26 bool_t res( list_.remove(rindex_) );
179
1/2
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
26 if(res == true)
180 {
181 26 count_.self++; ///< SCA MISRA-C++:2008 Defected Rule 5-2-10
182 26 rindex_ = ILLEGAL_INDEX;
183 26 curs_ = curs;
184 }
185 26 return res;
186 }
187
188 /**
189 * @copydoc eoos::api::ListIterator::getPrevious()
190 */
191 50 virtual TT& getPrevious()
192 {
193
2/2
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 15 times.
50 if( !hasPrevious() )
194 {
195 20 rindex_ = ILLEGAL_INDEX;
196 20 return illegal_; ///< SCA MISRA-C++:2008 Justified Rule 9-3-2
197 }
198
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 6 times.
30 curs_ = (curs_ == NULLPTR) ? last_ : curs_->getPrevious();
199 30 rindex_ = curs_->getIndex();
200 30 return curs_->getElement();
201 }
202
203 /**
204 * @copydoc eoos::api::ListIterator::getPreviousIndex()
205 */
206 48 virtual int32_t getPreviousIndex() const
207 {
208
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 23 times.
48 if( isModifiedByList() )
209 {
210 2 return api::ListIterator<TT>::ERROR_INDEX;
211 }
212
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 15 times.
46 if( !hasPrevious() )
213 {
214 16 return -1;
215 }
216
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 7 times.
30 return (curs_ == NULLPTR) ? last_->getIndex() : curs_->getPrevious()->getIndex();
217 }
218
219 /**
220 * @copydoc eoos::api::ListIterator::hasPrevious()
221 */
222 144 virtual bool_t hasPrevious() const
223 {
224
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 70 times.
144 if( isModifiedByList() )
225 {
226 4 return false;
227 }
228
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 60 times.
140 if(last_ == NULLPTR)
229 {
230 20 return false;
231 }
232
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 35 times.
120 if(curs_ == NULLPTR)
233 {
234 50 return true;
235 }
236
2/2
✓ Branch 1 taken 15 times.
✓ Branch 2 taken 20 times.
70 if(curs_->getPrevious() == last_)
237 {
238 30 return false;
239 }
240 40 return true;
241 }
242
243 /**
244 * @copydoc eoos::api::Iterator::getNext()
245 */
246 72 virtual TT& getNext()
247 {
248
2/2
✓ Branch 1 taken 17 times.
✓ Branch 2 taken 19 times.
72 if( !hasNext() )
249 {
250 34 rindex_ = ILLEGAL_INDEX;
251 34 return illegal_; ///< SCA MISRA-C++:2008 Justified Rule 9-3-2
252 }
253 38 Node* const node( curs_ );
254
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 10 times.
38 curs_ = (curs_ == last_) ? NULLPTR : curs_->getNext();
255 38 rindex_ = node->getIndex();
256 38 return node->getElement();
257 }
258
259 /**
260 * @copydoc eoos::api::ListIterator::getNextIndex()
261 */
262 58 virtual int32_t getNextIndex() const
263 {
264
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 28 times.
58 if( isModifiedByList() )
265 {
266 2 return api::ListIterator<TT>::ERROR_INDEX;
267 }
268
2/2
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 19 times.
56 return hasNext() ? curs_->getIndex() : static_cast<int32_t>( list_.getLength() );
269 }
270
271 /**
272 * @copydoc eoos::api::Iterator::hasNext()
273 */
274 200 virtual bool_t hasNext() const
275 {
276
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 96 times.
200 if( isModifiedByList() )
277 {
278 8 return false;
279 }
280
2/2
✓ Branch 0 taken 51 times.
✓ Branch 1 taken 45 times.
192 if(curs_ == NULLPTR)
281 {
282 102 return false;
283 }
284 90 return true;
285 }
286
287 /**
288 * @copydoc eoos::api::IllegalValue::getIllegal()
289 */
290 8 virtual TT const& getIllegal() const
291 {
292 8 return list_.getIllegal();
293 }
294
295 /**
296 * @copydoc eoos::api::IllegalValue::setIllegal(T const&)
297 */
298 8 virtual void setIllegal(TT const& value)
299 {
300 8 list_.setIllegal(value);
301 }
302
303 /**
304 * @copydoc eoos::api::IllegalValue::isIllegal(T const&)
305 */
306 8 virtual bool_t isIllegal(TT const& value) const
307 {
308 8 return list_.isIllegal(value);
309 }
310
311 protected:
312
313 using Parent::setConstructed;
314
315 private:
316
317 /**
318 * @brief Constructor.
319 *
320 * @param index Position in this list.
321 */
322 36 bool_t construct(int32_t const index)
323 {
324
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 18 times.
36 if( !isConstructed() )
325 { ///< UT Justified Branch: HW dependency
326 return false;
327 }
328
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 18 times.
36 if( !list_.isConstructed() )
329 { ///< UT Justified Branch: HW dependency
330 return false;
331 }
332
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 16 times.
36 if( list_.isIndexOutOfBounds(index) )
333 {
334 4 return false;
335 }
336 32 curs_ = list_.getNodeByIndex(index);
337 32 return true;
338 }
339
340 /**
341 * @brief Tests if list was modified by list object.
342 *
343 * @param true if modified.
344 */
345 528 bool_t isModifiedByList() const
346 {
347 528 return count_.list != count_.self;
348 }
349
350 /**
351 * @struct Counter
352 * @brief List changing counter.
353 */
354 struct Counter
355 {
356 /**
357 * @brief Constructor.
358 */
359 36 Counter(uint32_t& count)
360 36 : list (count)
361 36 , self (count) {
362 }
363
364 /**
365 * @brief Destructor.
366 */
367 34 ~Counter()
368 {
369 }
370
371 /**
372 * @brief Quantity of chang made by iterating list.
373 */
374 uint32_t const& list; ///< SCA MISRA-C++:2008 Justified Rule 11-0-1
375
376 /**
377 * @brief Quantity of chang made by the iterator.
378 */
379 uint32_t self; ///< SCA MISRA-C++:2008 Justified Rule 11-0-1
380
381 };
382
383 /**
384 * @brief Illegal iterator index
385 */
386 static const int32_t ILLEGAL_INDEX = -1;
387
388 /**
389 * @brief The list of this iterator.
390 */
391 List& list_;
392
393 /**
394 * @brief Number of changes in the iterator list.
395 */
396 Counter count_;
397
398 /**
399 * @brief Last node of the iterator list.
400 */
401 Node*& last_;
402
403 /**
404 * @brief Illegal value of the iterator list.
405 */
406 TT& illegal_;
407
408 /**
409 * @brief Pointer to current node of this iterator that returned as next element.
410 */
411 Node* curs_;
412
413 /**
414 * @brief Index of element of list which can be removed by remove function.
415 */
416 int32_t rindex_;
417
418 };
419 };
420
421 } // namespace lib
422 } // namespace eoos
423 #endif // LIB_LINKEDLIST_HPP_
424