gbadev.org forum archive

Hi,

I have a structure that is defined like this :

Code:

typedef struct {
int *tab[8];
int nb_elements;
} EX_STRUCT;

EX_STRUCT array[128];

And I would like to include in my ROM(in a .c file) the data from "array[128]", the problem is the "tab" inside each array elements can be of different size(the size is naturally "nb_elements").

example :
-- array[0].nb_elements = 4 so array[0].*tab[8] would be of the kind array[0].tab[4][8]
-- array[1].nb_elements = 7 so array[0].*tab[8] would be of the kind array[0].tab[7][8]

How can I include such data? Please this is really bugging me so if you do have an idea or even better, you've already done it, I would be glad to know how.

Cheers, Jeff.

I don't think there is any way to initialize it directly, but you can make the tab member of the struct an int** and declare the tab arrays outside the struct and then include that, like

Code:

typedef struct {
const int **tab;
int nb_elements;
} EX_STRUCT;

const int tabData1[8] = {0, 1, 2, 3, 4, 5, 6, 7};
const int tabData2[8] = {8, 9, 10, 11, 12, 13, 14, 15};

const int *tab[] = {tabData1, tabData2};

const EX_STRUCT array[1] =
{
{
tab, 2
},
};

_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku

You don't have to make it of type int**, if you know it will always be 8 pointers. (Speed, you know.) But it's true that you can't initialize like this:

Code:

typedef struct
{
int *tab[8];
int nb_elements;
} EX_STRUCT;

EX_STRUCT x =
{
{
{ 1, 2, 3 },
{ 4, 5, 6 },
...
},

3
};

The reason is that EX_STRUCT has to be of a specific size (flexible arrays in C99 notwithstanding), and so you can't have each instance of the struct be a different size. If each one holds 8 pointers and an int, then that's a well-defined size.

Now, if C supported array literals (in addition to array initializers), you would be able to do the above initialization, and the compiler would automatically create the array elsewhere and insert its pointer in the struct. As it is, you have to do it by hand:

Code:

int x_array1[] = { 1, 2, 3 };
int x_array2[] = { 4, 5, 6 };
...

EX_STRUCT x =
{
{
x_array1,
x_array2,
...
},

3
};

You might clean it up like this:

Code:

int x_arrays[8][3] =
{
{ 1, 2, 3 },
{ 4, 5, 6 },
...
};

EX_STRUCT x =
{
{
x_arrays[0],
x_arrays[1],
...
},

3
};

Look into flexible arrays for more options.

Do the following to get what you want:

Code:

typedef struct {
int length;
int elements[0];
} variable_int_array;

variable_int_array *make_array(int size) {
variable_int_array *p = malloc(sizeof(variable_int_array) + sizeof(int) * size);
p -> length = size;
return p;
}

Jeff
_________________
massung@gmail.com
http://www.retrobyte.org

Sajimori you are misunderstanding double pointers and arrays :

Quote:

You don't have to make it of type int**, if you know it will always be 8 pointers.

No it is (nb_elements) pointers, each one referencing a tab[8] array.

Besides an array of this kind :

Code:

int tab[8]

is not 8 pointers but only one.
You can access each item in an array by using its base adress, its rank and the type of data it contains.
If the adress of tab is 0x0000h; then the first element of the array is stocked at 0x0000h. The others will be stocked at :

Code:

tab[i] = *(0x0000 + i*sizeof(int)) = *(0x0000 + 4*i)

Dekuthree64 figured out what i meant, and believe me there are no difference in speed with int **tab and int *tab[8](maybe during compilation though...not sure).

Anyway thanks guys, I figured out now how it is done but I was hoping for a simpler way to do it cause it will obviously complicate the code this way.

Cheers, Jeff.

Quote:

No it is (nb_elements) pointers, each one referencing a tab[8] array.

If that was your intention then ok, but your original struct declaration specifies an array of 8 pointers.

Quote:

Besides an array of this kind :

Code:

int tab[8]

is not 8 pointers but only one.

Actually it's zero. An array is not a pointer.

Quote:

believe me there are no difference in speed with int **tab and int *tab[8]

There is an additional dereference per access with int**.

