Monthly Archives: August 2013

Dynamically Allocated 2d Array in C-99

While trying to implement a quadratic sieve (don’t ask, was my own fault) in C, I stumbled over the problem to implement a dynamically allocated two dimensional array to store the smooth numbers while and after generating. The way I do it (which is a silly way, by the way) neither the number of rows nor the number of columns are known in advance.
What comes into ones mind in that case…yes, I know it’s not a problem in C++, you can use vectors there but C is not C++, so get back on your seat, thank you… where have I been…oh, yes, what comes into ones mind first is most probably a linked list, but speed is one of the conditions besides being not so greedy with memory, so a linked list is not the best idea. On the other side lies a much more primitive approach:

    int32_t **matrix = 0;
    int32_t limit = 0;
    for (i = 0; i < 10; i++) {
	matrix = realloc(matrix, sizeof(int32_t) * (i + 1));
	limit = (int32_t) ((rand() % 10) + 10);
	matrix[i] = realloc(matrix[i], sizeof(int32_t) * (3));
	matrix[i][0] = limit;
	for (k = 1; k < limit; k++) {
	    matrix[i] = realloc(matrix[i], sizeof(int32_t) * (k + 1));
	    matrix[i][k] = (int32_t)rand() % 10;
	    printf("%"PRIi32", ", matrix[i][k]);
	}
	puts("");
    }
    puts("");
    puts("Output;");
    for (i = 0; i < 10; i++) {
	for (k = 1; k < matrix[i][0]; k++)
	    printf("%"PRIi32", ", matrix[i][k]);
	puts("");
    }
    puts("");

Despite my use of strict bounds no such limits are necessary. It was only to show that a problem exists: where to store the sizes of the individual rows and columns? Here I store the size of the rows in the first column of each row and it is possible to do the same with the number of rows, too, of course. I have ommitted it to leave it readable.

There is something in between the linked list and the simple construct above as shown in the code below. (I do not know why the indentation is so…crude, but I have my asumptions)

Beware: this snippet uses macros heavily and checks rarely. You need to know what you are doing when you use it and if you know what you are doing you wouldn’t use it.

#include <stdlib.h>
#include <stdio.h>

#include <stdint.h>
#include <inttypes.h>

typedef struct row_t {
    size_t size;
    size_t size_max;
    uint64_t *cell;
} row_t;

typedef struct matrix_t {
    size_t size;
    size_t size_max;
    struct row_t *row;
} matrix_t;

/* No checks! Really!*/
#define row_init(row) ((row)->size = (row)->size_max = 0, (row)->cell = NULL)
#define row_get(row,i)((row)->cell[i])
#define row_pop(row) ((row)->cell[--(row)->size])

#define row_push(row, x) \
  do {\
    if ((row)->size == (row)->size_max) {	\
      (row)->size_max = ((row)->size_max)? (row)->size_max<<1 : 2;\
      (row)->cell = (uint64_t*)realloc((row)->cell, sizeof(uint64_t)\
                                                          * (row)->size_max);\
        if ((row)->cell == NULL) {\
	  fprintf(stderr, "memory allocation for cell failed");\
          exit(EXIT_FAILURE);\
        }\
    }\
    (row)->cell[(row)->size++] = (x);\
  } while (0)


#define matrix_init(mat) ((mat)->size = (mat)->size_max = 0, (mat)->row = NULL)
#define matrix_getij(mat,i,j) ( (&(mat)->row[i])->cell[j]  )
#define matrix_size(mat) ((mat)->size)
#define matrix_row_size(mat,rnum)((&mat->row[rnum])->size)
/* Let me repeat: no checks! */
#define matrix_pop(mat) \
  do{\
   (mat)->row[(mat)->size-1];\
   free((&(mat)->row[(mat)->size])->cell);\
   (mat)->size--;\
  }while(0)
#define matrix_add_row(mat,newr)\
  do{\
    if ((mat)->size == (mat)->size_max) {	\
      (mat)->size_max = (mat)->size_max? (mat)->size_max<<1 : 2;\
      (mat)->row = realloc((mat)->row, sizeof(row_t) * (mat)->size_max);\
        if ((mat)->row == NULL) {\
	  fprintf(stderr, "memory allocation for row failed");\
          exit(EXIT_FAILURE);\
        }\
    }\
      (mat)->row[(mat)->size++] = (newr);\
  }while(0);
#define matrix_free(mat)\
  do{\
   while(matrix_size(matrix)>0){\
     free((&(mat)->row[(mat)->size])->cell);\
     (mat)->size--;\
   }\
   free(mat);\
  }while(0)

int main(int argc, char **argv)
{
    int i, k;
    matrix_t *matrix;
    row_t *row;
    if (argc > 1) {
	srand((unsigned int) atoi(argv[1]));
    }
    matrix = malloc(sizeof(matrix_t));
    if (matrix == NULL) {
	fprintf(stderr, "memory allocation for matrix failed");
	exit(EXIT_FAILURE);
    }
    matrix_init(matrix);
    for (i = 0; i < rand() % 10 + 10; i++) {
	row = malloc(sizeof(row_t));
	if (row == NULL) {
	    fprintf(stderr, "memory allocation for row failed");
	    exit(EXIT_FAILURE);
	}
	row_init(row);
	for (k = 0; k < rand() % 10 + 10; k++) {
	    row_push(row, (uint64_t) (rand() % 10 + 10));
	    printf("%" PRIu64 ", ", row_get(row, k));
	}
	puts("");
	matrix_add_row(matrix, *row);
	free(row);
    }

    printf("\nmatrix size %zu\n", matrix->size);
    printf("size of second row: %zu\n\n", matrix_row_size(matrix, 1));

    for (i = 0; i < (int) matrix_size(matrix); i++) {
	for (k = 0; k < (int) matrix_row_size(matrix, i); k++)
	    printf("%" PRIu64 ", ", matrix_getij(matrix, i, k));
	puts("");
    }
    matrix_free(matrix);
    exit(EXIT_SUCCESS);
}

Instead of the simple straight arrays structures are used, one for the columns and one for the rows. So far so simple. Two different sizes get stored: the actual number of data stored and the size of the memory allocated. The memory allocated gets doubled every time when necessary, this might be a bit much for other uses. Or too little, one never knows.
It is possible to “pop” a row with the row returned and the memory free’d immediately after it. That was a condition for me, your needs may vary.

It is quite a mess and needs a cleanup, especially the pointer juggling.

Did I mentioned that not enough checks are implemented? If you do not believe me, try to exchange the variabels in matrix_getij(matrix, i, k). It may or may not segfault on you—the exact dimensions of the matrix depend on the output of libc’s pseudo-random number generator.
If you have a GCC at hand you may give it a try:

gcc -std=c99  -g3 -O3  -W -Wall -pedantic  -o testbed testbed.c