Classical Array Implementation Using Pointers and Memory Allocation

Question

So I got this question from a competition website and I am completely puzzled. Here it is:

Which of the following memory allocation code for p[10][10] confirms perfectly to classical definition of an array? The options are:

char **p;
int i;
p = (char**)malloc(10*sizeof(char*));
*p = (char*)malloc(10*sizeof(char));
for(i = i; i<10; i++)
    p[i] = p[0] +10*i;

---

char **p;
int i;
p = (char**)realloc(p, 10*sizeof(char*));
*p = (char*)realloc(p, 10*sizeof(char));
for(i = i; i<10; i++)
    p[i] = p[0] +10*i;

---

char **p = NULL;
int i;
p = (char**)malloc(10*sizeof(char*));
*p = (char*)malloc(10*sizeof(char));
for(i = i; i<10; i++)
    p[i] = (char*)realloc(p[i-1], 10*i*sizeof(char));

---

char **p;
int i;
p = (char**)malloc(10*sizeof(char*));
for(i = i; i<10; i++)
    p[i] = (char*)malloc(10*sizeof(char));

I am completely puzzled. Any ideas are most welcome. Thanks.

EDIT: If none of them are are correct, what would be the correct implementation? A bit of explanation is most welcome as I am preparing for aa competitive exam that requres these skills which ask questions like this (most of which has obvious 'side effects' :( ). Also edited the typos.

Answer 1

None. This one does:

char (*p)[10] = malloc(10*sizeof(*p));

Explanation:
p is declared as a pointer to an array of ten chars. Since it points to an array, sizeof(*p) returns the size of that array, which is 10. So, the malloc() call allocates memory for ten such arrays, i. e. 100 bytes.

Now, when you derefence the pointer as in p[3], the value is the fourth array in the slap of memory. However, this value decays to a pointer to its first element in almost all contexts, so when you say p[3][5] the value is the 6th element within the 4th array within the memory slap.

Sorry, if this sounds a bit confusing, but it's really the same thing that's happening when you declare an array with char array[10][10];, except that the memory comes from a different place.

Answer 2

First things first : do not cast the return value of malloc in C. This is not your code, but anyway, it is always good to say.
Also, the loops should be rewritten like so : for(i = 1; i < 10; i++) or maybe for(i = 0; i < 10; i++). i = i is probably an error (what is that website, again ?), and I will assume so.

char **p;
int i;
p = malloc(10*sizeof(char*));
*p = malloc(10*sizeof(char));
for(i = 1; i < 10; i++)
    p[i] = p[0] + 10*i;

This first code allocates 10 char* to p, and then 10 char to *p, which is equivalent to p[0]. Then, it puts the addresses of an unallocated 2D array into the other values of p[i] for i from 1 to 9. Since the array is not allocated (or only partially - p[0] is allocated), this is pretty bad.

char **p;
int i;
p = realloc(p, 10*sizeof(char*));
*p = realloc(p, 10*sizeof(char));
for(i = 1; i < 10; i++)
    p[i] = p[0] + 10*i;

This second code uses realloc instead of malloc, which does not solve the previous problems, but also adds probable segmentation faults : realloc on an uninitialized pointer is a bad idea.

char **p = NULL;
int i;
p = malloc(10*sizeof(char*));
*p = malloc(10*sizeof(char));
for(i = 1; i < 10; i++)
    p[i] = realloc(p[i-1], 10*i*sizeof(char));

This third code does the same as the first one for the first part, but then uses realloc on p[i] for i starting with 0. I assume realloc deallocates the pointer you pass to it, so this is not really a good idea. And the 10*i*sizeof(char) is not a good idea either. Basically, you will have p[9] allocated with 90 char, and nothing else. And, by the way, initializing p to NULL here doesn't do anything.

char **p;
int i;
p = malloc(10*sizeof(char*));
for(i = 0; i < 10; i++)
    p[i] = malloc(10*sizeof(char));

This fourth code has something good at least : it allocates separately each p[i] for i from 0 to 9 (I assume i starts with 0 here, unlike in the other codes). So, this might be the answer you are looking for.

Finally, the question is badly formulated since none of these codes have the same semantics as a declaration like char p[10][10].

Edit :

If you want a dynamically allocated 2D array, you can use this for instance :

int i;
char **p = malloc(10 * sizeof *p);
for(i = 0; i < 10; i++)
    p[i] = malloc(10 * sizeof *p[i]);

You can also, as cmaster did, use a pointer to an array type (like char[10]). This is the exemple from cmaster : char (*p)[10].

Answer 3

Well let's see:

1. This will likely lead to errors because p[1][0] (among others) points to invalid memory locations.
2. This is undefined behavior because you pass an uninitialized pointer to realloc().
3. That code possibly leaves uninitialized pointers all over the place.
4. This code loops from [1, 10), where I would expect [0, 10). So it's also terrible.

Therefore:

All of these are terrible. The correct code is either:

char (*p)[10] = malloc(10 * sizeof(*p));

Or:

char **p = malloc(10 * sizeof(*p));
for (int i=0; i<10; ++i)
    p[i] = malloc(10 * sizeof(**p));