pfodParser 3.61.0 The pfodParser library is handles commands sent from the Android pfodApp, pfodApp supports WiFi, BLE, Bluetooth and SMS connections

pfodLinkedList.h
Go to the documentation of this file.
1 #ifndef PFOD_LINKEDLIST_H_
2 #define PFOD_LINKEDLIST_H_
3 // pfodLinkedList.h
4 /*
5 Revised 2022/09/26 to leave iterator unchanged except for remove() and getFirst()/getNext()
6
7 Modified by Matthew Ford to remove index and only use pointers and add getFirst(), getNext() iterator
8 Now acts as LOFO list
9 NULL data pointers not added to list
10 Not longer limited to 255 elements. Only limited by available memory. Still no caching
11 !! NOTE CAREFULLY !! This version pfodLinkedList DOES NOT call delete() on the data pointers so the call must clean up if necessary
12
13 (c)2022 Forward Computing and Control Pty. Ltd.
14 This code is not warranted to be fit for any purpose. You may only use it at your own risk.
15 These modifications may be freely used for both private and commercial use subject to the included LICENSE file
16 Provide this copyright is maintained.
17 */
18
19 /*
20
21 Light-weight implementation of LinkedList, appropriate for use in Arduino and other memory-critical environments.
22
23 - Handling pointers, rather than copies of actual contained objects.
24 - Up to 255 entries
25 - No last element pointer
26 - No sequential get-cache
27 - No support for sorting
28
29 This object consumes just 5 bytes per instance + 4 per node, making itself more appropriate for use in memory-critical
30 environments. Since the class is targeted for use with small lists with up to a few dozens of entries, the optimization
31 cuts are not significantly affecting the performance.
32
33 Based on LinkedList library by ivanseidel (https://github.com/ivanseidel/LinkedList).
34
35 Created on: 31. sij 2017.
36 Author: JonnieZG
37 */
38
39 #include <stddef.h>
40
41 template<class T>
42 struct pfodListNode {
43 T *data;
44 pfodListNode<T> *next;
45 };
46
47 template<typename T>
48 class pfodLinkedList {
49
50 protected:
51 pfodListNode<T> *root;
52 pfodListNode<T> *current; // for list tranversals
53 size_t count; // the number of items in the list
54
55 public:
56 pfodLinkedList();
57 virtual ~pfodLinkedList(); // calls clear to release the list containers, DOES NOT call delete on data so caller needs to clean up if necessary
58 /*
59 The size of the list
60 @ret - the current number of elements in the list
61 */
62 virtual size_t size();
63
64 /*
65 Adds this data pointer at the front of the list
66 NULL data pointers not added to list
67 current iterator not changed, call getFirst() to include this new element
68 @ret - true if added, else false if data pointer NULL or out of memory
69 */
70 virtual bool add(T*);
71
72 /*
73 Adds this data pointer at the end of the list
74 NULL data pointers not added to list
75 current iterator not changed
76 @ret - true if added, else false if data pointer NULL or out of memory
77 */
78 virtual bool append(T* _t);
79
80 /*
81 returns the index of data pointer or size() if not found
82 current iterator is NOT changed
83 @ret - index of this data, or size() if not found
84 */
85 virtual size_t getIndex(T*);
86
87 /*
88 returns the data pointer if the current iterator, can be NULL
89 use to mark current position and then reset later using
90 setCurrentIterator( )
91 @ret - NULL or point to list data
92 */
93 virtual T* getCurrentIterator();
94
95 /*
96 sets list iterator to this data item
97 getNext() will get the next item
98 If arg is NULL just set current iterator to NULL
99 If the dataItem is not longer on the list the current iterator is set to NULL
100 @ret - true if _current still in list
101 */
102 virtual bool setCurrentIterator(T* _current);
103
104 /*
105 Removes this data pointer
106 current iterator is set to NULL if its item is removed
107 @ret - NULL if data pointer not found on the list, else the removed data element pointer
108 */
109 virtual T* remove(T*);
110
111 /*
112 Removes this data pointer
113 current iterator is set to NULL if its item is removed
114 @ret - NULL if idx not found on the list, else the removed data element
115 */
116 virtual T* remove(size_t idx);
117
118 /*
119 inserts this data pointer at the idx, if idx >= size() append at end
120 current iterator is not changed
121 @ret - true if inserted, else false
122 */
123 virtual bool insertAt(T*, size_t idx);
124
125 /*
126 Removes first element
127 Use this repeatedly to clear list.
128 You need to free() the data pointer returned
129 current iterator is set to NULL if its item is removed
130 @ret - NULL if list empty, else first data element pointer
131 */
132 virtual T* remove();
133
134 /*
135 get the root of the list
136 Sets current interator to root
137 @ret - NULL at end of list, else first data element pointer
138 */
139 virtual T* getFirst();
140
141 /* get next element in list
142 using current interator
143 @ret - NULL at end of list, else next element
144 */
145 virtual T* getNext();
146
147 /* get idx element in list
148 current iterator is NOT changed
149 @ret - NULL if idx >= size()
150 */
151 virtual T* get(size_t idx);
152
153 /*
154 This is also called by the destructor when the list goes out of scope!!
155 !! NOTE CAREFULLY !! The destructor and clear() DOES NOT call delete() on the data pointers so caller needs to clearn up if necessary
156 Using pointers returned from malloc etc will most likely crash when clear() is called.
157 */
158 virtual void clear();
159
160 };
161
162 // pfodLinkedList.cpp
163 /*
164 Modified by Matthew Ford to remove index and only use pointers and add getFirst(), getNext() iterator
165 Now acts as LOFO list
166 NULL data pointers not added to list
167 Not longer limited to 255 elements. Only limited by available memory. Still no caching
168 !! NOTE CAREFULLY !! The destructor and clear() DOES NOT call delete() on the data pointers so caller needs to clearn up if necessary
169
170 (c)2022 Forward Computing and Control Pty. Ltd.
171 This code is not warranted to be fit for any purpose. You may only use it at your own risk.
172 These modifications may be freely used for both private and commercial use subject to the included LICENSE file
173 Provide this copyright is maintained.
174 */
175
176 /*
177
178 Light-weight implementation of LinkedList, appropriate for use in Arduino and other memory-critical environments.
179
180 - Handling pointers, rather than copies of actual contained objects.
181 - Up to 255 entries
182 - No last element pointer
183 - No sequential get-cache
184 - No support for sorting
185
186 This object consumes just 5 bytes per instance + 4 per node, making itself more appropriate for use in memory-critical
187 environments. Since the class is targeted for use with small lists with up to a few dozens of entries, the optimization
188 cuts are not significantly affecting the performance.
189
190 Based on LinkedList library by ivanseidel (https://github.com/ivanseidel/LinkedList).
191
192 Created on: 31. sij 2017.
193 Author: JonnieZG
194 */
195
196 // ------------ Template Implementation ------------
197
198 #include "pfodLinkedList.h"
199
200 template<typename T>
201 pfodLinkedList<T>::pfodLinkedList() {
202 root = NULL;
203 current = NULL;
204 }
205
206 /*
207 calls clear to release all data as well as the list containers
208 */
209 template<typename T>
210 pfodLinkedList<T>::~pfodLinkedList() {
211 clear();
212 }
213
214 /*
215 The size of the list
216 @ret - the current number of elements in the list
217 */
218 template<typename T>
219 size_t pfodLinkedList<T>::size() {
220 return count;
221 }
222
223 /*
224 Adds this data pointer at the front of the list
225 NULL data pointers not added to list
226 current iterator not changed, call getFirst() to include this new element
227 @ret - true if added, else false if data pointer NULL or out of memory
228 */
229 template<typename T>
230 bool pfodLinkedList<T>::add(T* _t) {
231 if (_t == NULL) {
232 return false;
233 }
234 size_t idx = getIndex(_t);
235 if (idx != size()) {
236 return false; // already on list
237 }
238 pfodListNode<T> *tmp = new pfodListNode<T>();
239 if (tmp == NULL) {
240 return false;
241 }
242 tmp->data = _t;
243 tmp->next = root;
244 root = tmp;
245 count++;
246 return true;
247 }
248
249 /*
250 Adds this data pointer at the end of the list
251 NULL data pointers not added to list
252 current iterator not changed
253 @ret - true if added, else false if data pointer NULL or out of memory
254 */
255 template<typename T>
256 bool pfodLinkedList<T>::append(T* _t) {
257 if (_t == NULL) {
258 return false;
259 }
260 size_t idx = getIndex(_t);
261 // if size() == 0, then not on list
262 // then idx will be returned as 0 so size()==idx
263 if (idx != size()) {
264 return false; // already on list
265 }
266 // else not on list or list empty
267 pfodListNode<T> *tmp = new pfodListNode<T>();
268 if (tmp == NULL) {
269 return false;
270 }
271 tmp->data = _t;
272 if (root == NULL) {
273 root = tmp;
274 } else {
275 pfodListNode<T> *currentPtr = root;
276 while (currentPtr->next != NULL) {
277 currentPtr = currentPtr->next;
278 }
279 currentPtr->next = tmp;
280 }
281 count++;
282 return true;
283 }
284
285 /*
286 Removes this data pointer
287 current iterator is set to NULL if its item is removed
288 @ret - NULL if data pointer not found on the list, else the removed data element pointer
289 */
290 template<typename T>
291 T* pfodLinkedList<T>::remove(T * _t) {
292 if ((root == NULL) || (_t == NULL)) {
293 return NULL;
294 }
295 T* rtnData = NULL;
296 pfodListNode<T> *toDelete = NULL;
297 if (root->data == _t) {
298 toDelete = root;
299 root = toDelete->next;
300 rtnData = toDelete->data;
301 if (current == toDelete) {
302 current = NULL;
303 }
304 delete(toDelete);
305 if (count >= 1) {
306 count--;
307 }
308 return rtnData;
309 }
310 // else not root
311 pfodListNode<T>* lastListPtr = root;
312 pfodListNode<T>* listPtr = root->next;
313 while (listPtr) {
314 if (listPtr->data == _t) {
315 // found it
316 toDelete = listPtr;
317 lastListPtr->next = toDelete->next;
318 rtnData = toDelete->data;
319 if (current == toDelete) {
320 current = NULL; // so getNext() returns next element in list
321 }
322 delete(toDelete);
323 if (count >= 1) {
324 count--;
325 }
326 return rtnData;
327 }
328 // else get next
329 lastListPtr = listPtr;
330 listPtr = listPtr->next;
331 }
332 return rtnData; // NULL; // null not found
333 }
334
335 /*
336 returns the index of data pointer or size() if not found
337 current iterator is NOT updated
338 @ret - index of this data, or size() if not found
339 */
340 template<typename T>
341 size_t pfodLinkedList<T>::getIndex(T * _t) {
342 if ((root == NULL) || (_t == NULL)) {
343 return size();
344 }
345 size_t idx = 0;
346 pfodListNode<T>* listPtr = root;
347 while (listPtr) {
348 if (listPtr->data == _t) { // found it
349 return idx;
350 }
351 idx++;
352 listPtr = listPtr->next;
353 }
354 return size(); // not found
355 }
356
357 /*
358 returns the data pointer if the current iterator, can be NULL
359 use to mark current position and then reset later using
360 setCurrentIterator( ) to restore it
361 @ret - NULL or point to list data
362 */
363 template<typename T>
364 T* pfodLinkedList<T>::getCurrentIterator() {
365 if (current) {
366 return current->data;
367 } //
368 return NULL;
369 }
370
371 /*
372 sets list iterator to this data item
373 getNext() will get the next item
374 If arg is NULL just set current iterator to NULL
375 If the dataItem is not longer on the list the current iterator is set to NULL
376 */
377 template<typename T>
378 bool pfodLinkedList<T>::setCurrentIterator(T* _current) {
379 current = NULL;
380 if ((root == NULL) || (_current == NULL)) {
381 return false;
382 }
383 pfodListNode<T>* listPtr = root;
384 while (listPtr) {
385 if (listPtr->data == _current) { // found it
386 current = listPtr;
387 return true;
388 }
389 listPtr = listPtr->next;
390 }
391 // not found leave as NULL
392 return false;
393 }
394
395 /*
396 Removes this data pointer
397 current iterator is set to NULL if its item is removed
398 @ret - NULL if idx not found on the list, else the removed data element
399 */
400 template<typename T>
401 T* pfodLinkedList<T>::remove(size_t idx) {
402 if ((root == NULL) || (idx >= size())) {
403 return NULL;
404 }
405 T* rtnData = NULL;
406 rtnData = get(idx); // can be null
407 return remove(rtnData); // handles null // updates size() // deletes linklist obj but not the data
408 }
409
410 /*
411 inserts this data pointer at the idx, current idx is pushed to idx+1
412 if idx >= size() append at end
413 current iterator is not changed
414 @ret - true if inserted, else false if already in list or memory alloc failed
415 */
416 template<typename T>
417 bool pfodLinkedList<T>::insertAt(T* _t, size_t idx) {
418 size_t existingIdx = getIndex(_t); // can be null
419 if (existingIdx != size()) { // works for empty list as well empty list returns 0 (size())
420 return false; // already on list
421 }
422 // else find idx and insert there
423 if (idx >= size()) {
424 return append(_t); // at end
425 }
426 if (idx == 0) {
427 return add(_t);
428 }
429 pfodListNode<T> *tmp = new pfodListNode<T>();
430 if (tmp == NULL) {
431 return false;
432 }
433 tmp->data = _t;
434
435 // else get idx-1 to position current
436 size_t idx_1 = idx - 1; // idx >0 from above
437 pfodListNode<T>* currentPtr = root;
438 size_t count = 0;
439 while ((count < idx_1) && (currentPtr != NULL)) {
440 currentPtr = currentPtr->next;
441 count++;
442 }
443 // currentPtr is idx-1
444 pfodListNode<T>* lastListPtr = currentPtr;
445 pfodListNode<T>* nextListPtr = currentPtr->next;
446 // insert
447 lastListPtr->next = tmp;
448 tmp->next = nextListPtr;
449 count++;
450 return true;
451 }
452
453 /*
454 Removes first element
455 Use this repeatedly to clear list.
456 You need to free() the data pointer returned
457 current iterator is set to NULL if its item is removed
458 @ret - NULL if list empty, else first data element pointer
459 */
460 template<typename T>
461 T* pfodLinkedList<T>::remove() {
462 if (root == NULL) {
463 return NULL;
464 }
465 T* rtnData = NULL;
466 pfodListNode<T> *toDelete = NULL;
467 toDelete = root;
468 root = toDelete->next;
469 rtnData = toDelete->data;
470 if (current == toDelete) {
471 current = NULL;
472 }
473 delete(toDelete);
474 if (count >= 1) {
475 count--;
476 }
477 return rtnData;
478 }
479
480 /*
481 get the root of the list
482 Sets current interator to root
483 @ret - NULL at end of list, else first data element pointer
484 */
485 template<typename T>
486 T* pfodLinkedList<T>::getFirst() {
487 current = root;
488 if (current) {
489 return (current->data);
490 } // else
491 return NULL;
492 }
493
494 /* get next element in list
495 using current interator
496 @ret - NULL at end of list, else next element
497 */
498 template<typename T>
499 T* pfodLinkedList<T>::getNext() {
500 if (current == NULL) {
501 return NULL;
502 } // else
503 current = current->next;
504 if (current) {
505 return (current->data);
506 } // else
507 return NULL;
508 }
509
510 /* get idx element in list
511 current iterator is NOT changed
512 @ret - NULL if idx >= size()
513 */
514 template<typename T>
515 T* pfodLinkedList<T>::get(size_t idx) {
516 pfodListNode<T>* currentPtr = root;
517 if (currentPtr == NULL) {
518 return NULL;
519 } // else
520 size_t count = 0;
521 while ((count < idx) && (currentPtr != NULL)) {
522 currentPtr = currentPtr->next;
523 count++;
524 }
525 if (currentPtr) {
526 return (currentPtr->data);
527 } // else
528 return NULL;
529 }
530
531 /*
532 This is also called by the destructor when the list goes out of scope!!
533 !! NOTE CAREFULLY !! The destructor and clear() now DOES NOT call delete() on the data pointers so call needs to clean up if necessary
534 */
535 template<typename T>
536 void pfodLinkedList<T>::clear() {
537 pfodListNode<T>* tmp;
538 current = NULL;
539 while (root != NULL) {
540 tmp = root;
541 root = root->next;
542 //delete tmp->data; // must be class created with new ...
543 // pfodLinkedList does not delete data
544 tmp->data = NULL;
545 delete tmp;
546 tmp = NULL;
547 }
548 count = 0;
549 }
550
551 #endif /* PFOD_LINKEDLIST_H_ */
pfodLinkedList
Definition: pfodLinkedList.h:48
pfodLinkedList::current
pfodListNode< T > * current
Definition: pfodLinkedList.h:52
pfodLinkedList::clear
virtual void clear()
Definition: pfodLinkedList.h:536
pfodLinkedList::pfodLinkedList
pfodLinkedList()
Definition: pfodLinkedList.h:201
pfodLinkedList::remove
virtual T * remove(size_t idx)
Definition: pfodLinkedList.h:401
pfodLinkedList::getFirst
virtual T * getFirst()
Definition: pfodLinkedList.h:486
pfodLinkedList::remove
virtual T * remove(T *)
Definition: pfodLinkedList.h:291
pfodLinkedList::append
virtual bool append(T *_t)
Definition: pfodLinkedList.h:256
pfodLinkedList::get
virtual T * get(size_t idx)
Definition: pfodLinkedList.h:515
pfodLinkedList::getNext
virtual T * getNext()
Definition: pfodLinkedList.h:499
pfodLinkedList::getCurrentIterator
virtual T * getCurrentIterator()
Definition: pfodLinkedList.h:364
pfodLinkedList::count
size_t count
Definition: pfodLinkedList.h:53
pfodLinkedList::~pfodLinkedList
virtual ~pfodLinkedList()
Definition: pfodLinkedList.h:210
pfodLinkedList::root
pfodListNode< T > * root
Definition: pfodLinkedList.h:51
pfodLinkedList::insertAt
virtual bool insertAt(T *, size_t idx)
Definition: pfodLinkedList.h:417
pfodLinkedList::add
virtual bool add(T *)
Definition: pfodLinkedList.h:230
pfodLinkedList::size
virtual size_t size()
Definition: pfodLinkedList.h:219
pfodLinkedList::remove
virtual T * remove()
Definition: pfodLinkedList.h:461
pfodLinkedList::setCurrentIterator
virtual bool setCurrentIterator(T *_current)
Definition: pfodLinkedList.h:378
pfodLinkedList::getIndex
virtual size_t getIndex(T *)
Definition: pfodLinkedList.h:341
pfodLinkedList.h
pfodListNode
Definition: pfodLinkedList.h:42
pfodListNode::next
pfodListNode< T > * next
Definition: pfodLinkedList.h:44
pfodListNode::data
T * data
Definition: pfodLinkedList.h:43