1

Before I start I should say this is not related to a direct problem, but out of curiosity and my inability to find something relating to exactly what I'm after. I'm currently teaching myself C, I have experience with several other languages so it's nothing new other than exactly how to perform certain things.

I wanted to do a challenge in C, like build a Stack that would grow as necessary by a certain amount and I chose to use a struct for this:

#define INITIAL_STACK_SIZE 10

typedef struct Stack {
  int max_size;
  int cur_top;
  int *elements;
} Stack;

I left the elements as an empty point so it could be expanded as necessary, this made the function that build the stack like:

Stack *Stack_make() {
  Stack *stack = malloc(sizeof(Stack)); // This is ultimately where I become confused
  stack->max_size = INITIAL_STACK_SIZE;
  stack->cur_top = -1;
  stack->elements = malloc(sizeof(int) * INITIAL_STACK_SIZE);

  return stack;
}

My confusion, as I pointed out, is with the malloc for the struct. I know C aligns struct data elements in memory, so I was curious how it would do this if the elements pointer was allocated later, or secondary, to the struct itself. Is this bad practice? Is there a better approach to this?

For completeness, this is what I to expand the stack:

// Relevant bits only
int new_size = stack->max_size + INITIAL_STACK_SIZE;
int *elements = malloc(sizeof(int) * new_size));
if (elements != NULL) {
  memcpy(elements, stack->elements, sizeof(int) * stack->max_size);
  free(stack->elements);
  stack->elements = elements;
}

I know this isn't the best place for "code review" but if you have suggestions to improvements and what not that would be appreciated. The actual question: Is there a better way to do this in C, are there any pitfalls I'm glossing over?

Brandon Buck
  • 7,177
  • 2
  • 30
  • 51

1 Answers1

2

I know C aligns struct data elements in memory, so I was curious how it would do this if the elements pointer was allocated later, or secondary, to the struct itself.

The pointer will be in the same contiguous memory as the rest of the struct, but the malloc'ed memory to which the pointer points will be whereever malloc puts it. (After all, you could have multiple structs with pointers to the same memory; obviously, it cannot be aligned with all of them.)

Is this bad practice?

It depends on what "this" is. If "this" is having a pointer in a struct to dynamically allocated memory, then no, that is not bad practice.

That said, your particular algorithm is not good, as it involves copying everything each time.

Is there a better approach to this?

Yes, realloc.

realloc, will, if possible, expand the memory allocated earlier for that pointer. If that is not possible, then it will move the memory block for you (and deallocate what was used). The return value is a pointer to the memory, which may be the same pointer, or a new one.

So your code (or at least the bit you shared) becomes:

int new_size = stack->max_size + INITIAL_STACK_SIZE;
int *elements = realloc(stack->elements, sizeof(int) * new_size);
if(elements != NULL) {
    stack->elements = elements;
}

FYI, flexible array members (in C99) have variable length, but are included in the memory allocated for the struct itself. They don't fit your need here, but you may be interested in knowing about them, given your question about memory alignment.

Community
  • 1
  • 1
Paul Draper
  • 78,542
  • 46
  • 206
  • 285
  • 1
    Ah, thanks for the reference to `realloc`, that definitely looks like a better approach. – Brandon Buck Mar 19 '14 at 05:00
  • Aggr! You fell into the `realloc` trap. If `realloc` returns `NULL`, you just leaked the block!!! – pat Mar 19 '14 at 05:04
  • Ah, "this" was referring to having this type of unsized pointer in a struct and allocating separate from the struct itself. – Brandon Buck Mar 19 '14 at 05:04
  • @pat You wouldn't check for `NULL` when that returns? – Brandon Buck Mar 19 '14 at 05:05
  • If `realloc` returns `NULL`, you just wrote `NULL` into `stack->elements`, which was where your only pointer to the original block was stored. You have now leaked the memory. – pat Mar 19 '14 at 05:06
  • @pat, yes you are right. I have corrected the example code. – Paul Draper Mar 19 '14 at 05:07
  • Also, flexible array members are not appropriate here, since growing the stack would involve reallocating the stack structure itself. If there are multiple pointers to the stack structure, they must all be updated. – pat Mar 19 '14 at 05:07
  • 1
    @pat, you are correct about flexible array members not being the right solution here (and I never said they were). They are, however, an example of how a variable amount of data can be include within the memory for the struct. – Paul Draper Mar 19 '14 at 05:10
  • Also, copying the contents of the array every time it needs to grow is fine if the array size grows geometrically (which is not the case here), resulting in constant amortized insertion time (see [here](http://en.wikipedia.org/wiki/Dynamic_array)). – pat Mar 19 '14 at 05:11
  • @pat, that's true. It's not an asymptotic ("Big-O") difference. Merge sort and quick sort both sort in `O(n log n)` on average, and yet quick sort is almost always preferred, because it is faster by a constant factor. It's a constant factor difference here too. – Paul Draper Mar 19 '14 at 05:16
  • @pat `flexible array members are not appropriate here, since growing the stack would involve reallocating the stack structure itself` Can you pls explain this ? – Balu Mar 19 '14 at 06:26
  • 2
    @Prakash With flexible members, you wouldn't be able to have an API like `int stack_push(Stack *stack, int element)` because, when the stack is full, the whole `Stack` struct would need to be `realloc`'d, possibly changing its address (because the elements are stored contiguously with the `Stack` itself), so any pointer to the `Stack` would now be invalid. – pat Mar 19 '14 at 06:32