Sometimes I get the sad impression that embedded FW engineers only understand 1 data container, the array. The array is a powerful thing and there are many good reasons to use it but it also has some serious problems. For instance, a number of TCP/IP libraries use arrays to hold a static list of sockets. When you wish to create a new socket the library takes one of the unused sockets from the array and returns a reference (a pointer or index) so the socket can be used as a parameter for the rest of the API. It turns out that sockets are somewhat heavy things (use lots of memory) so you always want to optimize the system to have the smallest number of sockets necessary. Unfortunately, you must "pick" a reasonable number of sockets early in the development process. If you run out of sockets you must go back and recompile the library to utilize the new socket count. Now there is a dependency that is not obvious, only fails at run time and links the feature count of the product with the underlying library. You will see bugs like, "when I am using the app I no longer get notification e-mails".
It turns out that this problem can be easily solved with a dynamic container. i.e. one that grows at runtime as you need it to. A brute force method would perhaps be to rely upon the heap to reallocate the array at runtime and simply give the library a pointer to an array. That will work but it inserts a heavy copy operation and the library has to be paused while the old array is migrated to the new array. I propose that you should consider a Linked List. I get a number of concerns from other engineers when I have made this suggestion so just hang tight just one moment.
Allocating the memory requires the heap and my application cannot do that.
Traversing the list is complicated and requires recursion. We cannot afford the stack space.
A linked list library is a lot of code to solve this problem when a simple array can manage it.
The linking pointers use more memory.
If you have a new concern, post it below. I will talk about these first.
Concern #1, Memory allocation
I would argue that a heap is NOT required for a linked list. It is simply the way computer science often teaches the topic.
Allocate a block of memory for the data.
place the data in the block of memory. Data is often supplied as function parameters.
insert the block into the list in the correct place.
Computer science courses often teach linked lists and sorting algorithms at the same time so this process forms a powerful association. However, what if the process worked a little differently.j
Library Code -> Define a suitable data structure for the user data. Include a pointer for the linked list.
User Code -> Create a static instance of the library data structure. Fill it with data.
User Code -> Pass a reference to the data structure to the library.
Library Code -> insert the data structure into the linked list.
If you follow this pattern, the user code can have as many sockets or timers or other widgets as it has memory for. The library will manage the list and operate on the elements. When you delete an element you are simply telling the library to forget but the memory is always owned by the user application. That fixes the data count dependency of the array.
Concern #2, Traversing the list is complex and recursive.
First, Recursion is always a choice. Just avoid it if that is a rule of your system. Every recursive algorithm can be converted to a loop.
.Second, Traversing the list is not much different than an array. The pointer data type is larger so it does take a little longer.
struct object_data *nextObject;
int findTheMassOfTheObjects(struct object_data *objectList)
thisObject = objectList;
totalMass += thisObject->mass;
thisObject = thisObject->nextObject;
printf("The mass of all the objects is %d grams\n", totalMass);
So here is a quick example. It does have the potential of running across memory if the last object in the list does NOT point at NULL. So that is a potential pitfall.
Concern #3, A linked list library is a lot of code
Yes it is. Don't do that. A generic library can be done and is a great academic exercise but most of the time the additional next pointers and a few functions to insert and remove objects are sufficient. The "library" should be a collection of code snippets that your developers can copy and paste into the code. This will provide reuse but break the dependency on a common library allowing data types to change, or modifications to be made.
Concern #4, A linked list will use more memory
It is true that the linked list adds a pointer element to the container data structure. However, this additional memory is probably much smaller than the "just in case" additional memory of unused array elements. It is probably also MUCH better than going back and recompiling an underlying library late in the program and adding a lot more memory so the last bug will not happen again.
A little history
The linked list was invented by Allen Newell, Cliff Shaw and Herbert Simon. These men were developing IPL (Information Processing Language) and decided that lists were the most suitable solution for containers for IPL. They were eventually awarded a Turing Award for making basic contributions to AI, Psychology of Human Cognition and list processing. Interestingly IPL was developed for a computer called JOHNIAC which had a grand total of 16 kbytes of RAM. Even with only 16KB IPL was very successful and linked lists were determined to be the most suitable design for that problem set. Most of our modern microcontrollers have many times that memory and we are falling back on arrays more and more often.
If you are going to insist on an array where a linked list is a better choice, you can rest easy knowing that CACHE memory works MUCH better with arrays simply because you can guarantee that all the data is in close proximity so the entire array is likely living in the cache.
P.S. - The timeout driver and the TCP library from Microchip both run on 8-bit machines with less than 4KB of RAM and they both use linked lists. Check out the code in MCC for details.