Dynamically growing Stack in C

Question

I'm experiencing some trouble with an assignment. I am supposed to implement a dynamically growing stack that doubles its size when it's full and halves it when it's 1/4 full. Since I am a total C beginner and are unfamiliar with pointers, I've looked through some examples and this is the Code I came up with.

It actually compiles in gcc without warnings, but produces a "Segmentation fault" when I try to run it. I found out that this probably has to do with broken pointers, but I don't see any mistakes and would be glad if someone could point it out for me.

Cheers

# ifndef STACK_H
# define STACK_H
# include "stdlib.h"

typedef struct stack {
  int *stack;
  int used;
  int size;
} stack;

stack* stck_construct() {
    stack *stck;
    stck->stack = (int *)malloc(10 * sizeof(int));
    stck->used = 0;
    stck->size = 10;
    return stck;
}

void   stck_destruct(stack *stck) {
    stck->stack = 0;
    stck->used = stck->size = 0;
    free(stck);
}

int    stck_push(stack *stck, int val) {
  if (stck->used == stck->size) {
    stck->size *= 2;
    stck->stack = (int *)realloc(stck->stack, stck->size * sizeof(int));
  }
  stck->stack[stck->used] = val;
  stck->used++;
  return 1;
}

int    stck_pop(stack *stck, int *val) {
  *val = stck->stack[stck->used];
  free(stck->stack);
  stck->used--;
  if (stck->used <= (stck->size)/4) {
    if (stck->size <=40) stck->size = 10;
    else stck->size /= 2;
    stck->stack = (int *)realloc(stck->stack, stck->size * sizeof(int));
  }

  return 1;
}

int main(){

    stack* test;

    test=stck_construct();

    int i; int out;
    for (i =1; i<=10; i++)
        stck_push(test, i);

    for (i =1; i<=10; i++)  {
        stck_pop(test,&out);
        printf("%i\n", out);
    }
    stck_destruct(test);
    return 0;
}

# endif

In C, [don't cast the return value of `malloc()` and `realloc()`](http://stackoverflow.com/a/605858/28169). — unwind, Jan 22 '13 at 15:28
In addition to what Alberto Miranda pointed out (which is likely the immediate cause of the segfault), you have a memory leak in `stck_destruct` (you only set `stck->stack` to null without freeing it). Also, you are freeing `stck->stack` in `stck_pop` before only conditionally reallocating it, which means you're destroying the previous contents and making it possible for `stck->stack` to remain unallocated. — David Brown, Jan 22 '13 at 15:33
@unwind For all my years programming in C, I had never considered this. It makes so much sense. Thanks! — Alberto Miranda, Jan 22 '13 at 15:40

Alberto Miranda · Accepted Answer · 2013-01-22T15:39:55.570

5

In stack* stck_construct() you're using stck-> without having created stck first. As it is, it's only a pointer referencing nowhere. This will surely produce a Segmentation Fault. You're confusing a stack* with an actual stack (or maybe you just forgot to malloc the whole thing :)

N.B: There are also some other bugs roaming around which I didn't mention. See David's and Alexey's comments if you're interested.

edited Jan 22 '13 at 15:39

answered Jan 22 '13 at 15:29

Alberto Miranda

382
6
16

thanks a lot, i really appreciate your help. sadly, i seem to lack basic understanding of pointers. i have tried to fit my construct function according to your hints to `stack* stck_construct() { stack *stck; stck = malloc(10 * sizeof(int)); stck->stack = NULL; stck->used = 0; stck->size = 10; return stck; }` , but it still produces the same error. could you maybe be a bit more specific about what i need to change in order for it to work? – Lion Härtner Jan 22 '13 at 16:05
alright, i figured it out myself, and fully understand your answer now. to whoever is interested: i used `stack* stck_construct() { stack *stck; stck = malloc(sizeof(stack)); stck->stack = malloc(10 * sizeof(int)); stck->used = 0; stck->size = 10; return stck; }` – Lion Härtner Jan 22 '13 at 17:26
@LionHärtner Sorry, I didn't see your question earlier. What you did is exactly what I meant: you have to allocate space for your structure before trying to access any of its fields. Good job! – Alberto Miranda Jan 22 '13 at 17:29

score 2 · Answer 2 · answered Jan 22 '13 at 15:41

Bugs annotated:

stack* stck_construct() {
    // stck is a pointer, you never initialize it to point to an existing object:
    stack *stck;
    // you dereference the invalid pointer with stck->stack:
    stck->stack = (int *)malloc(10 * sizeof(int));
    stck->used = 0;
    stck->size = 10;
    return stck;
}

void   stck_destruct(stack *stck) {
    stck->stack = 0;
    stck->used = stck->size = 0;
    // I thought you were assigning the pointer to the allocated memory to stck->stack,
    // and by now that pointer is 0 as you just did stck->stack = 0;
    free(stck);
}

  if (stck->used == stck->size) {
    stck->size *= 2;
    // if realloc() fails you end up with twice as big stck->size and
    // with stck->stack = NULL
    stck->stack = (int *)realloc(stck->stack, stck->size * sizeof(int));
  }

  // You first store the new element and then advance the index
  stck->stack[stck->used] = val;
  stck->used++;

  // But when you remove it you don't do the two operations in the reverse order:
  *val = stck->stack[stck->used];
  // and for some reason you additionally destroy all data
  free(stck->stack);
  stck->used--;

    // and then you realloc() using the invalid pointer (you just free()'d it!)
    stck->stack = (int *)realloc(stck->stack, stck->size * sizeof(int));

Dynamically growing Stack in C

2 Answers2