Dynamic array help

Hello all, I am creating a program that uses a dynamic array to store students. My code compiles but i keep getting a runtime error which prints out a bunch of stuff, but the main thing being:

*** glibc detected *** ./a.out: realloc(): invalid pointer: 0xb7fc2e00 ***

so apparently there is a problem with my realloc but I just can't seem to figure out what it is. As far as I can see it should work. Any help with this would be greatly appreciated.

Here is my main which is pointless right now. Basically it's just set up to test whether the add function works.

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include "student.h"

int main()
{
       
        student *array;
        student std1;
        int number_of_elements = 0;
        int array_size = 0;
       
        std1.lastname = "smith";
        std1.firstname = "bob";
        std1.score = 50;

        add(array, std1, &number_of_elements, &array_size);
       
        free(array);
        return 0;
}

---

And my header file

Code:

---

#include <stdlib.h>

#ifndef STUDENT_C
#define STUDENT_C
typedef struct student
{
        char *lastname;
        char *firstname;
        int score;
} student;

void add(student*, student, int*, int*);

#endif

---

and finally the important one. The student file which contains the dynamic memory function. Again the error seems to be on the realloc line.

Code:

---

#include <stdlib.h>
#include <stdio.h>
#include "student.h"

void add(student *array, student item, int *number_of_elements, int *array_size)
{
        if (*number_of_elements == *array_size) /*resize array*/
        {
                if (*array_size == 0)
                {
                        *array_size = 1;
                }
                else
                {
                        *array_size = *array_size * 2;
                }
                array = (student*)realloc(array, ((*array_size) * sizeof(student)));
               
                if (array == 0)
                {
                        printf("no space for memory");
                        exit(1);
                }
        }
        array[*number_of_elements] = item;
        (*number_of_elements)++;
}

---

Maybe the problem is the extra "student" in the first line of the definition:

Code:

---

typedef struct student
{
        char *lastname;
        char *firstname;
        int score;
} student;

---

thanks for the reply. hmmm.. removed that and it doesn't seem to make a difference

I just realized -- you're using realloc without ever having used malloc, so the pointer that you're giving to realloc doesn't point to any memory -- ergo invalid.

try this , define student *array=NULL; array must be NULL to allocate memory with realloc

Quote:

---

Originally Posted by xmariux

try this , define student *array=NULL; array must be NULL to allocate memory with realloc

---

that worked! Thanks a million, I can't believe it was something so trivial.

Try calling the add() function more than once in your main() function. You have a problem in that the array parameter is just a pointer, so this merely changes the local copy of the pointer:

Code:

---

array = (student*)realloc(array, ((*array_size) * sizeof(student)));

---

You should declare array to be a pointer to a student*. (Maybe you should also rename it to students.)

Quote:

---

Originally Posted by laserlight

Try calling the add() function more than once in your main() function. You have a problem in that the array parameter is just a pointer, so this merely changes the local copy of the pointer:

Code:

---

array = (student*)realloc(array, ((*array_size) * sizeof(student)));

---

You should declare array to be a pointer to a student*. (Maybe you should also rename it to students.)

---

sorry but I don't think I'm quite following, you mean that array should be a double pointer??

Quote:

---

Originally Posted by Perogy

sorry but I don't think I'm quite following, you mean that array should be a double pointer??

---

Yes, a student**. But not in main(), only in the add() function, so when you call the function from main the first argument will be &array.

ahhh ok I see what you mean, just so we can change the original it needs to be passed in as an address. I did that and now it seems to work perfectly for the first time I use add but if I use it again it segfaults. This is my new Student.

Code:

---

#include <stdlib.h>
#include <stdio.h>
#include "student.h"

