C: clever way to “shift” a matrix?

Question

I have an integer matrix that should act like a buffer:

x = {{0, 0, 0, 0, 0}, {1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}};

Now if I add a new row {3, 3, 3, 3, 3}, the new matrix should look like:

x = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}};

Is there a clever way of doing this without copying all elements around?

Answer 1

How about modulo operation?

If you access the elements as matrix[x + SZ * y] you could change it to:

matrix[x + SZ * ((y + FIRST_ROW) % SZ)] .

In this way to implement this shift you just put the new line {3, 3, 3..} where line {0, 0, 0} was, and increment the FIRST_ROW counter to point to the new starting row.

Answer 2

If your matrix is defined as an int ** and you separately allocate each row, then you would only have to swap the row pointers.

Answer 3

Use a linked list.

struct node
{
    int row[5];
    struct node *next;
};

Appending a row is as simple as walking the list to the end, then replacing the NULL next pointer with a new node (whose next pointer is NULL).

Answer 4

Can you increment x so that it points to the second row, then free the first row? Obviously, you would need to allocate a row at a time and this would not guarantee that the matrix is contiguous. If you require that, you could allocate one big block of memory to hold your matrix and then clobber the unused parts when you reach the end.

Answer 5

If you use an array of pointers to arrays (rather than an ordinary two-dimensional array), you can copy just the pointers to rows instead of copying all elements.

And if you're okay with overallocating the array of pointers, you could maybe add a new pointer to the end and advance the pointer to the "start" of the array. But this wouldn't be a good idea if you potentially want to do this sort of shift many times. And of course you'd want to make sure you have the original pointer somewhere so you can properly free() your resources.

Answer 6

Lazy to write code example - you can use modulo arithmetics to address the rows. When pushing a new row, simply increase a starting offset variable, add the matrix height and modulo the result by matrix height. This way you get a circular matrix with no need to copy the whole matrix and keeping the matrix array compact.