Code:

int** a; // *a yields a pointer to the start of the array
int *b[8]; // *b yields the start of the array itself.

Since arrays are not values in C, an expression can't really evaluate to an array (C only gives you a pointer to the start), but there is a difference interally. Check some assembler dumps to prove it to yourself.

Ah, the post body and subject line were a bit misleading to each other. Try the following:

Code:

int Data_0 [] = { 0, 1, 3, ... };
int Data_1 [] = { 7, 8, ... };

struct v_array {
int len;
int *elts;
};

#define V_ARRAY(p) { sizeof(p) / sizeof(int), p }

v_array data[] = {
V_ARRAY(Data_0),
V_ARRAY(Data_1),
};

Untested, but the idea should work just fine. Your compiler may not like using sizeof() at compile-time, in which case, just provide the length youself -- or as the first element in the array like so:

Code:

int Data_0 [] = { 3, 0, 1, 2 };
int Data_1 [] = { 4, 0, 1, 2, 3 };

#define V_ARRAY(p) { p[0], &p[1] }

Jeff
_________________
massung@gmail.com
http://www.retrobyte.org

sajiimori wrote:

Quote:

No it is (nb_elements) pointers, each one referencing a tab[8] array.

If that was your intention then ok, but your original struct declaration specifies an array of 8 pointers.

Well no, it was more of a int (*tab)[8] , if tab was of type int ** it would do :
tab = (int **)malloc(nb_elements *sizeof(int*));
for (i=0; i<nb_elements; i++)
tab[i] = (int *)malloc(8 * sizeof(int));
so it is not an array of 8 pointers.

sajiimori wrote:

Quote:

Besides an array of this kind :

Code:

int tab[8]

is not 8 pointers but only one.

Actually it's zero. An array is not a pointer.

lol. If an array is not a pointer for you, then you should seriously read some books on C or implement arrays in ASM.

sajiimori wrote:

Quote:

believe me there are no difference in speed with int **tab and int *tab[8]

There is an additional dereference per access with int**.

Code:

int** a; // *a yields a pointer to the start of the array
int *b[8]; // *b yields the start of the array itself.

Since arrays are not values in C, an expression can't really evaluate to an array (C only gives you a pointer to the start), but there is a difference interally. Check some assembler dumps to prove it to yourself.

I know what arrays are thanks :)
int **a and int *b[8] are the same conceptually, they need two inderections to determine the value of the variable that is stocked. But of course if an array is not a pointer for you...
Anyway it is getting a bit out of subject here.

Thanks Jma by the way ;)

Cheers, Jeff.

Ok, I'll try one more time despite your condescending tone. If you don't get it after this then I'm sure you'll survive just fine, since arrays act like pointers in C.

Compile this with -S:

Code:

int array[10];
int *pointer;
void g(int);
void f()
{
g(array[5]);
g(pointer[5]);
}

To save you the trouble, here are the relevant portions in x86:

Code:

pushl _array+20
call _g

Code:

movl _pointer, %eax
addl $20, %eax
pushl (%eax)
call _g

Accessing arrays via pointers takes an extra indirection.

jma wrote:

Do the following to get what you want:

Code:

typedef struct {
int length;
int elements[0];
} variable_int_array;

variable_int_array *make_array(int size) {
variable_int_array *p = malloc(sizeof(variable_int_array) + sizeof(int) * size);
p -> length = size;
return p;
}

Jeff

Is malloc really the answer to this question? I just think malloc has more to do with dynamic allocation than static arrays in memory. Also don't you need to cast malloc's returned pointer to the correct data type?

LOst? wrote:

Also don't you need to cast malloc's returned pointer to the correct data type?

In C++ you do, but C will automatically cast between (void *) and any other pointer type.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

I don't know if anybody has already suggested this....

Code:

template<unsigned int SIZE>
class someclass
{
public:
const unsigned int size(){return SIZE;}
int tab[SIZE];
};

someclass s<4> = {0,1,2,3};

