Arrays and Pointers
aai[2][4] is stored in memory as:-
aai[0][0]aai[0][1]aai[1][0]aai[1][1]aai[2][0]aai[2][1]
aai[3][0]aai[3][]aai[1]
*aai is of type int[]. Note that:-
aai[1][2] == *( (aai[1])+2) == *(*(aai+1)+2)
*aai can be used as a pointer:-
"In a value context, an object of type `array N of T' (for any
constant N and any suitable type T) turns into a value of type
`pointer to T', whose value is the address of the first (0'th)
element of the array."
so *aai is of type `array 4 of int'; it *becomes* `pointer to int' because it
is used where a value is needed.
But *aai is not equivalent to a pointer. For example, you can't change
its value. This distinction can easily and dangerously be blurred in
multi-file situations illustrated in the following example. Given
extern int *foo;
foo is a variable of type pointer-to-int with external linkage.
Foo's type is complete, (sizeof foo) is allowed. You can assign to foo:
foo = NULL;
and it is possible that
(foo == NULL)
might be true. But given
extern int baz[];
baz is a variable of type array-UNKNOWN-of-int with external linkage.
This is an "incomplete" type, you can't take (sizeof baz).
You cannot assign to baz, and although "baz" will decay into a pointer
in most contexts, it is not possible for
(baz == NULL)
ever to be true.
The compiler will allow you to mix the array/pointer notation and will get
it right, but it needs to know what the reality is. Once you declare the
array/pointer correctly, you can then access it either way.
Arrays/pointers are equivalent (with respect to referencing data) for just
about all cases EXCEPT for global variables and sizeof().
The reason that they are equivalent for function calls is that the array is
acually converted to (and passed as) a pointer.
***********************
* BY Steve Summit *
* scs@adam.mit.edu *
***********************
I hope there aren't too many people who still believe that
dynamic allocation is too exotic for general use, and that
fixed-size arrays are therefore a viable alternative. Someone
said that all you have to do is pick the largest size you can
think of and then multiply it by 10. That fails for two reasons:
1. The largest size you can think of today, that no one
would ever use, will be in widespread use tomorrow.
2. Orders of magnitude are big, even with virtual memory.
Doggedly sticking to fixed-size arrays, which have tens
of thousands of elements in hopes that they will always
be big enough, can waste prodigious quantities of memory,
especially if most invocations require only a few
elements. (Remember that address spaces, though large,
are not infinite, particularly on the all-too-popular
80*86, and that swap space isn't infinite, either.
Start-up time matters, too.)
Most of the time, writing code which dynamically allocates the
array space it needs is not very difficult. Suppose we have a
simple array, and a subroutine for adding items to it:
#define MAXELTS 100
int array[MAXELTS];
int nelts = 0;
install(x)
int x;
{
if(nelts >= MAXELTS)
{
fprintf(stderr, "too many elements (max %d)\n", MAXELTS);
exit(1);
}
array[nelts++] = x;
}
Let's see how easy it is to remove the arbitrary limitation in
this code, by dynamically allocating the array:
#include <stdlib.h>
int *array = NULL;
int nalloc = 0;
int nelts = 0;
install(x)
int x;
{
if(nelts >= nalloc)
{
nalloc += 10;
array = (int *)realloc((char *)array, nalloc * sizeof(int));
if(array == NULL)
{
fprintf(stderr, "out of memory with %d elements\n",
nelts);
exit(1);
}
}
array[nelts++] = x;
}
Be sure that realloc is declared correctly. If you don't have
<stdlib.h> yet, use extern char *realloc(); . If you want to be
true-blue ANSI, use size_t for nalloc and nelts. (Note, too,
the format of the error messages: it's nice to mention what the
limit is when a fixed limit is exceeded, and how much fit before
memory ran out when dynamic allocation is used.)
The transformation from fixed-size to dynamically-allocated is
simple: just change the array to a pointer, and add another
variable keeping track of how many slots have been allocated.
(If you always allocate the array just as big as it needs to be
at any given time, without any +10 slop, you don't even need the
extra variable. I'll talk more about overallocation in a
minute.) Wherever elements are added to the array, replace the
check against the fixed array size with code which checks the
dynamic size and reallocates a larger array if necessary.
Notice, if you haven't already, the self-starting nature of the
realloc code, and the use it makes of an apparent wart in the
specification of realloc: when realloc's first argument is NULL,
it essentially acts like malloc. Therefore we don't need a
clumsy special case like
if(array == NULL)
array = (int *)malloc(nalloc * sizeof(int));
else array = (int *)realloc((char *)array, nalloc * sizeof(int));
to handle the initial allocation. (Note that this wrinkle in
realloc has only become official with the ANSI C standard.
Under some pre-ANSI compilers, the special case and initial
explicit malloc were typically required.)
With one exception, no appearances of the global array (which is
now actually a pointer) in the rest of the code have to be
changed, because pointers can be subscripted the same as arrays
(more properly, all arrays are subscripted as pointers). I'll
get to the exception in a minute.
Suppose you have some code with a fixed-size array, which you
wish to modify via the above transformation. Here are two little
difficulties you might encounter:
1. The code didn't check for array overflow, making it
harder to replace those checks with the realloc code.
That's too bad, but the code needed fixing, at least to add those
checks, anyway. Fixed-size arrays are acceptable only if
overflow is checked for while filling them. Otherwise, they're
time bombs.
2. Insertions into the array are scattered all through the
code, rather than being centralized in one "insert" or
"add" subroutine as in the example above. I don't feel
like duplicating the realloc code all over the place.
Again, that's too bad, but it shouldn't be too difficult to
define the subroutine, do the reallocation there, and replace the
scattered explicit insertions with calls to the new routine.
It's easy to find all of the places in the code which might need
adjusting. Just grep for the name of the array and the name of
the counter variable (nelts in this example).
One thing to beware of when using realloc is that the array can
(and usually will) move around in memory, invalidating any other
pointers to elements within it. (This is the "one exception" I
alluded to above.) For example, if you had something like
(continuing from the code above)
int *special;
install(12);
install(34);
install(56);
special = &array[nelts - 1];
install(78);
the "special" pointer is not necessarily pointing to the third
element any more, after the fourth call to install.
Whenever there are pointers into an array or buffer, those
pointers must be relocated if the array or buffer is ever
reallocated. The easiest way is with offsets:
int offset_special = special - array;
array = (int *)realloc((char *)array, nalloc * sizeof(int));
if(array == NULL)
...
special = array + offset_special;
(Assuming you're using ANSI C a better type for the
offset_special variable would be size_t.)
If your code is nice and modular, you may find it uncomfortable
to adjust some pointers, which are dealt with and really belong
exclusively in some other part of the code, in the central
reallocation routine. In this case, why not keep them as indices
(or, if you prefer the term, offsets, i.e. just like the
temporary offset_special computed above) rather than pointers?
(The answer from the four winds will be "because pointers are
more efficient than indexed subscripting," but wait a minute.
For one thing, under some architectures, that's not true, and in
any case the special pointers which are kept into an array which
is still growing are typically not the scan-over-the-whole-array-
in-a-big-hurry pointers that need optimizing in the first place.)
Finally, we come to the topic of the incremental growth strategy,
which several people were flaming about earlier. My code
typically uses the kindergarten-style arithmetic iteration
illustrated in the example above:
if(nelts >= nalloc)
{
nalloc += 10;
...
If I am adding several elements at once, the code is slightly
different:
if(nelts + nnew > nalloc)
{
nalloc = nnew + 10;
...
or maybe
if(nelts + nnew > nalloc)
{
nalloc += 10;
if(nelts + nnew > nalloc)
nalloc = nelts + nnew;
...
Many people will tell you that all of thest are O(n**2) and
therefore too inefficient. They will say that you should use
nalloc *= 2 instead.
It's true that adding some number (rather than multiplying by
some number, i.e. an arithmetic rather than geometric
progression) is O(n**2). I can say, though, that I've never
found the arithmetic progression to be a problem, perhaps because
n is "always" small, or (more likely) because 65536/10 (or the
equivalent for a given memory size and slop factor) is never very
many iterations. (Often the I/O involved filling the array, or
other manipulations upon the data, swamp the allocation time
anyway.)
But why avoid geometric progression? One problem is that
nalloc *= 2;
won't work; it's not self-starting. You need something like
if(nalloc == 0)
nalloc = 10;
else nalloc *= 2;
(which is ugly, and we're back to a first-time-through special
case), or
nalloc = nalloc * 2 + 10;
which is probably a little better (although it's still weird-
enough looking that it may deserve a comment explaining it).
The bigger problem is that geometric progressions can seem to run
out of memory far too soon, especially if you don't have virtual
memory. If you've got, say, 40K available, and nalloc has grown
to the point where you're using 32K, and you need one element
more, doubling nalloc will cause you to ask for 64K, which you
won't get. So you have to put in a back-off strategy:
int oldnalloc = nalloc;
int *newarray;
nalloc = nalloc * 2 + 10;
newarray = (int *)realloc((char *)array, nalloc * sizeof(int));
if(newarray == NULL)
{
nalloc = oldnalloc + 10;
newarray = (int *)realloc((char *)array,
nalloc * sizeof(int));
if(newarray == NULL)
{
fprintf(stderr, "out of memory with %d elements\n",
nelts);
exit(1);
}
}
array = newarray;
...
Suddenly things have gotten pretty complicated, with messy-
looking extra tests and temporary variables, all of which have to
be thought about carefully, and documented. There are several
things one could do to "improve" this last algorithm, such as
trying to keep it from being strictly arithmetic after the
geometric progression overflows, but any such "improvements"
would be further complications, and I'll not digress.
(Note, too, that any back-off strategy requires that the first,
failing realloc not corrupt the old block. As has been mentioned
here already, ANSI X3.159 guarantees that realloc fails
gracefully, while many earlier systems did not. Indeed, I find
the line "When realloc returns 0, the block pointed to by ptr may
be destroyed" in the BUGS section of my old V7 manual, the
current 4.3 manual, and the Tenth Edition Research System manuals
I just found in a bookstore yesterday. This sounds to me like an
egregious, unacceptable failure mode. Presumably it's still
around because it's hard to fix. Can someone explain why it's
impossible for these old allocators to guarantee that a block
won't be corrupted during an unsuccessful enlargement attempt?)
To summarize: dynamic allocation of arrays is easy, except for
badly-written programs which need fixing anyway. Unless you're
writing really vigorous production code, where you know that n
will always be large, consider using a simple arithmetic
progression. (If a back-off strategy is too hard to get right,
I'd rather that the code perform slowly for huge n than that it
fail with half of its available memory still unused.)
----------------------------------------------------------------------
*******************************
* By - Chin Fang *
* fangchin@portia.stanford.edu *
*******************************
(A) Problem
(B) Illustrations
(C) Pseudo Code Segments
(A) Problem:
Given a 2D mxn matrix m shown in Fig.1:
where m is number of rows, n is number of columns.
_ _
|XXXX......XX|
|XXXX..... XX|
m := |XXXX........| n
|X...........|
|............|
|_.........._|
m
Fig.1
Two standard methods (1) simulating the given matrix using 1D C array,
(2) simulating the given matrix using array of ptrs.
(B) Illustrations:
Method (1)
(a) column-major storage (w.r.t. the matrix of course):
n elms n elms n elms n elms
ptr-> ------- . -------- . -------- . . . . . . . --------
col 1 col 2 col 3 col m
or
(b) row-major storage (same as above):
m elms m elms m elms m elms
ptr-> ------- . -------- . -------- . . . . . . . --------
row 1 row 2 row 3 row n
Which one is better depends on the computational algorithm(s) to be employed.
Experienced C programmers like the above scheme. No ptr-jumping at all during
computations if employed algorithm(s) match the storage scheme ((a) or (b)).
(as is obvious that ptr can increment continuously)
Elements are accessed thru the simplest ptr arithmetric, eg.
in (a), *ptr is the first element of the first column, *(ptr+n) is the first
element of the 2nd column (assuming zero ptr offset).
This scheme is most natural to C's array concept.
It has the additional advantage of being efficient in memory usuage.
Particularly when band, symmetric matrices are being stored; then h is half of
the bandwidth of the matrix, m is the total number of columns for (a),
diagonal terms are stored as well. (refer to (C) for def of h)
Only inconvenience could be more involved index arithmetric for certain
algorithms and non-symmetric matrices.
Similar schemes are popular among FORTRAN programmers, eg. for storing
stiffness matrices in Finite Element Analysis codes.
Method (2)
(a) column-major storage:
ptr1-> ------------------. col 1
ptr2-> ------------------. col 2
. . . . . .
. . . . . .
. . . . . .
ptrm-> ------------------. col m
(b) row-major storage:
ptr1-> ------------------. row 1
ptr2-> ------------------. row 2
. . . . . .
. . . . . .
. . . . . .
ptrn-> ------------------. row n
Both (a) and (b) above are a compromise between the C's array concept and
the typical 2d matrix notion. If employed algorithms match the storage
pattern, only moderate ptr jumping would occur during calculations. (typically
at the end of each column/row traversal, eg. in (a), ptr1, at the end of col 1
has to "jump" back to the address of ptr2 in the memory block allocated to the
array of ptrs.)
Normally convenient for small, dense matrices. Need additional ptr offsets to
store band matrices. Even more so if ragged arrays are to be stored. (pre-
scanning of external matrix element distribution pattern maybe necessary)
Relevant pseudo code segments for Method (1)&(2) are given below:
Note:
(1) malloc(3C) is not used directly. A free block cache fb_cache is assumed
to have been setup in the highest calling hierachy, and the private memory
allocation routine memory_alloc() is assumed to be visible to
Matrix_alloc(). This will reduce the overhead caused by too many malloc()
free() calls and potential memory leakage problems. (if a programmer is
not careful)
(2) matrices are always wrapped in a warpper function (see the two typedefs
below), advantages include (a) bounds checking is made easy
(b) run time size info of a particular matrix
is always available.
(c) as a consequence of (b), fast column/row
extractions, matrix data transfers, can
be efficiently accomplished thru memcpy(3C)
memmove(3C) instead of using nested loops.
(C) Pseudo Code Segments:
Method (1)
Using 1D C array simulating a 2D matrix:
#typedef struct{int h,n; DATA *mm} * Matrix;
/* extra ints should be incorporated if additional info is required later */
Matrix Matrix_alloc(int h, int m)
{
Matrix tmp;
tmp->h=h;
tmp->n=n;
tmp->mm=(DATA *)memory_alloc(fb_cache, h*m*sizeof(DATA));
/* fb_cache is a free block cache of data type DATA, if desired. */
/* In this implementation, it is implicitly assumed to be global */
/* w.r.t function Matrix_alloc */
assert(tmp->mm);
return tmp;
}
Method (2)
Using array of pointer to DATA simulating a 2D matrix:
#typedef struct {int nrl, nrh, ncl, nch;
DATA **mm} * Matrix;
Matrix Matrix_alloc(int nrl, int nrh, int ncl, int nch)
{
int i;
Matrix tmp;
DATA **mm;
if(nrl > nrh || ncl > nch) errormsg("bounds are wrong in allocation!");
tmp->nrl=nrl;
tmp->nrh=nrh;
tmp->ncl=ncl;
tmp->nch=nch;
mm=(DATA **)memory_alloc(fb_cache, (nrh-nrl+1)*sizeof(DATA *));
/* see comments above for Method (1) */
assert(mm);
mm-=ncl;
for(i=ncl;i<=nch;i++){
mm[i]=(DATA *)memory_alloc((nrh-nrl+1)*sizeof(DATA));
assert(mm[i]);
mm[i]-=nrl;
}
tmp->mm=mm;
return tmp;
}
#ifdef MATRIX_DEBUG
DATA bound_checked_access(Matrix MM,int row, int col)
{
int WRONG=FALSE;
if(row <MM->nrl||row >MM->nrh||col <MM->ncl||col >MM->nch) WRONG = TRUE;
if(WRONG) errormsg("input bounds wrong in matrix access!");
return MM->DATA[row][col];
}
#endif
#ifdef MATRIX_DEBUG
DATA bound_checked_access(Matrix, int, int);
#define M(MM,row,col) bound_checked_access(MM,row,col)
#else
#define M(MM,row,col) MM->DATA[row][col]
#endif
----------------------------------------------------------------------------
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 405 2750)
In value contexts, any array, when referred to by name only without subscripts,
translates into a pointer to the lowest element of the array.
If you have
float spam[M][N]; /* for some constants M and N */
the type of the object `spam' is `array M of array N of float'.
In a value context, this becomes a pointer to the first element of `the'
array, but which array?---we have two `array of's above.
The answer is that it becomes a `pointer to array N of float'. This
value is not an <object, array N of T> and therefore does NOT undergo
a second conversion. The result is a pointer to first of the sub-arrays
that make up the array `spam'. This is
float (*p)[N] = spam;
The result of `indexing' (which is in C a sham: e1[e2] does not really
`index' e1 `by' e2; instead, it adds e1 and e2 and indirects through
the result) a `pointer to T' is, if not an error, an object (lvalue) of
type T. If each pointer points to one or more `int's, then ptr[value]
is a single int (or an error).
In this case, p points to one or more---in fact, it points to exactly M
---`array N of float's, so p[value] is an object of type `array N of
float'. Since this *is* an array object, it goes through another of
those `array to pointer' conversions whenever it appears in a value
context, so p[v1][v2] is entirely legal and means to take the v1'th
`array N of float' at which p currently points, turn that object into
the address of the first of the N floats in that array, then take the
v2'th float at which the resulting pointer points:
0 1 2 ... N-1
+---+ +------------------+
| p |---------->| array N of float | p[0]
+---+ +------------------+
| array N of float | p[1]
+------------------+
| . |
| . | ...
| . |
+------------------+
| array N of float | p[M-1]
+------------------+
`p' points directly *to* one `array N of float' (p[0]), but p points
*at* a whole passel of `array N of float's (p[0] through p[M-1]). An
`array N of float' is slippery, though, and when you try to grab the
whole thing with p[0]:
+---+ +------------------+
| p |---------->| array N of float | p[0]
+---+ +------------------+
you have to loosen your hold and you end up with a pointer to the first
one:
$ p[0] in value context
|
v
+---+ +---+---+...+---+--+
| p |---------->| array N of float | p[0]
+---+ +------------------+
`$' is an intermediate value and is not (necessarily) actually stored
in memory anywhere in the computer (hence no box). It points to a
single float (here p[0][0]) but it points `at' N floats (p[0][0]
through p[0][N-1]). This means you can fetch `$[0]' (so to speak) to
get p[0][0], or `$[4]' to get p[0][4], and so on. Of course `$' is not
a legal character in C, except inside string and character constants
and comments.
(In the picture above, p points *to* the entire `array N of float', but
`$'---p[0] taken as a value---points *to* only one float, hence the
extra `+' marks along the top.)
-------------------------------------------------------------------------
There is, however, a more general reason to avoid types of the form
`pointer to array of unspecified length': namely, they are, for most
practical purposes, useless.
They have to exist, because arrays of unspecified length exist, and
`&array' is always legal. They may also be useful when you do not know
that something is an array---however, given C's peculiar (mis)treatment
of arrays, it is often essential that array types not be hidden.
Indeed, type abstraction in C virtually demands `struct' types (this is
why C++ classes compile to C structures). There are exceptions, but
as a general rule, array types should not be hidden. Given the code
fragment:
xyz_type v;
xyz_init(&v);
xyz_setup(&v);
look_at(v);
you can be fairly sure `look_at' does not alter v; but if xyz_type is
a name for an array type, look_at *could* alter v and all the `&v's
are red herrings.
To see why `pointer to array unknown_size of ...' is not a useful type,
we must consider how pointers are used. In other languages, a pointer
`points to' some object and is only useful for dealing with that one
particular object. The C language, however, makes a strong requirement
that other languages lack%. Namely, all object memory (except
`registers') must be `locally flat'. Any given chunk of `object
memory' can be broken down into bite-sized pieces, all of which are
right next to each other, with no holes or bumps in between. These
pieces are usually `bytes', though C requires only that they be
`char's; so while `char's are usually bytes and memory is usually made
up of bytes, C only requires that `char's exist and that memory is made
up of `char'-sized elements.$
-----
% Some might argue that this requirement fills a much-needed gap. If
memory need not be locally flat, other, possibly better, arrangements
can be considered. But we need not worry about this here; C makes
the requirement and C programmers use it all the time.
$ ANSI C says `char's *are* `byte's, and vice versa, yet allows `char's
to be more than 8 bits. Thus, you could have a compiler with 16-bit
`char's, but sizeof(char) would still be 1 and a `byte' would be 16
bits. I think most people will agree that this is an unconventional
defintion of `byte'; you will probably do best just to think in
terms of `char's.
----
In particular, after some chunk of object memory is broken down into
individual `char's, it can be reassembled in other forms. There can
be holes or bumps between these other forms, but if the holes, if any,
are considered part of each object, the memory can be treated as a
contiguous sequence of objects. C works this way and therefore C's
object memory can hold a contiguous sequence of objects.
Thus, if we have a sequence of four-char objects in a locally flat
segment of memory, it looks like this:
char number: 0 1 2 3 4 5 6 7 8 9 10 11 . . .
object: <object 000><object 001><object 002> . . .
Now, a C pointer can point to any one of those objects, or any one of
those `char's, just as other language's pointers can point to one
particular object. But since all of the objects are in sequence, such
a pointer also `points at' the whole sequence of objects:
char number: 0 1 2 3 4 5 6 7 8 9 10 11 . . .
object: <object 000><object 001><object 002> . . .
pointer: ^^^^^^^^^^
This pointer points directly to object number 1. If we add the integer
value `1', we get a new pointer that points to object number 2:
char number: 0 1 2 3 4 5 6 7 8 9 10 11 . . .
object: <object 000><object 001><object 002> . . .
pointer + 1: ^^^^^^^^^^
If we subtract 1, we get a new pointer that points to object number 0:
char number: 0 1 2 3 4 5 6 7 8 9 10 11 . . .
object: <object 000><object 001><object 002> . . .
pointer - 1: ^^^^^^^^^^
If we subtract 2, however, the resulting pointer `falls off the
edge of the world' (or at least, falls off the edge of the locally
flat memory region) and the computer may get eaten by a dragon.
Adding or subtracting an integer to or from a pointer is called
*pointer arithmetic*.
The way pointer arithmetic works, then, is quite simple. If you add
some (positive) integer value to a pointer, you `move right' that many
objects; if you subtract some integer value from a pointer, you `move
left' that many objects. You can also cast the pointer to `char *' or
`void *' and feed the result to functions that, like memmove(), deal in
terms of the individual `char's that make up each object.
Any sequence of identical objects can be treated as an *array*, and
any time you declare an array object, you get such a sequence. If
each of object in the sequence
object: <object 000><object 001><object 002>
is, say, a `long', then the whole sequence is an `array 3 of long'.
(This can also be called an `array of 3 longs', but if you spell it
this way you will get into trouble when you go to arrays of arrays:
we want to write things like `array 5 of array 2 of char', not
`array of 5 arrays of 2 chars'.)
Every array whose size is known can be described as an `array N of T',
where N is the number of objects in the array and T is the type of
each such object.
Now suppose that each of those <object nnn>'s is itself an array.
For instance, if each of the <object nnn> elements is changed from
a `long' to an `array 3 of char', we might get this picture:
char number: 0 1 2 3 4 5 6 7 8 9 10 11
object: <array 0><array 1><array 2><array 3>
Our whole object is an `array 4 of array 3 of char'. This is an `array
N of T', where N is 4 and T is `array 3 of char'. As a C declaration,
we might write:
char A[4][3];
Now suppose we make a pointer that points to <array 0>:
char number: 0 1 2 3 4 5 6 7 8 9 10 11
object: <array 0><array 1><array 2><array 3>
pointer: ^^^^^^^
If we add 1 to this pointer, we want it to point to array 1:
char number: 0 1 2 3 4 5 6 7 8 9 10 11
object: <array 0><array 1><array 2><array 3>
pointer + 1: ^^^^^^^
The pointers above each have type `pointer to array 3 of char', or
`pointer to T'.
One of the key concepts that make up the C language is that an `array N
of T' is a slippery customer, and quickly turns into a `pointer to T'
in most contexts. In particular, an `array N of T' is an object, and
when we need an object, that is just fine. Sometimes, however, we need
a value, rather than an object. A C array has N separate little pieces,
rather than one big value, and so C computes the `value' of an array as
the address of the array's first element.
This concept is so important that it is The Rule:
In any value context, an object of type `array N of T' becomes
a value of type `pointer to T', pointing to the first element
of that array, i.e., the one with subscript 0.
Thus, that pointer we made pointing to <array 0>, which was a `pointer
to T', is what we get if we put our array in a value context. One
value context is the operand of `+', so if we were to write:
char A[4][3]; ... A + 1 ...
we would first get the pointer pointing to <array 0>, and then we would
add 1 and wind up pointing to <array 1>. We can declare a suitable
pointer:
char (*p)[3]; /* p has type `pointer to array 3 of char' */
and write:
p = A + 1;
If we use the `*' indirection operator on the result, we get the entire
<array 1>, which is itself an `array 3 of char'. Thus,
*p
and
*(A + 1)
both mean `the object <array 1>'. Since A[1] is identical in effect
to *(A + 1), `A[1]' also means `the object <array 1>'.
Similarly, if we were to write:
*p + 0
or
A[1] + 0
we would work out A[1] as above and find that it is the whole object
`<array 1>', and we would have to apply The Rule again. This time we
have an object which is an array N=3 of T=char, so we get a pointer to
char, pointing to the first `char' in <array 1>:
char number: 0 1 2 3 4 5 6 7 8 9 10 11
object: <array 0><array 1><array 2><array 3>
A+1: ^^^^^^^
*(A+1): <array 1>
(*(A+1))+0: ^^
This time we add nothing, moving neither right nor left. The result is
a pointer pointing to the first `char' in <array 1>, or `char number 3'
in the overall sequence. If we apply the `*' indirection operator to
this last pointer, we get character number 3. Thus,
A[1][0]
is character number 3 in our overall picture.
We can also make a pointer that points to the whole thing:
char number: 0 1 2 3 4 5 6 7 8 9 10 11
object: <array 0><array 1><array 2><array 3>
pointer: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This pointer has type `pointer to array 4 of array 3 of char', and
can be written in C as:
char (*wholep)[4][3] = &A;
We have only drawn one of these `array 4 of array 3 of char's, so we
have no reason to use pointer arithmetic on `wholep'. That means
`wholep' last pointer is of no more use than `p': in particular, if we
set p to point to <array 0>, we can get to all of the array's elements
just by writing p[0], p[1], p[2], and p[3]. All we can do with
`wholep' is write `*wholep' (or `wholep[0]'), which just gives us the
whole array back. If we want to name A[1][0], we can either do this:
char (*p)[3] = A; /* or &A[0] */
p[1][0] = 'c';
or this:
char (*wholep)[4][3] = &A;
(*wholep)[1][0] = 'c';
In other words, p is `just as good' as wholep for our purposes. *There
is only one property wholep has that p lacks*: wholep points to a whole
`array 4 of array 3 of char', so if we had several such arrays in one
locally flat memory region, we could write `wholep + 1' to name the
whole array-4-of-array-3-of-char just to the right of *wholep.
So far, our pointers have always pointed to arrays of known size. What
happens when N is that special value, `unknown'?
Well, first, let us draw an array of unknown size, contained within
a larger locally-flat memory section.
char number: 0 1 2 ... ? ? ? ... ? ? ? ... ...
object: <array 0 ...><array 1 ...><array 2 ...> ...
Now, if we have a pointer that points to <array 1>, what can we
do with it?
char number: 0 1 2 ... ? ? ? ... ? ? ? ... ...
object: <array 0 ...><array 1 ...><array 2 ...> ...
pointer: ^^^^^^^^^^^
If we indirect through this pointer, we get the whole object `array 1'
(which has unknown size). We cannot inspect this object's value,
because of The Rule; if we try, all we get is another (different)
pointer, that points to the first element of <array 1>.
Is there anything we can do with our first pointer that we could not do
equally well with the one we get after applying `*' and The Rule? The
answer is no; but this is not obvious, and is only apparent once you
realize that all a `pointer to array N of T' gives you that a `pointer
to T' does not is the ability to step over whole `array N of T's. In
this case, we have no idea how big each array is, so we have no way to
step over a whole one.
In short, the type
T (*)[] /* pointer to array ? of T */
is no better than the type
T * /* pointer to T */
because all you can do with the former is get an `array ? of T', and
all you can really do with an `array ? of T' is name particular
elements of that array; and a `T *' is all you need to name elements
of an `array N of T'.
The difference is the same as that between an `array N of T' and a
`pointer to T': the constant N tells you the size of the array, and
thus allows you to step over whole arrays. If N is the special
value `unknown', the extra information N gives you is worthless:
you do not know the size of the array and cannot step over whole
arrays. So why bother to point to an array of unknown size? You
should do this only if you do not know, or are not supposed to know,
that the object you are addressing actually *is* an array of unknown
size. This is quite rare.
--
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 510 486 5427)
Berkeley, CA Domain: torek@ee.lbl.gov
-------------------------------------------------------------------
/*
* arrayn.c: Dynamic memory allocator for an n - dimensional array.
* ANSI conformance.
*
*/
#ifdef DEBUG
#include <stdio.h>
#endif /* DEBUG */
#ifndef __STDC__
#include <varargs.h>
extern char *malloc();
typedef char genptr_t;
#else
#include <stdarg.h>
extern void *malloc(unsigned n);
typedef void genptr_t;
#endif
typedef unsigned long u_long;
typedef struct _dimension_t {
u_long size; /* Number of elements in the dimension */
u_long totalsize; /* Total number of elements */
u_long elsize; /* Size of a single element in bytes */
u_long offset; /* offset from beginning of array */
} dimension_t;
/* arrayn():
* Allocate an n-dimensional array.
* We want to allocate only one chunk, so that free
* will free the whole array.
*/
#ifndef __STDC__
char *
/*VARARGS*/
arrayn(numdim, va_alist)
int numdim; /* Number of dimensions */
va_dcl
#else
void *
arrayn(int numdim, ...)
#endif
{
int i, j;
dimension_t *dim; /* Info about each dimension */
u_long total_size, /* Total size of the array */
pointer_size, /* Pointer size of the array */
element_size; /* Element size of the array */
genptr_t *array; /* the multi-dimensional array */
genptr_t **ptr, *data; /* Pointer and data offsets */
va_list va; /* Current pointer in the argument list */
#ifndef __STDC__
va_start(va);
#else
va_start(va, numdim);
#endif
if ( (dim = (dimension_t *)
malloc( (unsigned) (numdim * sizeof(dimension_t))))
== (dimension_t *) 0 )
return((genptr_t *) 0);
for ( i = 0; i < numdim; i++ ) {
dim[i].size = va_arg(va, u_long);
dim[i].elsize = sizeof(genptr_t *);
}
dim[numdim-1].elsize = va_arg(va, u_long);
va_end(va);
/*
* Compute the size of the array to be allocated
* elements : (x * y * z ... w * elementsize)
* pointers : (x * pointersize +
* y * x * pointersize +
* z * y * x * pointersize ..
*/
dim[0].totalsize = dim[0].size;
dim[0].offset = 0;
for ( i = 1; i < numdim; i++ ) {
dim[i].totalsize = dim[i-1].totalsize * dim[i].size;
dim[i].offset = dim[i-1].offset + dim[i-1].totalsize * dim[i-1].elsize;
}
element_size = dim[numdim-1].offset +
dim[numdim-1].totalsize * dim[numdim-1].elsize;
pointer_size = dim[numdim-1].totalsize;
total_size = element_size + pointer_size;
#ifdef DEBUG
(void) fprintf(stderr, "%20s : %10d\n", "Number of dimensions",
numdim, numdim);
(void) fprintf(stderr, "%20s : %10d (%.8x)\n", "Unit size",
dim[numdim-1].elsize, dim[numdim-1].elsize);
(void) fprintf(stderr, "%20s : %10d (%.8x)\n", "Size of pointers",
pointer_size, pointer_size);
(void) fprintf(stderr, "%20s : %10d (%.8x)\n", "Size of elements",
element_size, element_size);
(void) fprintf(stderr, "%20s : %10d (%.8x)\n", "Total size",
total_size, total_size);
(void) fprintf(stderr, "\nDimension\tSize\tTotal Size\tOffset\tElement\n");
for ( i = 0; i < numdim; i++ )
(void) fprintf(stderr, "%9d\t%4d\t%10d\t%6d\t%7d\n", i, dim[i].size,
dim[i].totalsize, dim[i].offset, dim[i].elsize);
#endif /* DEBUG */
/*
* Allocate space to hold the array
*/
if ( (array = (genptr_t *) malloc((unsigned) total_size)) ==
(genptr_t *) 0 ) {
(void) free((genptr_t *) dim);
return((genptr_t *) 0);
}
/*
* Thread the pointers
*/
for ( i = 0; i < numdim - 1; i++ ) {
ptr = (genptr_t **) (array + dim[i].offset);
data = (genptr_t *) (array + dim[i+1].offset);
for ( j = 0; j < dim[i].totalsize; j++ )
ptr[j] = data + j * dim[i+1].elsize * dim[i+1].size;
}
(void) free((genptr_t *) dim);
return(array);
} /* end arrayn */