Transpose tab-delimited table in C

Question

I have looked online for transposing programs, but have found that they have extreme RAM use for large tables. The RAM use is so extreme I can't run most jobs on my laptop. I also have a Perl program, this uses less memory than online tools, but the RAM use is still extreme (~50 GB RAM for a 8 GB file) or extremely slow (days to run, this takes a few seconds depending on the input size).

I have written a program in GNU99 C which works like this:

./2tranpose -i in.tsv -o out.tsv

and the source code for 2transpose.c is as follows:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define GNU_SOURCE

void help () {
    puts("This program is run thus:");
    puts("./transpose -i infile -o outfile");
}

int main(int argc, char * argv[]) {
    unsigned short int infile = 0, outfile = 0;
//I didn't like getopt's version of reading files, this is my own design
    for (unsigned short int loop = 1; loop < argc; loop++) {
        if (strcmp(argv[loop], "-i") == 0) {
            if (loop == (argc-1)) {//prevents segfault on argv
                printf("the '%s' option requires something to come after it.\n", argv[loop]);
                printf("Failed at %s line %u\n", __FILE__, __LINE__);
                exit(EXIT_FAILURE);
            }
            infile = loop+1;
            loop++;
        } else if (strcmp(argv[loop], "-o") == 0) {
            if (loop == (argc-1)) {//prevents segfault on argv
                printf("the '%s' option requires something to come after it.\n", argv[loop]);
                printf("Failed at %s line %u\n", __FILE__, __LINE__);
                exit(EXIT_FAILURE);
            }
            outfile = loop+1;
            loop++;
        } else {
            printf("%s isn't a recognized option.\n", argv[loop]);
            exit(EXIT_FAILURE);
        }
    }

    if (infile == 0) {
        puts("infile not defined.");
        help();
        exit(EXIT_FAILURE);
    }
    if (outfile == 0) {
        puts("outfile not defined.");
        help();
        exit(EXIT_FAILURE);
    }

    FILE *restrict fh = fopen(argv[infile], "r");
    if (fh == NULL) {
        printf("failed to read %s\n", argv[infile]);
        perror("");
        exit(EXIT_FAILURE);
    }

    unsigned int nrow = 0, ncol = 0;
    char *line = NULL;
    size_t len = 0;
    ssize_t read = 0;

    size_t ALL_DATA_size = sizeof(char);
    char ***restrict ALL_DATA = malloc(sizeof(char));

    while ((read = getline ( &line, &len, fh)) != -1) {
        char *restrict tmp_string = NULL;
        char * tmp_pointer = NULL;
        tmp_string = strtok_r(line, "\t ", &tmp_pointer);
        size_t this_row_size = sizeof(char) * strlen(tmp_string) + sizeof(char*);
        ALL_DATA_size += this_row_size;
        ALL_DATA       = realloc(ALL_DATA, ALL_DATA_size);
        if (ALL_DATA == NULL) {
            printf("ALL_DATA failed realloc at %s line %u at %s line %u\n", __FILE__, __LINE__, argv[infile], nrow+1);
            perror("");
            exit(EXIT_FAILURE);
        }
        ALL_DATA[nrow] = malloc(this_row_size);
        if (ALL_DATA[nrow] == NULL) {
            printf("ALL_DATA[%u] failed realloc at %s line %u at %s line %u\n", nrow, __FILE__, __LINE__, argv[infile], nrow+1);
            perror("");
            exit(EXIT_FAILURE);
        }
        ALL_DATA[nrow][0] = malloc(this_row_size);
        if (ALL_DATA[nrow][0] == NULL) {
            printf("failed to realloc ALL_DATA[%u][0] @ %s line %u\n", nrow, __FILE__, __LINE__);
            perror("");
            exit(EXIT_FAILURE);
        }
        strcpy(ALL_DATA[nrow][0], tmp_string);
        ncol = 1;
        while (tmp_string != NULL) {
            tmp_string = strtok_r(NULL, "\t ", &tmp_pointer);
            if (tmp_string == NULL) {
                break;
            }
            const unsigned int STR_LENGTH = sizeof(char)*strlen(tmp_string) + sizeof(char*);
            this_row_size += STR_LENGTH ;
            ALL_DATA_size += STR_LENGTH ;

            ALL_DATA = realloc(ALL_DATA, ALL_DATA_size);
            if (ALL_DATA == NULL) {
                printf("failed to realloc ALL_DATA for row %u @ %s line %u w/ string %s with length %u\n", nrow, __FILE__, __LINE__, tmp_string, STR_LENGTH);
                perror("");
                exit(EXIT_FAILURE);
            }
            ALL_DATA[nrow] = realloc(ALL_DATA[nrow], this_row_size);
            if (ALL_DATA[nrow] == NULL) {
                printf("failed to realloc ALL_DATA[%u] @ %s line %u\n", nrow,__FILE__, __LINE__);
                perror("");
                exit(EXIT_FAILURE);
            }
            ALL_DATA[nrow][ncol] = malloc(STR_LENGTH);
            if (ALL_DATA[nrow][ncol] == NULL) {
                printf("failed to realloc ALL_DATA[%u][%u] @ %s line %u\n", nrow, ncol, __FILE__, __LINE__);
                perror("");
                exit(EXIT_FAILURE);
            }
            strcpy(ALL_DATA[nrow][ncol], tmp_string);
            ncol++;
        }
        const unsigned int LENGTH = strlen(ALL_DATA[nrow][ncol-1]);
        if (ALL_DATA[nrow][ncol-1][LENGTH-1] == '\n') {
            ALL_DATA[nrow][ncol-1][LENGTH-1] = '\0';
        }
        nrow++;
    }
    fclose(fh);
    free(line); line = NULL;

    FILE *restrict out = fopen(argv[outfile], "w");

    if (out == NULL) {
        printf("failed to write %s\n", argv[outfile]);
        perror("");
        exit(EXIT_FAILURE);
    }

    for (unsigned int row = 0; row < ncol; row++) {
        fprintf(out, "%s", ALL_DATA[0][row]);
        for (unsigned int col = 1; col < nrow; col++) {
            fprintf(out, "\t%s", ALL_DATA[col][row]);
        }
        fprintf(out, "\n");
    }
    fclose(out);
    for (unsigned int row = 0; row < nrow; row++) {
        for (unsigned int col = 0; col < ncol; col++) {
            free(ALL_DATA[row][col]); ALL_DATA[row][col] = NULL;
        }
        free(ALL_DATA[row]); ALL_DATA[row] = NULL;
    }

    free(ALL_DATA); ALL_DATA = NULL;
    return 0;
}

