[phyrrus9]

Alright, I hate that big A word, so we will just call this a typeless stack. In C++ it was really simple, here on the other hand it is not so much. What are the pros and cons of using a typeless stack?

Pros:
Multiple data types
Can use multiple data types on the same stack
Easy way to manipulate data
Works same way as system stack

Cons:
Annoying at times
Difficult to manage
More math involved

So, let's get started with some structures. This tutorial assumes you know math, basic C, and pointers (as well as pointer arithmetic), if you do not please learn (or at least read) that before continuing.

Code:

struct Stack
{
     void *base;
     void *sp;
};

Now, here is where it's really cool. We actually don't need to use a structure. Remember the SP is the only thing we use, and the programmer needs to ensure his stack is balanced at all times. If we keep these assumptions (we do), then all we need is a single pointer.

Code:

typedef void* Stack;

But why even bother? Why not just use void *'s directly? Well, just for now we will use the typedef, for simplicity.

Stack.h:

Code:

#include <stdlib.h>
void Stack_init(Stack *obj, size_t size); //note the extra pointer
void Stack_push(Stack *obj, void *data, size_t size);
void Stack_pop(Stack *obj, void *data, size_t size);
void Stack_destroy(Stack obj);

Now, why do we have that extra pointer?
Well, if we assign it, we would be changing the value inside the function, but we just have a copy of that value (the address, for the trolls out there) so changing it will just result in a memory leak. If we have an address to the memory location storing the address, we can change it (double-pointer, or pointer-to-pointer).

Code:

void Stack_init(Stack *obj, size_t size)
{
     *obj = malloc(size); //this time, we wont error check, we assume the user is experienced
}

Yeah, pointless one-liner, I will make this cleaner later on (you will see)

Code:

void Stack_push(Stack *obj, void *data, size_t size)
{
     memcpy(*obj, data, size); //copy the data
     *obj += size; //update the stack pointer
}

And even that is pretty small. Why are the functions so much smaller?
Simple: it is a VERY basic type we are dealing with, and now we are hardly dealing with data at all.

Code:

void Stack_pop(Stack *obj, void *data, size_t size)
{
     *obj -= size; //update the sp first
     memcpy(data, *obj, size); //copy the data
}

And finally the most simple one:

Code:

void Stack_destroy(Stack obj)
{
     free(obj);
}

---

But the question I ask myself is WHY IS THIS EVEN A C FILE... It just doesn't have enough crap there for me... I would rather use macros:

Code:

#include <stdlib.h>
#include <string.h> //for memcpy
typedef void* Stack;
#define Stack_init(obj, size) obj = malloc(size)
#define Stack_push(obj, data, size); { memcpy(obj, data, size); obj += size; }
#define Stack_pop(obj, data, size); { obj -= size; memcpy(data, obj, size); }
#define Stack_destroy(obj) free(obj)

Now, we don't need to use double-pointers. If you notice, it is just a few things actually going on here. Some of our more advanced readers will probably be writing programs without these macros.

Code:

#include "Stack.h"
Stack s;
int a = 0x00112233;
char b, c, d, e;

int main()
{
     Stack_init(s, 4);
     Stack_push(s, &a, sizeof(int)); //lets assume 32-bit little-endian
     Stack_pop(s, &b, 1); //0x33
     Stack_pop(s, &c, 1); //0x22
     Stack_pop(s, &d, 1); //0x11
     Stack_pop(s, &e, 1); //0x0
     Stack_destroy(s);
     return 0;
}

Isn't that neat? For some this may be too basic, but for others a stepping ground.

[0xDEAD10CC]

You could also use macro's to easily create a defined stack type:

Code:

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

#define stack_t(T) T *
#define stack_init(T, len) malloc(len * sizeof(T))
#define stack_push(T, p, src) (memcpy(*p, src, sizeof(T)), ++(*p))
#define stack_pop(T, p) --(*p)
#define stack_free(p) free(p);

int main(void)
{
  int stack_size = 5;
  stack_t(int) stack_ptr = stack_init(int, stack_size);
  stack_t(int) p = stack_ptr;

  for (int n = 0; n < stack_size; ++n)
  {
    printf("push: %d\n", n);
    stack_push(int, &p, &n);
  }
  for (int n = 0; n < stack_size; ++n)
    printf("pop: %d\n", *stack_pop(int, &p));

  stack_free(stack_ptr);
}

It's just code however, so you're left to do all of the memory bounds checking on your own.

edit: What the heck is this? :S

Code:

#define Stack_push(obj, data, size); { memcpy(obj, data, size); obj += size; }
#define Stack_pop(obj, data, size); { obj -= size; memcpy(data, obj, size); }

