5
\$\begingroup\$

Given a list of strings (say a text file containing some C symbols: c-symbols.txt), the program can:

  1. Generate a graph of the underlying trie (-p/--prefix can be specified to inspect a specific prefix subtree) with Graphviz dot:
» time ./trie --prefix at --svg c-symbols.txt  

./trie --prefix at --svg c-symbols.txt 0.74s user 0.10s system 95% cpu 0.879 total 

Output Image:

Output Graph

(The green ones indicate terminal nodes.)

  1. Suggest completions for a given prefix:
» time ./trie -c at c-symbols.txt

at_quick_exit
atan
atan2
atan2d
atan2d128
atan2d32
atan2d64
atan2f
atan2l
atan2pi
atan2pid
atan2pid128
atan2pid32
atan2pid64
atan2pif
[94 more results...]

./trie -c at c-symbols.txt 0.00s user 0.01s system 76% cpu 0.018 total

With -s/--svg, the transient file graph.dot can be saved by specifying the -k/--keep flag.

»  cat graph.dot

digraph Trie {
    node [fillcolor=lightblue,style=filled,arrowhead=vee,color=black]
    Node_167 [label=at]
    Node_248 [label=A]
    Node_0 -> Node_248 [label=A]
    Node_63 [label=_]
    Node_0 -> Node_63 [label=_]
    Node_1 [label=a]
    Node_0 -> Node_1 [label=a]
    Node_2 [label=b]
    Node_1 -> Node_2 [label=b]
    Node_17 [label=c]
    Node_1 -> Node_17 [label=c]
    Node_53 [label=d]
    ...
    ...
    Node_448 -> Node_449 [label=c]
    Node_450 [label=i]
    Node_449 -> Node_450 [label=i]
    Node_451 [label=t,fillcolor=lightgreen]
    Node_450 -> Node_451 [label=t]
}

Code:

trie.c:

#undef _POSIX_C_SOURCE
#undef _XOPEN_SOURCE

#define _POSIX_C_SOURCE 200819L
#define _XOPEN_SOURCE 700

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>
#include <errno.h>
#include <inttypes.h>

#include <getopt.h>

#define IO_IMPLEMENTATION
#define IO_STATIC
#include "io.h"

#define PROGRAM_NAME    "auto-complete"
#define OUTPUT_DOT_FILE "graph.dot"
#define AC_BUFFER_CAP   1024 * 2

struct flags {
    bool kflag;                 /* Keep the transient .DOT file. */
    bool hflag;                 /* Help message. */
    bool sflag;                 /* Generate a .SVG file. */
    bool cflag;                 /* Suggest autocompletions. */
    bool pflag;                 /* Prefix for the .DOT file. */
};

#ifdef DEBUG
#include "size.h"
#define debug_printf(fmt, ...) \
    fprintf(stdout, "%s:%d:%s(): " fmt, __FILE__, __LINE__, \
            __func__, __VA_ARGS__)
#define D(x) x
#else
#define D(x) (void) 0
#endif

static void help(FILE *sink)
{
    fprintf(sink, "\nUSAGE\n"
        "\t" PROGRAM_NAME " [OPTIONS] [filename]\n\n"
        "DESCRIPTION\n"
        "\t" PROGRAM_NAME
        " is a program for auto-completion and graph visualization.\n\n"
        "OPTIONS:\n" "\t-k, --keep\t\tKeep the transient .DOT file.\n"
        "\t-h, --help\t\tDisplay this help message and exit.\n"
        "\t-s, --svg \t\tGenerate a .SVG file (with optional prefix).\n"
        "\t-c, --complete PREFIX   Suggest autocompletions for prefix.\n"
        "\t-p, --prefix PREFIX\tPrefix for the .DOT file.\n\n");
    exit(EXIT_SUCCESS);
}

static void usage_err(const char *prog_name)
{
    fprintf(stderr, "The syntax of the command is incorrect.\n"
        "Try %s -h for more information.\n", prog_name);
    exit(EXIT_FAILURE);
}

static void parse_options(const struct option * long_options,
                          struct flags *        opt_ptr, 
                          int                   argc, 
                          char **restrict       argv,
                          const char **restrict prefix)
{
    int c = 0;
    int err_flag = 0;

    while (true) {
        c = getopt_long(argc, argv, "shkc:p:", long_options, NULL);
        
        if (c == -1) {
            break;
        }

        switch (c) {
            case 'k':
                ++err_flag;
                opt_ptr->kflag = true;
                break;
            case 'h':
                help(stdout);
                break;
            case 's':
                if (opt_ptr->cflag) {
                    fprintf(stderr,
                        "Error: -s/--svg specified after -c/--complete.\n");
                    usage_err(argv[0]);
                }

                if (opt_ptr->pflag) {
                    --err_flag;
                }

                if (opt_ptr->kflag) {
                    --err_flag;
                }

                opt_ptr->sflag = true;
                break;
            case 'c':
                if (opt_ptr->sflag) {
                    fprintf(stderr,
                        "Error: -c/--complete specified after -s/--svg.\n");
                    usage_err(argv[0]);
                }

                *prefix = optarg;

                if (strlen(*prefix) >= AC_BUFFER_CAP) {
                    fprintf(stderr, "Error: PREFIX too long.\n");
                    exit(EXIT_FAILURE);
                }

                opt_ptr->cflag = true;
                break;
            case 'p':
                if (!opt_ptr->sflag) {
                    err_flag = true;
                }

                *prefix = optarg;
                opt_ptr->pflag = true;
                break;

                /* case '?' */
            default:
                usage_err(argv[0]);
        }
    }

    /* If the -p or -k flag was specified without -s: */
    /* Note: GNU provides an extension for optional arguments, which
     *       can be used to provide an optional prefix for -s. */
    if (err_flag) {
        if (opt_ptr->pflag) {
            fputs("Error: -p specified without -s.\n", stderr);
        }

        if (opt_ptr->kflag) {
            fputs("Error: -k specified without -s.\n", stderr);
        }
        usage_err(argv[0]);
    }
}

