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