5
\$\begingroup\$

One of my current side projects includes a stack-based interpreter written in C for a programming language I'm designing, SSBL. Since the entire language is stack-based, I needed a way to create and store stacks. Currently there are three separate stack types:

  • One that stores an array of unsigned chars.
  • One that stores an array of unsigned shorts.
  • One that stores an array of unsigned longs.

Each individual stack can also be created with a certain in-out type, which includes:

  • FIFO (first in, first out)
  • FILO (first in, last out)
  • LIFO (last in, first out)
  • LILO (last in, last out)

Here's the code:

ssbl_stack.h

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

#define STACK_SIZE 65535
#define STACK_MEMSET 0

typedef enum
{
    FIFO,
    FILO,
    LIFO,
    LILO
} SSBL_StackIO;

typedef struct
{
    SSBL_StackIO m_IO;
    unsigned short m_Count;
    unsigned char m_Elements[STACK_SIZE];
} SSBL_StackUint8;

typedef struct
{
    SSBL_StackIO m_IO;
    unsigned short m_Count;
    unsigned short m_Elements[STACK_SIZE];
} SSBL_StackUint16;

typedef struct
{
    SSBL_StackIO m_IO;
    unsigned short m_Count;
    unsigned long m_Elements[STACK_SIZE];
} SSBL_StackUint32;

SSBL_StackUint8* SSBL_StackUint8Create(SSBL_StackIO io);
void SSBL_StackUint8Push(SSBL_StackUint8* stack, unsigned char element);
unsigned char SSBL_StackUint8Pop(SSBL_StackUint8* stack);
unsigned char SSBL_StackUint8Get(SSBL_StackUint8* stack, unsigned short index);

SSBL_StackUint16* SSBL_StackUint16Create(SSBL_StackIO io);
void SSBL_StackUint16Push(SSBL_StackUint16* stack, unsigned short element);
unsigned short SSBL_StackUint16Pop(SSBL_StackUint16* stack);
unsigned short SSBL_StackUint16Get(SSBL_StackUint16* stack, unsigned short index);

SSBL_StackUint32* SSBL_StackUint32Create(SSBL_StackIO io);
void SSBL_StackUint32Push(SSBL_StackUint32* stack, unsigned long element);
unsigned long SSBL_StackUint32Pop(SSBL_StackUint32* stack);
unsigned long SSBL_StackUint32Get(SSBL_StackUint32* stack, unsigned short index);

ssbl_stack.c

#include "ssbl_stack.h"

SSBL_StackUint8* SSBL_StackUint8Create(SSBL_StackIO io)
{
    SSBL_StackUint8* newStack = malloc(sizeof(SSBL_StackUint8));
    newStack->m_IO = io;
    newStack->m_Count = 0;
    memset(newStack->m_Elements, STACK_MEMSET, sizeof(newStack->m_Elements));
    return newStack;
};

void SSBL_StackUint8Push(SSBL_StackUint8* stack, unsigned char element)
{
    SSBL_StackUint8 tempStack = *stack;
    if(tempStack.m_Count < STACK_SIZE)
    {
        if(tempStack.m_IO == FIFO || tempStack.m_IO == FILO)
        {
            for(int i = 0; i < tempStack.m_Count + 1; i++)
            {
                if((i + 1) < (tempStack.m_Count + 1))
                {
                    tempStack.m_Elements[i + 1] = stack->m_Elements[i];
                }
            }
            tempStack.m_Elements[0] = element;
            tempStack.m_Count++;
            *stack = tempStack;
        }

        else if(tempStack.m_IO == LIFO || tempStack.m_IO == LILO)
        {
            tempStack.m_Elements[tempStack.m_Count] = element;
            tempStack.m_Count++;
            *stack = tempStack;
        }
    }
}

unsigned char SSBL_StackUint8Pop(SSBL_StackUint8* stack)
{
    SSBL_StackUint8 tempStack = *stack;
    if(tempStack.m_Count > 0)
    {
        if(tempStack.m_IO == FIFO || tempStack.m_IO == LIFO)
        {
            unsigned char retVal = tempStack.m_Elements[0];
            for(int i = tempStack.m_Count - 1; i >= 0; i--)
            {
                tempStack.m_Elements[i - 1] = stack->m_Elements[i];
            }
            tempStack.m_Count--;
            *stack = tempStack;
            return retVal;
        }

        else if(tempStack.m_IO == FILO || tempStack.m_IO == LILO)
        {
            unsigned char retVal = tempStack.m_Elements[tempStack.m_Count - 1];
            tempStack.m_Elements[tempStack.m_Count - 1] = STACK_MEMSET;
            tempStack.m_Count--;
            *stack = tempStack;
            return retVal;
        }
    }

    return 0;
}

