Stack implementation using malloc in C

Question

for learning purpose I'm implementing a stack with it's functions in C. I added some small additional functionality to use malloc the first time and try to understand it properly.

I wrote a function which is initially creating my stack struct. The return value of the function is a new struct with an already allocate memory. What is the best way to handle a malloc exception in a function which return value should be a struct? Maybe should I design the function different? I'm aware that the printf is not doing it's job ;)

My Stack struct:

typedef struct Stack
{
    int count;
    int capacity;
    int *data;
} Stack;

Creating a Stack instance:

Stack create_stack(int initialcapacity)
{
    Stack new_stack;
    new_stack.count = 0;
    new_stack.capacity = initialcapacity;

    if (!(new_stack.data = malloc(initialcapacity * sizeof(int))))
        printf("not enough memory!");

    return new_stack;
}

The function is called with the initial capacity of the stack:

Stack stack = create_stack(10);

A second question came up while I was writing a function to delete the Stack instance.

int delete_stack(Stack *stack)
{
    stack->count = 0;
    stack->capacity = 0;
    free(stack->data);
    stack->data = NULL;
    return 0;
}

Am I able to remove also the struct instance itself? It feels not complete to just set the values back to 0 and direct int* to NULL.

Last but not least, I have a question to my push function. Also here I added some functionality which allows me to push something on the stack while it is already full:

void push(int value, Stack *stack)
{   
    if (stack->count == stack->capacity)
    {   
        int *temp = malloc(stack->capacity * sizeof(int));

        int i;
        for (i = 0; i < stack->count; i++)
            temp[i] = stack->data[i];

        free(stack->data);
        stack->data = NULL;
    
        stack->data = malloc(stack->capacity * 2 * sizeof(int));

        for (i; i > -1; i--)
            stack->data[i] = temp[i];

        free(temp);
        temp = NULL;
        stack->data[stack->count] = value;
        stack->count++;
        stack->capacity = stack->capacity * 2;
    }
    else
    {
        stack->data[stack->count] = value;
        stack->count++;
    }
}

Is it necessary to "free" the smaller array and put the pointer to NULL before I allocate a new array double the size?

If there is anything from my code which is unnecessary or not written properly, please let me know, I'm grateful for any hint which makes me better.

Cheeers, me

Razbit · Accepted Answer · 2016-12-11 19:59:53Z

2

I would do it with pointers. That is, your create_stack() would allocate a new Stack struct using malloc, then set the values to the struct and usee malloc again to allocate space for the Stack->data. Like this:

Stack* create_stack(int initialcapacity) {
    Stack* new_stack = malloc(sizeof(Stack));

    if (new_stack == NULL)
        return NULL; // return null to tell the caller that we failed

    new_stack->count = 0;
    new_stack->capacity = initialcapacity;
    new_stack->data = malloc(initialcapacity * sizeof(int))

    if (new_stack->data == NULL)
    {
        free(new_stack);
        return NULL;
    }

    return new_stack;
}

With this, we "handle" a malloc error by returning NULL, so the caller knows we failed.

Now that we have used malloc to allocate the Stack struct, you can (read: MUST) free the space taken by it using free(stack); in delete_stack().

In push(), the temporary array is not needed, that is, you could just right away allocate a bigger array, copy the contents to it from the original stack->data, free stack->data and set it to the newly malloc'd array:

int *temp = malloc(stack->capacity * 2 * sizeof(int));
// TODO: what if malloc fails?

int i;
for (i = 0; i < stack->count; i++)
    temp[i] = stack->data[i];

free(stack->data);
stack->data = temp;

stack->data[stack->count] = value;
stack->count++;
stack->capacity = stack->capacity * 2;

answered Dec 11, 2016 at 19:59

Razbit

1364 bronze badges

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

2 Comments

hi im vinzent Over a year ago

Thanks a lot. I catch myself daily in writing too complex routines, such as the temp array approach. I hope it just gets better while simply doing. Do you have any specific tips besides just coding and try to get as much feedback as possible?

Razbit Over a year ago

The more you code, the better you become. Don't be afraid to try new things, challenge yourself

gudok · Accepted Answer · 2016-12-11 20:00:26Z

2

Q. What is the best way to handle a malloc exception in a function which return value should be a struct?

There are at least three ways:

1) Instead of returning structure itself, return a pointer to it. This means two mallocs: one is for structure itself and another one is for data field. Returning NULL pointer means that something went wrong during construction.

struct Stack* create_stack(int initialcapacity) {
    struct Stack* stack = malloc(sizeof(struct Stack));
    ...
    return stack;
}

2) More flexible way is to pass pointer to already allocated structure. Flexibility comes from idea that calling code controls where to allocate structure: on stack or in dynamic memory. Return value of function may be used solely to notify calling code about errors:

bool create_stack(int initialcapacity, struct Stack* stack) {
  ...
}

// if calling code wants structure on stack (yeah, "stack" on stack)
struct Stack stack;
if (!create_stack(50, &stack)) {
  die();
}

// if calling code wants it in dynamic memory
struct Stack* stack = malloc(sizeof(struct Stack));
if (!stack) {
  die();
}
if (!create_stack(50, stack)) {
  die();
}

3) If your program is not a 10,000+ LOC production code, easiest way may be to simply print error message and abort program immediately if allocation fails. Usually allocation errors are fatal: you can't recover in any meaningful way if there is not enough memory. You may even create a wrapper function over malloc to automatically catch such errors and exit:

void* my_malloc(size_t count) {
    void* ptr = malloc(count);
    if (ptr == NULL) {
      fprintf(stderr, "Allocation failed");
      exit(EXIT_FAILURE);
    }
    return ptr;
}

Q. Am I able to remove also the struct instance itself?

No, you can't. Because it is allocated on stack (the structure itself, not the data). If you want to delete structure itself, you need to use approach #1 from above.

And, by the way, there is no need to set zeroes and NULLs to fields. It doesn't delete anything. Such approach is used rarely and with only purpose to catch bugs (when calling code first deletes some structure and then tries to use it afterwards).

Q. Is it necessary to "free" the smaller array and put the pointer to NULL before I allocate a new array double the size?

Once again, you don't need to NULLify anything -- it doesn't delete anything. Instead of two mallocs and manual copying use realloc, which will do most of the work for you.

answered Dec 11, 2016 at 20:00

gudok

4,2092 gold badges23 silver badges31 bronze badges

3 Comments

hi im vinzent Over a year ago

I read that setting a pointer to NULL after it's "used" is common c programming behaviour? It sounded legit as it allows me to check for NULL if needed? Any ideas on this approach?

gudok Over a year ago

@hiimvinzent, such aggressive NULLifying is only justifiable for safety reasons. It easily allows you to catch bug when calling code first calls delete_stack() but attempts to use deleted structure at some point later. Without NULL, there are chances that it will be able to access memory (if it was already reused by some other call to malloc()). NULL will generate memory access error instead. But such approach is not very often used in practice.

gudok Over a year ago

Primary reason for setting some pointer to NULL is semantics and not the fact that you've just deallocated memory through it. For example, struct Customer* current_customer; may point to different customers, be multiple times allocated, deallocated and reassigned during program execution. Setting and checking for NULL is required and is part of program logic.

Malcolm McLean · Accepted Answer · 2016-12-11 21:48:01Z

Generally, you should be able to declare a structure, then have an array of say 64 of them, with an integer to say which entry is on the top. Very simple, and no dynamic allocation. But 64 is pretty low, That's because stacks, recursion, and levels of nesting are intimately linked. Usually it should be possible to see that 64 is an insane level of nesting, and no legitimate input will ever even approach it. You then might need a guard to protect from malicious or corrupted input, but that just terminates the program or sub-routine.

If you can't establish a low sanity bound on a stack, it might that you still need one. Either it's a rare case where nesting goes very deep, or it's that you haven't approached the problem in the best way, but a sub-optimal program that still works is better than no program.

So you use the same structure, but the stack is set up with a call to malloc() and, if it grows out of bounds, regrow with a call to realloc(). You might want to still sanity check it, but now sanity checks are much higher, a million or so as opposed to 64. You also have to check that realloc does not fail.

typedef struct
{
    int x;
    char astring[32];
} ENTRY;

static ENTRY *stack = 0;;
static int top = -1;
static int N = 0; 

void push(const ENTRY *e)
{
   /* grow logic like this */
   ENTRY *temp = realloc(stack, newsize * sizeof(ENTRY));
   if(temp)
     stack = temp;
   else
   {
      /* reallocation has failed but stack still valid */
      free(stack);
      N = 0;
      top = -1;
      /* for the sake of argument do this. We need temp to avoid
         a memory leak */
      fprintf(stderr, "out of memory\n");
   }

    /* push here, trivial */
}

int pop(ENTRY *e)
{
    /* e is a non-const pointer. Fill and reset stack top */ 
}

You might want the stack global as in the example or you might want to wrap it in a structure you pass about. Usually you'll want either pointers or structures on the stack, but occasionally you might need a stack of integers or floating point values.

There's no good way of handling memory allocation errors in C, especially ones which can't happen (a computer with several GB of memory installed is more likely to develop an electrical fault than to run out of memory when asked for a couple of kilobytes). The usual rule is to shunt up. But that makes the push call difficult, because every push could potentially run the computer out of memory (but it can't really, it's just your encapsulation allows the function to fail).

Collectives™ on Stack Overflow

Stack implementation using malloc in C

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related