void add(student **array, student item, int *number_of_elements, int *array_size)
{
        if (*number_of_elements == *array_size) /*resize array*/
        {
                if (*array_size == 0)
                {
                        *array_size = 1;
                }
                else
                {
                        *array_size = *array_size * 2;
                }
                *array = (student*)realloc(*array, ((*array_size) * sizeof(student)));
               
                if (*array == 0)
                {
                        printf("no space for memory");
                        exit(1);
                }
        }
        *array[*number_of_elements] = item;
        (*number_of_elements)++;
}

---

It's good practice to not assume a pointer you're getting actually points to something. Check to make sure your pointers aren't NULL. Also, 'item' isn't a pointer, so once your function ends, the copy of that structure that you've just passed to the function no longer exists.


Quzah.

Can you post the updated code.

Quote:

---

Originally Posted by Perogy

.... but if I use it again it segfaults...

---

It shouldn't -- unless you have an error in main. I suspect that in the second call to add() you forgot to make the first argument a pointer (&array, ...)

Quote:

---

Originally Posted by quzah

Also, 'item' isn't a pointer, so once your function ends, the copy of that structure that you've just passed to the function no longer exists.
Quzah.

---

Not true. The array is an array of structures, not an array of pointers, so when the new 'item' is assigned to the array, its contents are copied into the memory allocated to the array. Even if 'item' itself is dynamically allocated, copied into the array and then 'item' is freed, the data in the array would not be lost.

Quote:

---

Originally Posted by quzah

It's good practice to not assume a pointer you're getting actually points to something. Check to make sure your pointers aren't NULL. Also, 'item' isn't a pointer, so once your function ends, the copy of that structure that you've just passed to the function no longer exists.
Quzah.

---

I don't see why item would have to be a pointer though, it just gets stored in the array and that's that. Let me know if I'm wrong.

I'll post the entire updated code shortly.

Quote:

---

Originally Posted by Perogy

I don't see why item would have to be a pointer though, it just gets stored in the array and that's that. Let me know if I'm wrong.

---

It doesn't. Did you read post #13?

Ok here's what I've got now, I have made some minor revisions to the structure and names of stuff so it might be a little hard to follow from the previous example, but nothing too major.

The main.c file

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "student.h"

#define BUFSIZE 256

int main()
{
        record *array = 0;
        record std;
        int number_of_elements = 0;
        int array_size = 0;
       
        char line[BUFSIZE];
        char first[21];
        char last[21];
        int score;
       
        /*get the user input line while not EOF*/
        while (fgets(line, BUFSIZE, stdin) != 0)
        {
                sscanf(line, "%s%s%d", last, first, &score);
                strcpy(std.name.lastname, last);
                strcpy(std.name.firstname, first);
                std.score = score;
                add(&array, &std, &number_of_elements, &array_size);
        }
        free(array);
        return 0;
}

---

The student.h header file (note I made a couple of changes to the structures)

Code:

---

#include <stdlib.h>

#ifndef STUDENT_C
#define STUDENT_C

#define NAMESIZE 21
typedef struct name
{
        char lastname[NAMESIZE];
        char firstname[NAMESIZE];
} name;

typedef struct record
{
        name name;
        int score;
} record;

void add(record**, record*, int*, int*);

#endif

---

and finally the student.c file which includes the dynamic array

Code:

---

#include <stdlib.h>
#include <stdio.h>
#include "student.h"

void add(record **array, record *item, int *number_of_elements, int *array_size)
{
        if (*number_of_elements == *array_size) /*resize array*/
        {
                if (*array_size == 0)
                {
                        *array_size = 1;
                }
                else
                {
                        *array_size = *array_size * 2;
                }
                *array = (record*)realloc(*array, ((*array_size) * sizeof(record)));
               
                if (*array == 0)
                {
                        printf("no space for memory");
                        exit(1);
                }
        }
        *array[*number_of_elements] = *item;
        (*number_of_elements)++;
}

---

To recap, it compiles and runs fine, the dynamic array works fine for the first string I enter, but it segfaults when I enter the second one :S this random behavior kind of leads me to believe it has to do with something not being initalized or something along those lines.

