AxlRadixTree – Radix Tree

See AxlData – Data Structures for an overview of all data modules including the radix tree (compact prefix tree).

Header: <axl/axl-radix-tree.h>

API Reference

Typedefs

typedef struct AxlRadixTree AxlRadixTree

Functions

AxlRadixTree *axl_radix_tree_new(void)

Create a new radix tree.

Values are not freed on removal or tree destruction.

Returns:

new AxlRadixTree, or NULL on allocation failure.

AxlRadixTree *axl_radix_tree_new_full(AxlDestroyNotify value_free)

Create a new radix tree with a value destructor.

Parameters:

  • value_free – value destructor, or NULL

Returns:

new AxlRadixTree, or NULL on allocation failure.

void axl_radix_tree_free(AxlRadixTree *tree)

Free a radix tree and all entries.

Calls value_free on each entry’s value (if set).

Parameters:

  • tree – radix tree (NULL-safe)

int axl_radix_tree_insert(AxlRadixTree *tree, const char *key, void *value)

Insert or replace a key-value pair.

If the key already exists, the old value is freed via value_free (if set) and replaced with the new value.

Parameters:

  • tree – radix tree

  • key – string key (copied internally)

  • value – value pointer

Returns:

0 on success, -1 on allocation failure.

void *axl_radix_tree_lookup(AxlRadixTree *tree, const char *key)

Exact lookup of a key.

Parameters:

  • tree – radix tree

  • key – key to look up

Returns:

value pointer, or NULL if not found.

void *axl_radix_tree_lookup_prefix(AxlRadixTree *tree, const char *key, const char **suffix)

Longest-prefix lookup.

Finds the longest inserted key that is a prefix of key and returns its value. Sets *suffix to point into key at the first character after the matched prefix. The caller can compute the prefix length as *suffix - key.

On no match, *suffix is not modified. Pass NULL for suffix if the suffix pointer is not needed.

Parameters:

  • tree – radix tree

  • key – key to match against

  • suffix – receives pointer into key after matched prefix

Returns:

value pointer, or NULL if no prefix matches.

bool axl_radix_tree_remove(AxlRadixTree *tree, const char *key)

Remove a key.

Calls value_free on the value (if set). Collapses intermediate nodes with a single child.

Parameters:

  • tree – radix tree

  • key – key to remove

Returns:

true if removed, false if not found.

size_t axl_radix_tree_size(AxlRadixTree *tree)

Get the number of entries.

Parameters:

  • tree – radix tree

Returns:

entry count.

void axl_radix_tree_foreach(AxlRadixTree *tree, AxlHashTableForeachFunc func, void *data)

Iterate all entries in depth-first order.

The key passed to func is a reconstructed NUL-terminated string valid only for the duration of the callback.

Parameters:

  • tree – radix tree

  • func – callback(key, value, data)

  • data – opaque data passed to callback