/* Instead of using the whole ASCII charset, we'd only use the set of printable
 * characters. This cuts down the struct size from 2056 bytes to 768 bytes if 
 * using 64-bit pointers, or from 1028 bytes to 384 bytes if using 32-bit integers.
 * (or so pahole outputs, there might be a slight difference in the size across 
 * different platforms).
 */

#define CHILDREN_COUNT 95

/* In the children array, 32 should map to 0, 65 should map to 33, and so on. */
#define ASCII_OFFSET ' '        /* ASCII code: 32, start of printable characters. */

/* This wastes half the indexing range. Perhaps we can use uint32_t instead of
 * int32_t, and use UINT32_MAX as the sentinel value.
 */
#define INVALID_OFFSET -1

#define INITIAL_POOL_CAP 1024 * 2

typedef struct {
    /* TODO: This still wastes a lot of memory. Something like Pythons's dict 
     * would be better. Explore the idea of using a dynamically growing 
     * hash-table for Node.children. 
     */

    /* We shall store indices within the `Trie.pool` array instead of storing
     * huge word size pointers. This also simplifies serializing and
     * deserializing the structure.
     *
     * See also: A case where int32_t wasn't sufficient - bbc.com/news/world-asia-30288542
     */
    int32_t children[CHILDREN_COUNT];
    bool terminal;
} Node;

struct Trie {
    Node *pool;
    int32_t count;
    int32_t capacity;
} Trie; 

static bool init_pool(void)
{
    Trie.pool = malloc(sizeof *Trie.pool * INITIAL_POOL_CAP);

    if (Trie.pool == NULL) {
        perror("malloc()");
        return false;
    }

    return Trie.capacity = INITIAL_POOL_CAP;
}

static inline void free_pool(void)
{
    Trie.capacity = 0;
    Trie.count = 0;
    free(Trie.pool);
}

static int32_t alloc_node(void)
{
    if (Trie.count >= Trie.capacity) {
        const int32_t remaining = INT32_MAX - Trie.capacity;

        /* We can no longer add more nodes. Bail out. */
        if (remaining == 0) {
            /* Is this helpful? */
            fputs("Error: too many nodes. Consider recompiling the program"
                "with a greater int width for more indexing range.\n", stderr);
            exit(EXIT_FAILURE);
        }

        Trie.capacity += remaining < INITIAL_POOL_CAP ? remaining : INITIAL_POOL_CAP;
        void *const tmp = realloc(Trie.pool, sizeof *Trie.pool * (size_t) Trie.capacity);

        if (tmp == NULL) {
            perror("realloc()");
            return INVALID_OFFSET;
        }

        Trie.pool = tmp;
    }

    Node *const tmp = &Trie.pool[Trie.count];

    memset(tmp->children, INVALID_OFFSET, sizeof tmp->children);
    Trie.pool[Trie.count].terminal = false;
    return Trie.count++;
}

static bool insert_text(int32_t root_idx, const char *text)
{
    while (*text != '\0') {
        const int32_t idx = *text - ASCII_OFFSET;

        if (Trie.pool[root_idx].children[idx] == INVALID_OFFSET) {
            const int32_t tmp = alloc_node();

            if (tmp == INVALID_OFFSET) {
                return false;
            }

            Trie.pool[root_idx].children[idx] = tmp;
        }
        root_idx = Trie.pool[root_idx].children[idx];
        ++text;
    }

    return Trie.pool[root_idx].terminal = true;
}

static char ac_buffer[AC_BUFFER_CAP];
static size_t ac_buffer_sz;

static void ac_buffer_push(char ch)
{
    /* No check here, for we would have exited in parse_options() if the length
     * of the prefix was greater than AC_BUFFER_CAP.
     */
    ac_buffer[ac_buffer_sz++] = ch;
}

static void ac_buffer_pop(void)
{
    if (ac_buffer_sz > 0) {
        ac_buffer_sz--;
    }
}

static int32_t find_prefix(int32_t root_idx, const char *prefix)
{
    while (*prefix != '\0') {
        const int32_t child_idx = *prefix - ASCII_OFFSET;

        if (Trie.pool[root_idx].children[child_idx] == INVALID_OFFSET) {
            return INVALID_OFFSET;
        }

        root_idx = Trie.pool[root_idx].children[child_idx];
        ac_buffer_push(*prefix);
        ++prefix;
    }
    return root_idx;
}