from what I can tell, this program works, but I'd like to keep RAM use at a minimum (which was the goal of the program).

Overall, the program isn't complicated, it saves strings into a massive 2D array and then switches rows with columns. But, the devil is in the details.

Is this good coding style in C? perhaps this can be made more efficient?

Answer 1

when compiling, always enable the warnings, then fix those warnings. ( for gcc, at a minimum use: -Wall -Wextra -Wconversion -pedantic -std=gnu11 ) The posted code causes the compiler to output several warnings.

for ease of readability and understanding:

1. follow the axiom: only one statement per line and (at most) one variable declaration per statement.
2. separate code blocks: ( for if else while do...while switch case default ) via a single blank line.
3. There are few reasons to use 'ALL CAPS' In general ALL CAPS is considered yelling. However, typical usage is with macro names and with elements of a enum statement.

===============

The function: strlen() returns a size_t (which, depending on the implementation will be either unsigned long int or unsigned int so this line:

const unsigned int LENGTH = strlen(ALL_DATA[nrow][ncol-1]);

would be better written as:

size_t length = strlen(ALL_DATA[nrow][ncol-1]);

=============

this code:

if (ALL_DATA[nrow][ncol-1][LENGTH-1] == '\n') {
        ALL_DATA[nrow][ncol-1][LENGTH-1] = '\0';
}

is very 'iffy'

suggest using a more appropriate logic, for instance:

char * newline;
EDIT: //if( strchr( ALL_DATA[nrow][ncol-1], '\n' ) )
if( (newline = strchr( ALL_DATA[nrow][ncol-1], '\n' ) ) != NULL )
{
    *newline = '\0';
}

Note: one of the functions in string.h can do this same operation in a single statement.

===========

regarding:

ALL_DATA[nrow][ncol] = malloc(STR_LENGTH);
if (ALL_DATA[nrow][ncol] == NULL) {
    printf("failed to realloc ALL_DATA[%u][%u] @ %s line %u\n", nrow, ncol, __FILE__, __LINE__);
    perror("");
    exit(EXIT_FAILURE);

the value of errno was changed by the intervening call to printf() AND all error messages should be output to stderr, not stdout so this statement:

printf("failed to realloc ALL_DATA[%u][%u] @ %s line %u\n", nrow, ncol, __FILE__, __LINE__);

should be:

fprintf( stderr, "failed to realloc ALL_DATA[%u][%u] @ %s line %u\n", nrow, ncol, __FILE__, __LINE__);

And the call to malloc() is NOT realloc ALL_DATA Rather it is trying to allocate another row in the 2 dimensional array ALL_DATA[][]

=============

When calling realloc(), always assign the returned value to a temp variable, check the temp variable to assure it is not NULL, and only then assign to the target variable. Otherwise, when the function:realloc()` fails, the original pointer will be lost, resulting in a memory leak

=================

This expression:

sizeof(char)

is defined in the standard as 1. Multiplying anything by 1 has no effect.

Usage of this expression: in:

const unsigned int STR_LENGTH = sizeof(char)*strlen(tmp_string) + sizeof(char*);

just clutters the code, making it more difficult to understand, debug, etc.

Answer 2

Here are some things that may help you improve your code.

Understand feature test macros

Feature test macros are used to provide the programmer control over definitions in system header files. As the man pages for feature_test_macros says:

NOTE: In order to be effective, a feature test macro must be defined before including any header files.

This means that your #define GNU_SOURCE should come before the #includes to be effective. Also, on my computer, that's not the right name anyway. The man pages for getline says this:

getline(), getdelim():
      Since glibc 2.10:
          _POSIX_C_SOURCE >= 200809L
      Before glibc 2.10:
          _GNU_SOURCE

Break the program into smaller routines

In the current code, everything is done in main. That makes the code harder to understand and maintain. Instead, break the code into manageable logical functions. For instance, the command line argument interpretation for infile and outfile is nearly identical. Instead, I'd recommend calling a function which returns a const char * which is the file name. (For that matter, I'd probably just use infile = argv[1] and outfile = argv[2] eliminating all need for command line parsing.) A first rewrite of your code looks now looks like this:

int main(int argc, char * argv[]) {
    if (argc != 3) {
        help();
        return 1;
    }
    unsigned rows;
    unsigned cols;
    char ***ALL_DATA = readCSV(argv[1], &rows, &cols);
    writeCSV(argv[2], ALL_DATA, rows, cols);
}

Don't leak memory

This program leaks memory because not every call to malloc is faithfully matched to a call to free. That should be fixed.

Understand the C standard

In the C standard, sizeof(char) is defined as 1. Always. So having sizeof(char) sprinkled throughout your code only makes the code harder to read.

Use better variable names

The names row and col are good because they are descriptive of the intent, but names like fh and ALL_DATA are not. Additionally, traditionally, a name in all caps such as ALL_DATA would signify a macro definition. I'd recommend choosing a consistent naming scheme and using it.

Understand the restrict keyword

There's little point to using restrict in most of the places it's currently used. Understand that it's intended to be a compiler optimization hint, but that it also puts the onus on you, the programmer, to assure that there are no aliases for pointers that would violate the meaning of restrict.

Use named constants

Buried deep within the code is the fact that the delimiters are actually both a tab and a space character. I'd make that a lot more obvious by creating a named constant like this:

static const char *delimiters = "\t ";

Gracefully handle input data

One problem with the use of strtok_r in this context is that, as mentioned in the man page,

a sequence of two or more contiguous delimiter bytes in the parsed string is considered to be a single delimiter

This means that if there are any empty fields in the input file, the program will probably crash because it will attempt to dereference an unitialized memory location. One could use the BSD-style non-standard routine strsep or write your own equivalent.

Consider a different algorithm

The current program stores the entire parsed file in memory at once, so the larger the file, the larger the memory use. An alternative, inspired from back in the days when data was stored on 9-track tapes and 32K of memory was "large" is to trade off memory use for I/O speed. So instead of reading the file once and then writing everything out, the old school method would be to process the input data multiple times; each time through pick out only the field of interest. Alternatively, create one output file per column, appending data to each as you go, and then concatenate all of the files together at the end.