NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/comp/lang/c/20009

Internet Message Format | 1993-01-21 | 8.2 KB

Path: sparky!uunet!spool.mu.edu!agate!dog.ee.lbl.gov!horse.ee.lbl.gov!torek
From: [e-mail] (Chris Torek)
Newsgroups: comp.lang.c
Subject: 2-d arrays, pointers, etc, for the N'th time: with pictures
Date: 21 Jan 1993 10:30:53 GMT
Organization: Lawrence Berkeley Laboratory, Berkeley CA
Lines: 206
Message-ID: <[e-mail]>
References: <[e-mail]>
NNTP-Posting-Host: 128.3.112.15

(This was a mail reply, but then I figured I might as well post it too.
This version has some additional commentary.)

>     Given a 2-dimensional array, how is it possible to dynamically
>allocate memory for the first dimension?

It is not possible; but you have asked the wrong question.  You
should instead ask:

    Given the desire to obtain something that functions as if
    it were a two-dimensional array, ...

and this question has (at least) two answers, both in the FAQ.

>In other words, I wanted to changed the declaration from
>record[56][5] to
>*record[5] or record[][5]

Neither of these is quite right.  If record is supposed to be accessed
as if it were an `array M of array N of data_t', it must have one of
the following three types:

    - array M of array N of data_t;
    - pointer to array N of data_t;
    - pointer to pointer to data_t.

The first case is simply, e.g.,

    data_t record[56][5];        /* M=56, N=5 */

The second form is:

    data_t (*record)[5];        /* pointer to array N=5 of ... */

and the third form is:

    data_t **record;

The latter two forms work because of The Rule (this is THE rule about
arrays, which must simply be memorized):

    In any value context, an object of type `array N of T', for any
    integer constant N and valid type T, becomes a value of type
    `pointer to T', pointing to the first element of that array, i.e.,
    the one with subscript 0.

Everything else about arrays and pointers is a consequence of The Rule,
along with the rules of pointer arithmetic.  Pointer arithmetic assumes
that objects are laid out contiguously in memory; since arrays *are*,
The Rule works out perfectly.

Thus, if you declare, e.g.,

    int a[4][7];

you have created an object named `a' of type `array 4 of array 7 of
int', or, if you prefer, `array of 4 arrays of 7 ints each'.  This has
the form `array N of T': N=4 and T=`array 7 of int'.  (Array types are
legal object types, of course, so T may have the form `array N2 of
T2'.)  Placing the object `a' in a value context invokes The Rule.

    <value context> a ==> a is an object of type array N=4 of T=...

