5

As the title says (and suggests), I'm new to C and I'm trying to return an arbitrary sized array of structs from a function. I chose to use malloc, as someone on the internet, whose cleverer than me, pointed out that unless I allocate to the heap, the array will be destroyed when points_on_circle finishes executing, and a useless pointer will be returned.

The code I'm presenting used to work, but now I'm calling the function more and more in my code, I'm getting a runtime error ./main: free(): invalid next size (normal): 0x0a00e380. I'm guessing this is down to my hacked-together implementation of arrays/pointers.

I'm not calling free as of yet, as many of the arrays I'm building will need to persist throughout the life of the program (I will be adding free() calls to the remainder!).

xy* points_on_circle(int amount, float radius)
{
  xy* array = malloc(sizeof(xy) * amount);

  float space = (PI * 2) / amount;

  while (amount-- >= 0) {
    float theta = space * amount;

    array[amount].x = sin(theta) * radius;
    array[amount].y = cos(theta) * radius;
  }

  return array;
}

My ground-breaking xy struct is defined as follows:

typedef struct { float x; float y; } xy;

And an example of how I'm calling the function is as follows:

xy * outer_points = points_on_circle(360, 5.0);
for(;i<360;i++) {
    //outer_points[i].x
    //outer_points[i].y
}

A pointer in the right direction would be appreciated.