unsigned char SSBL_StackUint8Get(SSBL_StackUint8* stack, unsigned short index)
{
    SSBL_StackUint8 tempStack = *stack;
    if(index >= 0 && index < tempStack.m_Count)
    {
        return tempStack.m_Elements[index];
    }

    return 0;
}

SSBL_StackUint16* SSBL_StackUint16Create(SSBL_StackIO io)
{
    SSBL_StackUint16* newStack = malloc(sizeof(SSBL_StackUint16));
    newStack->m_IO = io;
    newStack->m_Count = 0;
    memset(newStack->m_Elements, STACK_MEMSET, sizeof(newStack->m_Elements));
    return newStack;
}

void SSBL_StackUint16Push(SSBL_StackUint16* stack, unsigned short element)
{
    SSBL_StackUint16 tempStack = *stack;
    if(tempStack.m_Count < STACK_SIZE)
    {
        if(tempStack.m_IO == FIFO || tempStack.m_IO == FILO)
        {
            for(int i = 0; i < tempStack.m_Count + 1; i++)
            {
                if((i + 1) < (tempStack.m_Count + 1))
                {
                    tempStack.m_Elements[i + 1] = stack->m_Elements[i];
                }
            }
            tempStack.m_Elements[0] = element;
            tempStack.m_Count++;
            *stack = tempStack;
        }

        else if(tempStack.m_IO == LIFO || tempStack.m_IO == LILO)
        {
            tempStack.m_Elements[tempStack.m_Count] = element;
            tempStack.m_Count++;
            *stack = tempStack;
        }
    }
}

unsigned short SSBL_StackUint16Pop(SSBL_StackUint16* stack)
{
    SSBL_StackUint16 tempStack = *stack;
    if(tempStack.m_Count > 0)
    {
        if(tempStack.m_IO == FIFO || tempStack.m_IO == LIFO)
        {
            unsigned short retVal = tempStack.m_Elements[0];
            for(int i = tempStack.m_Count - 1; i >= 0; i--)
            {
                tempStack.m_Elements[i - 1] = stack->m_Elements[i];
            }
            tempStack.m_Count--;
            *stack = tempStack;
            return retVal;
        }

        else if(tempStack.m_IO == FILO || tempStack.m_IO == LILO)
        {
            unsigned short retVal = tempStack.m_Elements[tempStack.m_Count - 1];
            tempStack.m_Elements[tempStack.m_Count - 1] = STACK_MEMSET;
            tempStack.m_Count--;
            *stack = tempStack;
            return retVal;
        }
    }

    return 0;
}

unsigned short SSBL_StackUint16Get(SSBL_StackUint16* stack, unsigned short index)
{
    SSBL_StackUint16 tempStack = *stack;
    if(index >= 0 && index < tempStack.m_Count)
    {
        return tempStack.m_Elements[index];
    }

    return 0;
}

SSBL_StackUint32* SSBL_StackUint32Create(SSBL_StackIO io)
{
    SSBL_StackUint32* newStack = malloc(sizeof(SSBL_StackUint32));
    newStack->m_IO = io;
    newStack->m_Count = 0;
    memset(newStack->m_Elements, STACK_MEMSET, sizeof(newStack->m_Elements));
    return newStack;
}

void SSBL_StackUint32Push(SSBL_StackUint32* stack, unsigned long element)
{
    SSBL_StackUint32 tempStack = *stack;
    if(tempStack.m_Count < STACK_SIZE)
    {
        if(tempStack.m_IO == FIFO || tempStack.m_IO == FILO)
        {
            for(int i = 0; i < tempStack.m_Count + 1; i++)
            {
                if((i + 1) < (tempStack.m_Count + 1))
                {
                    tempStack.m_Elements[i + 1] = stack->m_Elements[i];
                }
            }
            tempStack.m_Elements[0] = element;
            tempStack.m_Count++;
            *stack = tempStack;
        }

        else if(tempStack.m_IO == LIFO || tempStack.m_IO == LILO)
        {
            tempStack.m_Elements[tempStack.m_Count] = element;
            tempStack.m_Count++;
            *stack = tempStack;
        }
    }
}

