I have this C program that rotates a character matrix. This is a straightforward rewrite of this Java implementation. Both versions do additional $ \Theta(mn)$ preprocessing and require $ \Theta(mn)$ additional space in order to run arbitrary rotations in $ \Theta((m + n) \min (m, n)) = \Theta(\max(m, n)\min(m, n)) = \Theta(mn)$ time.

rotable_char_matrix.h

#ifndef ROTABLE_CHAR_MATRIX_H #define ROTABLE_CHAR_MATRIX_H  #include <stdlib.h>  typedef struct rotation_list_node {     size_t x;     size_t y;     struct rotation_list_node* prev;     struct rotation_list_node* next; } rotation_list_node;  typedef struct rotable_char_matrix {     size_t rows;     size_t cols;     size_t number_of_rotation_lists;     size_t buffer_capacity;     size_t buffer_size;     char* data;     char* buffer;     rotation_list_node** rotations_list_heads;     size_t* rotation_list_lengths; } rotable_char_matrix;  /******************************** * Initializes a rotable matrix. * ********************************/ void rotable_char_matrix_init(rotable_char_matrix* matrix,                               size_t rows,                               size_t columns);  /****************************************** * Releases all the resources of a matrix. * ******************************************/ void rotable_char_matrix_clean(rotable_char_matrix* matrix);  /*********************************************** * Reads an individual character from a matrix. * ***********************************************/ char rotable_char_matrix_get(rotable_char_matrix* matrix,                              size_t x,                              size_t y);  /********************************************************* * Writes a character at a particular spot in the matrix. * *********************************************************/ void rotable_char_matrix_set(rotable_char_matrix* matrix,                              size_t x,                              size_t y,                              char value);  /************************************************************************** * Rotates the entire matrix 'abs(count)' steps. Positive value of 'count' * * rotates clockwise, negative value of 'count' rotates counter-clockwise. * **************************************************************************/ void rotable_char_matrix_rotate(rotable_char_matrix* matrix,                                 int count);  /*********************************************** * Returns the number of columns in the matrix. * ***********************************************/ size_t rotable_char_matrix_columns(rotable_char_matrix* matrix);  /******************************************** * Returns the number of rows in the matrix. * ********************************************/ size_t rotable_char_matrix_rows(rotable_char_matrix* matrix);  #endif /* ROTABLE_CHAR_MATRIX_H */ 

rotable_char_matrix.c

