1.How can I set an array's size at run time? How can I avoid fixed-sized arrays?
ANS: The equivalence between arrays and pointers allows
a pointer to malloc'ed memory to simulate an array quite
effectively. After executing
#include <stdlib.h>
int *dynarry;
dynarry = malloc(10 * sizeof(int));
(and if the call to malloc succeeds),
you can reference dynarry[i] (for i from 0 to 9) almost as if dynarry were a
conventional, statically-allocated array (int a[10]). The only difference is that sizeof will not
give the size of the ``.
2.How can I declare local arrays of a size
matching a passed-in array?
ANS: Until recently, you couldn't; array
dimensions in C traditionally had to be compile-time constants. However, C99
introduces variable-length arrays (VLA's) which solve this problem; local
arrays may have sizes set by variables or other expressions, perhaps involving
function parameters. (gcc has provided parameterized arrays as an
extension for some time.) If you can't use C99 or gcc, you'll have to use malloc, and
remember to call free before the function returns
3.How can I dynamically allocate a
multidimensional array?
ANS: The
traditional solution is to allocate an array of pointers to pointers, and then initialize
each pointer to a dynamically-allocated ``row.'' Here is a two-dimensional
example:
#include <stdlib.h>
int **array1 = malloc(nrows * sizeof(int *));
for(i = 0; i < nrows; i++)
arry1[i] = malloc(ncolumns * sizeof(int));
(In real code, of course, all of malloc's return
values would be checked. You can also use sizeof(*arry1) and sizeof(**arry1) instead of sizeof(int *) and sizeof(int); )
You can keep the array's contents
contiguous, at the cost of making later reallocation of individual rows more
difficult, with a bit of explicit pointer arithmetic:
int **arry2 = malloc(nrows * sizeof(int *));
arry2[0] = malloc(nrows * ncolumns * sizeof(int));
for(i = 1; i < nrows; i++)
arry2[i] = arry2[0] + i * ncolumns;
In either case (i.e for arry1 or arry2), the
elements of the dynamic array can be accessed with normal-looking array
subscripts: arryx[i][j] (for 0 <= i < nrows and
0 <= j < ncolumns). Here is a schematic illustration of the
layout of arry1 and arry2:
[FIGURE GOES HERE]
If the double indirection implied
by the above schemes is for some reason unacceptable, you can simulate a
two-dimensional array with a single, dynamically-allocated one-dimensional
array:
int *arry3 = malloc(nrows * ncolumns * sizeof(int));
However, you must now perform subscript
calculations manually, accessing the i,jth element with the expression
arry3[i * ncolumns + j]
and this array cannot necessarily be passed
to functions which expect multidimensional arrays. (A macro such as
#define Arrayaccess(a, i, j) ((a)[(i) * ncolumns + (j)])
could hide the explicit calculation, but
invoking it would require parentheses and commas which wouldn't look exactly
like conventional C multidimensional array syntax, and the macro would need
access to at least one of the dimensions, as well
Yet another option is to use
pointers to arrays:
int (*arry4)[NCOLUMNS] = malloc(nrows * sizeof(*arry4));
or even
int (*arry5)[NROWS][NCOLUMNS] = malloc(sizeof(*arry5));
but the syntax starts getting horrific
(accesses to arry5 look like (*arry5)[i][j]), and at most one dimension may be specified
at run time.
With all of these techniques, you
may of course need to remember to free the arrays when they are no longer
needed; in the case of array1 and arry2 this takes several steps :
for(i = 0; i < nrows; i++)
free((void *)arry1[i]);
free((void *)arry1);
free((void *)arry2[0]);
free((void *)arry2);
Also, you cannot necessarily intermix
dynamically-allocated arrays with conventional, statically-allocated ones .
Finally, in C99 you can use a
variable-length array.
All of these techniques can also
be extended to three or more dimensions. Here is a three-dimensional version of
the first technique (which, like the rest of the fragments presented here,
requires error-checking before being used in a real program):
int ***a3d = (int ***)malloc(xdim * sizeof(int **));
for(i = 0; i < xdim; i++) {
a3d[i] = (int **)malloc(ydim * sizeof(int *));
for(j = 0; j < ydim; j++)
a3d[i][j] = (int *)malloc(zdim * sizeof(int));
}
4.Here's a neat trick: if I write
int realarry[10];
int *arry = &realarry[-1];
I can treat array as if it
were a 1-based array.
ANS: Although this technique is attractive (and was
used in old editions of the book Numerical Recipes in C), it is not
strictly conforming to the C Standard. Pointer arithmetic is defined only as
long as the pointer points within the same allocated block of memory, or to the
imaginary ``terminating'' element one past it; otherwise, the behavior is undefined,
even if the pointer is not dereferenced.
The code above computes a pointer to memory before the beginning of realarry and could
fail if, while subtracting the offset, an illegal address were generated
(perhaps because the address tried to ``wrap around'' past the beginning of
some memory segment).
5.My compiler complained when I passed a
two-dimensional array to a function expecting a pointer to a pointer.
ANS: The rule by which arrays decay into pointers
is not applied
recursively. (Once the rule has been applied once, the result is a pointer to
which the rule no longer applies.) An array of arrays (i.e. a two-dimensional
array in C) decays into a pointer to an array, not a pointer to a pointer.
Pointers to arrays can be confusing, and must be treated carefully;
If you are passing a
two-dimensional array to a function:
int arry[NROWS][NCOLUMNS];
f(arry);
the function's declaration must match:
void f(int a[][NCOLUMNS])
{ ... }
or
void f(int (*ap)[NCOLUMNS]) /* ap is a pointer to an arry */
{ ... }
In the first declaration, the compiler
performs the usual implicit parameter rewriting of ``array of array'' to
``pointer to array'';in the second form the pointer declaration is explicit.
Since the called function does not allocate space for the array, it does not
need to know the overall size, so the number of rows, NROWS, can be
omitted. The width of the array is still important, so the column dimension NCOLUMNS (and, for
three- or more dimensional arrays, the intervening ones) must be retained.
If a function is already declared
as accepting a pointer to a pointer, it is almost certainly meaningless to pass
a two-dimensional array directly to it. An intermediate pointer would have to
be used when attempting to call it with a two-dimensional array:
extern g(int **ipp);
int *ip = &arry[0][0];
g(&ip); /* PROBABLY WRONG */
but this usage is misleading and almost
certainly incorrect, since the array has been ``flattened'' (its shape has been
lost).
6.How do I write functions which accept
two-dimensional arrays when the width is not known at compile time?
ANS: It's
not always easy. One way is to pass in a pointer to the [0][0] element,
along with the two dimensions, and simulate array subscripting ``by hand'':
void f2(int *aryp, int nrows, int ncolumns)
{ ... arry[i][j] is accessed as aryp[i * ncolumns + j] ... }
Note that the correct expression for manual
subscripting involves ncolumns (the ``width'' of each row), not nrows (the number of rows); it's easy to get
this backwards.
This function could be called
with the array as
f2(&arry[0][0], NROWS, NCOLUMNS);
It must be noted, however, that a
program which performs multidimensional array subscripting ``by hand'' in this
way is not in strict conformance with the ANSI C Standard; according to an
official interpretation, the behavior of accessing (&arry[0][0])[x] is not defined for x >= NCOLUMNS.
C99 allows variable-length
arrays, and once compilers which accept C99's extensions become widespread,
VLA's will probably become the preferred solution. (gcc has
supported variable-sized arrays for some time.)
When you want to be able to use a
function on multidimensional arrays of various sizes, one solution is to
simulate all the arrays dynamically.
7.How can I use statically- and
dynamically-allocated multidimensional arrays interchangeably when passing them
to functions?
ANS: There
is no single perfect method. Given the declarations
int arry[NROWS][NCOLUMNS];
int **arry1; /* ragged */
int **arry2; /* contiguous */
int *arry3; /* "flattened" */
int (*arry4)[NCOLUMNS];
int (*arry5)[NROWS][NCOLUMNS];
with the pointers initialized as in the code fragments
and functions declared as
void f1a(int a[][NCOLUMNS], int nrows, int ncolumns);
void f1b(int (*a)[NCOLUMNS], int nrows, int ncolumns);
void f2(int *aryp, int nrows, int ncolumns);
void f3(int **pp, int nrows, int ncolumns);
where f1a and f1b accept conventional two-dimensional arrays, f2 accepts a
``flattened'' two-dimensional array, and f3 accepts a pointer-to-pointer, simulated
array, the following calls should work as expected:
f1a(arry, NROWS, NCOLUMNS);
f1b(arry, NROWS, NCOLUMNS);
f1a(arry4, nrows, NCOLUMNS);
f1b(arry4, nrows, NCOLUMNS);
f1(*arry5, NROWS, NCOLUMNS);
f2(&arry[0][0], NROWS, NCOLUMNS);
f2(*arry, NROWS, NCOLUMNS);
f2(*arry2, nrows, ncolumns);
f2(arry3, nrows, ncolumns);
f2(*arry4, nrows, NCOLUMNS);
f2(**arry5, NROWS, NCOLUMNS);
f3(arry1, nrows, ncolumns);
f3(arry2, nrows, ncolumns);
The following calls would probably work on
most systems, but involve questionable casts, and work only if the dynamic ncolumns matches the
static NCOLUMNS:
f1a((int (*)[NCOLUMNS])(*arry2), nrows, ncolumns);
f1a((int (*)[NCOLUMNS])(*arry2), nrows, ncolumns);
f1b((int (*)[NCOLUMNS])arry3, nrows, ncolumns);
f1b((int (*)[NCOLUMNS])arry3, nrows, ncolumns);
It will be noticed that only f2 can
conveniently be made to work with both statically- and dynamically-allocated
arrays, though it will not
work with the traditional ``ragged'' array implementation, arry1. However,
it must also be noted that passing &arry[0][0] (or, equivalently, *arry) to f2 is not
strictly conforming;
If you can understand why all of
the above calls work and are written as they are, and if you understand why the
combinations that are not listed would not work, then you have a very good understanding of arrays
and pointers in C.
Rather than worrying about all of
this, one approach to using multidimensional arrays of various sizes is to make
them all dynamic. If there
are no static multidimensional arrays--if all arrays are allocated like arry1 or arry2 then all
functions can be written like f3.
8.Why doesn't sizeof properly
report the size of an array when the array is a parameter to a function? I have
a test routine
f(char a[10])
{
int i = sizeof(a);
printf("%d\n", i);
}
and it prints 4, not 10.
ANS: The
compiler pretends that the array parameter was declared as a pointer (that is,
in the example, as char *a; and sizeof reports the size of the pointer.
9. I want to know how many elements are in an
array, but sizeof yields the size in bytes.
ANS: Simply divide the size of the entire array by
the size of one element:
int arry[] = {1, 2, 3};
int narry = sizeof(arry) / sizeof(arry[0]);
10. Is there a way to have an array of bits?
ANS: No.
11. Why doesn't this fragment work?
char *answer;
printf("Type something:\n");
gets(answer);
printf("You typed \"%s\"\n", answer);
ANS: The
pointer variable answer, which is handed to gets() as the
location into which the response should be stored, has not been set to point to
any valid storage. It is an uninitialized variable, just as is the variable i in
int i;
printf("i = %d\n", i);
That is, in the first piece of code, we
cannot say where the pointer answer points, just as we cannot say what value i will have
in the second. (Since local variables are not initialized, and typically
contain garbage, it is not even guaranteed that answer starts out as a null pointer. )
The simplest way to correct the
question-asking program is to use a local array, instead of a pointer, and let
the compiler worry about allocation:
#include <stdio.h>
#include <string.h>
char answer[100], *p;
printf("Type something:\n");
fgets(answer, sizeof answer, stdin);
if((p = strchr(answer, '\n')) != NULL)
*p = '\0';
printf("You typed \"%s\"\n", answer);
This example also uses fgets() instead of gets(), so that the
end of the array cannot be overwritten. ( Unfortunately for this example, fgets() does not
automatically delete the trailing \n, as gets() would.) It would also be possible to use malloc() to allocate
the answer buffer, and to parameterize the buffer size
(with something like #define ANSWERSIZE 100 ).
12. I can't get strcat to work. I
tried
char *s1 = "Hello, ";
char *s2 = "world!";
char *s3 = strcat(s1, s2);
but I got strange results.
ANS: the
main problem here is that space for the concatenated result is not properly
allocated. C does not provide an automatically-managed string type. C compilers
allocate memory only for objects explicitly mentioned in the source code (in
the case of strings, this includes character arrays and string literals). The
programmer must arrange for sufficient space for the results of run-time
operations such as string concatenation, typically by declaring arrays, or by
calling malloc.
strcat performs no allocation; the second string is
appended to the first one, in place. The first (destination) string must be
writable and have enough room for the concatenated result. Therefore, one fix
would be to declare the first string as an array:
char s1[20] = "Hello, ";
(In production code, of course, we wouldn't
use magic numbers like ``20''; we'd use more robust mechanisms to guarantee
sufficient space.)
Since strcat returns the
value of its first argument (s1, in this case), the variable s3 in the
question above is superfluous; after the call to strcat, s1 contains the result.
The original call to strcat in the
question actually has two problems: the string literal pointed to by s1, besides
not being big enough for any concatenated text, is not necessarily writable at
all.
13. But the man page for strcat says that
it takes two char *'s as arguments. How am I supposed to know to
allocate things?
ANS: In general, when using pointers you always have to consider memory
allocation, if only to make sure that the compiler is doing it for you. If a
library function's documentation does not explicitly mention allocation, it is
usually the caller's problem.
The Synopsis section at the top
of a Unix-style man page or in the ANSI C standard can be misleading. The code
fragments presented there are closer to the function definitions used by an
implementor than the invocations used by the caller. In particular, many
functions which accept pointers (e.g. to structures or strings) are usually
called with a pointer to some object (a structure, or an array) which the
caller has allocated. Other common examples are time and stat.
14. I just tried the code
char *p;
strcpy(p, "abc");
and it worked. How? Why didn't it crash?
ANS: You got lucky, I guess. The memory randomly
pointed to by the uninitialized pointer p happened to be writable by you, and
apparently was not already in use for anything vital.
15. How much memory does a pointer variable
allocate?
ANS: That's a pretty misleading question. When
you declare a pointer variable, as in
char *p;
you (or, more properly, the compiler) have
allocated only enough memory to hold the pointer itself; that is, in this case
you have allocated sizeof(char *) bytes of memory. But you have not yet
allocated any memory for the
pointer to point to.
16. I'm
reading lines from a file into an array, with this code
char linebuf[80];
char *lines[100];
int i;
for(i = 0; i < 100; i++) {
char *p = fgets(linebuf, 80, fp);
if(p == NULL) break;
lines[i] = p;
}
Why do all the lines end up containing copies
of the last line?
ANS: You have only allocated memory for one line,
linebuf. Each time you call fgets, the
previous line is overwritten. fgets doesn't do any memory allocation: unless it
reaches EOF (or encounters an error), the pointer it returns is the same
pointer you handed it as its first argument (in this case, a pointer to your
single linebuf array).
To make code like this work,
you'll need to allocate memory for each line.
17. I have a function that is supposed to
return a string, but when it returns to its caller, the returned string is
garbage.
ANS: Whenever a function returns a pointer, make
sure that the pointed-to memory is properly allocated. For example, make sure
you have not done something
like
#include <stdio.h>
char *itoa(int n)
{
char retbuf[20]; /* WRONG */
sprintf(retbuf, "%d", n);
return retbuf; /* WRONG */
}
When a function returns, its automatic, local
variables are discarded, so the returned pointer in this case is invalid (it
points to an array that no longer exists).
One fix would be to declare the
return buffer as
static char retbuf[20];
This fix is imperfect, since a function using
static data is not reentrant. Furthermore, successive calls to this version of itoa keep
overwriting the same return buffer: the caller won't be able to call it several
times and keep all the return values around simultaneously.
References: K&R1 Sec. 7.8 p.
155
18. So what's the right way to return a
string or other aggregate?
ANS: The returned pointer should be to a
statically-allocated or to a buffer passed in by the caller, or to memory
obtained with malloc, but not
to a local (automatic) array.
For example, to have the caller
pass space for the result:
char *itoa(int n, char *retbuf)
{
sprintf(retbuf, "%d", n);
return retbuf;
}
....
char str[20];
itoa(123, str);
To use malloc:
#include <stdlib.h>
char *itoa(int n)
{
char *retbuf = malloc(20);
if(retbuf != NULL)
sprintf(retbuf, "%d", n);
return retbuf;
}
....
char *str = itoa(123);
(In this last case, the caller must remember
to free the returned pointer when it is no longer
needed.)
19. Why am I
getting ``warning: assignment of pointer from integer lacks a cast'' for calls
to malloc?
ANS: Have you #included <stdlib.h>, or otherwise arranged for malloc to be
declared properly? If not, the compiler assumes that it returns an int, which is
not correct. (The same problem could arise for calloc or realloc.)
References: H&S Sec. 4.7 p.
101
20. Why does some code carefully cast the
values returned by malloc to the pointer type being allocated?
ANS: Before ANSI/ISO Standard C introduced the void * generic
pointer type, these casts were typically required to silence warnings (and
perhaps induce conversions) when assigning between incompatible pointer types.
Under ANSI/ISO Standard C, these
casts are no longer necessary. It can also be argued that they are now to be
discouraged; Furthermore, well-defined, low-risk implicit conversions (such as
those which C has always performed between integer and floating-point types)
can be considered a feature.
On the other hand, some
programmers prefer to make every
conversion explicit, to record that they have considered each case and decided
exactly what should happen (Also, the casts are typically seen in C code which
for one reason or another is intended to be compatible with C++, where explicit
casts from void * are required.
(By the way, the language in
sections 6.5 and 7.8.5 of K&R2 which suggests that the casts are required
is ``overenthusiastic.'')
To some extent, whether you use
these casts or not is a matter of style;
21. What's wrong with casting malloc's return
value?
ANS: Suppose that you call malloc but forget
to #include <stdlib.h>. The compiler is likely to assume that malloc is a
function returning int, which is of course incorrect, and will lead
to trouble. Now, if your call to malloc is of the form
char *p = malloc(10);
the compiler will notice that you're
seemingly assigning an integer to a pointer, and will likely emit a warning of
the form ``assignment of pointer from integer lacks a cast”which will alert you
to the problem. (The problem is of course that you forgot to #include <stdlib.h>, not that you forgot to use a cast.) If, on
the other hand, your call to malloc includes a cast:
char *p = (char *)malloc(10);
the compiler is likely to assume that you
know what you're doing, that you really do want to convert the int returned by
malloc to a pointer, and the compiler therefore
probably won't warn you. But
of course malloc does not return an int, so trying
to convert the int that it doesn't return to a pointer is
likely to lead to a different kind of trouble, which will be harder to track
down.
(Of course, compilers are
increasingly likely--especially under C99--to emit warnings whenever functions
are called without prototypes in scope, and such a warning would alert you to
the lack of <stdlib.h> whether casts were used or not.)
22. In a call to malloc, what does
an error like ``Cannot convert `void *' to `int *''' mean?
ANS: It means you're using a C++ compiler instead
of a C compiler.
23. I see code like
char *p = malloc(strlen(s) + 1);
strcpy(p, s);
Shouldn't that be malloc((strlen(s) + 1) * sizeof(char))?
ANS: It's never necessary to multiply by sizeof(char), since sizeof(char) is, by
definition, exactly 1. (On the other hand, multiplying by sizeof(char) doesn't
hurt, and in some
24. What should malloc(0) do? Return
a null pointer or a pointer to 0 bytes?
ANS: The
ANSI/ISO Standard says that it may do either; the behavior is implementation-defined.
Portable code must either take care not to call malloc(0), or be prepared
for the possibility of a null return.
25. I've heard that some operating systems
don't actually allocate malloc'ed memory until the program tries to use it.
Is this legal?
ANS: It's hard to say. The Standard doesn't say
that systems can act this way, but it doesn't explicitly say that they can't,
either. (Such a ``deferred failure'' implementation would not seem to conform to
the implied requirements of the Standard.)
The conspicuous problem is that,
by the time the program gets around to trying to use the memory, there might
not be any. The program in this case must typically be killed by the operating
system, since the semantics of C provide no recourse. (Obviously, malloc is supposed
to return a null pointer if there's no memory, so that the program--as long as
it checks malloc's return value at all--never tries to use
more memory than is available.)
Systems that do this ``lazy
allocation'' usually provide extra signals indicating that memory is
dangerously low, but portable or naïve programs won't catch them. Some systems
that do lazy allocation also provide a way to turn it off (reverting to
traditional malloc semantics), on a per-process or per-user
basis, but the details vary from system to system.
26. I'm allocating a large array for some
numeric work, using the line
double *array = malloc(300 * 300 * sizeof(double));
malloc isn't
returning null, but the program is acting strangely, as if it's overwriting
memory, or malloc isn't allocating as much as I asked for, or
something.
ANS: Notice that 300 x 300 is 90,000, which will
not fit in a 16-bit int, even before you multiply it by sizeof(double). If you need to allocate this much memory, you'll have to be
careful. If size_t (the type accepted by malloc) is a
32-bit type on your machine, but int is 16 bits, you might be able to get away
with writing 300 * (300 * sizeof(double)) .Otherwise, you'll have to break your data
structure up into smaller chunks, or use a 32-bit machine or compiler, or use
some nonstandard memory allocation functions.
27. I've got 8 meg of memory in my PC. Why
can I only seem to malloc 640K or so?
ANS: Under the segmented architecture of PC
compatibles, it can be difficult to use more than 640K with any degree of
transparency, especially under MS-DOS.
28. My application depends heavily on dynamic
allocation of nodes for data structures, and malloc/free overhead is
becoming a bottleneck. What can I do?
ANS: One improvement, which is particularly
attractive if all nodes are the same size, is to place unused nodes on your own
free list, rather than actually freeing them. (This approach works well when one
kind of data structure dominates a program's memory use, but it can cause as
many problems as it solves if so much memory is tied up in the list of unused
nodes that it isn't available for other purposes.)
29. My program is crashing, apparently
somewhere down inside malloc, but I can't see anything wrong with it. Is
there a bug in malloc?
ANS: It is unfortunately very easy to corrupt malloc's internal
data structures, and the resulting problems can be stubborn. The most common
source of problems is writing more to a malloc'ed region than it was allocated to hold; a
particularly common bug is to malloc(strlen(s)) instead of strlen(s) + 1.Other problems may involve using pointers to
memory that has been freed, freeing pointers twice, freeing pointers not
obtained from malloc, freeing null pointers, allocating 0-sized objects
, or trying to realloc a null pointer . (The last three--freeing null
pointers, allocating 0-sized objects, and reallocing a null pointer--are sanctioned by the
Standard, though older implementations often have problems.) Consequences of
any of these errors can show up long after the actual mistake and in unrelated
sections of code, making diagnosis of the problem quite difficult.
Most implementations of malloc are
particularly vulnerable to these problems because they store crucial pieces of
internal information directly adjacent to the blocks of memory they return,
making them easy prey for stray user pointers.
30. I'm dynamically allocating an array, like
this:
int *iarray = (int *)malloc(nints);
malloc isn't
returning NULL, but the code isn't working.
ANS: malloc is a low-level, typeless allocator. It
doesn't know how you're going to use the memory; all it does is to allocate as
many bytes of memory as
you ask it. Therefore (except when you're allocating arrays of char) you must
multiply by the size of the elements in the array you're allocating:
int *iarray = malloc(nints * sizeof(int));
or
int *iarray = malloc(nints * sizeof(*iarray));
(The latter fragment can be more reliable if
the type of iarray might change, since there's only one place
to change it. Also, the casts have been removed.
31. You can't use dynamically-allocated
memory after you free it, can you?
ANS: No. Some early documentation for malloc stated that
the contents of freed memory were ``left undisturbed,'' but this ill-advised
guarantee was never universal and is not required by the C Standard.
Few programmers would use the
contents of freed memory deliberately, but it is easy to do so accidentally.
Consider the following (correct) code for freeing a singly-linked list:
struct list *listp, *nextp;
for(listp = base; listp != NULL; listp = nextp) {
nextp = listp->next;
free(listp);
}
and notice what would happen if the
more-obvious loop iteration expression listp = listp->next were used, without the temporary nextp pointer.
No comments:
Post a Comment