static void dump_dot_prefix(FILE *sink, int32_t root_idx)
{
    for (size_t i = 0; i < CHILDREN_COUNT; ++i) {
        if (Trie.pool[root_idx].children[i] != INVALID_OFFSET) {
            const int32_t child_index = Trie.pool[root_idx].children[i];

            if (Trie.pool[child_index].terminal) {
                fprintf(sink,
                    "\tNode_%" PRId32 " [label=%c,fillcolor=lightgreen]\n",
                    child_index, (char) (i + ASCII_OFFSET));
            } else {
                fprintf(sink, "\tNode_%" PRId32 " [label=%c]\n", child_index,
                    (char) (i + ASCII_OFFSET));
            }

            fprintf(sink, "\tNode_%" PRId32 " -> Node_%" PRId32 " [label=%c]\n",
                root_idx, child_index, (char) (i + ASCII_OFFSET));
            dump_dot_prefix(sink, Trie.pool[root_idx].children[i]);
        }
    }
}

static void dump_dot_whole(FILE *sink)
{
    for (int32_t i = 0; i < Trie.count; ++i) {
        const int32_t index = i;

        for (size_t j = 0; j < CHILDREN_COUNT; ++j) {
            if (Trie.pool[i].children[j] != INVALID_OFFSET) {
                const int32_t child_index = Trie.pool[i].children[j];

                if (Trie.pool[child_index].terminal) {
                    fprintf(sink,
                        "\tNode_%" PRId32 " [label=%c,fillcolor=lightgreen]\n",
                        child_index, (char) (j + ASCII_OFFSET));
                } else {
                    fprintf(sink, "\tNode_%" PRId32 " [label=%c]\n",
                        child_index, (char) (j + ASCII_OFFSET));
                }

                fprintf(sink,
                    "\tNode_%" PRId32 " -> Node_%" PRId32 " [label=%c]\n",
                    index, child_index, (char) (j + ASCII_OFFSET));
            }
        }
    }
}

static void print_suggestions(int32_t root_idx)
{
    if (Trie.pool[root_idx].terminal) {
        fwrite(ac_buffer, ac_buffer_sz, 1, stdout);
        fputc('\n', stdout);
    }

    for (size_t i = 0; i < CHILDREN_COUNT; ++i) {
        if (Trie.pool[root_idx].children[i] != INVALID_OFFSET) {
            ac_buffer_push((char) (i + ASCII_OFFSET));
            print_suggestions(Trie.pool[root_idx].children[i]);
            ac_buffer_pop();
        }
    }
}

static bool populate_trie(int32_t root_idx, char **lines, size_t num_lines)
{
    for (size_t i = 0; i < num_lines; ++i) {
        if (!insert_text(root_idx, lines[i])) {
            return false;
        }
    }
    return true;
}

static bool generate_graph(void)
{
    if (system("dot -Tsvg " OUTPUT_DOT_FILE " -O")) {
        fprintf(stderr, "Error: failed to generate the .SVG file, %s.\n",
            strerror(errno));
        return false;
    }

    return true;
}

static bool generate_dot(int32_t root_idx, const char *prefix)
{
    FILE *const sink = fopen(OUTPUT_DOT_FILE, "w");

    if (sink == NULL) {
        perror("fopen()");
        return false;
    }

    fprintf(sink, "digraph Trie {\n"
        "\tnode [fillcolor=lightblue,style=filled,arrowhead=vee,color=black]\n"
        "\tNode_%" PRId32 " [label=%s]\n", root_idx, prefix ? prefix : "root");

    root_idx == 0 ? dump_dot_whole(sink) : dump_dot_prefix(sink, root_idx);
    fprintf(sink, "}\n");
    return !fclose(sink);
}

static bool process_args(int32_t                root_idx,
                         const struct flags *   options, 
                         const char *restrict   prefix,
                         const char *restrict   out_file)
{
    bool rv = true;

    /* Handle --complete first as we are going to modify root later in case
     * prefix is not a null pointer. 
     */
    if (options->cflag) {
        const int32_t subtree_idx = find_prefix(root_idx, prefix);

        if (subtree_idx == INVALID_OFFSET) {
            fprintf(stderr, "Error: Unable to find prefix.\n");
            rv = !rv;
            goto cleanup;
        }

        print_suggestions(subtree_idx);
    }

    if (options->sflag) {
        if (prefix) {
            const int32_t subtree_idx = find_prefix(root_idx, prefix);

            if (subtree_idx == INVALID_OFFSET) {
                fprintf(stderr, "Error: Unable to find prefix.\n");
                rv = !rv;
                goto cleanup;
            }
            root_idx = subtree_idx;
        }

        if (!generate_dot(root_idx, prefix)
            || !generate_graph()) {
            rv = !rv;
        }
    }

  cleanup:
    if (!options->kflag) {
        remove(out_file);
    }

    return rv;
}