I'm thinking maybe it is something to do with the main, but whatever it is I've been fooling around with it for hours and can't seem to figure it out.

TIA

As I said last night, it wasn't necessary to make 'item' a pointer, but it's just as well that you did. It's more efficient to send the function a pointer to a struct rather than making an extra copy of the entire struct -- this would be important if you were dealing with a large structure.

Anyway, your segfault is due to one little detail in student.c. Access the array like this

Code:

---

    (*array)[*number_of_elements] = *item;

---

or

Code:

---

    *(*array + *number_of_elements) = *item;

---

By the way, I don't like the idea of reusing a typename to name a field in the structure, as in

Code:

---

name name;

---

although apparently the compiler doesn't mind. I just think that's looking for trouble/confusion.

Also, do you really want the arraysize to double every time it runs out of space? That may be OK going from 1 to 2 and 2 to 4, but do you really want to jump from 16 to 32, and so on?

Quote:

---

Originally Posted by R.Stiltskin

Also, do you really want the arraysize to double every time it runs out of space? That may be OK going from 1 to 2 and 2 to 4, but do you really want to jump from 16 to 32, and so on?

---

Why not - certainly it would NOT be a good idea to grow it by a small constant value. Imagine if you have to grow it to 16000 or so, by steps of (say) 8? On average you'd have copied half the array 2000 times, instead of 11 times with a doubling scheme. [In fact, this very problem existed in a driver a former colleague of mine workd on, where it grew an array by 4KB every time it ran out of space - but in this particular "error report", the software product needed 16MB of space. So it would copy the data 4000 times, averaging 8MB per copy. That takes a while even on the latest greates processors! By doubling instead, it went from 0.01 fps to 5 fps or some such - it still wasn't a fantastic frame-rate, but it was good enough that the application wasn't deemed "broken" any more].

It obviously does depend on how large you expect the array to grow, and thus how many times you need to copy it. But growing by a factor other than 1 element more every time is certainly not a bad idea.

--
Mats

Quote:

---

Originally Posted by matsp

It obviously does depend on how large you expect the array to grow, and thus how many times you need to copy it. But growing by a factor other than 1 element more every time is certainly not a bad idea.

--
Mats

---

I certainly agree with that. I had in mind something more in line with the nature of the application.

As for your example, granted, doubling each time is an easy way out of estimating what's actually needed, but I'd be pretty annoyed if the next error report was only 4K and cost me 16MB to store it.

But doubling gives a maximum unused overhead of (number_of_elements / 2)-1 times the size of the element. And that's only if the number of elements is 2^n+1. For anything else it is less. Since 2^n grows exponentially, it also is exponentially less likely that you will hit that special case [unless it so happens that your data ALWAYS is powers of 2 + 1 of course].

But it certainly is a trade-off between "how many times do we copy this" and "how much space is wasted".

--
Mats

Quote:

---

Originally Posted by R.Stiltskin

I certainly agree with that. I had in mind something more in line with the nature of the application.

---

What do you propose as an alternative, given that we have no idea if Perogy needs to store the data of students who took a class test or the data of students who took a national examination?

Quote:

---

Originally Posted by R.Stiltskin

As for your example, granted, doubling each time is an easy way out of estimating what's actually needed, but I'd be pretty annoyed if the next error report was only 4K and cost me 16MB to store it.

---

I do not see how a factor of 2 can possibly lead to 16 MB being used to store 4 KB of data. More likely it would be 8 KB, with a temporary total of 12 KB if realloc() needs to copy to a separate block in memory. Of course, one can choose a smaller factor like 1.5 and still get amortized constant time performance.

Quote:

---

Originally Posted by laserlight

What do you propose as an alternative, given that we have no idea if Perogy needs to store the data of students who took a class test or the data of students who took a national examination?

---

...which is exactly why I didn't propose an alternative. Presumably Perogy has some idea of his needs.

Quote:

---

