malloc

[UFP2161]

You might want to replace:
[c]char **x = (char**)malloc(5);[/c]
with
[c]char **x = (char**)malloc(5*sizeof(char*));[/c]

A pointer takes up (on most 32-bit systems) 4 bytes, not 1. Otherwise, yes that is how you should free memory.

[zoranh]

Straight forward technique has already been shown:

Code: Select all

#define ROWS 10
#define COLS 5

int **ppnMatrix = (int**)calloc(ROWS, sizeof(int));
for (int i = 0; i < ROWS; i++)
    ppnMatrix[i] = (int*)calloc(COLS, sizeof(int));

// now destroy it:
for (i = 0; i < ROWS; i++)
    free((void*)ppnMatrix[i]);
free((void*)ppnMatrix);

This solution is OK in most of situations, but not that good when ROWS is relatively large (e.g. for 1000, this takes on OnlineJudge about 100 milliseconds to execute!), and also when you need to initialize the matrix, say with all zeros.

Here follows the solution where whole matrix is allocated as one memory block.

Code: Select all

#define ROWS 1000
#define COLS 1000

int **ppnMatrix = (int**)calloc(ROWS, sizeof(int**));
for (int i = 0; i < COLS; i++)
    ppnMatrix[i] = (i == 0 ? (int*)calloc(ROWS * COLS, sizeof(int)) : ppnMatrix[i - 1] + COLS);

// init with all zeros
memset(ppnMatrix[0], 0, ROWS * COLS * sizeof(int));

// now destroy it:
free((void*)ppnMatrix[0]);
free((void*)ppnMatrix);

This works on the OnlineJudge in almost-zero time, and can be used with very large matrices, e.g. with dozens of thousands of rows.

[jakabjr]

a very interesting thing i've never seen b4 was the

int **a = (int **)calloc(10*10,sizeof(int));

a[0][2]=3

yes, triky way to get rid of some sintax, but let's see what happens, actually.
The "sintactic sugar for pointer arith" that moebius was talking about is somethig like a = *(a+i), where a is an adress and i is the offset from that adress (this is why u can write 3[a], which is a[3]).
in this line of reasoning, a[0][2] = *(a[0]+2) = *(*(a+0)+2).

So
int **a = (int **)calloc(10*10,sizeof(int)); is the same with
int **a = (int **)calloc(100,sizeof(int));, which means it allocates 100 ints and a is pointing to that zone. normally, u can use a[0][99] here to acces the last element.
u can even send this allocated pointer, a, to a function as an int** without any problems.

but what happens if u try to acces a[1]?
well, IMO, this is *(*(a+1)+i). but *(a+1) is the next int* after *a (a[0]), which points to nothing or something invalid. Therefore, zoranh's way to alloc is the valid one since it also takes care of the *a array.

FunkyELF wrote:
sorry for the n00bish question, but if I use the following code

[c:1:ab58cf01ea]int **array = (int**)calloc(ROWS, sizeof(int*));
for(i=0; i<ROWS;i++)
array = (int*)calloc(COLS,sizeof(int));[/c:1:ab58cf01ea]

and I wanted to iterate through this array[][]....which set of []'s would be associated with ROWS, and which with COLS. I tried to find out, setting ROWS to 1 and COLS to 600 and tried assigning and accessing array[0][599], and then array[599][0] and it let me do both even though one of these should be illegal. Not the best way to test it I know.

well, since u are allocating the columns separately, the compiler might decide to store them separately, so u cannot treat them as if they came one after the other. even though u might get no segmentation fault (because the size is rather small), this is not safe.
My point is that both uses are wrong.

PS: just to be clear, an allocated pointer is NOT an array, it is a pointer. It is generally called an array because it has the same behaviour.