int main(int argc, char *argv[])
{

    /* Sanity check. POSIX requires the invoking process to pass a non-NULL 
     * argv[0]. 
     */
    if (!argv[0]) {
        fprintf(stderr,
            "A NULL argv[0] was passed through an exec system call.\n");
        return EXIT_FAILURE;
    }

    static const struct option long_options[] = {
        { "keep", no_argument, NULL, 'k' },
        { "help", no_argument, NULL, 'h' },
        { "svg", no_argument, NULL, 's' },
        { "complete", required_argument, NULL, 'c' },
        { "prefix", required_argument, NULL, 'p' },
        { NULL, 0, NULL, 0 },
    };

    FILE *in_file = stdin;
    struct flags options = { false, false, false, false, false };
    const char *search_prefix = NULL;

    parse_options(long_options, &options, argc, argv, &search_prefix);

    if (options.sflag || options.cflag) {
        if ((optind + 1) == argc) {
            in_file = fopen(argv[optind], "r");
            if (in_file == NULL) {
                perror(argv[optind]);
                return EXIT_FAILURE;
            }
        }
    } else {
        usage_err(PROGRAM_NAME);
    }

    if (optind > argc) {
        usage_err(PROGRAM_NAME);
    }

    size_t nbytes = 0;
    char *const content = io_read_file(in_file, &nbytes);
    size_t nlines = 0;
    char **lines = io_split_lines(content, &nlines);

    if (lines == NULL) {
        free(content);
        perror("fread()");
        return EXIT_FAILURE;
    }

    bool rv = true;
    int32_t root_idx = INVALID_OFFSET;

    if (!init_pool()
        || (root_idx = alloc_node()) == INVALID_OFFSET
        || !populate_trie(root_idx, lines, nlines)) {
        rv = !rv;
        goto cleanup;

    }

    D(
        char *const total = calculate_size((size_t) Trie.capacity * sizeof *Trie.pool);
        char *const used = calculate_size((size_t) Trie.count * sizeof *Trie.pool);

        debug_printf("Total lines read: %zu.\n" "Total nodes allocated: %"
                    PRId32 ".\n" "Total nodes used: %" PRId32 ".\n"
                    "Total memory allocated: %s.\n" "Total memory used: %s.\n",
                    nlines, 
                    Trie.capacity, 
                    Trie.count, 
                    total, 
                    used); 
        /* free(total); */
        /* free(used); */
    );
    
    rv = process_args(root_idx, &options, search_prefix, OUTPUT_DOT_FILE);

  cleanup:
    /* We're exiting. There's no need of freeing memory. */
    /* free_pool();                /1* NO-OP if init_pool() returns false. *1/ */
    /* free(content); */
    /* free(lines); */

    if (in_file != stdin) {
        fclose(in_file);
    }

    return rv ? EXIT_SUCCESS : EXIT_FAILURE;
}

size.h:

#ifndef SIZE_H
#define SIZE_H 1

#include <stdint.h>

char *calculate_size(uint64_t size);

#endif                          /* SIZE_H */

size.c:

#include "size.h"

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

#define ARRAY_CARDINALITY(x) (sizeof(x) / sizeof (*(x)))

static const char *const sizes[] =
    { "EiB", "PiB", "TiB", "GiB", "MiB", "KiB", "B" };
static const uint64_t exbibytes =
    1024ULL * 1024ULL * 1024ULL * 1024ULL * 1024ULL * 1024ULL;

/* Acknowledgements:
 * @Jonathan Leffer - [Converting a number of bytes into a file size in C]
 * (https://stackoverflow.com/q/3898840/20017547)
 */
char *calculate_size(uint64_t size)
{
    char *const result = malloc(32);

    if (!result) {
        return NULL;
    }

    uint64_t multiplier = exbibytes;

    for (size_t i = 0; i < ARRAY_CARDINALITY(sizes); ++i, multiplier /= 1024) {
        if (size < multiplier) {
            continue;
        }

        if (size % multiplier == 0) {
            sprintf(result, "%" PRId64 " %s", size / multiplier, sizes[i]);
        } else {
            sprintf(result, "%.1lf %s", (double) size / (double) multiplier,
                sizes[i]);
        }
        return result;
    }

    return strcpy(result, "0");
}

#ifdef TEST_MAIN
int main(void)
{
    static const uint64_t list[] = {
        0, 1, 2, 34, 900, 1023, 1024, 1025, 2048, 1024 * 1024,
        1024 * 1024 * 1024 + 1024 * 1024 * 400
    };

    for (size_t i = 0; i < ARRAY_CARDINALITY(list); ++i) {
        char *const str = calculate_size(list[i]);

        if (!str) {
            perror("malloc()");
            return EXIT_FAILURE;
        }

        printf("%18" PRId64 " = %s\n", list[i], str);
        free(str);
    }

    return EXIT_SUCCESS;
}
#endif

io.h:

#ifndef IO_H
#define IO_H

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>