should work fine (havent compiled it, not at home so I can't test it) might have to add more {}.

As for the following, please take this in good humor and don't get upset, if you do you prove that you don't get a simple joke...

IT IS 2004.... USE C++ FOR FUCKS SAKE, STOP TRYING TO SOLVE SIMPLE PROBLEMS WITH C'S LIMITED RESOURCES!!!
_________________
www.hungrydeveloper.com
Version 2.0 now up - guaranteed at least 100% more pleasing!

MumblyJoe wrote:

As for the following, please take this in good humor and don't get upset, if you do you prove that you don't get a simple joke...

IT IS 2004.... USE C++ FOR FUCKS SAKE, STOP TRYING TO SOLVE SIMPLE PROBLEMS WITH C'S LIMITED RESOURCES!!!

I don't understand... is it a joke because you're ignoring the inefficiency of C++ features or the banality of applying the OO paradigm to tasks that don't benefit from it?

Dan.

poslundc wrote:

MumblyJoe wrote:

As for the following, please take this in good humor and don't get upset, if you do you prove that you don't get a simple joke...

IT IS 2004.... USE C++ FOR FUCKS SAKE, STOP TRYING TO SOLVE SIMPLE PROBLEMS WITH C'S LIMITED RESOURCES!!!

I don't understand... is it a joke because you're ignoring the inefficiency of C++ features or the banality of applying the OO paradigm to tasks that don't benefit from it?

Dan.

Really poslundc, I have seen alot of very clever things posted by you in the past, you are a top notch coder in all respects, so please don't take offence to this... but template params are all COMPILE TIME related, it has nothing to do with efficiency, besides the fact that templates have nothing more to do with OOP than int's. If you want to take random offence and try the solve to eternal C vs. C++ war, I am more than happy to do it, start a new thread "MumblyJoe(C++) vs. poslundc(C)" and get get somebody to lock it so only you and me can post in it and it does not get confused.

Sorry if the above seems odd, I have been drinking and drooling over this picture http://is0.okcupid.com/graphics/us/danposluns.jpg :P
_________________
www.hungrydeveloper.com
Version 2.0 now up - guaranteed at least 100% more pleasing!

Your template doesn't solve this problem because you can't have an array of that class where each has a different template argument, and the original post contained this line:

Code:

EX_STRUCT array[128];

Then again, the problem was pretty unclear from the beginning so maybe the OP would accept that limitation.

But I have to agree that templates needn't add any inefficiencies at runtime. Yours certainly won't.

MumblyJoe wrote:

template params are all COMPILE TIME related, it has nothing to do with efficiency

Templates tend to bloat code size, and increase compile times. The (relatively simple) code in my workplace is excessively templated, and it takes the better part of two hours to do a full recompile and we get absurdly huge object files. There is more to efficiency than simply how fast your code runs, especially on a platform like the GBA where multiboot programs must fit into 256KB.

In the specific case of your templated array class: there will probably not be observable code bloat in the general, limited-use case (you are looking at just creator, destructor and copy methods I suppose), and it will therefore probably serve as a more than adequate solution. But this is far from a ringing endorsement of the blind use of C++ features on a limited platform such as the GBA that you made earlier.

Quote:

Sorry if the above seems odd, I have been drinking and drooling over this picture http://is0.okcupid.com/graphics/us/danposluns.jpg :P

I am the sexiest thing to hit the Internet since Graga. (additional proof)

Dan.

sajiimori wrote:

Your template doesn't solve this problem because you can't have an array of that class where each has a different template argument, and the original post contained this line:

Code:

EX_STRUCT array[128];

Then again, the problem was pretty unclear from the beginning so maybe the OP would accept that limitation.

But I have to agree that templates needn't add any inefficiencies at runtime. Yours certainly won't.

Good point sajiimori. My template doesn't solve the entire problem.

Although... lets imagine the options we have here. imagine this:

Code:

template<unsigned int SIZE>
class someclass;

note that this class cannot be instantiated ever. If we then specialise this class as such:

Code:

template<>
class someclass<1>
{};

We can then only make someclass<1>, any other number as the template param will fail at compile time (the best time to fail).

Now while this also doesn't solve the problem, imagine we have classes for different types of backgrounds and sizes (I will post my library code later) that has specialised classes as above, then a lot of classes that use these. Imagine we have template container classes that construct encapsulated templated classes that use the params of the surrounding class. We have a type safe and compile-time error reporting system for many situations!

Sorry, I know this isn't the point of this thread, just saying it is a road to follow towards a solution for this error.
_________________
www.hungrydeveloper.com
Version 2.0 now up - guaranteed at least 100% more pleasing!

Sorry to dan, seems he does have a sense of humor :P And another sorry for linking to that picture :P
_________________
www.hungrydeveloper.com
Version 2.0 now up - guaranteed at least 100% more pleasing!

There is one key phrase in your post, Dan:

Quote:

...blind use of C++ features...

The blind use of any feature of any language on any platform is a bad idea.

What's wrong with this statement?: "Non-const C arrays are inefficient because if you blindly create a 40KB one on GBA you'll run out of IWRAM."

1) The programmer has to know how arrays work.

