04 noviembre 2009

Crear estructuras complejas en C con malloc

Supongamos que queremos crear una estructura para almacenar matrices de cualquier tamaño en C. La estructura tiene un array bidimensional de enteros y un par de enteros indicando el tamaño horizontal y vertical de la matriz.

typedef struct {
int w, h;
int **m;
} Matrix;


La forma simple de reservar memoria para esta estructura sería:

Matrix *mat = (Matrix *) malloc(sizeof(Matrix));
mat->w = W;
mat->h = H;
mat->m = (int **) malloc(sizeof(int *)*mat->h);
for (i = 0; i < mat->h; i++)
mat->m[i] = (int *) malloc(sizeof(int)*mat->w);


Y para liberar la memoria:

for (i = 0; i < mat->h; i++)
free(mat->m[i]);
free(mat->m);
free(mat);


Otra forma mejor de reservar la memoria es hacer un malloc del tamaño total que necesitamos y luego colocar los punteros a mano.

// memoria necesaria:
// la estructura + w*h elementos + h punteros a int para almacenar
// las filas de la matriz
size_t mem_needed = sizeof(Matrix) + sizeof(int)*w*h + sizeof(int*)*h;

Matrix *mat = (Matrix *) malloc(mem_needed);

// convertir el puntero a puntero a char
char *mem = (char *) mat;
// donde empieza el array de punteros a entero
mat->m = (int **)(mem + sizeof(Matrix));
// donde empieza el array de datos
int *p = (int *) (mem + sizeof(Matrix) + sizeof(int *)*h);

int i;
for (i = 0; i < h; i++) {
mat->m[i] = p;
p += w;
}



Y para liberar la estructura nos basta con:

free(mat)


La segunda forma es más complicada de programar, necesité pasarle varias veces el valgrind hasta que conseguí que funcionara, pero en cambio tiene la ventaja que luego se libera muy fácilmente y que toda la matriz está contigua en memoria cosa que podría no ocurrir si hacemos mallocs separados para cada fila.

Es muy importante convertir la memoria reservada a (char *) para poder mover el puntero. Si a un (int *) le sumamos 1, realmente estamos moviéndonos 4 posiciones de memoria porque un int son 4 bytes.

Para estructuras más complejas es bastante difícil de conseguir implementar correctamente la segunda forma. He llegado a ver en una librería como construían de esta forma un array de 5 o 6 dimensiones cada dimensión con tamaños distintos y da un poco de miedo.