Thread: Dynamic array help

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?

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.

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.

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?)

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 :-)

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