so we get a `pointer to T':

    <value, pointer to T=array 7 of int, &a[0]>

In C, the type `pointer to array 7 of int' is written `int (*)[7]'.
(Note that the constant N `drops out'; this means that in many cases it
can be ignored, and in some it need not even be supplied.  These are
nonetheless special cases.  It *always* works if you supply the
constant N; it *sometimes* works if you omit it.)

Now suppose instead of the *object* `a', we just figure out some
suitable *value* and save it away somewhere.  This value should
have the same type we just came up with---`int (*)[7]'---and we
can save it in an object of that type.  So:

    int (*ap)[7];    /* declare ap as pointer to array 7 of int */

    ap = a;        /* `a' is in a value context here */

ap now points to the first element of a (a[0]), which is a single
`array 7 of int'.  Note that ap points to all 7 ints, all at once.  If
we now ask for *ap, we fetch this object---but it has type `array 7 of
int', so if we put *that* in a value context, it again falls under The
Rule.  This gives us a pointer to the first of those 7 ints, i.e.,
&a[0][0], or &ap[0].

We can do exactly the same with the `record' variable: instead of
making it an array object (array M=56 of T=...) we make it a pointer
to `T'.  Now we can allocate space with malloc or calloc as needed,
so that we are not stuck with exactly 56 objects of type T.

Note that if we use `data_t (*record)[5]', while we are not stuck
with 56 arrays, we *are* stuck with 5 elements in each sub-array.  If
this is not OK, then we will be forced to use the third form.  The
third form has a disadvantage: it needs intermediate space for the
second set of pointers, as illustrated below.

In the following pictures, space that typically comes from malloc() is
not labelled at all---which seems fitting, since it does not have a
specific name.  There is no requirement to use malloc/calloc, but if
it is not used, there is little reason to bother with the pointers.

====================================================================

With data_t record[56][5]:

    record
    +---+---+---+---+---+
    | 0 | 1 | 2 | 3 | 4 |   (record[0])
    +---+---+---+---+---+
    | 0 | 1 | 2 | 3 | 4 |   (record[1])
    +---+---+---+---+---+
          .
          .
          .
    +---+---+---+---+---+
    | 0 | 1 | 2 | 3 | 4 |   (record[55])
    +---+---+---+---+---+

    (each record[i] is physically adjacent to record[i+1])

In this case `record' is a label for a block of 56*5 data_t objects.
All of the objects are `right there': all you have to do to find them
is go to the right row, then go to the right column.  Note that
`record' is the entire block of 56*5 objects: sizeof(record) = 56*5*
sizeof(data_t).

====================================================================

With data_t (*record)[5]:

    record
    +---+        +---+---+---+---+---+
    | ------------> | 0 | 1 | 2 | 3 | 4 | sub-block 0
    +---+        +---+---+---+---+---+
            | 0 | 1 | 2 | 3 | 4 | sub-block 1
            +---+---+---+---+---+
                  .
                  .
                  .
            +---+---+---+---+---+
            | 0 | 1 | 2 | 3 | 4 | sub-block 55 (or whatever)
            +---+---+---+---+---+
        (each of these sub-blocks is physically adjacent)

In this case `record' is just a pointer.  The memory holding the
various data objects must be allocated separately.  All of the objects
are `over yonder': to find them, you read the contents of the variable
`record', go there, then go to the right row, then to the right
column.  Note that record[i] is an entire sub-block, or 5 objects:
sizeof(record[i]) = 5*sizeof(data_t).  These sub-blocks are C arrays.
Their contiguous arrangement---where each sub-block is followed by the
corresponding next sub-block---makes the whole malloc()ed block `act
like' an array, but because it lacks a fixed compile-time size, it is
not actually a C array.

====================================================================

With data_t **record:

    record
    +---+        +---+      +---+---+---+---+---+
    | ------------> | ------> | 0 | 1 | 2 | 3 | 4 |
    +---+        +---+      +---+---+---+---+---+
            | ------\
    +---+---+---+---+    +---+    |    +---+---+---+---+---+---+
    | 0 | 1 | 2 | 3 | <---- |   \-----> | 0 | 1 | 2 | 3 | 4 | 5 |
    +---+---+---+---+    +---+        +---+---+---+---+---+---+
                  .
              .
              .
            +---+          +---+---+---+---+---+
            | ----------> | 0 | 1 | 2 | 3 | 4 |
            +---+          +---+---+---+---+---+

In this case `record' is again just a pointer, but this time it does
not point to the first of a whole series of data objects.  Instead, it
points to the first of a whole series of pointers.  The objects
themselves are `over the hills and through the woods'.  First we have
to read the value of `record' to find the series of pointers.  Next we
select the row---one of the series of pointers---and read its value to
find the series of columns.  Note that record[i][j] is a single
object: sizeof(record[i][j]) = sizeof(data_t).  There are no actual
arrays here, merely things that `act like them' due to contiguous
allocation.

In this case, the set of 56 (or whatever number of) intermediate
pointers must be contiguous, but each little group of 5 can be anywhere
independent of any other group of 5.  Since each group of 5 is
independent, they need not all be groups of 5: some can have 4, or 9,
or whatever, as shown above.  Of course, you can *make* them all
adjacent by allocating all 56*5 (or however many) at once, and then set
up the intermediate pointers as needed.

The last arrangement is clearly much more flexible.  There is a price,
however: the intermediate pointers take some storage.  They also take
extra time to load, which may or may not be offset by the time spent
calculating the proper row and column in the other versions.  The time
difference is negligible in most code; the space and `shape' difference
is typically the most important.
--
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE ([phone])
Berkeley, CA        Domain:    [e-mail]