/* 
 * To use, do this:
 *   #define IO_IMPLEMENTATION
 * before you include this file in *one* C to create the implementation.
 *
 * i.e. it should look like:
 * #include ...
 * #include ...
 *
 * #define IO_IMPLEMENTATION
 * #include "io.h"
 * ...
 * 
 * To make all functions have internal linkage, i.e. be private to the source
 * file, do this:
 *  #define `IO_STATIC` 
 * before including "io.h".
 *
 * i.e. it should look like:
 * #define IO_IMPLEMENTATION
 * #define IO_STATIC
 * #include "io.h"
 * ...
 *
 * You can #define IO_MALLOC, IO_REALLOC, and IO_FREE to avoid using malloc(),
 * realloc(), and free(). Note that all three must be defined at once, or none.
 */

#ifndef IO_DEF
    #ifdef IO_STATIC
        #define IO_DEF  static
#else
    #define IO_DEF  extern
    #endif              /* IO_STATIC */
#endif                  /* IO_DEF */

#if defined(__GNUC__) || defined(__clang__)
    #define ATTRIB_NONNULL(...)             __attribute__((nonnull (__VA_ARGS__)))
    #define ATTRIB_WARN_UNUSED_RESULT       __attribute__((warn_unused_result))
    #define ATTRIB_MALLOC                   __attribute__((malloc))
#else
    #define ATTRIB_NONNULL(...)             /* If only. */
    #define ATTRIB_WARN_UNUSED_RESULT       /* If only. */
    #define ATTRIB_MALLOC                   /* If only. */ 
#endif                          /* defined(__GNUC__) || define(__clang__) */

/* 
 * Reads the file pointed to by `stream` to a buffer and returns it.
 * The returned buffer is a nul-terminated string.
 * If `nbytes` is not NULL, it shall hold the size of the file. Otherwise it
 * shall hold 0.
 * 
 * Returns NULL on memory allocation failure. The caller is responsible for
 * freeing the returned pointer.
 */
IO_DEF char *io_read_file(FILE *stream, size_t *nbytes)
    ATTRIB_NONNULL(1) ATTRIB_WARN_UNUSED_RESULT ATTRIB_MALLOC;

/* 
 * Splits a string into a sequence of tokens. The `delim` argument 
 * specifies a set of bytes that delimit the tokens in the parsed string.
 * If `ntokens` is not NULL, it shall hold the amount of total tokens. Else it
 * shall hold 0.
 *
 * Returns an array of pointers to the tokens, or NULL on memory allocation
 * failure. The caller is responsible for freeing the returned pointer.
 */
IO_DEF char **io_split_by_delim(char *restrict s, const char *restrict delim,
    size_t *ntokens) 
    ATTRIB_NONNULL(1, 2) ATTRIB_WARN_UNUSED_RESULT ATTRIB_MALLOC;

/* 
 * Splits a string into lines.
 * A wrapper around `io_split_by_delim()`. It calls the function with "\n" as
 * the delimiter.
 *
 * Returns an array of pointers to the tokens, or NULL on memory allocation
 * failure. The caller is responsible for freeing the returned pointer.
 */
IO_DEF char **io_split_lines(char *s, size_t *nlines)
    ATTRIB_NONNULL(1) ATTRIB_WARN_UNUSED_RESULT ATTRIB_MALLOC;

/* 
 * Reads the next chunk of data from the stream referenced to by `stream`.
 * `chunk` must be a pointer to an array of at least size IO_CHUNK_SIZE. 
 *
 * If `size` is a non-null pointer, it'd hold the size of the chunk, else it
 * would hold 0 on failure.
 *
 * Returns a pointer to the chunk on success, or NULL elsewise. The returned
 * chunk is null-terminated.
 *
 * `io_read_next_chunk()` does not distinguish between end-of-file and error; the
 * routines `feof()` and `ferror()` must be used to determine which occured.
 */
IO_DEF char *io_read_next_chunk(FILE *stream, char *chunk, size_t *size)
    ATTRIB_NONNULL(1, 2) ATTRIB_WARN_UNUSED_RESULT;

/* 
 * Reads the next line from the stream pointed to by `stream`. The returned line 
 * is terminated and does not contain a newline, if one was found.
 *
 * The memory pointed to by `size` shall contain the length of the 
 * line (including the terminating null character). Else it shall contain 0.
 *  
 * Upon successful completion a pointer is returned and the size of the line is 
 * stored in the memory pointed to by `size`, otherwise NULL is returned and
 * `size` holds 0.
 * 
 * `io_read_line()` does not distinguish between end-of-file and error; the routines
 * `feof()` and `ferror()` must be used to determine which occurred. The
 * function also returns NULL on a memory-allocation failure. 
 *
 * Although a null character is always supplied after the line, note that
 * `strlen(line)` will always be smaller than the value is `size` if the line
 * contains embedded null characters.
 */
IO_DEF char *io_read_line(FILE *stream, size_t *size)
    ATTRIB_NONNULL(1, 2) ATTRIB_WARN_UNUSED_RESULT ATTRIB_MALLOC;

/*
 * `size` should be a non-null pointer. On success, the function assigns `size`
 * with the number of bytes read and returns true, or returns false elsewise.
 * The function also returns false if the size of the file can not be
 * represented.
 *
 * Note: The file can grow between io_fsize() and a subsequent read.
 */
