Hello
I'm trying to train how to program in a limited memory environment.
I was given an exercice to program a queue and "all storage" is done in a char array.
Can we save pointers and structs into a char array?
How is this done?
Hello
I'm trying to train how to program in a limited memory environment.
I was given an exercice to program a queue and "all storage" is done in a char array.
Can we save pointers and structs into a char array?
How is this done?
Old versions of malloc just returned char *. So yes, you can just get a memory address and assign it to whatever you want, assuming whatever it points to has enough space for what you are trying to put there.
Quzah.
Hope is the first step on the road to disappointment.
But how do you code it?
Something like:
If this is the right way to do it how would I save the next node? Like this?Code:typedef struct node_{ int valueA; int valueB; } Node; char memory[1024]; int main (void){ Node first; first.valueA = 1; first.valueB = 2; memory[0]=first; }
Code:Node second; second.valueA = 3; second.valueB = 4; memory[sizeof(node)] = second;
It is the other way around. Pointers into the memory array are given out and the memory is used through those pointers.
Code:#include <stdio.h> static char memory[1024]; static int current = 0; int main() { int* p = (int*)&memory[current]; int* q = (int*)&memory[current += sizeof(int)]; int* r = (int*)&memory[current += sizeof(int)]; *p = 11; *q = 22; *r = 33; printf("%d\n%d\n%d\n", *p, *q, *r); printf("%d\n%d\n%d\n", *(int*)&memory[0], *(int*)&memory[sizeof(int)], *(int*)&memory[2 * sizeof(int)]); }
How would you do it?Way too much risk of error in doing it this way...
Well, frankly I wouldn't. If the entire buffer is filled with node structs, making it anything but an array of structs is outright silly.
If the contents of the queue are mixed, ints, doubles, strings etc. things get a whole lot more complex real fast, now you have to write markers into the buffer denoting the type of data and a link to the next marker... sort of like a linked list using character offsets into the buffer instead of pointers (like you would do for a disk file). But, if the memory environment is that limited and the amount of data is only around 1k, it's likely they'll eat up more space coding the solution than they'll save by the memory buffer technique.Code:typedef struct node_{ int valueA; int valueB; } Node; // in main Node *Items=malloc(100 * sizeof(node); // to put stuff in Items[x].valueA = 42; // to get stuff out x = Items[x].valueA;
The OP does not have that option. malloc() is also not an option. The exercise is to simulate malloc with an array of char. Good idea or not, that is a restriction that can not be thrown out. How would you do it if you had no choice?Well, frankly I wouldn't. If the entire buffer is filled with node structs, making it anything but an array of structs is outright silly.
it's to store several fifo queues, optimizing memory and speed.
And thanks for the code, it really helped!
yup, integers
If it's all integers... make that 1024 bytes of memory an array of integers...
Depending on your system that will give you either 256 or 512 array elements to work with...Code:int cells = 1024 / sizeof(int)); int memory[cells];
Access is simple...
No need to mess with pointers.Code:memory[x] = 12; y = memory[x];
To maintain it as a fifo structure you have two options. In the simplest case you always fetch memory[0] and move everything else over...
A more high performance system would treat the array as a circle, keeping track of a head and a tail pointer...Code:// track used cells int used; // extract data x = memory[0]; // fetch data // rotate array for (y = 0; y < used; y++) memory[y] = memory[y+1]; used--; // point to next cell // to inject data if (used < (cells-1)) memory[used++] = x;
(this is for concept, the actual code would need logic to prevent head and tail from passing one another.)
As I say in this last case additional logic will be needed to prevent tail from getting ahead of head as this would mean a buffer overflow has occured.Code:int head = 0; // data goes in here int tail = 0; // data comes out here //inject data memory[head] = x; head = head++ % cells; // remove data x = memory[tail] tail = tail++ % cells;
Last edited by CommonTater; 06-02-2011 at 11:52 AM.
When I posted the question I was just interested in how to store de structs do the char array because the problem is to store several queues into this array.
The array type is unsigned char, actually. I didn't thought it mattered but know I'm not so sure. Is the code from post #2 still valid?
I said it was integers because I was being passed values like 1 and 2. Now I notice it's to store also unsigned char.
Your code gave me a really good idea though.
I'm just gonna use one part of the array to store where the queues end. Then I'll just shift the values as they are pushed and poped. It's not very efficient but I was playing around with structs with pointers and they take up a LOT of space, it's insane! I can store 10 times more objects using this method instead of pointers.
Last edited by kotoko; 06-02-2011 at 06:32 PM.
The idea was to give you ideas... so, there you go.
FWIW... a struct of two integers should take up no more space than two integers. The trick is to not be creating a bazillion pointers, just learn how to manipulate one pointer for your task; sort of like seeking in a disk file. You can also experiment with typecasting to see if you can shoehorn a struct into your char array, something like (node*)ptr = nodedata; or similar...
Last edited by CommonTater; 06-02-2011 at 06:51 PM.