Why won't [the sizeof sequence, "sizeof array / sizeof array[0]" for
instance] work on what the pointers are pointing to?
Because pointers lose information. The extra information attached
to an array object (besides its name, static-ness, etc.) is a *pair*
of things:
number-of-elements = N, element-type = T
(where N is an integer constant in C89, or the special value "unknown";
C99 adds a new wrinkle with Variable Length Arrays). The information
attached to a pointer object is just one item:
pointer-target-type = T
and The Rule that transforms an array object into a pointer value
discards the number-of-elements portion.
The sizeof operator is one of the few operators that does *not*
transform an array object into a pointer value. By suppressing
this transformation, it avoids losing the size information.
... Is the information lost when we create our array of pointers?
Yes.
There is another approach you can use -- instead of carrying the
sizes around in an auxiliary array, you can carry the locations
around in an auxiliary array.
To recap: you have (at the moment) a collection of one-dimensional
arrays whose elements are in turn one-dimensional arrays (of int,
I think). That is, you have an object like "table003" whose type
is "array N1 of (array N2 of int)", then one like table005, and
one like table013, and so on. Unfortunately, the element-types --
"array N2 of int" for table003 for instance -- change, because the
constant (N2) is different for table003 than for table041, whose
constant is different from that for table097, and so on.
The trick, as always, is to draw a picture, something like the
one that can be found at <
http://web.torek.net/torek/c/pa.html>.
In this case, however, the picture is much more complicated. We
have:
table003:
-----
| . |
-----
| . |
-----
| . |
-----
...
table041:
-------------
| . | . | . |
-------------
| . | . | . |
-------------
| . | . | . |
-------------
Because pointers must encode the size of the element to which
they point, a pointer to a "row" of table041 has to point to
a three-long-row (in the example above), while a pointer to a
"row" of table003 has to point to a one-long row (in the example
above). Thus, you cannot use a single pointer type to point to
both "rows of table003" and "rows of table041".
The trick discussed earlier is to point not to *rows* of each table,
but to the *very first int* in each table -- the box at (0,0).
Since C requires that array memory be "locally flat", and C compilers
that check for exceeding array subscript bounds are so rare that
few have ever even heard of one, we can then "cheat". Adding 1 to
a pointer pointing to table041[0][0] gets you to table041[0][1];
adding 1 again gets you to table041[0][2]; and adding 1 more is
*technically* undefined -- there is no table041[0][3] -- but on
all "real world" implementations it just wraps around to get to to
table041[1][0]. In table003, the wrap-around occurs right away,
because there is a table003[0][0] but no table003[0][1].
Instead of using this undefined behavior to achieve the desired
effect, though, you can throw more memory at the problem. (This
may actually slow it down.) Take the above drawing, with table003
and table041 as they are, and add some auxiliary tables:
aux_ptrs_for_003: table003:
------------- -----
| * | * | *-|-----> | . |
--|---|------ -----
| +-----------> | . |
| -----
+---------------> | . |
-----
...
aux_ptrs_for_041: table041:
------------- -------------
| * | * | *-|-----> | . | . | . |
--|---|------ -------------
| +-----------> | . | . | . |
| -------------
+---------------> | . | . | . |
-------------
Now each "aux_ptrs_for_nnn" array has type "array N of pointer to
int". (In the example above, N is always 3, but in practice it
will -- presumably -- vary. This will not matter because we are
about to eliminate the constant N, through that very same thing
that causes heartache with "sizeof".) Each "aux" array has its
various elements pointing to the [0][0], [1][0], and [2][0] element
of the corresponding "table". Just for illustration I will make
table003 only have two rows here:
int table003[2][1] = { ... };
int table041[3][3] = { ... };
int *aux_003[2] = { &table003[0][0], &table003[1][0] };
int *aux_041[3] = { &table041[0][0], &table041[1][0], &table041[2][0] };
Now we just need one last table, the "table of pointers that
points to the first of each aux pointer". For illustration
I will add aux_005 and aux_007 (not shown above):
#define N1 4 /* table[0] through table[3] */
int **table[N1] = { &aux_003[0], &aux_005[0], &aux_007[0], &aux_041[0] };
The picture here looks like this:
table: aux_007:
----------------- -------------
| * | * | * | * | +-> | * | * | * | (pointer arrows not shown)
--|---|---|---|-- | -------------
. | | | |
. | +---|----------+
. . |
v . | aux_042:
(aux_003). | -------------
v +--> | * | * | * |
(aux_005) -------------
Note that all of the "aux" arrays may be scattered around anywhere
in memory; all we demand is that there be a set of pointers to them,
all in a neat row, in the thing called "table". Each pointer --
each element of the table named "table" -- has type "pointer to
(pointer to int)", so that it points to the first of some unspecified
number of pointers. Each of those pointers has type "pointer to
int", so that it points to the first of some unspecified number
of "int"s.
If you look in table[0], you get the arrow pointing to aux_003[0].
If you follow that arrow -- as is the case for normal uses of the
value, including further subscripting -- you get the first element
of the array "aux_003", which is another pointer -- another arrow.
You can subscript by however many elements there really are in the
aux_003 array, to get the j'th pointer: table[0][j] is the j'th
pointer in the aux_003 array. Follow *that* arrow and you point
to table003[j][0], because we made aux_003[j] point to table003[j][0]
when we created the aux_003 array.
Thus, table
[j][k] is the i'th "aux" array, then its "j'th" element
(which points to the j'th row of a tableNNN), then that row's k'th
element.
Note that the table named "table" itself, and table, and
table[j], can all be dynamically allocated (by replacing the
array "table", of size N1, with a pointer to the same element type
that the table array had), if you prefer:
int ***table;
table = malloc(N1 * sizeof *table);
if (table == NULL) ...
/* now table, 0 <= i < N1, is valid */
table = malloc(N2 * sizeof *table);
if (table == NULL) ...
/* now table[j], 0 <= j <= N2; is valid */
table[j] = malloc(N3 * siezof *table[j]);
if (table[j] == NULL) ...
/* now table[j][k], 0 <= k < N3, is valid */
As before, there is no reason that N2 has to be the same for every
value of i, nor that N3 has to be the same for every pair (i,j).
If you draw a picture of this situation, it will look almost the
same as the one where "table" has type "int **[4]", except that
the four "int **" elements are now floating off in space somewhere
and "table" is just a pointer pointing to the first one, and the
"aux" name are gone -- they too are just floating off in space,
allocated by malloc:
table:
-----
| *-|--+
----- |
|
+-------------+
|
| ----------------- -------------
+->| * | * | * | * | +-> | * | * | * | (pointer arrows not shown)
--|---|---|---|-- | -------------
. | | | |
. | +---|----------+
. . |
v . |
. | -------------
v +--> | * | * | * |
-------------