IO_DEF bool io_fsize(FILE *stream, uintmax_t *size) 
    ATTRIB_NONNULL(1, 2) ATTRIB_WARN_UNUSED_RESULT;

/* 
 * Writes `lines` to the file pointed to by `stream`.
 * A wrapper around 
 * On success, it returns true, or false elsewise.
 */
IO_DEF bool io_write_lines(FILE *stream, size_t nlines, char *lines[const static nlines]) 
    ATTRIB_NONNULL(1, 3);

/* 
 * Writes nbytes from the buffer pointed to by `data` to the file pointed to 
 * by `stream`. 
 *
 * On success, it returns true, or false elsewise.
 */
IO_DEF bool io_write_file(FILE *stream, size_t nbytes, const char data[static nbytes]) 
    ATTRIB_NONNULL(1, 3);

#endif                          /* IO_H */

#ifdef IO_IMPLEMENTATION

#if defined(IO_MALLOC) != defined(IO_REALLOC) || defined(IO_REALLOC) != defined(IO_FREE)
    #error  "Must define all or none of IO_MALLOC, IO_REALLOC, and IO_FREE."
#endif

#ifndef IO_MALLOC
#define IO_MALLOC(sz)       malloc(sz)
#define IO_REALLOC(p, sz)   realloc(p, sz)
#define IO_FREE(p)          free(p)
#endif

#undef _POSIX_C_SOURCE
#define _POSIX_C_SOURCE 200809L

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

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

#define IO_CHUNK_SIZE          ((size_t)1024 * 8)
#define IO_TOKEN_CHUNK_SIZE    ((size_t)1024 * 2)

#define GROW_CAPACITY(capacity, initial) \
        ((capacity) < initial ? initial : (capacity) * 2)

IO_DEF char *io_read_file(FILE *stream, size_t *nbytes)
{
    char *content = NULL;
    size_t len = 0;
    size_t capacity = 0;

    if (nbytes) {
        *nbytes = 0;
    }

    for (size_t rcount = 1; rcount > 0; len += rcount) {
        capacity = GROW_CAPACITY(capacity, IO_CHUNK_SIZE);

        void *const tmp = IO_REALLOC(content, capacity + 1);

        if (tmp == NULL) {
            IO_FREE(content);
            return NULL;
        }
        content = tmp;
        rcount = fread(content + len, 1, capacity - len, stream);

        if (rcount < capacity - len) {
            if (!feof(stream)) {
                IO_FREE(content);
                return content = NULL;
            }
            /* If we break on the first iteration. */
            len += rcount;
            break;
        }
    }

    if (nbytes) {
        *nbytes = len;
    }
    content[len] = '\0';
    return content;
}

IO_DEF char **io_split_by_delim(char *restrict s, const char *restrict delim,
    size_t *ntokens)
{
    char **tokens = NULL;
    size_t capacity = 0;
    size_t token_count = 0;

    if (ntokens) {
        *ntokens = 0;
    }

    while (s != NULL && *s != '\0') {
        if (token_count >= capacity) {
            capacity = GROW_CAPACITY(capacity, IO_TOKEN_CHUNK_SIZE);
            char **const tmp = IO_REALLOC(tokens, sizeof *tokens * capacity);

            if (tmp == NULL) {
                IO_FREE(tokens);
                return NULL;
            }
            tokens = tmp;
        }
        tokens[token_count++] = s;
        s = strpbrk(s, delim);

        if (s) {
            *s++ = '\0';
        }
    }

    if (ntokens) {
        *ntokens = token_count;
    }
    return tokens;
}

IO_DEF char **io_split_lines(char *s, size_t *nlines)
{
    return io_split_by_delim(s, "\n", nlines);
}

IO_DEF char *io_read_next_chunk(FILE *stream, char *chunk, size_t *size)
{
    if (size) {
        *size = 0;
    }
    
    const size_t rcount = fread(chunk, 1, IO_CHUNK_SIZE, stream);

    if (rcount < IO_CHUNK_SIZE) {
        if (!feof(stream)) {
            /* A read error occured. */
            return NULL;
        }

        if (rcount == 0) {
            return NULL;
        }
    }
    
    chunk[rcount] = '\0';

    if (size) {
        *size = rcount;
    }

    return chunk;
}

IO_DEF char *io_read_line(FILE *stream, size_t *size)
{
    size_t count = 0;
    size_t capacity = 0;
    char *line = NULL;

    for (;;) {
        if (count >= capacity) {
            capacity = GROW_CAPACITY(capacity, BUFSIZ);
            char *const tmp = realloc(line, capacity + 1);

            if (tmp == NULL) {
                free(line);
                return NULL;
            }

            line = tmp;
        }

        const int c = getc(stream);

        if (c == EOF || c == '\n') {
            if (c == EOF) {
                if (feof(stream)) {
                    if (!count) {
                        free(line);
                        return NULL;
                    }
                    /* Return what was read. */
                    break;
                }
                /* Read error. */
                free(line);
                return NULL;
            } else {
                break;
            }
        } else {
            line[count] = (char) c;
        }
        ++count;
    }

    /* Shrink line to size if possible. */
    void *const tmp = realloc(line, count + 1);

    if (tmp) {
        line = tmp;
    }

    line[count] = '\0';
    *size = ++count;
    return line;
}

