2d array in C with negative indices

I am writing a C-program where I need 2D-arrays (dynamically allocated) with negative indices or where the index does not start at zero. So for an array[i][j] the row-index i should take values from e.g. 1 to 3 and the column-index j should take values from e.g. -1 to 9.

For this purpose I created the following program, here the variable columns_start is set to zero, so just the row-index is shifted and this works really fine.

But when I assign other values than zero to the variable columns_start, I get the message (from valgrind) that the command "free(array[i]);" is invalid. So my questions are:

1. Why it is invalid to free the memory that I allocated just before?
2. How do I have to modify my program to shift the column-index?

Thank you for your help.

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

main()
{

int **array, **array2;
int rows_end, rows_start, columns_end, columns_start, i, j;

rows_start = 1;
rows_end = 3;

columns_start = 0;
columns_end = 9;

  array = malloc((rows_end-rows_start+1) * sizeof(int *));

  for(i = 0; i <= (rows_end-rows_start); i++) {
    array[i] = malloc((columns_end-columns_start+1) * sizeof(int));
  }

  array2 = array-rows_start;                          //shifting row-index

  for(i = rows_start; i <= rows_end; i++) {
    array2[i] = array[i-rows_start]-columns_start;    //shifting column-index
  }

  for(i = rows_start; i <= rows_end; i++) {
    for(j = columns_start; j <= columns_end; j++) {
      array2[i][j] = i+j;                             //writing stuff into array
      printf("%i %i %d\n",i, j, array2[i][j]);
    }
  }

  for(i = 0; i <= (rows_end-rows_start); i++) {
    free(array[i]);
  }

  free(arra开发者_运维百科y);

}

When you shift column indexes, you assign new values to original array of columns: in

array2[i] = array[i-rows_start]-columns_start;

array2[i] and array[i=rows_start] are the same memory cell as array2 is initialized with array-rows_start.

So deallocation of memory requires reverse shift. Try the following:

free(array[i] + columns_start);

IMHO, such modification of array indexes gives no benefit, while complicating program logic and leading to errors. Try to modify indexes on the fly in single loop.

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

int main(void) {
    int a[] = { -1, 41, 42, 43 };
    int *b;//you will always read the data via this pointer
    b = &a[1];// 1 is becoming the "zero pivot"
    printf("zero: %d\n", b[0]);
    printf("-1: %d\n", b[-1]);
    return EXIT_SUCCESS;
}

If you don't need just a contiguous block, then you may be better off with hash tables instead.

As far as I can see, your free and malloc looks good. But your shifting doesn't make sense. Why don't you just add an offset in your array instead of using array2:

int maxNegValue = 10;
int myNegValue = -6;

array[x][myNegValue+maxNegValue] = ...;

this way, you're always in the positive range.

For malloc: you acquire (maxNegValue + maxPosValue) * sizeof(...)

Ok I understand now, that you need free(array.. + offset); even using your shifting stuff.. that's probably not what you want. If you don't need a very fast implementation I'd suggest to use a struct containing the offset and an array. Then create a function having this struct and x/y as arguments to allow access to the array.

I don't know why valgrind would complain about that free statement, but there seems to be a lot of pointer juggling going on so it doesn't surprise me that you get this problem in the first place. For instance, one thing which caught my eye is:

array2 = array-rows_start; 

This will make array2[0] dereference memory which you didn't allocate. I fear it's just a matter of time until you get the offset calcuations wrong and run into this problem.

One one comment you wrote

but im my program I need a lot of these arrays with all different beginning indices, so I hope to find a more elegant solution instead of defining two offsets for every array.

I think I'd hide all this in a matrix helper struct (+ functions) so that you don't have to clutter your code with all the offsets. Consider this in some matrix.h header:

struct matrix; /* opaque type */

/* Allocates a matrix with the given dimensions, sample invocation might be:
 *
 *    struct matrix *m;
 *    matrix_alloc( &m, -2, 14, -9, 33 );
 */
void matrix_alloc( struct matrix **m, int minRow, int maxRow, int minCol, int maxCol );

/* Releases resources allocated by the given matrix, e.g.:
 *
 *    struct matrix *m;
 *    ...
 *    matrix_free( m );
 */
void matrix_free( struct matrix *m );

/* Get/Set the value of some elment in the matrix; takes logicaly (potentially negative)
 * coordinates and translates them to zero-based coordinates internally, e.g.:
 *
 *    struct matrix *m;
 *    ...
 *    int val = matrix_get( m, 9, -7 );
 */
int matrix_get( struct matrix *m, int row, int col );
void matrix_set( struct matrix *m, int row, int col, int val );

And here's how an implementation might look like (this would be matrix.c):

struct matrix {
  int minRow, maxRow, minCol, maxCol;
  int **elem;
};

void matrix_alloc( struct matrix **m, int minCol, int maxCol, int minRow, int maxRow ) {
  int numRows = maxRow - minRow;
  int numCols = maxCol - minCol;

  *m = malloc( sizeof( struct matrix ) );
  *elem = malloc( numRows * sizeof( *elem ) );
  for ( int i = 0; i < numRows; ++i )
    *elem = malloc( numCols * sizeof( int ) );

  /* setting other fields of the matrix omitted for brevity */
}

void matrix_free( struct matrix *m ) {
  /* omitted for brevity */
}

int matrix_get( struct matrix *m, int col, int row ) {
   return m->elem[row - m->minRow][col - m->minCol];
}

void matrix_set( struct matrix *m, int col, int row, int val ) {
   m->elem[row - m->minRow][col - m->minCol] = val;
}

This way you only need to get this stuff right once, in a central place. The rest of your program doesn't have to deal with raw arrays but rather the struct matrix type.