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