Array of all possible edges [version 1]

The simplest solution is to store all possible pointers to children nodes in array of constant size. C-structure:

struct TrieNode {
        /* user data */

        struct TrieNode* children[256];
}

Procedure that returns child node or NULL depending on a letter works in constant time:

TrieNode* NEXT(TrieNode* node, uint8_t letter) {
        return node->children[letter]
}

Pointer to array of all possible edges [version 1a]

Instead of a static array of pointers allocate such array only when needed, i.e. leaf nodes don't occupy much memory. This cost additional test when accessing children.

Node structure:

struct TrieNode {
        /* user data */

        struct TrieNode** children;
}

Next function:

TrieNode* NEXT(TrieNode* node, uint8_t letter) {
        if (node->children)
                return node->children[letter];
        else
                return NULL;
}

Pointer to array of limited set of edges [version 1b]

Do not store the array of all possible pointers, but only a continuous range between first and last non-null pointer.

Node structure:

struct TrieNode {
        /* user data */

        uint8_t lo;
        uint8_t hi;
        struct TrieNode** children;
}

The array has size hi - lo + 1.

Next function:

TrieNode* NEXT(TrieNode* node, uint8_t letter) {
        if (node->children) {
                if (letter >= node->lo and letter <= node->hi)
                        return node->children[letter - node->lo];
                else
                        return NULL;
        }
        else
                return NULL;
}

Pointer to array of limited set of edges — lookup tables

This method extends 1b approach. The size of chars set stored in entire trie may be smaller than 256, for example words in english dictionary contains small and big letters and apostrophe, i.e. about 53 chars. Thus the size of array in each node could be much smaller, with cost of additional translation table(s).

Such translation tables can be applied for all nodes or be specific for nodes at the same depth. Sample functions retrieving a child node:

TrieNode* NEXT(TrieNode* node, uint8_t letter) {
        const uint16_t L = trie->translate[letter];
        if (L == trie->INVALID_LETTER)
                return NULL;
        else
                return node->children[L]
}


TrieNode* NEXT(TrieNode* node, uint8_t letter) {
        /* depth could be parameter of function! */
        const size_t depth = get_depth(node);

        const uint16_t L = trie->translate[depth][letter];
        if (L == trie->INVALID_LETTER)
                return NULL;
        else
                return node->children[L]
}

Dynamic table of pointers [version 2]

Dynamic table of pointers — store only non-null pointers. This require store also size of a table and a edge label.

struct TrieNode {
        /* user data */

        uint8_t letter; // edge label
        uint16_t n;             // array size
        TrieNode** children;    // array
}

Procedure returns next node:

TrieNode* g(TrieNode* node, uint8_t letter) {
        int i;
        const int n = node->n;
        for (i=0; i < n; i++)
                if (node->child[i]->letter == letter)
                        return node->child[i];

        return NULL;
}

struct TrieNode {
        /* user data */

        uint8_t letter;
        uint16_t n;
        union {
                TrieNode*       single_child;   // valid when n = 1
                TrieNode**      ptr_array;
        }
}

Linked list of pointers [version 2b]

