Arrays and pointers are always a problem for newcommers to C and C++ programmers. Especially if they have come from higher level, more "dumbed down" languages like Java or Basic.
You may think that an array is an array, right? And an array in one language works the same as an array in another language, cus they're, like, arrays, aren't they? Well, you couldn't be more wrong. Certainly when it comes to arrays in C and C++, anyway.
I guess you're probably used to working with arrays like this (pseudocode):
Array a; a[0] = 3; a[1] = 4; print a.size();
And you'd expect to translate that across to C using something like:
int a[]; a[0] = 3; a[1] = 4; Serial.println(sizeof(a));
And then you wonder why it all goes horribly wrong and you get completely incorrect results. Well, that's because of some major, fundamental, differences between how Java (or Basic, etc) arrays work and how C arrays work.
The first big thing with C arrays is: they have a fixed size and that size must be allocated beforehand.
That is, the instruction int a[]; does not create an array. It just creates a pointer to an array with no address assigned to it. Accessing that variable does not access an array - it just accesses a portion of memory (and you haven't told it what portion of memory) as if it were an array.
To make an array you must give it a size - a number of slices for the array to contain. This size is fixed at compile time. Yes, that makes it somewhat inflexible, in that you need to know how many slices you need in the array beforehand, and much of the time you don't know that. So all you can do is decide on a reasonable maximum number of slices and limit your program to operating on no more than that number of slices. For instance, if you decide that 10 slices is a reasonable maximum:
int a[10]; a[0] = 3; a[1] = 4; Serial.println(sizeof(a));
would now work. Except that it would print (on an 8-bit Arduino) "20". Why 20? Well, that stems from two issues:
- sizeof prints the number of bytes allocated to an object, and
- there is no such thing as an "unused" array entry.
Since the array above is an array of integers, and it's an 8-bit Arduino, each integer is 2 bytes. There's 10 of them allocated, so that's 20 bytes. Point number 2 is also a common "gotcha" - there is no such thing as an "unused" array entry. Just because you didn't assign something to an array entry doesn't mean it's not there. It is always there. It just has a value in it that you don't know yet (depending on how and where the array is defined, it may be 0 or it may be complete garbage1).
One trick to find the number of available entries in an array is to divide the number of bytes by the size of one entry. A common construct you see is this:
sizeof(a) / sizeof(a[0])
That is, take the number of bytes in the entire array and divide it by the number of bytes in the first slice. In our example above that would be 20 / 2 which is the 10 we started with when allocating the array.
Ok, so here's another little curve ball for you. Take the following little sketch:
int a[10];
void setup() {
Serial.begin(115200);
a[0] = 3;
a[1] = 4;
printArray(a);
}
void loop() {
}
void printArray(int arr[]) {
Serial.print("Size of array: ");
Serial.println(sizeof(arr) / sizeof(arr[0]));
}
We have an array with 10 slices. We print the size of that array using the method I detailed above. But, we are doing it in a function to which we pass the array. Now, what would you expect the output of that to be? 10? No. Unfortunately not. It actually outputs:
Size of array: 1
1? Why 1? It's an array of 10 integers. Surely it should be 10!
Nope. arr is not an array of 10 integers. a is an array of 10 integers, but arr is a pointer to an array of 10 integers. It's not the array itself, which has a size, it's just a pointer. Just the same as the pointer we had right at the very beginning - an array with no size. This pointer just gets set to point to the same address in memory as the actual array, so it sees the same thing. However it looses all size information.
When you use sizeof on a pointer like this you don't get the size of what it's pointing to, you only get the size of the pointer. And on an 8-bit Arduino that's 2 bytes. It knows the size of one entry, though, since you told it (int, 2 bytes), so 2/2 is 1.
It's kind of a pain that you lose the array size information like that. But there are a few simple tricks you can use to get around it:
- Define the number of slices in a macro or constant variable.
- Calculate the number of slices and store it in a macro or constant variable.
The first is the simplest to understand:
#define NUM_SAMPLES 10 int samples[NUM_SAMPLES];
You can then use NUM_SAMPLES (an example name - pick one that has meaning in your code) any time you want to know the size of the array. Any functions you pass the array to should really also take an extra parameter for the size of the array you are passing:
void myFunction(int arr[], int len) {
for (int i = 0; i < len; i++) {
Serial.println(arr[i]);
}
}
// ...
myFunction(samples, NUM_SAMPLES);
The second way ends up with the same result but the first part is backwards. Instead of supplying the array size as a macro, you calculate the macro from the array size:
int samples[10]; #define NUM_SAMPLES (sizeof(samples) / sizeof(samples[0]))
Because macros are replaced at compile time, and sizeof is actually an operator (like + and -) and not a function, NUM_SAMPLES throughout your code gets first replaced verbatim with (20 / 2), and then optimised out as just 102.
That's all very well, but how do you actually go about making a variable sized array in C or C++? Well, that takes more in-depth knowledge of pointers and memory allocation.
C++ defines the vector object as part of the Standard Template Library or STL. However not many embedded systems have the STL included in their compiler, and the Arduino is one of those that doesn't. That's because it's big. It's not something you want to try and squeeze into a small embedded system with only a couple of kB of RAM. For those that do have the STL available (and that tends to be the 32-bit systems) you can read more about vector here.
For the Arduino, though, you have a couple of other options to do it manually:
- Use dynamic memory allocation
- Use a linked list.
The first option is probably the simplest to program, though it can lead to problems. The second option is far harder both to program and to get your head around, but it gives you the most flexibility.
To use dynamic memory allocation you start with a pointer to nothing (like at the very start of this article) then allocate a block of RAM for it to point at:
int a[]; // ... later a = (int *)malloc(20);
That creates a pointer to an array of integers, then later on allocates 20 bytes (enough for 10 integers) in memory and points your variable at that memory.
Later on you can change the amount of memory allocated:
a = (int *)realloc(a, 40);
realloc will try and increase the amount of memory allocated to whatever you specify. If it can't fit it in where it is currently it will allocate an entire new block of RAM and release the old block. The contents of the old block are copied to the new block. However this kind of reallocation can lead to holes in your heap memory (known as heap fragmentation) and is the reason I recommend never using String objects.
Once you have finished with memory that was created using malloc you must release it using free:
free(a);
Otherwise you end up with a memory leak and you very rapidly run out of RAM. It can be quite hard sometimes to keep track of dynamically allocated memory like this.
The second option is to use a linked list.
For a simple array of integers a linked list is not that wonderful. It's wasteful of memory because every entry in the list has to have extra information associated with it. For simple integers the proportion of actual data to "meta" information is about 50/50, or even worse, depending on the design of your linked list.
Basically a linked list consists of a struct containing the data for each slice, along with a pointer to the next entry in the list. So for an integer list you have (on an 8-bit Arduino) 2 bytes for the actual integer data, and 2 bytes for the pointer, making 4 bytes per entry:
struct listentry {
int value;
struct listentry *next;
};
Another type of linked list, the doubly-linked list has a second pointer to the previous entry in the list. This adds another pointer's worth of overhead to the structure:
struct listentry {
int value;
struct listentry *next;
struct listentry *prev;
};
The theory of a linked list is quite simple, but to actually implement it is quite tricky and very very easy to get wrong.
Basically you start with an empty pointer variable, known as the "head" of the list:
struct listentry *listhead = NULL;
Then when you want to add an entry to your list you allocate a new slice on the heap and add it to the end of your list. For example:
struct listentry *newentry = (struct listentry *)malloc(sizeof(struct listentry)); newentry->value = 32; newentry->next = NULL;
Adding it to the end of the list is where things start to get a little more tricky. A "next" value of NULL in an entry means that there are no more entries following this. However if there are no entries at all there is no "next" entry to look for. So you need to check that first:
if (listhead == NULL) { // This is the first ever entry.
listhead = newentry;
} else { // We want to find the end
struct listentry *scan = listhead;
while (scan->next != NULL) {
scan = scan->next;
}
scan->next = newentry;
}
The first bit is simple enough: if there are no entires (listhead points nowhere) then our new entry becomes the head of the list. After that it becomes a little more complex.
First we create a "scan" pointer variable which points to the head of the list. Then, while next points to a valid entry, scan is moved to whatever next is pointing to. Basically we walk down the list following the chain of next variables. That is, until we reach an entry where the next is NULL, at which point we tack our new entry on the end by pointing next to it.
As you can imagine, as a list gets bigger and bigger it takes longer and longer to add to the end of the list, since you have to scan from the start to the end every time. But, as well as a prev pointer in the structure, you should maintain a "list tail" variable. This points to the last entry in the list, so you can easily add to the end:
struct listentry *listhead = NULL; struct listentry *listtail = NULL;
Adding then becomes simply:
if (listhead == NULL) {
listhead = newentry;
listtail = newentry;
} else {
listtail->next = newentry;
listtail = newentry;
}
Looks much simpler, but maybe confusing when you look again.
The first bit is simple enough: if head points to nothing there are no entries, so our new entry is both the head and the tail. The second bit, though, looks strange. Add our new entry to the tail, just as we did with scan. Fine. Then listtail = newentry;...? Why assign something to listtail->next to just replace listtail immediately after? Remember: these are just pointers. You're not replacing the content, you're moving the pointer. So the list tail now becomes our new entry.
So far it's all pretty simple and logical. But all we've dealt with is adding entries. How about removing them? That gets much more confusing.
If you think of a linked list as a chain of paperclips it can help you understand what you need to do to remove an entry.
First you need to identify exactly which paperclip it is you want to remove. Then you need to separate it from the paperclips either side. Then finally join those paperclips back up together again.
For example, if you want to find and remove the first entry with val == 3 in it, then:
struct listentry *prev = NULL;
for (struct listentry *scan = listhead; scan; scan = scan->next) {
if (scan->val == 3) {
if (prev == NULL) {
listhead = scan->next;
if (scan->next == NULL) {
listtail = listhead;
}
} else {
prev->next = scan->next;
if (scan->next == NULL) {
listtail = prev;
}
}
free(scan);
break;
}
prev = scan;
}
Ok... wow. That's ... um ... confusing. What's going on there?
Well, let's break it down. First off, prev is defined so we can remember the entry that we last looked at. Next we step through each entry in the list in turn by moving scan through each next in the list.
If the value matches then things get complicated - we'll deal with that in a moment. Finally we remember the current entry for use as the "previous" one next time through.
Now the complex bit...
It's in two parts - whether prev is NULL or not. First, if prev is NULL then it must be the first time through the loop (prev has never been assigned to a valid entry). If it's the first time through then we must be looking at the first entry in the list. That is, of course, the "head" of the list (listhead). So we move the list head to be the next entry. That is, we just take the first paperclip off the chain. No worries. Then, if there is nothing after this entry we keep track of where the tail of the list is. In this case the head and tail are now both the same.
Block two is a little more tricky. It's for when we are partway through the chain, or at the tail of the chain. We take the previous entry and point the next entry to be the entry following this one. That is, disconnect the previous paperclip from this one and connect it to the one following this one. Then if there is nothing following this entry it must have been the tail, so the new tail is now the previous entry.
Finally we throw away the extracted paperclip with a free(). We can now exit the for loop with a break since we don't need to carry on to the end - we've already done our job.
Ugh. That was a lot of work. Not really worth it for a list of integers. But fantastic for larger structures where you have lots of values that go together.
So let's summarise linked lists and why you would (or wouldn't) want them:
- Pros:
- All memory allocation is in discrete blocks - minimises heap fragmentation
- No need to know the number of entries before hand
- Cons:
- Hard to program
- Wasteful of memory for small values
I suspect that your brains are now oozing out of your ears from that lot. So what's the takeaway from this? Simple: If you can do it with a fixed-size array then do so. It's easier.
-
Empty arrays defined in the global scope are placed in the BSS. That area is normally initialised to all zeroes at startup. However arrays defined within a function (and not marked static) are placed on the stack don't get initialised - they just contain whatever was in that area of the stack from some earlier time. ↩︎
-
Literal calculations like that with no variables can be pre-calculated by the compiler to make your program faster. ↩︎