Originally Posted by laserlight

I do not see how a factor of 2 can possibly lead to 16 MB being used to store 4 KB of data. More likely it would be 8 KB, with a temporary total of 12 KB if realloc() needs to copy to a separate block in memory. Of course, one can choose a smaller factor like 1.5 and still get amortized constant time performance.

---

Just following the example given by matsp. If the previous "unusual" 16MB report filled the array, a subsequent 4K report would result in doubling the array size.


(Why are we arguing about this?)

Quote:

---

Originally Posted by R.Stiltskin

(Why are we arguing about this?)

---

Because whilst you are arguing it shouldn't be done this way, I and Laserlight think that doubling is a fine thing to do.

Yes, if you need 16MB + 4K, then you get 32MB. Compared to the OVERALL needs of a program that uses 16MB of vertices, I'm sure it's peanuts, but I guess there's always someone who will complain about it.

--
Mats

Quote:

---

Originally Posted by R.Stiltskin

As I said last night, it wasn't necessary to make 'item' a pointer, but it's just as well that you did. It's more efficient to send the function a pointer to a struct rather than making an extra copy of the entire struct -- this would be important if you were dealing with a large structure.

Anyway, your segfault is due to one little detail in student.c. Access the array like this

Code:

---

    (*array)[*number_of_elements] = *item;

---

or

Code:

---

    *(*array + *number_of_elements) = *item;

---

By the way, I don't like the idea of reusing a typename to name a field in the structure, as in

Code:

---

name name;

---

although apparently the compiler doesn't mind. I just think that's looking for trouble/confusion.

Also, do you really want the arraysize to double every time it runs out of space? That may be OK going from 1 to 2 and 2 to 4, but do you really want to jump from 16 to 32, and so on?

---

ahhh that was it, thank you very much. Those precedence errors can really catch a C newbie like me off guard.

And just for clarification this is a school assignment which states we have to double the array, so that is why i chose to do it that way :-)

Quote:

---

Originally Posted by R.Stiltskin

...which is exactly why I didn't propose an alternative. Presumably Perogy has some idea of his needs.

---

That's a cop out :p
If we consider asymptotic running time, the choice is between allocating just the right amount of space, or increasing the space by some factor greater than unity. Increasing the space by a constant amount risks quadratic time performance, though realloc() may expand the block in-place where possible, so it would not necessarily be so bad. As such, having some idea of your needs means knowing exactly the amount of space needed, or at least knowing the upper bound on space (and thus also wasting space if the upper bound is not reached).

Quote:

---

Originally Posted by Perogy

And just for clarification this is a school assignment which states we have to double the array, so that is why i chose to do it that way :-)

---

Sure, it is good to follow your assignment requirements, but also try to understand why it is done that way.

Quote:

---

Originally Posted by matsp

Because whilst you are arguing it shouldn't be done this way, I and Laserlight think that doubling is a fine thing to do.

Yes, if you need 16MB + 4K, then you get 32MB. Compared to the OVERALL needs of a program that uses 16MB of vertices, I'm sure it's peanuts, but I guess there's always someone who will complain about it.

--
Mats

---

I would like my money to grow exponentially (it doesn't), but I tend to think that I should avoid having my resource requirements grow exponentially absent some compelling reason. Call me stingy. :cool:


Edit: ...although I suppose it's not so bad if we consume only twice as much as we need in the worst case...

Quote:

---

Originally Posted by R.Stiltskin

I tend to think that I should avoid having my resource requirements grow exponentially absent some compelling reason

---

Memory is one resource, and processing time is another resource. Being able to allocate precisely the amount of space needed is indeed ideal. But if you do not know the size of the input before hand, then to achieve the insertion of an element at the back in amortized constant time, you have to increase space consumption by a factor. This space-time trade-off is often worth it, and of course one could resize to exact fit when done if necessary.

Yes, that is certainly valid. Thanks laserlight and mats for pointing that out.