2) The programmer has to know the difference between non-const and const data in C.

3) The programmer has to know the limitations of his platform.

Are any of these things the fault of the language or the feature?

sajiimori wrote:

There is one key phrase in your post, Dan:

Quote:

...blind use of C++ features...

The blind use of any feature of any language on any platform is a bad idea.

You're absolutely right, and the danger is certainly measurable in plain C as well (#include anyone?).

But I am of the opinion that the C++ extensions to the C language were designed with an ideology and philosophy that are not often consistent with the objectives of embedded system programming. The remark was intended more as cautionary against the blind adoption of that philosophy - specifically, things like heavy abstraction and OOP - versus the philosophy of C, which I believe strives to keep things relatively low-level and procedural.

Yes, you can produce C++ code that is just as efficient as C code on an embedded platform if you know how. But not without straddling the two different ideologies. So, do it if you so choose, but not blindly.

Dan.

The following code is very high level and abstract:

Code:

int main()
{
init_engine();
start_main_menu();
while(1)
game_tick();
}

Ok now it is totally out of subject...

PS : Dan, everybody must admit that you are a the most sexiest model seen on the net ;)

sajiimori wrote:

The following code is very high level and abstract:

Code:

int main()
{
init_engine();
start_main_menu();
while(1)
game_tick();
}

... but it is strictly procedural and doesn't give a damn about encapsulation. ;)

Dan.

It is very well encapsulated. main() knows nothing about the engine components that need initialization, or the current game state that needs to be updated.

I'm not sure what alternative to "procedural" you're thinking about. The alternatives that come to mind are "strict functional", "lazy functional", and "nondeterministic". C++ is not well-suited to any of those styles.

Or do you consider object orientation to be at odds with proceduralism? I certainly don't. C++ methods are just like regular C functions except the first argument is implicit, and it's passed by putting it on the left of the function name rather than inside the parentheses. Virtual functions are just like const function pointers except they save space by sharing tables of them between instances of the same class.

sajiimori wrote:

It is very well encapsulated. main() knows nothing about the engine components that need initialization, or the current game state that needs to be updated.

You're right that main is insulated from its children, but its children clearly are not going to be insulated from each other and will be sharing common memory, potentially in an unprotected way.

Quote:

Or do you consider object orientation to be at odds with proceduralism? I certainly don't. C++ methods are just like regular C functions except the first argument is implicit, and it's passed by putting it on the left of the function name rather than inside the parentheses. Virtual functions are just like const function pointers except they save space by sharing tables of them between instances of the same class.

Strictly speaking, OO is procedural, but it follows a different paradigm than "traditional" procedural (or just non-OO, if you prefer) programming. It encourages the programmer to focus on the state of objects and their interactions rather than the flow of code.

Dan.

To backup Saji, arrays are techincally not pointers, although their name does represent a memory address. An array is more than a pointer, it also includes inplied information about the size of lower dimensions in the array. For 1D arrays, no big difference (add and deref) - for 2+D arrays, big difference. If you ever try telling a compiler that a memory location you created is a 2D array, you'll get a better feel for this. Also, **ptr does indeed cause 2 dereferences while ptr[0][0] is only 1 and an add( and a mul if needed.) Minor difference, but when speed matter, it's important (of course when speed matters, why in Gods name are you using double dereferences anyways?) BTW, ptr[0][0][0] still is only 1 deref.