#include "rotable_char_matrix.h" #include <stdlib.h> #define MIN(X,Y) (((X) < (Y)) ? (X) : (Y))  /******************************************************** * Checks that the number of requested rows is not zero. * ********************************************************/ static void check_number_of_rows(size_t rows) {     if (rows == 0)     {         abort();     } }  /*********************************************************** * Checks that the number of requested columns is not zero. * ***********************************************************/ static void check_number_of_cols(size_t cols) {     if (cols == 0)     {         abort();     } }  /******************************************************************************* * Populate the 'rotation_list_index'th rotation list. The list with index zero * * is the outermost.                                                            * *******************************************************************************/ static void populate_rotation_list_at_index(rotable_char_matrix* matrix,                                             size_t rotation_list_index) {     rotation_list_node* previous_node = NULL;     rotation_list_node* current_node;     size_t x;     size_t y;      for (x = rotation_list_index; x != matrix->cols - rotation_list_index; x++)     {         current_node = malloc(sizeof(*current_node));         current_node->x = x;         current_node->y = rotation_list_index;          if (previous_node == NULL)         {             matrix->rotations_list_heads[rotation_list_index] = current_node;         }         else         {             previous_node->next = current_node;             current_node->prev = previous_node;         }          previous_node = current_node;     }      for (y = rotation_list_index + 1;          y != matrix->rows - rotation_list_index - 1;          y++)     {         current_node = malloc(sizeof(*current_node));         current_node->x = matrix->cols - rotation_list_index - 1;         current_node->y = y;         previous_node->next = current_node;         current_node->prev = previous_node;         previous_node = current_node;     }      for (x = matrix->cols - rotation_list_index - 1;          x > rotation_list_index;          x--)     {         current_node = malloc(sizeof(*current_node));         current_node->x = x;         current_node->y = matrix->rows - rotation_list_index - 1;         previous_node->next = current_node;         current_node->prev = previous_node;         previous_node = current_node;     }      /**************************************************************************     * If in the above loop 'rotation_list_index' is zero, the loop will never *     * terminate. For this reason, we "unroll" the last iteration out of it.   *     **************************************************************************/     current_node = malloc(sizeof(*current_node));     current_node->x = rotation_list_index;     current_node->y = matrix->rows - rotation_list_index - 1;     previous_node->next = current_node;     current_node->prev = previous_node;     previous_node = current_node;      for (y = matrix->rows - rotation_list_index - 2;          y > rotation_list_index;          y--)     {         current_node = malloc(sizeof(*current_node));         current_node->x = rotation_list_index;         current_node->y = y;         previous_node->next = current_node;         current_node->prev = previous_node;         previous_node = current_node;     }      previous_node->next = matrix->rotations_list_heads[rotation_list_index];     matrix->rotations_list_heads[rotation_list_index]->prev = previous_node;     matrix->rotation_list_lengths[rotation_list_index] =         2 * (matrix->cols - 2 * rotation_list_index) +         2 * (matrix->rows - 2 * (rotation_list_index + 1)); }  /************************************************** * Populates all the rotation lists of the matrix. * **************************************************/ static void populate_rotation_lists(rotable_char_matrix* matrix) {     size_t rotation_list_index;      for (rotation_list_index = 0;          rotation_list_index != matrix->number_of_rotation_lists;          rotation_list_index++)     {         populate_rotation_list_at_index(matrix, rotation_list_index);     } }  /******************************** * Initializes a rotable matrix. * ********************************/ void rotable_char_matrix_init(rotable_char_matrix* matrix,                               size_t rows,                               size_t cols) {     if (matrix != NULL)     {         check_number_of_rows(rows);         check_number_of_cols(cols);         matrix->rows = rows;         matrix->cols = cols;         matrix->data = calloc(rows * cols, sizeof(char));         matrix->buffer_capacity = rows + cols - 2;         matrix->buffer = malloc(sizeof(char) * (matrix->buffer_capacity));         matrix->buffer_size = 0;         matrix->number_of_rotation_lists = MIN(rows / 2, cols / 2);         matrix->rotation_list_lengths =         malloc(matrix->number_of_rotation_lists *                sizeof(*matrix->rotation_list_lengths));          matrix->rotations_list_heads =         malloc(matrix->number_of_rotation_lists *                sizeof(*matrix->rotations_list_heads));          populate_rotation_lists(matrix);     } }  /************************* * Frees a rotation list. * *************************/ static void free_single_rotation_list(rotation_list_node* head) {     rotation_list_node* current_node;     rotation_list_node* next_node;     head->prev->next = NULL;      for (current_node = head; current_node != NULL; current_node = next_node)     {         next_node = current_node->next;         free(current_node);     } }  /******************************************** * Frees all the rotation lists of a matrix. * ********************************************/ static void free_rotation_lists(rotable_char_matrix* matrix) {     size_t rotation_list_index;      for (rotation_list_index = 0;          rotation_list_index != matrix->number_of_rotation_lists;          rotation_list_index++)     {         free_single_rotation_list(                             matrix->rotations_list_heads[rotation_list_index]);     } }  /****************************************** * Releases all the resources of a matrix. * ******************************************/ void rotable_char_matrix_clean(rotable_char_matrix* matrix) {     free_rotation_lists(matrix);     free(matrix->buffer);     free(matrix->data);     free(matrix->rotation_list_lengths);     free(matrix->rotations_list_heads); }  /*********************************************** * Reads an individual character from a matrix. * ***********************************************/ char rotable_char_matrix_get(rotable_char_matrix* matrix, size_t x, size_t y) {     return matrix->data[matrix->cols * y + x]; }  /********************************************************* * Writes a character at a particular spot in the matrix. * *********************************************************/ void rotable_char_matrix_set(rotable_char_matrix* matrix,                              size_t x,                              size_t y,                              char value) {     matrix->data[matrix->cols * y + x] = value; }  /****************************************************************************** * Rotates a 'rotation_list_index'th rotation list in the matrix 'count' steps * * counter-clockwise.                                                          * ******************************************************************************/ static void rotate_rotation_list_counter_clockwise(rotable_char_matrix* matrix,                                                    size_t rotation_list_index,                                                    size_t count) {     rotation_list_node* source_node;     rotation_list_node* target_node;      source_node = matrix->rotations_list_heads[rotation_list_index];     target_node = source_node;      size_t i;      for (i = 0; i != count; i++)     {         matrix->buffer[i] = rotable_char_matrix_get(matrix,                                                     source_node->x,                                                     source_node->y);         source_node = source_node->next;     }      for (i = 0;          i != matrix->rotation_list_lengths[rotation_list_index] - count;          i++)     {         rotable_char_matrix_set(matrix,                                 target_node->x,                                 target_node->y,                                 rotable_char_matrix_get(matrix,                                                         source_node->x,                                                         source_node->y));         target_node = target_node->next;         source_node = source_node->next;     }      for (i = 0; i != count; i++)     {         rotable_char_matrix_set(matrix,                                 target_node->x,                                 target_node->y,                                 matrix->buffer[i]);          target_node = target_node->next;     } }  /****************************************************************************** * Rotates a 'rotation_list_index'th rotation list in the matrix 'count' steps * * clockwise.                                                                  * ******************************************************************************/ static void rotate_rotation_list_clockwise(rotable_char_matrix* matrix,                                            size_t rotation_list_index,                                            size_t count) {     rotation_list_node* source_node;     rotation_list_node* target_node;      source_node = matrix->rotations_list_heads[rotation_list_index];     target_node = source_node;      size_t i;      for (i = 0; i != count; i++)     {         matrix->buffer[i] = rotable_char_matrix_get(matrix,                                                     source_node->x,                                                     source_node->y);         source_node = source_node->prev;     }      for (i = 0;          i != matrix->rotation_list_lengths[rotation_list_index] - count;          i++)     {         rotable_char_matrix_set(matrix,                                 target_node->x,                                 target_node->y,                                 rotable_char_matrix_get(matrix,                                                         source_node->x,                                                         source_node->y));         target_node = target_node->prev;         source_node = source_node->prev;     }      for (i = 0; i != count; i++)     {         rotable_char_matrix_set(matrix,                                 target_node->x,                                 target_node->y,                                 matrix->buffer[i]);          target_node = target_node->prev;     } }  /******************************************************************************* * Rotates the 'rotation_list_index'th rotation list of a matrix 'count' steps. * * If count is positive, rotates clockwise. Otherwise, rotates                  * * counter-clockwise.                                                           * *******************************************************************************/ static void rotate_rotation_list(rotable_char_matrix* matrix,                                  size_t rotation_list_index,                                  int count) {     size_t current_rotation_list_length;     int count2;      current_rotation_list_length =     matrix->rotation_list_lengths[rotation_list_index];      count %= (int) current_rotation_list_length;      if (count == 0)     {         /* Nothing to do. */         return;     }      if (count < 0)     {         /* Rotate counter-clockwise. */         count = -count;         count2 = (int)(current_rotation_list_length) - count;          if (count < count2)         {             rotate_rotation_list_counter_clockwise(matrix,                                                    rotation_list_index,                                                    count);         }         else         {             rotate_rotation_list_clockwise(matrix,                                            rotation_list_index,                                            count2);         }     }     else     {         /* Rotate clockwise. */         count2 = (int)(current_rotation_list_length) - count;          if (count < count2)         {             rotate_rotation_list_clockwise(matrix,                                            rotation_list_index,                                            count);         }         else         {             rotate_rotation_list_counter_clockwise(matrix,                                                    rotation_list_index,                                                    count2);         }     } }  /************************************************************************** * Rotates the entire matrix 'abs(count)' steps. Positive value of 'count' * * rotates clockwise, negative value of 'count' rotates counter-clockwise. * **************************************************************************/ void rotable_char_matrix_rotate(rotable_char_matrix* matrix, int count) {     size_t rotation_list_index;      for (rotation_list_index = 0;          rotation_list_index != matrix->number_of_rotation_lists;          rotation_list_index++)     {         rotate_rotation_list(matrix, rotation_list_index, count);     } }  /*********************************************** * Returns the number of columns in the matrix. * ***********************************************/ size_t rotable_char_matrix_columns(rotable_char_matrix* matrix) {     return matrix->cols; }  /******************************************** * Returns the number of rows in the matrix. * ********************************************/ size_t rotable_char_matrix_rows(rotable_char_matrix* matrix) {     return matrix->rows; } 

main.c

#include "rotable_char_matrix.h" #include <stdio.h>  #define ROWS 4 #define COLS 5  static void print_matrix(rotable_char_matrix* matrix) {     size_t row;     size_t col;      for (row = 0; row != rotable_char_matrix_rows(matrix); row++)     {         for (col = 0; col != rotable_char_matrix_columns(matrix); col++)         {             printf("%c", rotable_char_matrix_get(matrix, col, row));         }          puts("");     } }  int main(int argc, const char * argv[]) {     int count;     int tokens_read;     rotable_char_matrix matrix;     rotable_char_matrix_init(&matrix, ROWS, COLS);     char c = 'a';     size_t row;     size_t col;      for (row = 0; row < ROWS; row++)     {         for (col = 0; col < COLS; col++)         {             rotable_char_matrix_set(&matrix, col, row, c++);         }     }      for (;;)     {         print_matrix(&matrix);         printf("\n> ");         tokens_read = scanf("%d", &count);          if (tokens_read != 1 || feof(stdin) || ferror(stdin))         {             break;         }          rotable_char_matrix_rotate(&matrix, count);     }      rotable_char_matrix_clean(&matrix);     return 0; } 

Critique request

I would like to hear anything that comes to mind.