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;
45 };
46 
47 template<typename T>
49 
50  protected:
52  pfodListNode<T> *current; // for list tranversals
53  size_t count; // the number of items in the list
54 
55  public:
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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_ */
pfodListNode< T > * current
virtual void clear()
virtual T * remove(size_t idx)
virtual T * getFirst()
virtual T * remove(T *)
virtual bool append(T *_t)
virtual T * get(size_t idx)
virtual T * getNext()
virtual T * getCurrentIterator()
virtual ~pfodLinkedList()
pfodListNode< T > * root
virtual bool insertAt(T *, size_t idx)
virtual bool add(T *)
virtual size_t size()
virtual T * remove()
virtual bool setCurrentIterator(T *_current)
virtual size_t getIndex(T *)
pfodListNode< T > * next