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 |