unsigned long SSBL_StackUint32Pop(SSBL_StackUint32* stack)
{
    SSBL_StackUint32 tempStack = *stack;
    if(tempStack.m_Count > 0)
    {
        if(tempStack.m_IO == FIFO || tempStack.m_IO == LIFO)
        {
            unsigned long retVal = tempStack.m_Elements[0];
            for(int i = tempStack.m_Count - 1; i >= 0; i--)
            {
                tempStack.m_Elements[i - 1] = stack->m_Elements[i];
            }
            tempStack.m_Count--;
            *stack = tempStack;
            return retVal;
        }

        else if(tempStack.m_IO == FILO || tempStack.m_IO == LILO)
        {
            unsigned long retVal = tempStack.m_Elements[tempStack.m_Count - 1];
            tempStack.m_Elements[tempStack.m_Count - 1] = STACK_MEMSET;
            tempStack.m_Count--;
            *stack = tempStack;
            return retVal;
        }
    }

    return 0;
}

unsigned long SSBL_StackUint32Get(SSBL_StackUint32* stack, unsigned short index)
{
    SSBL_StackUint32 tempStack = *stack;
    if(index >= 0 && index < tempStack.m_Count)
    {
        return tempStack.m_Elements[index];
    }

    return 0;
}

test.c

#include <stdio.h>
#include <conio.h>

#include "util/ssbl_stack.h"

int main(int argc, char** argv)
{
    printf("Starting up\n");
    printf("\n");
    _getch();

    SSBL_StackUint8* stack = SSBL_StackUint8Create(LILO);
    SSBL_StackUint8Push(stack, 44);
    SSBL_StackUint8Push(stack, 22);
    SSBL_StackUint8Push(stack, 11);

    printf("Stack Element=0 [get]: %d\n", SSBL_StackUint8Get(stack, 0));
    printf("Stack Element=1 [get]: %d\n", SSBL_StackUint8Get(stack, 1));
    printf("Stack Element=2 [get]: %d\n", SSBL_StackUint8Get(stack, 2));
    printf("\n");
    _getch();

    printf("Stack Element [pop]: %d\n", SSBL_StackUint8Pop(stack));
    printf("Stack Element [pop]: %d\n", SSBL_StackUint8Pop(stack));
    printf("Stack Element [pop]: %d\n", SSBL_StackUint8Pop(stack));
    printf("\n");
    _getch();

    return 0;
}

What can be improved? Can this be genericized? Are there any bad practices? Any critical issues?

\$\endgroup\$
  • 3
    \$\begingroup\$ I'm curious, why are you calling a FIFO structure a stack, shouldn't it be a queue? \$\endgroup\$ – pacmaninbw May 22 '17 at 15:44
  • \$\begingroup\$ Right now your code is broken, specifically the SSBL_StackUint32 struct is broken because it can't handle unsigned ints, only unsigned shorts. You also might want to look at calloc() versus malloc(). \$\endgroup\$ – pacmaninbw May 22 '17 at 15:52
  • \$\begingroup\$ @pacmaninbw Yep. I actually noticed and fixed that last night, right after I posted the question. Just forgot to upload it. Should be fixed now. \$\endgroup\$ – Ethan Bierlein May 22 '17 at 15:57
  • 4
    \$\begingroup\$ Is there a difference between FIFO and LILO (or FILO and LIFO)? \$\endgroup\$ – vnp May 22 '17 at 16:40
6
\$\begingroup\$

A few observations to help out:

Bug in Pop

In a LIFO structure the value to be returned is tempStack.m_Elements[tempStack.m_Count - 1] not tempStack.m_Elements[0];.

LIFO structures are definitely different from FIFO structures.

The Code is Not Portable

Right now the code will only compile on Windows because of the use of conio.h. It might be better to just use standard C io, in this case probably getchar(). It might also be better if conio.h was only included where it was needed rather than in utilit/ssbl_stack.h.

Struct Name May be Incorrect

It might be better to rename StackUint32 to StackUlong, an unsigned long is not guaranteed to be 32 bits, it may be 64 bits depending on the architecture and compiler used.

Prefer Calloc() Over Malloc() in This Particular Instance

Calloc by default zeros out the memory it allocates, so rather than calling malloc() and then using memset() to set the entire array to zero, call calloc() and the entire struct is already zero'd for your.

LILO Versus FIFO

@vnp is correct in his comment.

Is there really a difference between these two, as far as I can tell the both equate to FIFO?

