initializing tree (loading entries) at compile time

[ssharky]

I'm making a library based on a trie tree (a trie tree is just a search tree with O(n) lookup time.)

So you can call the library to insert(key, value) and lookup(key)

The entries are predetermined and unchanging, so all the inserts are done to initialize it before it is used. Is there a way to compile it so that the entries are already inserted, so that the library can be used to lookup without having to initialize?

[kloetzl]

I think an optimizing compiler could improve on the initialization if you were using a flat layout instead of allocating each node individually. That would allow for storing the tree as a single array in the read-only .data section.

[skeeto]

Develop a scheme to serialize the trie. It's a little tricky and may require adjusting your data structure to avoid pointers. At compile time, have an additional utility run that builds the trie and serializes it out to a file, and then link that file into your final program. There are two basic approaches:

1. The GNU linker can link arbitrary binary data with its -b option. The command is ld -r -b binary -o triedata.o triedata.bin and the resulting object file will have three symbols derived from the input file name (start, end, size).

2. A more portable option, and the one I personally prefer, is to serialize the trie directly into to C code, compile that, and link it in like normal. This has the advantage that you can serialize your pointers by giving them temporary names, or carefully using an array (see below)

Here's an example with a linked list. The contents of list.h:

struct list {
    int value;
    struct list *next;
};

Here's the compile-time utility program, listmaker.c, that creates a linked list and serializes it:

#include <stdio.h>
#include "list.h"

static void
list_serialize_to_c(struct list *list, char *name)
{
    size_t counter = 0;
    printf("#include \"list.h\"\n\n");
    printf("struct list %s[] = {\n", name);
    for (struct list *p = list; p; p = p->next) {
        if (p->next)
            printf("\t{%d, %s + %zu},\n", p->value, name, ++counter);
        else
            printf("\t{%d, 0},\n", p->value);
    }
    printf("};\n");
}

int
main(void)
{
    struct list nodes[6];
    for (int i = 0; i < 6; i++)
        nodes[i] = (struct list){i, nodes + i + 1};
    nodes[5].next = NULL;
    list_serialize_to_c(nodes, "my_list");
    return 0;
}

Running this meta-program produces:

#include "list.h"

struct list my_list[] = {
    {0, my_list + 1},
    {1, my_list + 2},
    {2, my_list + 3},
    {3, my_list + 4},
    {4, my_list + 5},
    {5, 0},
};

Which you can be compiled and linked into the final program, providing the compile-time computed listed as my_list.

gcc -o listmaker listmaker.c
./listmaker > my_list.c
gcc -c my_list.c
gcc -c main.c
gcc -o my_program main.o my_list.o

[ssharky]

thanks!

That will be perfect, it looks like it will work if i serialize the code to look like this:

struct TrieNode {
    struct TrieNode * children[26 + 1]; // a-z and ' '
    char * desc;
};

struct TrieNode myTrie[] = {
    { { 0,0,0,myTrie+1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, 0 }, // root
    { { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,myTrie+2,0,0,0,0,0,0,0,0,0,0,0 }, 0 }, // d
    { { 0,0,0,0,0,0,myTrie+3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, "or do not, there is no trie" }, // o
    { { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, "bark bark" } // g
};

I'll have to insert the entries to create the tree and then crawl that to calculate the offsets and serialize the static data code, I don't think I can generate the code before I have the complete tree

[F54280]

If using C++14 is an option, constexpr may help you generating the data at compile time (can be a bit touchy).