Use single-linked list instead of dynamic table. This requires also store a letter (label's edge) on a list.

struct TrieNode {
        /* user data */

        ListItem* head;
};

ListItem {
        uint8_t         letter;
        TrieNode*       child;
        ListItem*       next;
};

Procedure returns next node:

TrieNode* g(TrieNode* node, uint8_t letter) {
        ListItem* item = node->head;

        while (item) {
                if (item->letter == letter)
                        return item->child;
                else
                        item = item->next;
        }

        return NULL
}

Table of letters and pointers [version 3]

The dynamic table require two memory reads: the first gets a pointer to child, then get a letter from a child. In this representation letters are separated from the node structure and saved in front of the table of pointers. Sample memory layout for node with 3 children:

|     letters   |       pointers        |
+---+---+---+---+-------+-------+-------+
| a | b | c | _ | ptr_0 | ptr_1 | ptr_2 |
+---+---+---+---+-------+-------+-------+
  0   1   2   x     0       1       2     <- index

Letters area has size rounded to alignment, in this case 4 bytes.

Structure of node is simple:

struct TrieNode {
        /* user data */

        uint16_t n;
        void* children;
}

Procedure returns next node:

TrieNode* NEXT_v3(TrieNode* node, uint8_t letter) {
        const int n = node->n;
        const letters_size = round_up(n, aligment);

        char* letters =
                (char*)(node->children);

        TrieNode* pointers =
                (TrieNode*)(node->children + letters_size);

        /* find index */
        for (i=0; i < n; i++)
                if (chars[i] == letter)
                        return pointers[i];

        return NULL;
}

struct TrieNode {
        /* user data */

        uint16_t n;
        uint8_t  byte0; // n == 1 or n == 2
        uint8_t  byte1; // n == 2
        void*    children;
}

TrieNode* NEXT(TrieNode* node, uint8_t letter) {
        const int n = node->n;
        switch (n) {
                case 0:
                        return NULL;

                case 1:
                        if (node->byte0 == letter)
                                return (TrieNode**)(node->children)[0];
                        else
                                return NULL;

                case 2:
                        if (node->byte0 == letter)
                                return (TrieNode**)(node->children)[0];
                        else if (node->byte1 == letter)
                                return (TrieNode**)(node->children)[1];
                        else
                                return NULL;

                default:
                        return NEXT_v3(node, letter);
        }
}

Table of letters, children count and pointers [version 3b]

A modification of the previous scheme — move counter n to a dynamic array. Also type of n could be change to uint8_t. If node has no children, then pointer is NULL, and n never get value 0, so we have values ouside range 1..256.

Structure of node is simple:

struct TrieNode {
        /* user data */

        void* children;
}

Procedure returns next node:

TrieNode* NEXT(TrieNode* node, uint8_t letter) {
        const int n = (uint_8)(node->children[0]);
        const letters_size = round_up(n, aligment);

        char* letters =
                (char*)(node->children + 1);

        TrieNode* pointers =
                (TrieNode*)(node->children + letters_size + 1);

        /* find index */
        for (i=0; i < n; i++)
                if (chars[i] == letter)
                        return pointers[i];

        return NULL;
}

Sample memory layout for node with 3 children:

| n |  letters  |       pointers        |
+---+---+---+---+-------+-------+-------+
| 3 | a | b | c | ptr_0 | ptr_1 | ptr_2 |
+---+---+---+---+-------+-------+-------+
      0   1   2     0       1       2     <- index

Array of children nodes [version 4]

Instead of storing pointers to children it's possible to store all children nodes in a single array and save only one pointer to that array.

Structure of node:

struct TrieNode {
        /* user data */

        uint16_t  n
        uint8_t   letter;
        TrieNode* array;
}

struct TrieNode {
        /* user data */

        uint32_t        letter:8;       // 8-bit for letter
        uint32_t        eol:1;          // 1-bit for End-of-list marker
        uint32_t        index:23;       // index of subarray of children
}

TrieNode nodes[k];

TrieNode* NEXT(TrieNode* node, const uint8_t letter) {
        if (node->index == 0)
                return NULL;

        TrieNode* children = &nodes[index];
        size_t i = 0;

        while (1) {
                if (children[i].letter == letter)
                        return &children[i];
                else {
                        if (children[i].eol)
                                // last element of array
                                return NULL;
                        else
                                i += 1;
                }
        }
}

Table of letter and array of children nodes [version 4a]

This is merge of version 4 and version 3b — children nodes are saved in an array (v4), a children counter and edge lables are also stored in the table (v3b).

Structure of node:

struct TrieNode {
        /* user data */

        uint8_t* array;
}

(Pseudo)structure od array:

pseudostruct array {
        uint8_t n;
        uint8_t letters[n];
        uint8_t __alignment__[?];

        TrieNode next[n];
}

Procedure returns next node:

TrieNode* NEXT(TrieNode* node, uint8_t letter) {
        const int n = (int)(node->array[0]);
        const letters_size = round_up(n + 1, aligment);

        char* letters =
                (char*)(node->array + 1);

        TrieNode* next =
                (TrieNode*)(node->array + letters_size);

        /* find index */
        for (i=0; i < n; i++)
                if (letters[i] == letter)
                        return &next[i];

        return NULL;
}

Experiments

Two representations were tested with the English dictionary:

• linked list — separate stack-based memory pools for nodes and for list elements (both served 1024 elements per arena);
• dynamic array — stack-based memory pool for nodes (1024 elements per arena) and bitmap-based allocator for arrays elements (256 elements per arena).