Miked0801 wrote:

If you ever try telling a compiler that a memory location you created is a 2D array, you'll get a better feel for this.

This code demonstrates how to declare a pointer to a 2-D array:

Code:

void
foo()
{
int (*p)[10][10];
int i, j;

p = malloc(100);
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
(*p)[i][j] = i * j;
}

Works fine. In fact, you can declare:

Code:

int (*p)[][10];

If you don't want to tell the compiler how many rows there are.

Quote:

Also, **ptr does indeed cause 2 dereferences while ptr[0][0] is only 1 and an add( and a mul if needed.) Minor difference, but when speed matter, it's important (of course when speed matters, why in Gods name are you using double dereferences anyways?) BTW, ptr[0][0][0] still is only 1 deref.

You're right about pointers to pointers being multiple accesses, but what I've shown above is pretty much the same as an array access. Consider the following code:

Code:

extern int (*ptr)[10][10];

extern int arr[10][10];

void
fill_ptr()
{
int (*tp)[10][10] = ptr;
int i, j;

for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
(*tp)[i][j] = 0;
}

void
fill_arr()
{
int i, j;

for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
arr[i][j] = 0;
}

It's basically filling each table (one through a pointer and one as an array). Look at the ARM code:

Code:

The main loop is identical, but the fill_ptr function has one extra load at the start. A local variable, tp, was used so the compiler didn't think ptr could change through each iteration of the loop (and thus incur an extra load each time).

What this comes down to is that, for random accesses, pointers to tables incur a single extra instruction (regardless of dimension), but in loops a smart compiler will optimize the difference out.

This generated code isn't GCC, by the way. I don't have GCC with me right now, so I can't tell if GCC optimiser works the same way. The pointer syntax is ANSI C (K&R too).

Happy coding.

Marciano.

Marciano wrote:

Code:

p = malloc(100);

Make that: malloc(100 * sizeof(int))

:-)

gbadev.org forum archive

Coding > Including different size arrays in a structure

#25945 - funkeejeffou - Wed Sep 01, 2004 6:15 pm

#25947 - DekuTree64 - Wed Sep 01, 2004 6:41 pm

#25948 - sajiimori - Wed Sep 01, 2004 7:13 pm

#25951 - jma - Wed Sep 01, 2004 7:40 pm

#25952 - funkeejeffou - Wed Sep 01, 2004 8:23 pm

#25962 - sajiimori - Wed Sep 01, 2004 10:43 pm

#25966 - jma - Wed Sep 01, 2004 11:23 pm

#25967 - funkeejeffou - Thu Sep 02, 2004 12:02 am

#25969 - sajiimori - Thu Sep 02, 2004 12:24 am

#25974 - LOst? - Thu Sep 02, 2004 4:54 am

#25981 - tepples - Thu Sep 02, 2004 2:45 pm

#25983 - MumblyJoe - Thu Sep 02, 2004 4:50 pm

#25988 - poslundc - Thu Sep 02, 2004 5:07 pm

#25989 - MumblyJoe - Thu Sep 02, 2004 5:34 pm

#25990 - sajiimori - Thu Sep 02, 2004 6:08 pm

#25991 - poslundc - Thu Sep 02, 2004 6:29 pm

#25992 - MumblyJoe - Thu Sep 02, 2004 6:39 pm

#25993 - MumblyJoe - Thu Sep 02, 2004 6:44 pm

#25994 - sajiimori - Thu Sep 02, 2004 6:48 pm

#25995 - poslundc - Thu Sep 02, 2004 7:10 pm

#25997 - sajiimori - Thu Sep 02, 2004 7:53 pm

#25998 - funkeejeffou - Thu Sep 02, 2004 8:02 pm

#25999 - poslundc - Thu Sep 02, 2004 8:40 pm

#26003 - sajiimori - Thu Sep 02, 2004 11:10 pm

#26004 - poslundc - Fri Sep 03, 2004 12:57 am

#26005 - Miked0801 - Fri Sep 03, 2004 1:13 am

#26008 - Marciano - Fri Sep 03, 2004 2:05 am

#26022 - Marciano - Fri Sep 03, 2004 11:42 pm