Improve this question
3
  • One thing you could try is using valgrind to find out where the memory problem is located: valgrind.org Commented May 19, 2011 at 15:01
  • ha ha a 'pointer' in the right direction!! Commented May 19, 2011 at 15:06
  • As safe as I like to be when coding (see my answer), There's no need to un-allocated in the same function you allocate. Either way, you have to keep track. Either way, you have to know what you're doing, It just violates the DRY principle to malloc outside the function, and adds opportunities for other errors. After all, the malloc function itself does this very thing! Ok it has to (better examples anybody, it's been 12 years for me since I wrote C). It is just too common for a function to allocate its memory and expect it to be freed. More complex solutions you'll find it is required. Commented May 19, 2011 at 15:38

7 Answers 7

Reset to default
7

Allocating memory in one function and freeing it in another is fraught with peril.

I would allocate the memory and pass it (the memory buffer) to the function with a parameter indicating how many structures are allowed to be written to the buffer.

I've seen APIs where there are two functions, one to get the memory required and then another to actually get the data after the memory has been allocated.

[Edit] Found an example: http://msdn.microsoft.com/en-us/library/ms647005%28VS.85%29.aspx

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for the tip (and the link). My comfort zone of JavaScript seems a long way away now I've got to manage my own memory!
6

I would say that this program design is fundamentally flawed. First of all, logically a function which is doing calculations has nothing to do with memory allocation, those are two different things. Second, unless the function that allocates memory and the one that frees it belong to the same program module, the design is bad and you will likely get memory leaks. Instead, leave allocation to the caller.

The code also contains various dangerous practice. Avoid using -- and ++ operators as part of complex expressions, it is a very common cause for bugs. Your code looks as if it has a fatal bug and is writing out of bounds on the array, just because you are mixing -- with other operators. There is never any reason to do so in the C language, so don't do it.

Another dangerous practice is the reliance on C's implicit type conversions from ints to float (balancing, aka "the usual arithmetic conversions"). What is "PI" in this code? Is it an int, float or double? The outcome of the code will vary depending on this.

Here is what I propose instead (not tested):

void get_points_on_circle (xy* buffer, size_t items, float radius)
{
  float space = (PI * 2.0f) / items;
  float theta;
  signed int i;

  for(i=items-1; i>=0; i--)
  {
    theta = space * i;

    buffer[i].x = sin(theta) * radius;
    buffer[i].y = cos(theta) * radius;
  }
}
Improve this answer

3 Comments

20 years ago I used to write things like do { .. } while(--n); because the compilers back then were simpler and you got better code that way (sometimes, much better). Modern compilers are all very happy with for(i=0;i<n;i++){} ; any time you have a loop which can be written that way you should; it's clearer, and you will get as good code from it. For decreasing i, write the loop as above; but this example works with increasing i just as well; no need to make it decreasing. Tricky loop conditions are a major source of bugs.
@greggo I suspect that the reason why this is a down-counting loop is a mathematical one, rather than "optimize for compare vs zero and branch". See my comment to FastAl's answer: "I assumed that the OP had chosen to count downwards because they wanted to print the items in a certain order? Ie clockwise versus counter-clockwise around the circle".
@Lundin ok - but in all the examples here it's being calculated from n-1 down to 0, and stored in the array from [n-1] down to [0]. So, changing the order of traversal won't change the end result.
6

EDIT: You are returning the array correctly, but ...

Consider you're making an array with 1 element

xy *outer_points = points_on_circle(1, 5.0);

What happens inside the function?
Let's check ...

  xy* array = malloc(sizeof(xy) * amount);

allocate space for 1 element. OK!

  while (amount-- >= 0) {

1 is greater or equal to 0 so the loop executes (and amount gets decreased)
after setting array[0] you return to the top of the loop

  while (amount-- >= 0) {

0 is greater or equal to 0 so the loop executes (and amount gets decreased)
You're now trying to set array[-1], which is invalid because the index refers to an area outside of the array.

Improve this answer

2 Comments

Nice explanation. Way to walk through the code and show what's happening. :)
Thanks for your help and the useful walkthrough. I had my mind so focussed on all the malloc I missed that out!
3

I think this:

while (amount-- >= 0 ) {

should be:

while ( --amount >= 0 ) {

Consider the case where amount is zero initially.

Improve this answer

3 Comments

Yes. to add some detail, you are post-decrementing amount. It is compared to zero, and then decremented, so the last iteration of the loop has index -1. That overwrites the header malloc uses to keep track of allocated blocks leading to the error when you free the block.
That would definitely be right, you're trashing the byte after the allocated memory. Question after this is, you will have to change the code using the function to be zero-based (it wouldn't have been working if it were). That is the thing that Neil's answer does: changes the range in this example from 1-360 to 0-359.
Thanks for your help and the useful walkthrough. I had my mind so focussed on all the malloc I missed that out!
2

You're doing the right thing as far as I'm concerned, provided of course your callers are free'ing the results.

Some people prefer to have the memory allocation and freeing responsibility in the same place (for symmetry), i.e. outside your function. In this case you would pass a pre-allocated xy* as a parameter and return the size of the buffer if the pointer was null:

int requiredSpace = points_on_circle(10, 10, NULL);
xy* myArray = (xy*)malloc(requiredSpace);
points_on_circle(10, 10, myArray);
free(myArray);
Improve this answer

1 Comment

This doesn't seem like such a hot idea, because now you have a function that has vastly different functionality depending on the value of the parameters. So, it's not quite as intuitive. My suggestion would be to make the 'get the size' aspect a separate function.
1

You are iterating over one element to much.

You should use the goes down to zero operator instead:

while ( amount --> 0) {
    ...
}

Allocating memory in one function and freeing it in the other is like giving a gun to a four year old. You shoudn't do that.

Improve this answer

1 Comment

Thanks for your answer (and the link; I assumed that was one crazy operator before I read it!). Thanks for the tip on memory as well.
1

While your decision to count down amount and use while instead of using a temp value saved a few memory cycles, it is more conceptually confusing. Especially in a case where the maths are taking all the time here, you only save fractions.

But that is not the reason why you should waste minor amounts of time. This question is the reason: you've wasted hours! This applies to even the most experienced and smartest programmers. The mistakes are just more complicated and beyond the scope of a stackoverflow answer! In other words, the Peter Principle applies to coding too.

Don't make the mistake as you gain experience that you can get away with taking these kinds of risks to save a cycle or two. That is why McConnell in Code Complete lists Humility as a positive programmer attribute.

Here's the solution you probably thought of to start with:

xy* points_on_circle(int amount, float radius)
{
  xy* array = malloc(sizeof(xy) * amount);
 
  float space = (PI * 2) / amount;

  int index;

  for (index=0;index<amount;index++) {
    float theta = space * index;
 
    array[index].x = sin(theta) * radius;
    array[index].y = cos(theta) * radius;
  }
 
  return array;
}

If you need speed, a tiny thing you can do is put theta outside the loop set to 0 and add 'space' each time since + is bound to be cheaper than * in floating point.

speed it up 10x or more?

If you need serious speed, this tip from answers.com will give you an improvement of 10x if you do it right:

By Pythagoream's theorem, x2 + y2 is radius2. It is then simple to solve for x or y, given the other along with radius. You also do not need to compute for the whole circle - you can compute for one quadrant, and generate the other three quadrants by symmetry. You generation loop would, for example, simply iterate from origin to radius as x by delta x, generating y, and reflecting that in the other three quadrants. You can also compute for one half of a quadrant, and use both symmetry and reflection to generate the other seven half quadrants.

When I was 12 I thought I was hot stuff drawing a circle using sin and cos in graphics 8 on my atari 800. My cousin Marty (when as of late worked form Microsoft robotics) erased my program and implemented the above solution, using only addition in the loop if I remember right, and draw the same circle in 4 seconds instead of a minute! Had I not been baptized I would have bowed down in worship. Too bad I don't have the code handy but I'd bet a little googling would bring it up. Anybody?

Improve this answer

3 Comments

I assumed that the OP had chosen to count downwards because they wanted to print the items in a certain order? Ie clockwise versus counter-clockwise around the circle.
@drhirsch - looks familiar. I would have been so much better of a programmer if we'd have had wikipedia in the 80s!
Wise words :P. Good advise! Thanks for the detailed answer. Shame I've got so many to choose from to select the "accepted" for :(.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.