path: root/src/split_for_sort.c

/* SPDX-License-Identifier: Apache-2.0 */

/* Copyright 2025 Thorsten Töpper
 *
 * It takes quite some time for sort if it's about text files with multiple
 * gigabytes content. Split the content into buckets and afterwards sort those.
 * Once done the content of those sorted temporary files can be merged via cat.
 *
 * vim:ts=4:sw=4:expandtab
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>
#include <sys/stat.h>

#include "output.h"

/* Also used for paths => at least PATH_MAX */
#define BUFFERSIZE 4096

/* The arguments will be
 * PREFIX - file prefix...
 * SPLIT_LENGTH - the number of characters which will be relevant for file selection
 * FILES to split
 */
struct list_node {
    char *name;
    struct list_node *next;
    FILE *fd;
};

struct list_head {
    struct list_node *first;
    size_t splitlength;
    size_t length;
};

int push_into_list_unique(struct list_head *list, char *name);
int split_into_files(struct list_head *list, char *inputfile, char *prefix);
size_t list_check_length(struct list_head *list);
struct list_head *extend_list(struct list_head *list, size_t splitlength, char *fname);
struct list_node *get_node(struct list_head *list, char *name);
void destroy_list(struct list_head *list);
void fflush_list(struct list_head *list);
void print_list(struct list_head *list, FILE *out);

void destroy_list(struct list_head *list) {
    struct list_node *n = NULL, *b = NULL;
    if (list == NULL)
        return;
    n = list->first;
    while (n != NULL) {
        b = n->next;
        if (n->name != NULL) free(n->name);
        if (n->fd != NULL) fclose(n->fd);
        free(n);
        n = b;
    }
    free(list);
}

void fflush_list(struct list_head *list) {
    struct list_node *n = NULL;
    if (list == NULL) return;
    n = list->first;
    while (n != NULL) {
        if (n->fd != NULL) {
            fflush(n->fd);
        }
        n = n->next;
    }
}

void print_list(struct list_head *list, FILE *out) {
    struct list_node *n = NULL;
    if (list == NULL)
        return;
    if (out == NULL) out = stderr;
    fprintf(out, "length: %lu\n",list_check_length(list));
    n = list->first;
    while (n != NULL) {
        fprintf(out, "node '%s' %s\n", n->name,
            ((n->fd != NULL) ? "open file descriptor" : ""));
        n = n->next;
    }
}

inline size_t list_check_length(struct list_head *list) {
    size_t l = 0;
    struct list_node *ptr = NULL;
    if (list == NULL) {
        LOGERR("ERROR: No list given.\n");
        return 0;
    }
    ptr = list->first;
    while (ptr != NULL) {
        l++;
        ptr = ptr->next;
    }
    list->length = l;
    return l;
}

inline int push_into_list_unique(struct list_head *list, char *name) {
    size_t name_length = 0;
    struct list_node *ptr = NULL, *tmp = NULL;
    if (list == NULL || name == NULL || name[0] == '\0') {
        LOGERR("ERROR: Invalid function arguments.\n");
        return -1;
    }
    ptr = list->first;
    while (ptr != NULL) {
        if (strcmp(ptr->name, name) == 0) {
            return 0;
        }
        ptr = ptr->next;
    }

    if ((tmp = calloc(1, sizeof(struct list_node))) == NULL) {
        LOGERR("ERROR: Failed to allocate memory for new node\n");
        return -2;
    }

    name_length = strlen(name);
    if ((tmp->name = calloc(name_length+1, sizeof(char))) == NULL) {
        LOGERR("ERROR Failed to allocate %lu bytes for data in list\n", strlen(name)+1);
        free(tmp);
        return -3;
    }
    memcpy(tmp->name, name, name_length);
    tmp->fd = NULL;
    tmp->next = list->first;
    list->first = tmp;
    list->length++;
    return 0;
}

inline struct list_node *get_node(struct list_head *list, char *name) {
    struct list_node *n = NULL;
    if (list == NULL || name == NULL || name[0] == '\0') {
        LOGERR("ERROR: Invalid arguments\n");
        return NULL;
    }

    n = list->first;
    while (n != NULL) {
        if (strcmp(n->name, name) == 0)
            return n;
        n = n->next;
    }

    return NULL;
}

/* Open the given file and extend / create a list of output filenames,
 * based on the read content.
 * splitlength - the length of a line considered regarding the comparision.
 */
struct list_head *extend_list(struct list_head *list, size_t splitlength, char *fname) {
    FILE *fd = NULL;
    char *line = NULL, *previous = NULL;
    size_t i = 0, len = 0;

    if (fname == NULL || fname[0] == '\0' || splitlength == 0) {
        LOGERR("ERROR: filename or splitlength invalid\n");
        return NULL;
    }

    if ((fd=fopen(fname, "r")) == NULL) {
        LOGERR("ERROR: Failed to open file '%s': %s\n", fname, strerror(errno));
        return NULL;
    }

    if ((line = calloc(BUFFERSIZE, sizeof(char))) == NULL) {
        LOGERR("ERROR: Failed to allocate memory for read buffer\n");
        fclose(fd);
        return NULL;
    }

    if ((previous = calloc(BUFFERSIZE, sizeof(char))) == NULL) {
        LOGERR("ERROR: Failed to allocate memory for read buffer\n");
        free(line);
        fclose(fd);
        return NULL;
    }

    if ((list == NULL) && \
        ((list = calloc(1, sizeof(struct list_head))) == NULL)) {
            LOGERR("ERROR: Failed to create new list");
            free(line);
            fclose(fd);
            return NULL;
    }

