Matrix transposition: Difference between revisions

Line 232:

Playing more to C's strengths, the following implementation transposes a matrix of any type and dimensions

in place with only O(1) space. See the [[wp:In-place_matrix_transposition|Wikipedia article]] for more information.

⚫

<lang c>void *transpose_matrix(void *matrix, int rows, int cols, size_t item_size)

<lang c>void

⚫

*transpose_matrix(matrix,rows,cols,item_size)

void *matrix;

⚫

~~int~~ ~~rows;~~

int cols;

size_t item_size;

{

#define ALIGNMENT 16 /* power of 2 >= minimum array boundary alignment; maybe unnecessary but machine dependent */

Line 243:

Line 238:

char *cursor;

char carry[ALIGNMENT];

size_t block_size,remaining_size;

size_t block_size, remaining_size;

int nadir,lag,orbit,ents;

int nadir, lag, orbit, ents;

if ((rows == 1) ? ~~1 : (~~cols == 1))

if (rows == 1 || cols == 1)

return matrix;

ents = rows * cols;

cursor = (char *) matrix;

remaining_size = item_size;

block_size = ((ALIGNMENT < remaining_size) ? ALIGNMENT : remaining_size);

while ((block_size = ALIGNMENT < remaining_size ? ALIGNMENT : remaining_size))

{

⚫

~~while~~ (block_size)

⚫

nadir = 1; /* first and last entries are always fixed points so aren't visited */

⚫

while (nadir + 1 < ents)

{

⚫

memcpy(carry, &cursor[(lag = nadir) * item_size], block_size);

⚫

nadir = 1; /* first and last entries are always fixed points so aren't visited */

⚫

while ((orbit = lag / rows + cols * (lag % rows)) > nadir) /* follow a complete cycle */

⚫

while (nadir + 1 < ents)

{

memcpy(~~carry,~~&(cursor[(lag = ~~nadir)~~ * item_size]),block_size);

memcpy(&cursor[lag * item_size], &cursor[orbit * item_size], block_size);

⚫

lag = orbit;

⚫

while ((orbit = (lag / rows) + cols * (lag % rows)) > nadir) /* follow a complete cycle */

{

}

memcpy(&(cursor[lag * item_size]),~~&(cursor[orbit~~ * ~~item_size]),~~block_size);

memcpy(&cursor[lag * item_size], carry, block_size);

~~lag~~ = ~~orbit~~;

orbit = nadir++;

while (orbit < nadir && nadir + 1 < ents) /* find the next unvisited index by an exhaustive search */

⚫

}

⚫

{

⚫

memcpy(&(cursor[lag * item_size]~~),carry~~,block_size);

orbit = nadir++;

orbit = nadir;

while ((orbit < ~~nadir)~~ ? ~~(nadir~~ + 1 < ~~ents)~~ : 0) ~~/* find the next unvisited index by an exhaustive search */~~

while ((orbit = orbit / rows + cols * (orbit % rows)) > nadir);

{

if (orbit < nadir) nadir++;

~~orbit = nadir;~~

}

while ((orbit = (orbit / rows) + cols * (orbit % rows)) > nadir);

nadir = ((orbit < nadir) ? nadir + 1 : nadir);

}

cursor = cursor + block_size;

⚫

remaining_size = ~~remaining_size -~~ block_size;

block_size = ((ALIGNMENT < remaining_size) ? ALIGNMENT : remaining_size);

}

⚫

cursor += block_size;

⚫

remaining_size -= block_size;

}

return matrix;

}</lang>