/* 
 * Reasons to not use `fseek()` and `ftell()` to compute the size of the file:
 * 
 * Subclause 7.12.9.2 of the C Standard [ISO/IEC 9899:2011] specifies the
 * following behavior when opening a binary file in binary mode:
 * 
 * >> A binary stream need not meaningfully support fseek calls with a whence 
 * >> value of SEEK_END.
 *
 * In addition, footnote 268 of subclause 7.21.3 says:
 *
 * >> Setting the file position indicator to end-of-file, as with 
 * >> fseek(file, 0, SEEK_END) has undefined behavior for a binary stream.
 *
 * For regular files, the file position indicator returned by ftell() is useful
 * only in calls to fseek. As such, the value returned may not be reflect the 
 * physical byte offset. 
 *
 */
bool io_fsize(FILE *stream, uintmax_t *size)
{
/*
 *   Windows supports fileno(), struct stat, and fstat() as _fileno(),
 *   _fstat(), and struct _stat.
 *
 *   See: https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/fstat-fstat32-fstat64-fstati64-fstat32i64-fstat64i32?view=msvc-170
 */

#ifdef _WIN32
    #define fileno _fileno
    #ifdef _WIN64
        #define fstat  _fstat64
        #define stat   __stat64
    #else
        /* Does this suffice for a 32-bit system? */
        #define fstat  _fstat
        #define stat   _stat
    #endif                          /* WIN64 */
#endif                              /* _WIN32 */

/* According to https://web.archive.org/web/20191012035921/http://nadeausoftware.com/articles/2012/01/c_c_tip_how_use_compiler_predefined_macros_detect_operating_system
 * __unix__ should suffice for IBM AIX, all distributions of BSD, and all
 * distributions of Linux, and Hewlett-Packard HP-UX. __unix suffices for Oracle
 * Solaris. Mac OSX and iOS compilers do not define the conventional __unix__,
 * __unix, or unix macros, so they're checked for separately. WIN32 is defined
 * on 64-bit systems too.
 */
#if defined(_WIN32) || defined(__unix__) || defined(__unix) || (defined(__APPLE__) && defined(__MACH__))
    struct stat st;

    /* rewind() returns no value. */
    rewind(stream);

    if (fstat(fileno(stream), &st) == 0) {
        *size = (uintmax_t) st.st_size;
        return true;
    }
    return false;
#else
    /* Fall back to the default and read it in chunks. */
    uintmax_t rcount = 0;
    char chunk[IO_CHUNK_SIZE];

    /* rewind() returns no value. */
    rewind(stream);

    do {
        rcount = fread(chunk, 1, IO_CHUNK_SIZE, stream);

        if ((*size + rcount) < *size) {
            /* Overflow. */
            return false;
        }
        *size += rcount;
    } while (rcount == IO_CHUNK_SIZE);
    return !ferror(stream);
#endif                          /* defined(_WIN32) || defined(__unix__) || defined(__unix) || (defined(__APPLE__) && defined(__MACH__)) */
#undef fstat
#undef stat
#undef fileno
}

IO_DEF bool io_write_lines(FILE *stream, size_t nlines, 
        char *lines[const static nlines])
{
    for (size_t i = 0; i < nlines; ++i) {
        if (fprintf(stream, "%s\n", lines[i]) < 0) {
            return false;
        }
    }

    return true;
}

IO_DEF bool io_write_file(FILE *stream, size_t nbytes,
    const char data[static nbytes])
{
    return fwrite(data, 1, nbytes, stream) == nbytes;
}

#undef ATTRIB_NONNULL
#undef ATTRIB_WARN_UNUSED_RESULT
#undef ATTRIB_MALLOC
#undef TOKEN_IO_CHUNK_SIZE
#undef GROW_CAPACITY
#endif                          /* IO_IMPLEMENTATION */

#ifdef TEST_MAIN

#include <assert.h>

int main(int argc, char **argv)
{
    if (argc != 2) {
        fputs("Error: file argument missing.\n", stderr);
        return EXIT_FAILURE;
    }

    FILE *fp = fopen(argv[1], "r");
    if (!fp) {
        perror(argv[1]);
        return EXIT_FAILURE;
    }
    
    size_t nbytes = 0;
    char *const fbuf = io_read_file(fp, &nbytes);
    assert(fbuf && nbytes);
    assert(io_write_file(stdout, nbytes, fbuf));
    rewind(fp);

    size_t size = 0;
    bool rv = io_fsize(fp, &size);
    assert(rv);
    printf("Filesize: %zu.\n", size);

    size_t nlines = 0;
    char **lines = io_split_lines(fbuf, &nlines);
    assert(lines && nlines);
    assert(io_write_lines(stdout, nlines, lines));

    printf("Lines read: %zu.\n", nlines);

    for (size_t i = 0; i < nlines; ++i) {
        if (lines[i][0]) {
            size_t ntokens = 0;
            char **tokens = io_split_by_delim(lines[i], " \t", &ntokens);
            assert(tokens && ntokens);
            assert(io_write_lines(stdout, ntokens, tokens));
            free(tokens);
        }
    }
    
    rewind(fp);
 
    /* This can be allocated dynamically on the heap too. */
    char chunk[IO_CHUNK_SIZE];
    char *p = chunk;
    size_t chunk_size = 0;

    while ((p = io_read_next_chunk(fp, chunk, &chunk_size))) {
        printf("Read a chunk of size: %zu.\n", chunk_size); 
        puts(chunk);
    }
    
    rewind(fp);

    char *line = NULL;
    size_t line_size = 0;

    while ((line = io_read_line(fp, &line_size))) {
        line[strcspn(line, "\n")] = '\0';
        printf("Read a line of size: %zu.\n", line_size); 
        puts(line);
        putchar('\n');
        free(line);
    }

    free(fbuf);
    free(lines);    
    fclose(fp);
    
    return EXIT_SUCCESS;
}