    list->splitlength = splitlength;

    while (fgets(line, BUFFERSIZE, fd) != NULL) {
        len = strlen(line);
        len = (splitlength < len) ? splitlength : len;
        /* most simple way to stick with FS compatible characters */
        for (i=0; i<len; i++) {
            if (! isalnum(line[i]) ) {
                line[i] = '_';
            }
        }
        line[len] = '\0';
        if (strncmp(line, previous, splitlength) != 0) {
            if (push_into_list_unique(list, line) != 0) {
                LOGERR("WARNING: Failed to insert '%s' into list.\n", line);
                continue;
            }
            strncpy(previous, line, splitlength);
        }
    }

    fclose(fd);
    free(line);
    free(previous);

    return list;
}

/* Parse the inputfile and split it's content into the given list of targets
 * with the prefix for the name of the target.
 */
int split_into_files(struct list_head *list, char *inputfile, char *prefix) {
    FILE *fdin = NULL;
    char *line = NULL, *filename = NULL, *line_head = NULL, *prev_head = NULL;
    size_t i = 0, len=0, sl = 0;
    struct list_node *node = NULL;


    if (inputfile == NULL || strlen(inputfile) == 0) {
        LOGERR("ERROR: no valid filename for input.\n");
        return -1;
    }
    if (list == NULL) {
        LOGERR("ERROR: No list regarding output files given\n");
        return -1;
    }

    if ((line = calloc(BUFFERSIZE, sizeof(char))) == NULL) {
        LOGERR("ERROR: Failed to allocate memory for input buffer.\n");
        return -2;
    }
    if ((line_head = calloc(BUFFERSIZE, sizeof(char))) == NULL) {
        LOGERR("ERROR: Failed to allocate memory for input buffer.\n");
        free(line);
        return -2;
    }
    if ((prev_head = calloc(BUFFERSIZE, sizeof(char))) == NULL) {
        LOGERR("ERROR: Failed to allocate memory for input buffer.\n");
        free(line);
        free(line_head);
        return -2;
    }
    if ((filename = calloc(BUFFERSIZE, sizeof(char))) == NULL) {
        LOGERR("ERROR: Failed to allocate memory for input buffer.\n");
        free(line);
        free(line_head);
        free(prev_head);
        return -2;
    }

    if ((fdin = fopen(inputfile, "r")) == NULL) {
        LOGERR("ERROR: Failed to open file '%s' to read: %s\n",
                inputfile, strerror(errno));
        free(filename);
        free(line);
        free(line_head);
        free(prev_head);
        return -3;
    }

    /* Optical attraction: work action happens below */
    sl = list->splitlength;
    while (fgets(line, BUFFERSIZE, fdin) != NULL) {
        strncpy(line_head, line, sl+1);
        len = strnlen(line_head, sl);
        len = (len<sl) ? len : sl;
        for (i=0; i<len; i++) {
            if (! isalnum(line_head[i]) ) {
                line_head[i] = '_';
            }
        }
        line_head[len] = '\0';

        /* Gain performance if some files are partly sorted */
        if (strcmp(line_head, prev_head) != 0) {
            node = get_node(list, line_head);
            if (node == NULL) {
                LOGERR("WARNING: no node found for %s - skip line\n", line_head);
                continue;
            }

            /* keep the file descriptors open across the input files to be split */
            if (node->fd == NULL) {
                snprintf(filename, BUFFERSIZE, "%s%s", ((prefix==NULL)?"":prefix), node->name);
                if ((node->fd = fopen(filename, "w")) == NULL) {
                    LOGERR("ERROR: Failed to open file '%s': %s\n", filename, strerror(errno));
                    free(line);
                    free(line_head);
                    free(filename);
                    fclose(fdin);
                    return -4;
                }
            }
            strncpy(prev_head, line_head, sl);
        }

        if (fputs(line, node->fd) == EOF) {
            LOGERR("ERROR: Failed to write into output file for '%s': %s\n",
                    line_head, strerror(errno));
            free(line);
            free(line_head);
            free(filename);
            fclose(fdin);
            return -5;
        }
    }

    fflush_list(list);
    fclose(fdin);
    free(line);
    free(line_head);
    free(filename);
    return 0;
}

int main(int argc, char **argv) {
    int i = 3;
    size_t splitlength = 0;
    struct list_head *list = NULL;

    if (argc < 4) {
        fprintf(stderr, "Usage: %s prefix length files...\n\n", argv[0]);
        fprintf(stderr, "\tprefix - used with the output filenames\n"
                        "\tlength - the number of characters relevant for comparing\n");
        return EXIT_FAILURE;
    }

    splitlength = strtoull(argv[2], NULL, 10);
    if (splitlength == 0) {
        LOGERR("ERROR: Failed to read valid length from argument '%s' base 10 number >=1 expected\n", argv[2]);
        return EXIT_FAILURE;
    }

    for (i=3; i<argc; i++) {
//        fprintf(stderr, "=> Scan '%s' for bucket filenames\n", argv[i]);
        list = extend_list(list, splitlength, argv[i]);
    }

    for (i=3; i<argc; i++) {
//        fprintf(stderr,"=> Split '%s' into bucket files\n", argv[i]);
        if (split_into_files(list, argv[i], argv[1]) < 0) {
            destroy_list(list);
            return EXIT_FAILURE;
        }
    }

    destroy_list(list);

    return EXIT_SUCCESS;
}