C - Sorting a dynamically sized array of strings

Question

I'm quite new to C and trying to read an input stream of data from a file, appending it to a dynamically sized array, which works well to that point. After that, I want to sort the array alphabetically. I read the manpages of strcmp and think it's the best way to do this. However, I get hit by a "Segmentation Fault" whenever i'm trying to execute it. What exactly am I doing wrong when allocating the memory? Here is my code for reference:

int main (int argc, char* argv[]) {
    int c = getLineCount();

    FILE * wordlist = fopen("test", "r");
    // If file doesn't exist, handle error
    if ( wordlist == NULL ) {
        fputs("Unable to open input file", stderr);
        exit(1);
    }

    int length = 101;
    char line[length];
    int i = 0;
    char **words = malloc(c * sizeof(line));
    if ( words == NULL ) {
        fputs("Unable to allocate Memory", stderr);
        exit(1);
    }

    while (1) {
        char *l = fgets(line, length, wordlist);
        
        if ( (l == NULL) ) {
            // Check if EOF is reached
            if (feof(wordlist)) {
                // fputs("--- EOF ---\n", stdout);
                break;
            // Check if error occured while reading
            } else {
                fputs("Error reading file", stderr);
                exit(1);
            }
        } else if (strchr(line, '\n') == NULL) {
            // Check if line is too long
            // Iterate until newline is found or until EOF
            int c;
            while((c = fgetc(wordlist)) != '\n' && c != 0);
            fputs("--- LINE TOO LONG ---\n", stderr);
            continue;
        } else if ( line[0] == '\n' ) {
            // Check if line is only "\n", if yes, ignore the line
            continue;
        } else {
            words[i] = malloc(sizeof(line) * sizeof(char));
            if ( words[i] == NULL ) {
                fputs("Unable to allocate Memory", stderr);
                exit(1);
            }
            strcpy(words[i], line);
            i++;
        }
    }
    // Close file
    fclose(wordlist);

    char temp[101];
    for (int i = 0; i < (length-1); i++) {
        int lowest = i;
        for (int j = i+1; j < length; j++) {
            if (strcmp(words[j], words[lowest]) < 0) {
                lowest = j;
            }
        }
        if (lowest != i) {
            strcpy(temp, words[i]);
            words[i] = words[lowest];
            free(words[lowest]);
            words[lowest] = malloc(sizeof(temp) * sizeof(char));
            if ( words[lowest] == NULL ) {
                fputs("Unable to allocate Memory", stderr);
                exit(1);
            }
            strcpy(words[lowest], temp);
        }
    }

    // Print out array
    fputs("--- ARRAY ---\n\n", stdout);
    for (int i = 0; i < c; i++) {
        fputs(words[i], stdout);
    }
    
    exit(0);
}

What is getLineCount? Please post a Minimal, Reproducible Example. — Oka
– Oka, Commented May 7, 2022 at 15:38
It represents the number of valid lines in the input file im reading, for a file with the content Line1\nLine2\nLine3\0 getLineCount would return 3. I'm using it just to determine the size I need for the words array. — 1111moritz
– 1111moritz, Commented May 7, 2022 at 15:47
You should really add its implementation, and the appropriate header files, to the question (again, creating an MRE). Otherwise, we cannot make fully informed statements about the issue - instead relying on educated guesses, which may only be partially correct. — Oka
– Oka, Commented May 7, 2022 at 16:05

Oka · Accepted Answer · 2022-05-08 18:07:44Z

The upper bounds of the sorting algorithm is length, which is incorrect, as length is the size of the input line buffer.

for (int i = 0; i < (length-1); i++) {

The upper bounds should be i from the outer scope here, as it is incremented when a new line is added to the array:

strcpy(words[i], line);
i++;

This upper bounds

for (int i = 0; i < c; i++) {

should be changed as as well, as the number of valid lines might not match the number of expected lines.

Don't forget to free your memory after you are done with it.

These two lines quickly create a memory leak (original pointer value of words[i] is lost), and then set up a use-after-free bug, since the new value of words[i] is the same pointer value as words[lowest], which is freed.

words[i] = words[lowest];
free(words[lowest]);

There is no need for the extra buffer, the (de)allocations, and the string copying here. Just swap the pointer values like you would if you were sorting an array of integers, for example.

char *tmp = words[i];
words[i] = words[lowest];
words[lowest] = tmp;

Here is a common cursory example, without error handling, using strdup. It should illustrate swapping pointer values, and determining the length of the array.

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

#define MAX_LINES 256

int main(void) {
    char line[4096];
    char **lines = malloc(sizeof *lines * MAX_LINES);
    size_t len = 0;

    while (len < MAX_LINES && fgets(line, sizeof line, stdin))
        lines[len++] = strdup(line);

    for (size_t i = 0; i < len - 1; i++) {
        size_t lowest = i;

        for (size_t j = i + 1; j < len; j++)
            if (strcmp(lines[j], lines[lowest]) < 0)
                    lowest = j;

        if (lowest != i) {
            char *tmp = lines[i];
            lines[i] = lines[lowest];
            lines[lowest] = tmp;
        }
    }

    for (size_t i = 0; i < len; i++) {
        printf("%s", lines[i]);
        free(lines[i]);
    }

    free(lines);
}

stdin:

one
two
hello
foo
world
^D

stdout:

foo
hello
one
two
world

Collectives™ on Stack Overflow

C - Sorting a dynamically sized array of strings

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related