Offset-Indexed TRIE’s

type ymo_trie_node_t

Typedef forward declarations for translation units that don’t need defs:

Definition

typedef struct ymo_trie_node ymo_trie_node_t;

struct ymo_trie_node

Node type for an uncompressed trie.

Definition

struct ymo_trie_node {
    struct ymo_trie_node* children[YMO_TRIE_NO_CHILDREN];
    size_t                index;
    size_t                value_id;
    unsigned char         value;
};

struct ymo_trie

Uncompressed trie type. Used to construct lookup tables, but not to perform lookups.

Definition

struct ymo_trie {
    ymo_trie_node_t* root;
    size_t           no_nodes;
    size_t           no_values;
};

struct ymo_oitrie_node

Compressed trie node type.

Definition

struct ymo_oitrie_node {
    uint8_t              flags;
    ymo_trie_id_t        hdr_id;
    ymo_oitrie_offset_t  offset;
    unsigned char        value; /* Char value at this node */
};

ymo_trie_t *ymo_trie_create(void)

Create an uncompressed trie.

void ymo_trie_free(ymo_trie_t *root)

Release an umcompressed trie.

ymo_status_t ymo_trie_add_string(ymo_trie_t *trie, const char *str_in)

Add a string to the trie.

ymo_trie_node_t *ymo_trie_node_create(void)

Create a node for an uncompressed trie.

void ymo_trie_node_free(ymo_trie_node_t *root)

Free an uncompressed child node and all it’s child nodes.

ymo_oitrie_t *ymo_oitrie_create(ymo_trie_t *trie)

Create a compressed trie from an uncomprssed trie.

Note

This is a destructive action. All the nodes in the input trie are freed.

size_t ymo_oitrie_sizeof(const ymo_oitrie_t *oitrie)

Return the total number of bytes consumed by the oitrie.

void ymo_oitrie_free(ymo_oitrie_t *oitrie)

Free a compressed trie.

ymo_status_t ymo_oitrie_get_id(int *hdr_id, const ymo_oitrie_t *restrict oitrie, register const char *restrict str_in)

Given an input string, return the string id.