The same question applys to FILO and LIFO, in each case it evaluates to First In Last Out?

Typical computer science terminology refers to stacks as LIFO and queues as FIFO, the two alternate forms could confuse people using the structures as a library.

Incorrect Order of Execution of Create Functions

If the code continues to use malloc() rather than calloc() the call to memset() should clear the entire struct and occur immediately after the malloc rather than at the end. This would change the existing code from:

SSBL_StackUint8* SSBL_StackUint8Create(SSBL_StackIO io)
{
    SSBL_StackUint8* newStack = malloc(sizeof(SSBL_StackUint8));
    newStack->m_IO = io;
    newStack->m_Count = 0;
    memset(newStack->m_Elements, STACK_MEMSET, sizeof(newStack->m_Elements));
    return newStack;
};

to

SSBL_StackUint8* SSBL_StackUint8Create(SSBL_StackIO io)
{
    SSBL_StackUint8* newStack = malloc(sizeof(SSBL_StackUint8));
    memset(*newStack, STACK_MEMSET, sizeof(newStack));
    newStack->m_IO = io;
    return newStack;
};

Which reduces the complexity of the function and reduces the number of assignments to fields to 1.

Use of Fixed Sized Arrays

If the structs keep a record of the capacity of the arrays, they could start at a much smaller size (1024) and be reallocated as necessary when the m_Count value reaches the capacity while this performs slightly slower than what is currently implemented, it uses much less memory than the current implementation.

Prefer Linked Lists for FIFO Structures

It is much easier to implement FIFO structures as a linked list, then the pop becomes a simple removal of the first element in the list. While this does prevent with indexing into an array overall it is faster and more flexible for LIFO structures to be implemented this way. It reduces all the copying that is currently going into implementing LIFO structures.

\$\endgroup\$
  • 1
    \$\begingroup\$ In my implementation, there is a difference between FIFO and LILO, partially due to my (incorrect) interpretation of their definitions. In a FIFO stack, when ...Push is called, the passed element is added to the beginning of the stack and when ...Pop is called the element at the beginning of the stack is removed. Vice versa for LILO. The same concept applies to FILO and LIFO as well. \$\endgroup\$ – Ethan Bierlein May 22 '17 at 18:05
  • \$\begingroup\$ Why do you say, "calloc() by default zeros out the memory it allocates"? I don't think there's anything default about it; that's the only documented correct behaviour of the function. \$\endgroup\$ – Toby Speight May 23 '17 at 9:01
  • \$\begingroup\$ Typo in the memset() call: that should be sizeof *newStack, not sizeof newStack. You might suggest malloc(sizeof *newStack) too, to match (and that's a standard idiom I'd recommend). \$\endgroup\$ – Toby Speight May 23 '17 at 9:03
4
\$\begingroup\$

Use integer types with well-defined widths

In the stdint.h header, you are provided with fixed width types. Currently, your SSBL_StackUint32 structure assumes that long is 32 bits, however, on some implementations it will be 64 bits.

Simply replace unsigned long with uint32_t. The latter type is guaranteed to always be 32 bits wide.

typedef struct
{
    SSBL_StackIO m_IO;
    unsigned short m_Count;
    uint32_t m_Elements[STACK_SIZE]; // replaced here
} SSBL_StackUint32; // now the name is accurate

Your other structures work out with their current types, but I'd still suggest modifying them so that they have the explicit width you expect.

Add proper copy operations to improve performance

Your push()/pop() functions take a copy of the parameter stack like so:

SSBL_StackUint32 tempStack = *stack;

You will be copying STACK_SIZE * sizeof(int32_t) bytes. You only want to copy the bytes in your stack that contain values. A simple copy function will do the trick:

void stack32_copy(SSBL_StackUint32* restrict dst, SSBL_StackUint32 const* restrict src)
{
    memcpy(dst, src,
        sizeof(dst->m_IO) + sizeof(dst->m_Count) + sizeof(uint32_t) * src->m_Count);
}

This function simply copies the bytes starting at the src address up to the m_Elements + m_Count bytes into the dst address. It is the equivalent of copying m_IO, m_Count and m_Count elements starting from m_Elements.

You definitely do not want to copy STACK_SIZE * sizeof(<int_type>) bytes every single time you call push() or pop(), so this avoids wasteful copying.

You'll want to modify the original copying line into the following:

SSBL_StackUint32 tempStack;
stack32_copy(&tempStack, stack);

The remaining copy behaviour can be adapted from this point.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.