Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Simple Stacks! A Gentle Approach

dynamic array realloc memory leak stack

  • Please log in to reply
3 replies to this topic

#1 Dumaju

Dumaju

    CC Lurker

  • Just Joined
  • Pip
  • 8 posts

Posted 15 May 2010 - 05:57 PM

Welcome to my Simple Stacks tutorial! By all means, this is not the best nor greatest implementation but I'm sure you'll learn something new if you're just starting out. I also acknowledge I could have done a lot cooler looking stuff in C++ but that's just boring.

First off, we start with the header file:

#ifndef SIMPLESTACK_H_INCLUDED
#define SIMPLESTACK_H_INCLUDED

#include <stdlib.h>
#include <stdio.h>

/*
    It's probably a good idea to have some definite limit on the size of your data structures. For one,
    it'll be a lot harder to manage if you're careless.

    I imagine you could render this constant useless by setting it to -1 if you wanted to remove the limit.
*/
#define MAX_STACK_SIZE 50

/*
    I also like to have a constant defined to turn debugging messages on and off quickly and easily.
*/
#define STACK_DEBUG_MODE 1

/*
    Below is the basic structure of the stack.
    In this example, I'm using characters,
    just by random choice. However, you could use any
    data type really.

    Basically, it holds 2 pieces of data:
        - An array
        - The size of the stack, as 'unsigned short'.
*/
typedef unsigned short ushort;

typedef struct
{
    char* data;
    ushort size;
} SimpleStack;

/*
    You can find explainations and discussion
    about these procedures below.
*/
SimpleStack CreateStack(void);

void FreeStack(SimpleStack*);

ushort StackPush(SimpleStack*, char);

char StackPop(SimpleStack*);

char StackTop(SimpleStack*);

void ReportError(const char*);

#endif // SIMPLESTACK_H_INCLUDED

To make life easier, we will make a simple procedure that creates a new stack object for us when we need to use one. It saves the hassle of having to mess with malloc() and what not every time you need to use a stack.

SimpleStack CreateStack(void)
{
    SimpleStack newStack;

    newStack.data = (char*) malloc(sizeof(char));
    if (newStack.data == NULL)
    {
        ReportError("There's not enough memory to create a new stack!");
    }

    newStack.size = 1;

    return newStack;
}

I use pointers here but don't worry, they're not as scary as some people make them out to be, haha.

What makes pointers so useful is that not only can they be used as super-powerful references but they can also be used to dynamically allocate memory on the heap. This isn't really a pointers tutorial but I'm sure there are some decent ones around here on these forums.

This is the only procedure that passes by value. From now on, we will be passing by pointer. Although it's not that much of an issue with small data structures, performance issues can arise when they are large in size so it's best to get into the habit of passing by reference or pointer with objects, especially those that have the potential to take up a lot of memory, as soon as you can.

If you're new to C, you may not have seen malloc() before. malloc() is a powerful tool at every C programmer's disposal. You may be used to and possibly even been frustrated by the fact you have to predetermine every array you declare. Well, malloc() is the answer to that problem and allows you to, when coupled with pointers, to create dynamic arrays at run time. However, if you do ever need to use it, be aware that it expects you to give the size of the block you're allocating in bytes and not as the actual array length as I've witnessed before. You have to multiply the size of the data type you wish to allocate by the number of elements you need.

Oh and one more thing, don't use malloc() in C++, it has a much nicer alternative and a ** of a lot less confusing to new blood.

Since we're using the malloc() procedure, it's probably a wise idea to have some sort of method to help us safely remove unused stacks and free up the memory we allocated.

Infact, I can't stress to you enough how important it is. No one likes memory leaks and they especially don't like people who don't make an effort to stop them from happening. Although, I'm not saying you're one of them!

void FreeStack(SimpleStack* stackObj)
{
    free(stackObj->data);
    stackObj = NULL;
}

Also, take notice that we're now passing by pointer. Again, if you're new, the star next to the type name could have easily been missed.

Anyway, it just wouldn't be a stack implementation without the famous Push and Pop procedures.

Pushing data on to the stack is pretty straight forward but if you're new to C, you might not have come across realloc() yet. Good thing I'm here to explain it to you, eh?

As malloc() allows you allocate a block of memory dynamically, realloc() allows you to change the size of the block dynamically. It really comes in use when memory usage is restricted, though it's not something you can always rely on.

Obviously, this 'pushes' a new item on to the top of the stack, returning 1 on success or 0 on failure.

Here I reallocate the newly sized memory block to a temporary object. That way, if it failed, there's no risk of your original stack object being lost, which I imagine would be a total pain in the arse.

ushort StackPush(SimpleStack* stackObj, char item)
{
    if (stackObj->size == MAX_STACK_SIZE)
    {
        ReportError("Error: Maximum stack size has been exceeded");
        return 0;
    }

    char* tempObj = (char*) realloc(stackObj->data, sizeof(char) * ++stackObj->size);
    if (tempObj == NULL)
    {
        ReportError("There's not enough memory to push a new item on the stack!");
        return 0;
    }

    tempObj[stackObj->size - 1] = item;

    stackObj->data = tempObj;

    free(tempObj);

    return 1;
}

Again, same scenario as the Push procedure, just the opposite way round:

char StackPop(SimpleStack* stackObj)
{
    char item = '\0';

    if (stackObj->size == 0)
    {
        ReportError("Error: There are no data elements on this stack!");
        return (char) NULL;
    }

    else
    {
        stackObj->size--;
        item = stackObj->data[stackObj->size];
        stackObj->data[stackObj->size + 1] = (char) NULL;

        char* tempObj = (char*) realloc(stackObj->data, sizeof(char) * stackObj->size);
        if (tempObj == NULL)
        {
            ReportError("Could not pop the item off the stack!");
            return (char) NULL;
        }
    }
   
    stackObj = tempObj;
    free(tempObj);

    return item;
}

And finally, a procedure to look at the top of the stack, which is probably the simplest stack procedure of them all:

char StackTop(SimpleStack* stackObj)
{
    if (stackObj->size == 0)
    {
        ReportError("Error: There are no data elements on this stack!");
        return (char) NULL;
    }

    return stackObj->data[stackObj->size - 1];
}

Also, if you're copying things down from here, you'll want this procedure too:
void ReportError(const char* message)
{
    if (STACK_DEBUG_MODE == 1) perror(message);
}

Anyway, that just about wraps it up. Although this was pretty easy going, it'll come in great use when I write my next tutorial on converting infix expressions to postfix form (Reverse Polish Notation) and then evaluating it.

Thanks for your time, I hope you enjoy! ^^

Also, I've attached the source file. It isn't commented because I explained all of it in this post.

Attached Files


Edited by Dumaju, 16 May 2010 - 11:09 AM.

  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 16 May 2010 - 06:01 AM

Is there a reason why you aren't using standard data types?
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 Dumaju

Dumaju

    CC Lurker

  • Just Joined
  • Pip
  • 8 posts

Posted 16 May 2010 - 10:49 AM

The only datatypes I use are characters, character pointers, the structure and unsigned short integers which have been defined as 'ushort'. They all seem pretty standard to me?
  • 0

#4 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 16 May 2010 - 11:47 AM

I just find using aliases for standard types annoying. Guess it's just me.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download