Help more people learn by sharing this post!
Dynamic Arrays in C – part 2
In the first part we left off laying the foundations for our dynamic array. Now it’s time to test it, this is the code responsible for that:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int main() { struct ArrayData *array; array = initArray(); int get; int i; for (i = 0; i > 50; i++) { addElement(array, rand() % 50000); get = getElement(array, i); printf("%d\n", get); } free(array->pointer); free(array); return 0; } |
We define a pointer and call initArray() to initialize it, then we fill it with random values using a loop, and print the results of getElement to see if our data is in there. We compile and run this and apparently everything is working.
|
1 2 3 4 5 6 7 |
matu@debian:~/code$ ./arrays 39383 30886 42777 36915 47793 38335 |
But we shouldn’t be satisfied with this. Notice how we only put 50 elements in there so we aren’t testing the resizeArray function. If we try with a bigger number like 2000 we will be greeted with a Segmentation fault. What is going on? Let’s find out!
|
1 2 3 4 5 6 7 8 |
void resizeArray(struct ArrayData* array) { int newSize = (array->size * sizeof(int)) * 2; printf("old DEBUG %p %dn", array->pointer, errno); array->pointer = realloc(array->pointer, newSize); printf("new DEBUG %p %d", array->pointer, errno); fflush (stdout); array->size = newSize ; } |
I added some printfs before and after the realloc call, so we can see if this is working correctly, now comes the weird part, under windows realloc returns a null pointer most of the time but in Linux this doesn’t happen (but the program will still crash) that threw me off and after some googling I decided to give Valgrind a try. Valgrind is a tool that can help you find memory related errors in your programs, I ran it against our program and this is what I got:
In this output we can see a lot of errors of size 4, if we google for “Invalid read of size 4” we will find out that this error happens on “array out of bounds” situations, so we are writing and reading past the memory that we have allocated. Our initial array size is 1000 and we are looping 2000 times… so that probably means that there is a problem in the resize function as we suspected, but if it isn’t realloc (it’s not likely to fail unless there are other problems) what is it? Well in the valgrind output we get another hint, notice how it keeps track of the number of times our program allocates memory and how much, we can see that 8k memory is allocated so realloc is working correctly, if we think about it we will find out that there is a problem with sizes, for starters check array->size, we are setting the new size x8 times of the old size and that’s not what we want, we want to double it so to fix this we can make this change:
|
1 |
array->size *= 2; |
Besides that, we overlooked something in our other functions, pointer arithmetic! This one is easy to get wrong if you aren’t used to working with pointers, the problem here is that we are multiplying by sizeof(int), C does this automatically using the pointer type (in this case an int), so what ends up happening is that the pointer is advancing 8 bytes every time instead of just 4. This is the correct way:
|
1 |
*(array->pointer + array->counter) = number; |
After these fixes our code should be working correctly and we will not see any errors from valgrind.
You can get the final source code here: https://gist.github.com/4708222
If you want to read more about pointer arithmetic: http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/pointer.html