#endif                          /* TEST_MAIN */

And here's the makefile for the project:

CFLAGS  = -std=c17
CFLAGS  += -no-pie
CFLAGS  += -ftrapv
CFLAGS  += -Wall
CFLAGS  += -Wextra
CFLAGS  += -Warray-bounds
# CFLAGS    += -Wconversion
CFLAGS  += -Wmissing-braces
CFLAGS  += -Wno-unused-function
CFLAGS  += -Wno-parentheses
CFLAGS  += -Wno-format-truncation
CFLAGS  += -Wno-type-limits
CFLAGS  += -Wpedantic
CFLAGS  += -Wstrict-prototypes
CFLAGS  += -Wwrite-strings
CFLAGS  += -Winline
CFLAGS  += -D_FORTIFY_SOURCE=2

BIN          := trie
INSTALL_PATH := /usr/local/bin
SRCS         := trie.c 

ifeq ($(MAKECMDGOALS),debug)
SRCS += size.c
endif

all: CFLAGS += -s -O2
all: $(BIN)

debug: CFLAGS += -g3 -ggdb -fanalyzer -DDEBUG
debug: $(BIN)

$(BIN): $(SRCS)

install: $(BIN)
    install $< $(INSTALL_PATH)

uninstall:
    rm $(INSTALL_PATH)/$(BIN)

clean:
    $(RM) $(BIN) 

.PHONY: all debug clean install uninstall 
.DELETE_ON_ERROR:

The code was formatted with GNU Indent, compiles without any warnings with Clang, GCC, and MinGW on FreeBSD 14.0, Linux Mint 21.2, and Windows 10.0, and reports nothing awry under valgrind.

Although I did have to use gmake on FreeBSD because of some non-standard GNU extensions.

You could also clone this github repository: trie

Test run:

Here are the results of a sample run:

>> free && sync && echo 3 >| /proc/sys/vm/drop_caches && free

>> time ./trie --complete tran ~/data-set/wordlists/huge.txt 1> /dev/null
./trie --complete tran ~/data-set/wordlists/huge.txt > /dev/null  0.19s user 0.57s system 97% cpu 0.775 total

>> wc ~/data-set/wordlists/huge.txt
172819  172820 1916146 

Review Goals:

I am mainly interested in getting trie.c reviewed.

  • Do you see any issues with the design/structure of the program?
  • Does any part of my code exhibit undefined/implementation-defined behavior?
  • General coding comments, style, et cetera.

Do you have a faster alternative to Graphviz dot to suggest?

It would have been better to have a separate interface for the trie implementation, but as it is too coupled now, I have decided to leave it as it is, seeing that the trie implementation is specific to this application and I do not intend to reuse it.

\$\endgroup\$
3
  • \$\begingroup\$ How do I embed the SVG into the post? \$\endgroup\$
    – Harith
    Feb 15 at 10:58
  • 1
    \$\begingroup\$ You could add a Stack Snippet which has HTML/CSS support. \$\endgroup\$
    – ggorlen
    Feb 15 at 16:14
  • \$\begingroup\$ @ggorlen Thank you for the link. A raw github link did the job for me. \$\endgroup\$
    – Harith
    Feb 20 at 16:50

1 Answer 1

4
\$\begingroup\$

In alloc_node, you're missing a space between these two literals (at the end of the first or beginning of the second):

"Error: too many nodes. Consider recompiling the program"
"with a greater int width for more indexing range.\n"

free_pool would probably be safer if it assigned Trie.pool = NULL at the end.

This partly a matter of taste, but I find that address-of-index expressions like

&Trie.pool[Trie.count]

are more simply expressed as

Trie.pool + Trie.count

insert_text can re-express its loop as a for:

for (; *text != '\0'; ++text)

Expand

return Trie.pool[root_idx].terminal = true;

to

Trie.pool[root_idx].terminal = true;
return true;

As you've done elsewhere, convert ac_buffer_sz--; to pre-decrement style.

Good use of PRId32.

When you use the flags structure, it's more convenient to use the typedef syntax than using the non-typedef struct name.

io.h is very long and tricky. This kind of thing is often needed in C, but it should be captured in a library (yours or a third party). I don't like it but the language doesn't give you much choice.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.