[C] Type Ambiguous Stack 12-31-2014, 09:05 AM
#1
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.
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.
But why even bother? Why not just use void *'s directly? Well, just for now we will use the typedef, for simplicity.
Stack.h:
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).
Yeah, pointless one-liner, I will make this cleaner later on (you will see)
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.
And finally the most simple one:
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:
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.
Isn't that neat? For some this may be too basic, but for others a stepping ground.
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.