These macros are the equivalent of a redundant statement ';' followed by a scope which calls the defined functions and mathematical operations.. The semi-colon there is useless and silly. Would you ever write code like this?

Code:

int main(void)
{
  ;
  {
    int x = 10;
  }
}

0.o

edit2: The other thing you can do is have a stack type pre-generated for you of a defined type through a few macros. Then you can generate whatever stack types you want, with the types you intend on using for the stack data.

[phyrrus9]

Very good response. For once it actually contains constructive additions. As far as the ;{ being there, I just used the semicolon to force it having one, and the braces are just for beginners.

[0xDEAD10CC]

The other thing you could do if you wanted actual stack types, is define whichever ones you want, using macros:

Code:

/*
* Author: 0xDEAD10CC
* Date:   2015-01-01 16:04:36
* Filename: main.c
* Last Modified time: 2015-01-03 09:37:35
*/

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

#define def_stack_t(T)  \
  struct stack_t_##T    \
  {                     \
    T *p_base;          \
    T *data;            \
  };

#define stack_t(T) struct stack_t_##T

def_stack_t(int)
def_stack_t(float)

int main(void)
{
   stack_t(int) *stack_obj = ...;
   // deal with stack object here
   free(stack_obj);
}

Now you can define generic stack functions that work with void *, or you can create an army of macros to do all of the calculations for the sizes for you too.

[phyrrus9]

The other thing you could do if you wanted actual stack types, is define whichever ones you want, using macros:

Code:

/*
* Author: 0xDEAD10CC
* Date:   2015-01-01 16:04:36
* Filename: main.c
* Last Modified time: 2015-01-03 09:37:35
*/

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

#define def_stack_t(T)  \
  struct stack_t_##T    \
  {                     \
    T *p_base;          \
    T *data;            \
  };

#define stack_t(T) struct stack_t_##T

def_stack_t(int)
def_stack_t(float)

int main(void)
{
   stack_t(int) *stack_obj = ...;
   // deal with stack object here
   free(stack_obj);
}

Now you can define generic stack functions that work with void *, or you can create an army of macros to do all of the calculations for the sizes for you too.

That is a way to do a "template" stack in C, but not a real stack. Since you are only able to put integers on that stack.

[0xDEAD10CC]

That is a way to do a "template" stack in C, but not a real stack. Since you are only able to put integers on that stack.

How is it not a real stack because it's limited to a single type? The templated std:tack type in C++ only supports a single type unless you create a container to wrap around embedded data of certain types to add to the stack so that it's recognized as a single type. The idea of a stack is typically LIFO, as to what goes on the pile, it doesn't matter. The only way yours works with multiple types above is because you're using void pointers, and because it's a pointer all of the same type, and not the actual data being added to some kind of stack container, you don't have to deal with padding and memory alignment issues, but you're still going to have to cast back to the original type in question.

[phyrrus9]

How is it not a real stack because it's limited to a single type? The templated std:tack type in C++ only supports a single type unless you create a container to wrap around embedded data of certain types to add to the stack so that it's recognized as a single type. The idea of a stack is LIFO, as to what goes on the pile, it doesn't matter.

*limited to a single size more or less.

Code:

PSH A
PSH D:X
PSH D
PSH X:SSR

system stacks don't give a fuck about what you're putting on there

[0xDEAD10CC]

*limited to a single size more or less.

Code:

PSH A
PSH D:X
PSH D
PSH X:SSR

system stacks don't give a fuck about what you're putting on there

Why would they? They recognize the data as bytes, pile on the bytes, it doesn't matter how many bytes you give. The POP instruction determines what to take off, so the PUSH is irrelevant here anyways. If you push a char onto the stack and try to pop off an int with a width of 4 bytes obviously that's not going to work though. And even if the bytes within your user-defined stack were abundant enough to pop off data and retrieve enough bytes for said datatype, you still have to somehow recognize that you push'd datatype x so you need to pop datatype x in order to keep the original data in tact, unless you want only a portion of the bits from the data that initially went in.

[phyrrus9]

Why would they? They recognize the data as bytes, pile on the bytes, it doesn't matter how many bytes you give. The POP instruction determines what to take off, so the PUSH is irrelevant here anyways.

Correct. That is how the stack in this thread works. It is intended to emulate as close as possible a system stack while still being beginner level.

[0xDEAD10CC]

Which is fair enough, but my main point here is that you can't define a stack based on this 'system stack' you're referring to. Let's look at an analogy, if I have a pile of papers on a desk does that not make it a stack because I didn't put an apple on top? No. The operation of that stack still works as normal, and you're probably going to be taking the last items off first, which were added to the stack itself.